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

 

Изобретение относится к обл астй вычислительной техники и может быть применено при исследовании параметров сетевых графов. Цель изобретения состоит в расширении функциональных возможностей за счет определения минимального критического пути. Устройство содержит матрицу n-f п формирователей дуг, каждый из которых состоит из триггера и элемента И-ИЛИ, группу элементов ИЛИi первую группу блоков элементов И, Группу элементов задержки , группу реМстров, группу блоков элементов И-ИЛЙ, вторую группу блоков элементов И, третью группу блоков элементов И, первую группу элементов И, группу триггеров, вторую rpyriny элементов И, сумматор, блок элементов ИЛИ, узел выбора максималь- Hdrd кода, блок элементов И-ИЛИ, геийпульсов, первый элемент И, вычитающий счетчик, первый дешифратор , второй элемент И, суммирующий счетчик, второй дешифратор, третий депшфрато1э, пусковой вход устройства, вход управлений режимами работы устройства . Расшиг)ение функциональных возможностей дЬстигается за счет определения веса И вершин минимального критического пути. I ил. с s (Л (э tsD ОО

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

А1 (5р 4 С 06 Р 15/20

1\ с

Оа

°,а

ЪФ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3699550/24-24 (22) 10.02.84 (46) 30.04.86. Бюл. В 16 (72) Г.С.Евтушенко, В.П.Неверов, В.А.Титов и А.В.Герасименко (53) 681.333(088.8) (56) Авторское свидетельство СССР

N 943738, кл. G 06 F 15/20, 1980.

Авторское свидетельство СССР

NI 1076909, кл. G 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПУТЕЙ В ГРАФАХ (57) Изобретение относится к области вычислительной техники и может быть применено .при исследовании параметров сетевых графов. Цель изобретения состоит в расширении функциональных возможностей за счет определения минимального критического пути. Устройство содержит матрицу n+ n формирователей дуг, каждый из которых состоит

„„SU„„1228112 из триггера и элемента И-ИЛИ, группу элементов ИЛИ, первую группу блоков элементов И, Группу элементов задерж ки, группу реестров, группу блоков элементов И-HJN, вторую группу блоков элементов Й, третью группу блоков элементов И, первую группу элементов И, группу триггеров, вторую группу элементов И, сумматор, блок элементов ИЛИ, узел выбора максимапь. ного кода, блок элементов И-ИЛИ, генератор импульсов, первый элемент И, вычитающий счетчик, первый дешифратор, второй элемент И, суммирующий счетчик, второй дешифратор, третий дешйфратор, пусковой вход устройства, вход управлений режимами работы устройства. Расширение функциональных возможностей достигается sa счет on ределения веса и вершин минимального критического пути. 1 ил.

1 12281

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

Цель изобретения — расширение функциональных возможностей за счет определения минимального критического пути.

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

Устройство содержит матрицу .1 и п (n — число вершин графа) формирователей дуг, каждый из которых включает в себя триггер 2 и элемент

И-ИЛИ 3, группу элементов ИЛИ 4, первую группу блоков элементов И 5, группу элементов 6 задержки, группу регистров 7, группу блоков элементов

И-ИЛИ 8, вторую группу блоков элементов И 9, третью группу блоков элементов И 10 первую группу элементов

И 11, группу триггеров 12, вторую группу элементов И 13, сумматор 14, блок элементов ИЛИ 15, узел 16 выбора максимального кода, блок элементов И-ИЛИ 17, генератор 18 импульсов, первь|й элемент И 19, вычитающий счетчик 20, первый дешифратор 21, второй элемент И 22, суммирующий счетчик 23, второй дешифратор 24, третий дешифратор 25, пусковой вход

26 устройства, вход 27 задания режима, работы устройства.

Узел 16 осуществляет выбор кода максимального числа из поступающих

40 на входы кодов чисел и выдает на выход числа прямой и обратный коды максимального числа, на разрядный выход — позиционный код, в котором единичный сигнал присутствует на по45 зиции, соответствующей номеру входа, по которому подано максимальное число.

Первоначально в матрицу 1 заносится информация о топологии моделируемого графа. При этом триггеры 2, S0 моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 2 определяется пересечением строки с номером, равным номеру начального узла модели55 руемой ветви, и столбца с номером, равным номеру ее конечного узла. В регистры 7 заносятся коды чисел, со12 3 ответствующие весам вершин. В счетчик 20 заносится код числа и вершин ,графа, счетчик 23 находится в нулевом состоянии. При этом исходная информация о графе заносится в модель в порядке, при котором наименьший номер (первый) имеет начальная вершина, а наибольший — конечная вершина, В единичное состояние устанавливается также триггер 12, соответствующий начальной вершине. На вход 27 подается нулевой сигнал, если отыскивается максимальный критический нуль, или единичный сигнал, если отыскивается минимальный критический нуль. Такое занесение исходной информации о графе позволяет использовать процедуру динамического программирования.

Устройство работает следующим образом.

С кодового выхода счетчика 20 код поступает на вход дешифратора

21, в результате чего на одном из его выходов (вначале íà и-м) появит. ся высокий потенциал. В случае, если триггеры 2 в данной строке находятся в единичном состоянии, через соответствующие элементы И-ИЛИ 3 и ИЛИ 4 высокий потенциал с выходов этих триггеров подается на входы соответствующих элементов И 10, что в свою очередь обеспечивает подачу кодов через блок элементов И-ИЛИ 8 с регистров 7 на входы узла 16. Узел 16 обеспечивает выбор из поступивших на ezo вход кодов максимального и выдачу его через блок 17 в прямом или обратН0М коде (в зависимости от возбужденной выходной шины дешифратора 25) на второй вход сумматора 14. Одновременно на первый вход сумматора 14 подается прямой или обратный код с выхода регистра 7„ через соответствующие элементы И-ИЛИ 8, И9 и ИЛИ 15. Результат с выхода сумматора 14 через открытый блок элементов И 5„ (к этому моменту времени на входе блока элементов И 5„ появится высокий потенциал с выхода элемента 6„ задержки) поступит на вход регистра 7 . На этом этап формирования кода максимального (или минимального) пути для и-й отдельной вершины заканчивается.

С появлением пускового сигнала на входе 26 устройства элемент И 19 обес печивает прохождение импульсов с выхода генератора 18 на вход счетчика 20, так как на втором входе эле35

50 э 1228 мента И 19 будет высокий потенциал с выхода счетчика 20, на котором появляется обратный сигнал его нулевого состояния. Когда на вход счетчика 20 поступает первый импульс, возбуждается (n — 1)-й выход дешифратора 21, и процесс формирования величины критического пути для очередной вершины графа будет происходить аналогично.

Вычислительный процесс будет продолжаться до тех пор, пока на счетчике 20 не появится нулевой код, после чего появится нулевой код и появится низкий потенциал на втором входе элемента И.19, а подача импульсов на

15 вход счетчика 20 прекращается. Одновременно высокий потенциал с выхода счетчика 20 обеспечивает выдачу сигналов с выхода генератора 18 через элемент И 22 на вход счетчика 23 со20 ответственно состояниям которого единичные игналы поочередно появляются на выходах дешифратора 24. Если тот или иной триггер 12 находится в единичном состоянии, то высокий потенци25 ал с его выхода через одноименный элемент И 13 будет поступать на входы элементов И-ИЛИ 3 одноименной строки матрицы 1 и далее через элементы ИЛИ 4 на те входы элементов

И 10, которым в данной строке матри30 цы 1 соотв ет ствует дуга графа, т. е. единичное состояние триггера 2. Наличие высоких потенциалов на входах элементов И 10 обеспечивает поступление прямых или обратных кодов, в зависимости от сигнала на входе 27 и выходе дешифратора 25, с выходов регистров 7.через соответствующие блоки элементов И-ИЛИ 8, И 10 на входы узла 1 6,,который обеспечивает 40 выбор максимального кода из поступивших кодов, при этом соответствующие триггеры 12 перебрасываются в единичное состояние импульсом, проходящим через одноименный элемент 45

И 11, и т.д.

Процесс поиска максимального (или минимального) критического пути заканчивается при достижении показания счетчика 23 значения и числа вершин. Единичное состояние триггеров 12 указывает вершины искомого пути, а показания регистров 7 — величины критических путей из соответствующих вершин до и-й вершины графа. 55

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

Устройство для исследования путей в графах, содержащее матрицу и . n

II2 4 (и — число вершин графа) формирователей дуг, состоящих каждый из триггера и элемента И-ИЛИ, группу элементов ИЛИ, группу элементов задержки, первую, вторую и третью группы блоков элементов И, группу триггеров, группу регистров, блок элементов ИЛИ сумматор, узел выбора максимального кода, две группы элементов И, два элемента И, генератор импульсов, суммирующий и вычитающий счетчики, два дешифратора, причем в каждом формирователе дуги выход триггера соединен с первым входом элемента

И-ИЛИ, выход генератора импульсов подключен к первым входам первого и второго элементов И, выход первого элемента И соединен с входом вычи-. тающего счетчика, инверсный и прямой выходы нулевого состояния которого подключены к вторым входам первого и второго элементов И и первым входам элементов И первой группы, информационный выход вычитающего счетчика соединен с входом первого дешифратора i-й (=l,n) выход которого подключен к вторым входам элементов И-ИЛИ формирователей дуг i-й строки матрицы, входу i-ro элемента задержки и первому входу 1.-го блока элементов И второй группы, выход которого соединен с i-м входом блока элементов ИЛИ, выход которого подключен к первому входу сумматора, выход которого соединен с первыми входами блоков элементов И первой группы, вторые входы которых подключены к выходам соответствующих элементов за-. держки группы, а выходы — к входам соответствующих регистров группы, третий вход первого элемента И является пусковым входом" устройства, выходы элементов И-ИЛИ формирователей дуг каждого столбца матриц соединены с входами соответствующего элемента ИЛИ группы, выход которого подключен к первому входу соответствующего блока элементов И третьей группы, выход которого соединен с соответствующим входом узла выбора максимального кода, выходы выдачи позиционного кода которого подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с входами триггеров группы, выходы которых подключены к первым входам соответствующих элементов И второй группы, выходы которых соединены с третьими входаья элементов И-ИЛИ фор.

1228112

Составитель А.Шеоенков

Редактор 10.Середа Техред И.Попович Корректор М. Самборская

Заказ 2288/50 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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

1ð регистра группы подключен к первому, а выход обратного кода числа--к второму входу соответствующего блока элементов И-ИЛИ группы, первый и втоА рой выходы третьего дешифратора соединены соответственно с третьими и четвертыми входами блока элементов

И-ИЛИ и блоков элементов И-ИЛИ групПЫ.