SU708367A1 - Устройство дл моделировани сетевых графиков - Google Patents

Description

Изобретение относитс  к области вычислительной техники, в частности, к электронным моделирующим устройствам , и может быть использовано при построении цифровых специализированных машин дл  решени  задач исследован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

Claims (2)

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

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

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

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

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

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