Патент на изобретение №2398270

(54) УСТРОЙСТВО ПОИСКА НИЖНЕЙ ОЦЕНКИ РАЗМЕЩЕНИЯ В ПОЛНОСВЯЗНЫХ МАТРИЧНЫХ СИСТЕМАХ ПРИ ОДНОНАПРАВЛЕННОЙ ПЕРЕДАЧЕ ИНФОРМАЦИИ

(57) Реферат:

Изобретение относится к области вычислительной техники и предназначено для моделирования задач при проектировании вычислительных систем (ВС). Техническим результатом является расширение функциональных возможностей. Устройство содержит матрицу из 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.j) (i=1,2,,m, 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-м входом первого сумматора, выходы которых соединены с выходом максимальной длины ребра устройства и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов 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=l,2,,n) элементов ИЛИ, первая матрица (i.j) (i=1,2, m, j=1,2, n), вторая матрица (i.j) (i=1,2,,m, j=1,2,,n), третья матрица (i.j) (i=l,2,,m, j=l,2,,n), четвертая матрица (i.j) (i=1,2,,m, j=1,2, n), пятая матрица (i.j) (i=1,2, m, j=1,2,,n), шестая матрица (i.j) (i=1,2,,m, j=1,2,,n) элементов И, элемент ИЛИ, первый и второй инверторы, первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой, девятый и десятый элементы И, группа m элементов ИЛИ, причем вход запуска устройства соединен с генератором импульсов, выход которого соединен с первым входом третьего элемента И, второй вход которого подключен к прямому выходу второго триггера, выход третьего элемента И подключен ко второму входу четвертого элемента И, к первому входу второго элемента И и ко второму входу первого элемента И, к первому входу четвертого элемента И подключен выход генератора, причем выход четвертого элемента И подключен ко входу второго элемента ИЛИ, выход которого подсоединен к первому входу первого элемента ИЛИ и счетному входу третьего счетчика, выход переполнения которого подключен к счетным входам третьего и четвертого счетчиков инцидентной вершины, выход третьего счетчика подключен ко входу третьего дешифратора фиксируемой дуги, выходы с 1 по m-й которого подключены к соответствующим первым входам пятого, шестого, седьмого, восьмого, девятого и десятого элементов И, ко вторым входам восьмого, девятого и десятого элементов И подсоединен выход третьего инвертора, ко вторым входам пятого, шестого и седьмого элемента И подсоединен выход переполнения четвертого счетчика инцидентной вершины, который также подсоединен ко входу третьего инвертора, выходы пятого, шестого, седьмого элемента И подключены к первым входам элементов (i.j) и (i.j) (i=1,2,,m, j=1,2,m) И, выходы восьмого, девятого и десятого элементов И подсоединены к первым входам элементов (i.j) и (i.j) (i=1,2,,m, j=1,2,,m) И, выход переполнения четвертого счетчика подключен к входу сброса третьего счетчика, входы размещения третьего и четвертого счетчиков подключены к выходу третьего мультиплексора выбора элемента, выходы третьего и четвертого счетчиков подсоединены к входам третьего и четвертого дешифраторов, выходы с 1-го по m-й третьего дешифратора подсоединены к первому входу (i.j) и (i.j) элемента (i=1,2,,m, j=1,2,,m) И, выходы четвертого дешифратора с 1-го по m-й подсоединены ко второму входу (i.j) и (i.j) элемента (i=1,2,,m, j=1,2,m) И, инверсный выход второго триггера подсоединен к разрешающему входу третьего мультиплексора, S вход второго триггера подключен к выходу переполнения третьего счетчика, R вход второго триггера подключен к выходу переполнения второго счетчика инцидентной вершины, входы с 1 по m-й третьего мультиплексора подключены к соответствующим выходам группы m триггеров, управляющий вход третьего мультиплексора подключен к выходу счетчика столбцов, второй вход второго элемента И подключен к разрешающему входу второго мультиплексора выбора элемента и к прямому выходу первого триггера режима, инверсный выход которого соединен с разрешающим входом первого мультиплексора выбора элемента и с первым входом первого элемента И, выход которого подключен к счетному входу первого счетчика фиксируемой дуги и к первому входу элемента ИЛИ, выход второго элемента И соединен со вторым входом первого элемента ИЛИ и входом разрешения второго счетчика инцидентной вершины соответственно, S-вход первого триггера режима подключен к выходу переполнения первого счетчика инцидентной вершины, счетный вход второго счетчика фиксируемой дуги подключен к входу сброса второго счетчика инцидентной вершины счетный вход которого соединен с выходом второго мультиплексора выбора элемента, управляющий вход которого подключен к управляющему входу первого мультиплексора выбора элемента и к выходу счетчика столбцов, счетный вход которого соединен с выходом первого элемента ИЛИ, установочный вход счетчика столбцов подключен к выходу счетчика строк и к входу дешифратора выбора строки, выход переполнения счетчика строк соединен с выходом переполнения устройства, выходы с 1-го по n-й дешифратора выбора строки соединены с соответствующими управляющими входами группы m элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы групп m элементов запрета соединены с соответствующими входами групп m элементов ИЛИ, соответствующие выходы которых подключены к соответствующим S-входам группы m RS-триггеров, соответствующие R-входы которых подсоединены к выходу переполнения счетчика столбцов и к счетному входу счетчика строк, выходы группы из m триггеров подключены к соответствующим входам первого, второго и третьего мультиплексоров выбора элемента, выход первого мультиплексора выбора элемента подключен к входу разрешения выдачи первого счетчика инцидентной вершины, соответствующий счетный вход которого подключен к выходу переполнения первого счетчика фиксируемой дуги, выход которого соединен со входом первого дешифратора фиксируемой дуги, i-й выход (i=1,2,,m) которого подключен к соответствующим первым входам (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) счетчиков фиксированных дуг, выходы которых соединены с соответствующими входами второго сумматора, выход которого подключен к выходу значения нижней оценки устройства.

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

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

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

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

множество вершин графа G, вершины X_qkX которого соответствуют подзадачам (подалгоритмам), а дуги связей между ними e_ijЕ при i,j=(q-1)·n+k взвешиваются объемами данных m_ij, передаваемыми между

задачами и сведенными в матрицу обмена информацией (МОИ)

M=||m_ij||_N×N, где N=n²=|Х|

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

,

,v>

базового блока, организованных в матрицу |Р|n×n, где

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

Размещение пакета программ (комплекса задач), описываемых графом G в параллельной системе (ПС), может быть аналитически описано отображением

где

Здесь s – это номер очередной перестановки, соответствующий s-му варианту размещения. Мощность множества всевозможных отображений равна числу всевозможных перестановок задач {х_qk} в матрице X: ||=N!.

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

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

Сущность предлагаемой нижней оценки размещения поясняется фиг.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 устройства, а также дополнительно введенный блок 62 поиска нижней оценки, содержащий генератор 14 импульсов, первый 15, второй 16 и третий 17 мультиплексоры выбора элемента, дешифратор 18 выбора строки, первый 19, второй 21, третий 23 и четвертый 24 дешифраторы инцидентной вершины, первый 20, второй 22 и третий 25 дешифраторы фиксируемой дуги, счетчик 26 строк, счетчик 27 столбцов, первый 28, второй 29 и третий 31 счетчик фиксируемой дуги, первый 30, второй 32, третий 33 и четвертый 34 счетчики инцидентной вершины, первый 35 и второй 36 триггеры режима, группу из 37.1-37.m триггеров, второй 38 сумматор, группу из 39.1, 39.2,, 39.m блоков элементов запрета, матрица 40.i.j (i=1,2,,m, j=1,2,,n) счетчиков фиксированных дуг, матрица 42.i.j (i=1,2,, m, j=1,2,,n) элементов ИЛИ, первая матрица 46.i.j (i=l,2,,m, j=1,2,,n), вторая матрица 47.i.j (i=1,2,,m, j=l,2,,n), третья матрица 48.i.j (i=l,2,,m, j=1,2,,n), четвертая матрица 49.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) элементов И, 43 элемент ИЛИ, первый 44 и второй 45 инверторы, первый 58, второй 59, третий 60, четвертый 61, пятый 52, шестой 53, седьмой 54, восьмой 55, девятый 56 и десятый 57 элементы И, группа 41.1, 41.2-41.m элементов ИЛИ, причем вход 63 запуска устройства соединен с генератором 14 импульсов, выход которого соединен с первым входом третьего 60 элемента И, второй вход которого подключен к прямому выходу второго 36 триггера, выход третьего 60 элемента И подключен ко второму входу четвертого 61 элемента И, к первому входу второго 59 элемента И и ко второму входу первого 58 элемента И, к первому входу четвертого 61 элемента И подключен выход генератора 14, причем выход четвертого 61 элемента И подключен ко входу второго 44 элемента ИЛИ, выход которого подсоединен к первому входу первого 43 элемента ИЛИ и счетному входу третьего 31 счетчика, выход переполнения которого подключен к счетным входам третьего 33 и четвертого 34 счетчиков инцидентной вершины, выход третьего 31 счетчика подключен ко входу третьего 25 дешифратора фиксируемой дуги, выходы с 1 по m-й которого подключены к соответствующим первым входам пятого 52, шестого 53, седьмого 54, восьмого 55, девятого 56 и десятого 57 элементов И, ко вторым входам восьмого 55, девятого 56 и десятого 57 элементов И подсоединен выход третьего 45 инвертора, ко вторым входам пятого 52, шестого 53 и седьмого 54 элемента И подсоединен выход переполнения четвертого 34 счетчика инцидентной вершины, который также подсоединен ко входу третьего 45 инвертора, выходы пятого 52, шестого 53, седьмого 54 элемента И подключены к первым входам элементов 48.i.j и 49.i.j (i=1,2,m, j=1,2,,m) И, выходы восьмого 55, девятого 56 и десятого 57 элементов И подсоединены к первым входам элементов 50.i.j и 51.i.j (i=1,2,,m, j=1,2,,m) И, выход переполнения четвертого 34 счетчика подключен к входу сброса третьего 33 счетчика, входы размещения третьего 33 и четвертого 34 счетчиков подключены к выходу третьего 17 мультиплексора выбора элемента, выходы третьего 33 и четвертого 34 счетчиков подсоединены к входам третьего 23 и четвертого 24 дешифраторов, выходы с 1-го по m-й третьего 23 дешифратора подсоединены к первому входу 50.i.j и 48.i.j элемента (i=1, 2,,m, j=1, 2,, m) И, выходы четвертого 24 дешифратора с 1-го по m-й подсоединены ко второму входу 49.i.j и 51.i.j элемента (i=1, 2,,m, j=1, 2,,m) И, инверсный выход второго 36 триггера подсоединен к разрешающему входу третьего 17 мультиплексора, S вход второго 36 триггера подключен к выходу переполнения третьего 33 счетчика, R вход второго 36 триггера подключен к выходу переполнения второго 29 счетчика инцидентной вершины, входы с 1 по m-й третьего 17 мультиплексора подключены к соответствующим выходам группы 37.1-37.m триггеров, управляющий вход третьего 17 мультиплексора подключен к выходу счетчика 27 столбцов, второй вход второго 59 элемента И подключен к разрешающему входу второго 16 мультиплексора выбора элемента и к прямому выходу первого 35 триггера режима, инверсный выход которого соединен с разрешающим входом первого 15 мультиплексора выбора элемента и с первым входом первого 58 элемента И, выход которого подключен к счетному входу первого 28 счетчика фиксируемой дуги и к первому входу элемента 43 ИЛИ, выход второго 59 элемента И соединен со вторым входом первого 43 элемента ИЛИ и входом разрешения второго 32 счетчика инцидентной вершины соответственно, S-вход первого 35 триггера режима подключен к выходу переполнения первого 30 счетчика инцидентной вершины, счетный вход второго 29 счетчика фиксируемой дуги подключен к входу сброса второго 32 счетчика инцидентной вершины счетный вход которого соединен с выходом второго 16 мультиплексора выбора элемента, управляющий вход которого подключен к управляющему входу первого 15 мультиплексора выбора элемента и к выходу счетчика 27 столбцов, счетный вход которого соединен с выходом первого 43 элемента ИЛИ, установочный вход счетчика 27 столбцов подключен к выходу счетчика 26 строк и к входу дешифратора 18 выбора строки, выход переполнения счетчика 26 строк соединен с выходом переполнения устройства 65, выходы с 1-го по n-й дешифратора 18 выбора строки соединены с соответствующими управляющими входами группы 39.1-39.m элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы групп 39.1-39.m элементов запрета соединены с соответствующими входами групп 41.1-41.m элементов ИЛИ, соответствующие выходы которых подключены к соответствующим S-входам группы 37.1-37.m RS – триггеров, соответствующие R-входы которых подсоединены к выходу переполнения счетчика 27 столбцов и к счетному входу счетчика 26 строк, выходы группы из m триггеров подключены к соответствующим входам первого 15, второго 16 и третьего 17 мультиплексоров выбора элемента, выход первого 15 мультиплексора выбора элемента подключен к входу разрешения выдачи первого 30 счетчика инцидентной вершины, соответствующий счетный вход которого подключен к выходу переполнения первого 28 счетчика фиксируемой дуги, выход которого соединен со входом первого 20 дешифратора фиксируемой дуги, i-й выход (i=1,2,,m) которого подключен к соответствующим первым входам 46.i.j (i=1,2,,m, j=1,2,,n) элементов И, выход второго 29 счетчика фиксируемой дуги подключен ко входу второго 22 дешифратора фиксируемой дуги, соответствующий j-й (j=1,2,n) выход которого соединен со вторыми входами 47.i.j элементов (i=1,2,m, j=1,2,n) И, выход второго 32 счетчика инцидентной вершины подключен к входу второго 21 дешифратора инцидентной вершины, соответствующий i-й (i=1,2,,m) выход которого подключен к соответствующему первому входу 47.i.j элемента (1=1,2,,m, j=1,2,,n) И, первый 30 счетчик инцидентной вершины соединен с входом первого 19 дешифратора инцидентной вершины, соответствующий i-й (1=1,2,,m) выход которого подключен ко второму входу 46.i.j элемента (1=1,2,,m, j=1,2,,n) И, выходы первого 46.i.j, второго 47.i.j, третьего 48.i.j, четвертого 49 i.j, пятого 50.i.j, шестого 51.i.j подключены к соответствующим входам элементов 42.i.j ИЛИ, соответствующие выходы которых подсоединены к соответствующим счетным входам 40.i.j счетчиков фиксированных дуг, выходы которых соединены с соответствующими входами второго 38 сумматора, выход которого подключен к выходу 64 значения нижней оценки устройства.

Назначение элементов и блоков устройства поиска нижней оценки размещения в матричных сетях (фиг.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, второй 21, третий 23 и четвертый 24 дешифраторы инцидентной вершины предназначены для выбора очередной фиксируемой дуги, инцидентной текущим вершинам графа. Первый 19 дешифратор выбирает дугу для фиксации в строке МС, второй 21 дешифратор инцидентной вершины выбирают дугу для фиксации в столбце, третий 23 и четвертый 24 дешифраторы инцидентной вершины выбирает дугу для фиксации в диагоналях МС.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Группа 41.1-41.m элементов ИЛИ служат для объединения сигналов с выходов группы элементов 39.1-39.m запрета соответственно.

Матрица 42.i.j элементов ИЛИ предназначена для объединения сигналов с выходов матрицы 46.i.j, 47.i.j, 48.i.j, 49.i.j, 50.i.j, 51. i.j элементов И с последующей подачей на вход счетчика 40. i.j фиксированных дуг. Здесь i=1,2,,m,j=1,2,,n.

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

Элемент 43 ИЛИ предназначен для объединения сигналов с выходов первого 58, второго 59 и третьего 61 элементов И.

Первый 58, второй 59, третий 60 и четвертый 61 элементы И служат для подачи тактового импульса с генератора 14 импульсов в зависимости от значения прямого выхода второго 36 триггера режима соответственно будет работать распределение диагоналей, строк или столбцов, в зависимости от значения первого 35 триггера режима либо на первый 28 счетчик фиксируемой дуги и на первый вход элемента 43 ИЛИ, либо на второй вход элемента 43 ИЛИ и на вход разрешения выдачи второго 32 счетчика инцидентной вершины, либо на третий 31 счетчик инцидентной вершины диагоналей соответственно.

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

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

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

Инвертор 45 предназначен для активации элементов 55, 56, 57 элементов И.

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

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

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

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

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

Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения, соответствующий матрице смежности исходного графа. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. Группа 37.1-37.m триггеров находится в состоянии логического нуля. Триггер 35 режима находится в состоянии логического нуля, поэтому на прямом его выходе присутствует нулевой потенциал, а на инверсном – единичный. Триггер 36 находится в состоянии логической единицы и тогда в счетчиках матрицы 40.i.j (i=1,2,,m, j=1,2,,n) присутствует код нуля («0000»). В счетчике 26 и 27 присутствует код единицы («0001»). Единичное значение с выхода счетчика 26 подается на вход дешифратора 18, поэтому на первом его выходе присутствует единый сигнал, который подаются на соответствующие управляющие входы первого блока 39.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. Эти сигналы проходят через группу 41.1-41.m элементов ИЛИ, и поступают на соответствующие S-входы группы 37.1-37.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. В счетчике 30 и 34 содержится код двойки («00010»), в счетчиках 29, 33 – код единицы («0001»). Во втором сумматоре 38 и в счетчиках 28, 31 и 32 содержится код нуля.

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

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

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

Так как триггер 35 режима находится в состоянии логического нуля, то на его инверсном выходе присутствует единичный сигнал, который поступает на первый вход элемента 58 И и на разрешающий вход первого мультиплексора 15 выбора элемента. Единичный сигнал с прямого выхода триггера 36 поступает на второй вход элемента 60, разрешая прохождение импульса с генератора 14 на вторые входы элементов 58 и 59. В результате появления импульса на втором входе элемента 58 И на его выходе появляется единичный импульс, который поступает на счетный вход счетчика 28, увеличивая его содержимое по переднему фронту до кода единицы («0001»). Тот же импульс попадает на первый вход элемента 43 ИЛИ. Положительный импульс поступает на счетный вход счетчика 27 и увеличивает его содержимое по переднему фронту до кода двойки («00010»).

Код числа два с выхода счетчика 27 поступает на управляющие входы первого 15, второго 16 и третьего 17 мультиплексоров выбора элемента. Так как на разрешающем входе мультиплексора 15 присутствует единица, то поступивший на его управляющий вход код числа два пропускает единичное значение с выхода триггера 37.2. Если он находится в единичном состоянии, то на выходе мультиплексора 15 появляется единичный импульс. Единичный сигнал с выхода мультиплексора 15 поступает на входы разрешения выдачи счетчика 30, разрешая появление кодов на их выходах. В результате этого на входе дешифратора 19 появляется код числа два («00010»), поэтому на втором его выходе появляется единичный сигнал, который поступает на второй вход элемента 46.i.2 (i=1,2,,m) И МС.

К этому времени на выходе счетчика 28 уже присутствует код «0001», который поступает на вход дешифратора 20, поэтому на первом его выходе появляется единичный сигнал. Этот сигнал поступает на первые входы элементов 46.1.j (j=i,2,,n) И МС (фиг.1). Таким образом, на выходе элемента 46.1.2 И появляются единичные сигналы, которые проходят через соответствующий элемент 42.1.2 ИЛИ и поступает на счетный вход счетчика 40.1.2, увеличивая его содержимое на единицу. Таким образом происходит фиксация дуги в первой строке МС.

Очередной тактовый импульс поступает на второй вход элемента 58 И и на первый вход элемента 59 И. Так как на первом входе элемента 58 И присутствует единичный импульс с инверсного выхода триггера 35, на выходе элемента 58 И появляется положительный импульс, который поступает на счетный вход счетчика 28 и на элемент 43 ИЛИ, проходя на счетный вход счетчика 27. В результате в счетчике 28 по переднему фронту будет установлен код двойки («00010»), а в счетчике 27 по переднему фронту установится код числа три («00011»). Код тройки с выхода счетчика 27 поступит на управляющие входы мультиплексоров 15, 16 и 17. На разрешающем входе мультиплексора 15 присутствует единичный сигнал, который разрешает поступление сигналов на его выход. Если на выходе триггера 37.3 присутствует единичный сигнал (это означает наличие дуги в графе), то на выходе мультиплексора 15 появится единичный импульс, который поступит на вход разрешения выдачи счетчика 30. На входе дешифратора 19 появится код двойки с выхода счетчика 30. Соответственно на втором выходе дешифратора 19 появится единичный сигнал. Единичный сигнал со второго выхода дешифратора 19 поступит на второй вход элемента 46.i.2 (i=1,2,,m) И МС.

Код «00010» с выхода счетчика 28 поступает на вход дешифратора 20 и возбуждает на его втором выходе положительный импульс, который в свою очередь поступает на первый вход элемента 46.2.j (i=1,2,n) И. Таким образом, на выходе элемента 46.2.2 появится единый сигнал, который пройдет через соответствующий элемент 42.2.2 ИЛИ и увеличит по переднему фронту содержимое счетчика 40.2.2 на единицу, фиксируя тем самым очередную дугу рассматриваемого графа.

Так происходит до тех пор, пока не произойдет переполнение содержимого счетчика 28. Такая ситуация возникнет в том случае, когда содержимое счетчика >m. В этом случае на выходе переполнения счетчика 28 появится единичный импульс, а его содержимое сбрасывается в единицу. Импульс с выхода переполнения счетчика 28 поступит на счетный вход счетчика 30, увеличивая его содержимое по переднему фронту на единицу. Таким образом в счетчике 30 установится код числа три («00011»). В это время содержимое счетчика 27 будет увеличено по переднему фронту на единицу до кода четырех («000100»). После этого фиксация дуг повторяется так, как описано выше.

Так продолжается до тех пор, пока не произойдет переполнение либо счетчика 27 либо счетчика 30. Переполнение счетчика 27 произойдет в том случае, если его содержимое превысит код числа n. В этом случае на выходе переполнения появляется единичный импульс, который поступает на счетный вход счетчика 26 строк и увеличивает его содержимое по переднему фронту на единицу, устанавливая в нем код двойки («00010»). Код числа два поступает на вход дешифратора 18 и на установочный вход счетчика 27, устанавливая в нем начальное значение, равное коду двойки («00010»). На втором выходе дешифратора 18 появляется единичный импульс, который поступает на управляющие входы блока 39.2 элементов запрета, разрешая тем самым прохождение сигналов с индикаторных выходов элементов второй строки матрицы 1, которые проходят через соответствующие входы группы 41.1-41.m элементов ИЛИ и поступают на соответствующие S-входы группы 37.1-37.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. Далее работа происходит так, как описано выше.

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

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

К этому времени на управляющих входах мультиплексоров 15, 16 и 17 появится код числа, содержащегося в счетчике 27. Так как на разрешающем входе мультиплексора 16 присутствует положительный импульс, и, если в триггере 41.j (j=1,2,,n) содержится единица, то на выходе мультиплексора 16 появится положительный импульс. Единичный сигнал с выхода мультиплексора 16 поступает на счетный вход счетчика 32, увеличивая его содержимое по переднему фронту до кода «0001» соответственно. Поэтому на входе дешифратора 21 появится код «0001». При появлении кода на входе дешифратора 21, на первом выходе дешифратора 21 возбуждается единичный импульс, который поступает на первые входы элемента 47.1.j (i=1,2,,n) И МС.

Код «0001» с выхода счетчика 27 поступает на вход дешифратора 22, и на его первом выходе появляется единичный импульс, который поступает на второй вход элемента 47.i.1 (i=1,2,,m) И МС. Таким образом, на выходе этого элемента появится единичный импульс. Тем самым обеспечивается появление положительного сигнала на входе элемента 42.2.1 ИЛИ МС, который поступает на счетный вход соответствующего счетчика 40.2.1 и по переднему фронту увеличивает их содержимое на единицу. Так происходит фиксация дуги в столбце МС.

Очередной импульс с выхода генератора 14 импульсов возбуждает импульс на выходе элемента 59 И, который поступает на счетный вход счетчика 32, и на второй вход элемента 43 ИЛИ, который проходит на счетный вход счетчика 27, увеличивая его содержимое по переднему фронту на единицу. В счетчике 32 таким образом по переднему фронту установится код числа два («00010»).

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

На первом выходе дешифратора 22 по-прежнему присутствует единичное значение, которое поступает на второй вход элемента 47.i.1 (i=1,2,,m) И МС. Таким образом на выходе элемента 47.3.1 И появится единичное значение, которое, пройдя через элемент 42.3.1 ИЛИ, поступит на вход соответствующего счетчика 40.3.1 и увеличит его содержимое по переднему фронту на единицу. Таким образом произойдет фиксация очередной дуги в столбце МС.

Так происходит до тех пор, пока содержимое счетчика 32 не станет равным m-1, свидетельствующий о том, что дуги в первом столбце МС зафиксированы и необходимо переходить к следующему столбцу. Единичный импульс с выхода переполнения счетчика 32 поступит на счетный вход счетчика 29 и по переднему фронту увеличивает его содержимое на единицу до кода двойки («00010»). После этого процесс повторяется так, как описано выше.

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

После этого прохождение импульсов с генератора 14 импульсов через элемент 59 И закрывается, так как с прямого выхода триггера 36 подается нулевой импульс на второй вход элемента 60 И, а открывается через элемент 61 И, так как на его втором входе появится нулевое значение, проходящее потом через инвертор 44. На разрешающем входе мультиплексора 17 появится единичное значение, которое разрешает появление импульсов на его выходе, а на разрешающем входе мультиплексоров 15 и 16 появляется нулевое значение, которое запрещает появление импульсов на выходе этих мультиплексоров. Единичный импульс с элемента 44 попадает на счетный вход элемента 31, устанавливая его значение в единицу («0001») и на первый вход элемента 43 ИЛИ, положительный импульс поступает на счетный вход счетчика 27 и увеличивает его содержимое по переднему фронту до кода двойки («00010»).

Код числа два с выхода счетчика 27 поступает на управляющие входы первого 15, второго 16 и третьего 17 мультиплексоров выбора элемента. Так как на разрешающем входе мультиплексора 17 присутствует единица, то поступивший на его управляющий вход код числа два пропускает единичное значение с выхода триггера 37.2. Если он находится в единичном состоянии, то на выходе мультиплексора 17 появляется единичный импульс. Единичный сигнал с выхода мультиплексора 17 поступает на входы разрешения выдачи счетчиков 33 и 34, разрешая появление кодов на их выходах. В результате этого на входе дешифратора 23 появляется код числа единицы («0001»), поэтому на первом его выходе появляется единичный сигнал, который поступает на второй вход элемента 48.i.1 (i=1,2,.m) И МС. Одновременно с этим на втором выходе дешифратора 24 появляется единичный сигнал, который поступает на второй вход элемента 49.i.2 (i=1,2,,m) И МС.

К этому времени на выходе счетчика 31 уже присутствует код «0001», который поступает на вход дешифратора 25, поэтому на первом его выходе появляется единичный сигнал. Этот сигнал поступает на первые входы элементов 52 И и 55 И, но так как сигнала прерывания со счетчика 34 еще не было, то нулевой сигнал, проходя через инвертор 45, становится единичным и попадает на второй ход элемента 52 И, тем самым разрешая подачу сигнала дальше. С элемента 52 И сигнал попадает на элементы 48.1.j и 49.1.j. Так как положительный сигнал на первом входе присутствует только у элементов 48.1.1 и 49.2.2 через них и проходит положительный сигнал на соответствующие элементы 42.1.1 и 42.2.2 ИЛИ и поступают на счетные входы счетчиков 40.1.1 и 40.2.2, увеличивая их содержимое на единицу. Таким образом происходит фиксация дуги в первой строке МС.

Очередной тактовый импульс поступает на второй вход элемента 61 И. Импульс поступает с выхода инвертора 44 на вход элемента 43, тем самым устанавливая счетчик 27 в значение тройки («00… 11»), а счетчик 31 в значение двойки («0010»). Код тройки с выхода счетчика 27 поступит на управляющие входы мультиплексоров 15, 16 и 17. На разрешающем входе мультиплексора 17 присутствует единичный сигнал, который разрешает поступление сигналов на его выход. Если на выходе триггера 37.3 присутствует единичный сигнал (это означает наличие дуги в графе), то на выходе мультиплексора 17 появится единичный импульс, который поступит на входы разрешения выдачи счетчиков 33 и 34. Код единицы с выхода счетчика 33 поступит на вход дешифратора 23, а на входе дешифратора 24 появится код двойки с выхода счетчика 34. Соответственно на первом выходе дешифратора 23 и на втором выходе дешифратора 24 появятся единичные сигналы. Единичный сигнал с первого выхода дешифратора 23 поступит на второй вход элемента 48.i.1 (i=1,2,,m) И МС. Единичный сигнал со второго выхода дешифратора 24 поступит на второй вход элемента 49.i.2 (i=1,2,,m) И МС.

Код «00010» с выхода счетчика 31 поступает на вход дешифратора 25 и возбуждает на его втором выходе положительный импульс, который в свою очередь поступает на первые входы элементов 48.2.j (i=1,2,,n) и 49.2.j (i=1,2,,n) И через элементы 52-54 И. Таким образом, на выходе элементов 48.2.1 и 49.3.2 появятся единые сигналы, которые пройдут через соответствующие элементы 42.2.1 и 42.3.2 ИЛИ и увеличат по переднему фронту содержимое счетчиков 40.2.1 и 40.3.2 на единицу, фиксируя тем самым очередную дугу рассматриваемого графа.

Так происходит до тех пор, пока не произойдет переполнение содержимого счетчика 34. Такая ситуация возникнет в том случае, когда содержимое счетчика >m. В этом случае на выходе переполнения счетчика 34 появится единичный импульс, а его содержимое сбрасывается в единицу. Импульс с выхода переполнения счетчика 34 поступит на вход сброса счетчика 33, обнуляя его и устанавливая его содержимое в двойку («0010»), а в счетчике 34 установится код числа единицы («0001»). В это время содержимое счетчика 27 будет увеличено по переднему фронту на единицу до кода четырех («000100»).

После этого происходит фиксация правых диагоналей. Так как единичный сигнал с выхода переполнения счетчика 34 попал на вход счетчика 33, параллельно он попадает на вторые входы элементов 55-57 И, тем самым разрешая фиксацию правых диагоналей. Единичный сигнал, проходящий через инвертор 45, становится нулевым и, попадая на вторые входы элементов 52-54 И, запрещает фиксацию левых диагоналей. Импульсы с выходов элементов 55-57 попадают на вторые входы элементов 50.i.j и 51.i.j.

Код числа два с выхода счетчика 27 поступает на управляющие входы первого 15, второго 16 и третьего 17 мультиплексоров выбора элемента. Так как на разрешающем входе мультиплексора 17 присутствует единица, то поступивший на его управляющий вход код числа два пропускает единичное значение с выхода триггера 37.2. Если он находится в единичном состоянии, то на выходе мультиплексора 17 появляется единичный импульс. Единичный сигнал с выхода мультиплексора 17 поступает на входы разрешения выдачи счетчиков 33 и 34, разрешая появление кодов на их выходах. В результате этого на входе дешифратора 23 появляется код числа двойки («0010»), поэтому на первом его выходе появляется единичный сигнал, который поступает на второй вход элемента 50.i.1 (i=1,2,,m) И МС. Одновременно с этим на втором выходе дешифратора 24 появляется единичный сигнал, который поступает на второй вход элемента 51 i.2 (i=1,2,,m) И МС.

К этому времени на выходе счетчика 31 уже присутствует код «0001», который поступает на вход дешифратора 25, поэтому на первом его выходе появляется единичный сигнал. Этот сигнал поступает на первые входы элементов 52 И и 55 И, но так как сигнал прерывания со счетчика 34 был, то единичный сигнал, проходя через инвертор 45, становится нулевым и попадает на второй ход элемента 52 И, тем самым запрещая подачу сигнала дальше, а на второй вход элемента 55 И попадает единичный сигнал, разрешая подачу сигнала дальше. С элемента 55 И сигнал попадает на элементы 50.1.j и 51.2.j. Так как положительный сигнал на первом входе присутствует только у элементов 50.1.2 и 51.2.1 через них и проходят положительные сигналы на соответствующие элементы 42.1.2 и 42.2.1 ИЛИ и поступают на счетные входы счетчиков 40.1.2 и 40.2.1, увеличивая их содержимое на единицу. Таким образом происходит фиксация дуги в правой диагонали МС.

Так продолжается до тех пор, пока не произойдет переполнение либо счетчика 27, либо счетчика 33. Переполнение счетчика 27 произойдет в том случае, если его содержимое превысит код числа n. В этом случае на выходе переполнения появляется единичный импульс, который поступает на счетный вход счетчика 26 строк и увеличивает его содержимое по переднему фронту на единицу, устанавливая в нем код двойки («00010»). Код числа два поступает на вход дешифратора 18 и на установочный вход счетчика 27, устанавливая в нем начальное значение, равное коду двойки («00010»). На втором выходе дешифратора 18 появляется единичный импульс, который поступает на управляющие входы блока 39.2 элементов запрета, разрешая тем самым прохождение сигналов с индикаторных выходов элементов второй строки матрицы 1, которые проходят через соответствующие входы группы 41.1-41.m элементов ИЛИ и поступают на соответствующие S-входы группы 37.1-37.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. Далее работа происходит так, как описано выше.

Переполнение первого счетчика 33 фиксируемой дуги означает, что фиксация дуг исходного графа в правых диагоналях МС закончена. Сигнал с выхода переполнения счетчика 33 поступает на S-вход триггера 36, сбрасывая в состояние логической единицы. Тогда на его прямом выходе будет присутствовать единичный сигнал, а на инверсном – нулевой. Нулевой сигнал с инверсного выхода триггера 36 поступает на разрешающий вход мультиплексора 17 и запрещает прохождение сигналов на его выход. С прямого выхода триггера 36 единичный сигнал попадает на второй вход элемента 60 И, разрешая прохождение импульса на элементы 58 и 59 И.

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

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

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

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

РИСУНКИ