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

Изобретение относится к области вычислительной техники и предназначено для моделирования задач при проектировании вычислительных систем (ВС). Техническим результатом является расширение области применения устройства за счет поиска нижней оценки размещения в полносвязных матричных системах при двунаправленной передаче данных по критерию минимизации интенсивности взаимодействия процессов и данных. Устройство содержит матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, первый сумматор, блок памяти, блок поиска нижней оценки, содержащий генератор импульсов, три мультиплексора выбора элемента, дешифратор выбора строки, девять дешифраторов, счетчик строк, счетчик столбцов, девять счетчиков, два триггера режима, группу из m триггеров, второй сумматор, группу из m блоков элементов запрета, матрицу из (i,j) (i=1, 2, …, m, j=1, 2, …, n) счетчиков, матрицу из (i,j) (i=1, 2, …, m, j=1, 2, …, n) элементов ИЛИ, восемь матриц из i строк (i=1, 2, …, m) и j столбцов (j=1, 2, …, n) элементов И, элемент ИЛИ, два инвертора, десять элементов И, группу из m элементов ИЛИ. 2 ил.

 

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

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 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, разрешая появление кодов на их выходах. В результате этого на входе дешифратора 20 появляется код числа два («00…010»), поэтому на втором его выходе появляется единичный сигнал, который поступает на второй вход элемента 50.i.2 (i=1, 2, …, m) И МС. Одновременно с этим на первом выходе дешифратора 19 появляется единичный сигнал, который поступает на второй вход элемента 51.i.1 (i=1, 2, …, m) И МС.

К этому времени на выходе счетчика 30 уже присутствует код «00…01», который поступает на вход дешифратора 21, поэтому на первом его выходе появляется единичный сигнал. Этот сигнал поступает на первые входы элементов 51.1.j (j=1, 2, …, n) и 50.1.j (j=1, 2, …, n) И МС (фиг.1). Таким образом, на выходах элементов 51.1.1 и 50.1.2 И появляются единичные сигналы, которые проходят через соответствующие элементы 46.1.1 и 46.1.2 ИЛИ и поступают на счетные входы счетчиков 44.1.1 и 44.1.2, увеличивая их содержимое на единицу. Таким образом происходит фиксация дуги в первой строке МС.

Очередной тактовый импульс поступает на второй вход элемента 64 И и на первый вход элемента 65 И. Так как на первом входе элемента 64 И присутствует единичный импульс с инверсного выхода триггера 39, на выходе элемента 64 И появляется положительный импульс, который поступает на счетный вход счетчика 30 и на элемент 47 ИЛИ, проходя на счетный вход счетчика 29. В результате в счетчике 30 по переднему фронту будет установлен код двойки («00…010»), а в счетчике 29 по переднему фронту установится код числа три («00…011»). Код тройки с выхода счетчика 29 поступит на управляющие входы мультиплексоров 15, 16 и 17. На разрешающем входе мультиплексора 15 присутствует единичный сигнал, который разрешает поступление сигналов на его выход. Если на выходе триггера 41.3 присутствует единичный сигнал (это означает наличие дуги в графе), то на выходе мультиплексора 15 появится единичный импульс, который поступит на входы разрешения выдачи счетчиков 35 и 33. Код единицы с выхода счетчика 35 поступит на вход дешифратора 19, а на входе дешифратора 20 появится код двойки с выхода счетчика 33. Соответственно на первом выходе дешифратора 19 и на втором выходе дешифратора 20 появятся единичные сигналы. Единичный сигнал с первого выхода дешифратора 19 поступит на второй вход элемента 51.i.1 (i=1, 2, …, m) И МС. Единичный сигнал со второго выхода дешифратора 20 поступит на второй вход элемента 50.i.2 (i=1, 2, …, m) И МС.

Код «00…010» с выхода счетчика 30 поступает на вход дешифратора 21 и возбуждает на его втором выходе положительный импульс, который, в свою очередь, поступает на первые входы элементов 51.2.j (j=1, 2, …, n) и 50.2.j (j=1, 2, …, n) И. Таким образом, на выходе элементов 51.2.1 и 50.2.2 появятся единые сигналы, которые пройдут через соответствующие элементы 46.2.1 и 46.2.2 ИЛИ и увеличат по переднему фронту содержимое счетчиков 44.2.1 и 44.2.2 на единицу, фиксируя тем самым очередную дугу рассматриваемого графа.

Так происходит до тех пор, пока не произойдет переполнение содержимого счетчика 30. Такая ситуация возникнет в том случае, когда содержимое счетчика >m. В этом случае на выходе переполнения счетчика 30 появится единичный импульс, а его содержимое сбрасывается в единицу. Импульс с выхода переполнения счетчика 30 поступит на счетные входы счетчиков 35 и 33, увеличивая их содержимое по переднему фронту на единицу. Таким образом содержимое счетчика 35 установится в двойку и в нем будет содержаться код «00…010», а в счетчике 33 установится код числа три («00…011»). В это время содержимое счетчика 29 будет увеличено по переднему фронту на единицу до кода четырех («00…0100»). После этого фиксация дуг повторяется так, как описано выше.

Так продолжается до тех пор, пока не произойдет переполнение либо счетчика 29, либо счетчика 33. Переполнение счетчика 29 произойдет в том случае, если его содержимое превысит код числа n. В этом случае на выходе переполнения появляется единичный импульс, который поступает на счетный вход счетчика 28 строк и увеличивает его содержимое по переднему фронту на единицу, устанавливая в нем код двойки («00…010»). Код числа два поступает на вход дешифратора 18 и на установочный вход счетчика 29, устанавливая в нем начальное значение, равное коду двойки («00…010»). На втором выходе дешифратора 18 появляется единичный импульс, который поступает на управляющие входы блока 43.2 элементов запрета, разрешая тем самым прохождение сигналов с индикаторных выходов элементов второй строки матрицы 1, которые проходят через соответствующие входы группы 45.1-45.m элементов ИЛИ и поступают на соответствующие S-входы группы 41.1-41.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. Далее работа происходит так, как описано выше.

Переполнение первого счетчика 33 фиксируемой дуги означает, что фиксация дуг исходного графа в строках МС закончена (на фиг.2 это дуги, зафиксированные в модулях 1-2 и 3-4) и далее необходимо фиксировать дуги в столбах МС (на фиг.2 это модули 1-3 и 2-4). Сигнал с выхода переполнения счетчика 33 поступает на вход сброса счетчика 35, сбрасывая его до кода единицы. Тот же сигнал поступает на S-вход триггера 39 режима, устанавливая его в единичное состояние. Тогда на его прямом выходе будет присутствовать единичный сигнал, а на инверсном - нулевой. Нулевой сигнал с инверсного выхода триггера 39 поступает на разрешающий вход мультиплексора 15 и запрещает прохождение сигналов на его выход. Кроме того, тот же сигнал поступает на первый вход элемента 64 И, запрещая тем самым прохождение импульсов с генератора 14 импульсов. Единичный сигнал с прямого выхода триггера 39 поступает на второй вход элемента 65 И, разрешая прохождение импульсов с генератора 14 импульсов на его выходы и на разрешающий вход мультиплексора 16, разрешая тем самым прохождение сигналов с входов на его выход. В счетчике 33 устанавливается код двойки («00…010»)

Очередной тактовый импульс с генератора 14 импульсов поступает на первый вход элемента 65 И. Так как на двух его входах присутствуют единичные сигналы, то на выходе появляется единичный импульс, который поступает на второй вход элемента 47 ИЛИ и далее проходит на счетный вход счетчика 29, увеличивая его содержимое по переднему фронту на единицу. Тот же импульс с выхода элемента 65 И попадает на входы разрешения выдачи счетчиков 36 и 34, разрешая тем самым появление содержащихся в них кодов на соответствующих выходах.

К этому времени на управляющих входах мультиплексоров 15, 16 и 17 появится код числа, содержащегося в счетчике 29. Так как на разрешающем входе мультиплексора 16 присутствует положительный импульс, и, если в триггере 45.j (j=1, 2, …, n) содержится единица, то на выходе мультиплексора 16 появится положительный импульс. Единичный сигнал с выхода мультиплексора 16 поступает на счетные входы счетчиков 36 и 34, увеличивая их содержимое по переднему фронту до кодов «00…01» и «00…010» соответственно. Поэтому на входе дешифратора 23 появится код «00…01», а на входе дешифратора 22 - код двойки («00…010»). При появлении кодов на входах дешифраторов 22 и 23, на первом выходе дешифратора 23 возбуждается единичный импульс, который поступает на первые входы элемента 52.1.j (j=1, 2, …, n) И МС. На втором выходе дешифратора 22 появляется единичный импульс, который поступает на первые входы элементов 53.2.j (j=1, 2, …, n) И МС.

Код «00…01» с выхода счетчика 31 поступает на вход дешифратора 24, и на его первом выходе появляется единичный импульс, который поступает на вторые входы элементов 53.i.1 (i=1, 2, …, m) и 52.i.1 (i=1, 2, …, m) И МС. Таким образом, на выходах этих элементов появится единичный импульс. Тем самым обеспечивается появление положительных сигналов на входах элементов 46.1.1 и 46.2.1 ИЛИ МС, которые поступают на счетные входы соответствующих счетчиков 44.1.1, 44.2.1 и по переднему фронту увеличивает их содержимое на единицу. Так происходит фиксация дуги в столбце МС.

Очередной импульс с выхода генератора 14 импульсов возбуждает импульс на выходе элемента 65 И, который поступает на счетные входы счетчиков 36 и 34, и на второй вход элемента 47 ИЛИ, который проходит на счетный вход счетчика 29, увеличивая его содержимое по переднему фронту на единицу. В счетчике 36 таким образом по переднему фронту установится код числа два («00…010»), и в счетчике 34 - код числа три («00…011»).

В результате на втором выходе дешифратора 23 и на третьем выходе дешифратора 22 появляется единичные импульсы. Соответствующие импульсы поступят на соответствующие первые входы элемента 52.2.j (j=1, 2, …, n) И МС и на первые входы элемента 53.3.j (j=1, 2, …, n) И МС.

На первом выходе дешифратора 24 по-прежнему присутствует единичное значение, которое поступает на вторые входы элементов 53.i.1 (i=1, 2, …, m) и 52.i.1 (i=1, 2, …, m) И МС. Таким образом на выходах элементов 53.3.1 и 52.2.1 И появится единичное значение, которое, пройдя через элемент 46.3.1 и 46.2.1 ИЛИ, поступит на входы соответствующих счетчиков 44.3.1, 44.2.1 и увеличит их содержимое по переднему фронту на единицу. Таким образом произойдет фиксация очередной дуги в столбце МС.

Так происходит до тех пор, пока на выходе счетчика 34 не появится сигнал переполнения, свидетельствующий о том, что дуги в первом столбце МС зафиксированы и необходимо переходить к следующему столбцу. Единичный импульс с выхода переполнения счетчика 34 поступит на вход сброса счетчика 36, сбрасывая его содержимое в ноль и устанавливая в нем код «00…00». Тот же импульс поступает на счетный вход счетчика 31 и по переднему фронту увеличивает его содержимое на единицу до кода двойки («00…010»). В счетчике 34 устанавливается значение единицы. После этого процесс повторяется так, как описано выше.

Так происходит до тех пор, пока на выходе переполнения счетчика 31 не появится импульс переполнения, свидетельствующий о том, что дуги во всех столбцах МС зафиксированы. Импульс переполнения поступает на R-вход триггера 40 режима сбрасывая его содержимое в ноль. Таким образом, на его прямом выходе появится нулевое значение, а на инверсном - положительное.

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

Код числа два с выхода счетчика 29 поступает на управляющие входы первого 15, второго 16 и третьего 17 мультиплексоров выбора элемента. Так как на разрешающем входе мультиплексора 17 присутствует единица, то поступивший на его управляющий вход код числа два пропускает единичное значение с выхода триггера 41.2. Если он находится в единичном состоянии, то на выходе мультиплексора 17 появляется единичный импульс. Единичный сигнал с выхода мультиплексора 17 поступает на входы разрешения выдачи счетчиков 37 и 38, разрешая появление кодов на их выходах. В результате этого на входе дешифратора 25 появляется код числа единицы («00…01»), поэтому на первом его выходе появляется единичный сигнал, который поступает на второй вход элемента 54.i.1 (i=1, 2, …, m) И МС. Одновременно с этим на втором выходе дешифратора 26 появляется единичный сигнал, который поступает на второй вход элемента 55.i.2 (i=1, 2, …, m) И МС.

К этому времени на выходе счетчика 32 уже присутствует код «00…01», который поступает на вход дешифратора 27, поэтому на первом его выходе появляется единичный сигнал. Этот сигнал поступает на первые входы элементов 58 И и 61 И, но так как сигнала прерывания со счетчика 38 еще не было, то нулевой сигнал, проходя через инвертор 49, становится единичным и попадает на второй ход элемента 58 И, тем самым разрешая подачу сигнала дальше. С элемента 58 И сигнал попадает на элементы 54.1.j и 55.1.j. Так как положительный сигнал на первом входе присутствует только у элементов 54.1.1 и 55.2.2, через них и проходит положительный сигнал на соответствующие элементы 46.1.1 и 46.2.2 ИЛИ и поступают на счетные входы счетчиков 44.1.1 и 44.2.2, увеличивая их содержимое на единицу. Таким образом происходит фиксация дуги в первой строке МС.

Очередной тактовый импульс поступает на второй вход элемента 67 И. Импульс поступает с выхода инвертора 48 на вход элемента 47, тем самым устанавливая счетчик 29 в значение тройки («00… 11»), а счетчик 32 в значение двойки («00…10»). Код тройки с выхода счетчика 29 поступит на управляющие входы мультиплексоров 15, 16 и 17. На разрешающем входе мультиплексора 17 присутствует единичный сигнал, который разрешает поступление сигналов на его выход. Если на выходе триггера 41.3 присутствует единичный сигнал (это означает наличие дуги в графе), то на выходе мультиплексора 17 появится единичный импульс, который поступит на входы разрешения выдачи счетчиков 37 и 38. Код единицы с выхода счетчика 37 поступит на вход дешифратора 25, а на входе дешифратора 26 появится код двойки с выхода счетчика 38. Соответственно на первом выходе дешифратора 25 и на втором выходе дешифратора 26 появятся единичные сигналы. Единичный сигнал с первого выхода дешифратора 25 поступит на второй вход элемента 54.i.1 (i=1, 2, …, m) И МС. Единичный сигнал со второго выхода дешифратора 26 поступит на второй вход элемента 55.i.2 (i=1, 2, …, m) И МС.

Код «00…010» с выхода счетчика 32 поступает на вход дешифратора 27 и возбуждает на его втором выходе положительный импульс, который, в свою очередь, поступает на первые входы элементов 54.2.j (j=1, 2, …, n) и 55.2.j (j=1, 2, …, n) И через элементы 58-60 И. Таким образом, на выходе элементов 54.2.1 и 55.3.2 появятся единые сигналы, которые пройдут через соответствующие элементы 46.2.1 и 46.3.2 ИЛИ и увеличат по переднему фронту содержимое счетчиков 44.2.1 и 44.3.2 на единицу, фиксируя тем самым очередную дугу рассматриваемого графа.

Так происходит до тех пор, пока не произойдет переполнение содержимого счетчика 38. Такая ситуация возникнет в том случае, когда содержимое счетчика >m. В этом случае на выходе переполнения счетчика 38 появится единичный импульс, а его содержимое сбрасывается в единицу. Импульс с выхода переполнения счетчика 38 поступит на вход сброса счетчика 37, обнуляя его и устанавливая его содержимое в двойку («00…10»), а в счетчике 38 установится код числа единицы («00…01»). В это время содержимое счетчика 29 будет увеличено по переднему фронту на единицу до кода четырех («00…0100»).

После этого происходит фиксация правых диагоналей. Так как единичный сигнал с выхода переполнения счетчика 38 попал на вход счетчика 37, параллельно он попадает на вторые входы элементов 61-63 И, тем самым разрешая фиксацию правых диагоналей. Единичный сигнал, проходящий через инвертор 49, становится нулевым и попадая на вторые входы элементов 58-60 И, запрещает фиксацию левых диагоналей. Импульсы с выходов элементов 61-63 попадают на вторые входы элементов 56.i.j и 57.i.j.

Код числа два с выхода счетчика 29 поступает на управляющие входы первого 15, второго 16 и третьего 17 мультиплексоров выбора элемента. Так как на разрешающем входе мультиплексора 17 присутствует единица, то поступивший на его управляющий вход код числа два пропускает единичное значение с выхода триггера 41.2. Если он находится в единичном состоянии, то на выходе мультиплексора 17 появляется единичный импульс. Единичный сигнал с выхода мультиплексора 17 поступает на входы разрешения выдачи счетчиков 37 и 38, разрешая появление кодов на их выходах. В результате этого на входе дешифратора 25 появляется код числа двойки («00…10»), поэтому на первом его выходе появляется единичный сигнал, который поступает на второй вход элемента 56.i.1 (i=1, 2, …, m) И МС. Одновременно с этим на втором выходе дешифратора 26 появляется единичный сигнал, который поступает на второй вход элемента 57.i.2 (i=1, 2, …, m) И МС.

К этому времени на выходе счетчика 32 уже присутствует код «00…01», который поступает на вход дешифратора 27, поэтому на первом его выходе появляется единичный сигнал. Этот сигнал поступает на первые входы элементов 58 И и 61 И, но так как сигнал прерывания со счетчика 38 был, то единичный сигнал, проходя через инвертор 49, становится нулевым и попадает на второй ход элемента 58 И, тем самым запрещая подачу сигнала дальше, а на второй вход элемента 61 И попадает единичный сигнал, разрешая подачу сигнала дальше. С элемента 61 И сигнал попадает на элементы 56.1.j и 57.2.j. Так как положительный сигнал на первом входе присутствует только у элементов 56.1.2 и 57.2.1, через них и проходит положительный сигнал на соответствующие элементы 46.1.2 и 46.2.1 ИЛИ и поступают на счетные входы счетчиков 44.1.2 и 44.2.1, увеличивая их содержимое на единицу. Таким образом происходит фиксация дуги в правой диагонали МС.

Так продолжается до тех пор, пока не произойдет переполнение либо счетчика 29, либо счетчика 37. Переполнение счетчика 29 произойдет в том случае, если его содержимое превысит код числа n. В этом случае на выходе переполнения появляется единичный импульс, который поступает на счетный вход счетчика 28 строк и увеличивает его содержимое по переднему фронту на единицу, устанавливая в нем код двойки («00…010»). Код числа два поступает на вход дешифратора 18 и на установочный вход счетчика 29, устанавливая в нем начальное значение, равное коду двойки («00…010»). На втором выходе дешифратора 18 появляется единичный импульс, который поступает на управляющие входы блока 43.2 элементов запрета, разрешая тем самым прохождение сигналов с индикаторных выходов элементов второй строки матрицы 1, которые проходят через соответствующие входы группы 45.1-45.m элементов ИЛИ и поступают на соответствующие S-входы группы 41.1-41.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. Далее работа происходит так, как описано выше.

Переполнение первого счетчика 37 фиксируемой дуги означает, что фиксация дуг исходного графа в правых диагоналях МС закончена. Сигнал с выхода переполнения счетчика 37 поступает на S-вход триггера 40, сбрасывая в состояние логической единицы. Тогда на его прямом выходе будет присутствовать единичный сигнал, а на инверсном - нулевой. Нулевой сигнал с инверсного выхода триггера 40 поступает на разрешающий вход мультиплексора 17 и запрещает прохождение сигналов на его выход. С прямого выхода триггера 40 единичный сигнал попадает на второй вход элемента 66 И, разрешая прохождение импульса на элементы 64 и 65 И.

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

К этому времени во втором сумматоре 42 будет содержаться искомое суммарное значение нижней оценки, на входы которых уже поступили соответствующие коды с выходов счетчиков 44.i.j (i=1, 2, …, m, j=1, 2, …, n) матрицы 44.i.j (i=1, 2, …, m, j=1, 2, …, n) счетчиков фиксированных дуг. Суммарное значение нижней оценки с выхода сумматора 42 поступает на выход 70 значения нижней оценки с последующей подачей на ВУУ для дальнейшей обработки.

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