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

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

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

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

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

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

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

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

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

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

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

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

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

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

Топологическая модель для размещения (область размещения) задается матрицей расстояний D. Элементы матрицы расстояний для кольцевой модели образуются по формуле d_i,j=(j-i+n)modn (n - количество вершин). Для реализации критерия минимизации интенсивности взаимодействия процессов и данных необходимо чтобы размещение формировалось в соответствии с формулой:

где , - векторы, первый из которых содержит ненулевые элементы матрицы смежности А, расположенные по убыванию, а второй - ненулевые элементы матрицы расстояний D, расположенные по возрастанию; k - порядковый номер элемента; - мощность множества дуг Е (количество дуг). Таким образом, при размещении необходимо сначала назначать дуги на модули КС, для которых d_k'=1, после этого, для d_k'=2, и т.д.

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

Устройство размещения задач в кольцевых системах (фиг.1) содержит матрицу 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 подсчета единиц, выход которого соединен c j-м входом блока 3 нахождения максимума и j-м входом сумматора 4, выходы которых соединены с выходом 10 максимальной длины ребра устройства и выходом 11 суммарной длины ребер устройства соответственно, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i=1, 2,..., m) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также дополнительно введенный блок 33 размещения, содержащий генератор 14 импульсов, дешифратор 15 выбора строки, дешифратор 16 выбора элемента, мультиплексор 17 выбора элемента, счетчик 18 номера строки, счетчик 19 номера столбца, счетчик 20 фиксируемых дуг, счетчик 21 значения, счетчик 22 расстояния, счетчик 23 последнего модуля, регистр 24 количества вершин, триггер 25 режима, группу 26.1-26.m триггеров, группу 27.1-27.m счетчиков назначенных дуг, первый 29 и второй 28 элементы сравнения, группу 30.1-30.m блоков элементов запрета, группу 31.1-31.m элементов ИЛИ, элемент 32 задержки, первый 34 и второй 35 элементы И, элемент 36 ИЛИ, причем вход 38 запуска устройства подключен к входу генератора 14 импульсов, выход которого соединен со вторым входом первого 34 элемента И и со вторым входом второго 35 элемента И, первый вход первого 34 элемента И подключен ко второму выходу триггера 25 режима, первый выход которого соединен с первым входом второго 35 элемента И, выход первого 34 элемента И подключен к счетному входу счетчика 19 номера столбца, выход которого подключен к установочному входу мультиплексора 17 выбора элемента, выход переполнения счетчика 19 номера столбца соединен со счетным входом счетчика 18 номера строки и с соответствующими R-входами группы 26.1-26.m триггеров, выход переполнения счетчика 18 номера строки соединен с выходом 39 переполнения устройства, выход счетчика 18 номера строки подключен к входу дешифратора 15 выбора строки, выходы с 1-го по m-й которого соединены с соответствующими управляющими входами группы 30.1-30.m блоков элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы группы 30.1-30.m блоков элементов запрета соединены с соответствующими входами группы 31.1-31.m элементов ИЛИ, соответствующие выходы которых соединены с соответствующими S-входам группы 26.1-26.m триггеров, выходы которых подсоединены к соответствующим входам мультиплексора 17 выбора элемента, выход которого подключен к разрешающему входу счетчика 20 фиксируемых дуг, выход которого соединен со вторым входом первого 29 элемента сравнения, первый вход которого соединен с выходом регистра 24 количества вершин, вход которого соединен с входом 37 установки, первый выход первого 29 элемента сравнения подключен к S-входу триггера 25 режима, второй выход первого 29 элемента сравнения подключен к первому входу элемента 36 ИЛИ, к входу сброса счетчика 20 фиксируемых дуг и к счетному входу счетчика 21 значения, выход элемента 36 ИЛИ соединен с R-входом триггера 25 режима, выход второго 35 элемента И соединен со счетным входом счетчика 22 расстояния, выход которого подключен к первому входу второго 28 элемента сравнения, второй вход которого соединен с выходом счетчика 21 значения, первый выход второго 28 элемента сравнения соединен с входом элемента 32 задержки и со счетным входом счетчика 23 последнего модуля, второй выход второго 28 элемента сравнения соединен с входом сброса счетчика 22 расстояния, со вторым входом элемента 36 ИЛИ и со счетным входом счетчика 20 фиксируемых дуг, выход элемента 32 задержки подключен к управляющему входу дешифратора 16 выбора элемента, вход которого соединен с выходом счетчика 23 последнего модуля, выходы с первого по m-й дешифратора 16 выбора элемента соединены с соответствующими счетными входами группы 27.1-27.m счетчиков назначенных дуг, выходы которых подсоединены к соответствующим выходам 40.1-40.m назначенных дуг устройства.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дешифратор 16 выбора элемента служит для подачи сигнала о назначении дуги графа в один из модулей КС и увеличения на единицу соответствующего счетчика 27.i (i=1, 2,..., m) группы 27.1-27.m счетчиков назначенных дуг.

Мультиплексор 17 выбора элемента предназначен для подачи с выходов группы 26.1-26.m триггеров информации о наличии дуги в графе на вход дешифратора 16 выбора элемента.

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

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

Счетчик 20 фиксируемых дуг предназначен для подсчета количества фиксируемых дуг для текущего значения d_k'.

Счетчик 21 значения необходим для хранения текущего значения d_k'.

Счетчик 22 расстояния служит для подсчета количества модулей КС, в которых производиться фиксация данной дуги, соответствующая текущему значению d_k'. Например, на фиг.2г при d_k'=2 это дуга, зафиксированная в модулях 1-3.

Счетчик 23 последнего модуля необходим для хранения информации о номере последнего модуля КС, в котором произошла последняя фиксация дуги. Счетчик имеет коэффициент пересчета n. Это необходимо, так как топология представляет собой кольцо.

Регистр 24 количества вершин служит для хранения информации о количестве вершин размещаемого графа.

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

Группа 26.1-26.m триггеров необходима для хранения информации о наличии дуги в графе.

Группа 27.1-27.m счетчиков назначенных дуг служит для хранения информации о назначенных дугах для варианта размещения в КС.

Второй 28 элемент сравнения предназначен для сравнения текущего значения d_k', хранящегося в счетчике 21 значения с кодом, содержащимся в счетчике 22 расстояния.

Первый 29 элемент сравнения предназначен для сравнения кода, хранящегося в регистре 24 количества вершин с кодом, содержащемся в счетчике 20 фиксируемых дуг.

Группа 30.1-30.m блоков элементов запрета предназначена для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 соответственно на элементы 31.1-31.m ИЛИ.

Группа 31.1-31.m элементов ИЛИ служат для объединения сигналов с выходов группы 30.1-30.m блоков элементов запрета соответственно.

Элемент 32 задержки предназначен для задержки поступления импульса с первого выхода второго 28 элемента сравнения на управляющий вход дешифратора 16 выбора элемента.

Блок 33 размещения необходим для размещения задач в КС по критерию минимизации интенсивности взаимодействия процессов и данных.

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

Второй 35 элемент И служит для блокировки поступления импульсов на счетный вход счетчика 22 расстояний.

Элемент 36 ИЛИ служит для объединения сигналов с выходов первого 29 и второго 28 элементов сравнения.

Вход 37 установки служит для подачи сигнала от ВУУ о количестве вершин размещаемого графа.

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

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

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

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

Первоначально в матрице 1 элементов однородной среды задается матрица смежности, соответствующая исходному графу. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. Группа 26.1-26.m триггеров находится в состоянии логического нуля. В регистре 24 режима содержится код, соответствующий количеству вершин (n) исходного графа. В счетчике 18 номера строки содержится код единицы («00...01»), в счетчике 19 номера столбца хранится код единицы («00...01»). Триггер 25 режима находится в нулевом состоянии, поэтому на его первом выходе присутствует нуль, а на втором выходе - единица, которая подается на первый вход первого 34 элемента И. В счетчике 22 расстояния содержится код нуля, в счетчике 23 последнего модуля содержится код единицы («00...01»). Группа 26.1-26.m триггеров находятся в состоянии логического нуля. В счетчиках группы 27.1-27.m счетчиков назначенных дуг первоначально хранятся коды нулей. Так как в счетчике 18 номера строки содержится единица, то этот код поступает на вход дешифратора 15 выбора строки. Поэтому на первом выходе дешифратора 15 выбора строки присутствует единичный сигнал, который подается на управляющие входы блока 30.1 элементов запрета и обеспечивает прохождение на его выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. В счетчике 20 фиксируемых дуг и в счетчике 21 значения содержится код единицы («00...01»).

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

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

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

Появление единичного сигнала на входе 38 запуска устройства запускает генератор 14 импульсов. Импульс с выхода генератора 14 импульсов поступает на второй вход первого 34 элемента И, и на второй вход второго 35 элемента И. Так как на первом входе второго 35 элемента И присутствует ноль с первого выхода триггера 25, то единичный сигнал на выходе элемента 35 И не появляется. Единичный сигнал со второго выхода триггера 25 подается на первый вход первого 34 элемента И. Так как на его втором входе присутствует единичный импульс с выхода генератора 14 импульсов, то на его выходе появляется единичный сигнал, который поступает на счетный вход счетчика 19 и по переднему фронту увеличивает его содержимое на единицу. В результате в нем устанавливается код двойки («00...010).

Сигналы с индикаторных выходов элементов первой строки матрицы 1 поступают на элементы ИЛИ 31.1-31.m, т.к. блок 30.1 элементов запрета открыт. Если на выходах элементов ИЛИ 31.1-31.m присутствуют единицы, то они поступают на соответствующие S-входы триггеров 26.1-26.m и устанавливают их в единичное состояние. Код двойки с выхода счетчика 19 поступает на установочный вход мультиплексора 17 выбора элемента и разрешает прохождение на его выход сигнала с выхода триггера 26.2. Единичный сигнал с выхода мультиплексора 17 выбора элемента поступает на разрешающий вход счетчика 20, разрешая тем самым появление на его выходе кода единицы («00...01»). Этот код поступает на второй вход элемента 29 сравнения, на первом входе которого присутствует код с выхода регистра 24, соответствующий количеству вершин графа. В результате сравнения на первом выходе элемента 29 сравнения появляется единичный сигнал, так как результат сравнения будет истинным (содержимое счетчика 20 меньше). Единичный сигнал с первого выхода элемента 29 сравнения подается на S-вход триггера 25 режима, устанавливая его в единичное состояние. Таким образом, на его первом выходе присутствует единичный импульс, а на втором - нулевой. В результате этого на первом входе элемента 34 И появляется ноль, что запрещает появление на его выходе положительных импульсов. В то же время, на первом входе элемента 35 И появляется единичный сигнал, который разрешает появление положительного импульса на его выходе при поступлении на его второй вход соответствующего положительного сигнала.

Следующий тактовый импульс поступает на вторые входы первого 34 и второго 35 элементов И. На выходе элемента 34 единичного сигнала не появляется, так как на его первом входе присутствует нулевой сигнал со второго выхода триггера 25. Единичный импульс появляется на выходе второго 35 элемента И, который подается на счетный вход счетчика 22, увеличивая в нем содержимое по переднему фронту до единичного кода («00...01»). Код значения единицы с выхода счетчика 22 подается на первый вход элемента 28 сравнения, на второй вход которого поступает код числа один с выхода счетчика 21. Результат сравнения будет положительным, так как коды равны друг другу. В результате на первом выходе элемента 28 сравнения появляется положительный импульс, который поступает на вход элемента 32 задержки и на счетный вход счетчика 23 (счетчик 23 увеличивается с учетом коэффициента пересчета n) и устанавливает в нем по переднему фронту код числа два («00...010»). Элемент 32 задержки задерживает прохождение импульса на время, достаточное для установки в счетчике 23 нового кода. Код числа два с выхода счетчика 23 поступает на вход дешифратора 16. К этому времени элемент 32 задержки пропускает импульс со своего входа, который подается на управляющий вход дешифратора 16, разрешая появление импульсов на выходе. Код числа два на входе дешифратора 16 возбуждает на его втором выходе положительный импульс, который поступает на счетный вход счетчика 27.2, увеличивая его содержимое по заднему фронту на единицу и устанавливая в нем код числа один («00...01»). Таким образом происходит фиксация первой дуги графа в смежных модулях КС (d_k'=1).

Следующий тактовый импульс с генератора 14 импульсов поступает на вторые входы элементов 34 и 35 И, при этом положительный импульс формируется только на выходе элемента 35 И, так как на его первом входе присутствует единичный сигнал с первого выхода триггера 25. Единичный сигнал с выхода элемента 35 И подается на счетный вход счетчика 22 и увеличивает его содержимое по переднему фронту до кода двойки («00...010»). Соответствующий код с его выхода подается на первый вход элемента 28 сравнения, на втором входе которого присутствует значение единицы с выхода счетчика 21. Результат сравнения будет ложным, и единичный импульс возбуждается на его втором выходе. Этот сигнал поступает на вход сброса счетчика 22, сбрасывая его содержимое по переднему фронту в ноль, на счетный вход счетчика 20, увеличивая его содержимое по переднему фронту до кода двойки («00...010»), и на второй вход элемента 36 ИЛИ. Этот импульс проходит через элемент 36 ИЛИ и поступает на R-вход триггера 25, устанавливая его в нулевое состояние. В этом случае на первом выходе триггера 25 появляется нулевой сигнал, а на втором - единичный. Нулевой сигнал подается на первый вход элемента 35 И и запрещает появление положительных импульсов на его выходе. В то же время единица на первом входе элемента 34 И со второго выхода триггера 25 разрешает появление единичных сигналов на выходе элемента 34 И.

Очередной тактовый импульс с выхода генератора 14 импульсов поступает на вторые входы элементов 34 и 35 И. Единичный сигнал появляется на выходе элемента 34 И, который поступает на счетный вход счетчика 19, увеличивая его содержимое по переднему фронту на единицу и устанавливая в нем код числа три («00...011»). Этот код с его выхода подается на установочный вход мультиплексора 17 выбора элемента и разрешает прохождение единичного сигнала с выхода триггера 26.3 на выход мультиплексора 17. Положительный импульс с выхода мультиплексора 17 поступает на разрешающий вход счетчика 20 и разрешает появление кода на его выходе. Код двойки («00...010») с выхода счетчика 20 подается на второй вход элемента 29 сравнения, на первом входе которого присутствует код количества вершин графа. Результат сравнения будет положительным и на первом выходе элемента 29 сравнения появляется положительный сигнал, который поступает на S-вход триггера 25 и устанавливает его в единичное состояние. Тогда на первом его выходе устанавливается единичный сигнал, а на втором - отрицательный, поэтому элемент 34 И закрывается для прохождения импульсов, а элемент 35 И - открывается.

Далее работа устройства продолжается аналогично вышеописанному. Следующий тактовый импульс с выхода генератора 14 импульсов поступает на второй вход элемента 35 И, поэтому на его выходе появляется единичный импульс, который подается на счетный вход счетчика 22, увеличивая его содержимое по переднему фронту на единицу и устанавливая в нем код числа один («00...01»). Значение единицы с выхода счетчика 22 подается на первый вход элемента 28 сравнения, на втором входе которого присутствует код единицы с выхода счетчика 21. Результат сравнения будет положительным, и единичный сигнал появляется на счетном входе счетчика 23 и на входе элемента 32 задержки. Счетчик 23 увеличивается по переднему фронту до кода числа три («00...011»). Код тройки подается на вход дешифратора 16. К этому времени элемент 32 задержки пропускает импульс, который подается на управляющий вход дешифратора 16. В результате на третьем его выходе возбуждается положительный импульс, который подается на счетный вход счетчика 27.3 и увеличивает его содержимое по заднему фронту на единицу. Так происходит фиксация второй дуги графа для значения d_k'=1.

Такая фиксация происходит для всех n дуг графа со значением d_k'=1 (их количество хранит счетчик 20 фиксируемых дуг). После того, как в счетчике 20 установится код n+1, соответствующее значение поступает на второй вход элемента 29 сравнения, на первый вход которого подается значение n количества вершин графа. Результат сравнения будет отрицательный, поэтому на втором выходе элемента 29 сравнения появляется единичный импульс, который подается на счетный вход счетчика 21 и увеличивает его содержимое по переднему фронту на единицу. Таким образом, значение устанавливается в двойку. Кроме этого, положительный импульс со второго выхода элемента 29 сравнения поступает на вход сброса счетчика 20 и на первый вход элемента 36 ИЛИ, а с его выхода - на R-вход триггера 25, устанавливая его в нулевое состояние. В счетчике 20 устанавливается начальный код единицы («00...01»).

Следующий импульс с генератора 14 импульсов подается на вторые входы элементов 34 и 35 И, но, так как на первом выходе триггера 25 присутствует нулевое значение, то на выходе элемента 35 И импульса не появляется, а появляется на выходе элемента 34 И, который поступает на счетный вход счетчика 19, и увеличивает хранящийся в нем код по переднему фронту на единицу. В случае появления на выходе переполнения счетчика 19 сигнала переполнения, этот импульс поступает на счетный вход счетчика 18, увеличивая его содержимое по переднему фронту на единицу, и устанавливает в нем код числа два («00...010»). Сигнал переполнения с выхода переполнения счетчика 19 подается также на R-входы группы 26.1, 26.2, ..., 26.m триггеров и устанавливает их в нулевое состояние. Код числа два с выхода счетчика 18 подается на вход дешифратора 15 выбора строки. Поэтому на втором выходе дешифратора 15 появляется единичный сигнал, который подается на управляющие входы блока 30.2 элементов запрета и обеспечивает прохождение на его выходы сигналов с индикаторных выходов элементов второй строки матрицы 1. С входов блока 30.2 элементов запрета сигналы матрицы 1. С входов блока 30.2 элементов запрета сигналы поступают на их выходы и далее через соответствующие элементы 31.1, 31.2, ..., 31.m ИЛИ проходят на S-входы соответствующих триггеров 26.1, 26.2, ..., 26.m, устанавливая их в единичное состояние (при наличии соответствующих единичных сигналов).

Далее работа устройства продолжается аналогично. Тактовый импульс поступает на счетный вход счетчика 19 и по переднему фронту устанавливает в нем новый код. Этот код подается на установочный вход мультиплексора 17 и разрешает прохождение сигнала с выхода триггера 26.i (i=1, 2, ..., m) на выход мультиплексора 17. Сигнал с его выхода подается на разрешающий вход счетчика 20 и разрешает появление сигналов на его выходе. С выхода счетчика 20 код подается на второй вход элемента 29 сравнения и сравнивается с кодом из регистра 24. Результат сравнения будет положительным и сигнал с первого выхода элемента 29 сравнения подается на S-вход триггера 25, устанавливая его в единичное состояние. Единичный сигнал с его выхода открывает для прохождения импульсов элемент 35 И, а нулевой сигнал со второго выхода закрывает элемент 34 И.

Очередной тактовый импульс поступает на счетный вход счетчика 22 и увеличивает его содержимое по переднему фронту на единицу, устанавливая в нем код единицы. Этот код с выхода счетчика 22 подается на элемент 28 сравнения, где сравнивается с кодом из счетчика 21 (d_k'=2). Результат сравнения будет положительным, и с его первого выхода сигнал поступает на счетный вход счетчика 23 и на вход элемента 32 задержки. Счетчик 23 увеличивается по переднему фронту (с коэффициентом пересчета n) на единицу. Этот код подается на вход дешифратора 16. К этому времени элемент 32 задержки пропускает импульс, который поступает на управляющий вход дешифратора 16 и код i (i=1, 2, ..., m), поступивший на вход дешифратора 16 возбуждает соответствующий i-й выход. Сигнал с i-го выхода дешифратора 16 подается на счетный вход счетчика 27.i и увеличивает его содержимое по переднему фронту на единицу.

Так продолжается, пока на втором выходе элемента 28 сравнения не появится положительный импульс. Этот сигнал увеличит по переднему фронту содержимое счетчика 20 на единицу, установит триггер 25 в нулевое состояние и содержимое счетчика 22 в ноль. Таким образом, производится фиксация дуги в КС при d_k'=2.

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

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

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

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