Устройство поиска нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче информации

Устройство поиска нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче информации

Иллюстрации

Показать все

Реферат

Изобретение относится к области вычислительной техники и предназначено для моделирования задач при проектировании вычислительных систем (ВС).

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 1291957 СССР кл. G06F 7/00, опубл. 23.02.87, БИ №7).

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

Наиболее близким к предлагаемому устройству по технической сущности является устройство для оценки размещения элементов, содержащее матрицу элементов однородной среды, состоящую из элементов однородной среды, блоки подсчета единиц, блок нахождения максимума, сумматор, блок памяти, вход записи исходного гиперграфа, вход управления перестановкой столбцов, вход управления перестановкой строк, вход управления записью в блок памяти, выходы оценки текущего размещения, информационный выход и вход установки (а.с. 1410949 СССР, кл. G06F 7/00, 15/20, опубл. 15.10.88, БИ №38).

Недостатком указанного устройства является узкая область применения, обусловленная отсутствием средств для поиска нижней оценки размещения в полносвязных матричных системах (МС) при двунаправленной передаче данных по критерию минимизации интенсивности взаимодействия процессов и данных.

Технической задачей изобретения является расширение области применения устройства за счет введения средств для поиска нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче данных по критерию минимизации интенсивности взаимодействия процессов и данных.

Техническая задача решается тем, что в устройство поиска нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче данных, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, первый сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, …, n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен с j-м входом блока нахождения максимума и j-m входом первого сумматора, выходы которых соединены с выходом максимальной длины ребра устройства и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок поиска нижней оценки, содержащий генератор импульсов, первый, второй и третий мультиплексоры выбора элемента, дешифратор выбора строки, первый, второй, третий, четвертый, пятый и шестой дешифраторы инцидентной вершины, первый, второй и третий дешифраторы фиксируемой дуги, счетчик строк, счетчик столбцов, первый, второй и третий счетчик фиксируемой дуги, первый, второй, третий, четвертый, пятый и шестой счетчики инцидентной вершины, первый и второй триггеры режима, дешифратор фиксации дуги, группа из m триггеров, второй сумматор, группа из m блоков элементов запрета, матрица из (i,j) (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных дуг, матрица из (i,j) (1=1, 2, …, m, j=1, 2, …, n) элементов ИЛИ, первая матрица из строк (i=1, 2, …, m) и столбцов (j=1, 2, …, n), вторая матрица из строк (i=1, 2, …, m) и столбцов (j=1, 2, …, n), третья матрица из строк (i=1, 2, …, m) и столбцов (j=1, 2, …, n), четвертая матрица из строк (i=1, 2, …, m) и столбцов (j=1, 2, …, n), пятая матрица из строк (i=1, 2, …, m) и столбцов (j=1, 2, …, n), шестая матрица из строк (i=1, 2, …, m) и столбцов (j=1, 2, …, n), седьмая матрица из строк (i=1, 2, …, m) и столбцов (j=1, 2, …, n), восьмая матрица из строк (i=1, 2, …, m) и столбцов (j=1, 2, …, n) элементов И, элемент ИЛИ, первый и второй инверторы, первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой, девятый и десятый элементы И, группа из m элементов ИЛИ, причем вход запуска устройства соединен с генератором импульсов, выход которого соединен с первым входом третьего элемента И, второй вход которого подключен к прямому выходу второго триггера, выход третьего элемента И подключен ко второму входу четвертого элемента И, к первому входу второго элемента И и ко второму входу первого элемента И, к первому входу четвертого элемента И подключен прямой выход генератора, причем выход четвертого элемента И подключен ко входу элемента ИЛИ, выход которого подсоединен к первому входу первого элемента ИЛИ и счетному входу третьего счетчика, выход переполнения которого подключен к счетным входам пятого и шестого счетчиков инцидентной вершины, выход третьего счетчика подключен ко входу третьего дешифратора фиксируемой дуги, выходы с 1-го по m-й которого подключены к соответствующим первым входам с 5-го по 10-й элемента И, ко вторым входам с 6-го по 10-й элементов И подсоединен выход третьего инвертора, ко вторым входам с 5-го по 7-й элементов И подсоединен выход переполнения счетчика инцидентной вершины, который также подсоединен ко входу третьего инвертора, выходы пятого, шестого, седьмого элемента И подключены к первым входам элементов (i,j) (i=1, 2, …, m, j=1, 2, …, m) И, выходы восьмого, девятого и десятого элементов И подсоединены к первым входам 55 i.j и 57.i.j (i=1, 2, …, m, j=1, 2, …, m) И, выход переполнения шестого счетчика подключен ко входу сброса пятого счетчика, входы разрешения пятого и шестого счетчиков подключены к выходу третьего мультиплексора выбора элемента, выходы пятого и шестого счетчиков подсоединены к входам пятого и шестого дешифраторов, выходы с 1-го по m-й пятого дешифратора подсоединены к первому входу (i,j)-го элемента (i=1, 2, …, m, j=1, 2, …, m) И, выходы шестого дешифратора с 1-го по m-й подсоединены ко второму входу (i,j)-го элемента (i=1, 2, …, m, j=1, 2, …, m) И, инверсный выход второго триггера подсоединен к разрешающему входу третьего мультиплексора, S вход второго триггера подключен к выходу переполнения пятого счетчика, R вход второго триггера подключен к выходу переполнения четвертого счетчика инцидентной вершины, входы с 1 по m-й третьего мультиплексора подключены к соответствующим выходам группы с 1 по m-й триггеров, управляющий вход третьего мультиплексора подключен к выходу счетчика столбцов, второй вход второго элемента И подключен к разрешающему входу второго мультиплексора выбора элемента и к прямому выходу первого триггера режима, инверсный выход которого соединен с разрешающим входом первого мультиплексора выбора элемента и с первым входом первого элемента И, выход которого подключен к счетному входу первого счетчика фиксируемой дуги и к первому входу элемента ИЛИ, выход второго элемента И соединен со вторым входом элемента ИЛИ и входами разрешения второго и четвертого счетчиков инцидентной вершины соответственно, S-вход первого триггера режима подключен к выходу переполнения третьего счетчика инцидентной вершины и к входу сброса первого счетчика инцидентной вершины, счетный вход второго счетчика фиксируемой дуги которого подключен к входу сброса второго счетчика инцидентной вершины и к выходу переполнения четвертого счетчика инцидентной вершины, счетный вход которого соединен со счетным входом второго счетчика инцидентной вершины и выходом второго мультиплексора выбора элемента, управляющий вход которого подключен к управляющему входу первого мультиплексора выбора элемента и к выходу счетчика столбцов, счетный вход которого соединен с выходом элемента ИЛИ, установочный вход счетчика столбцов подключен к выходу счетчика строк и к входу дешифратора выбора строки, выход переполнения счетчика строк соединен с выходом переполнения устройства, выходы с 1-го по n-й дешифратора выбора строки соединены с соответствующими управляющими входами группы с 1-й по m-ю элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы элементов однородной среды, выходы групп с 1-й по m-ю элементов запрета соединены с соответствующими входами группы с 1-й по m-ю элементов ИЛИ, соответствующие выходы которых подключены к соответствующим S-входам с 1-го по m-й триггеров группы, соответствующие R-входы которых подсоединены к выходу переполнения счетчика столбцов и к счетному входу счетчика строк, выходы группы из m триггеров подключены к соответствующим входам первого, второго и третьего мультиплексоров выбора элемента, выход первого мультиплексора выбора элемента подключен к входам разрешения выдачи первого и второго счетчиков инцидентной вершины, соответствующие счетные входы которых подключены к выходу переполнения первого счетчика фиксируемой дуги, выход которого соединен с входом первого дешифратора фиксируемой дуги, i-й выход (i=1, 2, …, m) которого подключен к соответствующим первым входам (i.j)-x (i=1, 2, …, m, j=1, 2, …, n) элементов И, выход второго счетчика фиксируемой дуги подключен ко входу второго дешифратора фиксируемой дуги, соответствующий j-й (j=1, 2, …, n) выход которого соединен со вторыми входами (i.j)-x элементов (i=1, 2, …, m, j=1, 2, …, n) И, выход первого счетчика инцидентной вершины подключен ко входу первого дешифратора инцидентной вершины, соответствующий j-й выход (j=1, 2, …, n) которого подключен к соответствующему второму входу (i.j)-го элемента (i=1, 2, …, m, j=1, 2, …, n) И, выход третьего счетчика инцидентной вершины соединен со входом третьего дешифратора инцидентной вершины, соответствующий j-й выход (j=1, 2, …, n) которого подключен к соответствующему второму входу (i.j)-го элемента (i=1, 2, …, m, j=1, 2, …, n) И, выход четвертого счетчика инцидентной вершины подключен к входу четвертого дешифратора инцидентной вершины, соответствующий i-й (i=1, 2, …, m) выход которого подключен к соответствующему первому входу (i.j)-го элемента (i=1, 2, …, m, j=1, 2, …, n) И, второй счетчик инцидентной вершины соединен с входом второго дешифратора инцидентной вершины, соответствующий i-й (i=1, 2, …, m) выход которого подключен ко второму входу (i.j) элемента (i=1, 2, …, m, j=1, 2, …, n) И, выходы первого (i.j), второго (i.j), третьего (i.j), четвертого (i.j), пятого (i.j), шестого (i.j), седьмого (i.j) и восьмого (i.j) подключены к соответствующим входам элемента (i.j) ИЛИ, выходы которых (i.j) ИЛИ подсоединены к соответствующим счетным входам (i.j) счетчиков фиксированных дуг, выходы которых соединены с соответствующими входами второго сумматора, выход которого подключен к выходу значения нижней оценки устройства.

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

Общие особенности изобретения состоят в следующем.

Предлагаемое устройство может использоваться в области проектирования ВС, например при размещении процессов. Устройство позволяет находить так называемую нижнюю оценку размещения в МС по критерию минимизации интенсивности взаимодействия процессов и данных.

Исходная (размещаемая) задача (процесс, алгоритм) представляется в виде неориентированного невзвешенного графа G=<X,E>,

где

множество вершин графа G, вершины x_qk ∈ Х которого соответствуют подзадачам (подалгоритмам), а дуги связей между ними e_ij ∈ Е при i,j=(q-1)·n+k взвешиваются объемами данных m_ij, передаваемыми между задачами и сведенными в матрицу обмена информацией (МОИ) , где N=n²=|X|.

МС отображается однородной средой, которой ставится в соответствие топологическая модель в виде графа H=<P,V>,

где - множество идентификаторов процессорных модулей базового блока, организованных в матрицу |Р|_n×n, где |P|=N=n² - число процессорных модулей базового блока; V- множество межмодульных связей, задаваемых матрицей смежности .

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

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

Сущность предлагаемой нижней оценки размещения поясняется фиг.2. Модули МС на фиг.2а и 2б представлены квадратами, в левом верхнем углы которых представлены их номера. Внутри модулей кружками обозначены вершины графа с соответствующими номерами внутри. Пунктирные линии обозначают связи модулей МС, а сплошные линии рядом с пунктирными - гипотетические зафиксированные дуги, правая диагональ располагается между модулями МС 2 и 4, а левая между модулями МС 1 и 2. Из фиг.2а видно, что связи между модулями 1-2 и 1-3 распределены неравномерно, что неизбежно увеличивает суммарное время выполнения задачи, так как модули 1 и 2 будут загружены сильнее, чем модули 4 и 3. Время выполнения задачи можно уменьшить за счет переназначения дуг так, как показано на фиг.2б. Такой вариант размещения одновременно является нижней оценкой размещения для МС.

Устройство поиска нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче данных (фиг.1) содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блок 2.1-2.n подсчета единиц, блок 3 нахождения максимума, первый сумматор 4, блок 5 памяти, причем входы управления перестановкой столбцов матрицы 1 элементов однородной среды соединены с входом 7 управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы 1 элементов однородной среды соединены с входом 8 управления перестановкой строк устройства, входы установки матрицы 1 элементов однородной среды соединены с входом 13 установки устройства, информационные входы матрицы 1 элементов однородной среды соединены с входом 6 записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, …, n) матрицы 1 элементов однородной среды соединены с входом блока 2.j подсчета единиц, выход которого соединен с j-м входом блока 3 нахождения максимума и j-м входом первого сумматора 4, выходы которых соединены с выходом 10 максимальной длины ребра устройства и выходом 11 суммарной длины ребер устройства соответственно, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, m) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также дополнительно введенный блок 68 поиска нижней оценки, содержащий генератор 14 импульсов, первый 15, второй 16 и третий 17 мультиплексоры выбора элемента, дешифратор 18 выбора строки, первый 19, второй 20, третий 22, четвертый 23, пятый 25 и шестой 26 дешифраторы инцидентной вершины, первый 21, второй 24 и третий 27 дешифраторы фиксируемой дуги, счетчик 28 строк, счетчик 29 столбцов, первый 30, второй 31 и третий 32 счетчик фиксируемой дуги, первый 35, второй 33, третий 34, четвертый 36, пятый 37 и шестой 38 счетчики инцидентной вершины, первый 39 и второй 40 триггеры режима, группу из 41.1-41.m триггеров, второй 42 сумматор, группу из 43.1, 43.2, …, 43.m блоков элементов запрета, матрица 44.i.j (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных дуг, матрица 46.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов ИЛИ, первая матрица 50.i.j (i=1, 2, …, m, j=1, 2, …, n), вторая матрица 51.i.j (i=1, 2, …, m, j=1, 2, …, n), третья матрица 52.i.j (i=1, 2, …, m, j=1, 2, …, n), четвертая матрица 53.i.j (i=1, 2, …, m, j=1, 2, …, n), пятая матрица 54.i.j (i=1, 2, …, m, j=1, 2, …, n), шестая матрица 55.i.j (i=1, 2, …, m, j=1, 2, …, n), седьмая матрица 56.i.j (i=1, 2, …, m, j=1, 2, …, n), восьмая матрица 57.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И, 47 элемент ИЛИ, первый 48 и второй 49 инверторы, первый 64, второй 65, третий 66, четвертый 67, пятый 58, шестой 59, седьмой 60, восьмой 61, девятый 62 и десятый 63 элементы И, группа 45.1, 45.2-45.m элементов ИЛИ, причем вход 69 запуска устройства соединен с генератором 14 импульсов, выход которого соединен с первым входом третьего 66 элемента И, второй вход которого подключен к прямому выходу второго 40 триггера, выход третьего 66 элемента И подключен ко второму входу четвертого 67 элемента И, к первому входу второго 65 элемента И и ко второму входу первого 64 элемента И, к первому входу четвертого 67 элемента И подключен выход генератора 14, причем выход четвертого 67 элемента И подключен ко входу второго 48 элемента ИЛИ, выход которого подсоединен к первому входу первого 47 элемента ИЛИ и счетному входу третьего 32 счетчика, выход переполнения которого подключен к счетным входам пятого 37 и шестого 38 счетчиков инцидентной вершины, выход третьего 32 счетчика подключен ко входу третьего 27 дешифратора фиксируемой дуги, выходы с 1 по m-й которого подключены к соответствующим первым входам пятого 58, шестого 59, седьмого 60, восьмого 61, девятого 62 и десятого 63 элементов И, ко вторым входам восьмого 61, девятого 62 и десятого 63 элементов И подсоединен выход третьего 49 инвертора, ко вторым входам пятого 58, шестого 59 и седьмого 60 элемента И подсоединен выход переполнения шестого 38 счетчика инцидентной вершины, который также подсоединен ко входу третьего 49 инвертора, выходы пятого 58, шестого 59, седьмого 60 элемента И подключены к первым входам элементов 54.i.j и 55.i.j (i=1, 2, …, m, j=1, 2, …, m) И, выходы восьмого 61, девятого 62 и десятого 63 элементов И подсоединены к первым входам элементов 56.i.j и 57.i.j (i=1, 2, …, m, j=1, 2, …, m) И, выход переполнения шестого 38 счетчика подключен к входу сброса пятого 37 счетчика, входы размещения пятого 37 и шестого 38 счетчиков подключены к выходу третьего 17 мультиплексора выбора элемента, выходы пятого 37 и шестого 38 счетчиков подсоединены к входам пятого 25 и шестого 26 дешифраторов, выходы с 1-го по m-й пятого 25 дешифратора подсоединены к первому входу 56.i.j и 54.i.j элемента (i=1, 2, …, m, j=1, 2, …, m) И, выходы шестого 26 дешифратора с 1-го по m-й подсоединены ко второму входу 55.i.j и 57.i.j элемента (i=1, 2, …, m, j=1, 2, …, m) И, инверсный выход второго 40 триггера подсоединен к разрешающему входу третьего 17 мультиплексора, S вход второго 40 триггера подключен к выходу переполнения пятого 37 счетчика, R вход второго 40 триггера подключен к выходу переполнения четвертого 31 счетчика инцидентной вершины, входы с 1 по m-й третьего 17 мультиплексора подключены к соответствующим выходам группы 41.1-41.m триггеров, управляющий вход третьего 17 мультиплексора подключен к выходу счетчика 29 столбцов, второй вход второго 65 элемента И подключен к разрешающему входу второго 16 мультиплексора выбора элемента и к прямому выходу первого 39 триггера режима, инверсный выход которого соединен с разрешающим входом первого 15 мультиплексора выбора элемента и с первым входом первого 64 элемента И, выход которого подключен к счетному входу первого 30 счетчика фиксируемой дуги и к первому входу элемента 47 ИЛИ, выход второго 65 элемента И соединен со вторым входом первого 47 элемента ИЛИ и входами разрешения третьего 34 и четвертого 36 счетчиков инцидентной вершины соответственно, S-вход первого 39 триггера режима подключен к выходу переполнения второго 33 счетчика инцидентной вершины и к входу сброса первого 35 счетчика инцидентной вершины, счетный вход второго 31 счетчика фиксируемой дуги подключен к входу сброса четвертого 36 счетчика инцидентной вершины и к выходу переполнения третьего 34 счетчика инцидентной вершины, счетный вход которого соединен со счетным входом четвертого 36 счетчика инцидентной вершины и выходом второго 16 мультиплексора выбора элемента, управляющий вход которого подключен к управляющему входу первого 15 мультиплексора выбора элемента и к выходу счетчика 29 столбцов, счетный вход которого соединен с выходом первого 47 элемента ИЛИ, установочный вход счетчика 29 столбцов подключен к выходу счетчика 28 строк и к входу дешифратора 18 выбора строки, выход переполнения счетчика 28 строк соединен с выходом переполнения устройства 71, выходы с 1-го по n-й дешифратора 18 выбора строки соединены с соответствующими управляющими входами группы 43.1-43.m элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы групп 43.1-43.m элементов запрета соединены с соответствующими входами групп 45.1-45.m элементов ИЛИ, соответствующие выходы которых подключены к соответствующим S-входам группы 41.1-41.m RS-триггеров, соответствующие R-входы которых подсоединены к выходу переполнения счетчика 29 столбцов и к счетному входу счетчика 28 строк, выходы группы из m триггеров подключены к соответствующим входам первого 15, второго 16 и третьего 17 мультиплексоров выбора элемента, выход первого 15 мультиплексора выбора элемента подключен к входам разрешения выдачи первого 35 и второго 33 счетчиков инцидентной вершины, соответствующие счетные входы которых подключены к выходу переполнения первого 30 счетчика фиксируемой дуги, выход которого соединен со входом первого 21 дешифратора фиксируемой дуги, i-й выход (i=1, 2, …, m) которого подключен к соответствующим первым входам 50.i.j и 51.i.j (i=1, 2, …, m, j=1, 2, …, n) элементов И, выход второго 31 счетчика фиксируемой дуги подключен ко входу второго 24 дешифратора фиксируемой дуги, соответствующий j-й (j=1, 2, …, n) выход которого соединен со вторыми входами 53.i.j и 52.i.j элементов (i=1, 2, …, m, j=1, 2, …, n) И, выход первого 35 счетчика инцидентной вершины подключен ко входу первого 19 дешифратора инцидентной вершины, соответствующий j-й выход (j=1, 2, …, n) которого подключен к соответствующему второму входу 51.i.j элемента (i=1, 2, …, m, j=1, 2, …, n) И, выход третьего 34 счетчика инцидентной вершины соединен со входом третьего 22 дешифратора инцидентной вершины, соответствующий j-й выход (j=1, 2, …, n) которого подключен к соответствующему второму входу 53.i.j элемента (i=1, 2, …, m, j=1, 2, …, n) И, выход четвертого 36 счетчика инцидентной вершины подключен к входу четвертого 23 дешифратора инцидентной вершины, соответствующий i-й (i=1, 2, …, m) выход которого подключен к соответствующему первому входу 52.i.j элемента (i=1, 2, …, m, j=1, 2, …, n) И, второй 33 счетчик инцидентной вершины соединен с входом второго 20 дешифратора инцидентной вершины, соответствующий i-й (i=1, 2, …, m) выход которого подключен ко второму входу 50.i.j элемента (i=1, 2, …, m, j=1, 2, …, n) И, выходы первого 50.i.j, второго 51.i.j, третьего 52.i.j, четвертого 53.i.j, пятого 54.i.j, шестого 55.i.j, седьмого 56.i.j и восьмого 57.i.j подключены к соответствующим входам элементов 46.i.j ИЛИ, соответствующие выходы которых подсоединены к соответствующим счетным входам 44.i.j счетчиков фиксированных дуг, выходы которых соединены с соответствующими входами второго 42 сумматора, выход которого подключен к выходу 70 значения нижней оценки устройства.

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

Матрица 1 элементов однородной среды предназначена для моделирования процесса решения задач размещения.

Блоки 2.1 - 2.n подсчета единиц предназначены для преобразования кодов с индикаторных выходов элементов соответствующих столбцов матрицы 1 в двоичные коды.

Блок 3 нахождения максимума предназначен для выделения максимального кода из множества кодов на его входах.

Первый сумматор 4 предназначен для суммирования n двоичных кодов.

Блок 5 памяти предназначен для хранения наилучшего на данный момент варианта размещения.

Вход 6 записи устройства служит для записи матрицы, представляющей размещаемый граф.

Вход 7 управления перестановкой столбцов устройства предназначен для приема сигнала от ВУУ о перестановке столбцов.

Вход 8 управления перестановкой строк устройства предназначен для приема сигнала от ВУУ о перестановке строк.

Вход 9 управления записью устройства необходим для приема сигнала «Запись» от ВУУ. По этому сигналу в блок 5 памяти заносится текущий вариант размещения из матрицы 1.

Выход 10 максимальной длины ребра устройства необходим для выдачи значения максимальной длины ребра на ВУУ.

Выход 11 суммарной длины ребер устройства необходим для выдачи значения суммарной длины ребер на ВУУ.

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

Вход 13 установки устройства необходим для синхронизации записи информации в элементы матрицы 1.

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

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

Дешифратор 18 выбора строки служат для выбора очередной строки матрицы 1 (матрицы смежности размещаемого графа).

Первый 19, второй 20, третий 22, четвертый 23, пятый 25 и шестой 26 дешифраторы инцидентной вершины предназначены для выбора очередной фиксируемой дуги, инцидентной текущим вершинам графа. Первый 19 и второй 20 дешифраторы выбирают дугу для фиксации в строках МС, третий 22 и четвертый 23 дешифраторы инцидентной вершины выбирает дугу для фиксации в столбцах, пятый 25 и шестой 26 дешифраторы инцидентной вершины выбирает дугу для фиксации в диагоналях МС. Так как размещаемый граф невзвешенный, то при фиксации дуги необходимо учитывать две инцидентные фиксируемой дуге вершины.

Первый 21 дешифратор фиксируемой дуги предназначен для выбора очередной строки МС, в которую будет производится фиксация очередной дуги.

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

Третий 27 дешифратор фиксируемой дуги предназначен для выбора очередной строки МС, в которую будет производится фиксация очередной дуги.

В счетчике 28 строк содержится информация о текущей обрабатываемой строке матрицы 1.

В счетчике 29 столбцов содержится информация о текущем обрабатываемом столбце матрицы 1.

В первом 30 счетчике фиксируемой дуги содержится информация о номере дуги, фиксируемой горизонтально в МС. На фиг.2в, 2г это номера 1-2 и 3-4. Этот счетчик не может содержать значения больше m-1.

Второй 31 счетчик фиксируемой дуги предназначен для накапливания информации о номере дуги, фиксируемой вертикально в МС. На фиг 2в, 2г ими являются номера 1-3 и 2-4. Такой счетчик не может содержать значения большего n-1.

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

Первый 19 и второй 20 счетчики инцидентной вершины служат для накапливания информации о текущих фиксируемых дугах в строках МС, инцидентных выбранным вершинам графа из матрицы 1.

Третий 22 и четвертый 23 счетчики инцидентной вершины предназначены для хранения информации о текущих фиксируемых дугах в столбцах МС, инцидентных выбранным вершинам графа из матрицы 1.

Пятый 25 и шестой 26 счетчики инцидентной вершины предназначены для хранения информации о текущих фиксируемых дугах в левых и правых диагоналях МС, инцидентных выбранным вершинам графа из матрицы 1.

Первый 39 триггер режима служит для выбора режима фиксации дуг. В нулевом состоянии триггера происходит фиксация в строках МС, в единичном - в столбцах МС.

Второй 40 триггер режима для выбора режима фиксации дуг. В нулевом состоянии триггера происходит фиксация в правых диагоналях МС, в единичном - в левых диагоналях МС.

Группа 41.1-41.m RS-триггеров предназначена для хранения информации о наличии дуги между соответствующими инцидентными вершинами.

Второй 42 сумматор служит для накопления значения нижней оценки размещения в МС.

Группа 43.1-43.m элементов запрета предназначена для блокировки поступления значений от элементов с 1-й по m-ю строк матрицы 1 на соответствующие элементы ИЛИ 37.1-37.m.

Матрица 44.i.j (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных дуг служит для подсчета загрузки модулей МС.

Группа 45.1-45.m элементов ИЛИ служат для объединения сигналов с выходов группы элементов 43.1-43.m запрета соответственно.

Матрица 46. i.j элементов ИЛИ предназначена для объединения сигналов с выходов матрицы 50.i.j, 51.i.j, 52.i.j, 53.i.j, 54.i.j, 55.i.j, 56.i.j, 57.i.j элементов И с последующей подачей на вход счетчика 44.i.j фиксированных дуг. Здесь i=1, 2, …, m, j=1, 2, …. n.

Первая 50.i.j, вторая 51.i.j, третья 52.i.j, четвертая 53.i.j, пятая 54.i.j, шестая 56.i.j, седьмая 57.i.j матрицы элементов И необходимы для обеспечения фиксации инцидентной текущим вершинам дуги в модулях МС. Здесь i=1, 2, …, m и j=1, 2, …, n.

Элемент 47 ИЛИ предназначен для объединения сигналов с выходов первого 64, второго 65 и третьего 67 элементов И.

Первый 64, второй 65 и третий 67 элементы И служат для подачи тактового импульса с генератора 14 импульсов в зависимости от значения первого 39 и второго 40 триггеров режима либо на первый 30 счетчик фиксируемой дуги и на первый вход элемента 47 ИЛИ, либо на второй вход элемента 47 ИЛИ и на входы разрешения выдачи второго 34 и четвертого 36 счетчика инцидентной вершины, либо на пятый 25 и шестой 26 счетчики инцидентной вершины соответственно.

Группа 45.1-45.m элементов ИЛИ необходима для объединения сигналов с выходов первой группы 43.1-43.m элементов запрета соответственно.

Группа 58-63 элементов И предназначена для разделения двух режимов фиксации дуг: левая диагональ и правая диагональ при помощи инвертора 49.

Инвертор 48 предназначен для распределения фиксации дуг в диагоналях.

Блок 68 поиска нижней оценки служит для нахождения нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче данных.

Вход 69 запуска устройства необходим для подачи сигнала запуска генератора 14 импульсов от ВУУ.

Выход 70 значения нижней оценки служит для выдачи на ВУУ значения нижней оценки текущего варианта размещения в МС.

Выход 71 переполнения устройства служит для подачи информации о переполнении первого счетчика 28 номера строки, что одновременно является сигналом о завершении работы блока 68.

Работа блоков 1, 2, 3, 4 и 5 подробно описана в прототипе и поэтому здесь не рассматривается.

Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения, соответствующий матрице смежности исходного графа. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. Группа 41.1-41.m триггеров находится в состоянии логического нуля. Триггер 39 режима находится в состоянии логического нуля, поэтому на прямом его выходе присутствует нулевой потенциал, а на инверсном - единичный. Триггер 40 находится в состоянии логической единицы и тогда в счетчиках матрицы 44.i.j (i=1, 2, …, m, j=1, 2, …, n) присутствует коды нуля («00…00»). В счетчике 28 и 29 присутствует код единицы («00…01»). Единичное значение с выхода счетчика 28 подается на вход дешифратора 18, поэтому на первом его выходе присутствует единый сигнал, который подается на соответствующие управляющие входы первого блока 43.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. Эти сигналы проходят через группу 45.1-45.m элементов ИЛИ и поступают на соответствующие S-входы группы 41.1-41.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. В счетчике 33 и 38 содержится код двойки («00…010»), в счетчиках 31, 35, 37 и 34 - код единицы («00…01»). Во втором сумматоре 42 и в счетчиках 30, 32 и 36 содержится код нуля.

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

Оценка размещения по критериям суммарной длины ребер и максимальной длины ребра происходит следующим образом. Информация с индикаторных выходов элементов каждого столбца матрицы 1 поступает в соответствующие блоки подсчета единиц. Блок 2.i (i=1, 2, …, n) выдает двоичное число (код), равное количеству поступивших на его вход единиц. Полученное число далее поступает на входы первого сумматора 4 и блока 3 нахождения максимума, соответствующие данному блоку подсчета единиц. В результате на выходе 10 устройства образуется код (оценка) максимальной длины ребра, а на выходе 11 - код (оценка) суммарной длины ребер, отвечающие текущему варианту размещения схемы (содержащемуся в матрице 1). Полученные оценки далее поступают на ВУУ, где происходит их сравнение с предыдущими значениями. В случае улучшения оценок ВУУ подает импульс (сигнал «Запись») на вход 9 управления записью устройства и текущий вариант размещения переписывается в блок 5 памяти из матрицы 1.

Задача поиска значения нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче данных решается следующим образом. После выполнения очередной перестановки строк на индикаторных выходах элементов матрицы 1 появляются сигналы, соответствующие новому варианту размещения. Одновременно с этим запускается генератор 14 импульсов и начинается работа блока 68 поиска нижней оценки, которая делится на четыре этапа: первый этап заключается в фиксации дуг в строках МС, на втором этапе происходит фиксация в столбцах МС, а на третьем и четвертом этапах происходит фиксация дуг по диагоналям: левой и правой. В случае, если после всех четырех этапов работы устройства еще существуют незафиксированные дуги, то процесс фиксации повторяется до тех пор, пока не будут обработаны все дуги исходного графа. Об этом свидетельствует полный перебор всех значений в матрице смежности.

Так как триггер 39 режима находится в состоянии логического нуля, то на его инверсном выходе присутствует единичный сигнал, который поступает на первый вход элемента 64 И и на разрешающий вход первого мультиплексора 15 выбора элемента. Единичный сигнал с прямого выхода триггера 40 поступает на второй вход элемента 66, разрешая прохождение импульса с генератора 14 на вторые входы элементов 64 и 65. В результате появления импульса на втором входе элемента 64 И на его выходе появляется единичный импульс, который поступает на счетный вход счетчика 30, увеличивая его содержимое по переднему фронту до кода единицы («00…01»). Тот же импульс попадает на первый вход элемента 47 ИЛИ. Положительный импульс поступает на счетный вход счетчика 29 и увеличивает его содержимое по переднему фронту до кода двойки («00…010»).

Код числа два с выхода счетчика 29 поступает на управляющие входы первого 15, второго 16 и третьего 17 мультиплексоров выбора элемента. Так как на разрешающем входе мультиплексора 15 присутствует единица, то поступивший на его управляющий вход код числа два пропускает единичное значение с выхода триггера 41.2. Если он находится в единичном состоянии, то на выходе мультиплексора 15 появляется единичный импульс. Единичный сигнал с выхода мультиплексора 15 поступает на входы разрешения выдачи счетчиков 35 и 33, разрешая появление кодов на их выходах. В рез