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

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

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

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

Устройство содержит матрицу .1 п i п (п - число вершин графа) формирователей дуг, каждый из которых вклчает в себя триггер 2 и элемент И-ИЛИ 3, группу элементов ИЛИ 4, первую группу блоков элементов И 5, группу элементов 6 задержки, группу регистров 7, группу блоков элементов И-ИЛИ 8, вторую группу блоков элемен .тов И 9, третью группу блоков элементов И 10, первую группу элементов И 11, группу триггеров 12, вторую группу элементов И 13, сумматор 14, блок элементов ИЛИ 15, узел 16 выбора максимального кода, блок элементов И-ИЛИ 17, генератор 18 импульсов, первб1Й элемент И 19, вычитающий счетчик 20, первый дешифратор 21, второй элемент И 22, суммирующий счетчик 23, второй дешифратор 24, третий дешифратор 25, пусковой вход 26 устройства, вход 27 задания режима, работы устройства.

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

Первоначально в матрицу 1 эаносит ся информация о топологии моделируемого графа. При этом триггеры 2, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий триггер 2 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В регистры 7 заносятся коды чисел, со

О

15

20

25

81

.

30

5

0

5

0

5

122

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

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

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

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

. 3

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

Вычислительный процесс будет продолжаться до тех пор, пока на счетчике 20 не появится нЗ левой код, после чего появится нулевой.код и появится низкий потенциал на втором входе элемента И 19, а подача импульсов на вход счетчика 20 прекращается. Одновременно высокий потенциал с выхода счетчика 20 обеспечивает вьщачу сигналов с выхода генератора 18 через элемент И 22 на вход счетчика 23, соответственно состояниям которого единичные сигналы поочередно появляются на выходах дешифратора 24. Если тот или иной триггер 12 находится в единичном состоянии, то высокий потенциал с его выхода через одноименный элемент И 13 будет поступать на входы элементов И-ИЛИ 3 одноименной строки матрицы 1 и далее через элементы ИЛИ 4 на те входы элементов И 10, которым в данной строке матрицы 1 соответствует дуга графа, т.е. единичное состояние триггера 2. Наличие высоких потенциалов на входах элементов И 10 обеспечивает поступление прямых или обратных кодов, в зависимости от сигнала на входе 27 и выходе дешифратора 25, с выходов регистров 7. череэ соответствующие блоки элементов И-ИЛИ 8, И 10 на вкоды узла 16, который обеспечивает выбор максимального кода из посту пивших кодов, при этом соответствующие триггеры 12 перебрасываются в единичное состояние импульсом, проходящим через одноименный элемент И 11, и т.д.

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

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

0

5

0

5

81

0

5

0

5

50

55

124

(п - число вершин графа) формирователей дуг, состоящих каждый из триггера и элемента И-, группу элементов ИЛИ, группу элементов задержки, первую, вторую и третью группы блоков элементов И, группу триггеров, группу регистров, блок элементов ИЛИ сумматор, узел выбора максимального кода, две группы элементов И, два элемента И, генератор импульсов, суммирующий и вычитакиций счетчики два дешифратора, причем в каждом формирователе дуги выход триггера соединен с первым входом элемента И-ИЛИ, выход генератора импульсов подключен к первым входам первого и второго элементов И, выход первого элемента И соединен с входом вычитающего счетчика, инверсный и прямой выходы нулевого состояния которого подключены к вторым входам первого и второго элементов И и первым входам элементов И первой группы, информационный выход вычитающего счетчика соединен с входом перво го дешифратора i-й (,п) выход которого подключен к вторым входам элементов И-ИЛИ формирова телей дуг 1-й строки матрицы, входу 1-го элемента задержки и первому входу г-го блока элементов И второй группы, выход которого соединен с i-м входом блока элементов ИЛИ, выход которого подключен к первому входу сумматора, выход которого соединен с первыми входами блоков элементов И первой группы, вторые входы которых подключены к выходам соответствующих элементов за-- держки группы, а выходы - к входам соответствующих регистров группы,, третий вход первого элемента И является пусковым входом устройства, выходы элементов И-ИЛИ формирователей дуг каждого столбца матрицы соединены .С входами соответствующего элемента ИЛИ группы, выход которого подключен к первому входу соответствующего блока элементов И третьей группы, выход которого соединен с соответствующим входом узла выбора максимального кода, выходы выдачи позиционного кода которого подключены к первым входам соответствующих элементов И первой группы, выходы которых соединены с входами триггеров группы, выходы которых подключены к первым входам соответствующих элементов И второй группы, выходы которых соединены с третьими входами элементов И-Ш1И формирователей дуг соответствующих строк матрицы, выход второго элемента И подключен к входу сумг рующего счетчика, выход которого соединен с входом второго дешифратора, выходы которого соединены с вторыми входами соответствующих элементов И второй группы, отличающееся тем, что, с целью расширения функциональных возможностей за счет определения минимального критического пути, в устройство введены группа блоков эле- ментов И-ИЛИ, блок элементов И-ИЛИ и третий дешифратор, вход которого является входом задания режима работы устройства, причем выход каждого блока элементов И-ИЛИ соединен с вторыми входами соответствующих блоков элементов И второй и третьей групп, выход блока элементов И-ИЛИ подключен к второму входу сумматора, выход Кода максимального числа блока выбора максимального кода соединен с первым входом .блока элементов И-ШШ, выход прямого кода числа каждого регистра группы подключен к первому а выход обратного кода числа--к второму входу соответствующего блока элементов И-ИЛИ группы, первый и второй выходы третьего дешифратора co- единены соответственно с третьими и четвертыми входами блока элементов И-ИЛИ и блоков элементов И-ШВД группы.

I

Редактор 10. Середа

Составитель А.Шеоенков Техред И.Попович

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4.

Корректор М.Самборская

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