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

 

Изобретение относится к облас - ти автоматики и вычислительной техники и предназначено для моделирова-, ния комбинаторных задач проектирования радиоэлектронной аппаратуры и АСУ. Данное изобретение является усовершенствованием изобретения по а.с.. № 978139.Цель изобретения - расширение функциональных возможностей элемента среды за счет обеспечения возможности оценки текущего размещения при изоморфных преобразованиях . Для достижения поставленной цели в элемент однородной среды введен блок оценки текущего размещения. Элемент однородной среды работает в двух основных режимах: режиме трассировки и режиме изоморфных преобразований моделируемого объекта-. При решении задач проектирования радиоэлектронной аппаратуры принципиальная схема представляется в виде матричного эквивалента графа или гиперграфа , описывающего схему. Эта матрица накладывается на однородную среду, т.е. каждому элементу среды ставится в соответствие элемент матрицы цепей. Изоморфные преобразования матрицы в однородной среде, т.е. перестановки строк и столбцов матрицы приводят к изменению целевой функции оптимизации. Оценка целевой функции осуществляется по значениям сигналов на индикаторных выходах блоков оцейки текущего размещения в столбцах (строках) однородной среды. При получении оптимального значения целевой функции преобразование матрицы заканчивается. 2 ил.,4 табл. (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК. (51) 4 С 06 F 7/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 978139 (21) 3827461/24-24 (22) 19.12.84 (46) 23.02.87. Бюл. g. 7 (7 1) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) А.Н.Мелихов, Л.С.Берштейн, Д.П.Калачев и В.А.Новиков (53) 681.3(088.8) (56) Авторское свидетельство СССР

Р 978139, кл. С 06 F 7/00, 1980. (54) ЭЛЕМЕНТ ОДНОРОДНОЙ СРЕДЫ (57) Изобретение относится к облас" ти автоматики и вычислительной техники и предназначено для моделирова-, ния комбинаторных задач проектирова. ния радиоэлектронной аппаратуры и

АСУ. Данное изобретение является усовершенствованием изобретения по а.с. к" 978139.Цель изобретения— расширение функциональных возможностей элемента среды за счет обеспечения воэможности оценки текушего размещения при изоморфным преобразованиях. Для достижения поставленной цели в элемент однородной среды вве„„SU„, 1291957 A 2 ден блок оценки текущего размещения.

Элемент однородной среды работает в двух основных режимах: режиме трассировки и режиме иэоморфных преобразований моделируемого объекта. При решении задач проектирования радиоэлектронной аппаратуры принципиальная схема представляется в виде матричного эквивалента графа или гиперграфа, описывающего схему, Эта матрица накладывается на однородную среду, т.е. каждому элементу среды ставится в соответствие элемент матрицы цепей. Изоморфные преобразования матрицы в однородной среде, т.е. перестановки строк и столбцов матрицы приводят к изменению целевой функции оптимизации, Оценка целевой функции осуществляется по значениям сигналов на индикаторньж выходах блоков оценки текущего размещения в столбцах (строках) однородной среды. При получении оптимального значения целевой функции преобразование матрицы заканчивается.

2 ил.,4 табл.

1291957

Изобретение относится к цифровой вычислительной технике, предназначено для моделирования комбинаторных задач проектирования радиоэлектронной аппаратуры и АСУ и является усо- 5 вершенствованием изобретения по авт. св. У 978139.

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

На фиг. 1 приведена функциональная схема предлагаемого элемента 15 однородной среды; на фиг ° 2 — фрагмент однородной среды.

Элемент содержит блок 1 обработки входных сигналов, блок 2 запоминания признака конечной токи, блок 20

3 выходной логики, триггер 4 записи трасс, блок 5 передачи информации., управляющий вход 6, информационные входы 7 — 10, выходные элементы И-НЕ

11-14 блока 3 выходной логики, информационные выходы 15 — 18 элемента, выходы 19 и 20 элемента, входы

21 — 27 элемента. Блок 2 содержит риггер 28 и элементы И-НЕ 29 и 30.

Блок 5 содержит элементы И 31, И-НЕ 30

32 и 33, ИЛИ 34, дешифратор 35, триггер 36 промежуточной записи, элементы

И-ИЛИ 37-39, элементы И 40 и 41. Кроме того, в состав элемента однородной среды входит блок 42 оценки теку- З5 щего размещения, который содержит элементы И 43 и 44, элемент ИЛИ-НЕ

45, дополнительные информационные . входы 46 и 47, дополнительные информационные выходы 48 и 49, индикатор- 40 ный выход 50.

В блоке 2 хранится информация об элемента моделируемой матрицы. Блок

5 осуществляет связь соответствующих информационных выходов соседних эле- 45 ментов с информационными входами элемента и триггером 28 блока 2 в зависимости от сигналов управления.

Блок 1 служит для обработки входных информационных сигналов. Блок 3 вы- 50 ходной логики служит для формирования выходного информационного сигнала. Блок 42 служит для оценки текущего размещения.

Элемент однородной среды для модулирования комбинаторных задач проектирования работает в двух основных режимах; в режиме трассировки (построение кратчайших связывающих сетей) и режиме изоморфных преобразований моделируемого объекта.

В режиме трассировки предложенный элемент однородной среды работает так же как и известный.

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

Эта циклическая перестановка заканчивается в момент получения оптимального значения целевой функции.

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

В этом случае элементу однородной среды взаимно-однозначно ставится в соответствие элемент матрицы. цепей, в которой строки отмечаются элементами схемы, а столбцы — цепями, соединяющими эти элементы.Таким образом, однородная среда, содержащая n x m, элементов, физически отображает матрицу цепей электрической схемы, содержащей и элементов и m и соединяющих их цепей. На пересечении i-й строки и

j-го столбца ставится единица, если

i-й элемент входит в j-ю цепь, и ноль в противном случае. длиной j-и цепи называется разность между номерами самой нижней строки, в которой стоит единица в

j-м столбце, и номером самой верхней строки, в которой стоит единица в

j-м столбце (табл. 1). Каждое размещение характеризуется суммой длин входящих в него цепей. Номера столбцов соответствуют порядку размещения элементов в линейке. Обмен информацией, записанной в строках

3 с номерами k u f (перестановка местами строк Е и 8), соответствует обмену местами k-ro и 3-ro элементов размещаемой линейки схемы.

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

Такой обмен приводит к применению 10 суммарной длины всех цепей и,следовательно, к изменению качества решения задачи размещения, В табл. 1 приведена матрица исходного размещения элементов с указанием длин каж- 15 дой цепи и .суммарной длины всех це,пей. В табл. 2 приведена матрица, эквивалентная исходной, полученная путем перестановки первого и третьего элементов. Как видно иэ табл. 2 20 это привело к увеличению суммарной длины цепей. Лучшее линейное размещение приведено в табл. 3.

1291957

Продолжение табл.2

Элемен1

1 1

1 1 1

Длина цепи

Общая длина

Таблица1 25

Таблица3

Элемент

Элемент

Цепь

2 3 4 5 6 7

f I

1 1 1

1 1

1 1

1 1

1 1. 1

1 1 1

1 1 1 1 1

1 1 1

Длина цепи

Длина

2 5 4 3 2 цепи

3 5

Общая длина

Длина 14

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

Элемент

3! 1 1

1 1

Цепь

1 2 3 4 5 6 ()((1) 1 2 3 4 5 6 7

2 3 4 5 5 5 2

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

Работу элемента покажем на примере перестановки, приведенной в табл. 1 и 2.

На входы .47 элементов верхней строки и входы 46 элементов нижней строки подаются единичные потенциалы. В режиме иэоморфных преобразований на вход .6 управления подается единичный потенциал, а на вход 25— нулевой. При этом из четырех разре:шенных в режиме трассировки направлений передачи сигнала возбуждения ячейки разрешается два. В нашем примере .разрешенными будем считать направления вдоль строк в сторону возрастания номеров столбцов. Это достигается подачей нулевого потенциала на входы элементов И-НЕ 11 и 12.Кроме того, запрещается прохождение сигналов с выхода элемента ИЛИ 34 через элементы И-ИЛИ 37 и 38.

Значения элементов матрицы записываются через входы 23 в триггеры 28 элементов среды, В нашем примере (табл. 1) в первой строке эта запись производится в элементы, находящиеся в первом, втором и.четвертом столбцах, во второй строке — в первом, втором, пятом и седьмом столбцах и т.д,На входы 46 элементов среды нижней строки и входы 47 элементов среды верхней строки поданы единичные потенциалы. В результате на индикаторных выходах 50 элементов среды будут сигналы, представленные в табл. 4.

Таблица4

Элемент (15(I Г

2 3 4 5 6

1 1 0 1 0 0 0

1 1 0 1 1 0 1

Продолжение табл.4

Элемент цепь

2 3 4 5 6 7

1 1 1 1 1 1 1

1 1 1 1 1 1 1 . 0 1 1 1 1 1 0

0 1 О 1 1 1 0

Длина цепи 3 5 2 5 4 3 2

Рассмотрим подробнее формирование сигналов на индикаторных выходах на примере одного столбца, например первого. Единичный потенциал, 25 поданный на вход 47 верхнего элемента, не пройдет на выход элемента

И 44, поскольку на другом его входе присутствует нулевой потенциал с инверсного выхода триггера 28,так

30 как в нем записана " 1".

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

Единичный потенциал, поданный на вход 46 нижнего элемента среды первого столбца, в совокупности с единичным потенциалом на другом входе

40 элемента И 43 (в триггере 28 нижнего элемента первого столбца записан ноль) сформируют единичный потенциал на выходе элемента И 43, благодаря которому на индикаторном

45 выходе 50 (выход элемента ИЛИ-НЕ

45) будет нулевой потенциал.

Единичный потенциал с выхода 48 нижнего элемента среды, поступая на вход 46 соседнего сверху элемента среды вместе с единичным потенциалом на инверсном выходе триггера

28 (в пятой строке первого столбца записан ноль), также сформулирует нулевой потенциал на индикатор55 ном выходе 50 и единичный — на выходе 48. В четвертом элементе среды первого столбца единичный потенциал с выхода 46 элемента среды через элемент И 43 не пройдет, поскольку

7 12919 на инверсном выходе триггера 28 элемента среды будет присутствовать нулевой потенциал, так как в этом .элементе матрицы записана единица.

Поэтому на индикаторных выходах четвертого, третьего, второго и первого элементов среды первого столбца будут установлены единичные потенциалы.

Видно, что длина цепи определя- f0 ется количеством единиц в столбце матрицы (добавление константы к значению целевой функции не влияет на поиск экстремума).

Далее в нашем примере на вход

26 всех элемвнтов среды, находящихся в первой и третьей строках, подается единичный потенциал. Сигналами с выхода дешифратора 35 запрещается 20 прохождение сигнала с выхода элемента И-НЕ 32 через элемент И-ИЛИ

38, с выхода элемента И-НЕ 33 через элемент И-ИЛИ 37. Это необходимо для того, чтобы информационный сигнал не проходил на выходе элементов среды, участвующих в обмене информацией. Кроме того, разрешается прохождение информации, записываемой в триггере 28, через элементы 30

И-ИЛИ 38 и И-НЕ 14 на выход 18, а также прохождение информации, пришедшей на вход 8 элемента среды, через элементы И-НЕ 32 и И-ИЛИ 39 на входы триггера 36 предварительной записи.

Таким образом, информация с выхода триггеров 28 элементов среды, находящихся в первой строке (табл. 1) проходит через элементы среды, нахо- 40 дящиеся во второй строке, записывается в триггеры 36 промежуточной записи элементов среды, находящиеся в третьей строке. В то же время информация с выходов триггеров 28 эле- 45 ментов среды, находящихся в третьей строке, беспрепятственно проходит через элементы четвертой, пятой и шестой строк и записывается в триггеры 36 промежуточной записи элемен- 50 ,тов среды, находящихся в первой строке, т.е. при выполнении процедуры изоморфного преобразования в нашем примере выходы элементов среды шестой строки соединены с входами элементов среды первой строки, находящихся в одноименных столбцах, а выходы элементов среды седьмого столб,ца соединены с входами элементов сре57 8 ды первого столбца, находящихся в одноименных строках.

Вход 24 в режиме трассировки выполняет функцию ввода импульсов запуска, а в режиме изоморфных преобразований — функцию ввода импульсов записи. С приходом единичного импульса на вход 24 в триггер 28 записывается через элементы И 40 и 41 новое состояние, соответствующее записанной ранее в триггер 36 промежуточной записи. На этом обмен информацией между строками (перестановка двух строк, в матрице) заканчивается.

При обмене информацией между двумя столбцами единичный потенциал подается на вход 27. При этом также запрещается прохождение сигнала с выхода элемента ИЛИ 34 через элементы И-ИЛИ 37 и 38. Информационный сигнал приходит на вход 7 и через элементы И-НЕ 33 и И-ИЛИ 39 поступает на входы триггера 36 предварительной записи. С выхода триггера 28 сигнал проходит через элементы И- .

ИЛИ 37 и И-HE 13 и поступает на выход 17. В остальном элементы работают как и при обмене информацией между строками.

В режиме изоморфного преобразования информационный сигнал на входы

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

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

И-НЕ 32 и 33 через элементы И-ИЛИ

37 и 38. Таким образом, сигналы, пришедшие на вход этих элементов среды, бескрепятственно проходят

12919 >7 на выход. Нулевые потенциалы с выходов дешифратора 35 запрещают прохождение на выход элемента среды сигнала с выхода триггера 28, а также прохождение сигнала с входа 5 элемента среды на входы триггера

36 промежуточной записи. Память этих элементов среды не участвует в данном обмене.

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

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

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

Таким образом, наличие двух блоков оценки размещения позволит оценивать размещение как по столбцам так и по строкам.

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

Элемент однородной среды по авт. св. !!> 978139, о т л и ч а ю щ и й,с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности оценки текущего размещения при изоморфных преобразованиях, в него введен блок оценки текущего размещения, содержащий элементы И и элемент ИЛИ-НЕ, причем первые входы первого и второго элементов И объединены и соединены с информационным входом блока оценки текущего размещения, который соединен с инверсным выходом триггера блока запоминания конечной точки, вторые входы первого и второго элементов И соединены с первым и вторым дополнительными информационными входами элемента среды, выход первого элемента И соединен с первым входом элемента ИЛИ-НЕ блока оценки текущего размещения и первым дополнительный выходом элемента среды,выход второго элемента И соединен со вторым дополнительным информационным выходом элемента среды и вторым входом элемента ИЛИ-НЕ блока оценки текущего размещения, выход которого соединен с индикаторным выходом элемента среды.

1291957

1291957

Составитель А.Федоров

Техред В.Кадар Корректор E.ÑHðoõìÿí

Редактор В.Данко

Заказ 265/47 Тираж 673 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Л оизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 р