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

(Л

4

о со

к

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

-HZZ™H

giur.l

в сокращении аппаратурных затрат. Устройство содержит генератор I импульсов, блок 2 формирователей минимального пути, группу элементов И 3, распределитель импульсов 4, группу блоков 5 элементов И, группу сумматоров 6, группу элементов ИЛИ 7,блок |8 выбора максимального кода, группу I регистров 9, наддиагональную матрицу j10 регистров 11, группу элементов I задержки 12. Блок 2 содержит группу триггеров, три группы элементов И,

1

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

Цель изобретения состоит в сокращении аппаратурных затрат. I На фиг.1, 2 изображены функцио- |нальные схемы устройства и блока фор 1мирователей минимального пути; на |фиг,3 - граф, на примере которого рассматривается работа устройства. I Устройство (фиг.1) содержит гене- 1ратор 1 импульсов, блок 2 формирователей минимального пути группу элементов 3 И, распределитель 4 импульсов, группу блоков элементов 5 И Группу 6 сумматоров, группу элементов 7 ИЛИ, блок 8 выбора максимального кода, группу регистров 9, наддиагональную матрицу 10, элементами Которой являются регистры 1I, группу элементов задержки 12, Блок 2 содер- ркит (фиг.2) группу триггеров 13,г, 13 ментов 14,

.„ ,..., 13п.,„, первую группу эле+1, 14,,n И, вторую группу элементов 15,, , 15 ,4 15п-1, VI И, третью группу элементов 16,, , 16,4 ... 6п-1| и И, первую группу элементов 17,,17,...,17n-i ИЛИ, вторую группу элементов 18,. 18,... 18ft ИЛИ, регистр 19, первую группу 20 входов разрешения записи, вторую группу 21 входов разрешения записи, вход 22 разрешения считьтания.

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

После подачи пускового сигнала генератор ) начинает выдачу импульсов.

две группы .элементов ИЛИ, регистр, первую группу входов разрешения записи, вторую группу входов разрешения записи, вход разрешения считыва - ния. Сокращение аппаратурных затрат достигнуто за счет исключения из про- тоттдаа группы элементов И-НЕ, группы элементов И, триггеров, счетчика, дешифратора при дополнительном включении лишь группы элементов задержки, группы блоков элементов И и распределителя импульсов, 3 ил.

первый из которых поступает на первый вход блока 5 и на вход разрешения считывания регистра 9, с выхода которого вес дуги (1,2) поступает на второй вход сумматора 6. Пусковой импульс также поступает на вход распределителя 4, который выдает по первому выходу потенциал 1 на вход элемента задержки 1 . и входы сч итывания регистров 1 1 13 S Записанный в одном из них обратный код дуги (1,3) через элемент 7i ИЛИ поступает на первый вход блока 8, а записанный в регистре 1113 вес дуги (2,3) через элемент 7 ИЛИ поступает на вход первого слагаемого сумматора 6. Последний складывает веса дуг (1,2) и (2,3) и с инверсного выхода выдает обратный код суммы через блок 5 на второй вход блока 8, на остальньк входах которого нули. Блок 8 выбирает максимальный из входных кодов и вьщает его в обратном коде через выход максимального кода, на информационные входы регистров 9 начиная с регистра 9. С выхода элемента задержки 12 сигнал поступает на вход разрешения записи регистра 9-}, который запоминает число, которым выражается длина минимального пути из первой в третью вершину графа.

Для графа-примера (фиг.З) на первый вход блока 8 поступает обратньш код 1001 веса дуги (1,3), на входы сумматора 6 - коды 0010 и ООП весов дуг (1,2) и (3,2), которые после сложения в обратном коде поступают на второй вход блока 8, который выбирает максимальный из входных кодов (1010). и выдает его в обратном коде

на запись в регистр У как величину минимального пути из первой в третью вершин; графа. Блок 8 выдает также потенциал 1, который через вход 20 блока 2 поступает на вторые входы элементов 14 И. Одновременно с первого выхода распределителя 4 единичный сигнал поступает через вход 21-} на первые входы элементов 14,, 14 И. На выходе элемента появляется потенциал 1, перебрасывающий в единичное состояние триггер 13j.

Второй импульс генератора 1 вновь проходит на вход разрешения считывания регистра 9, и вес дуги (1,2) вновь подается на вход второго слагаемого сумматора 6. Второй импульс поступает также на первый вход блока Sj, а поскольку элемент З И открыт по второму входу единичным потенциалом с первого вькода распределителя 4, то этот импульс проходит на

ну минимального пути из первой в четвертую вершину. Блок 8 вьщает также признак максимального кода (потенциал 1), которьш через вход 20 проходит на вторые входы элементов 14,

аз

1474 И, Единичный сигнал с второго выхода распределителя 4 поступает через вход 214 на первые входы

10 элементов 14 (, 14,, 14, И. Единичный сигнал появляется на выходе элемента 14aq.H и перебрасьгеает в единичное состояние триггер 13.

Третий импульс генератора 1 вновь

15 проходит на вход разрешения считывания регистра 9 и на первый вход бло-, ка 5. Поступив на вход распределителя 4, третий импульс обусловливает задачу потенциала 1 и по третьему

20 выходу распределителя 4. Этот потенциал поступает на вход элемента задержки 125- и на входы считывания

. За11

регистров 1 1 15 , 1S

ЗЯ S

писанное в регистре I I ,; число О (та- вход считьшания регистра 9, который 25 дуги в графе нет) через элемент

выдает записанный в нем код числа на вход второго слагаемого сумматора б.. Указанный импульс генератора I поступает также на вход распределителя 4, который, продолжая выдавать потенциал 1 по первому выходу, вьщает этот же потенциал и по второму выходу. Tak как входы разрешения записи регистров 9 и входы разрешения считывания регистров 11 импульсные, то сохранение единичного потенциала на первом выходе распределителя 4 на них никакого влияния не оказывает, а потенциал 1 с второго выхода поступает на вход элемента задержки 124 и на входы разрешения считывания регистров , 1 Ii4 Н4 J которые выдают соответственно О (дуги 14 в графе нет), 4,2. Сумматор б находит сумму чисел и в обратном коде 1001 выдает ее через открытый блок 52 на второй вход блока 8, а сумматор 6j находит сумму чисел и в обратном коде через блок 5, открытый по первому входу импульсом с выхода элемента 3 И, вьщает на третий вход блока 8. Блок 8 определяет,что максимальным является поданный на второй вход код 1001, а потому вьща7( ИЛИ выставляется на первый вход блока 8, а на его второй, третий и четвертый входы подаются соответст- коды 0110, 0010, 0100, из ко30 торых максимальный код 0110 подан на второй вход. Его обратный код 1001 выставляется на информационные входы регистров 9. При поступлении сигнала с выхода элемента задержки 12 это

25 число (9) записывается в регистр 9 как величина минимального (искомого) пути из первой в пятую вершину графа. Одновременно блок 8 выдает потенциал 1 через вход 20 на вторые входы

40 элементов , 142.4, 14г5 И. Единичный сигнал с третьего выхода распределителя 4 через вход 21 поступает на первые входы элементов 1415, Lftir, 14J5,.На выходе элемента 14г5 И

45 появляется потенциал 1, перебрасывающий в единичное состояние триггер 13 45.

Четвертый импульс генератора 1 проходит на вход разрешения считывания

50 регистра 9, через элемент 3 И - на вход разрешения считьшания регистра 9, через элемент 3 И - на вход разрешения считывания регистра 94, а также на первые входы блоков 52 Sj,

ет его обратный код на информационные 55 4« Появление на входе распределите- входы регистров 9. Когда с выхода ля элемента задержки 12 сигнал поступает на вход разрешения записи регистра 94, он запоминает число 6 как дли4 четвертого импульса генератора 1 приводит к вьщаче потенциала 1 по четвертому выходу распределителя 4 на вход 22 разрешения считывания

3072

ну минимального пути из первой в четвертую вершину. Блок 8 вьщает также признак максимального кода (потенциал 1), которьш через вход 20 проходит на вторые входы элементов 14,

аз

1474 И, Единичный сигнал с второго выхода распределителя 4 поступает через вход 214 на первые входы

10 элементов 14 (, 14,, 14, И. Единичный сигнал появляется на выходе элемента 14aq.H и перебрасьгеает в единичное состояние триггер 13.

Третий импульс генератора 1 вновь

15 проходит на вход разрешения считывания регистра 9 и на первый вход бло-, ка 5. Поступив на вход распределителя 4, третий импульс обусловливает задачу потенциала 1 и по третьему

20 выходу распределителя 4. Этот потенциал поступает на вход элемента задержки 125- и на входы считывания

. За11

регистров 1 1 15 , 1S

ЗЯ S

писанное в регистре I I ,; число О (та- 25 дуги в графе нет) через элемент

7( ИЛИ выставляется на первый вход блока 8, а на его второй, третий и етвертый входы подаются соответст- енно коды 0110, 0010, 0100, из которых максимальный код 0110 подан на второй вход. Его обратный код 1001 выставляется на информационные входы регистров 9. При поступлении сигнала с выхода элемента задержки 12 это

число (9) записывается в регистр 9 как величина минимального (искомого) пути из первой в пятую вершину графа. Одновременно блок 8 выдает потенциал 1 через вход 20 на вторые входы

элементов , 142.4, 14г5 И. Единичный сигнал с третьего выхода распределителя 4 через вход 21 поступает на первые входы элементов 1415, Lftir, 14J5,.На выходе элемента 14г5 И

появляется потенциал 1, перебрасывающий в единичное состояние триггер 13 45.

Четвертый импульс генератора 1 проходит на вход разрешения считывания

регистра 9, через элемент 3 И - на вход разрешения считьшания регистра 9, через элемент 3 И - на вход разрешения считывания регистра 94, а также на первые входы блоков 52 Sj,

4« Появление на входе распределите- ля

4 четвертого импульса генератора 1 приводит к вьщаче потенциала 1 по четвертому выходу распределителя 4 на вход 22 разрешения считывания

и далее на вторые входы элементов 1 5 ,j и 16|g И. Сигнал с входа 22 проходит через открытые элементы 16 И до тех пор, пока не будет найден первый в последнем столбце находящийся в состоянии 1 триггер 13; в данном примере это триггер . Поэтому единичный сигнал считывания проходит через элементы 16,5 и И и 18дИЛИ

на последний, пятый,

g- i ал

информационный

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

через элемент поступит на вто- 15 И группы, р-й выход распределителя рой вход элемента 16, И, открытый импульсов (,п-3) соединен с р-м единичным потенциалом с выхода тригвходом разрешения записи второй гру пы блока формирователей минимально пути графа, входом разрешения считы

гера , и далее на информационный вход его первого разряда. Единичные состояния первого, второго и пятого разрядов регистра 19 укажут вершины графа, через которьй проходит искомый минимальный путь, длина (9) которого записана в регистре 9. В остальных регистрах 9 записаны длины минимальных путей от первой до соответствующих вершин графа. Единичный сигнал с четвертого выхода распределителя 4 проходит также на вход останова генератора 1 и на выход признака окончания работы устройства. Формула изобретения

Устройство для определения минимального пути в графе, содержаш;ее генератор импульсов, группу элементов И, группу сумматоров, группу элементов ИЛИ, блок выбора максимального кода, группу регистров, блок формирователей минимального пути графа и наддиагональную матрицу регистров размерности (n-l)- (п-2), где п - число вершин графа, причем выход первого элемента ИЛИ группы соединен с первым входом блока выбора максимального кода, выходы k-x элементов ИЛИ группы (,n-2) подключены к входам первого слагаемого (k-l)-x сумматоров группы, а выходы признаков максимального кода блока выбора максимального кода соединены с соответствующими входами разрешения записи первой группы блока формирователей минимального пути графа, отличающееся тем, что, с целью сокращения аппаратурных затрат, оно содержит группу блоков элементов И, группу элементов задержек, распре

30726

делитель импульсов, причем вход запуска генератора импульсов является входом пуска устройства, выход гене- ратйра импульсов соединен с входом распределителя импульсов, входом разрешения считывания первого регистра группы, первым входом первого блока элементов И группы и первыми входами элементов И группы, выходы k-x элементов И группы (,n-3) подключены к входам разрешения считывания ()x регистров группы и первым входам (k+l)-x блоков элементов

И группы, р-й выход распределителя импульсов (,п-3) соединен с р-м

входом разрешения записи второй группы блока формирователей минимального пути графа, входом разрешения считывания р-го столбца матрицы регистров, вторым входом р-го элемента И грзшпы и входом р-го элемента задержки группы, выход которого соединен с входом разрешения записи (р+1)-го регистра группы, выход которого соединен с входом второго слагаемого (р+1)-го сумматора группы, инверсный выход которого подключен к - второму входу (р+1)-го блока элементов И группы, выход которого соединен с (р+2)-м входом блока выбора макси-. мального кода, выход максимального кода которого подключен к информа- ционным входам k-x регистров группы

(, 11-1 )j (п-1)-й выход распределителя импульсов соединен с входом разрешения чтения блока формирователей минимального пути графа, входом останова генератора импульсов и

является выходом признака окончания работы устройства, выходы регистров k-й строки наддиагональной матрицы регистров (, п-2) объединены и подключены к входам k-ro элемента

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

выход которого подключен к входу разрешения записи (п-Ч)-го регистра группы.

3

21п

22

срие.2