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

,ЯО 14117 6 Р 15/3 ОПИСАНИЕ ИЗОБРЕТЕНИ ИДЕТЕЛЬСТВ У АВТОРСКОМ(71) Винницкий политех ческий инстиУДАРСТВЕННЫЙ НОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) Авторское свидетельство СССРУ 943738, кд. С 06 Р 15/20, 1980.Авторское свидетельство СССРй 1363247, кл, С 06 Р 15/347, 1986.(57) Изобретение относится к вычислительной технике, может быть использовано при исследовании параметровсетевых графов и позволяет вычислятьвеличины максимальных и минимальныхпутей в графе. Целью изобретения является повьппение быстродействия. Сэтой целью матричный вычислитель содержит матрицу вычислительных блоков,Функциональные связи которых обеспе-,чивают асинхронное вычисление максимального (минимального) пути в граФе. 1 э.п. Ф-лы, 2 ил,Изобретение относится к вычислительной технике, может быть использовано при исследовании параметров сетевых графов и позволяет определлтьвеличины максймальных и минимальныхпутей в графах,Пель изобретения - повышение быстродействия при вычислении максималь"ного (минимального) пути в графе, 10На фиг. 1 представлен матричныйвьчислитель на фиг. 2 - схема вьчис,11, схему 12 сравнения, группу блоков13 элементов И, группу блоков 14 элементов ИЛИ, группу триггеров 15,группу элементов И 16, группу регистров 17, группу сумматоров 18, группу 25схем 19 сравнения, две группы блоков20 элементов И, группу блоков 21элементов ИЛИ, группу триггеров 22,группу элементов И 23, группу регистров 24, группу сумматоров, 25, группу схем 26 сравнения, три группы блоков 27 элементов И, группу блокоВ 28элементов ИЛИ, группу триггеров 29,,схем 33 сравнения, три группы блоков34 элементов И и группу блоков 35 . лгэлементов ИЛИ.Вычислитель работает следующим образом. 40Первоначально в соответствующиерегистры и триггеры заносится информация о топологии графа и весах его,ветвей. Для графа, представленногона фиг. 2, триггеры 5 8 8 15 4515 З, 22 -22 и 29 -29 устанавливаютв единичное состояние. Триггер 5 соответствует ветви 5-6 графа, триггеры 8 и 8 - ветвям 4-6 и 4-5, триг г еры 1515 - ветвям 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 и 1017 -1724 -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 элементов И. Таким образом, на выходе сумматора 1 1 появляется код, соответствующий пути 4-5-6 моделируемого графа. Код с выхода сумматора 11 поступа ет на второй вход схемы 12 сравнения и на первые входы блоков 13 ,и 13 элементов И, Код ветви графа 4-6, записанный в регистре 10, поступает на первый вход схемы 12 сравнения и первый вход блока 13 элементов И. В схеме 12 сравнения пути сравниваются и выбирается наибольший (в данном случае путь 4-6), Поэтому сигналпоявляется на выходе признака Больше" схемы 12 сравнения и выдается на второй вход блока 13 элементов И, что обеспечивает прохождение кода пути 4-6 через блок 13, . Этот код подается на второй вход сумматора 18. через блок 14 элементов ИЛИ. Одновременно сигнал выхода схемы 12 сравнения поступает через блок 14 элементов ИЛИ на вторые входы блоков 16 -16 элементов И, Так как триггеры315 -15 находятся в единичном состоя 3нии, то через блоки 16-16 указанный сигнал выдается на вход признака чтения регистров 17 -17 З, в которых записаны коды ветвей 3-6, 3-4 и 3-5 графа, что обеспечивает выдачу кодов веса ветвей с регистра 17 на первый вход блока 20 и на первый вход схемы 19 сравнения, Код с регистра 17подается на первый вход сумматора18, код с регистра 17 - на первыйвход сумматора 18 е. Одновременно навторой вход сумматора 18 вьдаетсякод веса ветви с регистра 7, которыйсоответствует коду ветви 5-6 модулируемого графа. Таким образом, навыходе сумматора 181 появляется код,соответствующий путй 3-4-6 графа, ана выходе сумматора 18 - код, соответствующий пути 3-5-6 графа. Код свыхода сумматора 18 подаемся на второй вход схемы 191 сравнения и напервые входы блоков 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 черезблок 204 элементов И, который подается на второй вход сумматора 251 через блок 21 элементов ИЛИ. Одновременно сигнал с вь 1 хода схемы 19 сравнения через блок 21 элементов ИЛИпоступает на вторые входы блоков 23234 и тедеПо окончании процесса вычисленияна выходе блока 35 появляется кодвеса максимального пути 1-3-4-6 или1-2-3-4-6 графа. Одновременно сигналс выхода схемы 33 сравнения поступает на вход элемента НЕ 3 через блок354 элементов ИЛИ и работа устройства прекращается,Формула изобретения1. Матричный вычислитель, содержащий матрицу из (Р) строк по (Р-К)10 152025 ЗО35 40 ляется информационным выходом устройства, вход управления вычисления максимального (минимального) пути уст-. ройства подключен к входам задания режима работы всех вычнслительных блоков матрицы..2. Вычислитель по п, 1, о т ли - ч а ю щ и й с я тем, что каждьй вычислительный блок содержит блок элементов ИЛИ, три блока элементов И, сумматор и схему сравнения, вход задания режима "Выбор большего - выбор меньшего", который является входом задания режима работы вычислительного блока, первый информационньп 1 вход которого подключен к первому вхо ду блока элементов И и к первому ин 45 50 55 вычислительных блоков в каждой строке, где Р - количество вершин в графе, К = 1(Р) - порядковый номер строки матрицы, о т л и ч а ю - щ и й с я тем, что, с целью повышения быстродействия при вычислении мак. симального (минимального) пути в графе, первый информационньп вход К-йгруппы матричного вычислителя является входом задания .веса пути из К-й в (К+1)-ю вершину графа и подключен к первому информационному входу первого вычислительного блока К-й строки матрицы, (М+1)-й информационньп . вход К-й группы матричного вычислителя является входом задания веса пути из Кв (К+М)-ю вершину графа и подключен к второму информационному входу М-го вычислительного блока (М=1(Р-К К-й строки матрицы, первый информационный вход Р-й группы матричного вычислителя является входом задания веса пути из (Р)-й вР-ю вершину графа и подключен к третьему информационному входу первого вычислительного блока первой строки матрицы, выход М-го вычислительного блока (МР - К) К-й строки матрицы подключен к первому входу (М+1)-го вычислительного блока той же строкиматрицы, выход (Р-К)-го вычислительного блока К-й строки (К Ф 1) подключен к третьему информационному входу первого вычислительного блока (К)-й.строки матрицы, третий информационный вход М-го вычислительного блока (К+1)-й строки матрицы подключен к третьему информационному входу (М+1)- го вычислительного блока К-й строки матрицы, выход (Р)-го вычислительндго блока первой строки матрицы яв 5 1411778 6 формационному входу схемы сравнения, третьего блоков элементов И и второыход признака "Больше" которой под- му информационному входу схемы сравлючен к второму входу первого блока нения, выходЪ признаков "Равенство" и лементов И, выход которого подключен "Меньше" которой подключены к вторымпервому входу блока элементов ИЛИ, входам соответственно второго и треторой и третий информационные входы тьего блоков элементов И, выходы колока вычислений подключены соответ- торых подключены к второму и третье- твенно к входам первого и второго му входам блока элементов ИЛИ соот-лагаемых сумматоров, выход которого 1 О ветственно, выход которого является .подключен к первым входам второго и выходом блока вычислений,,Шекма Тираж 70 каз 365646 5 ая на роизводственно-поли рафическое предприятие, г. Ужгород, ул, Проектная,ВПИИПИ Государственного по делам изобретений113035, Москва, Ж, Рауш Подписноеитета СССРткрытий