Устройство распределения задач по процессорам Советский патент 1990 года по МПК G06F15/163 

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

Целью изобретения является повышение быстродействия.

На чертеже представлена .функциональная схема устройства.

На схеме обозначены матрица 1 триг геров 2, группа элементов И 3, блоки 4.анализа связности задач группы, мат рица элементов И 5, блоки элементов ИЛИ 6 и 7, элемент ИЛИ 8, группа элементов ИЛИ-НЕ 9, группа элементов И 10, группа триггеров 11, элемент ИЛИ 12, элемент И 13, элемент 14 задержки, группа регистров 15, группа блоков элементов И 16, группа элементов ИЛИ 17, группа блоков 18 контроля данных, матрица элементов И 119, матрица элементов ИЛИ 20, группа шифраторов 21, матрица схем 22 сравнения, группа элементов И 23, группа преобразователей 24 кода, блок элементов И(И-НЕ) 25, группа блоков элементов И 26, элемент ИЛИ 27, группа входов 28 установки в О, группа входов 29 установки в 1, вход 30 запуска, группа входов 31 номера задачи, группа входов 32 готовности, выход 33 конца работы, группа выходо 34 индикации готовности устройства, группа информационных выходов 35 устройства, выход 36 синхронизации устрбйства, преобразователи 37 кода связности матрицы задач в двоичный код группы и преобразователь 38 кода готовности процессоров в унитарный код.

25

30

35

40

45

50

55

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

В исходном состоянии триггеры 2 и 1 1 обнулены. По входам 29 в триггеры 2 заносится информация о топологии графа (вершины которого соответствуют задачам, а ветви - информационно-управляющим связям между ними). В соответствующий регистр 15 по входу 31 заносятся код номера задачи . и исходные данные для ее вьтолнения.

В работе устройства можно вьщелить три этапа.

На первом этапе производится определение независимых задач. При этом на выходах соответствующих элементов ШШ-НЕ 9 в столбцах, кот,орые соответствуют начальным вершинам информационно-управляющего графа, появляются высокие потенциалы, так как начальные вершины не содержат входящих ветвей, и триггеры 2 в этих столбцах находятся в нулевом состоянии. Импульс, запуска по входу 30 устройства устанавливает в нулевое состояние триггеры 11 и, пройдя через элемент ИЛИ 8, открьгоает элементы ИЗ, которые пропускают на выход сигналы выбора блоков 4.

На втором этапе производится выбор среди независимых задач тех, которые, будучи представленными в графе, имеют минимальную связность на полную глубину графа. Сигнал с выхода КР-го триггера 2 подается на первый вход КР-го элемента И 5 всех блоков 4. На вторые входы элементов И 5 К-й строки К-го блока 4 поступает сигнал с выхода К-го элемента И 3. Если

К-я задача независима, то в К-м блоке 4 открываются элементы И 5 К-й строки в столбцах, определяемых номерами конечных вершин для дуг, исходящих из К-й вершины. Сигналы с их выходов поступают на входы элемента ИЛИ 6 К-й строки и соответствующие элементы ИЛИ 7. Сигналы с выходов элементов ИЛИ 7 поступают на вторые входы элементов И 5 соответствующих строк (за исключением К-й строки). Если задания, соответствующие этим строкам, имеют исходящие дуги, то опять открьшаются элементы И 5 в этих строках, соответствующие номерам конечных верщин для данных дуг и т.п. Таким образом, на выходах элементов ИЛИ 6 (т.е. на выходах К-го блока 4) содер- .жится количество единичных сигналов, равное количеству дуг, которые необходимо пройти до выполнения конечных задач графа от К-й задачи. Коды с выходов соответствующих блоков 4 подаются на входы преобразователей 37, где при помощи блоков 18, 24 и 21 преобразуются в двоичный код. Двоичные коды подаются на матрицу схем 22 сравнения. На выходе элемента И 23, соответствующего номеру задания с максимальной связностью на полную глубину графа (в случае равнозначности двух и более заданий - номеру младшего из них), появляется единичный сигнал, который поступает на вход соответствующего элемента И 10, сигнал с выхода которого открывает соответствующий блок элементов И 16 и устанавливает в единичное состояние триггер 11.

На третьем этапе производится распределение выбранных независимых задач по свободным процессорам, вьдача процессорам вьиислительного комплекса исходных данньк для обслуживания за-- дач и установка в нулевое состояние триггеров 2 матрицы 1 тех строк, номера которых соответствуют номерам задач, обслуженных процессорами. Выбранный блок элементов И 16 пропускает на входы элементов ИЛИ 17 код номера задачи и исходных данных для ее вьтолнения с выхода соответствующего регистра 15. По входам 32 устройства подаются сигналы готовности процессоров комплекса на входы преобразова-i теля 38, среди которых выбирают млад- ий и оповещают его по соответствуюему выходу устройства 34 о том, что

15

е и х-

1594559

ему предстоит обслужить очередную задачу. Сигнал с выхода элемента 14 задержки, необходимого для учета вре- мени срабатывания устройства,в совокупности с сигналом с соответствующего выхода преобразователя 24 открывает блок элементов И 26 и пропускает на его выход, т.е. на вход младшего свободного процессора в комплексе, код номера выбранной задачи и исходные данные для ее выполнения Момент вьщачи определяется сигналом на выходе 36 устройства. В том случае, если еще остались независимые задачи (сигнал на выходе элемента ИЛИ 12 имеет единичное значение) и в комплексе есть свободные процессоры (сигнал на выходе элемента ИЛИ 27 имеет единичное значение), устройство запускается вновь сигналом с выхода элемента И 13. При окончании обработки одной из задач поступает сигнал по соответствующему

входу 28 устройства, который устанавливает в нулевое состояние триггеры 2 соответствующей строки матрицы I и, пройдя через элемент ИЛИ 8, при наличии независимых задач и свободных процессоров вновь запускает устройство. Окончание обслуживания всех задач сигнализируется нулевым значением на выходе 33 устройства.

35

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

Устройство распределения задач по процессорам, содержащее матрицу триггеров, три группы элементов И, 40 три элемента ИЛИ, элемент И, элемен задержки, группу элементов ШШ-НЕ, группу триггеров, группу регистров, две группы блоков элементов И, группу элементов ИЛИ, группу преоб- 45 Разователей кода связности матрицы задач в двоичный код, матрицу схем сравнения, преобразователь кода готовности процессоров в унитарный код, причем К-й вход установки в 1 50 .устройства поключен к входам установки в 1 триггеров К-й строки матрицы (К 1,N, число задач), Р-й вход (Р 1,N) номера задачи устройства подключен к входу 55 Р-го регистра группы, вход запуска устройства соединен с первым входом первого элемента ИЛИ и входами установки в О триггеров группы, К-й вход установки в О устройства подключей к входам установки в О триггеров К-й строки матрицы и к (К+1)-му входу первого элемента ИЛИ, а-й вход готовности устройства (;т 1 ,М, где М - число процессоров н составе вычислительного комплекса) г|одключен к т-му входу преобразовате- jJH кода готовности процессоров в у нитарный код, выход Р-го элемента фш-НЕ группы подключен к Р-му входу ВТОРОГО элемента ИЛИ и к первым вхо- Дам Р-х элементов И первой и второй lipynn, выход первого элемента ЛЛИ. сое- Динён с первым входом элемента И вторыми входами элементов И первой 1 руппы, вькод Р-го элемента И второй : руппы соединен с входом установки в Р-го триггера группы и первыми

выход Р-го преобразователя кода свя ности матрицы задач в двоичный код

группы подключен к первым

г-го разряда ( ,N-1 ; ,N и к вторым входам г-го разряда ji-x схем сравнения матрицы, выход призн ка больше или равно РК-й схемы срав ния матрицы соединен с (К-1)-м вход

0 Р-го, а выход признака меньше КР-й с К-м входом Р-го элемента И третье группы, выход которого подключен к второму входу Р-го элемента И второ группы, выход т-го блока элементов

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

ходами элементов И Р-го блока первой JQ лиза связности задач, причем выход Группы, выход s-ro (s 1,S, где - разрядность кода номера задачи и исходных данных) разряда Р-го ре- Ыстра группы соединен с вторым вхо-. Дом s-ro элемента и Р-го блока пер- группь, выход которого подключен К Р-му входу s-ro элемента .ИЛИ группы, выход Р-го триггера группы соединен с (N+1)-M входом Р-го элемента ИЛИ-НЕ группы, выход второго элемента ИЛИ подключен к второму входу элемента И и к выходу конца работы устройства, выход элемента И соединен с входом элемента задержки, выход которого подключен к (Ы+2)-му входу первого элемента ИЛИ, к первым входам элементов И всех блоков второй группы и к выходу синхронизации устройства, выход s-ro элемента ИЛИ группы подключен к вторым входам S-X элементов И всех блоков второй группы, т-й выход преобразователя кода готовности процессоров в унитарный код подключен к т-му выходу инКР-го триггера матрицы подключен к КР-м входам блоков анализа связности задач группы, выход Р-го элемент И первой группы соединен с входом в 25 бора Р-го блока анализа связности задач группы, К-й выход Р-го блока анализа связности задач группы подключен к К-му входу Р-го преобразов теля кода связности матрицы задач 30 в двоичный код группы, причем блок анализа связности задач содержит матрицу элементов И и два блока элементов ИЛИ, КР-й вход блока ана лиза связности задач подключен к 35 первому входу КР-го элемента И мат рицы, вход выбора К-го блока анали связности задач соединен с вторыми входами элементов И К-й строки мат цы, выход КР-го элемента И матрицы подключен к Р-му входу К-го элемен та ИЛИ первого блока и к К-му вход Р-ГО элемента ИЛИ второго блока, вы ход К-го элемента ИЛИ первого блок соединен с К-м выходом блока анали

40

выход Р-го преобразователя кода связности матрицы задач в двоичный код i

группы подключен к первым

г-го разряда ( ,N-1 ; ,N) и к вторым входам г-го разряда ji-x схем сравнения матрицы, выход признака больше или равно РК-й схемы сравнения матрицы соединен с (К-1)-м входом

Р-го, а выход признака меньше КР-й - с К-м входом Р-го элемента И третьей группы, выход которого подключен к второму входу Р-го элемента И второй группы, выход т-го блока элементов

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

КР-го триггера матрицы подключен к КР-м входам блоков анализа связности задач группы, выход Р-го элемента И первой группы соединен с входом вы- бора Р-го блока анализа связности задач группы, К-й выход Р-го блока анализа связности задач группы подключен к К-му входу Р-го преобразователя кода связности матрицы задач в двоичный код группы, причем блок анализа связности задач содержит матрицу элементов И и два блока элементов ИЛИ, КР-й вход блока анализа связности задач подключен к первому входу КР-го элемента И матрицы, вход выбора К-го блока анализа связности задач соединен с вторыми входами элементов И К-й строки матрит цы, выход КР-го элемента И матрицы подключен к Р-му входу К-го элемента ИЛИ первого блока и к К-му входу Р-ГО элемента ИЛИ второго блока, выход К-го элемента ИЛИ первого блока соединен с К-м выходом блока анали

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах. Целью изобретения является повышение быстродействия. Устройство содержит матрицу 1 триггеров 2, группу элементов И 3, блоки 4 анализа связности задач группы, матрицу элементов И 5, блоки элементов ИЛИ 6,7, элемент ИЛИ 8, группу элементов ИЛИ-НЕ 9, группу элементов И 10, группу триггеров 11, элемент ИЛИ 12, элемент И 13, элемент задержки 14, группу регистров 15, группу блоков элементов И 16, группу элементов ИЛИ 17, группу блоков 18 контроля данных, матрицу элементов И 19, матрицу элементов ИЛИ 20, группу шифраторов 21, матрицу схем сравнения 22, группу элементов И 23, группу преобразователей 24 кода, блок элементов И/И-НЕ/ 25, группу блоков элементов И 26, элемент ИЛИ 27, группу входов установки 28 в ноль, группу входов установки 29 в единицу, вход 30 запуска, группы входов 31 номера задачи 32 готовности, выход 33 конца работы, группу выходов 34 индикации готовности, группу 35 информационных выходов, выход 36 синхронизации устройства, преобразователь 37 кода связности матрицы задач в двоичный код группы, преобразователь 38 кода готовности процессоров в унитарный код. Поставленная цель достигается введением новых элементов и связей. 1 ил.