Патент на изобретение №2177172

(54) УСТРОЙСТВО ДЛЯ ОЦЕНКИ СТЕПЕНИ ОПТИМАЛЬНОСТИ РАЗМЕЩЕНИЯ

(57) Реферат:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сущность предлагаемого критерия поясняется фиг. 2. Здесь на фиг. 2а представлен вариант гипотетического исходного размещения, а фиг. 2б задает матрицу электрических цепей для исходного размещения элементов. Фиг. 2в описывает вариант размещения после перестановки элементов 3 и 4, а фиг. 2г отображает соответствующую ему матрицу. На фиг. 2а и 2в черными кружками обозначены выводы гипотетических радиоэлектронных элементов. Числа над пунктирными линиями обозначают степени загрузки канала между парами смежных элементов. Из фиг. 2а и 2б видно, что канал между элементами 3 и 4 имеет наибольшую загрузку. Качество размещения можно улучшить, переставив местами третий и четвертый элементы (фиг. 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.1 -17.m, элементы И 18.1 – 18.m, второй блок 19 нахождения максимума, регистр 20 загрузки каналов, элементы 22.11 – 22. m1, 22.12 – 22. m2, . .., 22.1n – 22.mn запрета, элемент 23 задержки, счетчики 24.1 – 24.m загрузки каналов, причем выход генератора 14 импульсов подключен к счетному входу счетчика 15 столбцов и к входу элемента 23 задержки, информационный выход счетчика 15 столбцов подключен к входу дешифратора 16 выбора столбца, выходы с первого по n-й которого подключены к управляющим входам элементов 22,11-22.m1, 22.12 22.m2,…, 22.1n 22.mn запрета соответственно, информационные входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды соответственно, выходы элементов 22.11 – 22-1n, 22.21 – 22.2n,…, 22.m1 – 22.mn запрета подключены к входам элементов ИЛИ 17.1, 17.2, …, 17.m с первого по n-й соответственно, выходы элементов ИЛИ 17.1 – 17. m подключены к первым входам элементов И 18.1 – 18.m соответственно, вторые входы которых подключены к выходу элемента 23 задержки, выходы элементов И 18.1 – 18.m подключены к счетным входам счетчиков 24.1 – 24. m загрузки каналов соответственно, выходы которых подключены к соответствующим входам блока 19 нахождения максимума, выход которого подключен к информационному входу регистра 20 загрузки каналов, вход синхронизации которого подключен к выходу переполнения счетчика 15 столбцов, который также подключен к входам сброса счетчиков 24.1 – 24.m загрузки каналов, вход генератора импульсов 14 соединен с входом запуска 25 устройства, выход регистра 20 загрузки каналов подключен к выходу 26 загрузки каналов устройства.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Счетчик 15 столбцов служит для организации последовательного перебора столбцов матрицы электрических цепей.

Дешифратор 16 выбора столбца предназначен для выбора столбца матрицы электрических цепей.

Элементы ИЛИ 17.1 -17.m предназначены для объединения сигналов с выходов элементов 22.11 – 22.1n,…, 22.m1 – 22.mn запрета соответственно.

Элементы И 18.1 – 18.m предназначены для блокирования прохождения импульсов с выхода элемента 23 задержки на счетные входы счетчиков 24.1 – 24.m соответственно.

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

Группы 22.11 – 22.m1, 22.12 – 22.m2,…, 22.n1 – 22.mn элементов запрета предназначены для блокировки поступления значений элементов с первого по n-й столбцов матрицы электрических цепей соответственно на элементы ИЛИ 17.1 – 17.m.

Элемент 23 задержки предназначен для задержки прохождения импульса с генератора 14 импульсов на вторые входы элементов И 18.1 – 18.m на время, достаточное для формирования значений элементов выбранного столбца матрицы электрических цепей на выходах элементов ИЛИ 17.1 – 17.m после переключения счетчика 15.

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

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

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

Работа блоков 1, 2, 3 (19), 4 и 5 более подробно описана в прототипе.

Рассмотрим работу предлагаемого устройства.

Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения, соответствующий матрице электрических цепей размещаемой схемы. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В регистре 20 загрузки каналов содержится нулевой код. В счетчике 15 столбцов и в счетчиках 24.1 – 24.m загрузки каналов также содержатся нули, поэтому на выходах дешифратора 16 выбора столбца находятся нулевые сигналы, блокирующие элементы 22.11 – 22. mn запрета, а на выходе блока 19 нахождения максимума присутствует нулевой код.

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

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

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

Первый импульс с генератора 14 поступает на счетный вход счетчика 15 столбцов и на вход элемента 23 задержки. В результате содержимое счетчика 15 увеличивается на единицу и на выходе счетчика 15 образуется код “0…01”. Данный код подается на вход дешифратора 16 выбора столбца и формирует единичный сигнал на его первом выходе. Полученный единичный сигнал подается на управляющие входы элементов 22.11 – 22.m1 запрета и обеспечивает прохождение на их выходы сигналов с индикаторных выходов элементов первого столбца матрицы 1. Далее указанные сигналы проходят через элементы ИЛИ 17.1 – 17.m и поступают на соответствующие элементы И 18.1 – 18.m. В случае если на первый вход элемента И 18.1 (18.2 – 18.m) поступила единица, этот элемент открывается и пропускает импульс с выхода элемента 23 задержки. Далее рассматриваемый импульс воздействует на счетный вход счетчика 24.1 (24.2 – 24.m) и задним фронтом инициирует увеличение его содержимого на единицу. Таким образом, в счетчике 24.1 (24.2 -24.m) фиксируется код “0…01”. Если же на первом входе элемента И 18.1 (18.2 – 18.m) установлен нуль, импульс с элемента 23 задержки не проходит на счетчик 24.1 (24.2 – 24.m) и последний, соответственно, остается в исходном состоянии.

Следующий импульс с генератора 14 импульсов также поступает на вход элемента 23 задержки и счетный вход счетчика 15 столбцов. Содержимое счетчика 15 увеличивается на единицу, что обуславливает появление единичного сигнала на следующем выходе дешифратора 16. Аналогично описанному сигналы с индикаторных выходов выбранного (в данном случае второго) столбца проходят через элементы 22.12 – 22.m2 запрета и элементы ИЛИ 17.1 – 17.m на соответствующие элементы И 18.1 – 18.m. Импульс с элемента 23 задержки проходит через те элементы И 18.1 – 18.m, которые оказываются открыты и обеспечивает переключение соответствующих счетчиков 24.1 – 24.m в следующее состояние. Тем самым обеспечивается последовательное накопление информации о загрузке канала между соответствующими смежными элементами.

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

После переполнения счетчика 15 в счетчиках 24.1 – 24.m загрузки каналов будут значения загрузки каналов между соответствующими смежными элементами, а на информационном входе регистра 20 – значение максимальной загрузки канала между смежными элементами с выхода блока 19. При переполнении счетчик 15 вырабатывает импульс переполнения и возвращается в исходное (нулевое) состояние. Данный импульс сбрасывает счетчики 24.1 – 24.m и, поступая на вход синхронизации регистра 20, передним фронтом заносит в него значение максимальной загрузки канала с выхода блока 19. Далее это значение через выход 26 поступает на ВУУ. Если полученное значение окажется лучше предыдущего, ВУУ выдает сигнал на сохранение текущего варианта размещения и осуществляет новую перестановку, после чего работа устройства повторяется снова.

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

Формула изобретения

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

РИСУНКИ

MM4A Досрочное прекращение действия патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе

Дата прекращения действия патента: 25.05.2002

Номер и год публикации бюллетеня: 32-2003

Извещение опубликовано: 20.11.2003