УСТРОЙСТВО ПОИСКА НИЖНЕЙ ОЦЕНКИ РАЗМЕЩЕНИЯ В СИСТЕМАХ С МАТРИЧНОЙ ОРГАНИЗАЦИЕЙ ПРИ НАПРАВЛЕННОЙ ПЕРЕДАЧЕ ИНФОРМАЦИИ Российский патент 2010 года по МПК G06F17/50 

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

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

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

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

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

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

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

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

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

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

Исходная (размещаемая) задача (процесс, алгоритм) представляется в виде ориентированного невзвешенного графа G=<X,E>, вершины x_i∈X которого соответствуют подзадачам (подалгоритмам), а дуги e_ij∈E⊆X*X задают управляющие и/или информационные связи между подзадачами.

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

- множество модулей МС, организованных

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

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

где , , , !

МС задается матрицей смежности где w_ij определяется интенсивностью взаимодействия (потока передачи данных, слов данных, кодовых слов передачи управления) между задачами x_i и x_j.

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

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

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

Устройство поиска нижней оценки размещения в системах с матричной организацией при направленном обмене информацией (фиг.1) содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блоки 2.1-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.i.j (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных модулей, матрицу 24. i.j (i=1, 2, …, m, j=1, 2, …, n) D-триггеров, матрицу 25.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И, причем вход 23 запуска устройства подключен к генератору 14 импульсов, выход которого подключен к счетным входам счетчика 18 текущего элемента и счетчика 20 столбцов, а также к разрешающим входам матрицы 24.i.j (i=1, 2, …, m, j=1, 2, …, n) D-триггеров, выход переполнения счетчика 20 столбцов подключен к счетному входу счетчика 19 строк, информационные выходы счетчика 20 столбцов подключены к соответствующим управляющим входам дешифратора 17 выбора столбца, информационные выходы счетчика 19 строк подключены к соответствующим управляющим входам дешифратора 16 выбора строки, i-й выход которого подключен к соответствующим первым входам элементов (i,1), (i,2), … (i,m) матрицы элементов 25.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И, j-й выход дешифратора 17 выбора столбца подключены к соответствующим вторым входам элементов (1,j), (2,j), … (n,j) матрицы 25.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И, выходы которой подключены к соответствующим (i,j)-м счетным входам матрицы 22.i.j (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных модулей, выходы которых соединены с соответствующими (i,j)-ми выходами матрицы 26.i.j (i=1, 2, …, m, j=1, 2, …, n) выходов значений нижней оценки устройства, D-входы матрицы 24.i.j (i=1, 2, …, m, j=1, 2, …, n) D-триггеров подключены к соответствующим индикаторным выходам элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы матрицы 24.i.j (i=1, 2, …, m, j=1, 2, …, n) D-триггеров подключены к соответствующим информационным входам мультиплексора 15 выбора элемента, выход переполнения счетчика 18 текущего элемента подсоединен к выходу 27 остановки устройства.

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

Матрица 1 элементов однородной среды предназначена для моделирования процесса решения задач размещения.

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

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

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

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

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

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

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

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

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

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

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

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

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

Мультиплексор 15 выбора элемента предназначен для подачи с выходов матрицы 24.i.j (i=1, 2, …, m, j=1, 2, …, n) D-триггеров информации о назначенной (размещенной) вершине в (i.j)-м модуле МС.

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

Счетчик 18 текущего элемента содержит информацию о текущей ячейке матрицы смежности.

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

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

Блок 21 поиска нижней оценки служит для определения нижней оценки размещения в МС по критерию минимизации интенсивности взаимодействия процессов и данных.

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

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

Матрица 24.i.j (i=1, 2,…, m, j=1, 2, …, n) D-триггеров служит для хранения информации о текущем варианте размещения (матрицы смежности).

Матрица 25.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И предназначена для объединения сигналов с выходов дешифратора 15 выбора строки и дешифратора 16 выбор столбца для последующей подачи на соответствующие счетные входы матрицы 22.i.j (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных модулей.

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

Выход 27 остановки устройства необходим для выдачи информации о переполнении счетчика 18 текущего элемента, что и является сигналом окончания работы блока 21 поиска нижней оценки.

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

Первоначально в матрице 1 элементов однородной среды содержится вариант размещения, соответствующий матрице смежности графа Н МС. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. Триггеры матрицы 37.i.j (i=1, 2, …, m, j=1, 2, …, n) D-триггеров находится в состоянии, соответствующем матрице смежности W. В счетчике 20 столбцов и счетчике 18 текущего элемента содержится код нуля («00…00»). В счетчике 19 строк содержится код единицы («00…01»). Код единицы с выхода счетчика 19 поступает на управляющий вход дешифратора 16 строк. В счетчиках матрицы 22.i.j (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных модулей содержаться коды нулей («00…00»).

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

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

Задача поиска нижней оценки размещения в системах с матричной организацией решается следующим образом. После выполнения очередной перестановки строк на индикаторных выходах элементов матрицы 1 появляются сигналы, соответствующие новому варианту размещения. Эти сигналы поступают на входы матрицы 24.i.j (i=1, 2, …, m, j=1, 2, …, n) D-триггеров. В результате в них устанавливаются коды, соответствующие матрице смежности графа Н МС. Одновременно с этим запускается генератор 14 импульсов и начинается работа блока 21 поиска нижней оценки.

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

Импульс с выхода генератора 14 импульсов подается на счетные входы счетчика 20 и счетчика 18 и по переднему фронту увеличивает их содержимое до кода единицы («00…01»). Этот же импульс поступает на разрешающие входы матрицы 24.i.j (i=1, 2, …, m, j=1, 2, …, n) D-триггеров, разрешая прохождение сигналов с выходов на соответствующие информационные входы мультиплексора 15. Код единицы с выхода счетчика 18 поступает на управляющие входы мультиплексора 15, определяя выбор первого информационного входа, сигнал которого проходит на разрешающий вход дешифратора 16. Код единицы с выхода счетчика 20 поступает на управляющий вход дешифратора 17, возбуждая единичный сигнал на первом выходе дешифратора 17, который подается на вторые входы (i.1) матрицы 25.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И. Код единицы с выхода счетчика 19 поступает на управляющий вход дешифратора 16. Так как на разрешающем входе дешифратора 16 присутствует нулевой сигнал с выхода мультиплексора 15, на всех выходах дешифратора 16 также остаются нулевые сигналы, которые поступают на первые входы матрицы 25.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И, что запрещает прохождение единичного сигнала на любой из счетных входов матрицы 22.i.j (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных модулей.

Очередной тактовый импульс с генератора 14 импульсов поступает на счетные входы счетчиков 18 и 20, увеличивая их содержимое по переднему фронту до кода двойки («00…10»). Код двойки с выхода счетчика 18 поступает на управляющий вход мультиплексора 15, разрешая прохождение сигнала со второго информационного входа на разрешающий вход дешифратора 16, на управляющем входе которого остается сигнал единицы с выхода счетчика 19. Код двойки с выхода счетчика 20 поступает на управляющий вход дешифратора 17, возбуждая единичный сигнал на втором выходе дешифратора 17. Этот сигнал подается на вторые входы (i.2) матрицы 25.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И. Так как на выходе мультиплексора 15 присутствует единичный сигнал со второго информационного входа, что означает наличие дуги, направленной во вторую вершину графа Н, на первом выходе дешифратора 16 в соответствии с кодом единицы на управляющем входе возбуждается единичный сигнал. Этот сигнал подается на первые входы (1,j) матрицы 25.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И. Таким образом, на обоих входах (1, 2)-элемента И присутствует единичный сигнал, проходящий на счетный вход счетчика 22.1.2, увеличивая его содержимое по заднему фронту до кода единицы («00…01»).

Так продолжается до тех пор, пока счетчик 20 не дойдет до кода тройки («00…11»), что возбуждает единичный сигнал на его выходе переполнения. Этот сигнал подается на счетный вход счетчика 19 и по заднему фронту увеличивает его содержимое на единицу, вызывая единичный сигнал на соответствующем выходе дешифратора 16 при наличии единичного сигнала с выхода мультиплексора 15. Счетчик 20 по окончании такта сбрасывается в нулевое состояние и в следующем такте вновь увеличивается до единицы, в результате чего вновь выбирается первый столбец матрицы счетчиков фиксированных модулей 25.i.j (i=1, 2, …, m, j=1, 2, …, n).

Счетчик 19 при достижении кода тройки возвращается в состояние единицы («00…01»), и устройство 21 продолжает работать по описанному сценарию до тех пор, пока на выходе переполнения счетчика 18 не появится единичный сигнал, что означает достижение конца матрицы смежности и является сигналом остановки устройства. Соответствующие значения интенсивностей к этому времени содержатся в матрице 25.i.j (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных модулей, а на соответствующих выходах 26.i.j (i=1, 2, …, m, j=1, 2, …, n) выходов значений интенсивности на ВУУ подаются соответствующие коды.

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

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