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

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

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

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

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

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

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

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

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

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

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

Топологическая модель для размещения (область размещения) задается матрицей расстояний D. Элементы матрицы расстояний для кольцевой модели образуются по формуле d_i,j=(j-i+n)modn (n - количество вершин). Минимально возможное значение интенсивности размещения L^* для орграфа G независимо от топологической модели определяется по формуле

где ||a^' _k||, ||d^' _k|| - векторы, первый из которых содержит ненулевые элементы матрицы смежности А, расположенные по убыванию, а второй - ненулевые элементы матрицы расстояний D, расположенные по возрастанию; k - порядковый номер элемента; t=|E|≤n²-n - мощность множества дуг Е (количество дуг). При этом фактическое значение интенсивности размещения всегда либо больше, либо равно L^*.

Принцип расчета нижней оценки L^* поясняется фиг.2. Здесь на фиг.2а представлен вариант гипотетического ориентированного графа G, на фиг.2б представлена соответствующая представленному графу матрица смежности А, на фиг.2в показана матрица расстояний для кольцевой топологической модели. Фиг.2г поясняет порядок формирования предельных вариантов размещения (здесь фактическое значение интенсивности размещения равно значению минимального). На фиг.2г кружками обозначены гипотетические модули, а цифры внутри модулей - их соответствующие номера. Здесь пунктирные линии означают связи между модулями топологической модели, а сплошные линии показывают размещенные (назначенные) дуги. На фиг.2д записаны вектор ||a^' _k|| и вектор ||d^' _k|| для кольцевой модели, а также показан расчет соответствующего значения интенсивности размещения L^* по формуле (1). Тем самым при применении предлагаемого устройства в ВС обеспечивается подсчет минимального значения интенсивности размещения. Этот показатель может быть использован, например, для сравнения фактического значения интенсивности с минимальным и принятия решения либо о фиксации полученного варианта размещения как более оптимального, либо о дополнительном поиске.

Устройство для подсчета минимального значения интенсивности размещения в системах с кольцевой организацией (фиг.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 устройства, а также дополнительно введенный блок 32 подсчета, содержащий генератор 14 импульсов, мультиплексор 15 выбора элемента, дешифратор 16 выбора строки, первый 17 и второй 18 счетчики расстояний, умножитель 19, второй 20 сумматор, регистр 21 значения интенсивности, группу 22.1-22.m элементов ИЛИ, группу 23.1-23.m триггеров, счетчик 24 номера строки, счетчик 25 номера столбца, группу 26.1-26.m блоков элементов запрета, одновибратор 27, элемент 28 задержки, причем вход 30 запуска устройства соединен с входом генератора 14 импульсов, выход которого подключен к счетному входу счетчика 25 номера столбца, к входу элемента 28 задержки и к счетному входу первого 17 счетчика расстояний, выход переполнения счетчика 25 номера столбца подсоединен к счетному входу счетчика 24 номера строки и к R-входам группы 23.1-23.m триггеров, выход счетчика 25 номера столбца соединен с разрешающим входом мультиплексора 15 выбора элемента, выход переполнения счетчика 24 строки соединен с выходом 29 переполнения устройства, выход счетчика 24 строки подключен к входу дешифратора 16 выбора строки, выходы с 1-го по m-й которого соединены с соответствующими управляющими входами группы 26.1, 26.2, ..., 26.m блоков элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы группы 26.1, 26.2, ..., 26.m блоков элементов запрета подсоединены к соответствующим входам группы 22.1, 22.2, ..., 22.m элементов ИЛИ, выходы которых подключены к соответствующим S-входам группы 23.1, 23.2, ..., 23.m триггеров, выходы которых соединены с соответствующими входами мультиплексора 15 выбора элемента, выход которого соединен с первым входом умножителя 19 и с разрешающим входом первого 17 счетчика расстояний, вход сброса которого подключен к выходу одновибратора 27, вход которого соединен с выходом переполнения первого 17 счетчика расстояний и со счетным входом второго 18 счетчика расстояний, выход которого соединен со вторым входом умножителя 19, выход которого подключен к первому входу второго 20 сумматора, выход которого соединен с входом данных регистра 21 значения интенсивности, разрешающий вход которого соединен с выходом элемента 28 задержки, выход регистра 21 значения интенсивности подключен к выходу 31 минимального значения устройства и ко второму входу второго 20 сумматора.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мультиплексор 15 выбора элемента предназначен для подачи с выходов группы 23.1-23.m триггеров информации о наличии дуги в размещаемом графе.

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

Первый 17 и второй 18 счетчики расстояний предназначены для организации перебора в возрастающем порядке ненулевых элементов матрицы расстояний D (на выходе счетчика 18 формируется очередной элемент вектора ||d^' _k||).

Умножитель 19 необходим для умножения веса дуги на расстояние между позициями топологической модели (элемент вектора ||d^' _k||) из второго 18 счетчика расстояний.

Второй 20 сумматор предназначен для суммирования значений, поступающих с выхода умножителя 19 и регистра 21 значения интенсивности.

Регистр 21 значения интенсивности служит для накапливания минимального значения интенсивности L^* для данного графа.

Группа 22.1-22.m элементов ИЛИ служит для объединения сигналов с выходов группы 26.1-26.m блоков элементов запрета соответственно.

Группа 23.1-23.m триггеров необходима для хранения информации о наличии дуги в графе.

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

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

Группа 26.1-26.m блоков элементов запрета предназначена для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 соответственно на элементы ИЛИ 22.1-22.m.

Одновибратор 27 необходим для формирования импульсов, формирующих сигнал сброса и установку в начальное состояние первого 17 счетчика расстояний.

Элемент 28 задержки обеспечивает задержку прохождения импульса с выхода генератора 14 импульсов на разрешающий вход регистра 21 значения интенсивности на время, достаточное для завершения операции умножения в умножителе 19 и операции суммирования во втором 20 сумматоре.

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

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

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

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

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

Первоначально в матрице 1 элементов однородной среды содержится вариант размещения, соответствующий матрице смежности исходного графа. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. Группа 23.1-23.m триггеров находится в состоянии логического нуля. В первом 17 счетчике расстояний содержится код нуля ("00...00"), во втором счетчике 18 расстояний содержится код единицы ("00...01"), который поступает на второй вход умножителя 19. Регистр 21 значения интенсивности содержит код нуля ("00...00"), который с его выхода подается на второй вход второго 20 сумматора. В счетчиках 24 и 25 содержатся коды единицы ("00...01"). Единичное значение с выхода счетчика 24 подается на вход дешифратора 16, поэтому на его первом выходе присутствует единый сигнал, который подается на соответствующие управляющие входы первого блока 26.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. Эти сигналы проходят через группу 22.1-22.m элементов ИЛИ и поступают на соответствующие S-входы группы 23.1-23.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов.

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

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

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

Появление единичного потенциала на входе 30 запуска устройства запускает генератор 14 импульсов. В результате на его выходе появляется импульс, который подается на счетный вход счетчика 25 и по переднему фронту увеличивает его содержимое до кода двойки ("00...010"). Импульс с генератора 14 импульсов также подается на вход элемента 28 задержки и блокирует прохождение импульса на время, достаточное для появления на выходе второго 20 сумматора кода полученной суммы. Также положительный импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 17, но увеличение его содержимого не происходит из-за отсутствия единичного сигнала на его разрешающем входе.

Код числа два с выхода счетчика 25 подается на разрешающий вход мультиплексора 15 и разрешает поступление импульса с выхода триггера 23.2 (в случае, если он установлен в единицу) на вход мультиплексора 15 и далее появление единицы на его выходе. В этом случае единичный импульс с выхода мультиплексора 15 поступает на первый вход умножителя 19, на втором входе которого присутствует код числа один (выбирается код расстояния d^' _k=1) с выхода счетчика 18. Этот же импульс с выхода мультиплексора 15 поступает на разрешающий вход счетчика 17 и разрешает увеличение его содержимого по переднему фронту на единицу. Так как на счетном входе счетчика 17 присутствует положительный импульс, то в нем происходит увеличение содержимого на единицу и устанавливается код единицы ("00...01"). В результате умножения на выходе умножителя 19 появляется код числа один ("00...01"). Этот код подается на вход данных регистра 21. К этому времени элемент 28 задержки пропускает импульс с его входа, и он поступает на разрешающий вход регистра 21. Таким образом, в нем записывается код числа единицы.

Следующий тактовый импульс с выхода генератора 14 импульсов подается на счетный вход счетчика 25, на счетный вход счетчика 17 и на вход элемента 28 задержки. В счетчике 25 по переднему фронту устанавливается код числа три ("00...011"). Код тройки с выхода счетчика 25 подается на разрешающий вход мультиплексора 15 и разрешает прохождение импульса с выхода триггера 23.3 на выход мультиплексора 15. Далее положительный импульс поступает на разрешающий вход счетчика 17 и тем самым разрешает увеличение его содержимого до кода числа два ("00...010"). Единичный импульс с выхода мультиплексора 15 подается на первый вход умножителя 19, на втором входе которого присутствует код числа один. В результате умножения получается единица, код которой с выхода умножителя 19 подается на первый вход второго 20 сумматора, на втором входе которого присутствует код числа один из регистра 21. После суммирования получается число два, код которого поступает на вход данных регистра 21. К этому времени элемент 28 задержки пропускает импульс со своего входа, который поступает на разрешающий вход регистра 21, разрешая в нем запись по переднему фронту кода числа два.

Так происходит до тех пор, пока на выходе переполнения счетчика 25 не появится импульс переполнения. Этот сигнал поступает на счетный вход счетчика 24 и по переднему фронту увеличивает его содержимое до кода числа два ("00...010"). Импульс переполнения с выхода счетчика 25 также подается на R-входы группы 23.1, 23.2, ..., 23.m триггеров и устанавливает их в нулевое состояние. Код числа два с выхода счетчика 24 поступает на вход дешифратора 16 и возбуждает на его втором выходе единичный импульс, который проходит на соответствующие управляющие входы блока 26.2 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов второй строки матрицы 1. Эти сигналы проходят через группу 22.1, 22.2, ..., 22.m элементов ИЛИ и поступают на соответствующие S-входы группы 23.1, 23.2, ..., 23.m триггеров, устанавливая их в единичное состояние при наличии соответствующих единичных сигналов. Счетчик 25 устанавливается в нулевое состояние ("00...00").

Очередной тактовый импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 25 и по переднему фронту увеличивает его содержимое до кода единицы ("00...01"). Импульс с генератора 14 импульсов также поступает на вход элемента 28 задержки, задерживая его прохождение на выход. Также импульс с генератора 14 импульсов поступает на счетный вход счетчика 17, но увеличение его содержимого не происходит. Код числа один с выхода счетчика 25 подается на разрешающий вход мультиплексора 15, и единичный сигнал с выхода триггера 23.1 подается на выход мультиплексора 15. Далее этот импульс поступает на первый вход умножителя и на разрешающий вход счетчика 17, разрешая увеличение содержащегося в нем кода на единицу. На втором входе умножителя 19 присутствует код числа один (d^' _k=1). Результат умножения подается на первый вход сумматора 20, на втором входе которого присутствует код с выхода регистра 21. Код результата суммирования подается на вход данных регистра 21. К этому времени элемент 28 задержки пропускает импульс, который проходит на разрешающий вход регистра 21. Таким образом, происходит запись нового кода.

Так происходит, пока на выходе переполнения первого 17 счетчика расстояний не появится единичный импульс (все n кодов для расстояний d^' _k=1 обработаны). Этот сигнал поступает на счетный вход второго 18 счетчика расстояний и по переднему фронту устанавливает в нем код числа два (d^' _k=2). Таким образом, выбирается код расстояния d^' _k=2. Сигнал переполнения с выхода счетчика 17 также поступает на вход одновибратора 27 и возбуждает на его выходе импульс. Этот импульс подается на вход сброса счетчика 17 и устанавливает в нем начальное, нулевое ("00...00"), состояние.

Далее устройство продолжает работать аналогично описанному выше. Очередной импульс с генератора 14 импульсов подается на счетный вход счетчика 25, на счетный вход счетчика 17 и на вход элемента 28 задержки. По приходу импульса с генератора 14 импульсов счетчик 25 по переднему фронту увеличивает свое содержимое на единицу, элемент 28 задержки задерживает импульс на время, достаточное для установления в умножителе 19 и сумматоре 20 нового кода. Код с выхода счетчика 25 подается на разрешающий вход мультиплексора 15 и разрешает прохождение единичного импульса с выхода триггера 23.i (i=1, 2, ..., m) на выход мультиплексора 15, откуда он поступает на первый вход умножителя 19 и на разрешающий вход счетчика 17. Появление этого импульса разрешает увеличение на единицу кода, содержащегося в счетчике 17. Одновременно с этим происходит умножение в умножителе 19 и выдача результата умножения на первый вход сумматора 20, на втором входе которого уже присутствует код с выхода регистра 21. К этому моменту элемент 28 задержки разрешает похождение импульса со своего входа на разрешающий вход регистра 21, разрешая запись в него нового кода с выхода второго 20 сумматора.

Так продолжается до тех пор, пока на выходе 29 переполнения счетчика 24 не появится положительный импульс, свидетельствующий об окончании процесса подсчета минимального значения интенсивности размещения в системах с кольцевой организацией. К этому моменту в регистре 21 содержится искомый код, а с выхода 31 минимального значения на ВУУ поступает минимальное значение интенсивности размещения.

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

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

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