УСТРОЙСТВО ДЛЯ ОЦЕНКИ СТЕПЕНИ ЗАГРУЗКИ КАНАЛОВ В СИСТЕМАХ С ДРЕВОВИДНОЙ ТОПОЛОГИЧЕСКОЙ ОРГАНИЗАЦИЕЙ

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