Устройство для решения задач на графах

 

Изобретение относится к вычислительной технике и предназначено для использования при решении задач комбинаторной оптимизации на графах. Цель изобретения - повышение быстродействия. Это достигается тем, что устройство для решения задач на графах содержит генератор 1 тактовых импульсов, блок 2 управления, коммутатор 3, В процессоров 4 (где В - число вершин графа) и блок 5 сравнения. 1 з.п. ф-лы, 5 ил. 00 ы XI ы

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

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

РЕСПУБЛИК

ННОЕ ПАТЕНТНОЕ

-- ". ЗИМ <>OVHQg

- 10 ГЕКА

ССР)

ПИСАНИЕ ИЗОБРЕТЕНИЯ

АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

) 4784401/24

) 18.01.90

) 30.08.93. Бюл. М 32

) В.Я. Певнев, С,А. Ильин, С,В. Листрой, В.В. Ковальчук и В.Н, Мариян

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

485451, кл. G 06 F 15/20, 1971.

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

640314, кл. G 06 G 7/122, 1978.

„„БЫ„„1837312 А1 (я)з G 06 F 15/20, G 06 6 7/122 (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и предназначено для использования при решении задач комбинаторной оптимизации на графах. Цель изобретения — повышение быстродействия. Это достигается тем, что устройство для решения задач на графах содержит генератор 1 тактовых импульсов, блок 2 управления, коммутатор

3, В процессоров 4 (где  — число вершин ф ) б 5 я. 1 З.п, ф-flbl, 5 и:i, 1837312

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

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

На фиг. 1 показана структурная схема устройства для определения кратчайших путей; на фиг. 2 — функциональная схема блока управления; на фиг. 3 — функциональная схема коммутатора; на фиг. 4 — функциональная схема процессора; на фиг. 5- функциональная схема блока сравнения.

Устройство для определения кратчайших путей (фиг. 1) содержит генератор 1 тактовых импульсов, блок 2 управления, коммутатор 3, процессоры 4.1...4,В, блок 5 сравнения, выход 6 генератора тактовых импульсов, выход 7 и группу выходов 8 блока

2 управления, выходы 9 коммутатора, выходы 10.1...10,В веса пути, выходы 11,1...11.В номеров вершин и веса пути, входы

12.1...12,B останова процессоров, выходы

13,1„.13.В блока 5 сравнения, вход 14 номера корневой вершины и вход 15 значения числа вершин графа.

Генератор 1 тактовых импульсов с выхода 6 подает на вход синхронизаии блока 2 управления последовательность тактовых импульсов, управляющих работой элементов и блоков устройства. Блок 2 управления предназначен для записи номера корневой вершины и выдачи управляющих сигналов на остальные блоки устройства. Для этого выход 7 блока 2 управления соединен с управляющим входом коммутатора 3, а группа выходов 8 подключена к входу кода операции каждого процессора 4 1.„4.В, Коммутатор3 служитдля передачи кратчайшего пути определенного ранга, принятого с одного из процессоров, на все процессоры 4, Для этого его выходы 9 подключены к первым информационным входам каждого процессора 4.1...4.В.

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

3, а весов путей — в блок 5 сравнения и запись кратчайшего пути к данной вершине.

Выходы 10.1„.10.В веса пути соответственно процессоров 4.1...4,В подключены к информационным входам блока 5 сравнения, а выходы 11.1...11.В номеров вершин и веса пути этих же процессоров 4,1...4.В подключены к информационным входам коммутатора 3. Блок 5 сравнения служит для выявления среди поступивших на его входы чисел (весов путей) меньшего и передачи управляющего сигнала на один из процес5 соров 4,1„.4.В. Для этого выходы 13 блока 5 ,. сравнения распределены и подключены к входам 12.1...12.В останова процессоров

4.1. „4.В.

В исходном состоянии в лроцессорах

"0 4.1...4.В записаны номера "своих" вершин и связи этих вершин с остальными вершинами графа.

Устройство для определения кратчайших путей работает следующим образом.

Номер корневой вершины со входа 15 устройства поступает на вторые информационные входы всех процессоров 4.1...4,В.

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

25 операции с блока 2 управления, сформируются и запомнятся пути первого ранга, а их веса с выходов 10 передадутся в блок 5 сравнения. В процессорах, вершины которых не имеют связи с корневой вершиной, 30 формирования путей первого ранга не произойдет и с их выходов 10 на блок 5 сравнения будут переданы максимально большие числа (т,е. во всех разрядах выхода 10 будут переданы "1").

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

40 кратчайший путь запомнится и передастся с выхода 11 перечня вершин и веса пути в коммутатор 3 и, кроме того, закроется первый информационный вход этого процессо-. ра, исключая его из дальнейшей работы

45 (кратчайший путь к данной вершине определился — им стал путь первого ранга).

Кратчайший путь первого ранга из коммутатора 3 по сигналу с выхода 7 блока 2 управления передастся на все процессоры

50 4.1...4.В (в исключенные из работы процессоры этот путь не пройдет). В процессорах, вершины которых имеют связь с последней вершиной полученного кратчайшего пути первого ранга, сформируются пути второго

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

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

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

Блок 2 управления (фиг. 2) содержит уз л сравнения 16, счетчик 17, распределите и 18, 19 и 20 импульсов, триггер 21.

Вход 6 синхронизации блока 2 управлен я соединен с входом синхронизации раси еделителя 18 импульсов. Распределитель

1 имеет пять выходов, которые подключен следующим образом: первый — к входу сч тчика 17 и входу распределителя 19 импу ьсов, второй — соответствует выходу 8.3, тр тий — к входу синхронизации распредели еля 20 импульсов, четвертый — к входу ус ановки в единицу триггера 21, пятый — к вх ду установки в ноль триггера 21 и, кроме то о, образует выход 7 блока 2 управления.

В ход переноса счетчика 17 соединен со вт рым информационным входом узла 16 ср внения, с первым информационным вход которого соединен вход режима 14, а вь ход узла 16 сравнения подключен к входу п изнака запуска/останова распределителя 18 импульсов. (В-1) выход распределителя 19 импульсов соответствует выходу 8,1. (В 1) выход распределителя 20 импульсов со тветствует выходу 8.2. Выход триггера

21 соответствует выходу 8.4. Выходы 8.1, 8., 8.3, 8.4, образуют группу выходов 8 блока 2 управления.

В исходном состоянии триггер 21 и оста ьные элементы памяти — в нулевом сост янии.

Блок 2 управления работает следующим об азам. Последовательность тактовых импу ьсов, поступающая на вход 6, вызывает по вление импульсов на выходах распредели еля 18, Импульс с первого выхода запис вает "1" в счетчик 17 и поступает на вход си хронизации распределителя 19, на пер5

55 вом выходе которого появляется импульс, поступающий на выход 8,1. Импульс со второго выхода распределителя 18 поступает на выход 8,3. Импульс с третьего выхода распределителя 18 поступает на вход синхронизации распределителя 20, на первом выходе которого появляется импульс, поступающий на выход 8.2. Импульс с четвертого выхода распределителя 18 поступает на вход установки в единицу триггера 21, переводит его в единичное состояние и высокий потенциал с выхода триггера поступает на выход 8.4, Импульс с пятого выхода распределителя 18 поступает на выход 7 блока 2 управления и, кроме того, на вход установки в ноль триггера 21 и переводит его в нулевое состояние — высокий потенциал с выхода 8.4 снимается, На этом заканчивается первый цикл работы блока 2 управления. При последующих циклах в счетчик 17 записываются "единицы", импульсы появляются на последующих выходах распределителей 19 и 20, а также на выходах 7, 8.3, 8.4. Число полных циклов работы блока 2 управления равно (В-1). На В-ом цикле импульс появляется только на первом выходе распределителя 18 — в счетчик 17 записывается В-ая

"единица", в узле 16 сравнения число "В" с входа режима 14 совпадает с числом "В" из счетчика 17 и импульс с выхода узла 16 сравнения прекратит работу распределителя 18 импульсов.

Коммутатор 3 (фг, 3) содержит сборки элементов ИЛИ 22.1...22,В и сборки элементов И 23,1...23.В.

Управляющий вход 7 подключен к разрешающим входам сборок элементов И

23,1...23.В. Информационные входы

11.1„.11.B подключены к входамсборокэлементов ИЛИ 22.1...22.В; вход 11.1 подключен к первым входам сборок элементов ИЛИ

22.1„.22.В, вход 11.2 — к вторым входам и т.д. Выходы сборок элементов ИЛИ

22.1„,22,В соединены с информационными входами соответствующих сборок элементов И 23.1...23.В, выходы которых образуют выход 9 коммутатора 3.

Комм татар 3 работает следующим образом. Информация о кратчайшем пути какого-то ранга (перечень номеров вершин и вес пути) с одного из входов 11.1...11.В.через сборки элементов ИЛИ 22.1...22.В поступает на информационные входы сборок элементов И 23.1...23.В и когда на их разрешающие входы поступает сигнал с входа 7, информация о кратчайшем пути поступает на выход 9.

Каждый из процессоров 4.1...4. В (фиг. 4) содержит элемент ИЛИ 24, триггер 25, сбор1837312 ки элементов И 26.1...26.В, элементы И 27 и

28, регистр 29, схему 30 совпадения, триггер

Ç1., сборки элементов И 32 и 33, линию 34 задержки, сборки элементов И 35.1...35.{В1), сборки элементов ИЛИ 36Л ...36.(В-1), регистры 37.1...37.В сумматор 38, сборки элементов И 39Л...39.(В-1), сборку элементов ИЛИ 40, сборку 41 регистров, включающую регистры 42.1...42.(В-1) и 43.1...43.(В-1), схемы 44.1...44,(В-1) совпадения, сборки элементов И 45,1...45.(В-1), сборку элементов ИЛИ 46, элемент ИЛИ 47, триггер 48, сборки элементов И 49.1...49.(В+1), регистры 50,1...50,(В+1), сборки элементов И 51 и

52, схему 53 сравнения, регистр 54, сборку элементов И 55, сборки элементов И 56 и

57.1...57.В, Первый информационный вход 9 подключен к информационным входам сборок элементов И 26.1...26.В. Второй информационный вход подключен к информационному входу сборки элементов И 32 и первому входу схемы 30 совпадения. Вход останова 12.1 (вхады 12.2...12.B в процессорах 4.2...4.В) подключен к первому входу элемента ИЛИ. 24 и разрешающим входам сборок элементов И 57Л.„57.В. Вход 58 соответствует выходу 8.4 блока 2 управления и подключен к разрешающему входу элементов И 27 и 28; вход 59 соответствует выходу 8.3 блока 2 и подключен к второму входу триггера 48; вход 60 соотвтстует выходу 8.2 блока 2 и подключен к разрешающим входам сборок элементов И

39.1..,39,(В-1); вход 61 соответствует выходу

8.1 блока 2 и подключен к разрешающим входам сборок элементов И 35Л...35.(В-1).

Подключение элементов внутри каждого процессора одинаковы, поэтому рассмотрим их на примере процессора 4.1. Выход регистра 29, в котором хранится номер

"своей" вершины, подключен к информационному входу сборки элементов И 33 и второму входу схемы 30 совпадения, выход которой подключен к входу триггера 31, Единичный выход триггера 31 соединен с разрешающими входами сборок элементов

И 32 и 33, а нулевой выход — с входом линии

34 задержки, выход которой подключен к устанавливающему входу регистра 37Л и второму входу элемента ИЛИ 24, выход которого соединен с входом триггера 25, единичный выход которого подключен к разрешающим входам сборок элементов И

26.1...26,B и информационному входу элемента И 27, выход которого соединен с разрешающим входом сборки элементов И 56, а нулевой выход триггера 25 подключен к информационному входу элемента И 28, выход которого соединен с разрешающим входом сборки элементов И 55.

Выходы сборок элементов И 26.1...26,В подключены к первым входам соответству5 ющих сборок элементов ИЛИ 36.1...36(В-1) и сумматора 38. Выход сборки элементов И

32 подключен к информационному входу регистра 37.1. Выход сборки элементов И 33 подключен к информационным входам сбо10 рок элементов И 35Л...35.(В-1), выходы которых подключены к вторым входам соответствующих сборок элементов ИЛИ

36.1...36.(В-1), выходы которых соединены с входами регистров 37.2...37.В, 15 Регистр 37.1 служитдля хранения номера корневой вершины, регистры 37.2...37. — для хранения номеров вершин, образующих пути рангов от первого до (B-1)-го к

"своей" вершине, сумматор 38-для получе20 ния веса пути соответствующего ранга, Выходы регистров 37Л ...37.(В-1) подключены к информационным входам соответствующих сборок элементов И 39.1...39.(В-1) и

49.1...49.(В-1), выход регистра 37.В подклю25 чен к информационному входу сборки элементов И 49.В.

В ыходы сборок элементов И

39.1...39.(В-1) соединены со входами сборки элементов ИЛИ 40, выход которой подклю30 чен к первым входам схем совпадения

44. t...44.(Â-1). В сборке регистров 41 хранятся связи "своей" вершины с остальными вершинами графа, причем в регистрах

42Л...42.(В-1) хранятся номера вершин, а в

35 регистрах 43Л ...43.(В-1) — веса ребер, соединяющих эти вершины со "своей" (при отсу1ствии связи в соответствующих регистрах

43Л ...43.{В-1) записаны "нули"). Выходы регистров 43Л ...43.(В-I) подключены к инфор

40 мационным входам соответствующих сборок элементов И 45,1...45.(В-1). Выходы регистров 42.1...42.(В-1) подключены .к вто-. рым входам соответствующих схем совпадения 44.1...44.(В-1), выходы которых

45 подключены к разрешающим входам соответствующих сборок элементов И

45.1...45.(В-1), выходы которых соединены со входами сборки элементов ИЛИ 46, вы. ход которой подключен к второму входу сум50 матора 38 и входу элемента ИЛИ 47.

Выход сумматора 38 подключен к информационным входам сборок элементов И

49.(B+1) и 51. Выходэлемента ИЛИ47соединен с первым входом триггера 48, выход которого

55 подключен к разрешающим входам сборок элементов И 51 и 52, Выходы сборок элементовы

И 49,1...49.(B+1) подключены к входам соответствующих регистров 50,1...50.(В+1),.в которых хранится информация о кратчайшем пути (номера вершин и вес пути).

1837312

Выходы регистров 50.2...50.(В+1) падлючены к информационным входам саотетствующих сборок элементов И

7.1.„57.В и, кроме того, выход регистра

0.(В+1) подключен к информационным вхоам сборок элементов И 52 и 56, Выходы борок элементов И 51 и 52 соединены со ходами схемы 53 сравнения, выход котоой подключен к разрешающим входам сбоок элементов И 49.1...49.(В+1). Регистр 54 лужит для записи максимально большого исла, его выход подключен к информационому входу сборки элементов И 55. Выходы сборок элементов И 55 и 56 соединены межу собой и образуют выход 10.1, а выходы борок элементов И 57.1„.57.B образуют

ыход 11.1 процессора 4.1. Аналогично обазуются выходы 10.2...10.В и 11,2...11.В роцессоров 4.2...4. В, В исходном состоянии в регистре 29 аписан номер "своей" вершины, регистры

7.1...37,В и сумматор 38 абнулены, в регистрах 42.1...42.(В-1) записаны номера вершин графа (кроме "своей"), в регистрах

3.1...43.(В-1) — веса ребер, связывающих оответствующие вершины со "сваей" (при тсутствии ребра в регистре — "0"), регистры

0.1...50.В обнулены, в регистрах 50,(В+1) и

4 записано максимально большое число (т.е; во всех разрядах — "1"), триггеры 25 и 31 в единичном состоянии, триггер 48 — в нулевом.

Процессор 4.1 работает следующим образом. На второй информационный вход 15 поступает номер корневой вершины, который через открытую сборку элементов И 32 запишется в регистр 37.1, а также поступит на первый вход схемы 30 совпадения. Если номер корневой вершины совпадает с номером "своей" вершины, то сработает схема 30 совпадения и перевернет триггер 31 в нулевое состояние: низкий потенциал с его единичного выхода закроет сборки элементов

И 32 и 33 (запрещается пропуск номера корневой вершины в регистр 37,1 и номера

"своей" вершины на сборки элементов И

35.1...35.(В-1)), высокий потенциал с нулевого выхода через линию 34 задержки приведет в исходное состояние ("ачистит") регистр 37.1, а также через элемент ИЛИ 24 поступит на, вход триггера 25 и переведет его в нулевое состояние, тем самым закроются сборки элементов И 26.1...26.В, т,е. в процессор не будет поступать информация из коммутатора 3 — таким образом, процессор из дальнейшей работы устройства исключается; кроме того, низкий потенциал с единичного выхода триггера 25 закроет элемент И 27, а высокий потенциал с ега нулевого выхода откроет элемент И 28. Если

55 номер корневой вершины не совпan с номерам "своей", то триггер 31 остается в единичном состоянии: в регистре 37.1 останется записанным номер корневой вершины, который с выхода регистра поступит на входы сборок элементов И 39.1 и 49.1, комер "своей" вершины поступит на информационные входы сборок элементов И

35.1 ...35,(В-1), сборки элементов И

26,1„,26,В останутся открытыми, При поступлении первого импульса на вход 61 откроется сборка элементов И 35.1 и номер

"своей" вершины через сборки элементов И

35.1 и ИЛИ 36.1 запишется в регистр 37,2, а с его выхода поступит на входы сборок элементов И 39.2 и 49.2. При поступлении первого импульса на вход 60 откроется сборка элементов И 39.1 и номер корневой вершины через сборки элементов И 39.1 и ИЛИ 40 поступит на первые входы всех схем GQBAaдения 44,1...44,(B-1).

На выходе одной из схем 44Л совпадения (схемы, на второй вход которой подается номер корневой вершины из регистра

42,i, где i=-1...(В-1)) появится высокий потенциал, который откроет соответствующую сборку элементов И 45.i и через нее, а также через сборку элементов ИЛИ 46, вес ребра, соединяющего корневую и "сваю вершины, запишется в сумматор 38 и поступит на вход элемента ИЛИ 47. При этом триггер 48 переворачивается s единичное состояние и высоким потенциалом со своего выхода открывает сборки элементов И 51 и 52, На информационный вход сборки элементов И

51 из сумматора 33 поступает вес ребра, соединяющего корневую и "свою" вершины, а на информационный вход сборки элементов И 52 — максимально большое число из регистра 50.(В+1).

Вес ребра и большое число сравниваются в схеме 53 сравнения (схема 53 сравнения работает таким образам, что сигнал на ее выходе появляется в случае, если число, поступающее на первый вход, меньше числа, поступающего на второй (правый) вход) и на ее выходе появится потенциал, который откроет сборки элементов И 49.1...49.(В+1).

Путь первого ранга запишется в регистры

50.", (корневая вершина), 50,2 ("своя" вершина) и 50,(В+1) (вес пути). Импульс са входа 59 перевернет триггер 48 в исходное состояние, "Своя" вершина и вес пути из регистров

50.2 и 50.(В+1) поступают на информационные входы сборок элементов И 57.1 и 57.В, кроме того, вес пути поступает на информационный вход сборки элементов И 56. (Если связи между корневой и "сваей вершиной нет, Tñ с соответствующего регис-ра 43.i Б сумматор 38 ничего не запишется, триггер

1837312

10

25

35

48 останется в исходном положении, схема

53 сравнения не сработает, в регистры

50.1.„50. В ничего не запишется, максимально большое число из регистра 50.(В+1) поступит на информационный вход сборки элементов И 56). Импульс со входа 58 через открытый элемент И 27 поступит на разрешающий вход сборки элементов И 56, пропуская число с ее входа на выход 10.1.

Если вес пути, сформированного в процессоре 4. I, является минимальным среди весов путем первого ранга, то на входе останова 12,1 появляется импульс, который откроет сборки элементов И 57,1...57.В, пропуская этот минимальный путь первого ранга ("свою" вершину и вес пути) на вход

11.1 и через элемент ИЛИ 24 перевернет триггер 25 в нулевое состояние, открывая элемент И 28 и закрывая элемент И 27 и сборки элементов И 26.1...26.В. тем самым исключая процессор 4.1 из дальнейшей работы, т.е, сформированный в процессоре путь является кратчайшим к данной вершине, Если вес пути, сформированного в llpoцессоре 4.1 не является минимальным, то импульс на вход 12.1 не поступит, В конце цикла работы устройства со входа 58 снимается высокий потенциал.

Таким образом, после первого цикла работы устройства (цикла выдачи импульсов с первого по пятый распределителем 18 импульсов блока 2 управления) в ряде процессоров сформируются пути первого ранга и среди них выберется кратчайший, который передается на все процессоры, кроме того, где этот путь выявлен, При втором цикле работы устройства с первого информационного входа 9 через сборки элементов И 26.1, 26.В и ИЛИ 36. t в регистр 37.2 запишется номер второй вершины кратчайшего пути первого ранга, а в сумматор 38 — вес этого пути. При поступлении второго импульса на вход 61 номер "своей" вершины через открывшуюся сборку элементов И 35.2 и.сборку элементов ИЛИ 36.2 запишется в регистр

37.3. При поступлении второго импульса на вход 60 номер второй вершины кратчайшего пути первого ранга из регистра 37,2 через открывшуюся сборку элементов И 39.2 и сборку элементов ИЛИ 40 поступит на первые входы всех схем совпадения

44.1...44.(В-1), Далее как и в первом цикле возможно либо формирование пути второго ранга, либо нет. Если связи между второй вершиной кратчайшего пути первого ранга и "своей" вершиной нет (путь второго ранга отсутствует), то со второго входа в сумматор

38 ничего не прибавится, триггер 48 останется в исходном состоянии, схема 53 сравнения не сработает и в регистрах

50,1„,50.(В+1) останется информация, записанная в них при первом цикле (т,е. либо путь первого ранга, либо максимально боль- шое число), эта информация поступит на информационные входы сборок элементов

И 56 и 57.1...57,В, а на выходы 10.1 и 11.1 она будет выдаваться как и в первом цикле.

Если путь второго ранга существует, то вес ребра, соединяющего вторую вершину кратчайшего пути первого ранга со "своей" вершиной, из регистра 43.! через открытую сборку элементов И 45.! и сборку элементов

ИЛИ 46 прибавится в сумматоре 38 к весу кратчайшего пути первого ранга и поступит на вход элемента ИЛИ 47. Триггер 48 перевернется в единичное состояние и высокий потенциал с его выхода откроет сборки элементов И 51 и 52.

В схеме 53 сравнения будут сравниваться: вес пути второго ранга (первый вход) и число, записанное в регистре 50.(В+1) при первом цикле (это либо вес пути первого ранга к "своей" вершине, либо максимально большое число). Если вес пути второго ранга больше или равен весу пути первого ранга, то схема 53 не сработает и в регистрах

50,1...50.(В+1) информация не изменится.

Если вес пути второго ранга меньше веса пути первого ранга (естественно меньше максимально большого числа), то схема 53 сработает и высокий потенциал с ее.выхода откроет сборки элементов И49.1...49(В+1)— в регистры 50.1„,50.(В+1) запишется путь второго ранга {в регистр 50,1 — корневая вершина, в регистр 50.2 — вторая вершина, в регистр 50.3 — третья "своя" вершина, в регистр 50,(В+1) — вес пути) и информация о нем поступит на входы сборок элементов И

56 и 57,1...57.В, а на выходы 10,1 и 11.1 она будет выдаваться как и в первом цикле. Из процессора, в котором сформировался кратчайший путь первого ранга, с выхода 10 веса пути в блок 5 сравнения передается максимально большое число (триггер 25 в нулевом состоянии, элемент И 27 закрыт, элемент И

28 открыт, а значит при поступлении импульса со входа 58 откроется сборка элементов И 55 и пропустит максимально большое число из регистра 54 на выход 10), это необходимо для исключения ошибочного срабатывания и зацикливания блока 5 сравнения (отсутствие веса пути с выхода закрытой сборки элементов И 56 будет восприниматься блоком 5 сравнения как наличие минимального числа).

Таким образом, в процессорах, где ранее был записан путь первого ранга, а при втором цикле сформирован путь второго ранга, из этих двух путей выявится кратчайший, После второго цикла работы устройст13

1837312 а в некоторых процессорах останутся пути ервого ранга, в других — сформируются пувторого ранга (кроме того, могут быть роцессоры, где формирования путей еще е произойдет, это зависит от структуры г афа), среди них опять выберется кратчайий, который передастся на все процессоы, кроме того, где этот путь выявлен, При оследующих циклах процессоры работают аналогично описанному выше. 5 сравнения (фиг. 5) содержит ры сга с о

1 и к и и м с п

М с

s р с н

1 н

В с и

В с к

6 н д л

6

6 в к

В в схем сравнения 62, каждая из орых предназначена для сравнения пачисел, и элементы И 63.1„,63.В, Схемы внения 62 сгруппированы в линейки. В емах сравнения первой линейки .1.1...52.1(В-1) происходит сравнение рвого числа (веса пути или максимально лысого числа, поступающих на вход 10.1) остальными числами, поступающими на оды 10.2...10.В. В схемах сравнения втой линейки 62.2.1...62,2(В-2) происходит авнение второго числа со всеми осталь ми числами, кроме первого, и т,д, Вход .1 подключен к первым входам схем сравния 62.1.1...62.1 (В-1) первой линейки. од 10,2 подключен к первым входам схем авнения 62,2.1...62.2.(В-2) второй линейки второму входу схемы сравнения 62.1,1. од 10.3 подключен к первым входам схем авнения 62.3.1...62.3(B-З) третьей линейи второму входу схем сравнения 62.1.2. и .2.1 и т.д. Первые выходы схем сравнения .1.1...62.1.(В-1) первой линейки подключек входам элемента И 63.1. Первые выхо схем сравнения 62.2.1...62.2,(В-2) второй нейки и второй выход схемы сравнения .1.1 подключены к входам элемента И .2. Первые выходы схем сравнения. .3.1...62.3.(В-З) третьей линейки и вторые ходы схем сравнения 62,1.2 и 62.2.1 подючены к входам элемента И 63.3 и т.д. ходы элементов И 63.1...63,В образуют ход 13 блока 5 сравнения.

Блок 5 сравнения работает следующим разом. Числа, поступающие на входы ,1...10.В, представляют собой либо веса ей, либо максимально большие числа. В дом цикле работы в схемах сравнения 62 оисходит одновременное сравнение всех ступивших чисел. При этом в каждой схесравнения высокий потенциал появляетна первом (левом) выходе, если число, ступившее на ее первый (левый) вход, ныне или равно числу, поступившему на рой (правый) вход, если число, поступиве на первый вход, больше числа, постувшего на второй вход, то высокий енциал появляется на втором (правом) 55 ответственно к первому информационному входу узла сравнения и к входу синхронизации первого распределителя импульсов, первый выход которого подключен к входу синхронизации второго распределителя импульсов и к счетному входу счетчика. выход переноса которого подключен к второму информационному входу узла сравнения, вывыходе схемы сравнения, Таким образом, в результате сравнения на одном из выходов каждой схемы сравнения 62 появляется высокий потенциал. Следовательно, на входы

5 элементов И 63.1...6З.В будут поступать комбинации высоких и низких потенциалов.

При этом комбинация, состоящая из одних высоких потенциалов, соответствует минимальному числу. Эта комбинация вызывает

10 срабатывание соответствующего элемента

И 63 и на его выходе появится импульс, который поступит на выход 13 блока 5 сравнения.

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

15 1. Устройство для решения задач на графах, содержащее блок управления и генератор тактовых импульсов, причем вход запуска устройства подключен к входу запуска-останова генератора тактовых импуль20 сов, отл и чаю щееся тем, что,сцелью повышения быстродействия, оно содержит коммутатор, блок сравнения и В процессоров, где  — число вершин графа, причем выход генератора тактовых импульсов под25 ключен к входу синхронизации блока управления, выходы группы которого подключены соответственно к входам кода операции процессоров с первого по В-й, выходы веса пути на графе а-го процессора (где а=1„,,F

30 подключены соответственно к информационным входам а-й группы блока сравнения, выходы с первого по В-й которого подк..ючены соответственно ко входам останова процессоров с первого по В-й, выходы но35 меров вершин пути на графе à-ro процессора подключены соответственно к информационным входам а-й группы коммутатора, выходы которого подключены к первым информационным входам процессоров

40 с первого по В-й, выход блока управления подключен к управляющему входу коммутатора; вход номера корневой вершины графа устройства подключен к входу режима блока управления, вход значения числа вершин

45 графа устройства подключен к вторым информационным входам процессоров с первого по В-й, 2. Устройство по и. 1, о тл и ч а ю ще ес я тем, что блок управления содержит узел

50 сравнения, счетчик, триггер и три распределителя импульсов, причем вход режима и вход синхронизации блока подключены со1837312

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

5 первого распределителя импульсов подключены соответственно к выходам группы блока.

1837312.

1837312

<РОГ

Составитель ВЛевнев

Техред М.Моргентал Корректор M.Êåðåöìàí

Редактор

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина. 101

Заказ 2867 Тираж Подписное

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

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