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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

Исходная (размещаемая) задача (процесс, алгоритм) представляется в виде неориентированного невзвешенного графа G=<X,E>, вершины х_i∈Х которого соответствуют подзадачам (подалгоритмам), а дуги е_ij∈Е⊆Х×X задают управляющие и/или информационные связи между подзадачами.

МС отображается однородной средой, которой ставится в соответствие топологическая модель в виде графа H=<U,V>, где U - множество модулей МС, организованных в матрицу |U|_t×k, где , , m=n, V - множество межмодульных связей. Размещение графа G в МС Н будем задавать в виде отображения β=Х→U

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

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

Сущность предлагаемой нижней оценки размещения поясняется фиг.2. Здесь на фиг.2а представляет гипотетический полный неориентированный граф G, а на фиг.2б соответствующая ему матрица смежности. Модули МС на фиг.2в и 2 г представлены квадратами, в левом верхнем углы которых представлены их номера. Внутри модулей кружками обозначены вершины графа с соответствующими номерами внутри. Пунктирные линии обозначают связи модулей МС, а сплошные линии рядом с пунктирными - гипотетические зафиксированные дуги. Из фиг.2в видно, что связи между модулями 1-2 и 4-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 элементов однородной среды соединены с входом блока 2j подсчета единиц, выход которого соединен с j-м входом блока 3 нахождения максимума и j-м входом первого сумматора 4, выходы которых соединены с выходом 10 максимальной длины ребра устройства и выходом 11 суммарной длины ребер устройства соответственно, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i=1, 2,..., m) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также дополнительно введенный блок 46 поиска нижней оценки, содержащий генератор 14 импульсов, первый 15 и второй 16 мультиплексоры выбора элемента, дешифратор 17 выбора строки, первый 18, второй 22, третий 19 и четвертый 21 дешифраторы инцидентной вершины, первый 20 и второй 23 дешифратор фиксируемой дуги, счетчик 24 строк, счетчик 25 столбцов, первый 26 и второй 27 счетчик фиксируемой дуги, первый 28, второй 29, третий 30 и четвертый 31 счетчики инцидентной вершины, триггер 32 режима, группа 33.1-33.m триггеров, второй 34 сумматор, группу 35.1, 35.2,..., 35.m блоков элементов запрета, матрица 36. i.j (i=1, 2,..., m, j=1, 2,..., n) счетчиков фиксированных дуг, матрица 38.i.j (j=1, 2,..., m, j=1, 2,..., n) элементов ИЛИ, первая матрица 39.i.j (i=1, 2,..., m, j=1, 2,..., n), вторая матрица 40.i.j (i=1, 2,..., m, j=1, 2,..., n), третья матрица 41.i.j (i=1, 2,..., m, j=1, 2,..., n) и четвертая матрица 42.i.j (i=1, 2,..., m, j=1, 2,..., n) элементов И, элемент 43 ИЛИ, первый 44 и второй 45 элементы И, группа 37.1-37.m элементов ИЛИ, причем вход 47 запуска устройства соединен с генератором 14 импульсов, выход которого соединен со вторым входом первого 44 элемента И и с первым входом второго 45 элемента И, второй вход которого подключен к разрешающему входу второго мультиплексора 16 выбора элемента и к прямому выходу триггера 32 режима, инверсный выход которого соединен с разрешающим входом первого мультиплексора 15 выбора элемента и с первым входом первого элемента 44 И, выход которого подключен к счетному входу первого счетчика 26 фиксируемой дуги и к первому входу элемента 43 ИЛИ, выход второго элемента 45 И соединен со вторым входом элемента 43 ИЛИ и с входами разрешения выдачи второго 29 и четвертого 31 счетчиков инцидентной вершины соответственно, S-вход триггера 32 режима подключен к выходу переполнения третьего счетчика 30 инцидентной вершины и к входу сброса первого счетчика 28 инцидентной вершины, R-вход триггера 32 режима подсоединен к выходу переполнения второго счетчика 27 фиксируемой дуги, счетный вход которого подключен к входу сброса второго счетчика 29 инцидентной вершины и к выходу переполнения четвертого счетчика 31 инцидентной вершины, счетный вход которого соединен со счетным входом второго счетчика 29 инцидентной вершины и с выходом второго мультиплексора 16 выбора элемента, управляющий вход которого подключен к управляющему входу первого мультиплексора 15 выбора элемента и к выходу счетчика 25 столбцов, счетный вход которого соединен с выходом элемента 43 ИЛИ, установочный вход счетчика 25 столбцов подключен к выходу счетчика 24 строк и к входу дешифратора 17 выбора строки, выход переполнения счетчика 24 строк соединен с выходом 49 переполнения устройства, выходы с 1-го по n-й дешифратора 17 выбора строки соединены с соответствующими управляющими входами группы 35.1-35.m элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы группы 35.1-35.m элементов запрета соединены с соответствующими входами группы 37.1-37.m элементов ИЛИ, соответствующие выходы которых подключены к соответствующим S-входам группы 33.1-33.m триггеров, соответствующие R-входы которых подсоединены к выходу переполнения счетчика 25 столбцов и к счетному входу счетчика 24 строк, выходы группы 33.1-33.m триггеров подключены к соответствующим входам первого 15 и второго 16 мультиплексоров выбора элемента, выход первого мультиплексора 15 выбора элемента подключен к входам разрешения выдачи первого 28 и второго 30 счетчиков инцидентной вершины, соответствующие счетные входы которых подключены к выходу переполнения первого счетчика 26 фиксируемой дуги, выход которого соединен со входом первого дешифратора 20 фиксируемой дуги, i-й выход (i=1, 2,..., m) которого подключен к соответствующим первым входам элементов И 40.i.j (j=1, 2,..., n) и 41.i.j (j=1, 2,..., n) второй 40.i.j (j=1, 2,..., n) и третьей 41.i.j (j=1, 2,..., n) матриц элементов И, выход второго счетчика 27 фиксируемой дуги подключен ко входу второго дешифратора 23 фиксируемой дуги, соответствующий j-й (i=1, 2,..., n) выход которого соединен со вторыми входами элементов И 39.i.j (i=1, 2,..., m) и 42.i.j (i=1, 2,..., m) первой 39.i.j (i=1, 2,..., m) и четвертой 42.i.j (i=1, 2,..., m) матриц элементов И, выход первого 28 счетчика инцидентной вершины подключен ко входу первого дешифратора 18 инцидентной вершины, соответствующий j-й выход (j=1, 2,..., n) которого подключен к соответствующему второму входу элемента И 40.i.j (i=1, 2,..., m) второй матрицы 40.i.j (i=1, 2,..., m) элементов И, выход третьего счетчика 30 инцидентной вершины соединен со входом третьего дешифратора 19 инцидентной вершины, соответствующий j-й выход (j=1, 2,..., n) которого подключен к соответствующему второму входу элемента И 41.i.j (i=1, 2, ..., m) третьей матрицы 41.i.j (i=1, 2,..., m) элементов И, выход четвертого счетчика 31 инцидентной вершины подключен к входу четвертого дешифратора 21 инцидентной вершины, соответствующий i-й (i=1, 2,..., m) выход которого подключен к соответствующему первому входу элемента И 39.i.j (j=1, 2,..., n) первой матрицы 39.i.j (j=1, 2,..., n) элементов И, второй счетчик 29 инцидентной вершины соединен с входом второго дешифратора 22 инцидентной вершины, соответствующий i-й (i=1, 2,..., m) выход которого подключен к первому входу элемента И 42.i.j (j=1, 2,..., n) четвертой матрицы 42.i.j (j=1, 2,..., n) элементов И, выходы счетчиков 36.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицы 36.i.j (i=1, 2,..., m, j=1, 2,..., n) счетчиков фиксированных дуг соединены с соответствующими входами второго 34 сумматора, выход которого подключен к выходу 48 значения нижней оценки.

Назначение элементов и блоков устройства поиска нижней оценки размещения в матричных сетях (фиг.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 мультиплексоры выбора элемента предназначен для подачи с выходов триггеров 33.1-33.m информации о наличии дуги, инцидентной двум выбранным вершинам размещаемого графа. Этим вершинам соответствует выбранная в данный момент строка и столбец матрицы смежности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Группа 37.1-37.m элементов ИЛИ служат для объединения сигналов с выходов группы элементов 35.1-35.m запрета соответственно.

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

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

Элемент 43 ИЛИ предназначен для объединения сигналов с выходов первого 44 и второго 45 элементов И.

Первый 44 и второй 45 элементы И служат для подачи тактового импульса с генератора 14 импульсов в зависимости от значения триггера 32 режима либо на первый 26 счетчик фиксируемой дуги и на первый вход элемента 43 ИЛИ, либо на второй вход элемента 43 ИЛИ и на входы разрешения выдачи второго 29 и четвертого 31 счетчика инцидентной вершины соотствественно.

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

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

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

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

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

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

Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения, соответствующий матрице смежности исходного графа. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. Группа 33.1-33.m триггеров находится в состоянии логического нуля. Триггер 32 режима находится в состоянии логического нуля, поэтому на прямом его выходе присутствует нулевой потенциал, а на инверсном - единичный. В счетчиках матрицы 36.i.j (i=1, 2,..., m, j=1, 2,..., n) присутствует коды нуля ("00...00"). В счетчике 24 и 25 присутствует код единицы ("00...01"). Единичное значение с выхода счетчика 24 подается на вход дешифратора 17, поэтому на первом его выходе присутствует единый сигнал, который подаются на соответствующие управляющие входы первого блока 35.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. Эти сигналы проходят через группу 37.1-37.m элементов ИЛИ, и поступают на соответствующие S-входы группы 33.1-33.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. В счетчике 30 содержатся код двойки ("00...010"), в счетчиках 27, 28 и 31 - код единицы ("00...01"). Во втором сумматоре 34 и в счетчиках 26 и 29 содержится код нуля.

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

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

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

Так как триггер 32 режима находится в состоянии логического нуля, то на его инверсном выходе присутствует единичный сигнал, который поступает на первый вход элемента 44 И и на разрешающий вход первого мультиплексора 15 выбора элемента. В результате появления тактового импульса на втором входе элемента 44 И на его выходе появляется единичный импульс, который поступает на счетный вход счетчика 26, увеличивая его содержимое по переднему фронту до кода единицы ("00...01"). Тот же импульс попадает на первый вход элемента 43 ИЛИ. Положительный импульс поступает на счетный вход счетчика 25 и увеличивает его содержимое по переднему фронту до кода двойки ("00...010").

Код числа два с выхода счетчика 25 поступает на управляющие входы первого 15 и второго 16 мультиплексоров выбора элемента. Так как на разрешающем входе мультиплексора 15 присутствует единица, то поступивший на его управляющий вход код числа два пропускает единичное значение с выхода триггера 33.2. Если он находится в единичном состоянии, то на выходе мультиплексора 15 появляется единичный импульс. Единичный сигнал с выхода мультиплексора 15 поступает на входы разрешения выдачи счетчиков 28 и 30, разрешая появление кодов на их выходах. В результате этого на входе дешифратора 19 появляется код числа два ("00...010"), поэтому на втором его выходе появляется единичный сигнал, который поступает на второй вход элемента 41.i.j (i=1, 2,..., m) И МС. Одновременно с этим на первом выходе дешифратора 18 появляется единичный сигнал, который поступает на второй вход элемента 40.j.1 (i=1, 2,..., m) И МС.

К этому времени на выходе счетчика 26 уже присутствует код "00...01", который поступает на вход дешифратора 20, поэтому на первом его выходе появляется единичный сигнал. Этот сигнал поступает на первые входы элементов 40.1.j (j=1, 2,..., n) и 41.1.j (j=1, 2,..., n) И МС (фиг.1). Таким образом, на выходах элементов 40.1.1 и 41.1.2 И появляются единичные сигналы, которые проходят через соответствующие элементы 38.1.1 и 38.1.2 ИЛИ и поступают на счетные входы счетчиков 38.1.1 и 38.1.2, увеличивая их содержимое на единицу. Таким образом происходит фиксация дуги в первой строке МС.

Очередной тактовый импульс поступает на второй вход элемента 44 И и на первый вход элемента 45 И. Так как на первом входе элемента 44 И присутствует единичный импульс с инверсного выхода триггера 32, на выходе элемента 44 И появляется положительный импульс, который поступает на счетный вход счетчика 26 и на элемент 43 ИЛИ, проходя на счетный вход счетчика 25. В результате в счетчике 26 по переднему фронту будет установлен код двойки ("00...010"), а в счетчике 25 по переднему фронту установится код числа три ("00...011"). Код тройки с выхода счетчика 25 поступит на управляющие входы мультиплексоров 15 и 16. На разрешающем входе мультиплексора 15 присутствует единичный сигнал, который разрешает поступление сигналов на его выход. Если на выходе триггера 33.3 присутствует единичный сигнал (это означает наличие дуги в графе), то на выходе мультиплексора 15 появится единичный импульс, который поступит на входы разрешения выдачи счетчиков 28 и 30. Код единицы с выхода счетчика 28 поступит на вход дешифратора 18, а на входе дешифратора 19 появится код двойки с выхода счетчика 30. Соответственно на первом выходе дешифратора 18 и на втором выходе дешифратора 19 появятся единичные сигналы. Единичный сигнал с первого выхода дешифратора 18 поступит на второй вход элемента 40. i.1 (i=1, 2,..., m) И МС. Единичный сигнал со второго выхода дешифратора 19 поступит на второй вход элемента 41.i.2 (i=1, 2,..., m) ИМС.

Код "00...010" с выхода счетчика 26 поступает на вход дешифратора 20 и возбуждает на его втором выходе положительный импульс, который в свою очередь поступает на первые входы элементов 40.2.j (j=1, 2,..., n) и 41.2.j (j=1, 2,..., n) И. Таким образом, на выходе элементов 40.2.1 и 41.2.2 появятся единые сигналы, которые пройдут через соответствующие элементы 38.2.1 и 38.2.2 ИЛИ и увеличат по переднему фронту содержимое счетчиков 36.2.1 и 36.2.2 на единицу, фиксируя тем самым очередную дугу рассматриваемого графа.

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

Так продолжается до тех пор, пока не произойдет переполнение либо счетчика 25 либо счетчика 30. Переполнение счетчика 25 произойдет в том случае, если его содержимое превысит код числа n. В этом случае на выходе переполнения появляется единичный импульс, который поступает на счетный вход счетчика 24 строк и увеличивает его содержимое по переднему фронту на единицу, устанавливая в нем код двойки ("00...010"). Код числа два поступает на вход дешифратора 17 и, на установочный вход счетчика 25, устанавливая в нем начальное значение, равное коду двойки ("00...010"). На втором выходе дешифратора 17 появляется единичный импульс, который поступает на управляющие входы блока 35.2 элементов запрета, разрешая тем самым прохождение сигналов с индикаторных выходов элементов второй строки матрицы 1, которые проходят через соответствующие входы группы 37.1-37.m элементов ИЛИ и поступают на соответствующие S-входы группы 33.1-33.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. Далее работа происходит так, как описано выше.

Переполнение первого счетчика 30 фиксируемой дуги означает, что фиксация дуг исходного графа в строках МС закончена (на фиг.2 это дуги, зафиксированные в модулях 1-2 и 3-4) и далее необходимо фиксировать дуги в столбах МС (на фиг.2 это модули 1-3 и 2-4). Сигнал с выхода переполнения счетчика 30 поступает на вход сброса счетчика 28, сбрасывая его до кода единицы. Тот же сигнал поступает на S-вход триггера 32 режима, устанавливая его в единичное состояние. Тогда на его прямом выходе будет присутствовать единичный сигнал, а на инверсном - нулевой. Нулевой сигнал с инверсного выхода триггера 32 поступает на разрешающий вход мультиплексора 15 и запрещает прохождение сигналов на его выход. Кроме того, тот же сигнал поступает на первый вход элемента 44 И, запрещая тем самым прохождение импульсов с генератора 14 импульсов. Единичный сигнал с прямого выхода триггера 32 поступает на второй вход элемента 45 И, разрешая прохождение импульсов с генератора 14 импульсов на его выходы и на разрешающий вход мультиплексора 16, разрешая тем самым прохождение сигналов с входов на его выход. В счетчике 30 устанавливается код двойки ("00...010").

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

К этому времени на управляющих входах мультиплексоров 15 и 16 появится код числа, содержащегося в счетчике 25. Так как на разрешающем входе мультиплексора 16 присутствует положительный импульс, и, если в триггере 37.j (j=1, 2,..., n) содержится единица, то на выходе мультиплексора 16 появится положительный импульс. Единичный сигнал с выхода мультиплексора 16 поступает на счетные входы счетчиков 29 и 31, увеличивая их содержимое по переднему фронту до кодов "00...01" и "00...010" соответственно. Поэтому на входе дешифратора 22 появится код "00...01", а на входе дешифратора 21 - код двойки ("00...010"). При появлении кодов на входах дешифраторов 21 и 22, на первом выходе дешифратора 22 возбуждается единичный импульс, который поступает на первые входы элемента 42.1.j (j=1, 2,..., n) И МС. На втором выходе дешифратора 21 появляется единичный импульс, который поступа