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

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

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

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

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

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

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

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

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

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

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

Исходная (размещаемая) задача (процесс, алгоритм) представляется в виде ориентированного невзвешенного графа G=<X,E>, вершины х_i∈Х которого соответствуют подзадачам (подалгоритмам), а дуги e_ij∈E⊆Х×Х задают управляющие и/или информационные связи между подзадачами. Размещаемый граф G задается соответствующей матрицей смежности. Строки и столбцы матрицы отмечаются номерами вершин графа. На пересечении i-й строки и j-го столбца ставится единица, если i-ю и j-ю вершину соединяет дуга, и ноль - в противном случае.

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

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

Сущность предлагаемой нижней оценки размещения поясняется фиг.2. Здесь на фиг.2а и 2в представлены гипотетические варианты размещения графа, а на фиг.2б и 2г представлены соответствующие матрицы смежности. На фиг.2а и 2в кружками обозначены гипотетические модули, а цифры внутри модулей - их соответствующие номера. Числа над пунктирными линиями обозначают интенсивность передачи информации (взаимодействия процессов, интенсивность передачи данных) между смежными модулями. Нижняя оценка размещения может быть найдена путем последовательного назначения дуг на смежные модули КС. Из фиг.2а видно, что такой вариант размещения не является нижней оценкой, так как при поиске нижней оценки размещения дуга из вершины 1 в вершину 4 не может быть зафиксирована в модулях 1-4, а должна быть назначена на соседние (смежные) модули КС. В то же время вариант размещения, изображенный на фиг.2в, является нижней оценкой, так как все дуги при этом назначены на соседние модули КС. Тем самым при применении предлагаемого устройства в ВС, где требуется максимальное время реакции системы, уменьшается общее время выполнения задачи.

Устройство планирования размещения задач в системах с кольцевой организацией при направленной передаче информации содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блоки 2.1-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 устройства, а также дополнительно введенный блок 28 нижней оценки, содержащий генератор 14 импульсов, первый 15 и второй 16 дешифраторы выбора строки, первый 17 и второй 18 мультиплексоры выбора элемента, дешифратор 19 дуги, элемент 20 сравнения, второй 21 сумматор, группу 22.1, 22.2,..., 22. m кольцевых счетчиков нижней оценки, счетчик 23 дуг, первый 24 и второй 25 счетчики столбцов, первый 26 и второй 27 счетчики строк, триггер 29 режима, первую 30.1, 30.2,..., 30.m и вторую 31.1, 31.2, ..., 31.m группы триггеров, первую 32.1, 32.2,..., 32.m и вторую 33.1, 33.2,..., 33.m группы блоков элементов запрета, первую 34.1, 34.2,..., 34.m и вторую 35.1, 35.2,..., 35.m группы элементов ИЛИ, первый 36 и второй 37 элементы И, первый 38 и второй 40 элементы ИЛИ, элемент 39 задержки, причем вход 41 запуска устройства соединен с входом генератора 14 импульсов, выход которого подключен к счетному входу первого 24 счетчика столбцов, выход генератора 14 импульсов соединен со вторым входом первого 36 элемента И, первый вход которого подключен к прямому выходу триггера 29 режима и ко второму входу второго 37 элемента И, R-вход триггера 29 режима соединен с выходом 42 сброса устройства, S-вход триггера 29 режима подключен к выходу переполнения первого 26 счетчика строк, выход которого подключен к установочному входу первого 24 счетчика столбцов и к входу первого 15 дешифратора выбора строки, счетный вход первого 26 счетчика строк подключен к выходу переполнения первого 24 счетчика столбцов и к R-входам первой 30.1, 30.2,..., 30.m группы триггеров, выход первого 24 счетчика столбцов соединен с управляющим входом первого 17 мультиплексора выбора элемента, выходы с первого по m-й первого 15 дешифратора выбора строки подключены к соответствующим управляющим входам первой 32.1, 32.2,..., 32.m группы блоков элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы первой 32.1, 32.2,..., 32.m группы блоков элементов запрета соединены с соответствующими входами первой 34.1, 34.2,..., 34.m группы элементов ИЛИ, выходы которых соединены с соответствующими S-входами первой 30.1, 30.2,..., 30.m группы триггеров, выходы которых подключены к соответствующим входам с первого по m-й первого 17 мультиплексора выбора элемента, выход которого подключен к соответствующим вторым входам первого 38 и второго 40 элементов ИЛИ, соответствующие первые входы которых соединены с выходом второго 37 элемента И, выход второго 40 элемента ИЛИ подключен к входу элемента 39 задержки, выход которого соединен с разрешающим входом дешифратора 19 дуги, вход которого соединен с выходом счетчика 23 дуги, счетный вход которого подключен к выходу первого 38 элемента ИЛИ, выходы с первого по m-й дешифратора 19 дуги подключены к соответствующим счетным входам группы 22.1, 22.2,..., 22.m кольцевых счетчиков нижней оценки, выходы которых подключены к соответствующим входам второго 21 сумматора, выход которого соединен с выходом 44 нижней оценки, выход первого 36 элемента И соединен со счетным входом второго 25 счетчика столбцов, выход которого подключен к управляющему входу второго 18 мультиплексора выбора элемента и ко второму входу элемента 20 сравнения, первый вход которого подключен к выходу второго 27 счетчика строки и к входу второго 16 дешифратора выбора строки, первый выход элемента 20 сравнения соединен с разрешающим входом второго 18 мультиплексора выбора элемента, второй выход элемента 20 сравнения соединен со счетным входом второго 27 счетчика строк и с R-входами второй 31.1, 31.2,..., 31.m группы триггеров, выход переполнения второго 27 счетчика строк подключен к выходу 43 переполнения устройства, выходы с первого по m-й второго 16 дешифратора выбора элемента соединены с соответствующими управляющими входами второй 33.1, 33.2,..., 33.m группы блоков элементов запрета, входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы второй 33.1, 33.2,..., 33.m группы блоков элементов запрета соединены с соответствующими входами второй 35.1, 35.2,..., 35.m группы элементов ИЛИ, выходы которых соединены с соответствующими S-входами второй 31.1, 31.2,..., 31.m группы триггеров, выходы которых подключены к соответствующим входам с первого по m-й второго 18 мультиплексора выбора элемента, выход которого подключен к первому входу второго 37 элемента И.

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

Матрица 1 элементов однородной среды предназначена для моделирования процесса решения задач размещения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый 17 мультиплексор выбора элемента предназначен для подачи с выходов первой 30.1, 30.2,..., 30.m группы триггеров информации о наличии дуги в графе, соответствующей верхнему треугольнику матрицы смежности.

Второй 18 мультиплексор выбора элемента служит для подачи с выходов второй 31.1, 31.2,..., 31.m группы триггеров информации о наличии дуги в графе, соответствующей нижнему треугольнику матрицы смежности.

Дешифратор 19 дуги служит для выбора очередной фиксируемой дуги графа и подачи сигналов на соответствующие входы группы 22.1, 22.2,..., 22.m кольцевых счетчиков нижней оценки.

Элемент 20 сравнения служит для сравнения значений, содержащихся во втором 27 счетчике строк и во втором 25 счетчике столбцов.

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

Группа 22.1, 22.2,..., 22.m кольцевых счетчиков нижней оценки предназначена для накапливания информации о загрузке модулей КС. Работа счетчика основана на пересчете поступающих значений по модулю m.

Счетчик 23 дуг предназначен для накапливания информации о номере очередной фиксируемой дуги.

Первый 24 и второй 25 счетчики столбцов служат для подсчета номеров обрабатываемых столбцов в текущей выбранной строке матрицы 1.

Первый 26 и второй 27 счетчики строк необходимы для накапливания информации о текущей обрабатываемой строке матрицы 1.

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

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

Первая 30.1, 30.2,..., 30.m и вторая 31.1, 31.2,..., 31.m группы триггеров необходимы для хранения информации о наличии дуги, инцидентной соответствующим выбранным вершинами матрицы смежности.

Первая 32.1, 32.2, ..., 32.m и вторая 33.1, 33.2, ..., 33.m группы блоков элементов запрета предназначены для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 на элементы первой 34.1, 34.2,..., 34.m и второй 35.1, 35.2,..., 35.m групп элементов ИЛИ соответственно.

Первая 34.1, 34.2,..., 34.m и вторая 35.1, 35.2,..., 35.m группы элементов ИЛИ необходимы для объединения сигналов с выходов первой 32.1, 32.2,..., 32.m и второй 33.1, 33.2,..., 33.m групп элементов запрета соответственно.

Первый 36 элемент И предназначен для объединения сигналов с прямого выхода триггера 29 режима и с выхода генератора 14 импульсов с последующей его подачей на счетный вход второго 25 счетчика столбцов.

Второй 37 элемент И служит для объединения сигналов с прямого выхода триггера 29 режима и с выхода второго 18 мультиплексора выбора элемента. Также он необходим для разрешения поступления сигналов на вход элемента 38 ИЛИ.

Первый 38 элемент ИЛИ предназначен для объединения сигналов с выхода второго 37 элемента И и с выхода первого 17 мультиплексора выбора элемента.

Элемент 39 задержки служит для задержки поступления импульса с выхода элемента 40 ИЛИ на разрешающий вход дешифратора 19 дуги.

Второй 40 элемент ИЛИ предназначен для объединения сигналов с выхода второго 37 элемента И и с выхода первого 17 мультиплексора.

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

Вход 42 сброса необходим для подачи на R-вход триггера 29 режима сигнала сброса состояния триггера.

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

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

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

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

Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения, соответствующий матрице смежности исходного графа. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В счетчиках 23, 24 и 26 содержится код единицы ("00...01"). В счетчике 27 содержится код двойки ("00...010"). Единичное значение с выхода счетчика 26 подается на вход дешифратора 15, поэтому на первом его выходе присутствует единый сигнал, который поступает на соответствующие управляющие входы первого блока 32.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. Эти сигналы проходят через группу 34.1, 34.2,..., 34.m элементов ИЛИ и поступают на соответствующие S-входы группы 30.1, 30.2,..., 30.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. Значение кода двойки с выхода счетчика 27 поступает на вход дешифратора 16 и на его втором выходе появляется единичный потенциал, который подают на соответствующие управляющие входы второго блока 33.2 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов второй строки матрицы 1. Соответствующие сигналы проходят через группу 35.1, 35.2,..., 35.m элементов ИЛИ и поступают на соответствующие S-входы группы 31.1, 31.2,..., 31.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. В счетчике 25 содержится код нуля. Триггер 29 находится в нулевом состоянии, поэтому на его прямом выходе присутствует нулевой потенциал, который поступает на первый вход элемента 36 И и на второй вход элемента 37 И и запрещает появление положительных сигналов на их выходах. В счетчиках 22.1, 22.2,..., 22.m содержатся коды нуля ("00...00"). Во втором сумматоре 21 содержится нулевой код.

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

Задача поиска нижней оценки в кольцевых системах при направленной передаче информации решается следующим образом. После выполнения очередной перестановки строк на индикаторных выходах элементов матрицы 1 появляются сигналы, соответствующие новому варианту размещения. Одновременно с этим запускается генератор 14 импульсов и начинается работа блока 28 поиска нижней оценки и его так называемой "нижней" части, в которую входят группа 32.1, 32.2,..., 32.m элементов запрета, группа 34.1, 34.2,..., 34.m элементов ИЛИ, группа 30.1, 30.2,..., 30.m триггеров, мультиплексор 17, дешифратор 15, счетчики 24 и 26.

Элементы 38 и 40 И, элемент 39 задержки, счетчик 23, генератор 14 импульсов, дешифратор 19, группа 22.1, 22.2,..., 22.m счетчиков и сумматор 21 относятся как к "верхней", так и к "нижней" части схемы и поэтому явно не включены ни в "верхнюю", ни в "нижнюю" часть.

Импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 24 и по переднему фронту увеличивает его содержимое до кода двойки ("00...010"). Одновременно импульс с выхода генератора 14 импульсов поступает на второй вход элемента 36 И, но так как на его первом входе присутствует нулевой сигнал, то прохождение сигналов на его выход блокируется. Код числа два с выхода счетчика 24 поступает на управляющий вход мультиплексора 17 и разрешает прохождение сигнала с выхода триггера 30.2 на выход мультиплексора 17. Положительный сигнал с выхода мультиплексора 17 поступает на второй вход элемента 38 ИЛИ и, проходя через него, обеспечивает появление на входе счетчика 23 положительного импульса, который увеличивает его содержимое по заднему фронту до кода двойки ("00...010"). Тот же импульс с выхода мультиплексора 17 поступает через элемент 40 ИЛИ на вход элемента 39 задержки и обеспечивает задержку поступления единичного сигнала на разрешающий вход дешифратора 19 на время, достаточное для установления в счетчике 23 нового значения кода.

После установления в счетчике 23 кода двойки соответствующий сигнал поступает на вход дешифратора 19. К этому времени элемент 39 задержки разрешает поступление импульса на разрешающий вход дешифратора 19. Поэтому на втором его выходе инициируется положительный сигнал, который поступает на счетный вход счетчика 22.2 и увеличивает его содержимое по заднему фронту на единицу. Поэтому в нем устанавливается код единицы ("00...01"). Тем самым обеспечивается фиксация первой дуги графа.

Очередной импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 24 и по переднему фронту увеличивает его содержимое до кода тройки ("00...011"). Тот же импульс поступает на второй вход элемента 36 И, но, из-за нулевого сигнала на его первом входе, положительный импульс на его выходе не появляется.

Код числа три с выхода счетчика 24 поступает на управляющий вход мультиплексора 17 и разрешает прохождение на его выход сигнала с выхода триггера 34.3. Если в нем содержится единичное значение, то оно поступает на выход мультиплексора 17 и далее на второй вход элемента 38 ИЛИ. Тот же сигнал поступает через элемент 40 ИЛИ на вход элемента задержки 39, задерживая импульс на время, достаточное для прохождения сигнала с выхода мультиплексора 17 на счетный вход счетчика 23 и установления в нем очередного значения. В это время единичный сигнал с выхода элемента 38 ИЛИ поступает на счетный вход счетчика 23 и по переднему фронту увеличивает его содержимое на единицу, устанавливая в нем код числа три ("00...011"). После установления в счетчике 23 кода числа три соответствующий сигнал с его выхода поступает на вход дешифратора 19. Элемент задержки 39 к этому времени пропускает сигнал на разрешающий вход дешифратора 19 и на его третьем выходе появляется единичный импульс. Положительный сигнал поступает на счетный вход счетчика 22.3 и по заднему фронту увеличивает его содержимое на единицу. Таким образом происходит фиксация второй дуги графа.

Так происходит до тех пор, пока в счетчике 24 не будет установлено значение (n+1). В этом случае на выходе переполнения этого счетчика появится положительный импульс, который поступает на счетный вход счетчика 26 и установит в нем по переднему фронту значение кода двойки ("00...010"). Одновременно импульс с выхода переполнения счетчика 24 поступает на R-входы триггеров 30.1, 30.1,..., 30.m и устанавливает их в нулевое состояние. Код числа два поступает на установочный вход счетчика 24 и устанавливает в нем начальное значение числа два. Код двойки с выхода счетчика 26 также поступает на вход дешифратора 15 и на его втором выходе появляется единичное значение. Единичный импульс с выхода дешифратора 15 поступает на соответствующие управляющие входы второго блока 32.2 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов второй строки матрицы 1. Эти сигналы проходят через группу 34.1, 34.2,..., 34.m элементов ИЛИ и поступают на соответствующие S-входы группы 30.1, 30.2,..., 30.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов.

Очередной импульс с выхода генератора 14 импульсов поступает на счетный вход счетчика 24 и по переднему фронту увеличивает на единицу содержащееся в нем значение. На второй вход элемента 36 И поступает импульс с генератора 14 импульсов, но на его выходе импульс не появляется, так как на первом его входе присутствует нулевой сигнал с прямого выхода триггера 29 режима.

Далее работа устройства продолжается так, как описано выше до тех пор, пока не будут обработаны все значения матрицы 1, соответствующие верхнему треугольнику матрицы смежности. Об этом свидетельствует положительный импульс на выходе переполнения счетчика 26 строк. На этом работа "нижней" части схемы завершается и начинается работа "верхней" части. В нее входят: триггер 29 режима, элементы 36 и 37 И, мультиплексор 18, дешифратор 16, счетчики 25 и 27, элемент 20 сравнения, группа 31.1, 31.2,..., 31.m триггеров, группа 35.1, 35.2,..., 35.m элементов ИЛИ и группа 33.1, 33.2,..., 33.m элементов запрета.

Импульс переполнения с выхода счетчика 26 поступает на S-вход триггера 29 режима и устанавливает его в единичное состояние. Единичный сигнал с прямого выхода триггера 29 поступает на первый вход элемента 36 И и на второй вход элемента 37 И. Тем самым разрешается появление на выходе элемента 36 И сигналов при появлении очередного импульса на выходе генератора 14 импульсов. На выходе элемента 37 И также разрешается появление импульсов.

Очередной импульс с выхода генератора 14 импульсов поступает на второй вход элемента 36 И, так как на его первом входе присутствует единичное значение с прямого выхода триггера 29. На выходе элемента 36 И появляется положительный импульс, который поступает на счетный вход счетчика 25 и по переднему фронту устанавливает в нем код единицы ("00...01"). Этот код поступает на второй вход элемента 20 сравнения. На первом его входе присутствует код двойки с выхода счетчика 27. Так как значение на первом входе больше значения на втором входе, то результат сравнения будет положительным. Поэтому на первом выходе элемента 20 сравнения появляется единичный импульс, который поступает на разрешающий вход мультиплексора 18. На управляющем его входе присутствует код единицы. Поэтому сигнал с выхода триггера 31.1 (если он установлен в единицу) проходит на выход мультиплексора 18 и подается на первый вход элемента 37 И. Так как на втором его входе присутствует единичный сигнал с прямого выхода триггера 29, то на выходе элемента 37 И появляется положительный импульс. Единичный сигнал с его выхода поступает на первые входы элементов 38 и 40 ИЛИ. Сигналы с соответствующих выходов проходят на счетный вход счетчика 23 и элемент 39 задержки. Счетчик 23 по переднему фронту увеличивает свое значение на единицу. Элемент 39 задержки задерживает прохождение сигнала на его выход на время, достаточное для установления очередного кода в счетчике 23. Код, установленный в счетчике 23, поступает на вход дешифратора 19. К этому времени элемент 39 задержки уже пропустил импульс на его выход и он поступает на разрешающий вход дешифратора 19, разрешая тем самым прохождение импульсов на его выходы. Код числа i (i=1, 2,..., m), поступивший на вход дешифратора 19, возбуждает соответствующий i-й (i=1, 2,..., m) выход, который поступает на счетчик 22.i (i=1, 2,..., m), увеличивает его по заднему фронту на единицу. Таким образом, фиксируется очередная дуга графа, соответствующая значению из нижнего треугольника матрицы смежности.

Очередной импульс с выхода генератора 14 импульсов через элемент 36 И поступает на счетный вход счетчика 25 и увеличивает его до кода двойки ("00...010"). Значение этого кода поступает на второй вход элемента 20 сравнения. На первом входе присутствует код числа два. Результат сравнения будет отрицательным, так как значения равны друг другу. Поэтому единичный импульс появляется на втором выходе элемента 20 сравнения, который поступает на счетный вход счетчика 27 и на R-входы триггеров 31.1, 31.2,..., 31.m, сбрасывая их в нулевое состояние. Содержимое счетчика 27 по переднему фронту увеличивается на единицу и в нем устанавливается код тройки ("00...011"). Код числа три с выхода счетчика 27 поступает на первый вход элемента 20 сравнения и на вход дешифратора 16. Так как на его вход поступил код тройки, на его третьем выходе появится положительный импульс, который поступает на соответствующие управляющие входы третьего блока 32.3 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов третьей строки матрицы 1. Эти сигналы проходят через группу 35.1, 35.2,..., 35.m элементов ИЛИ и поступают на соответствующие S-входы группы 31.1, 31.2,..., 31.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов.

Далее работа схемы продолжается так, как описано выше до тех пор, пока не будут обработаны все дуги рассматриваемого графа из "нижнего" треугольника матрицы смежности. Это произойдет, когда на выходе 43 переполнения появится положительный импульс, который свидетельствует о переполнении счетчика 27, одновременно является сигналом об окончании размещения дуг и сигналом о завершении работы блока 28.

Так как значения с выходов счетчиков 22.1, 22.2,..., 22.m подаются на соответствующие входы сумматора 21, то к моменту завершения работы блока 28 во втором сумматоре 21 будет содержаться суммарное значение нижней оценки размещения в КС при направленной передаче информации. Оно поступает на выход 44 нижней оценки с последующей подачей на ВУУ для дальнейшей обработки.

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

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

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