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

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

Иллюстрации

Показать все

Реферат

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

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. СССР 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=<X,E>,

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

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

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

МС отображается однородной средой, которой ставится в соответствие топологическая модель в виде графа H=<P,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) присутствует код нуля («00…00»). В счетчике 26 и 27 присутствует код единицы («00…01»). Единичное значение с выхода счетчика 26 подается на вход дешифратора 18, поэтому на первом его выходе присутствует единый сигнал, который подаются на соответствующие управляющие входы первого блока 39.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. Эти сигналы проходят через группу 41.1-41.m элементов ИЛИ, и поступают на соответствующие S-входы группы 37.1-37.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. В счетчике 30 и 34 содержится код двойки («00…010»), в счетчиках 29, 33 - код единицы («00…01»). Во втором сумматоре 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, увеличивая его содержимое по переднему фронту до кода единицы («00…01»). Тот же импульс попадает на первый вход элемента 43 ИЛИ. Положительный импульс поступает на счетный вход счетчика 27 и увеличивает его содержимое по переднему фронту до кода двойки («00…010»).

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

К этому времени на выходе счетчика 28 уже присутствует код «00…01», который поступает на вход дешифратора 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 по переднему фронту будет установлен код двойки («00…010»), а в счетчике 27 по переднему фронту установится код числа три («00…011»). Код тройки с выхода счетчика 27 поступит на управляющие входы мультиплексоров 15, 16 и 17. На разрешающем входе мультиплексора 15 присутствует единичный сигнал, который разрешает поступление сигналов на его выход. Если на выходе триггера 37.3 присутствует единичный сигнал (это означ