Устройство для моделирования сетевых графов

(19) (11) 4(51) 6 06 Р 15/20 ОПИСАНИЕ ИЗОБРЕТЕНИЯН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) 1. Авторское свидетельство СССР В 842842, кл. 6 Об С 7/122, 1980.2, Авторское свидетельство СССР по заявке В 3341571, кл. С 06 Р 15/20, 1981 (прототип)(54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее генератор тактовых импульсов, выход которого соединен с информационным входом элемента И, управляющий вход которого является входом запуска устройства, выход элемента И соединен с входом первого триггера группы триггеров, выход счетчика соединен с входом дешифратора, первую группу элементов И, блок формирователей пути, первая группа входов которого соединены с первой группой выходов шифратора, первую группу регистров, выходы всех, кроме последнего, регистров которой подключены к информационным входам элементов И второй группы, треугольную наддиагональную матрицу, включающую группу Ь)11/2 регистров и группы из (й) 11/2 элементов И (где Ь. - количество. вершин графа), выходы каждого регистра группы треугольной наддиагональной матрицы соединены с информационными входами одноименных элементов И группы треугольной наддиагональной матрицы, выходы элементов И группы каждой строки треугольной наддиагональной матрицы соединены с входами одноименного элемента ИЛИ группы И, отличающееся тем, что, с целью упрощения устройства, оно содержит группу элементов И-НЕ и группу суьжаторов, причем выходы всех, кроме первого, элементов ИЛИ группы соединены с первыми входами соответствующих сумматоров группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, выходы сумматоров группы соединены с группой информационных входов шифратора, информационный вход которого соединен с выходом первого элемента ИЛИ группы, вторая группа выходов шифратора соединена с информационными входами соответствующих элементов И-НЕ группы, выходы всех элементов И-НЕ группы подключены к входам всех, кроме первого, регистров группы, выходы дешифратора подключены к второй группе входов блока формирователей пути, к управляющим входам элементов И группы треугольной наддиагональной матрицы, к управляющим входам элементов И-НЕ группы, выход элемента И соединен с входом счетчика с информационными входами элементов И первой группы и с управляющим входом первого элемента И второй группы, выходы элементов И первой группы соединены с управляющими входами остальных элементов И второй группы и с входами соответствующих тригге 4ров, выход . 1 -го триггера группы подключен к управляющему входу ( +1)- го элемента и первой группы.1 1151Изобретение относится к вычислительной технике и может быть использовано при организации вычислительного процесса в диспетчерах управляющих многомашинных вычислительных систем при решении информационно-связанного пакета задач управления объектом или процессом.Известно устройство для определения кратчайшего пути в графе, содер" 1 О жащее блок Управления, генератор тактовых импульсов, счетчики, тригге ры, дифференцирующие цепочки, элементы ИЛИ, элементы НЕ, элементы И с соответствующими связями Я .Недостатком данного устройства является его сложная функциональная структура.Наиболее близким по технической сущности к предложенному является устройство дпя моделирования сетевых граФов, содержащее первую группу из х 1 регистров, образующих треугольную наддиагональную матрицу(=1 в ;=1+1,м)первую группу элемен тов ИЙИ .блок управления и вторую группу регистров, выходы 1 -го регистра второй группы подключены к первым входам-ых элементов И первой группы, вторые входы которых сое. З .динены с соответствующим разрядом первой выходной шины блока управления, 1 -й разряд второй выходной шины которого подключен к нервьщ входам 1 -х элементов И второй группы, выходы которых соединены с35 входами 1-го регистра второй группы, сумматор, блок формирователей шу. ма, блок выбора максимального кода, вторая группа элементов ИЛИ третья группа регистров, третья, четвертая и пятая группа элеиентов И, элементы И, элемент ИЛИ, выход которого подключен к иервьи входам элементов И, вторые входы которых соединены с со.ответствующими разрядами первой вы ходной шины блока управления, выход -го элемента.И подключен к первым входам 1 -х элементов И третьей группы, выходы которых соединены с выходами 1 -го регистра третьей группы, выходы которого подключены к первым1входам 1 -х элементов И четвертой группы выходы которых соединены с входами 1-й группы блока выбора максимального хода, выходы первой груп-пы которого подключены к вторьм входам еоответствующих элементов И второй группы выходы второй 979 2группы блока выбора максимального кода соединены с входами первой груп пы блока формирователей пути, входы второй группы которого подключены к соответствующим разрядам второй выходной шины блока управления, первый выход которого соединен с входом блока формирователей пути, установочные входы регистров третьей группы подключены к второму выходу блока управления, третий выход которого соединен с вторыми входами элементов И четвертой группы, выходы 11. "го регистра первой группы подключены к первым входам 11 -х элементов И пятой группы, выходы которых соединены с 1 -ми входами соответствующих элементов ИЛИ первой группы, выходы которых подключены к входам элемента ИЛИ и к входам первой группы сумматора, выходы которого соединены с вторьки входами соответствующих элементов И третьей группы, 11 -й разряд третьей выходной шины блока управления подключен к вторым входам-х элементов И пятой группы, выходы-х элементов И первой группы соеФдинены с 1 -ми входами соответствующих элемейтов ИЛИ второй группы, выходы которых подключены к входам второй группы сумматора, первый вход блока управления является управляющим входом блока управления, кроме того, блок формирователей пути содержит регистр, первую и вторую группу элементов ИЛИ и треугольную наддиагональную матрицу формирователей пути, каждый 1й ( =1 п =1 11 ьд формирователь пути содержит три элемента И и триггер, вход которого соединен с выходом первого элемента И, единичный и нулевой выходы триггера подключены к первым входам второго и третьего элементов И соответственно выход третьего элемента И (1 1 +1)-го формирователя пути соединей с вторьии входами второго и .третьего элементов И (1+1+1)-го Формирователя пути, вход третьего элемента И (11 +1)-го формирователя пути подключен к входу 1 -го элемента ИЛИ первой группы, выход которого соединен с вторьии входами второго и третьего элементов И формирователя пути, выход второго эле" мента И ( )-го формирователя пути1подключен к входу 1 -го элемента ИЛИ первой группы н к .входу 1 -го эле-мента ИЛИ второй группы, выход кото1151979 40 рого соединен с входом одноименногоразряда регистра, выход первого элемента ИЛИ первой группы подключен квходу первого разряда регистра, вторые входы второго и третьего эпементов И (1,в)-го формирователя путисоединены с входом блока, 1 -й входпервой группы входов которого подключен к первым входам первых элементовИ Формирователей пути 1 -й строки,-й вход второй группы входов блокаподключен к вторым входам первыхэлементов И формирователей пути-гостолбца, кроме того, блок управлениясодержит в+2 триггера, четыре группы 15элементов И, группу инверторов,элемент ИЛИ, элемент И, инвертор, регистр, счетчик, схему сравнения, дешифратор и генератор, выходкоторого. подключен к первому входуэлемента И, второй вход которого соединен с четвертым входом блока, выход элемента И подключен к синхронизирующнм входам триггеров, выходба+2)-го триггера соединен с вторымвходом блока, с информационным вхо.дом первого триггера и со счетнымвходом счетчика, выходы которого подключены к входам первой группы схемы сравнения и к входам дешифратора, 301-и (1=1,щ) выход дешифратора соединен с первым входом-го(1=1+1, в )элемента И первой группы, с первыми входами ( )-х элементов И второй группы, с первым входом-го З 5элемента И третьей группы и через4"й инвертор группы с первым входомФ-го элемента И четвертой группы,выход которого подключен к информационному входу (1+1)-го триггера,выход 1 -го триггера соединен с вторычи входами-х элементов Итретьей и четвертой группы, с вторьгми входами(1)-х элементов И второй группы н с 1 -м разрядом первой 45выходной шины блока, выход (1 )-гоэлемента И второй группы подключенк (1 )-му разряду третьей выходнойшины блока, выходы элементов Итретьей. Группы и выход в-го триггера соединены с соответствующими входами элемента ИЛИ, выход которогоподключен к инФормационному входу(щ+2)-го триггера,. с третьим выхо 4дом блока и с вторыми входами элементов И первой группы, выходы кото рых подключены к соответствующим разрядам группы, выходы которых подключены к соответствующим разрядам второй выходной шины блока, выходы регистра соединены с входами второй выходной шины блока, выходы регистра соединены с входами второй выходной шины блока, выходы регистра соединены с входами второй группы схемы сравнения, выход которой подключен к первому выходу блока и через инвертор к третьему входу элемента И 2 .Недостатком известного устройства является сложная функциональная структура.Цель изобретения - упрощение устройства.Поставленная цель достигается тем, что.устройство для моделирования сетевых графов, содержащее генератор тактовых импульсов, выход которого соединен с информационныч входом элемента И, управляющий вход которого является входом запуска устройства, выход элемента И соединен с входом первого триггера группы триггеров, выход счетчика соединен с входом дешифратора, первую группу элементов И, блок формирователей пути, первая группа входов которого соединена с первой группой выходоы шифратора, первую группу регистров, выходы всех, кроме последнего, регистров которой подключены к информационным входам элементов И второй группы, треугольную иаддиагонапьную матрицу, включающую группу из Й) и/2 регистров и группы из (Г 1-1)О/2 элементов И (где П - количество вершин граФа), выходы каждого регистра группы треугольной наддиагональной матрицы соединены с информационными входами одноименных элементов И группы треугольной наддиагонапьиой матрицы, выходы элементов И группы каждой строки треугольной наддиагоиальиой.матрицы соединены с входами одноийенного элемента ИЛИ групцы И, содержит группу элементов И-НБ и группу сумматоров, причем выходы всех, кроме первого, элементов ИЛИ группы соединены с первычи входами соответствующих 1сумматоров группы, вторые входы ко- .торык подключены к выходам соответствующих элементов И второй группы,выходы сумматоров группы соединеныс группой информационных входов шиАратора, информационнЫй вход которого соединен с выходом первого элемента ИЛИ группы, вторая группа выходов шифратора соединена с информационными входами соответствующихэлементов И-НЕ-группы, выходы всех10элементов И-НЕ группы подключенык входам всех, кроме первого, регистров группы, выходы дешифратора подключены к второй группе входов блока формирователей пути, к управляющим входам, элементов И треугольнойнаддиагональной матрицы к управляющим входам элементов И-ЙЕ группы, выход элемента И соединен с входомсчетчика, информационными входамиэлементов И первой группы и с управляющим входом первого элемента Ивторой группы соединены с управляющими входами остальных элементов Ивторой группы и с входами соответствующих триггеров группы, выход-го триггера группы подключен к управляющему входу ( +1)-го элемента ипервой группы,На Фиг.1 изображено предлагаемое З 0устройство; на Фиг2 и 3 - примерыпостроения функциональных схем блокаФормирователей пути и шифратора,Устройство содержит генератор 1тактовых импульсов, элемент И 2, З 5блок 3 Формирователей пути, счетчик4, дешифратор 5, сумматоры 6бв , где 0 - максимальное количество вершин в графе, группу элементовИЛИ 71. ,7 ь,1, группу элементов И-НЕ 40Зраеу 8 ду Группу регистров 9 уу9 группу элементов И 10110 д.,треугольную наддиагональную матрицу11 у сОстоящую из.Группы реГистров12 .,12 О,1 и группы элементов И 4513,131,1, группу триггеров14,в,,14Группу элементов И15115 ц шиФратор 16, вход 17,Блок 3 формирователей пути (Фнг.2)включает триггеры 18118( )я 0первый 1919.,1, вторые 20,20.,)и третьи элементы И 2121.,1, первую 22122 я, и вторую 23(23, группы элементовИЛИ, регистр 24, входы 2525, 5526126 я и 27.ШиФратор 16 (Фиг.З) включает эле-менты ИЛИ 28 и элементы И 29, входящие в состав узлов 30 130 д,анализа разрядов (в - число разрядов в кодах), включающих схемы поразрядного переноса 31 ,31 щ,элементы ИЛИ-НЕ 32 ,32, выходы 33 1 33 и 34 , 341, )входы 3535,1,В исходном состоянии регистрыц григгеры 1414(Фиг.1) установлены в нулевое состо;яние. На регистрах 121."12(н.1)яматрицы 11 записаны обратные коды1 весов" соответствующих дуг графа,при этом обратный код "веса" путииз первой вершины во вторую записанв регистре 9. Если дуги между какими-либо вершинами графа отсутствуют, то на соответствующих регистрахзаписаны коды нуля.Триггер 18 (Фиг.2) установленв единичное состояние, а триггеры1811 18 ь.,1 и триггеры регистра24 установлены в.нулевое состояние.Работа устройства начинается после подачи на вход 17 высокого потенциала, По этому сигналу первыйимпульс с генератора 1 поступает натриггер 143, который устанавливается в единичное состояние. По это"му же импульсу записывается единицав счетчик 4 и подается разрешающийсигнал на второй вход элемента И10, Код с выхода счетчика 4 (в данном случае код единицы) поступаетна вход дешифратора 5, на первомвыходе которого появляется высокийпотенциал. Этот сигнал подаетсяна вторые входы элементов И-НЕ 3И 1311 и 131, а также по входу 25(фиг.2) на .первые входы элементовИ 191 и 19 блока 3. По этому сигналу код с регистра 1211 поступаетчерез группу элементов И 1311 и группу элементов ИЛИ 71 на первую группу входов шифратора 16, на вторыевходы которого поступает с сумматора б результат сложения кодов с регистра 9 и с регистра 31, на другие входы - нулевые коды с выходомсумматоров 66 ,ПЫфратор работает следующим образом,На входы элементов ИЛИ 28 и И 29схем первого поразрядного узла перекоса по входам 351 ,35,1 поступает (й) кодов, каждый из которыхпредставлен Ф разрядаии. В первыймомент анализируются старшие разряды.всех кодов. Если хотя бы один из старших разрядов кодов равен единице, то на выходе элемента ИЛИ-НЕ 32 появляется низкий потенциал (код1 "О"), который соответствует сигналу запрета при анализе остальных разрядов кодов, старшие разряды которых равны "О". Эти. сигналы форми- руются на выходах элементов ИЛИ 28О и поступают на входы элементов .И 29, Коды, старшие разряды которых равны "1", проходят через элементы И 29 узла 30. Если старшие разряды всех. чисел равны фО", то на выходе элемента ИЛИ-НЕ 32 сформируется "1" благодаря чему обеспечивается разрешение на прохождение остальных разрядов всех кодов через элементы И 29 узла 30. Аналогичным образом анализируются вторые по старшинству разряды всех кодов и т.д., в результате чего на выходах 34 .,34 . сформирован позиционный код номера максимального кода, а на выходах 331,3333сформируется обрат-25 ный код максимального из всех анализируемых кодов, т.е, в данном случае код минимального из чисел, .поступивших на первый и второй входы шифратора 1. Полученный код через О группу элементов И-НЕ 8 записывает ся в регистр 9. Сигналы с выходов 34 шифратора 6 подаются на входы 26 блока 3.Блок 3 формирователей пути слу жит для идентификации вершин модели" руемого графа, составляющих минимальный путь. Блок функционирует следующим образом.Пусть на 1 -м шаГе работы схемы 4 О высокий потенциал появляется на-м выходе шифратора 16 Этот сигнал подается по входу 26на вторые входы элементов И 19,+с, 19 19,. Одновременно с 1 -го выхода де шифратора 5 иа вход 25;, поступает высокий потенциал. Этим сигналом устанавливается в единичное состояние триггер 181. Это свидетельствует о том, что минимальный путь про ходит через (к, +1)-ю вершину графа. Если например,на-й и 1 -й входы шифратора 16 поступают одинаковые (минимальные). коды, то на 1-м и 1 -м .выходах шифратора 16 ноя вятся высокие потенциалы, которые подаются на входы 261 и 26 блока 3, после чего устанавливаются в единичное состояние триггеры 18; и 18( 1.На следующем такте работы устройства устанавливается в единичное состояние триггер 14 , Высокий потенциал подается на вторые входы групп элементов И 1 О и 1 О 1, с второго выхода дешифратора 5 высокий потенциал подается на вторые входы элементов И 1314, 134, 13 и на первые входы элементов 19,4, 19 у 4, 1914 блока 3 (фиг,2). В результате на первую, вторую и третью группы входов шифратора 16 поступают следующие коды: код с выхода регистра 124., результат сложения кодов с регистров 9 н 124, результат сложения кодов с регистров 9 у и 124. В зависимости от результата сравнения на шифраторе 16 устанавливается в единичное состояние триггер 18;4, (т=,1,2,3) блока 3 (фиг.2), а код минимального числа записан на регистр 94.Далее работа устройства происходит аналогично рассмотренному. Например, в 1 -м такте. работы устройства произведено .суммирование содержимого регистров 12 (+1)-го столбца матрицы 11 с содержимым регистров 9 1,.,9 и), содержимое регистра 12,(; ,) подается на вход шифратора 6 чреез группу элементов ИЛИ 7 определен минимальный иэ. кодов и записан на регистр 9 , а один из181( ф 18( ,18+(ф) блока 3 (или несколько триггеров в случае, если на несколько входов шифратора 16 поступят одинаковые коды, что означает - через соответствующие вершины исследуемого графа проходят одинаковые по величине минимальные пути) устанавливается в единичное состояние.Работа устройства продолжается до появления иа и -ом выходе дешифратора высокого потенциала, который поступает по входу 27 блока 3 (фиг.2) на вторые входы элементов И 201 и 21,.Единичные выходы триггеров 18 соединены с первыми входами элементов И 20, а нулевые выходы - с первыми входами элементов И 21. Таким образом если триггер 18 установлен в единичное состояние, то соответствующие ему элемент И 20 открыт, а элемент И 21 закрыт, и на 9 11 оборот. Сигнал опроса, поступаюший на вход 27, проходит через открытые элементы И 211,21, т.е. сначала спрашиваются триггеры П -го столбца блока 3 до тех пор, пока не найден первый триггер 18 установленный в единичное состояние, у которого закрыт элемент И 21; и открыт элемент И 20;, Высоким потенциалом с выхода элемента И 20, через элемент ИЛИ 23 и установлен в единичное состояние и -й триггер регистра 24. Это означает, что и -я вершина моделируемого графа входит в кратчайший путь, и через элемент ИЛИ 22;сигнал опроса поступает на опрос (-1)-го столбца блока 3 (т.е. поступает на вторые входы элементов 20(;+ и 21(. Если же в И -м столбце матрицы 3 ни51979 10 один из триггеров 18 не находится в единичном состоянии, то высокий потенциал с выхода элемента И 21,кчерез элемент 22. поступит на опрос (и)-го столбца (т.е. поступит на вторые входы элементов 20(.,1 и 21(пАналогичным образом опрос продолжается до тех пор, пока не найден 10 триггер 18 , установленный в единичное состояние. Это означает, что1из 1 -й вершины в первую вершину моделируемого графа имеется кратчайший путь. В этом случае установлены, 15 в единичное состояние-й и первыйтриггеры регистра 24, что сигнализирует об окончании моделирования.Введение новых блоков и связеймежду ними позволяет упростить функ циональную схему устройства.1151979 оставитель А.Колчехред Т.Фанта тор А,Обручар едактор. А.Шандо каз 2325/3ВНИИПИ 03 иал ППП "Патент", г. Ужгород, ул. Проектная, 4 Тираж 710Государственного коелам изобретений иосква, Ж, Раушск Подписноемитета СССРоткрытийая наб д, 4/5