Устройство для решения задач на графах Советский патент 1993 года по МПК G06F15/20 G06G7/122 

.i

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

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

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

Устройство для определения кратчайших путей (фиг. 1) содержит генератор 1 тактовых импульсов, блок 2 управления, коммутатор 3, процессоры 4.1..Л.В, блок 5 сравнения, выход 6 генератора тактовых импульсов, выход 7 и группу выходов 8 блока 2 управления, выходы 9 коммутатора, выходы 10.1...10.В веса пути, выходы 11.1...11.В номеров вершин и веса пути, входы 12.1...12.В останова процессоров, выходы 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 сравнения служит для выявления среди поступивших на его входы чисел (весов путей) меньшего и передачи управляющего сигнала на один из процес- соров 4.1,..4.В. Для этого выходы 13 блока 5 сравнения распределены и подключены к входам 12.1,..12.В останова процессоров 4.1...4.В.

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

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

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

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

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

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

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

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

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

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

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

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

весов путей первого и второго рангов и

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

ср те

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

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

Вход 6 синхронизации блока 2 управления соединен с входом синхронизации распределителя 18 импульсов. Распределитель 18 имеет пять выходов, которые подключе- нь следующим образом: первый - к входу сч гтчика 17 и входу распределителя 19 им- путьсов, второй -соответствует выходу 8.3,

тр

зтий - к входу синхронизации распреде218.2 ка

та ст

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

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

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

Блок 2 управления работает следующим образом. Последовательность тактовых им- путьсов, поступающая на вход 6, вызывает появление импульсов на выходах распределителя 18, Импульс с первого выхода записывает 1 в счетчик 17 и поступает на вход синхронизации распределителя 19, на первом выходе которого появляется импульс, поступающий на выход 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.В подключены к входам сборок элементов ИЛИ 22.1...22.В; вход 11.1 подключен к первым входам сборок элементов ИЛИ 22.1,..22.В, вход 11.2 - к вторым входам и т.д. Выходы сборок элементов ИЛИ

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

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

элементов И 23.1.,.23.В и когда на их разре- шающие входы поступает сигнал с входа 7, информация о кратчайшем пути поступает на выход 9.

Каждый из процессоров 4.1 ...4.В (фиг. 4)

содержит элемент ИЛИ 24, триггер 25, сборки элементов И 26.1...26.8, элементы И 27 и Ј8, регистр 29, схему 30 совпадения, триггер 31, сборки элементов И 32 и 33, линию 34 задержки, сборки элементов И 35.1...35.(В- 1), сборки элементов ИЛИ 36.1..,36.(В-1), регистры 37.1...37.8 сумматор 38, сборки элементов И 39.1...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Д...50,(В-И), сборки элементов И 51 и 52, схему 53 сравнения, регистр 54, сборку элементов И 55, сборки элементов И 56 и 57.1...57.В.

Первый информационный вход 9 подключен к информационным входам сборок элементов И 26.1...26.В. Второй информационный вход подключен к информационному входу сборки элементов И 32 и первому входу схемы 30 совпадения. Вход останова 12.1 (входы 12.2...12.В в процессорах 4.2...4.В) подключен к первому входу элемента ИЛИ 24 и разрешающим входам сборок элементов И 57.1...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.1...35.(В-1). Подключение элементов внутри каждого процессора одинаковы, поэтому рассмотрим их на примере процессора 4.1. Выход регистра 29, в котором хранится номер своей вершины, подключен к информационному входу сборки элементов И 33 и второму входу схемы 30 совпадения, выход которой подключен к входу триггера 31. Единичный выход триггера 31 соединен с разрешающими входами сборок элементов И 32 и 33, а нулевой выход - с входом линии 34 задержки, выход которой подключен к устанавливающему входу регистра 37.1 и второму входу элемента ИЛИ 24, выход которого соединен с входом триггера 25, единичный выход которого подключен к разрешающим входам сборок элементов И 26.1...26.В и информационному, входу элемента И 27, выход которого соединен с разрешающим входом сборки элементов И 56, а нулевой выход триггера 25 подключен к информационному входу элемента И 28, выход которого соединен с разрешающим входом сборки элементов И 55.

Выходы сборок элементов И 26.1...26.В подключены к первым входам соответствующих сборок элементов ИЛИ 36.1...36(В-1) и сумматора 38. Выход сборки элементов И 32 подключен к информационному входу регистра 37.1. Выход сборки элементов И 33 подключен к информационным входам сбо0 рок элементов И 35.1...35.(В-1), выходы которых подключены к вторым входам соответствующих сборок элементов ИЛИ 36.1...36.(В-1), выходы которых соединены с входами регистров 37.2...37.В.

5 Регистр 37.1 служит для хранения номера корневой вершины, регистры 37.2...37.В - для хранения номеров вершин, образующих пути рангов от первого до (В-1)-го к своей вершине, сумматор 38-для получе0 ния веса пути соответствующего ранга. Выходы регистров 37.1...37.(В-1) подключены к информационным входам соответствующих сборок, элементов И 39.1 ...39.(В-1) и 49.1...49.(В-1), выход регистра 37.В подклю5 чен к информационному входу сборки элементов И 49.В.

Выходы сборок элементов И 39.1...39.(В-1) соединены со входами сборки элементов ИЛИ 40, выход которой подклю0 чен к первым входам схем совпадения 44.1...44.(В-1). В сборке регистров 41 хранятся связи своей вершины с остальными вершинами графа, причем в регистрах 42.1...42.(В-1) хранятся номера вершин, а в

5 регистрах 43.1.,.43.(В-1)-веса ребер, соединяющих эти вершины со своей (при отсутствии связи в соответствующих регистрах 43.1...43.(В-1) записаны нули). Выходы регистров 43.1...43.(В-1) подключены к инфор0 мационным входам соответствующих сборок элементов И 45.1...45.(В-1). Выходы регистров 42.1...42.(В-1) подключены к вторым входам соответствующих схем совпадения 44.1...44.(В-1), выходы которых

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

Выход сумматора 38 подключен к информационным входам сборок элементов И 49 .(В+1) и 51. Выход элемента ИЛ И47 соединен с первым входом триггера 48, выход которого

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

Выходы регистров 50.2.,.50.(В+1) подключены к информационным входам соответствующих сборок элементов И Г7.1...57.В и, кроме того, выход регистра Ю.(В+1) подключен к информационным вхо- дам сборок элементов И 52 и 56. Выходы :борок элементов И 51 и 52 соединены со годами схемы 53 сравнения, выход кото- эой подключен к разрешающим входам сбо- зок элементов И 49.1...49.(В+1). Регистр 54 :лужит для записи максимально большого шсла, его выход подключен к информацион- юму входу сборки элементов И 55. Выходы :борок элементов И 55 и 56 соединены меж- цу собой и образуют выход 10.1, а выходы ;борок элементов И 57.1...57.В образуют зыход 11.1 процессора 4.1. Аналогично об- эазуются выходы 10.2...10.В и 11.2...11.В процессоров 4.2...4.В.

В исходном состоянии в регистре 29 записан номер своей вершины, регистры 37.1...37.В и сумматор 38 обнулены, в регистрах 42.1...42.(В-1) записаны номера вершин графа (кроме своей), в регистрах 43.1...43.(В-1) - веса ребер, связывающих соответствующие вершины со своей (при отсутствии ребра в регистре- О), регистры 50.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. Если

I

номер корневой вершины не совпал с номером своей, то триггер 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 и AHVI 40 поступит нз первые входы всех схем совпадения 44.1... 44.(В-1).

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

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

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

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

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

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

Таким образом, после первого цикла работы устройства (цикла выдачи импульсов с первого по пятый распределителем 18 импульсов блока 2 управления) в ряде процессоров сформируются пути первого ранга и среди них выберется кратчайший, который передается на все процессоры/кроме того, где этот путь выявлен. При втором цикле работы устройства с первого информационного входа 9 через сборки элементов И 26.1, 26.В и ИЛИ 36.1 в регистр 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) останется информация, записанная в них при первом цикле (т.е. либо путь первого ранга, либо максимально большое число), эта информация поступит на

5 информационные входы сборок элементов И 56 и 57.1...57,В, а на выходы 10.1 и 11.1 она будет выдаваться как и в первом цикле. Если путь второго ранга существует, то вес ребра, соединяющего вторую вершину крат10 чайшего пути первого ранга со своей вершиной, из регистра 43.1 через открытую сборку элементов И 45.1 и сборку элементов ИЛИ 46 прибавится в сумматоре 38 к весу кратчайшего пути первого ранга и поступит

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

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

5 больше или равен весу пути первого ранга, то схема 53 не сработает и в регистрах 50.1,..50.(В+1) информация не изменится. Если вес пути второго ранга меньше веса пути первого ранга (естественно меньше

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

5 вершина, в регистр 50.2 - вторая вершина, в регистр 50.3 - третья своя вершина, в регистр 50.(В+1) - вес пути) и информация о нем поступит на входы сборок элементов И 56 и 57.1.„57.В, а на выходы 10..1 и 11.1 она

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

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

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

Блок 5 сравнения (фиг. 5) содержит

- схем сравнения 62, каждая из

которых предназначена для сравнения пары чисел, и элементы И 63.1.,,63.В. Схемы сэавнения 62 сгруппированы в линейки. В схемах сравнения первой линейки 62,1.1...62.1(В-1) происходит сравнение первого числа (веса пути или максимально большого числа, поступающих на вход 10.1) с остальными числами, поступающими на вчоды 10.2...10.В. В схемах сравнения вто- рэй линейки 62.2.1...62.2(В-2) происходит сравнение второго числа со все ми остальными числами, кроме первого, и т.д. Вход 1i).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(6-3) третьей линей- и второму входу схем сравнения 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.(В-3) третьей линейки и вторые

KI

6: б:

н

Д

Л1

б: 6: &

внходы схемсравнения 62.1.2 и 62.2.1 под- кг ючены к входам элемента И 63.3 и т.д. В .(ходы элементов И 63.1...63.В образуют вц ход 13 блока 5 сравнения.

Блок 5 сравнения работает следующим о разом. Числа, поступающие на входы 1C,1...10.8, представляют собой либо веса

тей, либо максимально большие числа. В каркдом цикле работы в схемах сравнения 62

оисходит одновременное сравнение всех

ступивших чисел. При этом в каждой схе- м сравнения высокий потенциал появляется) на первом (левом) выходе, если число,

ступившее на ее первый (левый) вход, м ньше или равно числу, поступившему на

эрой (правый) вход, если число, поступившее на первый вход, больше числа, поступившего на второй вход, то высокий

тенциал появляется на втором (правом)

выходе схемы сравнения. Таким образом, в результате сравнения на одном из выходов каждой схемы сравнения 62 появляется высокий потенциал. Следовательно, на входы

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

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

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

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

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

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

5 графа устройства подключен к вторым информационным входам процессоров с первого по В-й.

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

0 сравнения, счетчик, триггер и три распределителя импульсов, причем вход режима и вход синхронизации блока подключены соответственно к первому информационному входу узла сравнения и к входу синхрониэа5 ции первого распределителя импульсов, . первый выход которого подключен к входу синхронизации второго распределителя импульсов и к счетному входу счетчика, выход переноса которого подключен к второму кн- формационному входу узла сравнения, выход которого подключен к входу признака запуска-останова первого распределителя импульсов, второй и третий выходы которого подключены соответственно к входу синхронизации третьего распределителя импульсов и к входу установки в 1 триггера, четвертый выход первого распределителя импульсов подключен к входу установки в О триггера и к выходу блока, выход триггера, выходы второго и третьего распределителей импульсов и пятый выход первого распределителя импульсов подключены соответственно к выходам группы блока.

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

Фие.2

- -

TISnDS

JHilt ЫШЩ |gg.6j

db -tfcJ

I gas. . .|g3.gga.j i-1...-.ILJ

.

I

zt«.

Р

L

OJ i

1837312

I-В

Фиг. 5