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

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

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

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

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

Наиболее близким к предлагаемому устройству по технической сущности является устройство для оценки размещения элементов, содержащее матрицу элементов однородной среды, состоящую из элементов однородной среды, блоки подсчета единиц, блок нахождения максимума, первый сумматор, блок памяти, вход записи исходного гиперграфа, вход управления перестановкой столбцов, вход управления перестановкой строк, вход управления записью в блок памяти, выходы оценки текущего размещения, информационный выход и вход установки (а.с. 1430949 СССР, кл. G06F 7/00, 15/20, опубл. 15.10.88, БИ 38).

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

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

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

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

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

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

Исходная задача (процесс, алгоритм) представляется в виде неориентированного невзвешенного графа G=<X,E>, вершины x, Х которого соответствуют подзадачам (подалгоритмам), а дуги е_ij Е × Х × Х задают управляющие и/или информационные связи между подзадачами и фактически являются каналами передачи данных.

Шинная структура (ШС) отображается однородной средой, которой ставится в соответствие топологическая модель в виде графа H=<U,V>, где U - множество модулей ШС (фиг.2б) |U|=N=n и является количеством модулей ШС и количеством вершин графа G, V - множество межмодульных связей. ШС может быть описана матрицей смежности W=||w_ij ||_n×n, где w_ij определяется интенсивностью взаимодействия (потока передачи данных, слов данных, кодовых слов передачи управления и т.п.) между подзадачами х₁ и x_j.

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

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

Сущность предлагаемого критерия поясняется на фиг.2. Здесь на фиг.2а представлен размещаемый граф G. В нем линии представляют дуги графа и соответственно каналы передачи данных, а цифры рядом с ними - веса дуг (объемы передаваемых данных). Кружки представляют вершины графа, а внутри них - соответствующие номера вершин графа G. На фиг.2б показан вариант шинной топологии с гипотетическим вариантом размещения. Здесь кружки с соответствующими номерами подзадач внутри обозначают назначенные подалгоритмы. Данному варианту размещения соответствует матрица смежности W, представленная на фиг.2в. Предлагаемый в устройстве поиск нижней оценки размещения предполагает, что топология исходного графа G и графа связей Н между модулями тождественны. При этом при вычислении минимального значения интенсивности не принимаются во внимание ограничения, накладываемые фактическими связями между задачами в графе G. То есть, при вычислении минимального значения необходимо назначать дуги графа G на смежные модули ДС. Полученное в результате суммарное значение интенсивности называется минимальным. Реальное суммарное значение интенсивности графа возможно будет больше, и чем ближе оно к значению минимальной нижней оценки, тем лучше качество полученного варианта размещения.

Устройство поиска минимального значения интенсивности размещения в системах с шинной организаций при двунаправленной передаче информации содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блоки 2.1, 2.2,,2.n подсчета единиц, блок 3 нахождения максимума, первый сумматор 4, блок 5 памяти, причем входы управления перестановкой столбцов матрицы 1 элементов однородной среды соединены с входом 7 управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы 1 элементов однородной среды соединены с входом 8 управления перестановкой строк устройства, входы установки матрицы 1 элементов однородной среды соединены с входом 13 установки устройства, информационные входы матрицы 1 элементов однородной среды соединены с входом 6 записи устройства, индикаторные выходы элементов j-го столбца (j=1,2,,n) матрицы 1 элементов однородной среды соединены с входом блока 2.j подсчета единиц, выход которого соединен с j-м входом блока 3 нахождения максимума и j-м входом первого 4 сумматора, выходы которых соединены с выходом 10 максимальной длины ребра устройства и выходом 11 суммарной длины ребер устройства соответственно, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i=1,2,,m) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также дополнительно введенный блок 21 поиска минимального значения, содержащий генератор 14 импульсов, дешифратор 15 строк, дешифратор 16 фиксируемой дуги, мультиплексор 17 выбора элемента, счетчик 18 строк, счетчик 19 столбцов, второй 20 сумматор, группу 22.1, 22.2,,22.m счетчиков фиксированных дуг, группу 23.1, 23.2,,23.m RS-триггеров, группу блоков 24.1, 24.2,,24.m элементов запрета, группу 25.1, 25.2,,25.m элементов ИЛИ, причем вход 28 запуска устройства соединен с входом генератора 14 импульсов, выход которого подключен к счетному входу счетчика 19 столбцов, выход которого подключен к управляющим входам мультиплексора 17 выбора элемента и дешифратора 16 фиксируемой дуги, выход переполнения счетчика 19 столбцов подсоединен к счетному входу счетчика 18 строк и к R-входам группы 23.1, 23.2,,23.m RS-триггеров, выход счетчика 18 строк подключен к входу дешифратора 15 строк и к установочному входу счетчика 19 столбцов, выход переполнения счетчика 18 строк подсоединен к выходу 26 переполнения устройства, выходы с 1-го по m-й дешифратора 15 строк подключен к управляющим входам группы блоков 24.1, 24.2,,24.m элементов запрета, соответствующие входы которых подсоединены к соответствующим выходам элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы группы блоков 24.1, 24.2,,24.m элементов запрета подсоединены к соответствующим входам группы 25.1, 25.2,,25.m элементов ИЛИ, выходы которых подсоединены к соответствующим S-входам группы 23.1, 23.2,,23.m RS-триггеров, выходы которых соединены с соответствующими входами мультиплексора 17 выбора элемента, выход которого подключен к входу дешифратора 16 фиксируемой дуги, выходы с 1-го по m-й которого подсоединены к соответствующим счетным входам группы 22.1, 22.2,, 22.m счетчиков фиксированных дуг, выходы которых соединены с соответствующими входами второго 20 сумматора и с выходами 27.1, 27.2,,27.m значений интенсивности устройства, выход второго 20 сумматора подключен к выходу 29 значения интенсивности устройства.

Назначение элементов и блоков устройства поиска минимального значения интенсивности размещения в системах с шинной организаций при двунаправленной передаче информации (фиг.1) состоит в следующем:

Матрица 1 элементов однородной среды предназначена для моделирования процесса решения задач размещения и отображает матрицу смежности W для графа G задачи.

Блоки 2.1 - 2.n подсчета единиц предназначены для преобразования кодов с индикаторных выходов элементов соответствующих столбцов матрицы 1 в двоичные коды.

Блок 3 нахождения максимума предназначен для выделения максимального кода из множества кодов на его входах.

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

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

Вход 6 записи устройства служит для записи матрицы, представляющей размещаемый граф.

Вход 7 управления перестановкой столбцов устройства предназначен для приема сигнала от ВУУ о перестановке столбцов.

Вход 8 управления перестановкой строк устройства предназначен для приема сигнала от ВУУ о перестановке строк.

Вход 9 управления записью устройства необходим для приема сигнала «Запись» от ВУУ. По этому сигналу в блок 5 памяти заносится текущий вариант размещения из матрицы 1.

Выход 10 максимальной длины ребра устройства необходим для выдачи значения максимальной длины ребра на ВУУ.

Выход 11 суммарной длины ребер устройства необходим для выдачи значения суммарной длины ребер на ВУУ.

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

Вход 13 установки устройства необходим для синхронизации записи информации в элементы матрицы 1.

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

Дешифратор 15 строк служит для выбора строки матрицы 1 элементов однородной среды.

Дешифратор 16 фиксируемой дуги служит для подачи информации о текущей дуге, подлежащей фиксации.

Мультиплексор 17 выбора элемента предназначен для разрешения подачи сигнала с очередного триггера 23.i (i=1,2,,m) группы 23.1-23.m RS-триггеров на вход дешифратора 16 фиксируемой дуги. Фактически мультиплексор 17 выбирает очередной элемент матрицы смежности.

Счетчик 18 строк служит для хранения информации о номере текущей обрабатываемой строки матрицы 1.

Счетчик 19 столбцов необходим для хранения информации о номере текущего обрабатываемого столбца выбранной строки матрицы 1 (текущего столбца смежности W).

Второй 20 сумматор служит для хранения суммарного значения минимальной нижней оценки размещения для текущего размещаемого графа G.

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

Группа 22.1, 22.2,,22.m счетчиков фиксированных дуг хранит информацию о значениях интенсивности размещения для i-го (i=l, 2,,m) модуля системы с шинной организации.

Группа 23.1, 23.2,.,23.m RS-триггеров предназначена для временного хранения информации о наличии дуг в модулях выбранной строки МС.

Группа 24.1, 24.2,,24.m блоков элементов запрета необходима для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 элементов однородной среды на соответствующие элементы группы 25.1, 25.2,,25.m элементов ИЛИ соответственно.

Группа 25.1, 25.2,,25.m элементов ИЛИ служит для объединения сигналов с выходов группы 24.1, 24.2,,24.m блоков элементов запрета.

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

Выходы 27.1, 27.2,,27.m значений интенсивности устройства служат для подачи на ВУУ значений интенсивности для i-ro (i=1, 2,,m) модуля системы с шинной организацией.

Вход 28 запуска устройства предназначен для запуска генератора 14 импульсов, что одновременно служит сигналом запуска работы блока 21 поиска минимального значения.

Выход 29 значения интенсивности предназначен для подачи на ВУУ информации о минимальном значении интенсивности размещения в системах с шинной организацией.

Работа блоков 1, 2, 3, 4 и 5 подробно описана в прототипе и поэтому здесь не рассматривается.

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

Первоначально в матрице 1 элементов однородной среды содержится вариант размещения. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В счетчике 18 строк и 19 столбцов хранится код единицы («0...01»), триггеры 23.i (i=1, 2,,m) группы 23.1, 23.2,,23.m RS-триггеров находятся в состоянии логического нуля. В счетчиках 22.i (i=1, 2,,m) группы 22.1, 22.2,,22.m счетчиков фиксированных дуг содержатся коды нулей («000»), во втором 20 сумматоре первоначально также содержится код нуля. Так как в счетчике 18 строк хранится код единицы, то этот код поступает на вход дешифратора 15 строк и на его первом выходе появляется единичный импульс, который поступает на управляющие входы первого блока 24.1 элементов запрета и разрешает прохождение сигналов с индикаторных выходов первой строки матрицы 1. Этот импульс поступает на соответствующие входы 25.1, 25.2,,25.m элементов ИЛИ. Импульсы пройдя через элементы ИЛИ подаются на соответствующие S-входы группы 23.1, 23.2,,23.m RS-триггеров и устанавливают соответствующие триггеры в единичные состояния при условии наличия единичных сигналов.

Оценка размещения по критериям суммарной длины ребер и максимальной длины ребра происходит следующим образом. Информация с индикаторных выходов элементов каждого столбца матрицы 1 поступает в соответствующие блоки подсчета единиц. Блок 2.i (i=1,2,,n) выдает двоичное число (код), равное количеству поступивших на его вход единиц. Полученное число далее поступает на входы первого 4 сумматора и блока 3 нахождения максимума, соответствующие данному блоку подсчета единиц. В результате на выходе 10 устройства образуется код (оценка) максимальной длины ребра, а на выходе 11 - код (оценка) суммарной длины ребер, отвечающие текущему варианту размещения схемы (содержащемуся в матрице 1). Полученные оценки далее поступают на ВУУ, где происходит их сравнение с предыдущими значениями. В случае улучшения оценок ВУУ подает импульс (сигнал «Запись») на вход 9 управления записью устройства и текущий вариант размещения переписывается в блок 5 памяти из матрицы 1. Более подробно рассмотренный режим работы устройства описан в прототипе.

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

Первый тактовый импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 19 столбцов и по переднему фронту увеличивает его содержимое на единицу, устанавливая в нем код числа два («0010»). Код двойки поступает на управляющие входы мультиплексора 17 и дешифратора 16. Следовательно, единичный импульс с выхода триггера 23.2 поступает на второй вход мультиплексора 17 и далее проходит на вход дешифратора 16. Так как на его управляющем входе присутствует код числа два, то на втором выходе дешифратора 16 возбуждается единичный импульс, который подается на счетный вход счетчика 22.2 и по заднему фронту увеличивает его значение на единицу до кода единицы («001»). Таким образом происходит фиксация первой дуги графа G.

Второй импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 19 и по переднему фронту увеличивает его содержимое на единицу до кода числа три («0011»). Код тройки с выхода счетчика 19 подается на управляющие входы мультиплексора 17 и дешифратора 16. Таким образом, единичный потенциал с выхода триггера 23.3 поступает на выход мультиплексора 17 и далее проходит на вход дешифратора 16. Так как на его управляющем входе присутствует код числа три, то на третьем выходе дешифратора 16 появляется единичный импульс, который проходит на счетный вход счетчика 22.3 и по заднему фронту увеличивает его содержимое на единицу до кода числа один («001»). Так происходит фиксация второй дуги графа G.

Аналогично работа схемы продолжается до тех пор, пока на выходе переполнения счетчика 19 не появится единичный импульс. Это означат, что элементы первой строки матрицы 1 обработаны. В этом случае единичный сигнал поступает на R-входы триггеров 23.i (i=1, 2,,m) группы 23.1, 23.2,,23.m RS-триггеров и сбрасывает их в нулевое состояние. Тот же самый импульс подается на счетный вход счетчика 18 и по переднему фронту увеличивает его содержимое на единицу, устанавливая в нем код числа два («0010»). Код числа два поступает на вход дешифратора 15 и на втором его выходе возбуждается единичный импульс, который подается на управляющие входы второго блока 24.2 элементов запрета и разрешает прохождение сигналов с индикаторных выходов второй строки матрицы 1. Этот импульс поступает на соответствующие входы 25.1, 25.2,,25.m элементов ИЛИ. Импульсы пройдя через элементы ИЛИ подаются на соответствующие S- входы группы 23.1, 23.2,,23.m RS-триггеров и устанавливают соответствующие триггеры в единичные состояния при условии наличия единичных сигналов. Код числа два с выхода счетчика 18 также поступает на установочный вход счетчика 19 и устанавливает в нем начальное состояние - число два.

Следующий тактовый сигнал с выхода генератора 14 импульсов поступает на счетный вход счетчика 19 и по переднему фронту увеличивает его содержимое на единицу до кода тройки («0.011»). Этот код поступает на управляющие входы мультиплексора 17 и дешифратора 16. Вследствие этого, единичный импульс с выхода триггера 23.3 поступает на третий вход мультиплексора 17 и далее на вход дешифратора 16. Так как на его управляющем входе присутствует код числа три, то на третьем выходе дешифратора 16 появляется единичный сигнал, который поступает на счетный вход счетчика 22.3 и по заднему фронту увеличивает его содержимое на единицу.

Таким образом работа устройства продолжается до тех пор, пока выходе переполнения не появится единичный импульс, который свидетельствует о том, что все строки матрицы 1 элементов однородной среды (матрицы смежности) обработаны и работа блока 21 закончена. В тоже время в счетчиках 22.i (i=1, 2,,m) группы 22.1, 22.2,,22.m счетчиков фиксированных дуг содержатся коды значений интенсивности каждого модуля системы с шинной организацией. В тоже время во втором 20 сумматоре хранится суммарное значение интенсивности. Коды значений интенсивности, хранящиеся в счетчиках 22.1, 22.2,,22.m фиксированных дуг подаются на соответствующие выходы 27.1, 27.2,, 27.m значений интенсивности устройства, откуда эти значения подаются на ВУУ для обработки. В случае необходимости анализа суммарного значения интенсивности размещения, соответствующий код поступает на выход 29 значения интенсивности устройства и поступает на ВУУ для дальнейшей обработки.

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

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