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

11151979J

Изобретение относится к вычисли- группы блока выбора максимального тельной технике и может быть исполь- кода соединены с входами первой групзовано при организации вычислительного процесса в диспетчерах управляющих многомашинных вычислительных систем при решении информационно-связанного пакета задач управления объектом или процессом. Известно устройство для определения кратчайшего пути в графе, содержащее блок управления, генератор ,

тактовых импульсов, счетчики, триггеры, дифференцирующие цепочки, элементы ИЛИ, элементы НЕ, элементы И с соответствующими связями ОJ

Недостатком данного устройства является его сложная функциональная структура.

Наиболее близким по технической сущности к предложенному является устройство для моделирования сетевых графов, содержащее первую группу из UJ регистров, образунищх треугот г; ную наддиагональную матрицу( ,, ; i+t,m), первую группу элементов ИЛИ, блок управления и вторую группу регистров, вьхходы } -го регистра второй группы нодключены к первым входам j -ых элементов И первой группы, вторые входы которых сое .динены с соответствующим разрядом первой выходной щины блока управлекия, i -и разряд второй выходной шины которого подключен к первым входам -X элементов И второй группы, выхода которых соединены с входами J-го регистра второй груп пы, сумматор, блок форьшрователей шу ма, блок выбора максимального кода, вторая группа элементов ИЛИ, третья группа регистров, третья, четвертая и пятая группа элекентов И, элементы И, элемент ИЛИ, выход которого подключен к первьм входам элементов И, вторые входы которых соединены с соответствукяцими разрядами первой выходной шины блока управления, выход 1-го элемента И подключен к перида входам i -X элементов И третьей груп пы, выходы которых соединены с выходами J -го регистра третьей группы, выходы которого подключень к первьи входам f-X элементов И четвертой грзтпы, выхода которьк соединены с входами 4-и группы блока максимального хода, выхбды первой группы которого подключены к вторю входам еоответствукяцих элементов И второй гругаш, выходы второй

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

первым входам ij -х элементов И пятой группы, выходы которьк соединены с iJ -ми входами соответствующих элементов ИЛИ первой группы, выходы которых подключены к входам элемента

ИЛИ и к входам первой группы сумматопы блока формирователей пути, входы второй группы которого подключены к соответствующим разрядам второй выходной шины блока управления, первый выход которого соединен с входом блока формирователей пути, установочные входы регистров третьей группы подключены к второму выходу блока управления, третий выход которого ра, выходы которого соединены с вторьми входами соответствующих элементов И третьей группы, ) -и разряд третьей выходной шины блока управления подключен к вторьм входам ij -х элементов И пятой группы, выходы -X элементов И первой группы соединены с j -ми входами соответствующих элементов ИЛИ второй группы, выходы которьк подключены к входам второй группы сумматора, первьй вход блока управления является управляющим входом блока управления, кроме того. блок формирователей пути содержит регистр, первую и вторую группу элементов ИЛИ и треугольную наддиагональную матрицу формирователей пути, каждьй «i -и (1, j f-f-1 ,m) формирователь пути содержит три элемента И и триггер, вход которого соединен с вькодом первого элемента И, единичный и нулевой выходы Триггера подключены к первьм входам второго и третьего элементов И соответственно, вькод третьего элемента И (| } t)-ro формирователя пути соединен с вторыми входами второго и третьего элементов И (4+1, i+O-ro фop даpoвaтeля пути, вход третьего элемента И ()го 4юрмирователя пути подключен к входу j -го эп&лента ИЛИ первой группы выход которого соединен с вторыми входами второго и третьего элеме|1Тов И формирователя пути, выход второго элемента И (j )-го формирователя пути подключен к входу j -го элемента ИЛИ первой группы и к входу j -го эле- t мента ИЛИ второй группы, выход которого соединен с входом одноименного разряда регистра, выход первого элемента ИЛИ первой группы подключен к входу первого разряда регистра, вторые входы второго и третьего эпементов И (1,т)-го формирователя пути соединены с входом блока, i -и вход первой группы входов которого подклю чен к первым входам первых элементов И формирователей пути л -и строки, -й вход второй группы входов блока подключен к вторым входам первых элементов И формирователей пути -г столбца, кроме того, блок управления содержит т+2 триггера, четьгре группы элементов И, группу инверторов, элемент ИЛИ, элемент И, инвертор, регистр, счетчик, схему сра нения, дешифратор и генератор, выход которого подключен к первому входу элемента И, второй вход которого соединен с четвертым входом блока, выход элемента И подключен к синхрони рукяцим входам триггеров, выход ()-го триггера соединен с вторым входом блока с информационным вхо-дом первого триггера и со счетным входом счетчика, вькоды которого под ключены к входам первой группы схемы сравнения и к входам дешифратора 1 -If ( 1 1 ,rn-1) выход дешифратора сое динен с первым входом -го (j 1+1, m ) элемента И первой группы, с первыми входами (ij)-х элементов И второй группы, с первым входом i -го элемента И третьей г(уппы и через -и инвертор группы с первым входом -го элемента И четвертой группы, выход которого подключен к информационному входу (1+1)-го триггера, выход 1 -го триггера соединен с вторыми входами i -к элементов И /третьей и четвертой группы, с вторы ми входами (ij)-x элементов И второ0 группы и с i -м разрядом перво вькодной шины блока, выход (ij ) -го элемента И второй группы подключен к (||)-му разряду третьей выходной шины блока, выходы элементов И третьей группы и выход т-го тригге ра соединены с соответствукяцими входами элемента ИЛИ, выход которого подключен к информационному входу (m+D-ro триггера, выход которого подключен к информационному входу (П)+2)-Го триггера, выход которого соединен с информационным входом (т+2)-го триггера, с третьим выходом блока и с вторыми входами элементов И первой группы, выходы которых подключены к соответствующим разрядам группы, выходы которых подключены к соответствующим разрядам второй выходной шины блока, выходы регистра соединены с входами второй выходной шины блока, выходы регистра соединены с входами второй выходной шины блока, выходы регистра соединены с входами второй группы схемы сра внения, выход которой подключен к первому выходу блока и через инвертор к третьему входу элемента И 2j , Недостатком известного устройства является сложная функ1щональ- ная структура. Цель изобретения - упрощение уст-- ройства. Поставленная цель достигается тем, что устройство для моделирования сетевых графов, содержащее генератор тактовых импульсов, выход которого соединен с информационньм входом элемента И, управляющий вход которого является входом запуска устройства, выход элемента И соединен с входом первого триггера группы триггеров, выход счетчика соединен с входом дешифратора, первую группу элементов И, блок формирователей пути, первая группа входов которого соединена с первой группой выходоы шифратора, первую группу регистров, выходы всех, кроме последнего, регистров которой подключены к информационным входам элементов И второй группы, треугольную иадциаговальную матрицу, включающую группу из (п-1)- п/2 регистров и группы из (п-1)П/2 элементов И (где Л - количество вершин гра,фа), выходы каждого регистра группы треугольной наддиагональной матрицы соединены с информационньми входами одноименных элементов И группы треугольной наддиагональной матрицы, выходы элементов И группы каждой строки треугольной наддиагональной. матрицы соединены с входами одноименного элемента ЯПИ группы И, содержит элементов И-НЕ и группу сумматоров, причем выходы всех, крсше первого, элементов ИЛИ грзгппы соединены с первыми входами соответствующих сумматоров группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, вьтходы сумматоров группы соединены с группой информационных .входов шиф ратора, информацисннЬяй вход которого соединен с выходом первого элемента ИЛИ группы, вторая группа выходов шифратора соединена с информационными входами соответствующих элементов И-НЕ-группы, выходы всех элементов И-НЕ группы подключены к входам всех, кроме первого, регис тров группы, выходы дешифратора под ключены к второй группе входов блока формирователей пути, к управляющим входам, элементов И треугольной наддиагональной матри1 1 к управляющим входам элементов И-ЙЕ группы, в ход элемента И соединен с входом счетчика, информационными входами элементов И первой группы и с управ лянкцим входом первого элемента И второй группы соединены с управляюп ми входами остальных элементов И второй группы и с входами соответствующих триггеров группы, выход j го триггера группы подключен к упра ляаощему входу (i+D-ro элемента и первой группы. На фиг,1 изобр ажено тредлагаемое устройство; на фиг.2 и 3 - примеры построения функциональных схем блок формирователей пути и шифратора. Устройство содержит генератор 1 тактовых импульсов, элемент И 2, блок 3 формирователей пути, счетчик 4, дешифратор 5, сумматоры б,-. где г - максимальное количест во вершин в графе, группу элементов ИЛИ 7,..,,7д.,, группу элементов И8,...,8д, группу регистров 9,..., 9р, группу элементов И 10 ,..., lO треугольную наддиагональную матрицу 11, состоящую из группы регистров ..., 12( группы элементов И 13,j,..., 13(,,.,„ , группу триггеров 14,,.,., 14„,,, группу элементов И ISj,..., 15,, , шифратор 16, вход 17 Блок 3 формирователей пути (фиг. вктаочает триггеры 18jj,, , 1 %), первый 19,5, VOn 20,, 20(„ и третьи элементм И 21(2,..., .,)д, первую 22,...,22„., и вторую 23(, 4. .,23 группы элементов ИЛИ, регистр 24, входы 25,...,25, 26,,...,26п и 27. Шифратор 16 (фиг.З) включает эле менты ИЛИ 28 и эяементы И 29, входя щие в состав узлов 30,...,30 анализа ра:зрядов (т- число разрядов в кодах), включающих схемы поразрядного переноса 31,,,... ,31 , элементы ИЛИ-НЕ 32,,...,32, , выходы 33 ,... ,33 34,,..., 34 входы 35„,... ,.1) , В исходном состоянии регистры 9;5j..., 9 и триггеры 14, ,..., 14„., (фиг.1) установлены в нулевое состо.яние. На регистрах 1 2,,..., 12 („.,) матрицы 11 записаны обратные коды весов соответствующих дуг графа, при этом обратный код веса пути из первой вершины во вторую записан в регистре 9. Если дуги между какими-либо вершинами графа отсутствуют, то на соответствующих регистрах записаны коды нуля. Триггер 18, (фиг.2) установлен в единичное состояние, а триггеры 18,,.. ., 18((,..,ц и триггеры регистра 24 установлены в.нулевое состояние. Работа устройства начинается после подачи на вход 17 высокого потенциала. По этому сигналу первьй импульс с генератора I поступает на триггер 14, которьй устанавливается в единичное состояние. По этому же импульсу записывается единица в счетчик 4 и подается разрешающий сигнал на второй вход элемента И 10. Код с вьгхода счетчика 4 (в данном случае код единицы) поступает на вход дешифратора 5, на первом выходе которого появляется высокий потенциал. Этот сигнал подается на вторые входы элементов И-НЕ 3 .О И 13| и 13, а также по входу 25 (фиг.2) на первые входы элементов И t9( и 192 блока 3. По этому сигналу код с регистра поступает через группу элементов И группу элементов ИЛИ 7 на первую группу входов шифратора 16, на вторые входы которого поступает с сумматора 6 результат сложения кодов с регистра 9 и с регистра 13, на другие входы - нулевые коды с выходом сумматоров 6,...,6.,. Шифратор работает следующим образом. На входы элементов ИЛИ 28 и И 29 схем первого поразрядного узла переноса по входам 35,.. .,35, поступает (п-1) кодов, каждый из которых представлен m разрядами, В первый момент анализируются старвше разряды всех кодов. Если хотя бы один из старших разрядов кодов равен единице, то на выходе элемента ШИ-НЕ 32 появляется низкий потенциал (код О), который соответствует сигналу запрета при анализе остальных разрядов кодов, старшие разряды которых равны О. Эти :сигналь формируются на выходах элементов ШМ 28 и поступают на входы элементов И 29 Коды старшие разряды которьк равны 1, проходят через элементы И 29 узла 30(. Если старшие разряды всех чисел равны О, то на выходе элемента ШШ-НЕ 32 сформируется 1 благодаря чему обеспечивается разрешение на прохождение остальных разрядов всех кодов через элементы И 29 узла 30(. Аналогичньад образом анализируются вторые по старшинству разряды всех кодов и т.д., в результате чего на выходах 34 ,..., 34 „., сформирован позиционный код номера максимального кода, а на выходах 33,33,...,33 сформируется обрат ный код максимального из всех анализируемых кодов, т.е. в данном слу чае код минимального из чисел, .поступивших на первый и второй входы шифратора 1. Полученный код через группу элементов И-НЕ 8 записывает ся в регистр 9. Сигналы с выходов 34 ш ифратора 16 подаются на входы 26 блока 3. Блок 3 формирователей пути служит для идентификации вершин модели руемого графа, составляющих минимал ный путь. Блок функционирует следую щим образом. Пусть на V-и шаге работы схемы высокий потенциал появляется на к -м выходе шифратора 16. Этот сигнал подается по входу 26 к на вторые входы элементов И 19к, «с+т, к ,с+г 19)f. Одновременно с л -го выхода де шифратора 5 на вход 25,-, поступает высокий потенциал. Этим сигналом устанавливается в единичное состояние триггер t8|;(4. Это свидетельств ет о том, что минимальный путь проходит через (k,i +1)-ю вершину графа. Если например,на j-и и k -и входы шифратора 16 поступают одинаковые (минимальные) коды, то на I j-M и k -м выходах шифратора V6 поя вятся высокие потенциалы, которые подаются на входы 26 у и 26 блока 3, после чего устанавливаются в единичное состояние триггеры 8;jj,,j и , На следующем такте работы устройства устанавливается в единичное состояние триггер 14 . Высокий потенциал подается на вторые входы групп элементов И 10 и 10 , с второго выхода дешифратора 5 высокий потенциал подается на вторые входы элементов И 13,, 13., 13}4 и на первые входы элементов 19, 2 блока 3 (фиг.2).. В результате на первую, вторую и третью группы входов шифратора 16 поступают следующие коды: код с выхода регистра 12|4 , результат сложения кодов с регистров 92 и 12j4 результат сложения кодов с регистров 9 и 12;. В зависимости от результата сравнения на шифраторе 16 устанавливается в единичное состояние триггер 18,(j, (,2,3) блока 3 (фиг.2), а код минимального числа записан на регистр 94 . Далее работа устройства происходит аналогично рассмотренному. Например, в t -м такте- работы устройства произведено суммирование содержимого регистров 12 (+1)-го столбца матрищ 1 11 с содержимым регистров ,... ,9,4.,) , содержимое регистра подается на вход шифратора 16 чреез группу элементов ИЛИ 7 , определен минимальный из кодов и записан на регистр 9,, а один из триггеров 18,(,„, t82(;,,j,...,l8i(,v, блока 3 (или несколько триггеров в случае, если на несколько входов шифратора 16 поступят одинаковые коды, что означает - через соответствующие вершины исследуемого графа проходят одинаковые по величине минимальные пути) устанавливается в единичное состояние. Работа устройства продолжается до появления на п -ом выводе дешифратора высокого потенциала, который поступает по входу 27 блока 3 (фиг.2) на вторые входы элементов И 20,„и 21. Единичные выходы триггеров 18 соединены с первыми входами элементов И 20, а нулевые выходы - с первыми входами элементов И 21. Таким образом если триггер 18 установлен в единичное состояние, то соответствзтеицие &ty элемент И 20 открыт, а элемент И 21 закрыт, и на9оборот. Сигнал опроса, поступающий на вход 27, проходит через открытые элементы И 21.„ ,...,21, , т.е. сначала опрашиваются триггеры П -го столбца блока 3 до тех пор, пока не найден первьш триггер 18 тановленный в единичное состояние, у которого закрыт элемент И 21- и открыт элемент И 20 . Высоким потенциалом с вьскода элемента И 20, через элемент ИЛИ 23 j установлен в единичное состояние п -и триггер регистра 24. Это означает, что ц я вершина моделируемого графа входит в кратчайший путь, и через элемент ИЛИ 22 ,. сигнал опроса поступает н опрос (i-l)-ro столбца блока 3 (т.е. поступает на вторые входы элементов 20(4) и 21(. . Если же в h -м столбце матрицы 3 ни 79 .. 10 один из триггеров 18 не находится в е.диничном состоянии, то высокий потенциал с выхода элемента И 21,„, через элемент 22. поступит на опрос ()-го столбца (т.е. поступит на вторые входы элементов 20д(п-,Ч и 21,1., . Аналогичным образом опрос продолжается до тех пор, пока не найден триггер 181J , установленный в единичное состояние. Это означает, что из j -и вершины в первую вершину моделируемого графа имеется кратчайший путь. В этом случае установлены. в единичное состояние j -и и первый триггеры регистра 24, что сигнализирует об. окончании моделирования. Введение новых блоков и связей между ними позволяет упростить функциональную схему устройства.

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее генератор тактовых импульсов, выход которого соединен с информационньм входом элемента И, управляющий вход которого является входом .запуска устройства, выход элемента И соединен с входом первого триггера группы триггеров, выход счетчика соединен с входом дешифратора, первую группу элементов И, блок формирователей пути, первая группа входов которого соединены с первой группой выходов шифратора, первую группу регистров, выходы всех, кроме последнего, регистров которой подключены к информационным входам элементов И второй группы, трэуголь-ную наддиагонапьную матрицу, включающую группу (г)-1)п/2 регистров и группы из (п-1)п/2 элементов И (где П - количество, вершин графа) , выходы каждого регис.тра группы треугольной наддиагональной матрицы соединены с информационными входами одноименных элементов и группы треугольной наддиагональной матрицы, выходы элементов И группы каждой строки треугольной наддиагональной матрицы соединены с входами одноименного элемента ИЛИ группы И, отлич ающе е ся тем, что, с целью упрощения устройства, оно содержит группу элементов И-НЕ и группу сумматоров, причем выходы всех, кроме первого, элементов ИЛИ группы соединены с первыми входами соответствующих сумматоров группы, вторые входы которых подключены к выходам соответств5пощих элементов И второй группы, выходы сумматоров группы соединены с группой информационных входов шифратора, информационньй вход которого соединен с выходом первого элемента ИЛИ группы, вторая группа выходов шифратора соединена с информационными входами соответствующих элементов И-НЕ группы, выходы всех элементов И-НЕ группы подключены к входам всех, кроме первого, регистров группы, выходы дешифратора подключены к второй группе входов блока формирователей СП пути, к управляющим входам элементов И группы треугольной наддиагональной со матрицы, к управляющ ™ входам элеvj ментов И-НЕ группы, выход элемента И соединен с входом;счетчика с ин- со формационньыи входами лементов И первой группы и с злпфавляю1цим входом первого элемента И второй группы, выходы элементов И первой группы соединены с управляювщми входами остальных элементов И второй группы и с входами соответствующих триггеров, выход J -го триггера группы подключен к управляющему входу Cj+1) - го элемента и первой группы.