Матричный вычислитель

 

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

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

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

РЕСПУБЛИН (д) 4 G 06 F 15/347

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 4106009/24-24 (22) 07.08.86 (46) 23.07.88. Бюп. У 27 (71) Винницкий политехнический институт (72) И.В.Кузьмин, И,М.Мусаев, В.И.Роптанов и С.В. Юхимчук (53) 681.333 (088.8) (56) Авторское свидетельство СССР

Р 943738, кл. С 06 F 15/20, 1980.

Авторское свидетельство СССР ,У 1363247, кл. G 06 F 15/347, 1986.

„„Я0„„1411778 А1 (54) МАТРИЧНЫЙ ВЫЮ1СЛИТЕЛЪ (57) Изобретение относится к вычислительной технике, может быть использовано при исследовании параметров сетевых графов и позволяет вычислять величины максимальных и минималь ых путей в графе. Целью изобретения является повьппение быстродействия. С этой целью матричный вычислитель содержит матрицу вычислительных блоков, функциональные связи которых обеспе-, чивают асинхронное вычисление максимального (минимального) пути в графе. 1 s.ï. ф-лы, 2 ил.

1411778

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

На фиг. 1 представлен матричный ( вь»числитель на фиг. 2 — схема вычисЭ

;ления максимального (минимального) пути в графе.

Вычислитель содержит генератор 1 15 импульсов, элемент И 2, элемент HE 3,,матрицу 4 вычислительных блоков, триггер 5, элемент И б, регистр 7, группу триггеров 8, группу элементов

И 9, группу регистров 10, сумматор 20 ,11, схему 12 сравнения, группу блоков

13 элементов И, группу блоков 14 эле ментов ИЛИ, группу триггеров 15, группу элементов И 16, rp уппу р er истров 17, группу сумматоров 18, группу 25

: схем 19 сравнения, две группы блоков 20 элементов И, группу блоков 21 элементов ИЛИ, группу триггеров 22, группу элементов И 23, группу регистров 24, группу сумматоров. 25, груп- 30 .пу схем 26 сравнения, три группы бло-. ков 27 элементов И, группу блокоВ 28 элементов ИЛИ, группу триггеров 29,,группу элементов И 30, группу регист ров 31, группу сумматоров 32, группу ., схем 33 сравнения, три группы блоков

34 элементов И и группу блоков 35 элементов ИЛИ.

Вычислитель работает следующим образом. 40

Первоначально в соответствующие регистры и триггеры заносится информация о топологии графа и весах его .ветвей. Для графа, представленного на фиг. 2, триггеры 5, 8, 8, 15»вЂ”

15З, 22» -224 и 29 -29 устанавливают в единичное состояние. Триггер 5 соответствует ветви 5-6 графа, триггеры 8 и 8 — ветвям 4-6 и 4-5,тригrеры 15

15 — ветвям 3-6, 3-4 и 3-5, триггеры 22» -224 — ветвям 2-6, 2-3, 2-4 и

2-5, триггеры 29» -29 — ветвям 1-6, 1-2, 1-3, 1-4 и 1-5. В регистры 7, 10» и 10, 17» -17, 24» -244> 31, -31 записьщаются коды ветвей мод "ируемо 55 го графа, Так в регистр 7 заносится код ветви 5-6, а в регистр 10, и 10< — коды ветвей 4-6 и 4-5, в регистры 17»вЂ”

17 — колы ветвей 3-6, 3-4 и 3-5, в регистры 24» — 244 — коды ветвей 2-6, 2-3, 2-4 и 2-5, в регистрь1 31, -31 — коды ветвей 1-6, 1-2, 1-3, 1-4 и 1-5 соответственно. Так как в моделируемом графе нет ветвей 1-6, 1-4 и 1-5, то в регистры 31, 314, 31» заносится код нуля.

С появлением сигнала на входе пуска устройства элемент И 2 обеспечивает прохождение сигнала с выхода генератора 1, который через элемент

И 2, поступает на второй вход элементов И 6 и на входы элементов И 9» и

9 . Так как триггеры 5, 8, и 8 находятся в единичном состоянии, то через элементы И 6, 9» и 9 сигнал поступает на входы регистров 7, 10» и

10, что в свою очередь обеспечивает подачу кодов с регистра 7 на второй вход сумматора 11 второй группы, Код с регистра 10 поступает на первый вход сумматора 11, а код с регистра

10 — на первый вход схемы 12 сравне» ния и первый вход блока 13» элементов И. Таким образом, на выходе сумматора 11 появляется код, соответствующий пути 4-5-6 моделируемого графа. Код с выхода сумматора 11 поступа ет на второй вход схемы 12 сравнения и на первые входы блоков 13,и 13> элементов И. Код ветви графа 4-6, записанный в регистре 10», поступает на первый вход схемы 12 сравнения и первый вход блока 13» элементов И. В схеме 12 сравнения пути сравниваются и выбирается наибольший (в данном случае путь 4-6) . Поэтому сигнал

It появляется на выходе признака Больше" схемы 12 сравнения и выдается на второй вход блока 13 элементов И, что обеспечивает прохождение кода пути 4-6 через блок 13, . Этот код подается на второй вход сумматора 18 через блок 142 элементов ИЛИ. Одновременно сигнал выхода схемы 12 сравнения поступает через блок 14< элементов ИЛИ на вторые входы блоков

16 -16 элементов И. Так как триггеры

» 3

15 -15 находятся в единичном состоя» 3 нии, то через блоки 16 -161 указанный сигнал выдается на вход признака чтения регистров 17» -17» в которых записаны коды ветвей 3-6, 3-4 и 3-5 графа, что обеспечивает выдачу кодов веса ветвей с регистра 17„на первый вход блока 20» и на первый вход схемы

19» сравнения. Код с регистра 17

1411778

ЗО

55 подается на первый вход сумматора

18, код с регистра 171 — на первый вход сумматора 18 . Одновременно на второй вход сумматора 18 вьдается код веса ветви с регистра 7, который соответствует коду ветви 5-6 модулируемого графа. Таким образом, на выходе сумматора 18 появляется код, соответствующий путй 3-4-6 графа, а на выходе сумматора 18> — код, соответствующий пути 3-5-6 графа. Код с выхода сумматора 18< подаемся на второй вход схемы 19 сравнения и на первые входы блоков 20 и 20, элемен тов И. Код с выхода сумматора 18< подаемся на второи вход схемы 19> сравнения и на первые входы блоков

20 и 206 элементов И. В схеме 19 сравнения сравниваются пути 3-6 и

3-4-6 и выбирается наибольший (в данном случае путь 3-4-6). Поэтому сигнал появится на выходе признака "Мень ше" схемы 19 сравнения. Этот сигнал поступает на второй вход блока 20> элементов И, что обеспечивает про,хождение кода веса пути 3-4-6 через блок 20>, этот код подается на первый вход схемы 19 сравнения и на первый вход блока 204 элементов И через блок 21 элементов ИЛИ. В схеме

19 сравнения сравниваются пути 3-4-6 и 3-5-6 и выбирается наибольший (в данном случае путь 3-4-6). Поэтому сигнал появится на выкоде признака

"Больше" схемы 19 сравнения, Этот сигнал подается на второй вход блока

20 4 элементов И, что обеспечивает прохождение кода пути 3-4-6 через блок 20 элементов И, который подается на второй вход сумматора 25 через блок 21 элементов ИЛИ. Одновременно сигнал с выхода схемы 19 сравнения через блок 21 элементов ИЛИ поступает на вторые входы блоков 23>234 и т,де

По окончании процесса вычисления на выходе блока 35 появляется код веса максимального пути 1-3-4-6 или

1-2-3-4-6 графа. Одновременно сигнал с выхода схемы 33 сравнения поступает на вход элемента НЕ 3 через блок

354 элементов ИЛИ и работа устройства прекращается.

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

1. Матричный вычислитель, содержащий матрицу из (P-1) строк по (P-К) вычислительных блоков в каждой строке, где Р— количество вершин в графе, К = 1,..., (P-1) — порядковый номер строки матрицы, о т л и ч а ю— шийся тем, что, с целью повышения быстродействия при вычислении максимального (минимального) пути в графе, первый информационный вход К-й группы матричного вычислителя является входом задания веса пути из К-й в (К+1)-ю вершину графа и подключен к первому информационному входу первого вычислительного блока К-й строки матрицы, (М+1)-й информационньп . вход К-й группы матричного вычислителя является входом задания веса пути из К-1 в (К+М)-ю вершину графа и подключен к второму информационному входу М-го вычислительного блока (М=

1,...,(Р-К)) К-й строки матрицы, первый информационный вход P-й группы матричного вычислителя является входом задания веса пути из (P-1) — и в

P-ю вершину графа и подключен к третьему информационному входу первого вычислительного блока первой строки матрицы, выход М-ro вычислительного блока (М ф Р— К) К-й строки матрицы подключен к первому входу (М+1)-ro вычислительного блока той же строки матрицы, выкод (P-К)-го вычислительного блока К-й строки (К Ф 1) подключен к третьему информационному входу первого вычислительного блока (К-1)-й .! е строки матрицы, третий информационный вход M-го вычислительного блока (К+1)-й строки матрицы подключен к третьему информационному входу (М+1)ro вычислительного блока К-й строки матрицы, выход (P-1)-го вычислительндго блока первой строки матрицы является информационным выходом устройства, вход управления вычисления максимального (минимального) пути устройства подключен к входам задания режима работы всех вычнслительных блоков матрицы. .2. Вычислитель по п. 1, о т л и— ч а ю шийся тем, что каждьй вычислительный блок содержит блок элементов ИЛИ, три блока элементов

И, сумматор и схему сравнения, вход задания режима "Выбор большего— выбор меньшего", который является входом задания режима работы вычислительного блока, первый информационньп1 вход которого подключен к первому вхо. ду блока элементов И и к первому ин5 1411778 6 формационному входу схемы сравнения, третьего блоков элементов И и второыход признака "Больше" которой под- му информационному входу схемы сравлючен к второму входу первого блока нения, выходЪ| признаков "Равенство" и лементов И, выход которого подключен э "Меньше" которой подключены к вторым первому входу блока элементов ИЛИ, входам соответственно второго и треторой и третий информационные входы тьего блоков элементов И, выходы колока вычислений подключены соответ- торых подключены к второму и третьетвенно к входам первого и второго му входам блока элементов ИЛИ соот лагаемых сумматоров, выход которого 10 ветственно, выход которого является .Подключен к первым входам второго и выходом блока вычислений, 1411778

Составитель А.Мишин

Редактор Н.Лазаренко Техред А.Кравчук Корректор С.Шекмар

Заказ 3656/46

Тираж 704 Подписное

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

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

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