УСТРОЙСТВО ДЛЯ ПОДСЧЕТА ЗНАЧЕНИЯ ИНТЕНСИВНОСТИ РАЗМЕЩЕНИЯ В ПОЛНОСВЯЗНЫХ МАТРИЧНЫХ СИСТЕМАХ
DEVICE FOR CALCULATION OF LOCATION INTENSITY VALUE IN FULLY CONNECTED MATRIX SYSTEMS

Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании вычислительных систем (ВС).
Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 1291957 СССР, кл. G06F 7/00, опубл. 23.02.87, БИ №7).
Недостатком указанного элемента является узкая область применения, обусловленная отсутствием средств для оценки качества (степени оптимальности) размещения по критериям суммарной длины ребер и максимальной длины ребра.
Наиболее близким к предлагаемому устройству по технической сущности является устройство для оценки размещения элементов, содержащее матрицу элементов однородной среды, состоящую из элементов однородной среды, блоки подсчета единиц, блок нахождения максимума, сумматор, блок памяти, вход записи исходного гиперграфа, вход управления перестановкой столбцов, вход управления перестановкой строк, вход управления записью в блок памяти, выходы оценки текущего размещения, информационный выход и вход установки (а.с. 1410949 СССР, кл. G06F 7/00, 15/20, опубл. 15.10.88, БИ №38).
Недостатком указанного устройства является узкая область применения, обусловленная отсутствием средств для подсчета значения интенсивности размещения в полносвязных матричных системах (МС) по критерию минимизации интенсивности взаимодействия процессов и данных.
Технической задачей является расширение области применения за счет введения средств для подсчета значения интенсивности размещения в полносвязных МС.
Техническая задача решается тем, что в устройство для подсчета значения интенсивности размещения в полносвязных матричных системах, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, …, n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен с j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра устройства и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок подсчета интенсивности, содержащий генератор импульсов, дешифратор строк, мультиплексор выбора элемента, дешифратор выбранного модуля, счетчик строк, счетчик столбцов, группу с 1-го по m-й счетчиков значений интенсивности, группу с 1-го по m-й блоков элементов запрета, группу из m RS-триггеров, группу из m элементов ИЛИ, причем вход запуска устройства подключен к генератору импульсов, выход которого подключен к счетному входу счетчика столбцов, выход которого соединен с управляющим входом мультиплексора выбора элемента, выход переполнения счетчика столбцов соединен со счетным входом счетчика строк, выход переполнения которого соединен с выходом переполнения устройства, выход счетчика строк соединен с управляющим входом дешифратора выбранного модуля и с входом дешифратора строк, выходы с 1-го по m-й которого подключены к соответствующим управляющим входам групп из m блоков элементов запрета, соответствующие входы которых подсоединены к соответствующим выходам элементов с первого по n-й столбцов матрицы элементов однородной среды, выходы группы с 1-й по m-ю блоков элементов запрета подсоединены к соответствующим входам группы из m элементов ИЛИ, выходы которых подсоединены к соответствующим S-входам группы из m RS-триггеров, R-входы которых соединены с соответствующим выходом переполнения счетчика столбцов и со счетным входом счетчика строк, выходы группы из m RS-триггеров соединены с соответствующими входами мультиплексора выбора элемента, выход которого подсоединен к входу дешифратора выбранного модуля, выходы с 1-го по m-й подключены к соответствующим счетным входам группы из m счетчиков значений интенсивности, выходы которых соединены с соответствующими m выходами значений интенсивности устройства.
Сущность изобретения поясняется чертежами, где на фиг.1 изображена функциональная схема устройства для подсчета значения интенсивности размещения в полносвязных МС; фиг.2 поясняет сущность предлагаемого критерия.
Общие особенности изобретения состоят в следующем.
Предлагаемое устройство может использоваться в области проектирования ВС, например, при размещении процессов (алгоритмов, задач). Устройство позволяет подсчитывать значения интенсивности размещения в полносвязных МС.
i
ij
Исходная (размещаемая) задача (процесс, алгоритм) представляется в виде неориентированного невзвешенного графа G=<X,E>, вершины х ∈ Х которого соответствуют подзадачам (подалгоритмам), а дуги е ∈ Е ⊆ Х × Х задают управляющие и/или информационные связи между подзадачами.
МС отображается однородной средой, которой ставится в соответствие топологическая модель в виде графа H=<U,V>, где
- множество модулей ПС, организованных в матрицу
=N=n и является количеством модулей ПС и количеством вершин графа G, V - множество межмодульных связей.
Размещение графа G в МС Н будем задавать в виде отображения:
где
p,k
ij
i
j
Полносвязная МС полностью аналогична обычной МС. Отличием является наличие у модуля и u не четырех инцидентных связей, как для обычной МС, а восьми (фиг.2а). Такая МС может быть описана матрицей смежности , где w определяется интенсивностью взаимодействия (потока передачи данных, слов данных, кодовых слов передачи управления и т.п.) между подзадачами x и х.
Для удобства дальнейшего описания будем считать, что однородная среда содержит m×n элементов, при этом m=n (где m и n - число процессов). Функционирование однородной среды аналогично прототипу. При поступлении сигнала от внешнего устройства управления (ВУУ) происходит перестановка двух вершин графа и получение нового варианта размещения. Предлагаемое устройство вычисляет значения критериев оценки и выдает указанные значения ВУУ. Последнее анализирует принятые значения и либо фиксирует полученное размещение как более оптимальное, если значения критериев улучшают ранее найденные значения, либо игнорирует его.
В отличие от прототипа, где оценка выполняется по двум критериям - суммарной длине ребер и максимальной длине ребра, предлагаемое устройство дополнительно реализует подсчет значения интенсивности размещения в полносвязных МС.
Сущность предлагаемого критерия поясняется на фиг.2. Здесь на фиг.2а и 2б предлагаются гипотетические варианты размещения. Модули МС представлены квадратами, в левом верхнем углу которых представлены их номера. Внутри модулей кружками обозначены вершины графа с соответствующими номерами внутри. Пунктирные линии обозначают связи модулей МС. Сплошные линии показывают гипотетические зафиксированные дуги. На фиг.2в и 2г представлены матрица смежности W для соответствующих вариантов размещения на фиг.2а и 2б. Из анализа матриц смежности следует, что интенсивность взаимодействия для модуля 4 МС на фиг.2а наибольшая - 8, а для модулей 3 и 9 наименьшая и соответствует единице. На фиг.2б представлен альтернативный вариант размещения для такого же количества дуг графа, а на фиг.2г - соответствующая ему матрица смежности, из которой видно, что в данном случае значения интенсивностей взаимодействия не превышают 6. Минимизация этого свойства ВС важна для уменьшения общего времени выполнения всей задачи в целом. Из анализа матриц смежности на фиг.2б и 2в можно сделать вывод, что для подсчета значения интенсивности каждого из модулей МС достаточно найти сумму всех ненулевых значений для каждой строки матрицы 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 устройства, а также дополнительно введенный блок 21 подсчета интенсивности, содержащий генератор 14 импульсов, дешифратор 15 строк, мультиплексор 16 выбора элемента, дешифратор 17 выбранного модуля, счетчик 18 строк, счетчик 19 столбцов, группу 20.1, 20.2, …, 20.m счетчиков значений интенсивности, группу 22.1, 22.2, …, 22.m блоков элементов запрета, группу 23.1, 23.2, …, 23.m RS-триггеров, группу 24.1, 24.2, …, 24.m элементов ИЛИ, причем вход 26 запуска устройства подключен к генератору 14 импульсов, выход которого подключен к счетному входу счетчика 19 столбцов, выход которого соединен с управляющим входом мультиплексора 16 выбора элемента, выход переполнения счетчика 19 столбцов соединен со счетным входом счетчика 18 строк, выход переполнения которого соединен с выходом 25 переполнения устройства, выход счетчика 18 строк соединен с управляющим входом дешифратора 17 выбранного модуля и с входом дешифратора 15 строк, выходы с 1-го по m-й которого подключены к соответствующим управляющим входам групп 22.1, 22.2, …, 22.m блоков элементов запрета, соответствующие входы которых подсоединены к соответствующим выходам элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы группы 22.1, 22.2, …, 22.m блоков элементов запрета подсоединены к соответствующим входам группы 24.1, 24.2, …, 24.m элементов ИЛИ, выходы которых подсоединены к соответствующим S-входам группы 23.1, 23.2, …, 23.m RS-триггеров, R-входы которых соединены с соответствующим выходом переполнения счетчика 19 столбцов и со счетным входом счетчика 18 строк, выходы группы 23.1, 23.2, …, 23.m RS-триггеров соединены с соответствующими входами мультиплексора 16 выбора элемента, выход которого подсоединен к входу дешифратора 17 выбранного модуля, выходы с 1-го по m-й подключены к соответствующим счетным входам группы 20.1, 20.2, …, 20.m счетчиков значений интенсивности, выходы которых соединены с соответствующими выходами 27.1, 27.2, …, 27.m значений интенсивности устройства.
Назначение элементов и блоков устройства для подсчета значения интенсивности размещения в полносвязных матричных системах состоит в следующем.
Матрица 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 импульсов предназначен для формирования тактовых импульсов, синхронизирующих работу блока 21 подсчета интенсивности.
Дешифратор 15 строк служит для выбора строки матрицы 1 элементов однородной среды.
Мультиплексор 16 выбора элемента необходим для разрешения подачи сигнала с очередного триггера 23.i (i=1, 2, …, m) группы 23.1-23.m RS-триггеров на вход дешифратора 17 зафиксированного модуля. Фактически это означает выбор очередного элемента матрицы смежности.
Дешифратор 17 выбранного модуля предназначен для выдачи информации о наличии зафиксированной вершины графа G в данном анализируемом модуле МС.
Счетчик 18 строк служит для хранения информации о номере текущей обрабатываемой строки матрицы 1.
Счетчик 19 столбцов служит для хранения информации о номере обрабатываемого столбца в данной выбранной строке матрицы 1.
Группа 20.1, 20.2, …, 20.m счетчиков значений интенсивности предназначена для хранения информации о значениях интенсивности размещения модулей МС. Соответственно, каждый из счетчиков хранит информацию об интенсивности для каждого из модулей МС.
Блок 21 подсчета интенсивности необходим для подсчета значения интенсивности размещения в полносвязных матричных системах.
Группа 22.1, 22.2, …, 22.m блоков элементов запрета предназначена для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 на соответствующие элементы группы 24.1, 24.2, …, 24.m элементов ИЛИ соответственно.
Группа 23.1, 23,2, …, 23.m RS-триггеров служит для временного хранения информации о наличии зафиксированных дуг в модулях выбранной строки МС.
Группа 24.1, 24.2, …, 24.m элементов ИЛИ служит для объединения сигналов с выходов группы 22.1, 22.2, …, 22.m блоков элементов запрета.
Выход 25 переполнения устройства служит для подачи информации о переполнении счетчика 18 строк и одновременно о завершении работы блока 21 подсчета интенсивности.
Вход 26 запуска устройства служит для запуска генератора 14 импульсов от ВУУ.
Выходы 27.1, 27.2, …, 27.m значений интенсивности предназначены для подачи на ВУУ информации о значении интенсивности размещения модулей МС.
Работа блоков 1, 2, 3, 4 и 5 подробно описана в прототипе и поэтому здесь не рассматривается.
Предлагаемое устройство предназначено для оценки размещения по критериям суммарной длины ребер, максимальной длины ребра. Дополнительно предлагаемое устройство позволяет подсчитывать значения интенсивности размещения в полносвязных матричных системах по критерию минимизации интенсивности взаимодействия процессов и данных, а также предназначено для решения задачи трассировки. Задача трассировки решается в матрице 1, так же как и в прототипе, и поэтому здесь не рассматривается.
Первоначально в матрице 1 элементов однородной среды содержится вариант размещения. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В счетчике 18 строк содержится код единицы («00…01»), в счетчике 19 столбцов - код нуля. В счетчиках 20.1, 20.2, …, 20.m группы счетчиков значений интенсивности содержатся коды нулей. Код единицы с выхода счетчика 18 поступает на вход дешифратора 15, и на его первом выходе появляется единичный импульс, который поступает на управляющие входы первого блока 22.1 элементов запрета и разрешает прохождение сигналов с индикаторных выходов первой строки матрицы 1. Эти сигналы проходят через элементы первого 22.1 блока элементов запрета и поступают на входы группы 24.1, 24.2, …, 24.m элементов ИЛИ. Пройдя через элементы ИЛИ, сигналы поступают на S-входы группы 23.1, 23.2, …, 23.m RS-триггеров и устанавливают соответствующие триггеры в единичные состояния при условии наличия единичных сигналов.
Оценка размещения по критериям суммарной длины ребер и максимальной длины ребра происходит следующим образом. Информация с индикаторных выходов элементов каждого столбца матрицы 1 поступает в соответствующие блоки подсчета единиц. Блок 2.i (i=1, 2, …, n) выдает двоичное число (код), равное количеству поступивших на его вход единиц. Полученное число далее поступает на входы сумматора 4 и блока 3 нахождения максимума, соответствующие данному блоку подсчета единиц. В результате на выходе 10 устройства образуется код (оценка) максимальной длины ребра, а на выходе 11 - код (оценка) суммарной длины ребер, отвечающие текущему варианту размещения схемы (содержащемуся в матрице 1). Полученные оценки далее поступают на ВУУ, где происходит их сравнение с предыдущими значениями. В случае улучшения оценок ВУУ подает импульс (сигнал «Запись») на вход 9 управления записью устройства и текущий вариант размещения переписывается в блок 5 памяти из матрицы 1. Более подробно рассмотренный режим работы устройства описан в прототипе.
Задача подсчета значения интенсивности размещения в полносвязных МС по критерию минимизации интенсивности взаимодействия процессов и данных решается в предлагаемом устройстве следующим образом. После выполнения очередной перестановки строк на индикаторных выходах элементов матрицы 1 появляются сигналы, соответствующие новому варианту размещения. Одновременно с этим запускается генератор 14 импульсов и начинается работа блока 21 подсчета интенсивности.
Первый тактовый импульс с выхода генератора 14 импульсов подается на счетный вход счетчика 19, и по переднему фронту увеличивает его содержимое на единицу, устанавливая в нем код единицы («00…01»). Код единицы с выхода счетчика 19 подается на управляющий вход мультиплексора 16 и разрешает прохождение единичного сигнала с выхода триггера 23.1 (при условии, что триггер 23.1 установлен в единицу) на выход мультиплексора 16. Этот сигнал подается на вход дешифратора 17. В это время на управляющем входе дешифратора 17 присутствует код единицы с выхода счетчика 18, и поэтому на первом выходе дешифратора 17 появляется единичный импульс. Этот сигнал подается на счетный вход счетчика 20.1 и по заднему фронту увеличивает его содержимое на единицу, устанавливая в нем код единицы («00…01»). Таким образом происходит анализ первой зафиксированной дуги в полносвязной матричной системе.
Очередной тактовый импульс с выхода генератора 14 импульсов подается на счетный вход счетчика 19 и по переднему фронту увеличивает его содержимое до кода двойки («00…010»). Этот код с выхода счетчика 19 поступает на управляющий вход мультиплексора 16 и разрешает прохождение сигнала с выхода триггера 23.2 на выход мультиплексора 16 и далее на вход дешифратора 17. На его управляющем входе присутствует код значения единицы. Поэтому на первом выходе появляется единичный импульс, который поступает на счетный вход счетчика 27.1 и по заднему фронту увеличивает его содержимое на единицу, сохраняя в нем значение кода двойки («00…010»).
Так происходит перебор n столбцов 1-й строки матрицы 1. Попытка увеличения содержимого счетчика 19 до кода n+1 вызывает инициирование единичного импульса на выходе переполнения счетчика 19. Этот сигнал поступает на счетный вход счетчика 18 и увеличивает его содержимое на единицу до кода двойки («00…010»). Таким образом происходит выбор для анализа 2-го модуля матричной системы. Сигнал с выхода переполнения счетчика 19 также поступает на R-входы триггеров 23.1, 23.2, …, 23.m и сбрасывает их в нулевое состояние.
Код двойки с выхода счетчика 18 поступает на вход дешифратора 15. Поэтому на втором его выходе появляется единичный сигнал, который поступает на управляющие входы второго блока 22.2 группы 22.1, 22.2, …, 22.m блоков элементов запрета. Таким образом сигналы с индикаторных выходов 2-й строки матрицы 1 поступают на входы второго блока 22.2 элементов запрета. Эти сигналы проходят на их соответствующие выходы, проходят через группу 24.1, 24.2, …, 24.m элементов ИЛИ и поступают на соответствующие входы группы 23.1, 23.2, …, 23.m RS-триггеров, устанавливая их в единичное состояние.
Далее работа устройства происходит аналогично по описанному выше принципу. Очередной тактовый импульс с выхода генератора 14 импульсов подается на счетный вход счетчика 19 и увеличивает его содержимое на единицу. Этот код поступает на управляющий вход мультиплексора 16 и разрешает прохождения единичного сигнала с выхода триггера 23.i (i=1, 2, …, m) на выход мультиплексора 16, далее на вход дешифратора 17. На его управляющем входе присутствует код i (i=1, 2, …, m) с выхода счетчика 18. Соответственно, на выходе i (i=1, 2, …, m) дешифратора 17 появляется единичный импульс, который подается на счетный вход счетчика 20.i (i=1, 2, …, m) группы счетчиков 20.1, 20.2, …, 20.m. Таким образом происходит анализ очередной зафиксированной дуги матрицы 1.
Так происходит до тех пор, пока на выходе переполнения счетчика 18 строк не появится единичный сигнал, который сигнализирует о том, что перебор всех строк матрицы 1 (матрицы смежности графа G) закончен, а в счетчиках 20.1, 20.2, …, 20.m содержатся значения интенсивности размещения для данного варианта размещения в полносвязной матричной системе. Эти коды с выходов 27.1, 27.2, …, 27.m значений интенсивности подаются на ВУУ для дальнейшей обработки.
Таким образом, предлагаемое устройство для подсчета значения интенсивности размещения в полносвязных матричных системах обеспечивает возможность оценки размещения как по критериям суммарной длины ребер, максимальной длины ребра, так и обеспечивает возможность подсчета значения интенсивности размещения в полносвязных МС по критерию минимизации интенсивности взаимодействия процессов и данных. Тем самым обеспечивается расширение функциональных возможностей устройства и, следовательно, области его целесообразного применения.