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

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

Целью изобретения является упро- щение функциональной схемы устройства.

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

Блок 1 моделирования топологии сети содержит блок 5 памяти первой

выходящей ветви, блок 6 памяти первой входящей ветви, блок 7 памяти выходящих ветвей, блок 8 памяти входящих ветвей, регистр 9 текущего узла, регистр 10 конечного узла, регистр 11 текущего адреса, узел 12 сравнения, буферные регистры 13 и 14, триггер 15, элементы ШШ 16 и 17.

Вход 18 элемента ИЛИ 17 и вход 19 регистра 10 конечного узла являются входными полюсами устройства.

Входы 20 и 21 соответственно в ячейки памяти 5 и 6 являются зшравляю Щими топологическими входами считыва- ния.

Входы 22 и 23 являются входами обращения к буферным регистрам 13 и 14. Входы 24 и 25 предназначены для подачи управляющих сигналов записи соответственно в регистры 9 текущего узла и текущего адреса 11.

Выходы 26 - 28 образуют группу управляюпщх выходов топологических меток и берутся соответственно с едя ничного выхода триггера 15 и последних разрядов буферных регистров 13 и 14.

Выход 29 узла .12 сравнения является выходом окончания временного моделирования.

Выход 30 -является выходом регистра 11 текущего адреса, соответствую

5 0

5

5

о

5

0

S

щие ему вход 31 - вход арифметического блока 3, и вход 32 - вход блока 4 регистрации.

Выход 33 является выходом считываемого адреса арифметического блока 3, соответствующие ему вход 34 - вход блока 4 регистрации, и вход 35- вход блока 1 формирования топологии.

Выходы 36 - управляющие топологические выходы считывания блока 2 управления.

Выходы 38 и 39 - выходы обращения к буферным регистрам 13 и 14 блока 2 управления.

Выходы,40 и 41 - управляющие топологические выходы записи блока 2 управления.

Входы 42 - 44 - группа управляющих входов топологических меток блока 2 управления.

Вход 45 - вход окончания временного моделирования блока управления 2. Выходы 46 - 56 - группа управляющих выходов блока 2 управления, соответствующая ей группа входов 57 - 67 арифметического блока 3.

Выход 68 - счетньй выход блока 2 управления, соответствующий ему вход 69 арифметического блока 3.

Выход 70 - информационный выход метки блока управления 2, соответствующий ему вход 71 арифметического блока 3.. .

Выход 72 - выход свершения узла |арифметического блока 3, соответствующий ему входу 73 блока 2 з равлення.

Выходы 74-75 - управляющие выходы операционных меток арифметического блока 3, соответствующие им входы 76-77 блока 2 управления.

Выходы 78-79 - выходы свершения блокЗ 4 регистрации, соответствующие им входы 80-81 блока 2 управления, выходной полюс 82 устройства.

Выходы 83 - 88 - группа управляющих выходов регистрации блока 2 управления, соответствующая ей группа входов 89 - 94 блока 4 регистрации, информационный вход 95 метки блока 4 регистрации.

В блоках памяти первой выходящей 5 и первой входящей 6 ветвей по адресу номера узла содержится информация о номере соответствующих ветвей. В последнем информационном разряде блоков памяти первой входящей ветви 6 содержится метка. Число блоков 5 и 6 памяти равно числу узлов сети.

В блоках памяти выходящих 7 и входящих 8 ветвей информация о номере ветви содержится по адресу номера предшествующей ветви. Таким образом содержится информация о соответствующем списке ветвей. По адресу номера последней ветви в списке находится информация . о номере узла и метка :в последнем информационном разряде, iЧисло блоков 7 и 8 памяти соответствует числу ветвей исследуемой сети.

На фиг. 2 приведена схема арифметического блока 3, который содержит блок 96 памяти длительности, блок.97 памяти длительности, блок 98 памяти ветвей, комбинационный сумматор 99, счетчик 100 длительности, регистр 10 относительной длительности, регистр

102считываемой длительности, узел

103сравнения, буферные регистры 104 1- 106, коммутаторы 107 и 108, элемент ИЛИ 109.

Блок-96 памяти длительности содержит по адресу номера ветви инфор- : мацию о ее длительности.

Блок.97 памяти длительности содержит nQ адресу относительной длительности информацию о номере ветви.

Блок 98 памяти ветвей предназначе для хранения инфорг4ации. о списке номеров ветвей, имеющих одинаковую относительную длительность, причем в таком списке по номеру первой из данных ветвей содержится информация о метке и в остальных по адресу номера ветвей содержится информация о номере предьздущей ветви в этом списке.

ч

Узлы 12 и 103 сравнения представляют собой многоразрядную схему совпадения .

Регистры 9-11, 13, 14, 101, 102,

104- 106 представляют собой регистры с параллельным приемом информации

На фиг. 3 приведена схема блока 4 регистрации, который содержит элемент ИЛИ 110, блок 111 памяти свершения ветвей, блок 112 памяти дерева длиннейших путей, блок 113 памяти ветвей длиннейшего пути, триггеры 114 и 115. Блок 111 памяти свершения ветвей по адресу номера ветви содержит информацию о завершении процесса временного моделирования ветви.

Блок 112 памяти дерева длиннейших путей по адресу номера ветви содержит информацию о ветвях, завершивших последними процесс временного моделирования для данного узла.

Блок 113 памяти ветвей длиннейшего пути по адресу номера ветви содержит информацию о принадлежности ветвей длиннейшего пути.

На фиг. 4 приведена схема блока 2 управления, который содержит триггер 116 прерывания, генератор 117 тактовых импульсов, регистр 1Ш состояния, шифратор 119.

Регистр 118 состояний представляет собой регистр с параллельным приемом информации, выполненный на двойных триггерах типа ведущий - ведомый так, что принимаемая в

регистр информация имеет место на его выходах лишь после снятия синхронизирующего сигнала управления от генератора импульсов.

Шифратор 119 преобразует комбинации кодов на его входе в определенные комбинации кодов на выходе в зависимости от состояния регистра 118. ифратор выполнен на диодных сборках.

До момента решения задачи на устройстве оператор в блоки памяти первой выходящей ветви 5, первой входящей ветви 6, выходящих ветвей 7 и входящих ветвей 8 блока 1 формирования топологии заносит информацию о топологии сети, а в блоки памяти длительности 96 арифметического блока 3 - информацию о длинах ветвей. При этом выбор первых выходящей

и входящей ветвей для каждого узла, а также формирование списков выходящих и входящих ветвей осуществляется оператором произвольно.

Код конечного узла сети заносится в регистр 10 конечного узла, а код начального узла - через элемент ИЛИ 17 по управляющему сигналу с входа 24 от блока 2 управления с выхода 40 - в регистр 9 текущего узла. Все остальные регистры, счетчик, триггеры и остальные ячейки памяти устанавливаются в нулевое состояние.

Топологическое моделирование

заключается в определении моментов

свершения узла и подготовке к

временному моделированию ветвей,

исходящих из свершившегося узла.

Для установления факта свершения узла необходимо, чтобы закончились все входящие в узел ветви. Это определяется опросом всего схюска входящих в узел ветвей. Опрос начи- нается с номера ветви, которая закончила процесс временного моделирования и, перебирая все элементы списка, проверяют свершения ветвей. По номеру последней в списке ветви счи- тьтают номер узла, в который входят данные ветви. По номеру узла переходят в начало списка и продолжают процедуру опроса до появления номера ветви, с которого начался процесс. Если в результате обнаружится, что все входящие в узел ветви закончили процесс временного моделирования своих ;су1ительностей, т узел считается свершенным и пере- ходит к формированию списка ветвей, выходящих из данного узла, и временному моделированию.

Подготовка к временному моделированию длительностей ветвей заключа- ется в установлении связей между моделируемыми ветвями.. Для этого по величине длительности ветви из блока 96 памяти и содержимого счетчика измерений суммированием определяют величину относительной длительности ветви. Максимально возможная длительность ветви в сети определяется 2 - - 1, а полная емкость счетчика измерений равна 2 - 1, где m - число ветвей в сети для случая, если сеть представляет собой последовательное соединение всех ветвей одна за другой в цепь. Далее, используя величину относительной длительности ветви в качестве адреса, номер ветви записывается в блок 97 памяти длительности, а в п -и разряд информационного слова ставится метка, свидетельствующая о наличии и процессе вре- менного моделирования ветви с данной относительной длительностью. В блоке 98 памяти ветвей по адресу номера данной ветви заносится метка в п -м разряде. Данная метка предназначена для определения последней из списка ветви с одинаковой относительной длительностью. Если список состоит из одной ветви, то она будет, естест венно, первой и последней. Бели же на последующих этапах моделированяя появляются ветви с такой же величиной относительной длительности, то.

j 0 5 0

определив в процессе моделирования по метке наличие ветвей с данной относительной длительностью,- выполняется запись новой ветви в ячейки памяти.

Запись осуществляется следующим образом.

По адресу величины относительной длительности в блок 97 памяти длительности з;аписывается номер новой ветви и метка в и -м разряде, а в блок 98 памяти ветвей по адресу номера новой ветви записывается номер ветви, которая до этого была в данном списке ранее, и метка в п -м .разряде не ставится. Таким образом, организуется связь между элементами с одинаковой относительной длительностью в процессе подготовки к временному моделированию.

Блок 2 управления организует функционирование устройства следующим образом. По адресу номера начального узла и управляющему топологическому сигналу считывания с входа 20 от блока 2 управления с выхода 36 из блока памяти первой выходящей ветви 5 поступает информация о но- мере ветви через элемент ИЛИ 16 и записывается по управляющему сигналу записи с входа 25 от блока 2 управления с выхода 41 регистр 11 текущего адреса, с этого момента с выхода этого регистра на адресных шинах; блоков 7 памяти выходящих ветвей находится информация о номере ветви, следовательно, в буферном регистре 13 находится номер следующей ветви в списке. С выхода 30 блока 1 формирования топологии через вход 31 ариф метического блока 3 информация о но мере Ьетви поступает на адресные шины блока 96 памяти длительности и через элемент ШШ 109 блока 98 памяти ветвей - на информационные шины блока 97 памяти длительности. По адресу номера ветви и управляющему сигналу считывания с входа 57 от блока 2 управления с выхода 46 информация о длительности ветви из блока 96 памяти длительности поступает на адресные шины блока 97 памяти длительности.

При этом прохождение информации о длительности ветви через буферный регистр 104, сумматор 99 (на второй вход которого в начальный момент поступает О), регистр 101 относи

тельной длительности, коммутатор 107 обеспечивается управляющими сигналами соответственно с входов 65, 63, 66 ари||метического блока 3 от блока 2 управления соответственно с выходов 54, 52 и 55.

По управляющему сигналу считывания с входа 59 арифметического блока 3 с выхода 48 блока 2 управления из блока 97 памяти длительности поступает информация в буферный ре- тистр 105 (в данный момент времени нулевая- информация). Далее по управ- лякяцимсигналаг:1 записи с входов 58 и 60 арифметического блока 3, с выходов соответственно 47 и 49 блока 2 управления заносится информация о номере ветви по адресу ее длины в блок 97 памяти длительности, и по адресу номера ветви в блок 98 памяти ветвей с входа 71 арифметического блока 3 из блока 2 управления с информационного выхода метки 70 в последние разряды заносится метка.

Вновь по управляющему сигналу записи с входа 25 в регистр 11 текущего адреса заносится информация из буферного регистра 13 о номере следующей ветви в списке. Повторяется вся последовательность сигналов аналогично изложенному.

Процесс повторяется до тех пор, пока не обратится к ветви, последней в списке, связанном с данным у:з- лом, и с выхода 27 блока 1 формирова ния топологии через вход 43 в блок 2 управления не поступит сигнал метки с последнего разряда буферного регистра 13.

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

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

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

Для этого блок 2 управления через счетный выход 68 в арифметический Ьлок 3 на вход 69 подает импульс, который поступает на вход счетчика 100 и далее через коммутатор 107 - . на адресные входы блока 97 памяти длительности. Прохождение информации обеспечивает управляющий сигнал с входа 63 арифметического блока 3 от блока управления соответственно с выхода 52.

Блоком 2 управления осуществляется считьшание информации о номере ветви по адресу со счетчика 100 из блока 97 памяти длительности в буферный регистр 105. Процесс поступления счетных импульсов повторяется до тех пор, пока с выхода 74 последнего информационного разряда буферного регистра 105 арифметического блока 3 через вход 76 в блок 2 управления не поступит сигнал о метке, 1тем самым определяется ветвь с минимальной относительной длительностью в данный момент времени.

Через коммутатор 108 по управляющему сигналу записи с входа 67 арифметического блока 3 с выхода 56 от блока 2 управления в регистр 102 считываемой длительности запоминается информация о номере ветви и устанавливается в единичное состояние триггер 116 прерывания в блоке 2 управления.

Номер ветви из регистра 102 считываемой длительности находится не- рез элемент ИЛИ 109 на адресных входах блока 98 памяти ветвей и с выхода 33 арифметического блока 3 через вход 35 блока 1 формирования то пологий через элемент ИЛИ 16 на входе регистра 11 текущего адреса, с входа 34 блока 4 регистрации через i элемент ИЛИ 110 на адресных шинах блока 111 памяти свершения ветвей. Кроме того, эта информация находится на входе схемы 103 сравнения.

По управляющему сигналу записи с входа 25 блока 1 формирования топологии и с входа 89 блока 4, регистрации от блока 2 управления соответственно с выходов 4т и 83 записывает-- ся номер ветви в регистр 11 текущего адреса и по адресу номера ветви с входа 95 заносится метка в блок 111 памяти свершения ветвей из регистра 102 считываемой длительности.

По адресу номера ветви из регистра 1 1 текущего адреса с выхода 30 блока 1 формирования топологии на вход 32 блока 4 регистрации через элемент ИЛИ 110 при условии наличия метки по управляющему сигналу с входа 90 от блока 2 управления с вхо- да 84 устанавливается в,единичное состояние триггер 114.

В блоке формирования топологии по сигналу с входа 23 от блока 2 управления с выхода 39 по адресу из регистра 11 текущего адреса заносится ин- (формация из блока 8 памяти входящих ветвей в буферный регистр 14 и далее через элемент ИЛИ 16 - в регис:тр 11 текущего адреса. Таким образом, наличием сигнала с единичного выхода триггера 114 через выход 78 блока 4 регистрации на вход 80 блока 2 управления проверяются на свершение все последующие ветви из списка входящих в узел, начиная с ветви с минимальной относительной длитель- ностью в данный момент.

Процесс повторяется до тех пор, пока с выхода последнего разряда 28 буферного регистра 14 блока 1 формирования топологии через вход 44 в блок 2 управления не поступит сигнал топологической метки, свидетельствую- щей о том, что данная ветвь в анапи- зируемом списке последняя и в буферном регистре 14 находится информация о номере узла, в котором она заканчивается.Информация с выхода буферного регистра 14 через элемент ИЛИ 17 о номере узла запоминается в регистре 9 текущего узла.и подается далее на

адресные входы блока памяти первой входящей ветви 6. Это обеспечивается подачей управляющих сигналов с входов 24 и 21 блока 1 формирования топологий от блока 2 управления соответственно с выходов 40 и 37.

Далее, как и для случая списка выходяощх ветвей, блок 2 управления, используя информацию в блоке 6 памя-

ти первой входящей ветви и в блоке 8 памяти входящих ветвей и регистр 11 текущего адреса, проверяет на свершение список входящих ветвей (для номера узла, находящегося в регистре

текущего узла 9). При этом всякий раз аналогично осуществляется блоком 2 управления и блоком 4 регистрации проверка на свершение анализируемых ветвей. Кроме того, после

поступления через вход 44 в блок управления сигнала топологической метки информация о номере ветви в регистре 11 текущего адреса всякий раз сравнивается через выход 30 блока 1

формирования топологии и вход 31 арифметического блока 3 узлом сравнения 103 с информацией , хранящейся, в регистре 102 считываемой длительности о номере ветви, с которой начался анализ.

Сигнал совпадения кодов в узле 103 сравнения является сигналом свершения узла с выхода 72 арифметического блока 3 в блок 2 упра,вления на вход 73. По этому сигналу и управляющему сигналу с выхода 85 блока 2 управления на вход 91 блока 4 регистрации заносится метка с входа 95 в ячейки памяти дерева длиннейших пу|Тей 112, так как именно данная ветвь окончила прбцесс моделирования последний среди всех ветвей, оканчивающихся в данном узле. I

По сигналу свершения узла осуществляется узлом 12 сравнения сравнение кодов номеров узлов в регистре 10 ко нечного узла и регистре 9 текущего узла, так как в последнем хранился номер анализируемого узла. В случае

совпадения этих кодов с выхода 29 блока 1 формирования топологии на вход 45 блока 2 управления подается сигнал окончания временного моделирования.

После считывания информации из блока 96 памяти длительности на сумматоре 99 образуется и в регистр 101 относительной длительности заносится

111206791

относительная длительность, равная сумме длины считываемой ветви и содержимого младших разрядов счетчика 100. Число младших разрядов счетчика соответствует величине максимальной длины среди всех длин ветвей.

По адресу относительной длительности 4 из блока 97 памяти длительности с выхода последнего разряда буферного регистра 105 с выхода 74 арифметического блока 3 на вход 76 блока 2 управления считывается мет- ка, в остальных разрядах будет ин-- формация о. номере ветви, занесенной по этому адресу ранее при рассмотре- НИИ узла 1. Блок 2 управления сигна- лом с выхода 49 на вход 60 арифметического блока 3 по адресу номера ветви из регистра 11 текущего адреса записывает информацию о номере соЬтве.тствующей ветви в блок 98 .па- мяти ветвей.Далее блоком2 управления в блок 97 памяти длительности по адресу относительной длительности 4 заносится информация о номере следующей ветви.

Повторяется описанный анализ на

жащ лен неч

5 кущ вой вхо етс нах

10 ка ния в д мом буд

15 вых гис лен рег с в

20 с п дли

в р адр

25 ка вае ном спи Про

свершение ветвей, топологически связанных окончанием в узле с данной ветвью, полученной из списка вет- зо ления сигнала метки с выхода 27

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

Так повторяется до тех пор, пока в блок 2 управления с полюса 77 не поступит сигнал метки о том, что ветвь, по адресу которой в буферном регистре 106 проводилось считывание информации из блока 98 памяти ветвей, является последней в списке ветвей с равной относительной длительностью. В этом случае считанная в регистр 102 считываемой длительности информация является не номером очередной ветви, а лишь меткой, по которой и определяется конец списка блоком 2 управления. Затем триггер 116 прерывания ставится в нулевое состояние, а по адресу величины относительной длительности в счетчике 100 в памяти длительности 97 обнуляется метка.

Число импульсов, накопленное к моменту окончания моделирования в счетчике 100, будет соответствовать величине длиннейшего пути в сети.

12

Для определения ветвей, принадлежащих длиннейшему пути, т.е. определения его структуры, по номеру конечного узла сети в регистре 9 текущего узла из блока 6 памяти первой входящей ветви и блока 8 памяти входящих ветвей аналогично вызывается список свершившихся ветвей и находится по сигналу с входа 92 блока 4 регистрации от блока 2 управления с выхода 86 ветвь, свершившаяся в данном узле последней (в данный момент - в конечном узле). Об этом будет служить сигнал с единичного

выхода 79 триггера 115 блока 4 регистрации на вход 81 блока 2 управ- ления, по сигналу с входа 93 блока 4 регистрации от блока 2 управления с выхода 87 заносится сигнал метки

с полюса 95 в ячейки памяти ветвей длиннейшего пути 113.

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

блока 1 формирования топологии на вход 43 блока 2 управления о том, что данная ветвь из списка выходящих из анализируемого узла послед- няя, следовательно, в регистре 11 текущего адреса - информация о номеч ре ее начального узла.

Полученный номер начального узла ветви заносится в регистр 9 текущего узла, и организуется поиск ветви, входящей в данный узел и принадлежащей дереву длиннейших путей.

Процесс определенияструктуры длин- нейшего пути продолжается до прихода в начальж 1й узелсети ипоявления навхо- де 42блока 2управления с единичного выхода 26трггера 15нулевого сигнала, так как лишь у этого узла не имеется списка входящих в него ветвей.

5

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

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

5

0

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

выходам блока регистрации, причем арифметический блок выполнен в виде первого и второго коммутаторов, узла сравнения, первого, второго, третьего, четвертого и пятого регистров, счетчика, сумматора, первого, второго и третьего блоков памяти элементов ИЛИ, выход которого подключен к первому входу первого блока памяти, управлякяций вход записи которого соединен с управляющими входами, записи второго и третьего блоков памяти и подключен к входу управления записью арифметического блока, выход первого блока памяти подключен к входу первого регистра, выходы всех разрядов которого, кроме последнего, соединены с первым информационным входом первого коммутатора, второй информационный вход которого подключен ко всем разрядам, кроме последнего, второго регистра, вход которого соединен с выходом второго блока памяти, выход первого коммутатора соединен с ин0 формационным входом третьего регистр ра, выход которого соединен с первыми входами узла сравнения и элемента ИЛИ, второй вход узла сравнения соединен с вторым входом элемен5 та ИЛИ, с первыми входами второго и третьего блоков памяти и подключен к второму информационному входу apифмeтичecкofo блока, выход третье0

5

0

5

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

и пятого регистров, входы выбор си адреса первого, второго и третьего блоКов памяти и входы разрешения записи

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

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

2, Устройство по п. 1,о т л и чающееся тем, что блок регистрации выполнен в виде первого и второго триггеров,первого,второго Гтретье- го блоков памяти и элемента ИЛИ,причем выход элемента 11Ш. подключен к первому

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

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

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

(I о ( I

75 67 Фиг. г

W О-

Ш

Фиъ.3

91

Фиг.

Составитель A. Колчин Редактор П. Коссей Техред 3.Палий Корректор Л. Патай

Заказ 8714/50 Тираж 673 Подписное ВНИШШ Государственного комитета СССР

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

Филиал ШШ Патент, г. Ужгород, ул. Проектная, 4