Устройство для моделирования сетевых графиков Советский патент 1980 года по МПК G06G7/48 

Изобретение относится к области вычислительной техники, в частности, к электронным моделирующим устройствам, и может быть использовано при построении цифровых специализированных машин для решения задач исследован1 я операций. Известно устройство для моделирования путей в графе, содержащее триг геры, формирователь временного интер вала, задатчики адресов и элементы И 1. Недостатком известного устройства является большой расход оборудования Наиболее близким по технической сущности к предложенному изобретению является устройство для моделирования сетевых графиков, содержащее блок моделей ребер по числу работ исследуемого графика, каждая из которых выполнена в виде первого и второго задатчиков адресов, выход второго задатчика адреса подключен к первому входу первого элемента И, выход которого соединен с первым входсян элемента ИЛИ, второй вход которого подключен к выходу элемента НЕ, вход которого соединен с выходом второго задатчика адреса, пе вого триггера, первый выход которого подклкзчен ко второму входу первого элемента И, второй выход первого триггера соединен с первым входом второго элемента И, выход которого подключен к первому входу формирователя временнЕдх интервалов, выход которого соединен с первыми входами первого и второго триггеров, блок формирования топологии, выполненный в виде первого элемента ИЛИ, входы которого соединены с выходами вторых триггеров всех модулей ребер, выход первого элемента ИЛИ через элемент НЕ подключен к первому входу первого элемента И, выход которого соединен со вторыми входами формирователей временных интервалов всех моделей ребер, выход первого элемента ИЛИ подключен к первому входу второго элемента И, выход которого соединен с первым входом второго элемента ИЛИ, выход которого подключен ко входам первого и второго задатчиков адресов всех моделей ребер, третьего элемента И, входы которого соединены с выходами элементов ИЛИ всех моделей ребер, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ, выход которого соединен со вторыми входами вторых элементов и всех моделей ребер, генератор импульсов, первый к второй выходы КОТОРОГО подключены соответственно ко вторым входам первого и второго элементов И блока формировани-я топологии, блок управления, первый выход которого соединен со вторым входом второго элемента ИЛИ блока ф мирования топологии, второй выход блока управления подключен ко второ му входу третьего элемента ИЛИ блока формирования топологии, выход которого соединен со входом блока управления 2, Недостатком известного устройства являются узкие функциональные возможности. Цель изобретения - расширение класса решаемых задач за счет обеспечения ассоциативного поиска и сокращение оборудования. Поставленная цель достигается , тем, что во все модели ребер введены первый и второй блоки сравнения, третий и четвертый триггеры, третий и четвертый элементы И, а в блок формирования топологии дополнительно введен четвертый элемент ИЛИ, причем входы четвертого элемента .ИЛИ блока формирования топологий со динены с выходами третьих элементов И всех моделей ребер, выход четверт.ого элемента ИЛИ блока формирования топологии подключен к первым входам первьйх и вторых блоков сравнения всех моделей ребер, выход первого блока сравнения каждой моде ребер соединен со входом третьего триггера, первый выход которого под ключен к третьему входу элемента ИЛ второй выход третьего триггера соед нен с Третьим входом первого элемента И и с первым входом третьего элемента И, второй вход которого соединен со вторым входом первого блока сравнения и подключен к выходу второго задатчика адреса, третий вход третьегоэлемента И соединен с выходом второго триггера, второй вход которого подключен к выходу четвертого элемента И, первый вход которого соединен со вторым выходом третьего триггера, выход первого задатчика адреса подключен ко второ му входу второго блока сравнения, выход которого соединен со входом четвертого триггера, выход которого подключен к третьему входу второго элемента И, и четвертые входы вторых элементов И всех моделей ребер соединены с третьим выходом блока управления, четвертый выход которого подключен ко вторым входам четвертых элементов И всех моделей. На фиг. 1 изображена функциональ ная схема предложенного устройства; на фиг. 2, 3, 4, 5 показаны фрагмен ты моделируемых графов. Устройство содержит блок 1 моделей ветвей, блок 2 формирования топологии, блок 3 управления, генератор импульсов 4. Каждая модель ветви содержит задатчики 5, б адресов начального и конечного узлов соответственно, выполненные в виде кольцевых сдвиговых регистров (далее называемые ЗАНУ и ЗАКУ), формирователь 7 временных интервалов, триггеры 8-11, блоки сравнения 12, 13, элементы И 14-17, инвертор 18, элемент ИЛИ 19. Блок формирования топологии содержит элементы И 20-22, инвертор 23, элементы ИЛИ 24-27. На фиг. 2а, За, 4а и 5 кружками обозначены узлы графа, стрелками - ветви графа. Номера узлов проставлены над их изображениями. На фиг. 26, 36, 46 показано содержимое, задатчиков адресов начальных и конечных узлов (ЗАНУ или ЗАКУ) в начале цикла. В этих задатчиках отмечен разряд, отведенный для записп логической функции узла (ЛФУ). Не оконченные в рассматриваемый момент времени входящие ветви обозначены на фиг. 2а, За, 4а пунктиром. Работу устройства рассмотрим на примерах. 1. Пусть в графе моделируется кратчайший путь, т.е.. все узлы типа ИЛИ. Пусть узлу 41 (фиг. 2а) инцидентны б ветвей: 3 входящих (Q, ti, с) и 3 выходящих (х, у, z). В ЗАКУ моделей ветвей а,ь,с и в ЗАНУ моделей ветвей X, у, г записан двоичный код числа 41. Содержимое этих задатчиков при условии, что задатчики семиразрядные, приведено на фиг. 26. В седьмом разряде, предназначенном для записи ЛФУ, записан нуль. Работу устройства рассмотрим с момента окончания одной из ветвей, входящих в узел 41 (например, ветви о.) ... В момент окончания формирования временного интервала триггер 8 модели ветви л устанавливается в единицу, и через элемент ИЛИ 24 и инвертор 23 на первый вход элемента И 21 блока формирования топологии подается запрещающий сигнал. Поэтому импульсы серии А перестают поступать на формирователи временных интервалов всех моделей ветвей. Сигнал с выхода элемента ИЛИ 24 разрешает поступление импульсов серии Б на выход элемента И 22 и через элемент ИЛИ 26 - на входы всех задатчиков 5, б. До начала каждого цикла формирования топологии триггеры 10, 11 всех моделей ветвей устанавливаются в единичное состояние (установочные входы на фиг. 1 не показаны). На задатчики начинают поступать импульсы серии Б, сдвигающие вправо содержимое задатчиков. После первого импульса серии Б на выходе ЗАКУ

оделей ветвей CL,. it, с (ЗАНУ модеей ветвей X, у, z ) появляется единичный сигнал. Поскольку на двух входах элемента И 16 модели вети О, присутствуют разрешающие сигналы, этот единичный сигнал через третий вход элемента И 16 поступит, на его вход и на выход элемента ИЛИ 25 блока формирования топологии, откуа он поступает на первые входы блоков сравнения всех моделей ветвей. Поскольку в этот момент единичный сигнал присутствует на выходах ЗАНУ моделей ветвей х/ у, 2, то на выходе блока сравнения 12 упомянутых оделей ветвей будут нулевые сигналы и триггеры 10 тех же моделей останутся в единичнс л состоянии. Триггеры 10 моделей ветвей, на выходе I ЗАНУ которых в этот момент будет нулевой сигнал, сустанавливаются на этом такте в . нулевое состояние (так как на выходах соответствующих блоков сравнения 12 присутствуют единичные сигналы). Аналогично этому, остаются в единичном состоянии триггеры 11 моделей ветвей а, b, с (так как на выходах соответствующих блоков сравнения 13 будут нулевые сигналы). Триггеры 11 моделей ветвей, на выходах ЗАКУ которых в этом такте присутствуют нулевые сигналы, устанавливаются в нулевое состояние. На следующем такте на выходе элемента И 16 модели ветви Q присутствует нулевой сигнал.(так как во втором разряде ЗАКУ модели ветви Остоит нуль). Поскольку ветвь Q - единственная из ветвей, окончившаяся в предыдущем периоде поступления импульсов серии А ( т.е. в рассматриваемом цикле формирования топологии находится в единичном состоянии единственный триггер 8, принадлежащий мо-. дели ветви а), то на выходах всех элементов И 16, а, следовательно, на выходе элемента ИЛИ 25, тоже бужет нулевой сигнал. В этом такте на выходах блоков сравнения 13 (12) моделей ветвей сх, ti, с (х, у, z) тоже будут нулевые сигналы, и триггеры 11 (10) упомянутых моделей ветвей остаются в единичном состоянии. После этого такта в единичном-состоянии остаютсятриггеры 10 (11) тех моделей ветвей, в задатчиках 5(6) которых в первом и втором разрядах справа записана комбинация 01. В нулевом состоянии находятся триггеры 10 (11) тех моделей ветвей, в задатчиках 5 (6) которых в первом и втором разрядах справа записана любая комбина1;ия, отличная от 01 (т.е. 00,11,10). Формирование топологии происходит аналогичным образом в течение последующих четырех тактов. После шестого такта рассматриваемого цикла формирования топологии в единичном состоянии останутся триггеры

11 моделей ветвей а, Ь, с и триггеры 10. моделей ветвей х, у, z.. далее, на седьмом такте, производится формирование логической функции узла. В последнем такте каждого цикла формирования топологии остаются в единичном состоянии триггеры 11 моделей ветвей, входящих в моделируемый узел. Триггеры 11 всех остальных моделей ветвей находятся в нулевом состоянии. В рассматриваемом при0мере в седьмом такте в единичном состоянии находятся триггеры моделей ветвей а, Ь, с. Остальные триггеры 11 находятся в нулевом состоянии, их нулевые выходы через элементы

5 ИЛИ 19 соответствукяцих моделей ветвей обеспечивают наличие единичных сигналов на соответствующих входах элемента И 20 блока формирования топологии. Нулевые сигналы с выходов

0 ЗАКУ мод:елей ветвей о, Ъ, ев седьмом такте через инверторы 18 и элементы ИЛИ I9 также обеспечивают единичные сигьалы на соответствующих входах элемента И 20. Таким образом, в

5 седьмом такте рассматриваемого цикла формигрования топологии на всех входах элемента И 20 блока формирования топологии присутствуют единичные сигналы, вследствие чего на выходе элемента И 20 также присутству0ет единичный сигнал. Этот сигнал через элемент ИЛИ 27 Поступает на первые входи элементов И 14 всех моделей ветвой. Синхронно с последним ицпульсом сдвига в каждом цикле (т.е.

5 в данном блучае синхронно с седьмым импульсом сдвига) блок 3 управления :выдает разрешающий сигнал на вторые :входы элементов И 14 всех моделей ветвей. Поскольку триггеры 10 мо0делей ветвей X, у, z остались в единичном состоянии, а триггеры- 9 тех же моделей ветвей находятся в нулевом состоянии (ветви х, у, z не окончены), то на всех входах эле5ментов И 14 моделей ветвей х, у, z присутству1от единичные сигналы.Следовательно, на выходах упомянутых элементов появляются единичные сигналы, которые поступают на формирователи временных интервалов в моделей

0 ветви X, у, Z, разрешая этим формирователям отсчет импульсов серии А. Через время t , где t пфвмвремя подготовки формирователя к отсчету импульсов серии А, блок 3

5 управления выдает единичный сигнал на первые входы элементов И 15 всех моделей ветвей. Так как триггеры 11 моделей ветвей Q, h, с находятся в единичном состоянии, единичные сиг0налы появляются на выходах упомянутых элементов. Сигнал с выхода элемента И 15 модели ветви D устанавливает триггер 8 модели а в нулевое состояние. Сос Ьяния триггеров 8 мо5делей ветвей Ь и с не изменяются (тси как эти триггеры находятся в нулевом состоянии). Поскольку все триггеры находятся в нулевом состоянии, на выходе элемента ИЛИ 24 появляется ну левой сигнал, который через инвертор 23 и элементы И 21, 22 запрещает пос тупление импульсов серии Б и разреша ет поступление импульсов серии А на модели ветвеЗ. Отсчет импульсов сери А производится всеми формирователями, на которые было подано разрешение, в том числе фо иирователями моделей ветвей х, у, z. Рассмотрим цикла формирования топологии в том случае, когда непос редственно перед его началом одновре менно окончились две ветви, входящие в разные узлы (ветви т, d, входящие в узлы 21 и 49 соответственно фиг. 3). В течение рассматриваемого цикла формирования топологии находятся в единичном состоянии триггеры 8 моделей т, d . Поскольку в первом и втором разрядах справа в ЗАКУ моделей ветвей m и d записана оди наковая комбинация 01 (см. фиг. 36) то первые два такта цикла происходят, как описано выше. На третьем .такте цикла формирования топологии на выходе элемента И 16 моделей ветви m присутствует единичный сигнал (так как триггеры 8 и 11 модели вет ви находятся в единичном состоянии, и в третьем справа разряде ЗАКУ модели ветви m записана единица). Следовательно, единичный сигнал при сутствует также на выходе элемента ИЛИ 25 блока формирования топологии На выходе ЗАКУ модели ветви d в этот момент присутствует нулевой (Сигнал. Поэтому на йыходе блока сра нения 13 модели ветви d появляется единичный сигнал (по первому входу этого элемента от элемента ИЛИ 25 поступает единичный сигнал, по втор му входу от ЗАКУ - нулевой сигнал). Единичный сигнал с выхода блока 13 модели ветви устанавливает в нуль триггер 11 той же модели. Поэтому в течение остальных тактов рассматр ваемого цикла на одном из входов, а следовательно,. на выходе элемента И 16 модели ветви d присутствует нулевой сигнал. Таким образом, далее в этом цикле производится проверка совпадения адресов с конечным адресом ветви m (т.е. с 21). Цикл продолжается и оканчиваетея как описано выше, выдачей разрешения на формирователи моделей г, р, После окончания цикла триггер 8 модели ветви d выходным сигналом элемента И 15 той же модели ветви d не устанавливается в нулевое состоя ние, так как на одном из входов эле мента И 15 той же модели, а, следовательно, и на выходе присутствует нулевой сигнал, обусловленный нуле вым состоянием триггера 11 той же модели. Поэтому единичный сигнал с выхода ; элемента ИЛИ 24 через инвертор 23 по-прежнему запрещает поступление импульсов серии А и разрешает поступление импульсов серии Б на модели ветвей. Таким образом, организуетсяследующий цикл формирования топологии. В этом цикле выбранным адресом, т.е. адресом, с которым производится сравнение, является конечный адрес ветви d (т.е. 49) . Поскольку триггер 8 модели ветви m находится в нулевом состоянии, на выходе элемента И 16 той же модели в течение этого цикла присутствует нулевой сигнал. В конце уцикла поступают разрешающие сигналы на формирователи моделей ветвей f, g. Аналогично производится выбор одного из адресов в каждом цикле, если одновреммно окончилось большее число ветвей. 2. Работа устройства в режиме моделирования длиннейшего пути (т.е., когда в узлах выполняется функция конъюнкции).иллюстрируется фиг. 4а, 46. Пусть моделируется узел 37 (фиг. 4а), и к началу рассматриваемого цикла формирования топологии окончилась одна ветвь - Q. Первые шесть тактов цикла формирования топологии происходит совершенно так же, как описано выше. На седьмом такте цикла формирование топологии на выходах всех элементов ИЛИ 19, кроме элемента ИЛИ 19 модели ветви Ь, присутствуют единичные сигналы. Действительно, после шестого такта формирования топологии.все триггеры 11, кроме триггеров-11 моделей ветвей а, Ь, находятся в нулевом состоянии и единичные сигналы с их нулевых выходов поступают на входы соответствующих элементов ИЛИ 19. На выходе элемента и 17 модели ветви а присутствует единичный си.гнал, так как триггеры 9 и 11 модели ветви а находятся в единичном состоянии, а в седьмом разряде ЗАКУ моделей ветвей а, Ь записана единица. Последнее обуславливает также наличие нулевых сигналов на выходах инверторов 18 моделей ветвей Q, То. Таким образом, на выходе элемента ИЛИ 19 присутствует единичный сигнал, обусловленный единичным сигналом с выхода элемента И 17 той же модели. На выходе элемента И 17 модели ветви в имеется нулевой сигнал,, так как триггер 9 модели ветви Ь находится в нулевом состоянии (ветвь не окончена). Поскольку на остальных входах элемента ИЛИ 19 модели ветви. Ь также имеются нулевые сигналы, на выходе упомянутого элемента также присутствует нулевой сигнал. Таким образом, в этом такте на выходе элемента И 20 блока формирования топологии, а,следовательно, и

на соответствующих входах элементов И 14 всех моделей ветвей присутствуют нулевые сигналы, вследствие чего ча формкрователи моделей ветвей с, d не поступает разрешение на счет импульсов серии А. как описано ранее выходной сигнал элемента И 15 устанавливает в нуль триггер 8 модели ветви а. Поступление импульсов серии Б прекращается, начинается поступление импульсов серии А. Когда формирователь 7 модели ветви в закончит свою работу, в следующем цикле формирования топологии будет снова проверяться адрес 37. Первые шест тактов цикла происходит так описано выше. В седьмом такте на выходе элемента И 17 модели ветви Ъ присутствует единичный сигнал, так как триггер 9 этой модели ветви установился в единичное состояние. Таким образом в этом такте единичные сигналы присутствуют на всех входах элемента И 20, а значит и на его выходе. Следовательно, в этом такте на всех входах элементов И 14 моделей ветвей с имеются разрешающие сигналы и на формирователи упомянутых моделей ветвей поступают сигналы, разрешающие счет импульсов серии А. Таким образом, произошло формирование функции конъюнкции в узле 37 (т.е. разрешение на формирование ветвей с и d выдано только-после того, так окончились ветви а и Ь).

3.Предложенное устройство может также моделировать пути в сложнсм графе, то есть в графе, часть узлов которого выполняет функцию дизъюнкции, а другая часть - функцию конъюнкции. Фрагмент сложного графа показан на фиг. 5. Узлы 15 и 47 - узлы типа И, то есть ветвь е (f) начинается только тогда, когда „окончились ветви а и Ъ (с и d), узел 26 узел типа ИЛИ (т.е. ветвь g начинается, когда окончилась ветвь е или f). Пусть все задатчики адресов-семиразрядные. Тогда в седьмом разряде ЗАКУ (ЗАНУ) моделей ветвей е, t (g) записывается нуль, а в седьмом разряде ЗАКУ (ЗАНУ) моделей ветвей и, ft,

с, d (e,f ) записьшается единица. При моделировании узлов 15 и 47 устройство функционирует, как описано в примере 2, а при моделировании узла 26 - как описано в примере 1.

4.Возможность выполнения устройством ассоциативного поиска рассмотрим на примере поиска по упорядоченной совокупности признаков.

В этом случае формирователи выполняют роль ячеек памяти данных, а ЗАКУ роль ячеек памяти ассоциативных признаков. А именно, каждый разряд ЗАКУ соответствует определенному признаку. Единица в i-M разряде ЗАКУ и ;i-и модели ветви означает, что

информация, хранящаяся в формирователе 7 этой модели ветви, обладает признаком. Например, если в ЗАКУ

j -и модели ветви записан код 00

0101, это означает, что содержимое формирователя облашает первым и третьим признаками.

При установке всех триггеров 8 и 9 в единицу, устройство может производить ассоциативный поиск по различным совокупностям признаков.

0 Если, например, подавать разрешающие сигналы из блока управления на . элементы И 14 синхронно первым и вторым импульсами серии Б в каждом цикле ФоЕ 1ирования топологии, то в

5 первую очередь выбираются формирователи, информация в которых обладает первым и вторым признаками (т.е. формирователи тех моделей ветвей, в ЗАКУ которых записан код 11),

0 далее формирователи моделей ветвей, в ЗАКУ которых записаны коды U1,

10,00. -(Под выбором формирователя понимается подача на его вход разрешающего сигнала с выхода соответ5ствующего элемента И 14). Подобным образом можно организовать ассоциативный поиск информации по другим совокупностям признаков.

Предложенное устройство благодаря

0 наличию новых элемеитов и связей между ними позволяет решать задачу ассоциативного поиска на исследуемом

сетевом графике.

35

Формула изобретения

Устройство для моделирования сетевых графиков , содержащее блок мо0делей ребер по числу работ исследуемого графика, каждая из которых выполнена в виде первого и второго задатчиков адресов, выход второго.задатчика адреса подключен к первому первого элемента И, выхбд

5 которого соединен с первым входом элемента ИЛИ, второй вход которого подключен к выходу элемента НЕ, вход которого соединен с выходом второго задатчика адреса, первого

0 триггера, первый-выход которого подключен ко второму входу первого. элемента И, второй выход первого; триггера соединен с первым входом второго элемента И, выход которого

5 подключен к первому входу формирователя временных интервалов, выход которого соединен с первыми входами первого и второго триггеров, блок формирования топологии, выполненный в

0 виде первого элемента ИЛИ, входы которого соединены с выходами вторых триггеров всех моделей ребер, вьлход первого элемента ИЛИ через элемент НЕ подключен к первому входу перво5го элемента И, выход которого соединен со вторыми входами формирователе временных интервалов всех моделей ре бер, выход первого элемента ИЛИ подключен к первому входу второго элемента И, выход которого соединен с первым входом второго элемента ИЛИ, выход которого подключен ко входам первого и второго задатчиков адресов всех моделей ребер, третьего элемента И, входы которого соединены с выходами элементов ИЛИ всех моделей ребер, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ, выход которого соединен со вторыми входами вторых элементов И всех моделей ребер, генератор импульсов, первый и второй выходы которого подключены соответственно ко вторым входам первого и второго элементов И блока формирования топологии, блок управления, первый выход которого соединен со вторым входом второго, элемента ИЛИ блока формирования топологии, второй выход блока управления подключен ко второму входу третьего элемента ИЛИ блока формирования топологии, выход которого соединен со входом блока управления, отличающееся тем, что, с целью расширения класса решаемых задач за счет ассоциативного поиска и сокращения оборудования эо все модели ребер введены первый и второй блоки сравнения, третий и четвертый триггеры, третий и четвертый элементы И, а в блок формировани топологии дополнительно введен четве тый элемент ИЛИ, прич€яи входы четвертого элемента ИЛИ блока формирования топологии соединены с выходами третьих элементов И всех моделей ребер, четвертого элемента ИЛИ блока формирования топологии подключен к первым входам .первых и вторых блоков сравнения всех моделей ребер, выход первого блока сравнения каждой модели ребра соединен со входом третьего триггера, первый выход которого подключен к третьему входу элемента ИЛИ, второй выход третьего триггера соединен с третьим входом первого элемента И и с первьм входом третьего элемента И, второй вход которого соединен со вторым входом первого блока сравнения и подключен к выходу второго задатчика адреса, третий вход третьего элемента И соединен с выходом второго триггера, второй вход которого подключен к выходу четвертого элемента И, первый вход которого соединен со вторым выходом третьего триггера, выход первого задатчика адреса подключен ко второму входу второго блока сравнения, выход которого соединен со входом четвертого триггера, выход которого подключен к третьему входу второго элемента И, четвертые входы Вторых элементов И всех моделей ребер соединены с третьим выходом блока управления, четвертый выход которого подключен ко вторым входам четвертых элементов И всех моделей ребер. Источники информации, принятые во внимание при экспертизе 1.Авторское, свидетельство СССР по заявке №2199427, 06.07,77. 2.Авторское свидетельство СССР № 422002, кл. G Об G 7/48, 30.03.74 прототип) ,