Устройство для оценки размещения элементов Советский патент 1988 года по МПК G06F15/173 

со о со

4 CD

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

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

На фиг. 1 изображена функционалъ- ная схема предлагаемого устройства; на фиг. 2 - одна из возможных реализаций блока подсчета ед1шиц; на фиг. 3 - одна из возможных реализаций блока нахождения максимума о

Устройство содержит матрицу 1 элементов однородной среды, состоящую из элементов однородной среды, блоки 2 подсчета единиц, блок 3 нахождения максимума, сумматор 4, блок 5 памя- ти, вход 6 записи исходного гиперграфа, вход 7 управления перестановкой столбцов, вход 8 управления перестановкой строк, вход 9 управления записью в блок памяти, выходы 10 и 11 оценки текущего размещения, информационный выход 2 и вход 13 установки

Соединение элементов в матрицу элементов однородной среды приведено в прототипе.

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

Можно составить таблицу (табл.1), отобра:-;яющую все происходящие в сети преобразования.

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

г

ю

J5 20

25 ЗО

эс

Q 45 0

5

На фиг. 3 изображено устройство, орие}1тированное на операцию поиска максиму 1а, представляющее из себя двумерную однородную структуру размером NxM. Для поиска максимума используется алгоритм поразрядного сравнения всех признаков:

1-и шаг. Просматривается содержимое информационных входов элементов левого (1-го) столбца, т.е. старшие разряды всех N чисел. Если все эти разряды содержат О,, то на сле- шаге просматриваются вторые разряды всех N чисел. Если же в первом столбце есть 1, то на втором шаге просматриваются только те числа, которые имели единицы в первом разряде.

j-й шаг. Просматривается содержимое только в тех строках, которые бьти вьщелены на j 1 шаге. Логика работы та же, что и на 1-ом шаге. После подачи граничных сигналов Z0 1, и XQ 0, по окончании переходных процессов сигналы Z на правой границе матрицы устанавливаются в тех строках, на входы которых поступили максимальные числа, а на нижней границе - само это число.

Устройство предназначено для решения задач оценки размещения элементов. Схема представляется в виде матричного эквивалента графа или гиперграфа, описьшающего схему. При данной нумерации строк матрицы можно вычислить значение целевой ции оптш 1изации. Если поменять местами строки, то за счет изменения локальных свойств матрицы изменяется и значение целевой функции оптимизации. Таким образом, решение.; сводится к перестановке строк матрицы, т.е к ее изоморфному преобразованию с оценкой текущего размещения Эта циклическая перестановка заканчивается в момент получения оптимального значения целевой ф 1кции или по истечении лимита времени. Строки матрицы отмечаются элементами схемы, а столбцы - цепями, coeдшiяющими эти элементы. Таким образом, однородная среда, содержащая N х m элементов, физически отображает матрицу цепей, состоящую из N элементов и m соединяющих их цепей. На пересечении i-й . строки и j-го столбца ставится единица, если i-й эле :- еп Г входит в j-ю цепь. Г Hoj fb - Б npoTJ-шнок случае.

3

Длиной j-й цепи называется ра:1нооть между номерами самой н -1жией строки, в которой стоит единица в j-ом столбце, и номером самой верхней строки, в которой стоит единица в j-ом столбце .

Устройство работает следующим образом.

На вход 6 записи поступают данные по сигналу 1. Иа входе 13 происходит запись информации в элементы однородной среды. На вход 9 поступа

В соответствии с любым рациональным алгоритмом выбираются строки, которые необходимо переставить и выдается сигнал на обмен строк. В нашем примере выбраны строки 1 и 3. Затем производится оценка, (как бьию описано выше) до тех пор, пока не будет найдено решение, удовлетворяю- щре некоторым- критериям, либо пока

на решение задачи Формул

изобретения

ет сигнал Запись и информация из триггеров з«апоминания признака конеч- is будет исчерпано время, отведенное ной точки переписьюается в блок 5 памяти. Для нашего примера в однородную среду бьши записаны данные, приведенные в табл.2 в графе Состояния элемента однородной -среды. На индикаторных выходах элементов после окончания переходньсх процессов устанавливаются единицы, если элементы расположены между двумя другими элементами в триггерах заг1оми1-1ания конечной точки, в которых содер5 атся единицы или в триггерах запоминания

20

Устройство для оценки размещения элементов, содержащее матрицу из п строк и m столбцов элементов однород ной среды, входы управления перестановки столбцов матрицы элемен /ов однородной среды соединены с входом

25 управления перестановкой столбцов

устройства, входы управления переста новки строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устко 1ечной точки самого элемента содержится единица, в противйом случае установится О, Для нашего примера состо яние индикаторных выходов отражено в соответствующих графах, табл.2- 4. Информация с индикаторных выходов элементов каждого столбца поступает

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

В соответствии с любым рациональным алгоритмом выбираются строки, которые необходимо переставить и выдается сигнал на обмен строк. В нашем примере выбраны строки 1 и 3. Затем производится оценка, (как бьию описано выше) до тех пор, пока не будет найдено решение, удовлетворяю- щре некоторым- критериям, либо пока

будет исчерпано время, отведенное

на решение задачи Формул

изобретения

будет исчерпано время, отведенное

будет исчерпано время, отведенное

Устройство для оценки размещения элементов, содержащее матрицу из п строк и m столбцов элементов однородной среды, входы управления перестановки столбцов матрицы элемен /ов однородной среды соединены с входом

управления перестановкой столбцов

устройства, входы управления перестановки строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройс ва, входы установки матрицы однородных элементов соединены с входом начальной установки устройства, информационный вход матрицы элементов однородной среды соедушен с вхо

Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании РЭА. Для расширения функциональных возможностей, а именно обеспечения возможности оценки текущего размещения по двум критериям: суммарная длина ребер и максимальная длина ребра, в устройство дополнительно введены блоки 2 подсчета единиц, блок 3 нахождения максимума, блок 5 памяти и сумматор 4. 3 ил, 4 табл„

в блок лодсчета единиц, соответству- 5 ° записи исходного гиперграфа данному столбцу. Блок подсчета единиц на выходе выдает двоичное ЧИСЛО, равное количеству поступавших на его входы единиц. Для нашего примера - это графа Количество единиц в соответствующих таблицах. Полученное число поступает на -входы, соответствующие данному блоку подсчета единиц, сумматора и нахождения максимума. Б сумматоре проис- - ходит суммирование всех двоичных чисел поступивших на входы, а в блоке нахождения максимума отыскивается максимальное число из них,

I

Полученные оценки поступают на выходы устройства, откуда - на устройство управления.. Для нашего примера - это графы Сумма и Максимум, Устройство управления сравнивает полученные значения целевой функции с предыдущим наилучшим значением и в случае улучшения выдает сигнал Запись.на вход управроиства, отличающеес я тем, что, с целью расширения функциональных возможностей путем обеспечения возможности оценки текущего раз4Q мещения при изоморфных преобразованиях по двум критериям - суммарной длины ребер и максимальной длины ребра и запоминания наилучшего размещения эле аентов, в него введены

g щ блоков лодсчета единиц, блок на- .хождения максимума, сумматор, блок памяти, управляющий вход которого соединен с входом управления памятного устройства.1-е индикаторные выgQ ходь матрицы элементов однородной среды (i 1, m) соединены с входом i-ro блока подсчета единиц, выход которого соединен с i-ым информационным входом блока нахождения максимуgg ма и входом i-ro слагаемого сумматора, выходы которых соединены с пер- . вым и вторым выходами оценки текущего размещения соответственно, j-e информационные выходы матрицы элероиства, отличающеес я тем, что, с целью расширения функциональных возможностей путем обеспечения возможности оценки текущего размещения при изоморфных преобразованиях по двум критериям - суммарной длины ребер и максимальной длины ребра и запоминания наилучшего размещения эле аентов, в него введены

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

Т а б л и ц а 1

Сигнал на вход памяти при оценке по сумме

по максимуму Обмен

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

Т а б л и ц а 2

О О 1 с 3

Количество единиц

Сумма Максимум

Сигнал на вход памяти при оценке

по сумме

по максимум Обмен

.Номер элемента

ТаблицаЗ

6

31

6

О

О

4 с 3

Таблица4

1430949

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

tfiuf.Z

. I li

IL Ml Ml

ТГ ТГ IT

рагЗ