Устройство поиска степени оптимальности размещения в кластерных многопроцессорных системах при направленной передаче информации Российский патент 2023 года по МПК G06F7/24 G06F17/10 

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

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

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

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

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

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

Устройство поиска степени оптимальности размещения в кластерных многопроцессорных системах при направленной передаче информации содержит первый регистр сдвига, второй регистр сдвига, блок формирования перестановок, блок постоянной памяти, блок запоминания лучшего варианта, коммутатор, арифметико-логическое устройство, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, первый элемент сравнения, триггер начала счета, триггер режима, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу элементов с первого по n-й ИЛИ, группу элементов с первого по m-й И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый элемент задержки, первый блок элементов ИЛИ, причем выходы блока формирования перестановок соединены с соответствующими входами блока постоянной памяти и соответствующими входами блока запоминания лучшего варианта, сигнализирующий выход блока формирования перестановок соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом арифметико-логического устройства, выход которого соединен с информационным входом блока запоминания лучшего варианта, а выход блока запоминания лучшего варианта соединен с первым информационным входом арифметико-логического устройства, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы регистров с первого по n-й подключены к первым и вторым входам элементов ИЛИ соответственно, выход переполнения регистра сдвига соединен с управляющим входом арифметико-логического устройства и с управляющим входом блока формирования перестановок, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом блока формирования перестановок и с первыми входами элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом элемента И, третий вход элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом элемента И, выход элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l = 1, 2, …, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ, выход элемента И соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом арифметико-логического устройства, выходы элементов с первого по 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) элементов ИЛИ, первую матрицу из i.j (i=1, 2, …,m; j=1, 2,…, n) элементов И, вторую матрицу из i.j (i=1, 2, …,m; j=1, 2,…, n) элементов И, пятый строк, первый многовходовой блок сумматоров, шестой счетчик номера кластера, седьмой дешифратор номера кластера, второй многовходовой блок сумматоров, четвёртый SR-триггер объединения номера кластера, шестой элемент И номера кластера, второй элемент ИЛИ номера кластера, седьмой элемент И, причем тактовый вход устройства подключен к R-входу триггера объединения номера кластера, второму входу второго элемента ИЛИ номера кластера, первому входу элемента И номера кластера, счетным входам четвертого счетчика столбцов, пятого счетчика строк и второму входу седьмого элемента И, обратный выход четвертого SR-триггера объединения номера кластера соединен с первым входом второго элемента ИЛИ номера кластера, выход которого подключен ко второму входу шестого элемента И номера кластера, выход которого подключен к счетному входу шестого счетчика номера кластера, выход которого подключен ко входу седьмого дешифратора номера кластера, выходы с первого по n-й которого соединены с счетному входу пятого счетчика строк, выход которого соединен с входом четвертого дешифратора горизонтально зафиксированных дуг, выходы с первого по n-й которого соединены с соответствующими первыми входами второй матрицы из i.j (i=1, 2, …,m; j=1, 2,…, n) элементов И, вторые входы которых подключены к соответствующим выходам с первого по n-й третьего дешифратора горизонтально зафиксированных дуг, вход которого подключен к выходу второго счетчика строк, сетный вход которого подключен к выходу переполнения пятого счетчика строк, выход переполнения второго счетчика строк соединен с ое-входами третьего и четвертого счетчика столбцов, счетный вход третьего счетчика столбцов подключен к выходу переполнения четвертого счетчика столбцов, выход которого подсоединен ко входу шестого дешифратора вертикально зафиксированных дуг, выходы с первого по n-й которого соединены со вторыми входами соответствующих элементов матрицы из i.j (i=1, 2, …,m; j=1, 2,…, n) элементов И, первые входы которых подключены к соответствующим выходам с перового по n-й пятого дешифратора вертикально зафиксированных дуг, вход которого подключен к выходу третьего счетчика столбцов, выход переполнения которого соединен с е2-входами матрицы из i.j.n (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) элементов ИЛИ соединены с соответствующими ое-входами матрицы из i.j (i=1, 2, …,m; j=1, 2,…, n) регистров, соответствующие выходы которых подключены к входам матрицы из i.j (i=1, 2, …,m; j=1, 2,…, n) сумматоров, выходы которых соединены с соответствующими входами первого многовходового блока сумматоров, выход которого подключен к выходу устройства, прямой выход второго триггера режима подключен к первому входу седьмого элемент И, D1- и D2-входы матрицы из i.j (i=1, 2, …,m; j=1, 2,…, n) регистров подключены к выходу блока оперативной памяти.

Электронная модель графа (фиг. 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.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 блок сумматоров, четвёртый SR-триггер 77 объединения номера кластера, шестой 78 элемент И номера кластера, второй 79 элемент ИЛИ номера кластера, седьмой 80 элемент И, причем тактовый 46 вход устройства подключен к R-входу триггера 77 объединения номера кластера, второму входу второго 79 элемента ИЛИ номера кластера, первому входу элемента 78 И номера кластера, счетным входам четвертого 62.n счетчика столбцов, пятого 71.n счетчика строк и второму входу седьмого 80.n элемента И, обратный выход четвертого SR-триггера 77 объединения номера кластера соединен с первым входом второго 79 элемента ИЛИ номера кластера, выход которого подключен ко второму входу шестого 78 элемента И номера кластера, выход которого подключен к счетному входу шестого счетчика 74 номера кластера, выход которого подключен ко входу седьмого дешифратора 75 номера кластера, выходы с первого по n-й которого соединены с счетному входу пятого 71.n счетчика строк, выход которого соединен с входом четвертого 65.n дешифратора горизонтально зафиксированных дуг, выходы с первого по n-й которого соединены с соответствующими первыми входами второй 70.i.j.n (i=1, 2, …,m; j=1, 2,…, n) матрица элементов И, вторые входы которых подключены к соответствующим выходам с первого по n-й третьего 64.n дешифратора горизонтально зафиксированных дуг, вход которого подключен к выходу второго 60.n счетчика строк, сетный вход которого подключен к выходу переполнения пятого 71.n счетчика строк, выход переполнения второго 60.n счетчика строк соединен с ое-входами третьего 61.n и четвертого 62.n счетчика столбцов, счетный вход третьего 61.n счетчика столбцов подключен к выходу переполнения четвертого 62.n счетчика столбцов, выход которого подсоединен ко входу шестого 67.n дешифратора вертикально зафиксированных дуг, выходы с первого по n-й которого соединены со вторыми входами соответствующих элементов матрицы 69.i.j.n (i=1, 2, …,m; j=1, 2,…, n) элементов И, первые входы которых подключены к соответствующим выходам с перового по n-й пятого 66.n дешифратора вертикально зафиксированных дуг, вход которого подключен к выходу третьего 61.n счетчика столбцов, выход переполнения которого соединен с е2-входами матрицы 63.i.j.n (i=1, 2, …,m; j=1, 2,…, n) регистров и с ое-входом первого многовходового 73.n блока сумматоров, выходы матрицы 69.i.j.n (i=1, 2, …,m; j=1, 2,…, n) элементов И подключены к соответствующим первым входам матрицы 68.i.j.n (i=1, 2, …,m; j=1, 2,…, n) элементов ИЛИ, вторые входы которых подключены к соответствующим выходам второй 70. i.j.n (i=1, 2, …,m; j=1, 2,…, n) матрицы элементов И, выходы матрицы 68.i.j.n (i=1, 2, …,m; j=1, 2,…, n) элементов ИЛИ соединены с соответствующими ое-входами матрицы 63.i.j.n (i=1, 2, …,m; j=1, 2,…, n) регистров, соответствующие выходы которых подключены к входам матрицы 59.i.j.n (i=1, 2, …,m; j=1, 2,…, n) сумматоров, выходы которых соединены с соответствующими входами первого многовходового 73.n блока сумматоров, выход которого подключен к выходу устройства, прямой выход второго триггера 13 режима подключен к первому входу седьмого 80.n элемент И, D1- и D2-входы матрицы 63.i.j.n (i=1, 2, …,m; j=1, 2,…, n) регистров подключены к выходу блока 10 оперативной памяти.

Устройство по п.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.1 дуги (фиг. 2) служит для моделирования l-й дуги орграфа G, l = 1,2, …, m.

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

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

Четвёртый элемент И 31.1 необходим для формирования сигнала наличия 1-й дуги в графе.

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

Первый элемент ИЛИ 33.1 служит для объединения сигналов.

Назначение элементов блоков 58.1, 58.2,...,58.n степени оптимальности необходимо для поиска степени оптимальности размещения в кластерных многопроцессорных системах при направленной передаче информации.

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

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

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

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

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

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

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

Матрица 68.i.j.n (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.n (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.n (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.n счетчик строк служит для хранения номера соответствующей строки и столбца, необходимой для выбора пары процессоров, предназначенных для фиксации очередной дуги графа G в строках МС.

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

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

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

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

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

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

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

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

Седьмой 80.n элемент И необходим для объединения сигналов с прямого выхода триггера 13 и тактового 46 выхода устройства.

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

Первоначально в матрице 59.i.j.n (i=1, 2, …,m; j=1, 2,…, n) сумматоров и матрице 63.i.j.n (i=1, 2, …,m; j=1, 2,…, n) регистров хранится код нуля ("0...0"). В счетчике 74 хранится код нуля. Триггер 77 находится в состоянии логической единицы, поэтому на его обратном выходе присутствует код нуля, в результате чего на выходе элемента 78 И присутствует нулевой потенциал, запрещающий работу счетчика 74. В матрице 63.i.j.n (i=1, 2, …,m; j=1, 2,…, n) регистров также хранятся коды нулей. В счетчике 60.n хранится код единицы ("0...01") и поэтому на первом выходе дешифратора 64.n присутствует единичный потенциал, поступающий на вторые входы второй 70.1.j.n (j=1, 2,…, n) матрицы элементов И. В счетчике 71.n содержится код нуля. В счетчике 61.n хранится код единицы и поэтому, так как на первом выходе дешифратора 66.n присутствует единичный потенциал, на первых входах первой 69.1.j.n (j=1, 2,…, n) матрицы элементов И присутствует единичный импульс. В счетчике 62.n содержится код нуля.

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

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

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

Единичный импульс с тактового 46 входа устройства поступает на R-вход SR-триггера 77 и поэтому на его обратном входе появляется нулевой потенциал, поступающий на первый вход элемента 79 ИЛИ. Одновременно с этим единичный импульс с тактового 46 входа устройства подается на вторые входы элемента 79 ИЛИ, первый вход элемента 78 И, счетным входам счетчиков 62.1 и 71.1 блока 58.1. Также на второй вход элемента 80.1 И этого же блока, на первом выходе которого присутствует единичный потенциал с прямого выхода SR-триггера 13. В результате этого на выходе элемента 80.1 И появляться единичный импульс, поступающий на ое-вход счетчика 71.1, разрешая его работу. В результате единичный импульс поступает на счетный вход счетчика 74 и по переднему фронту увеличивает его содержимое на единицу до кода значения единицы ("0...01"). В результате единица с выхода счетчика 74 подается на вход дешифратора 75 и его первом выходе появляется единичный импульс, который подается на счетный вход счетчика 71.1 блока 58.1, увеличивая его содержимое по переднему фронту на единицу до кода значения один. В результате единица поступает на вход дешифратора 65.1 и на его первом выходе появляется единичный импульс, поступающий на соответствующие первые входы элементов 70.1.j.1 (j=1, 2,…, n) И. Таким образом на выходе элемента 69.1.1.1 И появляется единичный импульс, который проходит через элемент 68.1.1.1 ИЛИ и поступает на ое-вход регистра 63.1.1.1, разрешая его работу. В этом случае значение интенсивности с выхода блока 10 поступает на вход D1 регистра 63.1.1.1 для последующего сохранения. Этот код далее подается на вход сумматора 59.1.1.1 для суммирования с хранящимся там кодом, который далее поступает на соответствующий вход блока сумматоров 73.1.

Следующий тактовый импульс аналогично поступает на счетный вход счетчика 74, увеличивая в нем код по переднему фронту на единицу до кода двойки ("0...010"), которая подается на вход дешифратора 75 и на его втором выходе появляется единичный импульс, поступающий на ое-вход счетчика 71.2 блока 58.2, разрешая его работу.

Далее аналогично описанному выше принципу обрабатывается блок 58.2 кластерной многопроцессорной системы. Аналогично также единичный импульс подается на вторые входы счетчиков 62.2 и 71.2 блока 58.2 и на второй вход элемента 80.2 И этого же блока. на первом выходе которого присутствует единичный потенциал с прямого выхода SR-триггера 13. В результате этого на выходе элемента 80.2 И появляться единичный импульс, поступающий на ое-вход счетчика 71.2, разрешая его работу. Таким образом единичный импульс поступает на счетный вход счетчика 74 и по переднему фронту увеличивает его содержимое на единицу до кода значения двойки ("0...010"). В результате двойка с выхода счетчика 74 подается на вход дешифратора 75 и его втором его выходе появляется единичный импульс, который подается на счетный вход счетчика 71.2 блока 58.2, увеличивая его содержимое по переднему фронту на единицу до кода значения один. В результате единица поступает на вход дешифратора 65.2 и на его первом выходе появляется единичный импульс, поступающий на соответствующие первые входы элементов 70.1.j.2 (j=1, 2,…, n) И. Таким образом на выходе элемента 69.1.1.2 И появляется единичный импульс, который проходит через элемент 68.1.1.2 ИЛИ и поступает на ое-вход регистра 63.1.1.2, разрешая его работу. В этом случае значение интенсивности с выхода блока 10 поступает на вход D1 регистра 63.1.1.2 для последующего сохранения. Этот код далее подается на вход сумматора 59.1.1.2 для суммирования с хранящимся там кодом, который далее поступает на соответствующий вход блока сумматоров 73.2.

Так продолжается до тех пор, пока на выходе переполнения счетчиков 71.n () не появится единичный импульс, означающий переполнение счетчика 71 и признак того, что все межсоединения в первой строе кластерной многопроцессорной системы зафиксированы. Например, на фигуре 4 это процессоры 1–2 и 2–3 и необходимо переход ко второй строке, то есть к процессорам 4-5 и 5-6.

Поэтому единичный импульс с выхода переполнения счетчика 71.n () поступает на счетные входы счетчиков 60.n () и по переднему фронту увеличивает их содержимое на единицу до кода двойки ("0...010").

Далее аналогично описанному выше принципу происходит, например заполнение значениями интенсивности дуг процессоров 4-5 и 5-6 и так для всех m строк кластерных блоков МС.

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

В следствие этого, единичный импульс с выхода переполнения счетчика 60.n поступает на ое-входы счетчиков 61.n и 62.n, разрешая их работу.

Очередной тактовый импульс с выхода генератора 46 тактовых импульсов поступает на счетный вход счетчика 62.n и по переднему фронту увеличивает его содержимое до кода единицы ("0...01"). Этот код подается на вход дешифратора 67.n и на его первом выходе появляется единичный импульс, который поступает на вторые входы элементов 69.1.n.n И. Поэтому на выходе элемента 69.1.1.n И появляется единичный импульс, который проходит через элемент 68.1.1.n ИЛИ и подается на ое-вход регистра 63.1.1.n, разрешая его работу. В следствие этого на вход D2 триггера 63.1.1.n подается значение интенсивности с выхода блока 10 оперативной памяти для сохранения. Этот код далее поступает на вход сумматора 59.1.1.n для суммирования с уже хранящимся там значением и далее соответствующий вход первого многовходового 73.n блока сумматоров для суммирования.

Следующий тактовый импульс поступает на счетный вход счетчика 62.n и по переднему фронту увеличивает его содержимое до кода двойки ("0...010"), которое подается на вход дешифратора 67.n и на втором его выходе появляется единичный импульс, который поступает на вторые входы элемента 69.2.1.n И. Из-за наличия двух единичных импульсов на его входах, на выходе элемента 69.2.1.n И появляется единичный потенциал, который проходит через элемент 68.2.1.n ИЛИ и подается на ое-вход регистра 63.2.1.n, разрешая его работу. В следствие на его D1-вход подается значение интенсивности с выхода блока 10 оперативной памяти для последующего сохранения. Далее этот код с выхода регистра 63.2.1.n поступает на вход сумматора 59.2.1.n для суммирования с хранящимся в нем кодом. Таким образом очередное значение интенсивности фиксируется в МС. Например, на фигурах 4 и 5 это могут быть процессорные модули 1-4.

Следующий тактовый и импульс поступает на счетный вход счетчика 62.n и по переднему фронту увеличивает его содержимое до кода тройки ("0...011), которое подается на вход дешифратора 67.n и на его третьем выходе появляется единичный импульс, который поступает на вторые входы элемента 69.3.1.n И. Из-за наличия двух единичных импульсов на его входах, на выходе элемента 69.3.1.n И появляется единичный потенциал, который проходит через элемент 68.3.1.n ИЛИ и подается на ое-вход регистра 63.3.1.n, разрешая его работу. В следствие на его D1-вход подается значение интенсивности с выхода блока 10 оперативной памяти для последующего сохранения. Далее этот код с выхода регистра 63.3.1.n поступает на вход сумматора 59.2.1.n для суммирования с хранящимся в нем кодом. Таким образом очередное значение интенсивности фиксируется в МС. Например, на фигурах 4 и 5 это могут быть процессорные модули 4-7.

Так продолжается до тех пор, пока на выходе счетчика 62.n не появится сигнал переполнения, который подается на счетный вход счетчика 61.n и по переднему фронту увеличивает его до кода двойки, который поступает на первые входы элементов 69.1.2.n. Единичный импульс с выхода счетчика 62.n также сбрасывает его в единицу.

Работа устройства продолжается аналогично, пока, например в МС на фигурах 4 и 5 не будут зафиксированы значения интенсивности на процессоры 1-4, 2-5, 3-6, 4-7, 5-8 и 6-9. В этом случае сигнал переполнения с выхода счетчика 61.n подается на ое-вход блока 73.n сумматоров и разрешает его работу. В этом случае значения, поступившие на его соответствующие входы суммируются и поступают на выход блока 73.n сумматоров. Этот код далее подается на соответствующий вход многовходового 76 блока сумматоров.

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

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

Изобретение относится к вычислительной технике. Технический результат заключается в расширении области применения устройства за счет введения средств для анализа степени оптимальности размещения в многопроцессорных системах с общей памятью по критерию минимизации интенсивности взаимодействия процессов и данных. Устройство поиска степени оптимальности размещения в кластерных многопроцессорных системах при направленной передаче информации содержит матрицу из m строк и n столбцов элементов однородной среды, 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) элементов И, пятый строк, первый многовходовой блок сумматоров, шестой счетчик номера кластера, седьмой дешифратор номера кластера, второй многовходовой блок сумматоров, четвёртый SR-триггер объединения номера кластера, шестой элемент И номера кластера, второй элемент ИЛИ номера кластера, седьмой элемент И. 1 з.п. ф-лы, 9 ил.

1. Устройство поиска степени оптимальности размещения в кластерных многопроцессорных системах при направленной передаче информации, содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок, блок постоянной памяти, блок запоминания лучшего варианта, коммутатор, арифметико-логическое устройство, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, первый элемент сравнения, триггер начала счета, триггер режима, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу элементов с первого по n-й ИЛИ, группу элементов с первого по m-й И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый элемент задержки, первый блок элементов ИЛИ, причем выходы блока формирования перестановок соединены с соответствующими входами блока постоянной памяти и соответствующими входами блока запоминания лучшего варианта, сигнализирующий выход блока формирования перестановок соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом арифметико-логического устройства, выход которого соединен с информационным входом блока запоминания лучшего варианта, а выход блока запоминания лучшего варианта соединен с первым информационным входом арифметико-логического устройства, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы регистров с первого по n-й подключены к первым и вторым входам элементов ИЛИ соответственно, выход переполнения регистра сдвига соединен с управляющим входом арифметико-логического устройства и с управляющим входом блока формирования перестановок, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом блока формирования перестановок и с первыми входами элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход элемента И соединен со счетным входом счетчика дуг и с входом элемента задержки, выход которого соединен со вторым входом элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом элемента И, третий вход элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом элемента И, выход элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l=1, 2, …, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ, выход элемента И соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом арифметико-логического устройства, выходы элементов с первого по 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) элементов ИЛИ, первая матрица из i,j (i=1, 2, …, m; j=1, 2, …, n ) элементов И, вторая матрица из i,j (i=1, 2, …, m; j=1, 2, …, n) элементов И, пятый строк, первый многовходовой блок сумматоров, шестой счетчик номера кластера, седьмой дешифратор номера кластера, второй многовходовой блок сумматоров, четвертый SR-триггер объединения номера кластера, шестой элемент И номера кластера, второй элемент ИЛИ номера кластера, седьмой элемент И, причем тактовый вход устройства подключен к R-входу триггера объединения номера кластера, второму входу второго элемента ИЛИ номера кластера, первому входу элемента И номера кластера, счетным входам четвертого счетчика столбцов, пятого счетчика строк и второму входу седьмого элемента И, обратный выход четвертого SR-триггера объединения номера кластера соединен с первым входом второго элемента ИЛИ номера кластера, выход которого подключен ко второму входу шестого элемента И номера кластера, выход которого подключен к счетному входу шестого счетчика номера кластера, выход которого подключен ко входу седьмого дешифратора номера кластера, выходы с первого по n-й которого соединены со счетным входом пятого счетчика строк, выход которого соединен с входом четвертого дешифратора горизонтально зафиксированных дут, выходы с первого по n-й которого соединены с соответствующими первыми входами второй матрицы из i,j (i=1, 2, …, m; j=1, 2, …, n) элементов И, вторые входы которых подключены к соответствующим выходам с первого по n-й третьего дешифратора горизонтально зафиксированных дуг, вход которого подключен к выходу второго счетчика строк, счетный вход которого подключен к выходу переполнения пятого счетчика строк, выход переполнения второго счетчика строк соединен с ое-входами третьего и четвертого счетчика столбцов, счетный вход третьего счетчика столбцов подключен к выходу переполнения четвертого счетчика столбцов, выход которого подсоединен к входу шестого дешифратора вертикально зафиксированных дут, выходы с первого по n-й которого соединены со вторыми входами соответствующих элементов матрицы из i,j (i=1, 2, …, m; j=1, 2, …, n) элементов И, первые входы которых подключены к соответствующим выходам с первого по n-й пятого дешифратора вертикально зафиксированных дуг, вход которого подключен к выходу третьего счетчика столбцов, выход переполнения которого соединен с е2-входами матрицы из i,j,n (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) элементов ИЛИ соединены с соответствующими ое-входами и матрицы из i,j (i=1, 2, …, m; j=1, 2, …, n) регистров, соответствующие выходы которых подключены к входам матрицы из i,j (i=1, 2, …, m; j=1, 2, …, n) сумматоров, выходы которых соединены с соответствующими входами первого многовходового блока сумматоров, выход которого подключен к выходу устройства, прямой выход второго триггера режима подключен к первому входу седьмого элемент И, D1- и D2-входы матрицы из i,j (i=1, 2, …, m; j=1, 2, …, n) регистров подключены к выходу блока оперативной памяти.

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