УСТРОЙСТВО ДЛЯ ОЦЕНКИ СТЕПЕНИ ПРИБЛИЖЕНИЯ РАЗМЕЩЕНИЯ К ОПТИМАЛЬНОМУ Российский патент 2005 года по МПК G06F17/00 G06G7/122 

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

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

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

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

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

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

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

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

Сущность предлагаемого критерия поясняется фиг.2. Здесь на фиг.2а представлен вариант гипотетического исходного размещения, а фиг.2б задает матрицу инцидентности для исходного размещения элементов. Фиг.2в описывает вариант размещения после перестановки модулей 2 и 3, а фиг.2г отображает соответствующую ему матрицу инцидентности. На фиг.2а и 2в кружками обозначены гипотетические модули, а цифры внутри модулей - их соответствующие номера. Числа над пунктирными линиями обозначают степени загрузки канала между смежными парами, цифры рядом с дугами означают их номера. Из фиг.2а видно, что канал между модулями 1-2 и 2-3 имеет наибольшую загрузку. Качество размещения улучшается при перестановке местами модулей 2 и 3 (фиг.2в). Максимальная степень загрузки канала для обоих пар при этом уменьшается до 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 устройства, а также дополнительно введенный блок 24 оценки степени загрузки каналов, содержащий генератор 14 импульсов, мультиплексор 15 выбора элемента, дешифратор 16 выбора элемента, дешифратор 17 выбора строки, элементы ИЛИ 18.1-18.m, триггеры 19.1-19.m, счетчики 20.1-20.m загрузки канала, счетчик 21 номера строки, счетчик 22 номера столбца, группу 23.1, 23.2,..., 23.m блоков элементов запрета, причем первый выход генератора 14 импульсов соединен с разрешающим входом дешифратора 16 выбора элемента, а второй выход генератора 14 импульсов подключен к счетному входу счетчика 22 номера столбца, выход переполнения которого соединен со счетным входом счетчика 21 номера строки и с входами сброса триггеров 19.1-19.m, а выход данных счетчика 22 номера столбца подключен к управляющему входу мультиплексора 15 выбора элемента и к управляющему входу дешифратора 16 выбора элемента, вход которого соединен с выходом мультиплексора 15 выбора элемента, входы которого подключены к прямым выходам соответствующих триггеров 19.1-19.m, S-входы которых соединены с выходами соответствующих элементов ИЛИ 18.1-18.m, входы которых соединены с соответствующими выходами группы 23.1-23.m блоков элементов запрета, управляющие входы которых подключены к соответствующим выходам дешифратора 17 выбора строки, вход которого соединен с выходом данных счетчика 21 номера строки и с установочным входом счетчика 22 номера столбца, выход переполнения счетчика 21 номера строки подключен к выходу 25 переполнения устройства, информационные входы группы 23.1-23.m блоков элементов запрета подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, вход 26 запуска устройства подключен к входу генератора 14 импульсов, информационные выходы счетчиков 20.1-20.m загрузки канала соединены с выходами 27.1-27.m загрузки канала устройства соответственно, входы счетчиков 20.1-20.m загрузки канала подключены к соответствующим выходам дешифратора 16 выбора элемента.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Элементы ИЛИ 18.1-18.m служат для объединения сигналов с выходов группы элементов 23.1-23.m запрета соответственно.

Триггеры 19.1-19.m необходимы для хранения информации о загрузке канала между соответствующими элементами матрицы 1.

Счетчики 20.1-20.m загрузки канала предназначены для накапливания информации о загрузке канала между соответствующими смежными модулями размещаемой схемы.

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

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

Группа 23.1-23.m элементов запрета предназначена для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 соответственно на элементы ИЛИ 18.1-18.m.

Блок 24 оценки степени загрузки каналов необходим для оценки размещения по критерию загрузки каналов между соседними модулями.

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

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

Выходы 27.1-27.m загрузки каналов устройства предназначены для выдачи ВУУ соответствующих кодов загрузки канала между смежными модулями для данного варианта размещения.

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

Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения, соответствующий матрице инцидентности схемы. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В счетчиках 20.1-20.m содержится нулевой код. Триггеры 19.1-19.m находятся в состоянии логического нуля. В счетчике 21 номера строки содержится код “00...01”, поэтому на первом выходе дешифратора 17 выбора строки присутствует единичный сигнал, который подается на управляющие входы блока 23.1 элементов запрета и обеспечивает прохождение на его выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. В счетчике 22 номера столбца содержатся нули.

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

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

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

Появление единичного потенциала на входе 26 запуска устройства запускает генератор 14 импульсов. В результате на втором выходе генератора 14 появляется импульс, а на первом выходе генератора он появится с задержкой в половину такта. Импульс со второго выхода генератора 14 импульсов поступает на счетный вход счетчика 22 и по переднему фронту увеличивает его содержимое на единицу. В результате там будет содержаться код “00...01”.

Сигналы с индикаторных выходов элементов первой строки матрицы 1 поступают на элементы ИЛИ 18.1-18.m, т.к. блок 23.1 элементов запрета открыт. Если на выходах элементов ИЛИ 18.1-18.m присутствуют единицы, то они поступают на соответствующие S-входы триггеров 19.1-19.m и устанавливают их в единичное состояние. К этому времени на выходе счетчика 22 уже присутствует код “00...01”, который поступает на управляющий вход мультиплексора 15 и дешифратор 16, разрешая прохождение сигнала с триггера 19.1. В случае если он находится в единичном состоянии, соответствующий сигнал поступает на вход дешифратора 16. При появлении на разрешающем входе этого дешифратора сигнала с первого выхода генератора 14 импульсов сигнал с выхода мультиплексора 15 проходит на счетный вход счетчика 20.1 загрузки канала и по заднему фронту увеличивает его на единицу. В результате в счетчике будет содержаться код “00...01”.

Новый импульс на втором выходе генератора 14 импульсов поступает на счетный вход счетчика 22 и по переднему фронту устанавливает в нем код двойки (“00...10”). Код “00...10” поступает на управляющие входы мультиплексора 15 и дешифратора 16. Появление импульса с первого выхода генератора 14 импульсов на разрешающих входах мультиплексора 15 и дешифратора 16 пропускает сигнал с выхода триггера 19.2 на счетный вход счетчика 20.2. В результате в нем будет установлен код “00...01”.

Так происходит до тех пор, пока на первом выходе счетчика 22 не появится сигнал переполнения. Этот сигнал поступает на счетный вход счетчика 21 номера строки и по переднему фронту увеличивает в нем код “00...10” и одновременно обнуляет все триггеры 19.1-19.m. Код “00...10” с выхода счетчика 21 поступает на вход дешифратора 17, и на втором его выходе появляется единичный сигнал. Этот сигнал обеспечивает прохождение сигналов с индикаторных выходов второй строки матрицы 1 через блок 23.2 элементов запрета на элементы ИЛИ 18.1-18.m. Одновременно код с выхода счетчика 21 поступает на установочный вход счетчика 22, устанавливая его начальное состояние в “00...10”.

Следующий тактовый импульс со второго выхода генератора 14 импульсов по переднему фронту увеличивает содержимое счетчика 22 до значения “00...011”. Код числа три с выхода счетчика 22 поступает на управляющие входы мультиплексора 15 и дешифратора 16. Сигналы с индикаторных выходов второй строки матрицы 1 проходят через соответствующие элементы запрета 23.2, через элементы ИЛИ 18.1-18.m и устанавливают триггеры 19.1-19.m, на входы которых поступили единичные импульсы, в единичное состояние.

При поступлении импульса с первого выхода генератора 14 импульсов на разрешающий вход дешифратора 16 сигнал с выхода триггера 19.3 поступает на вход счетчика 20.3 загрузки канала и увеличивает его на единицу по заднему фронту.

Так продолжается до тех пор, пока на выходе переполнения счетчика 21 номера строки не появится единичный импульс, свидетельствующий об окончании процесса оценки размещения по критерию максимальной загрузки канала между смежными модулями. В счетчиках 20.1-20.m к этому моменту появятся соответствующие значения загрузки для каждого модуля.

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

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

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