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

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

Реферат

 

Изобретение относится к вычислительной технике. Целью изобретения является расширение функциональных возможностей за счет обеспечения размещения элементов схем, отображаемых мультиграфами. Устройство содержит генератор 1 тактовых импульсов, распределитель 2 импульсов, элемент 3 запрета, блок 4 формирования перестановок, распределитель 5 импульсов, элемент ИЛИ 6, триггер 7, группу 8 элементов ИЛИ, группу 9 элементов И, блок 10 памяти, схему 11 сравнения, буферный регистр 12, элемент ИЛИ 13, элемент 14 задержки, коммутатор 15, элемент И 16, элемент ИЛИ 17, блок 18 памяти топологии графа, шифратор 19, дешифратор 20, блок 21 умножения, вычитатель 22, элемент 23 задержки, накапливающий сумматор 24, регистры 25, вход 26 установки исходного состояния. 2 ил.

Изобретение относится к вычислительной технике и может быть использовано для автоматизированного конструирования радиоэлектронной и электронно-вычислительной аппаратуры. Целью изобретения является расширение функциональных возможностей за счет обеспечения размещения элементов схем, отображаемых мультиграфами. На фиг. 1 приведена схема устройства; на фиг. 2 схема блока умножения. Устройство содержит генератор 1 тактовых импульсов, распределитель 2 импульсов, элемент 3 запрета, блок 4 формирования перестановок, распределитель 5 импульсов, элемент ИЛИ 6, триггер 7, группу 8 элементов ИЛИ, группу 9 элементов И, блок 10 памяти, схему 11 сравнения, буферный регистр 12, элемент ИЛИ 13, элемент 14 задержки, коммутатор 15, элемент И 16, элемент ИЛИ 17, блок 18 памяти топологии графа, шифратор 19, дешифратор 20, блок 21 умножения, вычитатель 22, элемент 23 задержки, накапливающий сумматор 24, регистры 25 группы, вход 26 установки исходного состояния, информационный вход 27 устройства, группу 28 элементов ИЛИ, группу 29 элементов И, группу 30 элементов ИЛИ, элемент ИЛИ 31, элемент 32 задержки, элемент ИЛИ 33, элементы 34, 35 задержки. Принцип работы устройства состоит в следующем. Оптимизируемым критерием качества L является суммарная длина связи между элементами схемы при их расположении в заранее определенных фиксированных позициях Р монтажной плоскости. Формализовано суммарная длина связей определяется из выражения где Cij элемент матрицы связности С, равный числу ребер, инцидентных i-й и j-й вершинам графа и равен "0", если вершины не смежны; dP(i) Р(j)- элемент матрицы расстояний D, равный числу шагов координатной сетки между Р(i) и P(j) позициями при ij и dP(i)P(j)=0 при i=j; n множество элементов схемы. Значения величин Cij матрицы смежности формируются на выходах блока 18, в который перед началом работы подачей соответствующих кодoв на входы 27 заносится топология исходного графа, отображающего заданную схему. Входы блока 18, соединенные с выходами элементов ИЛИ группы 8, соответствуют вершинам графа, а выходы ребрам. В регистры 25 заносятся двоичные коды позиции: в первый регистр (верхний по схеме) записывается двоичный код первой позиции - 10.0, во второй двоичный код второй пoзиции 010.0 и т.д. Величина dP(i)P(j) определяется с помощью вычитателя 22 как разность двоичных кодов позиции P(i) и P(j). Накопление же суммы длин расстояния осуществляется с помощью блока 21 и сумматора 24. Перебор всех возможных размещений элементов в позициях осуществляется с помощью блока 4. При этом каждая перестановка соответствует определенному размещению элементов в позиции. Так в перестановке "3 1 2" соответствует помещение первого элемента схемы во вторую позицию, второго элемента в третью и третьего в первую. Единичный сигнал в каждый тактовый момент времени появляется только на одном выходе блока 4. Последовательность же появления единичных сигналов на всех его выходах определяется каждой новой перестановкой. Так, перестановке "3 1 2" соответствует появление первого тактового импульса на втором выходе (нумерация выходов блока 4 сверху вниз), второго на третьем и третьего на первом выходе. Смена перестановок осуществляется подачей сигнала на вход блока 4 с выхода распределителя 5, когда проанализируется смежность каждой вершины с каждой и произойдет накопление суммарной взвешенной длины связей при данной перестановке (размещении). С помощью распределителей 2 и 5 осуществляется последовательный периодический перебор всех вершин и проверка смежности первой вершины со всеми остальными, второй со всеми остальными и т.д. Синхронно с этим блок 4 для каждой вершины определяет позицию в соответствии со сформированной перестановкой. Подготовка устройства к работе состоит в подаче на вход 26 единичного сигнала, по которому в распределители 2 и 5 единица записывается соответственно в нулевой и первый разряды. Блок 4 устанавливается в исходное состояние, соответствующее первой перестановке, в регистры 25 записываются двоичные коды номеров позиций (в первый регистр код 100, во второй 010, в третий 011), триггер 7 устанавливается в единичное состояние, буферный регистр 12 и регистры сумматора 24 устанавливаются в нулевое состояние. По входам 27 в блок 18 устанавливается топология исходного графа. Динамику работы устройства рассмотрим на примере размещения трех элементов с того момента, когда сигнал с выхода распределителя 5 установит в блоке 4 перестановку "3 1 2" (ей предшествовали перестановки "1 2 З", "2 1 З", "2 3 1" и "3 2 1"). После этого первый тактовый импульс с выхода генератора 1 передвинет "1" на первый верхний выход распределителя 2, и, поступая через элемент 3 запрета на вход блока 4, возбудит единичный сигнал на его втором выходе. С этого момента начнется подсчет длины связей между первой вершиной графа и всеми остальными. Поэтому двоичный код 010 с выходов второго регистра группы 25 через коммутатор 15 (верхний его выход) в качестве уменьшаемого по сигналу, поступающему на вход вычитателя 22 и сумматора 24 с первого выхода распределителя 2, перепишется в вычитатель 22, а в сумматор 24 из вычитателя 22 перепишется нулевой код. На первом (верхнем) элементе И группы 9 произойдет совпадение единичных сигналов и он поступит через элемент ИЛИ 13 и элемент 14 задержки на нулевой вход триггера 7. Вследствие этого коммутатор 15 подключит регистры 25 ко входам (нижним по схеме фиг. 1) вычитателя 22. Второй тактовый импульс передвинет "1" на второй выход распределителя 2 и возбудит единичный сигнал на третьем выходе блока 4, который подключит через коммутатор 15 третий регистр 25 к вычитателю 22. При этом единичный сигнал поступит на первый вход блока 18 с выхода распределителя 5 через первый (верхний) элемент ИЛИ группы 8 и на второй вход блока 18 с выхода распределителя 2 через второй элемент ИЛИ группы 8 (т.е. на первую и вторую вершины исходного графа). Если первая и вторая вершины графа смежны, то на первом выходе блока 18 появится единичный сигнал, который через элемент ИЛИ 17 и элемент И 16 поступит на вход вычитателя 22. Поэтому из кода 010 номера второй позиции вычтется по модулю код 011 номера третьей позиции и по сигналу с элемента 23 задержки результат вычитания поступит на сумматор 24. При этом, если первая и вторая вершины связаны одним ребром, то на выходе шифратора 19 зафиксируется двоичный код числа "1", на выходе дешифратора 20 единичный сигнал появится на первом выходе, который поступит на первый вход первого элемента ИЛИ группы 30 (фиг. 2), Поэтому к сумматору 24 через элементы И группы 29 (верхней на фиг. 2) и соответствующие элементы ИЛИ 28 подключаются выходы вычитателя 22 без сдвига. По сигналу с элемента 23 задержки произойдет сложение двоичного кода "1" с содержимым сумматора 24. Если первая и вторая вершины связаны двумя ребрами, сигналы о которых могут появиться на любых двух выходах блока 18, то на выходе шифратора 19 зафиксируется двоичный код числа "2", на выходе дешифратора 20 возбудится второй выход, сигнал с этого выхода поступит на вход второго элемента ИЛИ группы 30, а с него на элементы И 29. Поэтому к сумматору 24 подключатся выходы вычитателя 22 со сдвигом на один разряд. Это означает, что содержимое вычитателя 22 удваивается и по сигналу с элемента 23 задержки оно складывается с содержимым сумматора 24. В случае, если первая и вторая вершины связаны тремя ребрами, то сложение содержимых вычитателя 22 и сумматора 24 будет происходить дважды. Сначала по сигналу с третьего выхода дешифратора 20, поступающего на вход второго элемента ИЛИ группы 30, через элементы И 29, но уже без сдвига. Поэтому произойдет второе сложение содержимых вычитателя 22 и сумматора 24. В результате описанных действий происходит умножение на "3" длины связи, полученной в вычитателе 22, и сложение этого результата с содержимым сумматора 24. Аналогичные операции происходят при связях первой и второй вершин четырьмя, пятью, шестью, семью и восемью ребрами путем подключения выходов вычитателя 22 через соответствующую группу 29 элементов И к входам сумматора 24. Третий тактовый импульс передвинет "1" на третий выход распределителя 2 и возбудит первый выход блока 4. Поэтому, если первая и третья вершины смежны, то на соответствующем выходе блока 18 появится сигнал, который через элементы ИЛИ 17 поступит на вычитатель 22. Тогда к последнему подключится первый регистр 25 и из кода 010 вычтется код 100. Результат вычитания по сигналу с элемента 23 задержки аналогично описанному выше сложится с содержимым сумматора 24. Четвертый тактовый импульс на один из выходов блока 4 не возбуждает, а только подготавливает его к следующему циклу формирования перестановки "3 1 2", но появляется на выходе распределителя 2. Поэтому в распределителе 5 единица продвинется на его второй выход, а триггер 7 перейдет в единичное состояние. Содержимое сумматора 24 при этом не меняется. С пятого тактового импульса начнется новый цикл формирования перестановки "3 1 2". Но подсчет длины связей будет производится только от второй вершины до третьей, так как длина связи от первой вершины до второй была уже определена в предыдущем цикле. Этим самым исключается двойной учет одних и тех же связей. А реализуется это тем, что после первого цикла просмотра смежности первой вершины со всеми остальными перевод триггера 7 в нулевое состояние осуществляется не первым же тактовым импульсом в новом цикле (т.е. пятым при сквозном счете), а вторым, когда произойдет совпадение единичных сигналов на втором элементе И группы 9. Поэтому на протяжении двух тактов коммутатором 15 к входам вычитателя 22 будут подключены регистры 25 и код последнего из подключаемых регистров (в данном случае 011 третьего регистра, соответствующий помещению второй вершины в третью позицию) зафиксируется в вычитателе 22 в качестве уменьшаемого. Только после этого, задержанным на элементе 14 вторым тактовым импульсом триггер 7 переведется в нулевое состояние и коммутатором 15 регистры 25 будут подключены к входам вычитателя 22. Аналогично четвертому тактовому импульсу по восьмому импульсу блок 4 подготовится к формированию нового цикла перестановки "3 1 2", а "1" перейдет на третий выход распределителя 5. Следующие девятый, десятый и одиннадцатый тактовые импульсы подсчет длины связей производить не будут, так как все они были уже подсчитаны в предыдущих двух циклах и просуммированы сумматором 24. По двенадцатому тактовому импульсу "1 "появится на распределителях 2 и 5. Это вызовет перевод триггера 7 в единичное состояние, подготовку блока 4 к формированию новой перестановки "3 2 1" и сравнению кодов в сумматоре 24 и в буферном регистре 12. Предположим, что код в сумматоре 24 меньше кода в регистре 12 (это означает, что последнее размещение элементов в позиции дает меньшую суммарную длину связей, поэтому его нужно запомнить), тогда на выходе схемы 11 сравнения появляется сигнал, по которому содержимое сумматора 24 переписывается в буферный регистр 12, а соответствующая перестановка переписывается из блока 4 в блок 10. После этого начнется процесс формирования нового размещения и анализ суммарной длины связей между вершинами. Если новое размещение будет иметь меньшую суммарную длину связей, то этот вариант размещения запомнится в блоке 10. После перебора всех перестановок и анализа соответствующих размещений на управляющем выходе блока 4 появится сигнал окончания решения задачи. При этом в блоке 10 зафиксируется оптимальный вариант размещения элементов на плоскости.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2

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

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

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