Устройство для распределения заданий процессорам Советский патент 1987 года по МПК G06F9/50 

.1

Изобретение относится к вычислительной технике и может быть исполь- зовано для распределения заданий процессорам мультипроцессорной системы.

Цель изобретения - расширение области применения устройства за счет аппаратной реализации функций диспетчера вычислительной системы.

На фиг. 1 показана- структурная схема устройства (для вершин); на фиг. 2 - блок сортировки информации; на фиг. 3 - ячейка итеративной сети.

Устройство содержит матрицу 1 формирователей весов дуг, состоящую из формирователей 2,, -2,, весов дуг,каждый из которых состоит из счетчики 3, первого и второго триггеров 4 и 5 и элементов И 6, - 6j, элемент 7 задержки, генератор 8 тактовых импульсов, блока 9 управления, включающий элементы И 10 и 11, триггер 12, элемент И 13, вход 14 пуска устройства, сигнальный выход 15 устройства, элементы 16 - 16, запрета, регистрирующие счетчики 17 ( - 17-.), блоки элементов И 18, - 18,, блок 19 сортировки информации, группу входов 20 и выходов 21 блока 19, группу входов 22 сброса счетчиков 17, регистр 23 приоритета, регистр 24 выбранных вершин, группу информационных выходов 25( - 25, первую и вторую группы информационных входов 26) - 26 и 27, - 27J устройства, вход 28, ячейки 29, элементы НЕ 30, блок элементов И 31, входы 32-38, выходы 39-41, элементы И 42 и 44 и элементы НЕ 43 и 45.

Устройство работает следующим образом.

В исходном состоянии регистры 23 и 24, счетчики 17 и 17 находятся в нулевом состоянии, а триггер 12 - в единичном состоянии, в счетчик 17 записано максимальное число, в матрицу 1 заносится информация о топологии ориентированного графа. При этом триггеры 4 и 5 формирователей 2, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствующий формирователь 2 определяется пересечением строки с номером, равным номеру начального узла моделирующей ветви, и столбца с номером ее конечного узла. В счетчике 3 соответствующих формировате1 2

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

элементов И 6, объединяющих выходы формирователей 2 в столбцах, соответствующих начальным узлам графа, устанавливаются высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель начальные узлы не содержат входных ветвей, а следовательно, и триггеры 4 и 5, находящиеся в этом столбце, находятся в нулевом состоянии. Исходный граф заносится в матрицу 1 в инверсном порядке, т.е. матрица сличимости заносимого графа транспортирована относительно главной диагонали. Это позволяет для расчета максимальных путей в графе использовать процедуру динамического программирования.

С появлением пускового сигнала на входе 14 срабатывает триггер 14

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

генератора 8 через элемент И 10 поступают на входы всех элементов 16( - 16,, запрета и на счетные входы счетчиков 3 всех формирователей 2. При этом начинают работать счетчики 3

тех формирователей 2, которые моделируют веса дуг, исходящих из начального узла графа, за счет подачи высокого потенциала с выхода элемента И 6, на разрешающие входы счетчиков

3 формирователей 2 „ - 2 , . Импульсы от генератора 8 проходят на регистрирующие счетчики 17 всех вершин графа, кроме начальной, так как на выходе элемента И 6, устанавливаетя высокий потенциал, следовательо, элемент 16, запрета не пропусает импульсы от генератора 8 на реистрирующий счетчик 1 7 .

Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 3 одного из формирователей 2 переполняется, устанавливается в нулевое состояние соответствующий

триггер 4 и на вход соответствуюего элемента И 6 поступает высокий отенциал с инверсного выхода этого триггера. Если на остальных входах того элемента И 6 находится высокий

потенциал, единичный уровень поступает на соответствующий элемент 16 запрета и закрывает его. Это свидетельствует о том, что все веса дуг, входящих в узел графа, номер которо- го соответствует номеру столбца формирователей 2, объединенных этим элементом И 6, сформированы. При этом формируется разрешение работы счетчиков 3 формирователей 2, моделирующих ветви графа, исходящие из формированного узла графа. На выходе счетчика 17 данного столбца фиксируется время максимального пути для данной вершины графа.

Подсчитывание импульсов в счетчиках 17 продолжается до тех пор, пока на выходах всех элементов И 6 не присутствует высокий потенциал. Это свидетельствует о том, что все узлы исследуемого графа сформированы. Все это время на выходах 21 блока сортировки информации 19 присутствуют нулевые потенциалы, так как он закры

по управляющему входу 28. Одновремен-25 мы диспетчер посылает единичный сигное наличие единичных потенциалов на входах элемента И 11 приводит к срабатыванию триггера 12 блока 9 управления. На вход элемента И 10 поступает нулевой потенциал, который прекращает подачу импульсов генератора 8 в схему. В это же время сигналом с единичного выхода триггера 12 сбра- сьшаются все триггеры 5, которые

нал на соответствующий вход 27, ко рый обнуляет триггеры 4 соответствующей строки формирователей 2. По ле этого появляются единичные сиг 30 лы на выходе элемента И 6 одного и нескольких столбцов. Дальнейшая ра та устройства происходит аналогичн описанному. При наличии в регистре 23 приоритетов нескольких единиц д

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

i

Таким образом, в триггеры 4 всех формирователей 2 переписывается информация о топологии ориентированного графа. После этого единичный потенциал, задержавшись на линии задержки 7 на время, необходимое для срабатывания элементов матрицы формирователей 1, поступает на управляющий вход 28 блока сортировки информации и открывает его.Так как начальная вершина графа.не зависит ни от каких других, на всех входах элемента И 6 появляются единичные потенциалы, на его выходе появляется высокий потенциал, который, поступая на вход элемента И 18,, разрешает подачу с вьпсода счетчика 17 кода на вход 20. блока 19 сортировки информации, который обеспечивает

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

40 записаны единицы, которые откроют элемент И 13, с выхода которого ед ничный сигнал поступает на выход 1 сигнализируя о том, что работа уст ройства закончена. Этим же сигнало

45 сбрасываются все разряды регистра После восстановления исходного сос тояния схемы весь цикл можно повто рить заново.

Блок 10 сортировки информации с

50 держит однородную структуру размер N X М (фиг. 2), где М - разрядност счётчика 17, N - количество столбц матрицы 1 (фиг. 1), блок элементов 31 с управляющим входом 32. Таким

55 разом, на каждую строку матрицы (в ды 20, - 20) поступает .одно число а одноименные разряды всех чисел р положены в одноименных столбцах ма рицы (старшие разряды слева). Для

появление высокого потенциала на одном или нескольких выходах, которые соответствуют максимальному ко- ду,,подаваемому на его входы. Вследствие этого высокий потенциал с выхода 21, блока 19 сортировки информации записывается в первьй разряд регистра 23 приоритетов, на выходе которого в первом разряде появляется высокий потенциал и поступает на выход 25( и далее к диспетчеру вычислительной системы, который выбирает на реализацию соответствующую программу. После выбора соответствующей программы для реализации ее в вычислительной системе диспетчер записывает единицу в соответствующий разряд регистра 24 выбранных вершин, которая обнуляет соответствующий разряд регистра 23 и счетчик 17.

До момента выполнения подпрограммы, выбранной на реализацию в устройстве, никаких изменений не происходит После выполнения данной подпрограмнал на соответствующий вход 27, который обнуляет триггеры 4 соответствующей строки формирователей 2. После этого появляются единичные сигна- лы на выходе элемента И 6 одного или нескольких столбцов. Дальнейшая работа устройства происходит аналогично описанному. При наличии в регистре 23 приоритетов нескольких единиц дисграмму, для которой номер разряда, содержащего единицу, наименьший.Когда все программы взяты на обслуживание, во всех разрядах регистра 24

записаны единицы, которые откроют элемент И 13, с выхода которого единичный сигнал поступает на выход 15, сигнализируя о том, что работа устройства закончена. Этим же сигналом

сбрасываются все разряды регистра 24. После восстановления исходного состояния схемы весь цикл можно повторить заново.

Блок 10 сортировки информации содержит однородную структуру размером N X М (фиг. 2), где М - разрядность счётчика 17, N - количество столбцов матрицы 1 (фиг. 1), блок элементов И 31 с управляющим входом 32. Таким образом, на каждую строку матрицы (входы 20, - 20) поступает .одно число, а одноименные разряды всех чисел расположены в одноименных столбцах матрицы (старшие разряды слева). Для

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

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

j-й шаг. Просматриваются информа- ционные входы j-ro столбца в тех строках, которые выделены На (j-l)-M шаге. Если все эти разряды содержат нули, на следующем шаге просматриваются (j+1)-e разряды тех же строк. Если на просматриваемых информационных входах имеются как нули, так и единицы, на (j+)-M шаге просматриваются только строки, соответствуюш 1е единицам. Вьщеленное на последнем (М-м) шаге подмножество строк содержит максимальное число.

Данный алгоритм реализован с помощью двумерной интеративной сети с двумя направлениями распространения межэлементньЕх сигналов.

В горизонтальном направлении имеется цепь, просматривающая последо

вательно, слева направо, информационные входы и продолжающая з.тот просмотр, если на данном информационном входе находится единица или если на всех просматриваемых информационных -входах в данном столбце находятся нули. Эту работу выполняет двоичный канал, реализующий в каждой ячейке 29 (фиг.З) итеративной сети логическую функцию z z (а V у),

где z - сигнал на боковом выходе 39

ячейки 29;

z - сигнал на боковом входе 38/ а - информационный вход 37; у - переменная, характеризующая содержимое просматриваемых ячеек данного столбца (вход 36) : у 1, если все.они содержат нули и у О - в противном случае.

На входе 38 (z) всех ячеек левого столбца матрицы поданы граничные константы z 1 (вход 34 блока 19 сортировки, информации) . Поэтому наличие сигнала z 1 (на выходе 39) в горизонтальном канале любой строки означает, что данная строка подлежит дальнейшему просмотру (в противном случае сигнал z принимает значение О, ко торое в дальнейшем измениться не может) .

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

х X V а Z,

где х - сигнал на нижнем выходе

40 ячейки 29, X - сигнал на верхнем входе 35

ячейки 29.

На входы X (вход 35) всех ячеек 29 верхней строки матрицы подаются граничные константы х 0. Поэтому

межэлементньш сигнал х (выход 40) принимает значение 1 в первой же

(начиная сверху) ячейке 29, которая подлежит просмотру (z 1), и содержит единицу (а 1), причем х 1 в дальнейшем измениться не может. Только в таком случае, если в проверяемом столбце нет ни одной такой ячейки, в вертикальном канале сохраняется х О и на выходе 41 нижней (N-й)ячейки столбца вырабатывается x j, 0.

Для правнпьной работы горизонтальных каналов организован еще один проходной вертикальный канал у (вход Зб) и соединен в каждом столбце его вход с выходом х (выход 40) через инвертор 30. Вся система логических функций ячейки итеративной сети, реализующей поиск максимума, имеет следущий вид:

(avy) - горизонтальный канал

х xvaz l J

- вертикальные каналы

у х - вспомогательная функция.

о N

После подачи граничных сигналов Z(, сигналы z 1 на прав.ой границе матрицы установятся в строке или нескольких строках, которые содержат максимальные числа.

Разрешающий сигнал поступает на вход 28 блока 19 сортировки информации и поступает на управляющий вход 32 блока элементов И 31, разреша51

прохождение информации с выхода матрицы через блок элементов И 31 на выходы 21, 21, блока 19 сортировки.

Формула изобретения

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

формационных входов устройства, о т- личающееся тем, что, с целью расширения области применения устройства, в каждый формирователь весов дуг введены матрицы формирователей, второй триггер, а в устройство введено N элементов запрета,элемент задержки, в блок управлениявведен третий элемент И, причем в каждом формирователе весов дуг матришл нулевой выход второго триггера соединен с 1-входом первого триггера, R-входы первых триггеров формирователей весов дуг i-й строки матрицы соединены между собой и подключены к i-му входу второй группы информационных входов устройства, прямые входы элементов запрета соединены с выходом первого элемента И блока управления, выход i-ro элемента запрета соединен со счетным входом i-ro регистрирующего счетчика, группа входов третьего элемента И блока ynpaiB- ления соединена с группой выходов регистра выбранных вершин, выход третьего элемента И блока управления соединен с сигнальным выходом устройства и с входами сброса всех разрядов регистра выбранных вершин, выход i-ro разряда регистра выбран- йых вершин соединен с входом сброса. i-ro регистрирующего счетчика и с входом сброса i-ro разряда регистра приоритетов, выход i-ro элемента И группы соединен с входом i-ro блока элементов И группы блоков элементов И и с инверсным входом i-ro элемента запрета того же столбца, прямой выход триггера блока управления соединен с К-входами вторых триггеров всех формирователей весов дуг. матрицы и с входом элемента задержки, выход которого соединен с управляющим входом блока сортировки информации, нулевой выход триггера блока управления соединен с вторым входом первого элемента И блока управления, выход которого соединен со счетными входами счетчиков всех формирователе весов дуг матрицы.

.. «N4 si vo

Csj «M CM

Tin,

Фиг.

55 Ъ6Ъ1

Ц

.2/2

Фиг. 2

Фи&З

Составитель М.Сорочан Редактор Н.Рогулич Техред м.Ходанич

Заказ 2513/43 Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Корректор F.Решетник

Изобретение относится к вычислительной технике и может быть использовано для распределения заданий процессорам мультипроцессорной системь). Устройство для распределения заданий процессорам содержит Матрицу формирователей весов ДУГ, группу элементов запрета, группу счетчиков, группу блоков элементов ; И, блок сортировки информации, регистр приоритетов,регистр выбранных вершин, блок управления. В матрицу формирователей весов дуг заносится информация о топологии ориентирован- ного графа и весах дуг. При поступ лении входного сигнала в регистрирующих счетчиках накапливаются импульсы, число которых пропорционально времени максимального пути для соответствующей вершины графа. После того как будет сформирована необхо- димая информация в счетчиках, в соответствующий разряд регистра приоритетов с помощью блока сортировки информации будет записана логическая единица и на обслуживание выберется готовая вершина, для которой время максимального пути наибольшее. 3 ил. I W со х :о