УСТРОЙСТВО ДЛЯ ОЦЕНКИ КАЧЕСТВА РАЗМЕЩЕНИЯ Российский патент 2001 года по МПК G06F17/00 G06F15/163 G06N1/00 

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

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

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

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

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

Исходная (размещаемая) схема представляется в виде соответствующего графа, заданного матрицей электрических цепей Строки матрицы А отмечаются номерами элементов схемы, а столбцы - номерами цепей, соединяющих эти элементы. На пересечении i-й строки и j-го столбца ставится единица (a_ij = 1), если i-й элемент входит в j-ю цепь, и ноль (a_ij=0) - в противном случае. Кроме того, вводится дополнительная матрица Элементы матрицы C получаются из матрицы A по следующей формуле:

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

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

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

Из фиг. 2а видно, что суммарное количество пересечений P=7. Это же значение получается при применении формулы (1) к матрицам А и С (фиг. 2б, 2в). Качество размещения можно улучшить, переставив местами первый и четвертый элементы (фиг. 2г - 2е). При этом суммарное количество пересечений P уменьшается до 2. Качество размещения также можно улучшить, переставив местами цепи 3 и 4 (фиг. 2ж - 2и). Суммарное количество пересечений P уменьшается до 5. Таким образом, появляется возможность уменьшения потенциального числа слоев печатной платы.

Устройство для оценки качества размещения (фиг. 1) содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блок 3 нахождения максимума, первый сумматор 4, блок 5 памяти, блоки 2.1 -2.n подсчета единиц, причем входы управления перестановкой столбцов матрицы 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 устройства, а также дополнительно введенный блок 34 оценки суммарного количества пересечений, содержащий генератор 14 импульсов, второй сумматор 15, первый дешифратор 16, второй дешифратор 17, одновибратор 18, первый элемент И 19, второй элемент И 20, блок 21 сравнения, первый счетчик 22 цепей, второй счетчик 23 цепей, первую группу элементов ИЛИ 24.1 - 24. m, вторую группу элементов ИЛИ 25.1 - 25.m, группу элементов И 26.1 - 26.m, счетчики 27.1 - 27.m числа пересечений, первую группу блоков 28.1, 28.2,..., 28. (n- 1) элементов запрета, вторую группу блоков 29.2, 29.3,..., 29.n элементов запрета, регистр 32 числа пересечений, причем вход генератора 14 импульсов является входом 30 запуска устройства, выход генератора 14 импульсов подключен к счетному входу счетчика 22 цепей, счетному входу счетчика 23 цепей и вторым входам элементов И 19 и 20 соответственно, первый выход блока 21 сравнения соединен с первым входом элемента И 20 и с входом разрешения счетчика 23 цепей, выход которого соединен с первым входом блока 21 сравнения и входом дешифратора 17, выходы с первого по (n-1)-й которого соединены с управляющими входами блоков 28.1 - 28.(n-1) элементов запрета соответственно, индикаторные выходы элементов k-й строки (k = 1, 2, ..., m) матрицы 1 элементов однородной среды с первого по (n-1)-й подключены к k-м информационным входам блоков 28.1-28.(n-1) элементов запрета соответственно, k-e выходы которых соединены с соответствующими входами элемента ИЛИ 24.k, выходы элементов ИЛИ 24.1 - 24.m подключены к первым входам элементов И 26.1 - 26.m соответственно, выходы которых подключены к счетным входам счетчиков 27.1 - 27. m числа пересечений соответственно, выходы которых подключены к соответствующим входам сумматора 15, выход которого подключен к информационному входу регистра 32 числа пересечений, вход синхронизации которого, а также выход 31 конца операции устройства и входы сброса счетчиков 27.1 - 27m числа пересечений подключены к выходу переполнения счетчика 22 цепей, выход регистра 32 числа пересечений соединен с выходом 33 числа пересечений устройства, второй выход блока 21 сравнения подключен к первому входу элемента И 19 и к входу разрешения счетчика 22 цепей, информационный выход которого подключен к второму входу блока 21 сравнения и к входу дешифратора 16, выходы с первого по (n-1)-й которого соединены с управляющими входами блоков 29.2 - 29.n элементов запрета соответственно, информационные выходы элементов l-го столбца (l=2, 3, ..., n) матрицы 1 элементов однородной среды с первого по m-й подключены к информационным входам блока 29.(l-1) элементов запрета с первого по m-й соответственно, выходы с первого по m-й которого соединены с (l-1)-ми входами элементов ИЛИ 25.1 - 25.m соответственно, выходы которых подключены к вторым входам элементов И 26.1 - 26.m соответственно, третьи входы которых соединены с выходом элемента И 20, выход элемента И 19 подключен к входу одновибратора 18, выход которого подключен к входу сброса счетчика 23 цепей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Назначение элементов введенного блока 34 оценки суммарного количества пересечений состоит в следующем.

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

Сумматор 15 предназначен для суммирования двоичных кодов с выходов счетчиков 27.1 - 27.m числа пересечений.

Дешифратор 16 обеспечивает выбор столбцов матрицы электрических цепей А и управляет прохождением соответствующих им значений через блоки 29.2 - 29.n элементов запрета.

Дешифратор 17 осуществляет выбор столбцов матрицы С и управляет прохождением соответствующих значений через блоки 28.1 - 28.(n-1) элементов запрета.

Одновибратор 18 предназначен для формирования импульса сброса счетчика 23.

Элементы И 19 и 20 необходимы для блокирования прохождения импульсов с генератора 14 импульсов на одновибратор 18 и третьи входы элементов И 26.1 - 26.m соответственно.

Блок 21 сравнения необходим для сравнения кодов, поступающих с выходов счетчиков 22 и 23 цепей соответственно.

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

Элементы ИЛИ 24.1 - 24.m необходимы для объединения сигналов, поступающих с первых m-х выходов блоков 28.1 - 28.(n-1) элементов запрета.

Элементы ИЛИ 25.1 - 25.m необходимы для объединения сигналов, поступающих с первых - m-х выходов блоков 29.2 - 29.n элементов запрета.

Элементы И 26.1 - 26.m служат для блокировки прохождения сигналов с выходов элементов ИЛИ 25.1 - 25.m на счетные входы счетчиков 27.1 - 27.m.

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

Блоки 28.1 - 28.(n-1) элементов запрета необходимы для блокировки поступления значений элементов с первого по (n-1)-й столбцов матрицы С на соответствующие входы элементов ИЛИ 24.1 - 24.m.

Блоки 29.2 - 29.n элементов запрета служат для блокировки поступления значений элементов со второго по n-й столбцов матрицы электрических цепей А на соответствующие входы элементов ИЛИ 25.1 - 25.m.

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

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

Регистр 32 числа пересечений предназначен для хранения кода суммарного количества пересечений проводников для текущего варианта размещения.

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

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

Первоначально в матрице 1 элементов однородной среды (фиг. 1) содержится вариант размещения, соответствующий исходной матрице электрических цепей размещаемой схемы (А). Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В регистре 32 содержится нулевой код. В счетчике 22 содержится код "0...01", поэтому на первом выходе дешифратора 16 сформирован единичный сигнал (выбран второй столбец матрицы А). Этот сигнал поступает па управляющие входы блока 29.2 элементов запрета и тем самым пропускает через него сигналы с информационных выходов элементов второго столбца матрицы 1 (эти сигналы отражают значения элементов а₁₂, а₂₂,..., а_m2). Указанные сигналы проходят через элементы ИЛИ 25.1 - 25.m на вторые входы элементов И 26.1 - 26. m соответственно. В счетчике 23 содержится код "0...00", поэтому на первом выходе дешифратора 17 сформирован единичный потенциал (выбран первый столбец матрицы С). Данный потенциал поступает на управляющие входы блока 28.1 элементов запрета и обеспечивает прохождение на его выходы сигналов с индикаторных выходов элементов первого столбца матрицы 1 (эти сигналы отражают значения элементов с₁₁, c₂₁,..., c_m1). Далее указанные сигналы через элементы ИЛИ 24.1 - 24.m проходят на первые входы элементов И 26.1 - 26.m соответственно. Па первом выходе блока 21 сравнения присутствует единичный потенциал ("не равно"), который поступает на первый вход элемента И 20 и разрешающий вход счетчика 23. На втором выходе блока 21 сравнения присутствует нулевой потенциал, который блокирует элемент И 19 и счетчик 22.

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

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

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

Первый импульс с генератора 14 импульсов поступает на вторые входы элементов И 19 и 20 и счетные входы счетчиков 22 и 23. Так как на входе разрешения счетчика 22 и первом входе элемента И 19 находится нулевой сигнал, воздействие данного импульса на счетчик 22 и элемент 19 не вызывает изменений. В то же время импульс проходит через элемент И 20 (на его первом входе установлена единица). Далее рассматриваемый импульс поступает на третьи входы элементов И 26.1 - 26.m. Если на первом и втором входах элемента И 26.1 (26.2 - 26.m) установлены единицы (что соответствует наличию пересечения - в формуле (1) слагаемое а_i2 c_i1 = 1), то импульс проходит на счетчик 27.1 (27.2 - 27.m) и задним фронтом увеличивает его содержимое на единицу. Если же на первом или втором (или обоих) входе(ах) элемента И 26.1 (26.2 - 26.m) установлен нуль, импульс не проходит на счетчик 27.1 (27.2 - 27.m) и последний, соответственно, остается в исходном состоянии.

Этот же импульс с генератора 14 по заднему фронту увеличивает содержимое счетчика 23 на единицу и оно становится равным "0...01" (осуществляется выбор второго столбца матрицы C). Код "0...01" с выхода счетчика 23 подается па первый вход блока 21 сравнения, на втором входе которого присутствует код "0...01" с информационного выхода счетчика 22. В результате на втором выходе блока 21 появляется единичный потенциал ("равно"), а на первом выходе потенциал с единичного меняется на нулевой, что запрещает увеличение значения счетчика 23 при появлении следующего импульса и блокирует элемент И 20. В то же время единичный потенциал со второго выхода блока 21 открывает элемент И 19 и разрешает работу счетчика 22.

Очередной импульс с генератора 14 импульсов поступает на вторые входы элементов И 19 и 20 и на счетные входы счетчиков 22 и 23. Однако теперь этот импульс воздействует не на счетчик 23, как описано выше, а на счетчик 22. По заднему фронту импульса счетчик 22 увеличивает свое значение и на его выходе появляется код "0...010" (в формуле (1) это означает увеличение предела j на 1 для внутренней суммы). Этот код поступает на второй вход блока 21, а также на вход дешифратора 16, на втором выходе которого в результате появляется единичный сигнал. Данный сигнал поступает па управляющие входы блока 29.3 элементов запрета и разрешает прохождение через него сигналов с информационных выходов элементов третьего столбца матрицы 1 (указанные сигналы отражают значения элементов а₁₃, а₂₃,..., a_m3). Эти сигналы поступают через соответствующие элементы ИЛИ 25.1 - 25.m на вторые входы элементов И 26.1 - 26.m соответственно.

Одновременно тот же самый импульс проходит через открытый элемент И 19 и задним фронтом воздействует на одновибратор 18. В результате на выходе одновибратора 18 появляется импульс, который, поступая на вход сброса счетчика 23. сбрасывает его в нулевое состояние. Таким образом, на выходе счетчика 23 появляется код "0...00". Этот код поступает на первый вход блока 21 и вход дешифратора 17. На первом выходе блока 21 восстанавливается единичный потенциал, а на втором - единичный потенциал меняется на нулевой, что снова запрещает прохождение импульсов через элемент И 19 и работу счетчика 22. В то же самое время единичный потенциал с первого выхода блока 21 поступает на первый вход элемента И 20 и вновь разрешает прохождение импульсов через этот элемент. Одновременно код "0. . .00", поступивший на вход дешифратора 17, формирует единичный сигнал на его первом выходе. Этот сигнал поступает на управляющие входы блока 28.1 элементов запрета и разрешает прохождение через него сигналов с индикаторных выходов элементов первого столбца матрицы 1 (вновь происходит выбор первого столбца матрицы С).

Аналогично описанному выше следующий импульс с генератора 14 поступает на счетный вход счетчика 23 и по заднему фронту увеличивает его значение до "0. . .01" (в формуле (1) выбирается слагаемое a_i3 c_i1). Импульс с генератора 14 импульсов также проходит через элемент И 20 и далее передается через открытые элементы из числа элементов И 26.1 - 26.m. С выходов элементов 26.1 - 26. m импульс обеспечивает переключение соответствующих счетчиков 27.1 - 27. m в следующее состояние (в указанных счетчиках продолжают накапливаться суммы числа пересечений для соответствующих им строк). Описанный процесс повторяется до тех пор, пока на втором выходе блока 21 снова не появится единичный потенциал ("равно"). После появления указанного потенциала аналогично описанному выше происходит сброс счетчика 23 в нулевое состояние и увеличение содержимого счетчика 22 на единицу (осуществляется выбор четвертого столбца матрицы А). Далее счетчик 23 и дешифратор 17 обеспечивают последовательный выбор первого - третьего столбцов матрицы C, в счетчиках 27.1 - 27.m накапливаются суммы количества пересечений проводников для соответствующих строк и т. д. Описанный процесс повторяется до тех пор, пока не произойдет переполнение счетчика 22, означающее завершение перебора столбцов матрицы А.

После переполнения счетчика 22 в счетчиках 27.1 - 27.m будут зафиксированы коды количества пересечений проводников для соответствующих строк (элементов), а на информационном входе регистра 32 - значение суммарного количества пересечений P с выхода сумматора 15 (сумматор 15 вычисляет внешнюю сумму в формуле (1)). При переполнении счетчик 22 вырабатывает импульс переполнения и возвращается в исходное состояние "0...01". Данный импульс, поступая на вход синхронизации регистра 32, передним фронтом заносит в него значение суммарного количества пересечений проводников P с выхода сумматора 15. Одновременно этот же импульс передается через выход 31 устройства на ВУУ и индицирует окончание работы блока 34, а также сбрасывает счетчики 27.1 - 27. m в нулевое состояние. Значение из регистра 32 через выход 33 устройства поступает на ВУУ. ВУУ, приняв указанное значение, сопоставляет его с ранее полученным наилучшим значением. В зависимости от результата сопоставления ВУУ может либо осуществить следующую перестановку строк (столбцов) с сохранением предыдущего варианта размещения (или без него), либо остановить генератор 14 импульсов. В последнем случае работа устройства считается завершенной.

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

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

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