Устройство поиска степени оптимальности размещения в кластерных многопроцессорных системах

Изобретение относится к области цифровой вычислительной техники. Технический результат заключается в расширении области применения устройства за счет введения средств для поиска минимального значения интенсивности размещения в многопроцессорных гиперкубических системах по критерию минимизации интенсивности взаимодействия процессов и данных. Технический результат достигается за счет устройства для поиска степени оптимальности размещения в кластерных многопроцессорных системах, содержащего блок с первого по n-й поиска степени оптимальности, содержащий матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) сумматоров, второй счетчик строк, первый счетчик столбцов, второй счетчик столбцов, матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) регистров, первый и второй дешифраторы горизонтально зафиксированных дуг, первый и второй дешифраторы вертикально зафиксированных дуг, матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ, первую матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, вторую матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, первый счетчик строк, первый многовходовой блок сумматоров, счетчик номера кластера, дешифратор номера кластера, второй многовходовой блок сумматоров многопроцессорной системы, элемент И номера кластера многопроцессорной системы, первый элемент ИЛИ номера кластера многопроцессорной системы, второй элемент ИЛИ номера кластера. 1 з.п. ф-лы, 9 ил.

 

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

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 1291957 СССР кл. G06F 7/00, опубл. 23.02.87, БИ №7).

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

Наиболее близкой к предлагаемому устройству по технической сущности является устройство для формирования субоптимального размещения и его оценки, содержащая блок формирования перестановок, блок постоянной памяти, коммутатор, арифметико-логическое устройство (АЛУ), блок запоминания лучшего варианта, введены дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, группа элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, третий элементы задержки, два регистра сдвига, элемент ИЛИ и группу элементов ИЛИ, электронную модель графа (ЭМГ) содержащую m электронных моделей дуги, причем l-я электронная модель дуги (l = 1, 2, …, m) содержит триггер блокировки дуги, регистр веса дуги, регистр блокировки дуги, первый элемент И, второй элемент И, элемент ИЛИ (Патент РФ №2193796, кл. G06F 17/10, 7/38, опубл. 27.11.2002, БИ №33).

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

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

Устройство для поиска степени оптимальности размещения в кластерных многопроцессорных системах содержит первый регистр сдвига, второй регистр сдвига, блок формирования перестановок, блок постоянной памяти, блок запоминания лучшего варианта, коммутатор, арифметико-логическое устройство, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, первый элемент сравнения, триггер начала счета, триггер режима, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу элементов с первого по n-й ИЛИ, группу элементов с первого по m-й И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый элемент задержки, первый блок элементов ИЛИ, причем выходы блока формирования перестановок соединены с соответствующими входами блока постоянной памяти и соответствующими входами блока запоминания лучшего варианта, сигнализирующий выход блока формирования перестановок соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом арифметико-логического устройства, выход которого соединен с информационным входом блока запоминания лучшего варианта, а выход блока запоминания лучшего варианта соединен с первым информационным входом арифметико-логического устройства, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы регистров с первого по n-й подключены к первым и вторым входам элементов ИЛИ соответственно, выход переполнения регистра сдвига соединен с управляющим входом арифметико-логического устройства и с управляющим входом блока формирования перестановок, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом блока формирования перестановок и с первыми входами элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом элемента И, третий вход элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом элемента И, выход элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l = 1, 2, …, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ, выход элемента И соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом арифметико-логического устройства, выходы элементов с первого по n-й ИЛИ подключены к соответствующим входам элементов с первого по m-й И, а также дополнительно введенный блок дополнительно введенный блок с первого по n-й поиска степени оптимальности, содержащий матрицу из i.j (i=1, 2, …,m; j=1, 2,…, n) сумматоров, второй счетчик строк, первый счетчик столбцов, второй счетчик столбцов, матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) регистров, первый и второй дешифраторы горизонтально зафиксированных дуг, первый и второй дешифраторы вертикально зафиксированных дуг, матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ, первую матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, вторую матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, первый счетчик строк, первый многовходовой блок сумматоров, счетчик номера кластера, дешифратор номера кластера, второй многовходовой блок сумматоров многопроцессорной системы, элемент И номера кластера многопроцессорной системы, первый элемент ИЛИ номера кластера многопроцессорной системы, второй элемент ИЛИ номера кластера, причем тактовый вход устройства подключен к R-входу триггера И номера кластера многопроцессорной системы, S-вход которого подключен к выходу счетчика номера кластера и к счетному входу счетчика номера кластера, выход переполнения которого соединен с выходом переполнения устройства и с ое-входом второго многовходового блока сумматоров многопроцессорной системы, входы которого подсоединены к соответствующим первым входам элемента И объединения номера кластера многопроцессорной системы, второй вход которого подсоединен к тактовому входу устройства, выход элемента И объединения номера кластера многопроцессорной системы подключен к ое-входу первого счетчик строк, счетный вход которого соединен с тактовым входом устройства, выход первого счетчик строк подключен ко входу второго дешифратора горизонтально зафиксированных дуг, выходы с первого по m-которого подключены к соответствующим первым входам второй матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, вторые входы которых соединены с соответствующими выходами первого дешифратора горизонтально зафиксированных дуг, вход которого подсоединен к выходу второго счетчика строк, счетный вход которого соединен с выходом переполнения первого счетчика трок, тактовый вход устройства подключен к счетному входу второго счетчика столбцов, выход которого соединен со входом второго дешифратора вертикально зафиксированных дуг, выходы с первого по m-й которого соединены со вторыми соответствующими входами первой матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, первые входы которых подключены к соответствующим выходам первого дешифратора вертикально зафиксированных дуг, вход которого подсоединен к выходу первого счетчика столбцов, счетный вход которого подключен к выходу переполнения второго счетчика столбцов, ое-вход которого подключен к ое-входу первого счетчика столбцов и к выходу переполнения второго счетчика строк, выходы матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ подключены к соответствующим о-е входам матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) регистров, D-входы которых подсоединены к блоку 10 оперативной памяти, выходы матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) регистров подключены к соответствующим входам матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) сумматоров, выходы которых подключен к соответствующим входам первого многовходового блока сумматоров, выход которого подключен к выходу устройства, выход первой матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И соединен с соответствующими первыми входами матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ, вторые входы которых подключены к соответствующим выходам второй матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) матрицы элементов И.

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

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

На фигурах 4 и 5 кружками обозначены процессорные модули с соответствующими их номерами внутри. Линями обозначены каналы обмена данными между процессорными модулями, в цифры рядом с ними означают их объем (биты, байты, килобайты и т.д.).

Из фиг. 4 видно, что вариант размещения не является оптимальным, так как в данном случае передаваемые данные сосредоточены в пределах левого кластера многопроцессорной системы (МС). Вариант размещения, представленный на фиг. 5 является более оптимальным, так как все передаваемые данные не создают перегрузки трафика передачи из-за равномерности передачи данных. На фиг. 6, 7. 8 и 9 представлено устройство поиска степени оптимальности размещения в кластерных многопроцессорных системах.

Общие особенности изобретения состоят в следующем.

Исходная задача (процесс, алгоритм, программа) представляется в виде двунаправленного взвешенного графа G=<Х,E> (фиг. 1), вершины которого соответствуют подзадачам (подалгоритмам, подпрограммам и т.п.), а дуги задают управляющие и/или информационные связи между подзадачами и фактически являются каналами передачи данных. Граф G может быть описан матрицей смежности , где ; - объем передаваемых данных между i-м и j-м процессорным модулем (фиг. 2).

Многопроцессорная система отображается однородной средой, которой ставится в соответствие топологическая модель в виде графа H=<U,V>, где

- множество модулей МС, организованных в матрицу |U|=N=n, где n является количеством модулей МС и количеством вершин графа G, - множество межмодульных связей.

Размещение графа G в МС H будем задавать в виде отображения:

,

(1)

где , ,

Для удобства дальнейшего описания будем считать, что однородная среда содержит m×n элементов, при этом m=n (где m и n - число процессов). Функционирование однородной среды аналогично прототипу. При поступлении сигнала от внешнего устройства управления (ВУУ) происходит перестановка двух вершин графа и получение нового варианта размещения. Предлагаемое устройство вычисляет значения критериев оценки и выдает указанные значения ВУУ. Последнее анализирует принятые значения и либо фиксирует полученное размещение как более оптимальное, если значения критериев улучшают ранее найденные значения, либо игнорирует его.

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

Устройство для поиска степени оптимальности размещения в кластерных многопроцессорных системах содержит первый регистр 1 сдвига, второй регистр 2 сдвига, блок 3 формирования перестановок, блок 4 постоянной памяти, блок 5 запоминания лучшего варианта, коммутатор 6, арифметико-логическое устройство 7, дешифратор 8 выбора дуги, реверсивный счетчик 9 ячеек, блок 10 оперативной памяти, первый элемент 11 сравнения, триггер 12 начала счета, триггер 13 режима, счетчик 14 дуг, дешифратор 15 блокировки дуги, регистр 16 номера дуги, регистр 17 минимального веса, электронную модель 24 графа, группу элементов ИЛИ 18.1 - 18.n, группу элементов И 19.1 - 19.m, первый 20 и второй 21 элементы И, второй блок элементов ИЛИ 22, третий элемент И 23, первый 25 элемент задержки, первый блок элементов ИЛИ 26, причем выходы блока формирования перестановок 3 соединены с соответствующими входами блока 4 постоянной памяти и соответствующими входами блока запоминания лучшего варианта 5, сигнализирующий выход блока формирования перестановок 3 соединен с установочным входом триггера 12 начала счета, выходы блока 4 постоянной памяти соединены с соответствующими входами коммутатора 6, выход которого соединен с входом арифметико-логического устройства 7, выход которого соединен с информационным входом блока запоминания лучшей варианта 5, а выход блока запоминания лучшего варианта 5 соединен с первым информационным входом арифметико-логического устройства 7, выход переполнения регистра 1 сдвига соединен с входом регистра 2 сдвига, выходы регистров 1 и 2 с первого по n-й подключены к первым и вторым входам элементов ИЛИ 18.1 - 18.n соответственно, выход переполнения регистра 2 сдвига соединен с управляющим входом арифметико-логического устройства 7 и с управляющим входом блока формирования перестановок 3, тактовый вход 46 устройства соединен с входом регистра 1 сдвига, с тактовым входом блока формирования перестановок 3 и с первыми входами элементов И 20 и 21, выход счетчика 14 дуг соединен с входом дешифратора 8 выбора дуги и входом данных регистра 16 номера дуги, выход блока элементов ИЛИ 22 подключен к первому входу элемента 11 сравнения и к входу данных регистра 17 минимального веса, выход регистра 17 минимального веса соединен с вторым входом элемента 11 сравнения и с входом данных блока 10 оперативной памяти, выход элемента 25 задержки соединен с входом установки регистра 17 минимального веса и с входом установки регистра 16 номера дуги, выход третьего элемента И 23 соединен с синхровходом регистра 17 минимального веса и с синхровходом регистра 16 номера дуги, выход регистра 16 номера дуги соединен с информационным входом дешифратора 15 блокировки дуги, выход переполнения счетчика 14 дуг соединен с разрешающим входом дешифратора 15 блокировки дуги, а также с входом элемента 25 задержки, первым счетным входом реверсивного счетчика 9 ячеек и входом записи блока 10 оперативной памяти, выход элемента И 20 соединен со счетным входом счетчика 14 дуг и со входом элемента 47 задержки, выход которого соединен со вторым входом элемента И 23, первый вход которого соединен с выходом элемента 11 сравнения, второй вход элемента И 20 соединен с прямым выходом триггера 12 начала счета, который также соединен со вторым входом элемента И 21, третий вход элемента И 20 соединен с инверсным выходом триггера 13 режима, прямой выход которого соединен с третьим входом элемента И 21, выход элемента И 21 соединен со вторым счетным входом реверсивного счетчика 9 ячеек, выход которого подключен к адресному входу блока 10 оперативной памяти, выход переполнения реверсивного счетчика 9 ячеек подключен к установочному входу триггера 13 режима, вход сброса которого подключен к входу 48 установки устройства, вход сброса триггера 12 начала счета подключен к входу 49 установки устройства, l-й выход дешифратора 8 выбора дуги (l = 1, 2, …, m) соединен с l-м входом выбора дуги электронной модели 24 графа, l-й выход дешифратора 15 блокировки дуги соединен с l-м входом блокировки дуги электронной модели 24 графа, l-й выход веса дуги электронной модели 24 графа соединен с l-м входом блока элементов ИЛИ 26, выход элемента И 29.l соединен с l-м управляющим входом электронной модели 24 графа, выход блока элементов ИЛИ 26 соединен со вторым информационным входом арифметико-логического устройства 7, выходы элементов ИЛИ 18.1 - 18.n подключены к соответствующим входам элементов И 19.1 - 19.m, а также дополнительно введенный блок 58.1, 58.2, ..., 58.n поиска степени оптимальности, содержащий матрицу 59.i.j (i=1, 2, …, m; j=1, 2,…, n) сумматоров, второй 60 счетчик строк, первый 61 счетчик столбцов, второй 62 счетчик столбцов, матрицу 63.i.j (i=1, 2, …, m; j=1, 2,…, n) регистров, первый 64 и второй 65 дешифраторы горизонтально зафиксированных дуг, первый 66 и второй 67 дешифраторы вертикально зафиксированных дуг, матрицу 68.i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ, первую 69.i.j (i=1, 2, …, m; j=1, 2,…, n) матрицу элементов И, вторую 70.i.j (i=1, 2, …, m; j=1, 2,…, n) матрицу элементов И, первый 71 счетчик строк, первый многовходовой 73 блок сумматоров, счетчик 74 номера кластера, дешифратор 75 номера кластера, второй многовходовой 76 блок сумматоров многопроцессорной системы, элемент 77 И номера кластера многопроцессорной системы, первый 78 элемент ИЛИ номера кластера многопроцессорной системы, второй 79 элемент ИЛИ номера кластера, причем тактовый 46 вход устройства подключен к R-входу триггера 77 И номера кластера многопроцессорной системы, S-вход которого подключен к выходу счетчика 74 номера кластера и к счетному входу счетчика 74 номера кластера, выход переполнения которого соединен с выходом 72 переполнения устройства и с ое-входом второго многовходового 76 блока сумматоров многопроцессорной системы, входы которого подсоединены к соответствующим первым входом элемента 77 И объединения номера кластера многопроцессорной системы, второй вход которого подсоединен к тактовому 46 входу устройства, выход элемента 77 И объединения номера кластера многопроцессорной системы подключен к ое-входу первого 71 счетчик строк, счетный вход которого соединен с тактовым 46 входом устройства, выход первого 71 счетчик строк подключен ко входу второго 65 дешифратора горизонтально зафиксированных дуг, выходы с первого по m-которого подключены к соответствующим первым входам второй 70.i.j (i=1, 2, …, m; j=1, 2,…, n) матрицы элементов И, вторые входы которых соединены с соответствующими выходами первого 64 дешифратора горизонтально зафиксированных дуг, вход которого подсоединен к выходу второго 60 счетчика строк, счетный вход которого соединен с выходом переполнения первого 71 счетчика трок, тактовый 46 вход устройства подключен к счетному входу второго 62 счетчика столбцов, выход которого соединен со входом второго 67 дешифратора вертикально зафиксированных дуг, выходы с первого по m-й которого соединены со вторыми соответствующими входами первой 69.i.j (i=1, 2, …, m; j=1, 2,…, n) матрицы элементов И, первые входы которых подключены к соответствующим выходам первого 66 дешифратора вертикально зафиксированных дуг, вход которого подсоединен к выходу первого 61 счетчика столбцов, счетный вход которого подключен к выходу переполнения второго 62 счетчика столбцов, ое-вход которого подключен к ое-входу первого 61 счетчика столбцов и к выходу переполнения второго 60 счетчика строк, выходы матрицы 68.i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ подключены к соответствующим о-е входам матрицы 63.i.j (i=1, 2, …, m; j=1, 2,…, n) регистров, D-входы которых подсоединены к блоку 10 оперативной памяти, выходы матрицы 63.i.j (i=1, 2, …, m; j=1, 2,…, n) регистров подключены к соответствующим входам матрицы 59.i.j (i=1, 2, …, m; j=1, 2,…, n) сумматоров, выходы которых подключен к соответствующим входам первого многовходового 73 блока сумматоров, выход которого подключен к выходу устройства, выход первой 69.i.j (i=1, 2, …, m; j=1, 2,…, n) матрицы элементов И соединен с соответствующими первыми входами матрицы 68.i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ, вторые входы которых подключены к соответствующим выходам второй 70.i.j (i=1, 2, …, m; j=1, 2,…, n) матрицы элементов И.

Устройство по п.1, отличающееся тем, что электронная модель 24 графа (фиг. 7) содержит m электронных моделей дуги, причем электронная модель 27.l дуги (l = 1, 2, …, m) содержит триггер 28.l блокировки дуги, регистр 29.l веса дуги, регистр 30.l блокировки дуги, первый элемент И 31.l, второй элемент И 32.l, элемент ИЛИ 33.l, причем входы элемента И 31.l соединены с соответствующими входами 45.y и 45.z задания графа устройства (где y и z - номера соответственно начальной и конечной вершины l-й дуги графа), выход элемента И 31.l соединен с синхровходом регистра 29.l веса дуги и с установочным входом триггера 28.l блокировки дуги, вход сброса которого соединен с l-м входом блокировки дуги модели 24, вход данных регистра 29.l веса дуги соединен с входом 50.l веса дуги устройства, первый вход элемента ИЛИ 33.l соединен с l-м управляющим входом модели 24, а второй вход элемента ИЛИ 33.l соединен с выходом элемента И 32.l, первый вход которого соединен с прямым выходом триггера 28.l блокировки дуги и с разрешающим входом регистра 30.l блокировки дуги, второй вход элемента И 32.l соединен с l-м входом выбора дуги модели 24, вход сброса регистра 30.l блокировки дуги соединен с входом 51.l сброса устройства, выход регистра 30.l блокировки дуги соединен с l-м выходом веса дуги модели 24, который также соединен с выходом регистра 29.l веса дуги, выход элемента ИЛИ 33.l подключен к разрешающему входу регистра 29.l веса дуги.

Назначение элементов и блоков устройства (фиг.6) состоит в следующем.

Первый и второй регистры 1 и 2 сдвига необходимы для реализации последовательного перебора пар вершин орграфа G.

Блок 3 формирования перестановок осуществляет перебор всех возможных размещений вершин графа G по позициям заданной топологической модели.

Блок 4 постоянной памяти хранит двоичные коды номеров позиций.

Блок 5 запоминания лучшего варианта служит для запоминания лучшего на настоящий момент варианта размещения.

Коммутатор 6 обеспечивает последовательное списывание из блока 4 кодов номеров выбираемых позиций для передачи их в арифметико-логическое устройство 7.

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

Дешифратор 8 выбора дуги вместе со счетчиком 14 дуг предназначены для выбора из ЭМГ 24 дуги с номером, записанным в счетчике 14.

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

Блок 10 оперативной памяти служит для хранения весов w_i,j дуг орграфа G в порядке возрастания их значений.

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

Триггер 12 начала счета служит для индикации перехода из режима формирования размещения в режим его оценки.

Триггер 13 режима служит для хранения признака текущей операции. Если триггер 13 установлен в ноль - это означает запись весов дуг по возрастанию в блок 10 оперативной памяти, а в единицу - нахождение минимально возможной длины L^* по формуле (1).

Счетчик 14 дуге предназначен для подсчета количества обработанных дуг графа G.

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

Регистр 16 номера дуги служит для хранения номера дуги с минимальным весом, выбранной в текущем цикле работы устройства.

Регистр 17 минимального веса необходим для хранения значения минимального на данный момент веса дуги.

Группа элементов ИЛИ 18.1 - 18.n необходима для объединения соответствующих сигналов с регистров 1 и 2.

Группа элементов И 19.1 - 19.m предназначена для выбора соответствующих дуг графа G по сигналам с элементов ИЛИ 18.1 - 18.n.

Первый и второй элементы И 20 и 21 необходимы для блокировки передачи импульсов с тактового входа устройства на элементы и блоки, обеспечивающие упорядочение весов дуг графа в блоке 10.

Второй блок элементов ИЛИ 22 необходим для подключения веса текущей дуги к элементу 11 сравнения и регистру 17.

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

Электронная модель 24 графа служит для моделирования топологии графа G, представляющего размещаемый объект (фиг. 2).

Первый элемент 25 задержки служит для задержки импульса переполнения со счетчика 14 дуг на время, достаточное для обеспечения блокировки дуги дешифратором 15 и записи минимального веса из регистра 17 в блок 10 оперативной памяти.

Первый блок элементов ИЛИ 26 необходим для подачи в арифметико-логическое устройство 7 веса текущей дуги.

Электронная модель 27.l дуги (фиг. 2) служит для моделирования l-й дуги орграфа G, l = 1,2, …, m.

Триггер 28.l блокировки дуги служит для выдачи сигнала блокировки повторного выбора соответствующей дуги во время работы устройства.

Регистр 29.l веса дуги и регистр 30.l блокировки дуги предназначены для хранения веса текущей дуги и нулевого кода соответственно. Регистры 29.l и 30.l имеют выходы с тремя состояниями; перевод выходов в третье (высокоимпедансное) состояние обеспечивается соответственно единичным и нулевым сигналом на входах разрешения (oe).

Первый элемент И 31.l необходим для формирования сигнала наличия l-й дуги в графе.

Второй элемент И 32.l служит для формирования сигнала выбора/блокировки дуги.

Элемент ИЛИ 33.l служит для объединения сигналов.

Назначение элементов блока 58 поиска степени оптимальности (фиг. 8, 9) состоит в следующем.

Матрица 59.i.j (i=1, 2, …, m; j=1, 2,…, n) сумматоров предназначена для суммирования и последующей записи в соответствующую матрицу 63.i.j (i=1, 2, …, m; j=1, 2,…, n) регистров кодов значений интенсивности дуг, назначенных на соответствующие пары процессоров.

Второй 60 счетчик строк служат для хранения номера соответствующей строки и столбца, необходимой для выбора пары процессоров, предназначенных для фиксации очередной дуги графа G в строках МС.

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

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

Матрица 63.i.j (i=1, 2, …, m; j=1, 2,…, n) регистров предназначена для хранения суммарных кодов значений интенсивности дуг, назначенных на данную пару процессоров в строках и столбцах МС.

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

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

Матрица 68.i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ служит для объединения сигналов с выходов соответствующих элементов первой 69.i.j (i=1, 2, …, m; j=1, 2,…, n) и второй 70.i.j (i=1, 2, …, m; j=1, 2,…, n) матриц элементов И с последующей подачей на разрешающие входы матрицы 63.i.j (i=1, 2, …, m; j=1, 2,…, n) регистров.

Первая 69.i.j (i=1, 2, …, m; j=1, 2,…, n) матрица элементов И предназначена для объединения сигналов с последующей подачей на соответствующие входы 68.i.j (i=1, 2, …,m; j=1, 2,…, n) элементов ИЛИ и дальнейшим его поступлением на соответствующие разрешающие входы oe матрицы 63.i.j (i=1, 2, …, m; j=1, 2,…, n) регистров.

Вторая 70.i.j (i=1, 2, …, m; j=1, 2,…, n) матрица элементов И предназначена для объединения сигналов с последующей подачей на соответствующие входы 68.i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ и дальнейшим его поступлением на соответствующие разрешающие входы oe матрицы 63.i.j (i=1, 2, …, m; j=1, 2,…, n) регистров.

Первый 71 счетчик строк служат для хранения номера соответствующей строки и столбца, необходимой для выбора пары процессоров, предназначенных для фиксации очередной дуги графа G в строках МС.

Выход 72 переполнения устройства служит для подачи на ВУУ сигнала о переполнении счетчика 61, что одновременно является сигналом завершения работы устройства.

Первый многовходовой 73 блок сумматоров необходим для подсчета суммарной величины интенсивности размещения кластера () многопроцессорной системы.

Счетчик 74 номера кластера предназначен для подсчета номера текущего обрабатываемого кластера многопроцессорной системы.

Дешифратор 75 номера кластера необходим для выбора текущего обрабатываемого кластера многопроцессорной системы.

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

Элемент 77 И объединения номера кластера многопроцессорной системы необходим для выбора одного из n кластеров многопроцессорной системы.

Первый 78 элемент ИЛИ номера кластера многопроцессорной системы предназначен для управления режимом работы кластерной многопроцессорной системы.

Второй 79 элемент ИЛИ номера кластера служит для выбора номера кластерной многопроцессорной системе, подлежащей анализу.

Рассмотрим работу предлагаемого устройства.

Первоначально в счетчике 36, регистрах 38.i.j, 39.i.j, сумматорах 41.1, 41.2,…,41.8 содержится код нуля («0…0»). SR-триггеры 40.1, 40.2,…,40.8 находятся в единичном состоянии, поэтому на их прямых выходах присутствует единичный потенциал, который подается на е-входы регистров 38.i.j (, ), а на их обратных выходах присутствует нулевой потенциал, поступающий на е-входы регистров 39.i.j (, ), запрещая этим их работу. В матрице 59.i.j (i=1, 2, …, m; j=1, 2,…, n) сумматоров и матрице 63.i.j (i=1, 2, …, m; j=1, 2,…, n) регистров хранится код нуля. В счетчике 74 код нуля. Триггер 77 находится в состоянии логической единицы, поэтому на его обратном выходе присутствует код нуля, в результате чего на выходе элемента 78 присутствует нулевой потенциал, запрещающий работу счетчика 78.

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

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

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

Единичный импульс с тактового 46 входа устройства поступает на R-вход триггера 77 и переводит его в единичное состояние, в результате чего на его обратном выходе появляется единичный импульс, который далее проходит через элемент 79 ИЛИ и подается на второй вход элемента 78 И.

В это время на первом входе элемента 78 И присутствует единичный импульс с тактового 46 входа устройства. В результате на его выходе появляется единый потенциал, переводящий триггер 77 в единичное стояние и на его обратном выходе появляется нулевой потенциал. Но, так как до этого на счетный вход элемента 78 И уже поступил единый импульс, то содержимое счетчика 74 по переднему фронту увеличивается на единицу до кода значения единицы ("0....01").

Код единицы подается на вход дешифратора 75 и на его первом выходе появляется единичный импульс, поступающий на второй вход элемента 77 И, и, на его выходе появляется единичный импульс, поступающий на ое-вход счетчика 71, разрешающий тем самым его работу. В это время на его счетном входе присутствует единый импульс, увеличивающий его содержимое на единицу до кода единицы ("0...01"). Это значение поступает на вход дешифратора 65 и на его первом выходе появляется единый потенциал, который подается на первые входы элементов 70.1.1, ...., 70.1.n И. В то же время, на их вторых соответствующих входах присутствует единичное значение с первого выхода дешифратора 64. В результате присутствия двух единичных сигналов на входах элемента 70.1.1 И, на его выходе появляется единица, которая подается на второй вход элемента 68.1.1 ИЛИ и далее на ое-вход регистра 63.1.1. Из-за этого код значения интенсивности с выхода блока 10 оперативной памяти поступает на D-регистра 63.1.1 для своей записи. Таким образом, в регистре 63.1.1 записывается код значения интенсивности дуги графа G. Например, это может быть процессор 1 или 3 на фигуре 4.

Следующий тактовый импульс поступает на R-вход триггера 77, устанавливая его в нулевое стояние. В это время тот же самый тактовый импульс подается на первый вход элемента 77 И так как на его втором входе присутствует единица, то на ое-входе счетчика 71 появляется единица, разрешая его работу. Единичный импульс поступает на счетный вход счетчика 71 и по переднему фронту увеличивает го содержимое на единицы до кода двойки ("0...10"). Этот импульс возбуждает единичный импульс на втором выходе дешифратора 65, в результате чего на первых входах элементов 70.2.1...70.2.m И появляется единица. К этому времени, на их соответствующих вторых входах присутствуют единичные потенциалы со второго выхода дешифратора присутствует единица с первого выхода дешифратора 64. В результате, на выходе элемента 70.2.1 И появляется единичный потенциал, который подается на второй вход элемента 70.2.1 ИЛИ, в результате чего на ое-входе регистра 62.2.1 появляется единица, разрешающая его работу. Таким образов, следующий код значения интенсивности записывается в регистр 63.2.1 и вес дуги графа G заносится в многопроцессорную систему. Например, это могут быть вершины 1-4 на фигуре 4а, 5б.

Следующий тактовый импульс снова поступает на второй вход элемента 77 И и на его выходе появляется единый импульс, который поступает на ое-вход счетчика 71, увеличивая его содержимое на единицу до кода тройки ("0.011"). Таким образом, на третьем выходе дешифратора 65 появляется единичный импульс, который возбуждает единичный импульс на втором входе элемента 70.3.1 И. Далее единый сигнал появляется на ое-входе регистра 63.3.1. Таким образом, очередной код записывается в регистр 63.3.1.

Так, продолжается до тех пор, пока на выходе переполнения счетчика 71 не появляется сигнал переполнения, который поступает на счетный вход счетчика 60, увеличивая его содержимое до кода двойки ("0....010"). Этот код подается на вход дешифратора 64 и на его втором выходе возбуждается единичный импульс, поступающий на вторые входы элементов 70.1.2...70.2.m И. При этом содержимое счетчика 71 сбрасывается в ноль.

Следующий тактовый импульс поступает на второй вход элемента 77 И и на его выходе появляется единый импульс, который поступает на ое-вход счетчика 71, разрешая его работу. Тот же самый тактовый импульс поступил н счетный вход счетчика 71 и по переднему фронту увеличивает его содержимое на единицу до кода значения единицы ("0...01"). Этот код подается на вход дешифратора 65 и на его первом выходе появляется единичный импульс, поступающий на первые входы элементов 70.1.1,..., 70.1.n И. Таким образом, на выходе элемента 70.1.1 И появляется единый сигнал, поступающий на второй вход элемента 68.1.1 ИЛИ и далее на ое-вход регистра 63.1.1, разрешая его работу. Следовательно, код значения интенсивности с выхода блока 10 оперативной памяти записывается в регистр 63.1.1. Далее этот код поступает на сумматор 59.1.1, который накапливает поступающие на него коды.

Следующий тактовый импульс аналогично подается на счетный вход счетчика 71 и по переднему фронту увеличивает его содержимое до кода двойки. Аналогично на втором выходе дешифратора 65 появляется единичный импульс, поступающий на первые входы элементов 70.2.1, 70.2.2, ...., 70.2.n И. Тогда на выходе элемента 70.2.1 И появляется единица, которая проходит через элемент 68.2.1 ИЛИ и подается на ое-вход регистра 63.2.1, разрешая его работу. Тогда код с выхода блока 10 оперативной памяти записывается в регистр 63.2.2, после чего этот код записывается в сумматор 59.2.2 для накопления общей суммы.

Так продолжается до тех пор, пока на выходе переполнения счетчика 60 не появится единый импульс, поступающий на ое-входы счетчиков 61 и 62, разрешая их работу.

Очередной тактовый импульс поступает на счетный вход счетчика 62 и по переднему фронту увеличивает его содержимое да кода единицы ("0...01"). Этот код подается на вход дешифратора 67 и на первом его выходе появляется единичный сигнал, поступающий на первые входы элементов 69.1.1, 69.1.2,... 69.1.n И.

К этому времени на первом на втором входе элемента 69.1.2 И присутствует единый потенциал, а значит на его выходе появляется единица, вызывающая появление единичного импульса на его выходе. В результате импульс проходит через элемент 68.1.2 ИЛИ и далее подается на ое-вход регистра 63.1.2, разрешая его работу. В результате код с выхода блока 10 оперативной памяти записывается в регистр 63.1.2 и далее суммируется с содержимым сумматора 59.1.2. Таким образом, например, анализируется размещение между модулями 1-2 на фигурах 4 и 5.

Следующий тактовый импульс поступает на счетный вход счетчика 62 и по переднему фронту увеличивает его стояние на единицу до кода двойки. Этот код поступает на вход дешифратора 67 и на его втором выходе появляется единичный импульс, который подается на вторые входы элементов 69.2.1, 69.2.2,... 69.2.n И.

К этому времени на втором входе элемента 70.2.2 И уже присутствует единый импульс, который вызывает появления единицы на выходе элемента 68.2.2 ИЛИ, от чего на его выходе появляется единица, поступающая на ое-вход регистра 63.2.2. В результате код с выхода блока 10 оперативной памяти записывается в регистр 63.2.2. Таким образом, например, анализируется 4 и 5 на фигурах 4 и 5.

Так продолжается до тех пор, пока на выходе переполнения счетчика 62 не появится единичный импульс, поступающий на счетный вход счетчика 61, который по переднему фронту увеличивает его содержимое до кода двойки ("0...010").

Следующий тактовый импульс подается на четный вход 62, устанавливая в нем код единицы, который возбуждает единичный потенциал на первом выходе дешифратора 67, поступающий на вторые входы элементов 69.1.1, 69.1.2,...., 69.1.n И.

К этому времени на втором выходе дешифратора 70.1.1 присутствует единичный импульс, поступающий на первые входы элементов 69.2.1, 69.2.2,..., 69.2.n. К этому времени на их вторых входах присутствуют единичные сигналы. В результате, на выходе элемента 69.2.2 И появляется единичный импульс, поступающий через элемент 68.2.2 ИЛИ и далее на ое-вход регистра 63.2.2 для записи кода значения интенсивности.

Так продолжается до тех пор, пока на выходе переполнения счетчика 61 не появится единичный импульс, поступающий на ое-вход сумматора 73, суммирующий все поступившие на его входы значения и выдающие результат на соответствующий выход сумматора 76. В то же время тот же самый единый импульс подается на второй вход элемента 79 ИЛИ и далее на второй вход элемента 78 И, на первом входе которого присутствует единичный импульс с тактового 46 входа устройства. В результате код в счетчике 74 переднему фронту увеличивается на единицу. Соответственно код, поданный на соответствующий вход дешифратора 75 появляется на одном из его выходов.

Так продолжается до тех пор, пока на выход переполнения счетчика 74 не появится единичный импульс. Этот сигнал подается на ое-вход сумматора 76 и разрешает поступлении суммарных кодов, поступивших его выходы на выход ВУУ устройства. Одновременно тот же единичный импульс с выхода переполнения счетчика 74 поступает на выход ВУУ устройства.

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

1. Устройство для поиска степени оптимальности размещения в кластерных многопроцессорных системах, содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок, блок постоянной памяти, блок запоминания лучшего варианта, коммутатор, арифметико-логическое устройство, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, первый элемент сравнения, триггер начала счета, триггер режима, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу элементов с первого по n-й ИЛИ, группу элементов с первого по m-й И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый элемент задержки, первый блок элементов ИЛИ, причем выходы блока формирования перестановок соединены с соответствующими входами блока постоянной памяти и соответствующими входами БЗЛВ, сигнализирующий выход блока формирования перестановок соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом арифметико-логического устройства, выход которого соединен с информационным входом блока запоминания лучшего варианта, а выход блока запоминания лучшего варианта соединен с первым информационным входом арифметико-логического устройства, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы регистров и с первого по n-й подключены к первым и вторым входам элементов ИЛИ соответственно, выход переполнения регистра сдвига соединен с управляющим входом арифметико-логического устройства и с управляющим входом блока формирования перестановок, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом блока формирования перестановок и с первыми входами элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен со вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом элемента И, третий вход элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом элемента И, выход элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l=1, 2, …, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ, выход элемента И соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом арифметико-логического устройства, выходы элементов с первого по n-й ИЛИ подключены к соответствующим входам элементов с первого по m-й И, отличающееся тем, что в него дополнительно введен блок с первого по n-й поиска степени оптимальности, содержащий матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) сумматоров, второй счетчик строк, первый счетчик столбцов, второй счетчик столбцов, матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) регистров, первый и второй дешифраторы горизонтально зафиксированных дуг, первый и второй дешифраторы вертикально зафиксированных дуг, матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ, первую матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, вторую матрицу из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, первый счетчик строк, первый многовходовой блок сумматоров, счетчик номера кластера, дешифратор номера кластера, второй многовходовой блок сумматоров многопроцессорной системы, элемент И номера кластера многопроцессорной системы, первый элемент ИЛИ номера кластера многопроцессорной системы, второй элемент ИЛИ номера кластера, причем тактовый вход устройства подключен к R-входу триггера И номера кластера многопроцессорной системы, S-вход которого подключен к выходу счетчика номера кластера и к счетному входу счетчика номера кластера, выход переполнения которого соединен с выходом переполнения устройства и с ое-входом второго многовходового блока сумматоров многопроцессорной системы, входы которого подсоединены к соответствующим первым входам элемента И объединения номера кластера многопроцессорной системы, второй вход которого подсоединен к тактовому 46 входу устройства, выход элемента И объединения номера кластера многопроцессорной системы подключен к ое-входу первого счетчика строк, счетный вход которого соединен с тактовым входом устройства, выход первого счетчика строк подключен ко входу второго дешифратора горизонтально зафиксированных дуг, выходы с первого по m-й которого подключены к соответствующим первым входам второй матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, вторые входы которых соединены с соответствующими выходами первого дешифратора горизонтально зафиксированных дуг, вход которого подсоединен к выходу второго счетчика строк, счетный вход которого соединен с выходом переполнения первого счетчика строк, тактовый вход устройства подключен к счетному входу второго счетчика столбцов, выход которого соединен со входом второго дешифратора вертикально зафиксированных дуг, выходы с первого по m-й которого соединены со вторыми соответствующими входами первой матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И, первые входы которых подключены к соответствующим выходам первого дешифратора вертикально зафиксированных дуг, вход которого подсоединен к выходу первого счетчика столбцов, счетный вход которого подключен к выходу переполнения второго счетчика столбцов, ое-вход которого подключен к ое-входу первого счетчика столбцов и к выходу переполнения второго счетчика строк, выходы матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ подключены к соответствующим о-е входам матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) регистров, D-входы которых подсоединены к блоку 10 оперативной памяти, выходы матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) регистров подключены к соответствующим входам матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) сумматоров, выходы которых подключены к соответствующим входам первого многовходового блока сумматоров, выход которого подключен к выходу устройства, выход первой матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов И соединен с соответствующими первыми входами матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) элементов ИЛИ, вторые входы которых подключены к соответствующим выходам второй матрицы из i.j (i=1, 2, …, m; j=1, 2,…, n) матрицы элементов И.

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