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

 

Изобретение относится к вычислительной технике и может быть использовано для конструирования радиоэлектронной и электро - вычислительной аппаратуры. Целью изобретения является повышение быстродействия. Устройство содержит генератор 1 тактовых импульсов, распределитель 2 импульсов, элемент ЗАПРЕТ 3, блок 4 формирования перестановок, распределитель 5 импульсов, элемент ИЛИ 6, триггер 7, группу 8 элементов И, блок 9 памяти, схему 10 сравнения, буферные регистры 11, 12, регистры 13, 14, элемент ИЛИ 15, элемент 16 задержки, формирователь 17 прямоугольных импульсов, элементы И 18, 19, элементы 20, 21 задержки, коммутаторы 22 - 26, блок 27 умножения, элемент И 28, элемент ИЛИли 29, блок 30 памяти топологии графа, шифратор 31, дешифратор 32, вычитатель 33, сумматор 34, блок 35 регистров, триггер 36, элементы И 37 - 40, элементы ИЛИ 41, 42. 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-26, блок 27 умножения, элементы И 28, элемент ИЛИ 29, блок 30 памяти топологии графа, шифратор 31, дешифратор 32, вычитатель 33, сумматор 34, блок 35 регистров, триггер 36, элементы И 37-40, элемент ИЛИ 41, 42. Принцип работы устройства состоит в следующем. Оптимизируемым критерием является суммарная длина связей мультиграфов, минимизация которых осуществляется на основе факторизации исходного графа по строкам и столбцам. Исходный граф размещения факторизуется относительно массивов строк и столбцов, т.е. вершины Х_i.Х_j, входящие в строку (столбец), заменяются одной вершиной Х_ij, причем ребра, соединяющие Х_i и Х_j между собой, исключаются, а ребра, идущие из X_i,X_j к другим вершинам, приписываются X_ij. Элементы схемы располагаются начальным размещением в определенных позициях плоскости размещения, причем число позиций в строке (столбце) P , где n общее число позиций (элементов) размещения. Далее исходный граф G, имеющий Х вершин, разобьем на р классов и отнесем к ним вершины, лежащие в строках сетки размещения. В каждом классе выделим внутренние и соединительные ребра. Теперь строим новый граф, в котором вершинами являются классы Х_i. Получим линейно расположенный мультиграф G_p, содержащий только соединительные ребра. Аналогично проводим операцию разбиения на р классов, вершины каждого из которых принадлежат столбцам области размещения. Получим мультиграф G_p. Для этих мультиграфов нетрудно определить перестановку вершины на основе полного перебора вариантов. После получения оптимального размещения мультиграфа производится переход к графу G. Значения величин матрицы заносятся в блок отображения графа перед началом работы. В блок регистров заносятся двоичные коды позиций: в первый регистр блока заносятся двоичный код первой позиции 10.0, во второй двоичный код второй позиции 0100.0 и т.д. Величина d_p(i)(j) определяется с помощью вычитателя как разность двоичных кодов позиций р(i) и р(j). Накопление сумм длин расстояний L как для переставления строк, так и столбцов осуществляется с помощью блока умножения, коммутатора и сумматора. Перебор всех возможных размещений элементов в позициях осуществляется с помощью блока 4, при этом каждая перестановка соответствует определенному размещению элементов в позиции. Так, например, перестановка 3 1 2 соответствует перемещению первой строки (столбца) элементов во вторую позицию, второй строки (столбца) в третью позицию, третьей строки (столбца) в первую позицию. Последовательность появления единичных сигналов на выходах блока 4 определяется каждой новой перестановкой. Так перестановка 3 1 2 соответствует появлению первого тактового импульса на втором входе, второго на третьем и третьего на первом выходе. Смена перестановок осуществляется подачей сигнала на вход блока 4 с выхода распределителя. С помощью распределителей осуществляется последовательный периодический перебор всех групп вершин и проверка наличия связей между первой строкой (столбцом) элементов и всеми остальными, второй строки (столбца) со всеми остальными и т.д. Синхронно с этим блок 4 для каждой группы вершин определяет позицию в соответствии с сформированной перестановкой. Подготовка устройства к работе состоит в подаче на вход единичного сигнала, по которому в распределители 2, 5 единица записывается соответственно в нулевой и первый разряды. Блок 4 устанавливается в исходное состояние, соответствующее первой перестановке, в блок регистров записываются двоичные коды номеров позиций, триггеры 7, 36 устанавливаются соответственно в единичное и нулевое состояние, регистры 11, 12, 13, 14 в нулевые, в блок памяти топологии графа заносится матрица смежности исходного графа. Динамику работы устройства рассмотрим на примере размещения 9-ти элементов с того момента, когда сигнал с выхода распределителя установит перестановку 3 1 2 (ей предшествовали перестановки 1, 2, 3; 2 1 3; 2 3 1; 3 2 1). Начальное размещение приведено на фиг. 2 и имеет матрицу смежности Rr где r_ij число ребер между i и j вершиной. R Первый тактовый импульс с выхода генератора 1 передвинет "1" на первый выход распределителя 2 и, поступив через элемент ЗАПРЕТ 3 на вход блока 4, возбудит единичный сигнал на его втором выходе. С этого момента начнется подсчет длины связей между первой строкой элементов и всеми остальными. Двоичный код 010 с выхода блока 35 через коммутатор 23 (верхний выход) в качестве уменьшаемого по управляющему сигналу, поступающему на вход вычитателя 33 и управляющий вход сумматора 34 с первого выхода распределителя 2, перепишется в вычитатель 33, на нижнем элементе И группы 8 произойдет совпадение сигналов, и он поступит через элемент ИЛИ 15 и элемент 16 задержки на нулевой вход триггера 7, вследствие этого коммутатор 23 подключит регистры 35 к нижним входам вычитателя 33. Второй тактовый импульс передвинет "1" на второй выход распределителя 2 и возбудит сигнал на 3-м выходе блока 4, который подключит через коммутатор 23 третий регистр блока 35 к вычитателю 33, при этом на управляющем входе коммутатора 22 появится код (начиная сверху вниз по схеме фиг. 1) 11000010, что соответствует подключению к шифратору 31 следующих элементов матрицы смежности: r₁₄= 0, r₁₅=0, r₁₆=0, r₂₄=1, r₂₅=0, r₂₆=0, r₃₄=0, r₃₅=0, r₃₆=0 и на выходе шифратора 31 зафиксируется код, соответствующий числу связей между элементами первой и второй строками, на соответствующем выходе дешифратора 32 появляется сигнал, который поступает на вход блока 27 умножения в качестве множителя, а множимое как разность между первой и второй позицией поступает с вычитателя 33, кроме того, импульс через элемент ИЛИ 29 поступает на счетный вход триггера 36, устанавливая его в единичное состояние, и через элемент И 28 на управляющий вход вычитателя 33 и вход коммутатора 24, в результате содержимое вычитателя, помноженное на множитель, поступающий с дешифратора 32 с блока 27, поступает в сумматор 34. Задержанным импульсом с выхода формирователя 17, поступающим на управляющий вход сумматора 34, содержимое блока умножения суммируется с содержимым сумматора 34. Импульс со второго выхода формирователя 17 через элемент И 37 поступает на управляющий вход регистра 13, в результате содержимое сумматора 34 записывается в регистр 13, а импульс с третьего выхода формирователя 17 через элемент И 40 поступает на управляющий вход коммутатора 24, подключая выход регистра 14 к сумматору, по сигналу с элемента ИЛИ 41 осуществляется перезапись содержимого регистра 14 в сумматор 34. Задержанный импульс с элемента 20 поступает на вход триггера 36, устанавливая его в нулевое состояние, и на управляющий вход коммутатора 22, в результате чего формируется код 11000001, что соответствует подключению к шифратору 31 следующих элементов матрицы смежности: r₁₂=1, r₁₅=0, r₁₈=0, r₄₂= 1, r₄₅=1, r₄₆=0, r₇₂=0, r₇₅=0, r₇₈=0 и на выходе шифратора сформируется код, соответствующий числу связей между первым и вторым столбцами поля размещения (см. фиг. 2). На выходе дешифратора 32 возбуждается сигнал, поступающий в блок 27 умножения, указывая количество связей (множитель) между первым и вторым столбцами, а с вычитателя 33 множимое, указывающее расстояние между первой и третьей позицией. Сигнал с выхода элемента ИЛИ 29 через элемент И 28 поступает на управляющий вход коммутатора 24, подключая результат (произведение) с блока 27 умножения к сумматору 34, и сигналом с первого выхода формирователя 17 происходит сложение содержимого сумматора 34 (регистра 14) с результатом перемножения. Сигнал со второго выхода формирователя 17 через элемент И 38 поступает на управляющий вход регистра 14, и содержимое сумматора 34 переписывается в регистр 14. Таким образом, в регистре 14 происходит накопление суммарной длины при размещении столбцов элементов поля размещения. Аналогично в регистре 18 происходит накопление суммарной длины при размещении строк элементов поля размещения. Подсчет суммарных длин заканчивается сигналом с выхода распределителя 5, поступающего в блок 4 формирования перестановок, устанавливая его в исходное состояние, и блокирующего с помощью элемента 3 прохождение сигналов с генератора на вход блока 4. Сигнал с выхода распределителя поступает на вход коммутаторов 25, 26, в результате на схему 10 сравнения поступает содержимое регистров 13 и 11, и по импульсу с элемента ИЛИ 42 осуществляется сравнение. Если содержимое регистра 11 больше содержимого регистра 13, на выходе схемы 10 формируется сигнал 1, поступающий через элемент ИЛИ 18 на вход регистра 11, осуществляя перезапись содержимого регистра 13 в регистр 11, тем самым в регистре 13 запоминается суммарная длина для лучшего варианта размещения строк элементов поля размещения. Задержанным импульсом с элемента 21, поступающим на соответствующие входы коммутаторов 25, 26, аналогично происходит сравнение содержимого регистров 14, 12 и в случае, если содержимое регистра 14 меньше содержимого регистра 12, на выходе схемы 10 сравнения по сигналу с элемента ИЛИ 42 появляется сигнал, поступающий через элемент 19 на вход регистра 12, разрешающий запись содержимого регистра 14 в регистр 12. Таким образом, в регистре 12 хранится минимальная суммарная длина размещения элементов поля размещения по столбцам. Перестановки, при которых получается минимальная суммарная длина при размещении строк (столбцов), запоминаются в блоке 9 по сигналам с элементов И 18 строки и 19 (столбцы).

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

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

РИСУНКИ

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