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

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

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

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

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

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

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

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

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

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

- множество модулей МС, организованных в матрицу |U|=N=n, где n является количеством модулей МС и количеством вершин графа G, V - множество межмодульных связей.

Размещение графа G в МС Н будем задавать в виде отображения:

где , , ,

Так как полносвязная МС идентична по своей структурной организации обычной МС, то она может быть описана матрицей смежности W=||w_ij||_n×n, где w_ij определяется интенсивностью взаимодействия (потока передачи данных, слов данных, кодовых слов передачи управления и т.п.) между подзадачами х_i и x_j.

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

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

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

Устройство подсчета значения интенсивности размещения в полносвязных матричных системах при направленной передаче информации (фиг.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-m входом сумматора 4, выходы которых соединены с выходом 10 максимальной длины ребра устройства и выходом 11 суммарной длины ребер устройства соответственно, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, m) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также дополнительно введенный блок 26 подсчета интенсивности, содержащий генератор 14 импульсов, дешифратор 15 строк, дешифратор 16 выбранного модуля, мультиплексор 17 выбранного элемента, первый 18 и второй 19 счетчик строк, первый 20 и второй 21 счетчик столбцов, группу 22.1, 22.2, …, 22.m счетчиков значений интенсивности, группу 23.1, 23.2, …, 23.m RS-триггеров, триггер 24 режима, группу 25.1, 25.2, …, 25.m блоков элементов запрета, первый 27 и второй 28 элемент И, первый 29, второй 30 и третий 36 элемент ИЛИ, группу 31.1, 31.2, …, 31.m элементов ИЛИ, причем вход 34 запуска устройства соединен с входом генератора 14 импульсов, выход которого соединен со вторыми входами первого 27 и второго 28 элемента И, первый вход второго 28 элемента И подключен к инверсному выходу триггера 24 режима, прямой выход которого подключен к первому входу первого 27 элемента И, к разрешающему входу второго 19 счетчика строк, счетный вход которого соединен с выходом переполнения второго 21 счетчика столбцов и с первым входом первого 29 элемента ИЛИ, выход переполнения второго 19 счетчика строк подключен к выходу 35 переполнения устройства, выход второго 19 счетчика строк подсоединен к первому входу третьего 36 элемента ИЛИ и к установочному входу второго 21 счетчика столбцов, второй вход третьего 36 элемента ИЛИ подсоединен к выходу первого 18 счетчика строк, выход переполнения которого подключен к S-входу триггера 24 режима, R-вход которого соединен со входом 33 сброса устройства, счетный вход первого 18 счетчика строк подключен к выходу переполнения первого 20 счетчика столбцов и ко второму входу первого 29 элемента ИЛИ, выход третьего 36 элемента ИЛИ подсоединен ко входу дешифратора 15 строк, выходы с 1-го по m-й которого подсоединены к соответствующим управляющим входам групп 25.1, 25.2, … 25.m блоков элементов запрета, соответствующие входы которых подсоединены к соответствующим выходам элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы группы 25.1, 25.2, …, 25.m блоков элементов запрета подсоединены к соответствующим входам группы 31.1, 31.2, …, 31.m элементов ИЛИ, выходы которых подключены к соответствующим S-входам группы 23.1, 23.2, …, 23.m RS-триггеров, R-входы которых подсоединены к выходу первого 29 элемента ИЛИ, выходы группы 23.1, 23.2, …, 23.m RS-триггеров соединены с соответствующими входами мультиплексора 17 выбранного элемента, выход которого подключен ко входу дешифратора 16 выбранного модуля, выходы с первого по m-й которого соединены со счетными входами группы 22.1, 22.2, …, 22.m счетчиков значений интенсивности, выходы которых соединены с соответствующими выходами 32.1, 32.2, …32.m значений интенсивности устройства, управляющие входы мультиплексора 17 выбранного элемента и дешифратора 16 выбранного модуля соединены с выходом второго 30 элемента ИЛИ, второй вход которого подключен к выходу первого 20 счетчика столбцов, счетный вход которого подключен к выходу второго 28 элемента И, первый вход второго 30 элемента ИЛИ соединен с выходом второго 21 счетчика столбцов, счетный вход которого подключен к выходу первого 27 элемента И.

Назначение элементов и блоков устройства для подсчета значения интенсивности размещения в полносвязных матричных системах состоит в следующем:

Матрица 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 импульсов предназначен для формирования тактовых импульсов, синхронизирующих работу блока 26 подсчета интенсивности.

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

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

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

Первый 18 и второй 19 счетчик строк предназначен для хранения информации о номере выбранной строки матрицы 1 элементов однородной среды.

Первый 20 и второй 21 счетчик столбцов служит для хранения информации о номере обрабатываемого столбца в выбранной строке матрицы 1.

Группа 22.1, 22.2, …, 22.m счетчиков значений интенсивности предназначена для хранения информации о значениях интенсивности размещения модулей МС.

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

Триггер 24 режима необходим для выбора режима работы блока 26 подсчета интенсивности. Когда триггер находится в нулевом состоянии обрабатывается верхний треугольник матрицы смежности. В случае единичного состояния обрабатывается нижний треугольник матрицы смежности.

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

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

Первый 27 элемент И предназначен для блокировки поступления тактового импульса на счетный вход второго счетчика 21 столбцов.

Второй 28 элемент И предназначен для блокировки поступления тактового импульса на счетный вход первого счетчика 20 столбцов.

Первый 29 элемент ИЛИ служит для объединения сигналов с выходов переполнения первого 20 и второго 21 счетчика столбцов.

Второй 30 элемент ИЛИ необходим для объединения сигналов с выходов первого 20 и второго 21 счетчика столбцов.

Третий 36 элемент ИЛИ необходим для объединения сигналов с выходов первого 18 и второго 19 счетчиков строк.

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

Выходы 32.1, 32.2, …, 32.m значений интенсивности предназначены для подачи на ВУУ информации о значении интенсивности размещения в полносвязных матричных системах.

Вход 33 сброса устройства служит для установки триггера 24 режима в нулевое состояние.

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

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

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

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

Первоначально в матрице 1 элементов однородной среды содержится вариант размещения. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В первом 18 счетчике строк содержится код единицы («00…01»), во втором 19 счетчике строк первоначально хранится код значения т.В первом 20 счетчике столбцов содержится код единицы, а во втором 21 счетчике столбцов хранятся код нуля. Триггер 24 режима находится в нулевом состоянии, поэтому на его прямом выходе присутствует нулевой потенциал, а на инверсном - единичный. Следовательно, первый 27 элемент И закрыт для прохождения тактовых импульсов, а второй 28 элемент И - открыт. На разрешающем входе второго 19 счетчика строк присутствует нулевой потенциал с прямого выхода триггера 24 режима, что запрещает работу второго 19 счетчика строк. Триггеры группы 23.1, 23.2, …, 23.m RS-триггеров находятся в нулевом состоянии, в счетчиках группы 22.1, 22.2, …, 22.m счетчиков значений интенсивности хранятся коды нулей. Код единицы с выхода счетчика 18 строк поступает через третий 36 элемент ИЛИ на вход дешифратора 15, поэтому на его первом выходе присутствует единый сигнал, который подаются на соответствующие управляющие входы первого блока 25.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. Эти сигналы проходят через соответствующие элементы группы 31.1, 31.2, …32.m элементов ИЛИ, и поступают на соответствующие S-входы группы 23.1-23.m RS-триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов.

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

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

Работа предлагаемого устройства происходит за два этапа. На первом этапе происходит анализ верхнего треугольника матрицы смежности. При этом триггер 24 режима находится в нулевом состоянии, в этом случае элемент 28 И открыт для прохождения тактовых импульсов. В то же время элемент 27 И закрыт, так как на его первом входе присутствует нулевой потенциал с прямого выхода триггера 24.

На втором этапе происходит анализ нижнего треугольника матрицы смежности. При этом триггер 24 режима находится в единичном состоянии и в этом случае элемент 27 И открыт для прохождения тактовых импульсов из-за присутствия на его первом входе единичного потенциала, а элемент 28 И - закрыт, так как на его первом входе присутствует нулевой потенциал.

Появление положительного сигнала на входе 34 запускает генератор 14 импульсов. Первый тактовый импульс с выхода генератора 14 импульсов поступает на вторые входы первого 27 и второго 28 элемента И. Так как элемент 27 И закрыт, то импульс на его выходе не появляется. Импульс с выхода элемента 28 И подается на счетный вход счетчика 20 и по переднему фронту увеличивает его содержимое на единицу, устанавливая в нем код значения двойки («00…010»). Код двойки с выхода счетчика 20 через элемент 30 ИЛИ подается на управляющий вход мультиплексора 17, разрешая прохождение единичного сигнала с выхода триггера 23.2 на выход мультиплексора 17. Этот сигнал поступает на вход дешифратора 16, на управляющем входе которого присутствует код двойки с выхода элемента 30 ИЛИ. Следовательно, на втором выходе дешифратора 16 появляется единичный импульс, который поступает на счетный вход счетчика 22.2 и по заднему фронту увеличивает его содержимое на единицу до кода единицы. Тем самым происходит анализ первой зафиксированной дуги в МС, например на фиг.2б это дуга из модуля 1 в модуль 2.

Работа схемы происходит аналогично описанному выше. Следующий тактовый импульс поступает на вторые входа первого 27 и второго 28 элемента И, но единичный сигнал появляется только на выходе второго элемента И 28, который поступает на счетный вход счетчика 20 и по переднему фронту увеличивает в нем код до значения трех («00…011»). Код числа три подается на второй вход элемента 30 ИЛИ и проходит дальше на управляющий вход мультиплексора 17. Этот код разрешает прохождение сигнала с триггера 23.3 на выход мультиплексора 17 и дальше на вход дешифратора 16. На его управляющем входе присутствует код числа три с выхода элемента 30 ИЛИ. Следовательно, на третьем выходе дешифратора 16 возбуждается единичный импульс, который поступает на счетный вход счетчика 22.3 и по заднему фронту увеличивает его содержимое на единицу. Таким образом, происходит анализ следующей дуги.

Работа устройства продолжается аналогично до тех пор, пока на выходе переполнения счетчика 20 не появится сигнал переполнения. Этот импульс поступает на второй вход элемента 29 ИЛИ и на счетный вход счетчика 18, в котором по переднему фронту увеличивает содержимое на единицу, устанавливая в нем код числа два. Импульс со второго входа элемента 29 ИЛИ проходит на его выход и поступает на R-входы триггеров группы 23.1, 23.2, …, 23.m RS-триггеров, сбрасывая их в нулевое состояние. Код числа два с выхода счетчика 18 через элемент 36 ИЛИ подается на вход дешифратора 15 и на втором его выходе возбуждается положительный импульс, который подается на соответствующие управляющие входы второго блока 29.2 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов второй строки матрицы 1. Эти сигналы проходят через группу 31.1, 31.2, …, 31.m элементов ИЛИ, и поступают на соответствующие S-входы группы 23.1, 23.2, …, 23.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов.

Далее аналогично описанному выше тактовый импульс поступает на вторые входы элементов 27 и 28 И, на выходе элемента 28 И появляется единичный сигнал, который подается на счетный вход счетчика 20 и по переднему фронту увеличивает его содержимое на единицу до кода j (j=1, 2, …, n). Коду (j=1, 2, …, n) с выхода счетчика 20 через элемент 30 ИЛИ поступает на управляющие входы мультиплексора 17 и дешифратора 16. Мультиплексор 17 разрешает прохождение сигнала с выхода триггера 23.j (j=1, 2, …, n) на выход мультиплексора 17 и далее на вход дешифратора 16. На j-м (j=1, 2, …, n) выходе дешифратора 16 появляется положительный импульс, который подается на счетный вход счетчика 22.j (j=1, 2, …, n) и по заднему фронту увеличивает его содержимое на единицу.

Работа устройства по описанному выше принципу происходит до тех пор, пока на выходе переполнения счетчика 18 не появится сигнал переполнения. Это означает, что все строки верхнего треугольника матрицы смежности просмотрены, и первый этап работы устройства закончен. Импульс с выхода переполнения счетчика 18 поступает на S-вход триггера 24, устанавливая его в единичное состояние. Следовательно, на прямом его выходе появляется единица, а на инверсном - ноль. Единичный сигнал с прямого выхода триггера 24 разрешает работу элемента 27 И, закрывая при этом элемент 28 И, так на его первом входе присутствует ноль с инверсного выхода триггера 24. Единичный сигнал с прямого выхода триггера 24 также поступает на разрешающий вход счетчика 19 и разрешает его работу.

На данном этапе счетчик 19 содержит в себе код значения m. Это необходимо, так как просмотр строк матрицы смежности будет происходить в обратном порядке, то есть от большего номера к меньшему (от m к 1). Код числа m с выхода счетчика 18 через элемент 36 ИЛИ поступает на вход дешифратора 15 и на m-м его выходе появляется единичный импульс, который подается на управляющие входы блока 25.m группы 25.1, 25.2, …, 25.m элементов запрета, разрешая прохождение сигналов с индикаторных выходов m-й строки матрицы 1. Соответствующие сигналы через группу 31.1, 31.2, …, 31.m элементов ИЛИ подаются на соответствующие входы группы 23.1, 23.2, …, 23.m RS-триггеров, устанавливая их в единичные состояния при наличии соответствующих единичных сигналов. Код значения m также подается на установочный вход счетчика 21 и устанавливает предел счета этого счетчика.

Очередной тактовый импульс поступает на вторые входы элементов 27 и 28 И, но только на выходе элемента 27 И появляется положительный импульс, который поступает на счетный вход счетчика 21 и по переднему фронту увеличивает его содержимое на единицу до кода единицы («00…01»). Этот код поступает на первый вход элемента 30 ИЛИ и далее на управляющие входы мультиплексора 17 и дешифратора 16. Мультиплексор 17 пропускает сигнал с выхода триггера 23.1 на выход мультиплексора 17 и далее на выход дешифратора 16. Так как на управляющем входе дешифратора 16 присутствует код единицы, то на первом его выходе появляется единичный импульс, который поступает на счетный вход счетчика 22.1 и по заднему фронту увеличивает его содержимое на единицу.

Аналогично описанному выше очередной тактовый импульс поступает на вторые входы элементов 27 и 28 И. Единичный сигнал появляется на выходе элемента 27 И и поступает на счетный вход счетчика 21, увеличивая его содержимое по переднему фронту на единицу до кода двойки («00…010»). Код числа два с выхода счетчика 21 подается через элемент 30 ИЛИ на управляющие входы мультиплексора 17 и дешифратор 16. Единичный сигнал с выхода триггера 23.2 проходит на выход мультиплексора 17 и поступает на вход дешифратора 16. Так как на его управляющем входе присутствует код числа два, то на втором выходе дешифратора 16 появляется единичный сигнал, который поступает на счетный вход счетчика 22.2 и по заднему фронту увеличивает его содержимое на единицу.

Так работа устройства продолжается до тех пор, пока на выходе переполнения счетчика 21 не появится сигнал переполнения. Этот сигнал поступает на счетный вход счетчика 19, по переднему фронту уменьшает его содержимое на единицу и устанавливает в нем код числа m-1. Положительный сигнал с выхода переполнения счетчика 21 также подается на первый вход элемента 29 ИЛИ. Единичный сигнал с выхода элемента 29 ИЛИ подается на R-входы триггеров 23.1, 23.2, …, 23.m и сбрасывает их в нулевое состояние.

Очередной тактовый импульс проходит через элемент 27 И и поступает на счетный вход счетчика 21, увеличивая его содержимое по переднему фронту на единицу до кода j (j=1, 2, …, n). Этот код проходит через элемент 30 ИЛИ и поступает на управляющие входы мультиплексора 17 и дешифратора 16. С выхода триггера 23.j (j=1, 2, …, n) сигнал проходит на выход мультиплексора 17 и подается на вход дешифратора 16. На его j-м выходе появляется положительный импульс, который поступает на счетный вход счетчика 22.j (j=1, 2, …, n) и по заднему фронту увеличивает его содержимое на единицу.

Так продолжается до тех пор, пока на выходе переполнения счетчика 19 не появится сигнал переполнения, который поступает на выход 35 переполнения устройства. Это сигнализирует о том, что все элементы нижнего треугольника матрицы 1 (матрицы смежности графа G) просмотрены и работа устройства завершена. К этому времени в счетчиках 22.1, 22.2, …, 22.m будут содержаться значения интенсивностей для каждого модуля матричной системы, которые подаются на соответствующие выходы 32.1, 32.2, …, 32.m, а они в свою очередь на ВУУ.

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

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

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