УСТРОЙСТВО ДЛЯ ПОДСЧЕТА МИНИМАЛЬНОГО ЗНАЧЕНИЯ ИНТЕНСИВНОСТИ РАЗМЕЩЕНИЯ В СИСТЕМАХ С ДРЕВОВИДНОЙ ОРГАНИЗАЦИЕЙ Российский патент 2010 года по МПК G06F7/00 

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

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

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

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

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

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

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

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

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

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

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

Древовидная структура (ДС) отображается однородной средой, которой ставится в соответствие топологическая модель в виде графа Н=<U,V>, где U - множество модулей ДС, организованных в виде дерева (фиг.2а) |U|=N=n, и является количеством модулей ДС и количеством вершин графа G, V - множество межмодульных связей.

Множество модулей ДС (фиг.2а) разбивается на L подмножеств, образующих соответствующие уровни. При этом первый уровень (корневой, корень дерева) обязательно имеют одну связь с элементами (i-1)-го уровня и по k связей с элементами (i+1)-го уровня, где k - количество связей с элементами нижестоящего уровня. Корень дерева связан k связями только с элементами второго уровня, а модули L-го уровня связаны только с элементами (L-1)-го уровня. ДС может быть описана матрицей смежности W=||w_ij||_n×n, где w_ij определяется интенсивностью взаимодействия (потока передачи данных, слов данных, кодовых слов передачи управления и т.п.) между подзадачами x_i и x_j.

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

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

Сущность предлагаемого критерия поясняется на фиг.2. Здесь на фиг.2а представлен гипотетический вариант графа G, представленного в виде древовидной топологии, а на фиг.2б - соответствующая ему матрица смежности W. На фиг.2а кружками обозначены вершины графа G, а рядом с каждой вершиной соответствующий ей номер. Стрелки в графе, направленные из одной вершины в другую, обозначают дуги. При подсчете минимального значения интенсивности размещения предполагается, что топология исходного графа G и графа связей Н между модулями тождественна. При этом при вычислении минимального значения интенсивности не принимаются во внимание ограничения, накладываемые фактическими связями между задачами в графе G. То есть при вычислении минимального значения необходимо назначать дуги графа G на смежные модули ДС. Полученное в результате суммарное значение интенсивности называется минимальным. Качество размещения с учетом топологии графа будет тем лучше, чем ближе его суммарное значение интенсивности к значению нижней оценки.

Устройство для подсчета минимального значения интенсивности размещения в системах с древовидной организацией (фиг.1) содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блоки 2.1, 2.2,…,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 устройства, а также дополнительно введенный блок 22 минимального значения, содержащий генератор 14 импульсов, дешифратор 15 инцидентной дуги, элемент 16 задержки, мультиплексор 17 выбора элемента, счетчик 18 строк, счетчик 19 столбцов, группу 20.1, 20.2,…, 20.m счетчиков фиксируемых дуг, второй 21 сумматор, группу 23.1, 23.2,…, 23.m RS-триггеров, группу 24.1, 24.2,…, 24.m блоков элементов запрета, группу 25.1, 25.2,…, 25.m элементов ИЛИ, первый 26 и второй 27 счетчики последнего зафиксированного модуля, первый 28 элемент ИЛИ, дешифратор 29 строк, второй 30 и третий 31 элементы ИЛИ, одновибратор 32, причем вход 33 запуска устройства соединен со входом генератора 14 импульсов, выход которого соединен со счетным входом счетчика 19 столбцов, выход переполнения которого подсоединен к счетному входу счетчика 18 строк и к R-входам группы 23.1, 23.2,…, 23.m RS-триггеров, выход переполнения счетчика 18 строк подсоединен к выходу 34 переполнения устройства, выход счетчика 18 строк подключен к установочному входу счетчика 19 столбцов и к входу дешифратора 29 строк, выходы с 1-го по m-й которого подключены к соответствующим управляющим входам группы 24.1, 24.2,…, 24.m блоков элементов запрета, соответствующие входы которых подсоединены к соответствующим выходам элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы группы 24.1, 24.2,…, 24.m блоков элементов запрета подсоединены к соответствующим входам группы 25.1, 25.2,…, 25.m элементов ИЛИ, выходы которых подсоединены к соответствующим S-входам группы 23.1, 23.2,…, 23.m RS-триггеров, выходы которых подключены к соответствующим входам мультиплексора 17 выбора элемента, выход которого соединен с первым разрешающим входом дешифратора 15 инцидентной дуги, с входом элемента 16 задержки и со вторым входом третьего 31 элемента ИЛИ, первый вход которого подключен к входу сброса второго 27 счетчика последнего зафиксированного модуля и к первому выходу одновибратора 32, выход третьего 31 элемента ИЛИ подключен к счетному входу второго 27 счетчика последнего зафиксированного модуля, выход которого подсоединен ко второму входу первого 28 элемента ИЛИ, первый вход которого соединен с выходом первого 26 счетчика последнего зафиксированного модуля, счетный вход которого соединен с выходом второго 30 элемента ИЛИ, второй вход которого подключен к выходу элемента 16 задержки, первый вход второго 30 элемента ИЛИ соединен со вторым выходом одновибратора 32, вход которого подключен к выходу переполнения первого 26 счетчика последнего зафиксированного модуля и ко второму разрешающему входу дешифратора 15 инцидентной дуги, выходы с первого по m-й которого соединены с соответствующими входами группы 20.1, 20.2,…, 20.m счетчиков фиксируемых дуг, выходы которых подключены к соответствующим входам второго 21 сумматора, выход которого соединен с выходом 35 значения интенсивности устройства, выход счетчика 19 столбцов подсоединен к управляющему входу мультиплексора 17 выбора элемента.

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

Матрица 1 элементов однородной среды предназначена для моделирования процесса решения задач размещения и отображает матрицу смежности W для размещаемого графа G задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

Дешифратор 15 инцидентной дуги необходим для подачи на соответствующие входы 20.i (i=1, 2,…, m) счетчиков фиксируемых дуг информации об инцидентных выбранной дуге вершинах, подлежащих фиксации.

Элемент 16 задержки служит для задержки единичного импульса с выхода мультиплексора 17 выбора элемента на время, достаточное для установления нового кода во втором 27 счетчике последнего зафиксированного модуля, поступления его на второй вход элемента 28 ИЛИ, подачи его на вход дешифратора 15 инцидентной дуги и возбуждения на одном из его входов единичного импульса.

Мультиплексор 17 выбора элемента служит для разрешения подачи сигнала с очередного триггера 23.i (i=1, 2,…, m) группы 23.1-23.m RS-триггеров на выход мультиплексора 17.

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

Счетчик 19 столбцов необходим для хранения информации о номере обрабатываемого столбца в данной выбранной строке матрицы 1.

Группа 20.1, 20.2,…, 20.m счетчиков фиксируемых дуг служит для моделирования древовидной структуры. В каждом из счетчиков хранится информация о значении интенсивности соответствующего модуля ДС.

Второй 21 сумматор служит для суммирования отдельных значений интенсивности ДС и последующей подачи суммарного значения на ВУУ.

Блок 22 минимального значения предназначен для подсчета минимального значения интенсивности размещения в системах с древовидной организацией по критерию минимизации интенсивности взаимодействия процессов и данных.

Группа 23.1, 23.2,…, 23.m RS-триггеров служит для временного хранения информации о наличии дуг в строке матрицы 1 элементов однородной среды (фактически в строке матрицы смежности размещаемого графа).

Группа 24.1, 24.2,…, 24.m блоков элементов запрета необходима для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 элементов однородной среды на соответствующие элементы группы 25.1, 25.2,…, 25.m элементов ИЛИ соответственно.

Группа 25.1, 25.2,…, 25.m элементов ИЛИ служит для объединения сигналов с выходов группы 24.1, 24.2,…, 24.m блоков элементов запрета.

Первый 26 и второй 27 счетчики последнего зафиксированного модуля необходимы для хранения информации о номерах модулей, в которых была произведена последняя фиксация дуги. Так как исходный граф G задачи ненаправленный, то передача информации может происходить сразу в двух направлениях, а значит, следует помнить номера двух модулей МС, в которых бала произведена последняя фиксация.

Первый 28 элемент ИЛИ предназначен для объединения сигналов с выходов первого 26 и второго 27 счетчика последнего зафиксированного модуля с последующей подачей на вход дешифратора 15 инцидентной дуги.

Дешифратор 29 строк служит для выбора строки матрицы 1 элементов однородной среды.

Второй 30 и третий 31 элементы ИЛИ служат для объединения сигналов, поступающих с одновибратора 32, элемента задержки 16, мультиплексора 17 выбора элемента и подачи их на счетные входы первого 26 и второго 27 счетчиков последнего зафиксированного модуля.

Одновибратор 32 предназначен для генерации одиночного импульса и подачи его на соответствующие первые входы второго 30 и третьего 31 элементов ИЛИ. Формируемый импульс подается с двух разных выходов с задержкой, достаточной для установления в первом 26 счетчике последнего зафиксированного модуля нового кода, поступления этого кода на вход дешифратора 15 инцидентной дуги, возбуждения на соответствующем выходе единичного импульса и подачи его на соответствующий счетчик 20.i (i=1, 2,…, m).

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

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

Выход 35 значения интенсивности устройства предназначен для подачи на ВУУ информации о минимальном значении интенсивности размещения в системах с древовидной организацией.

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

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

Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В счетчике 19 столбцов содержится код числа единицы («00…01»), триггеры 23.i (i=1, 2,…, m) группы 23.1, 23.2,…, 23.m RS-триггеров находятся в состоянии логического нуля, в счетчиках 20.i (i=1, 2,…, m) группы 20.1, 20.2,…, 20.m счетчиков фиксируемых дуг содержатся коды нулей. Во втором 21 сумматоре хранится код нуля, в счетчике 18 строк хранится код единицы («0…01»). Этот код подается на вход дешифратора 29, и на его первом выходе появляется единичный импульс, который поступает на управляющие входы первого блока 24.1 элементов запрета и разрешает прохождение сигналов с индикаторных выходов первой строки матрицы 1. Эти сигналы проходят через элементы первого 24.1 блока элементов запрета и поступают на входы группы 25.1, 25.2,…, 25.m элементов ИЛИ. Пройдя через элементы ИЛИ, сигналы поступают на соответствующие S-входы группы 23.1, 23.2,…, 23.m RS-триггеров и устанавливают соответствующие триггеры в единичные состояния при условии наличия единичных сигналов. В первом 26 счетчике последнего зафиксированного модуля хранится код нуля, а во втором 27 счетчике последнего зафиксированного модуля - код единицы.

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

Задача подсчета минимального значения интенсивности размещения в системах с древовидной организацией по критерию минимизации интенсивности взаимодействия процессов и данных основана на следующем предположении. Так как предполагается, что обмен информацией ведется в двух направлениях, то при фиксации отдельной дуги графа G интенсивность взаимодействия увеличивается сразу для двух инцидентных модулей ДС. Например, на фиг.2а это дуга из вершины x₁ в вершину х₂. Соответственно при фиксации дуги в модули 1-2 ДС интенсивности будут увеличены на единицу для двух модулей.

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

Первый тактовый импульс с выхода генератора 14 импульсов подается на счетный вход счетчика 19 и по переднему фронту увеличивает его содержимое на единицу до кода двойки («0…010»). Этот код с выхода счетчика 19 поступает на управляющий вход мультиплексора 17 и разрешает прохождение единичного сигнала с выхода триггера 23.2 на его выход. Этот сигнал с выхода мультиплексора 17 подается на вход элемента 16 задержки, на первый разрешающий вход дешифратора 15 и на второй вход элемента 31 ИЛИ. Единичный сигнал с выхода элемента 31 ИЛИ поступает на счетный вход счетчика 27 и увеличивает его содержимое по переднему фронту на единицу до кода двойки («0…010»). Код числа два с выхода счетчика 27 подается на второй вход элемента 28 ИЛИ и далее на вход дешифратора 15. Так как на его разрешающем входе присутствует единица, то на втором выходе дешифратора 15 возбуждается единичный импульс, который поступает на соответствующий счетный вход счетчика 20.2 и по заднему фронту увеличивает содержимое счетчика на единицу, устанавливая в нем код единицы.

К этому моменту элемент 16 задержки пропускает единичный импульс на выход, который подается на второй вход элемента 30 ИЛИ, а далее на счетный вход счетчика 26, увеличивая в нем по переднему фронту код на единицу до кода единицы («0…01»). С соответствующего выхода код единицы поступает на первый вход первого 28 элемента ИЛИ и далее на вход дешифратора 15. На соответствующем первом выходе появляется единичный импульс, который поступает на счетный вход счетчика 20.1, по заднему фронту увеличивая его содержимое на единицу до кода единицы. Таким образом происходит фиксация первой дуги графа G (на фиг.2а это дуга x₁-х₂) в ДС.

Очередной тактовый импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 19 и по переднему фронту увеличивает его содержимое на единицу, устанавливая в нем код числа три («0…011»). Код тройки подается на управляющий вход мультиплексора 17, что разрешает прохождение единичного сигнала с выхода триггера 23.3 на выход мультиплексора 17. Этот код далее подается на первый разрешающий вход дешифратора 15, на вход элемента 16 задержки и на второй вход элемента 31 ИЛИ. С выхода элемента 31 ИЛИ единичный сигнал подается на счетный вход счетчика 27, который по переднему фронту увеличивает его содержимое на единицу, устанавливая в нем код числа три («0…011»). Код тройки через элемент 28 ИЛИ проходит на вход дешифратора 15. В соответствии с поступившим кодом на вход дешифратора 15 на его третьем выходе появляется единичный сигнал, который поступает на счетный вход счетчика 20.3, увеличивая его содержимое по заднему фронту на единицу до кода значения единицы.

В это время элемент 16 задержки уже пропустил единичный сигнал, который через элемент 30 ИЛИ поступает на счетный вход счетчика 26. Поступивший сигнал увеличивает содержимое счетчика по переднему фронту на единицу до кода двойки. Код числа два проходит через элемент 28 ИЛИ и поступает на вход дешифратора 15. Так как на его входе присутствует код двойки, то на соответствующем втором выходе появляется единичный импульс, который подается на соответствующий счетный вход счетчика 20.2, увеличивая его содержимое по заднему фронту на единицу до кода двойки.

Аналогично работа схемы продолжается до тех пор, пока в счетчике 26 не установится код числа m. Это вызывает сигнал переполнения на выходе переполнения счетчика 26. Соответствующий единичный сигнал поступает на второй разрешающий вход дешифратора 15, который разрешает его работу, а также на вход одновибратора 32, который генерирует одиночный единичный импульс, подающийся с двух выходов с запаздыванием. Запаздывание импульса, поступающего со второго (нижнего) выхода, должно обеспечить время, достаточное для того, чтобы обеспечить импульсу с первого (верхнего) выхода пройти цепь элементов: элемент ИЛИ 31, счетчик 27, элемент ИЛИ 28, дешифратор 15, счетчик 20.i (i=1, 2,…, m). Таким образом импульс с первого выхода одновибратора 32 подается на первый вход элемента 31 ИЛИ и на вход сброса счетчика 27, сбрасывая его в начальное единичное состояние. Импульс с выхода элемента 31 ИЛИ поступает на счетный вход счетчика 27, где по переднему фронту увеличивает его содержимое на единицу до кода k (k=1, 2,…, m). Значение кода k через элемент ИЛИ 28 поступает на вход дешифратора 15. Тогда на k-м выходе дешифратора 15 возбуждается единичный импульс, который поступает на соответствующий счетчик 20.k и увеличивает его содержимое по заднему фронту на единицу.

В это время со второго выхода одновибратора 32 уже поступил единичный импульс на первый вход элемента 30 ИЛИ. Счетчик 26 уже сбросился в исходное нулевое состояние. На его счетный вход поступает сигнал с выхода элемента 30 ИЛИ, увеличивая его содержимое на единицу. Этот код через элемент 28 ИЛИ поступает на вход дешифратора 15. Тогда на соответствующем его выходе возбуждается единичный сигнал, который передается на соответствующий счетный вход счетчика 20.i (i=1, 2,…, m) и по заднему фронту увеличивает его содержимое на единицу. Таким образом происходит фиксация очередной дуги графа G.

Работа схемы продолжается аналогично до тех пор, пока на выходе переполнения счетчика 19 столбцов не появится сигнал переполнения, свидетельствующий о том, что обработка первой строки матрицы 1 элементов однородной среды закончена. Сигнал переполнения подается на R-входы триггеров 23.i (i=1, 2,…, m) группы 23.1, 23.2,…, 23.m RS-триггеров и устанавливает их в нулевое состояние. Сигнал переполнения с выхода счетчика 19 столбцов также поступает на счетный вход счетчика 18 строк и по переднему фронту увеличивает его содержимое на единицу до кода двойки («0…010»). Код двойки с выхода счетчика 18 строк поступает на установочный вход счетчика 19 столбцов и устанавливает его в начальное состояние два. Также код двойки с выхода счетчика 18 строк поступает на вход дешифратора 29 строк. В результате на втором его выходе возбуждается единичный сигнал, который поступает на управляющие входы второго блока 24.2 элементов запрета и разрешает прохождение сигналов с индикаторных выходов второй строки матрицы 1. Эти сигналы проходят через элементы второго 24.2 блока элементов запрета и поступают на входы группы 25.1, 25.2,…, 25.m элементов ИЛИ. Пройдя через элементы ИЛИ, сигналы поступают на соответствующие S-входы группы 23.1, 23.2,…, 23.m RS-триггеров и устанавливают соответствующие триггеры в единичные состояния при условии наличия единичных сигналов.

Далее работа схемы продолжается аналогично описанному выше принципу до тех пор, пока на выходе переполнения 34 счетчика 18 не появится сигнал переполнения, свидетельствующий о том, что все дуги графа G зафиксированы в вычислительной системе с древовидной топологической организацией. При этом в сумматоре 21 хранится суммарное минимальное значение интенсивности размещения. Полученное значение с выхода сумматора 21 поступает на выход 35 значения интенсивности и далее подается на ВУУ для дальнейшей обработки.

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

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

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