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

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

 

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

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

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

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

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

Исходная (размещаемая) задача (процесс, алгоритм) представляется в виде неориентированного невзвешенного графа G=<X,E>, вершины х_i∈Х которого соответствуют подзадачам (подалгоритмам), а дуги е_ij∈Е⊆Х×X задают управляющие и/или информационные связи между подзадачами. Размещаемый граф G задается соответствующей матрицей смежности. Строки и столбцы матрицы отмечаются номерами вершин графа. На пересечении i-й строки и j-го столбца ставится единица, если i-ю и j-ю вершину соединяет дута, и ноль - в противном случае.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мультиплексор 17 выбора элемента предназначен для подачи с выходов триггеров 24.1, 24.2, ... 24.m информации о наличии дуги в графе.

Первый 18 и второй 19 дешифраторы инцидентной вершины служат для выбора очередной дуги графа и подачи соответствующих сигналов на входы второй группы 23.1-23.m элементов ИЛИ.

Дешифратор 20 выбора строки служит для выбора очередной строки матрицы 1 (матрицы смежности размещаемого графа).

Первая группа 21.1-21.m элементов ИЛИ необходима для объединения сигналов с выходов группы элементов 28.1-28.m запрета соответственно.

Группа 22.1-22.m кольцевых счетчиков нижней оценки предназначена для накапливания информации о загрузке модулей КС. Работа счетчика основана на пересчете поступающих значений по модулю m.

Вторая группа 23.1-23.m элементов ИЛИ служит для объединения сигналов с выходов первого 18 и второго 19 дешифраторов инцидентной вершины и последующей подачи на соответствующие кольцевые счетчики 22.(i-1) (i=1, 2, ..., m) и 22.i (i=1, 2, ..., m) группы 22.1-22.m кольцевых счетчиков нижней оценки.

Группа 24.1-24.m триггеров необходима для хранения информации о наличии дуги, инцидентной соответствующим выбранным вершинами из матрицы смежности.

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

Блок 27 поиска нижней оценки необходим для поиска нижней оценки размещения в кольцевых системах.

Группа 28.1-28.m блоков элементов запрета предназначена для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 на соответствующие элементы ИЛИ 21.1-21.m.

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

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

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

Выход 32 значения нижней оценки служит для выдачи ВУУ значения нижней оценки текущего варианта размещения в КС.

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

Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения, соответствующий матрице смежности исходного графа. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В счетчиках 15 и 16 содержится код единицы («00...01»). Единичное значение с выхода счетчика 15 подается на вход дешифратора 20, поэтому на первом его выходе присутствует единый сигнал, который подаются на соответствующие управляющие входы первого блока 28.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. Эти сигналы проходят через группу 21.1-21.m элементов ИЛИ и поступают на соответствующие S-входы группы 24.1-24.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. В счетчике 25 содержится код нуля, а в счетчике 26 - код единицы («00...01»). В счетчиках 22.1-22.m содержится код нуля.

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

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

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

Импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 16 и по переднему фронту увеличивает его содержимое до кода двойки («00...010»). Код числа два с его выхода поступает на разрешающий вход мультиплексора 17 выбора элемента и разрешает прохождение сигнала с выхода триггера 24.2 на выход мультиплексора 17. В случае, если триггер 24.2 установлен в единицу, то единичный импульс с выхода мультиплексора 17 поступит на счетные входы счетчиков 25 и 26. В результате в счетчике 25 будет по переднему фронту установлен код единицы («00...01»), а в счетчике 26 по переднему фронту будет установлен код двойки («00...010»).

Код единицы с выхода счетчика 25 и код двойки с выхода счетчика 26 поступает на соответствующие входы первого 18 и второго 19 дешифраторов инцидентной вершины. В результате этого на первом выходе дешифратора 18 и на втором выходе дешифратора 19 возбуждаются единичные импульсы, которые поступают на соответствующие входы элементов 23.1 и 23.2 ИЛИ. В результате этого на входах счетчиков 22.1 и 22.2 появляются единичные импульсы, и соответствующие счетчики по заднему фронту увеличиваются на единицу. Таким образом происходит фиксация первой дуги графа.

Очередной тактовый импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 16 столбцов и по переднем фронту устанавливает в нем код тройки («00...011»). Код числа три поступает на разрешающий вход мультиплексора 17, и импульс с выхода триггера 24.3 поступает на выход мультиплексора 17. Таким образом, единичный сигнал с выхода мультиплексора 17 поступает на счетные входы счетчиков 25 и 26, устанавливая в них по переднему фронту коды два («00...010») и три («00...011») соответственно. Коды с выходов счетчиков 25 и 26 поступают на соответствующие входы дешифраторов 18 и 19. В результате на соответствующем втором выходе дешифратора 18 и на соответствующем третьем выходе дешифратора 19 возбуждается единичный импульс. Единичный сигнал проходит через соответствующие элементы 23.2 и 23.3 ИЛИ и поступает на соответствующие входы счетчиков 22.2 и 23.3, увеличивая их содержимое по заднему фронту на единицу. В результате происходит фиксация второй дуги графа.

Так продолжается, пока в счетчике 16 не установится код (n+1). В результате этого на его выходе переполнения появится единичный импульс, который поступит на счетный вход счетчика 15 и по переднему фронту установит в нем код двойки («00...010»). Единичный импульс с выхода переполнения счетчика 16 поступает также на R-входы группы 24.1-24.m триггеров и сбрасывает их содержимое в ноль.

Код числа два с выхода счетчика 15 поступает на установочный вход счетчика 16 и устанавливает в нем начальное значение кода числа два («00...010»). Тот же код поступает на вход дешифратора 20 выбора строки, и поэтому на его втором выходе возбуждается единичный импульс. Единичный импульс поступает на соответствующие управляющие входы второго блока 28.2 элементов запрета и обеспечивает прохождение на их выходы сигналов с индикаторных выходов элементов второй строки матрицы 1. Эти сигналы проходят через группу 21.1-21.m элементов ИЛИ и поступают на соответствующие S-входы группы 24.1-24.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов.

Очередной тактовый импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 16 столбцов и по переднему фронту устанавливает в нем код числа три («00...011»). Код числа три с выхода счетчика 16 поступает на разрешающий вход мультиплексора 17 и разрешает прохождение единичного импульса с выхода триггера 24.3 на выход мультиплексора 17. Единичный импульс с выхода мультиплексора 17 подается на счетные входы счетчиков 25 и 26, увеличивая их содержимое по переднему фронту на единицу. Коды значений, установленных в счетчиках 25 и 26, поступают на соответствующие входы дешифраторов 18 и 19, возбуждая в них выходы, соответствующие поступившим на их входы кодам. Единичный импульс с выходов дешифраторов 18 и 19 через соответствующие элементы 23.i (i=1, 2, ..., m) и 23.j (i=1, 2, ..., m) ИЛИ второй группы 23.1-23.m элементов ИЛИ поступает на счетные входы счетчиков 23.j (j=1, 2, ...m) и 23.j (i=1, 2, ..., m) группы 22.1-22.m кольцевых счетчиков, увеличивая их содержимое по переднему фронту на единицу и фиксируя очередную дугу графа.

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

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

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

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