Элемент однородной среды

/О ЗОБ АНИ ТЕНИ Н АторСНО 11 льств ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ(7 1) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) А.Н.Мелихов, Л.С.Берштейн, Д.П.Калачев и В,А.Новиков (53) 681.3(088.8)(56) Авторское свидетельство СССР У 978139, кл. С 06 Р 7/00, 1980. (54) ЭЛЕМЕНТ ОДНОРОДНОЙ СРЕДЫ (57) Изобретение относится к облас- ти автоматики и вычислительной техники и предназначено для моделирова-, ния комбинаторных задач проектирова. ния радиоэлектронной аппаратуры и АСУ. Данное изобретение является усовершенствованием изобретенияпо а.с. В 978139.Цель изобретения - расширение функциональных возможностей элемента среды за счет обеспечения воэможности оценки текушего размещения при изоморфным преобразованиях. Для достижения поставленной цели в элемент однородной среды введен блок оценки текущего размещения.Элемент однородной среды работаетв двух основных режимах: режиме трассировки и режиме иэоморфных преобразований моделируемого объекта, Прирешении задач проектирования радиоэлектронной аппаратуры принципиальная схема представляется в виде матричного эквивалента графа или гиперграфа, описывающего схему, Эта матрица накладывается на однороднуюсреду, т.е. каждому элементу средыставится в соответствие элемент матрицы цепей. Изоморфные преобразования матрицы в однородной среде,т.е. перестановки строк и столбцов матрицы приводят к изменениюцелевой функции оптимизации, Оценкацелевой функции осуществляется позначениям сигналов на индикаторньжвыходах блоков оценки текущего размещения в столбцах (строках) одно"родной среды. При получении оптимального значения целевой функции преобразование матрицы заканчивается.2 ил 4 табл.Изобретение относится к цифровой вычислительной технике, предназначено для моделирования комбинаторных задач проектирования радиоэлектронной аппаратуры и АСУ и является усо вершенствованием изобретения по авт. св. У 978139,Целью изобретения является расширение функциональных воэможностей 10эа счет обеспечения возможности оценки текущего размещения при изоморфных преобразованиях,На фиг. 1 приведена функциональная схема предлагаемого элемента 5однородной среды; на фиг2 - фрагмент однородной среды,Элемент содержит блок 1 обработки входных сигналов, блок 2 запоминания признака конечной токи, блок 203 выходной логики, триггер 4 записитрасс, блок 5 передачи информации.,управляющий вход 6, информационныевходы 7 - 10, выходные элементы И-НЕ11-14 блока 3 выходной логики, информационные выходы 15 - 18 элемента, выходы 19 и 20 элемента, входы21 - 27 элемента, Блок 2 содержитриггер 28 и элементы И-НЕ 29 и 30.Блок 5 содержит элементы И 31, И-НЕ ЗО32 и 33, ИЛИ 34, дешифратор 35, триггер 36 промежуточной записи, элементыИ-ИЛИ 37-39, элементы И 40 и 41. Кроме того, в состав элемента однородной среды входит блок 42 оценки теку- З 5щего размещения, который содержитэлементы И 43 и 44, элемент ИЛИ-НЕ45, дополнительные информационныевходы 46 и 47, дополнительные информационные выходы 48 и 49, индикаторный выход 50.В блоке 2 хранится информация обэлемента моделируемой матрицы. Блок5 осуществляет связь соответствующихинформационных выходов соседних элементов с информационными входамиэлемента и триггером 28 блока 2 взависимости от сигналов управления.Блок 1 служит для обработки входныхинформационных сигналов. Блок 3 выходной логики служит для Формирования выходного информационного сигнала. Блок 42 служит для оценки текущего размещения.Элемент однородной среды для модулирования комбинаторных задачпроектирования работает в двух основных режимах; в режиме трассировки(построение кратчайших связывающих сетей) и режиме изоморфных преобразований моделируемого объекта.В режиме трассировки предложенный элемент однородной среды работает так же как и известный.Рассмотрим режим изоморфных преобразований, При решении задач проектирования радиоэлектронной аппаратуры принципиальная (Функциональная) схема представляется в виде матричного эквивалента графа или гиперграфа. При даннои нумерации строк и столбцов матрицы можно вычислить значение целевой Функции оптимизации. Если поменять местами строки и/или столбцы матрицы, то за счет изменения локальных свойств матрицы изменяется и значение целевой функции оптимизации. Таким образом, рещение (нахождение экстремума целевой функции) сводится к перестановке строк и/или столбцов матрицы, т.е, к ее изоморфиому преобразованию с оценкой текущего размещения. Эта циклическая перестановка заканчивается в момент получения оптимального значения целевой функции.Рассмотрим задачу линейного размещения графа или гиперграфа, являющуюся моделью задачи линейного размещения радиоэлектронных элементов, например микросхем. В этом случае элементу однородной среды взаимно-однозначно ставится в соответствие элемент матрицы цепей, в которой строки отмечаются элементами схемы, а столбцы - цепями, соединяющими эти элементы.Таким образом, однородная среда, содержащая и х ш, элементов, физически отображает матрицу цепей электрической схемы, содержащей и элементов и ш и соединяющих их цепей. На пересечении д-й строки и 1-го столбца ставится единица, если х-й элемент входит в 1-ю цепь, и ноль в противном случае.Длиной 1-и цепи называется разность между номерами самой нижней строки, в которой стоит единица в 1-м столбце, и номером самой верхней строки, в которой стоит единица в .1-м столбце (табл. 1). Каждое размещение характеризуется суммой длин входящих в него цепей. Номера столбцов соответствуют порядку размещения элементов в линейке. Обмен информацией, записанной в строках3с номерами К и 1 (перестановкаместами строк Е и 1), соответствует обмену местами К-го и 3-гоэлементов размещаемой линейки схемы.В результате обмена получаем матрицу, изоморфную данной, т,е. описывающую исходную электрическую схемупри другом порядке нумерации ееэлементов,Такой обмен приводит к применению 1 Осуммарной длины всех цепей и,следовательно, к изменению качества решения задачи размещения, В табл. 1приведена матрица исходного размещения элементов с указанием длин каждой цепи и .суммарной длины всех це,пей. В табл. 2 приведена матрица,эквивалентная исходной, полученнаяпутем перестановки первого и третьего элементов. Как видно иэ табл. 2 20это привело к увеличению суммарнойдлины цепей. Лучшее линейное размещение приведено в табл. 3. 1291957 Продолжение табл.2( ). ( (1) Элемен 12 3 4 5 6 7 1 1 1 1 1 Длинацепи 2 3 4 5 5 5 2 Общая длина 28 Таблица 1 25 Таблица 3 Элемент Элемент Цепь2 3 4 5 6 7 1 1 1 1 1 1 1 1 1 1 35 1 1. 1 1 1 1 1 1 1 1 1 1 1 1 5 Длинацепи Длина2 5 4 3 2 цепи 2 3 1 2 Э 2 145 3 5 Общая длина Длина 14 24 50 Для среды, состоящей из данныхэлементов, могут быть разработаны специальные алгоритмы, с помощью которьк приведенная задача н ряд других решаются значительно быстрее, 7 55 чем на универсальных вычислительныхмашинах, поскольку обмен информацией между строками осуществляется параллельно по строкам (или столбцам). Указанные изоморфные преобраТаблица 2 Цепь1 2 3 4 5 6 Элемент Э1 1 1 1 1 1Таблица 4 Элемент 11 Г 2 3 4 5 6 7 1 1 О 1 0 О О1 1 О 1О 1 зования являются основной процедурой при решении таких комбинаторнологических задач, как покрытие,компоновка, размещение и т.д. Однакосами алгоритмы покрытия, компоновки,размещения и составляющие как компоненты, такие как выбор переставляемыхподсчет значений целевых функций, сравнение и выбор максимальных значений. и т.д., не могут бытьреализованы в элементе однороднойсреды. Они реализуются в специальномустройстве, содержащем однороднуюсреду из предлагаемых элементов иряд специальных блоков.Работу элемента покажем на примере перестановки, приведенной втабл. 1 и 2.На входы .47 элементов верхнейстрокии входы 46 элементов нижнейстроки подаются единичные потенциалы, В режиме иэоморфных преобразований на вход .6 управления подаетсяединичный потенциал, а на вход 25 -нулевой. При этом из четырех разре:шенных в режиме трассировки направлений передачи сигнала возбужденияячейки разрешается два. В нашем примере разрешенными будем считать направления вдоль строк в сторону возрастания номеров столбцов. Это достигается подачей нулевого потенциалана входы элементов И-НЕ 11 и 12.Кроме того, запрещается прохождениесигналов с выхода элемента ИЛИ 34через элементы И-ИЛИ 37 и 38,Значения элементов матрицы записываются через входы 23 в триггеры 28элементов среды, В нашем примере(табл. 1) в первой строке эта записьпроизводится в элементы, находящиесяв первом, втором и четвертом столбцах, во второй строке - в первом,втором, пятом и седьмом столбцах ит.д,На входы 46 элементов среды нижней строки и входы 47 элементовсреды верхней строки поданы единичные потенциалы, В результате на индикаторных выходах 50 элементовсреды будут сигналы, представленныев табл. 4.Продолжение табл.4 Элемент цепь 2 3 4 5 6 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . О 1 1 1 1 1 ОО 1 О 1 1 1 О 3104 6 Длинацепи 3 5 2 5 4 3 2 20Рассмотрим подробнее формирование сигналов на индикаторных выходах на примере одного столбца, например первого. Единичный потенциал, 25 поданный на вход 47 верхнего элемента, не пройдет на выход элементаИ 44, поскольку на другом его входеприсутствует нулевой потенциал синверсного выхода триггера 28,так 30 как в нем записана " 1".Таким образом, на выходе 49 верхнего элемента среды будет нулевойпотенциал, который, поступая навход 47 следующего элемента среды,вызовет аналогичную реакцию и т.д.Единичный потенциал, поданный навход 46 нижнего элемента среды первого столбца, в совокупности с единичным потенциалом на другом входе 40 элемента И 43 (в триггере 28 нижнего элемента первого столбца записан ноль) сформируют единичный потенциал на выходе элемента И 43,благодаря которому на индикаторном 45 выходе 50 (выход элемента ИЛИ-НЕ45) будет нулевой потенциал.Единичный потенциал с выхода 48нижнего элемента среды, поступаяна вход 46 соседнего сверху элемента среды вместе с единичным потенциалом на инверсном выходе триггера28 (в пятой строке первого столбца записан ноль), также сформулирует нулевой потенциал на индикатор ном выходе 50 и единичный - на выходе 48. В четвертом элементе средыпервого столбца единичный потенциалс выхода 46 элемента среды черезэлемент И 43 не пройдет, поскольку7 12919 на инверсном выходе триггера 28 элемента среды будет присутствовать нулевой потенциал, так как в этом .элементе матрицы записана единица.Поэтому на индикаторных выходах четвертого, третьего, второго и первого элементов среды первого столбца будут установлены единичные потенциалы.Видно, что длина цепи определя ется количеством единиц в столбце матрицы (добавление константы к значению целевой функции не влияет на поиск экстремума).15Далее в нашем примере на вход26 всех элемвнтов среды, находящихся в первой и третьей строках, подается единичный потенциал. Сигналамис выхода дешифратора 35 запрещается 20прохождение сигнала с выхода элемента И-НЕ 32 через элемент И-ИЛИ38, с выхода элемента И-НЕ 33 черезэлемент И-ИЛИ 37. Это необходимодля того, чтобы информационный сигнал не проходил на выходе элементов среды, участвующих в обмене информацией. Кроме того, разрешаетсяпрохождение информации, записываемой в триггере 28, через элементы 30И-ИЛИ 38 и И-НЕ 14 на выход 18, атакже прохождение информации, пришедшей на вход 8 элемента среды,через элементы И-НЕ 32 и И-ИЛИ 39на входы триггера 36 предварительной записи.Таким образом, информация с выхода триггеров 28 элементов среды,находящихся в первой строке (табл. 1)проходит через элементы среды, находящиеся во второй строке, записывается в триггеры 36 промежуточнойзаписи элементов среды, находящиесяв третьей строке. В то же время информация с выходов триггеров 28 элементов среды, находящихся в третьейстроке, беспрепятственно проходитчерез элементы четвертой, пятой ишестой строк и записывается в триггеры 36 промежуточной записи элемен,тов среды, находящихся в первойстроке, т.е. при выполнении процедуры изоморфного преобразования в нашем примере выходы элементов средышестой строки соединены с входами 55элементов среды первой строки, находящихся в одноименных столбцах, авыходы элементов среды седьмого столб,ца соединены с входами элементов сре 57 8ды первого столбца, находящихся в одноименных строках.Вход 24 в режиме трассировки выполняет функцию ввода импульсов запуска, а в режиме изоморфных преобразований - функцию ввода импульсов записи. С приходом единичного импульса на вход 24 в триггер 28 записывается через элементы И 40 и 41 новое состояние, соответствующее записанной ранее в триггер 36 промежуточной записи. На этом обмен информацией между строками (перестановка двух строк, в матрице) заканчивается.При обмене информацией между двумя столбцами единичный потенциал подается на вход 27. При этом такжезапрещается прохождение сигнала свыхода элемента ИЛИ 34 через элементы И-ИЛИ 37 и 38. Информационныйсигнал приходит на вход 7 и черезэлементы И-НЕ 33 и И-ИЛИ 39 поступает на входы триггера 36 предварительной записи. С выхода триггера 28сигнал проходит через элементы И- . ИЛИ 37 и И-НЕ 13 и поступает на выход 17. В остальном элементы работают как и при обмене информациеймежду строками.В режиме изоморфного преобразования информационный сигнал на входы 9 и 10 не поступает, так как разрешены только два из четырех направлений распространения сигнала. Поскольку информационный сигнал не проходит через элементы среды, участвующие в обмене, то в среде можно осуществлять одновременную циклическую перестановку более чем одной строки или столбца. Например, одновременно можно переписать информацию из первой строки во вторую, из второй в третью, а из третьей в четвертую. Для этого единичный потенциал необходимо подать на вход 26 элементов среды, находящихся в первой, второй и треть. ей строках.На входы 26 и 27 элементов среды, не участвующих в обмене информацией (например элементы, находящиеся во второй, четвертой, пятой и шестой строках), подается нулевой потенциал. Единичный сигнал с выходадешифратора 35 разрешает прохождение сигнала с выходов элементовИ-НЕ 32 и 33 через элементы И-ИЛИ 37 и 38. Таким образом, сигналы, пришедшие на вход этих элементов среды, бескрепятственно проходятна выход. Нулевые потенциалы с выходов дешифратора 35 запрещают прохождение на выход элемента среды сигнала с выхода триггера 28, а также прохождение сигнала с входа 5 элемента среды на входы триггера 36 промежуточной записи, Память этих элементов среды не участвует в данном обмене.Поскольку вертикальный и горизонтальный каналы передачи информации через элементы среды, не участвующие в обмене, не пересекаются, то в среде из данных элементов может быть осуществлен обмен информа 5 цией между строками и между столбцами одновременно (обмен строки с столбцами и наоборот осуществлять ся не может). В элементах среды, находящихся на пересечении обмениваемых строк и столбцов, на всех выходах дешифратора 35 устанавливается нулевой потенциал, запрещающий прохождение сигнала через этот элемент среды как в горизонтальном, так и в вертикальном направлениях, а также запрещающий участие памяти этих элементов среды в данном обмене.Учитывая, что можно обмениваться как строками так и столбцами,. можно добавить в элемент среды еще один блок, аналогичный блоку оценки размещения, но соединение входов и вы ходов этих блоков произвести не в столбец как на фиг. 2, а в строку. Таким образом, наличие лвух блоковоценки размещения позволит оцениватьразмещение как по столбцам так и построкам.Формула изобретенияЭлемент однородной среды по авт. св. У 918139, отличающий,с я тем, что, с целью расширения функциональных возможностей за счет обеспечения врзможности оценки текущего размещения при изоморфных преобразованиях, в него введен блок оценки текущего размещения, содержащий элементы И и элемент ИЛИ-НЕ, причем первые входы первого и второго элементов И объединены и соединены с информационным входом блока оценки текущего размещения, который соединен с инверсным выходом триггера блока запоминания конечной точки, вторые входы первого и второго элементов И соединены с первым и вторым дополнительными информационными входами элемента среды, выход первого элемента И соединен с первым входом элемента ИЛИ-НЕ блока оценки текущего размещения и первым дополнительньпй выходом элемента среды,выход второго элемента И соединен со вторым дополнительным информационным выходом элемента среды и вторым входом элемента ИЛИ-НЕ блока оценки текущего размещения, выход которого соединен с индикаторным выходом элемента среды.1291957 А.федоровар Корректор Е.Сирохма СоставителТехред В. Редактор В.Даик каз 265 к и д. 4 шская на Л оизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 р Тираж 673 ВНИИПИ Государственног по делам изобретени 113035, москва, Ж, Подписнотета СССРкрытий