Устройство распределения задач по процессорам

 

Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах. Целью изобретения является повышение быстродействия. Устройство содержит матрицу 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 ил.

СОЮЗ СОЕЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)5 G 06 Р !5/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

npH rHHT СССР

1 (21) 4463785/24-24 (22) 20.07.88 (46) 23.09.90. Бюл. !! 35 (72) С.В.Ефимов, Н.В.Кутузов, M.Ì.3àðåöêèé и В.В.Мазаник (53) 681.32(088.8) (56) Авторское свидетельство СССР

Ф 1037267, кл. G 06 F 15/20, !983.

Авторское свидетельство СССР

У 1427381, кл. G 06 F 15/20, !987. (54) УСТРОЙСТВО РАСПРЕДЕЛЕНИЯ ЗАДАЧ

ПО ПРОЦЕССОРАМ

„.,SU„„1594559 A 1

2 (57) Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах. Целью изобретения является повышение быстродействия. Устройство содержит матрицу ! триггеров 2,,группу элементов И 3, блоки 4 анализа связности задач группы, матрицу элементов И 5, блоки элементов ИЛИ 6, 7, элемент ИЛИ 8, группу элементов ИЛИ-НЕ 9, группу элементов И 10, группу триггеров 11, 1594559

10 элемент ИЛИ 12, элемент И 13, элемент задержки 14, группу регистров

15, группу блоков элементов И 16, группу элементов ИЛИ 17, группу блоков 18 контроля данных, матрицу элементов И 19, матрицу элементов

ИЛИ 20, группу шифраторов 21, матрицу схем сравнения 22, группу элементов

И 23, группу преобразователей 24 кода, блок элементов И (И-НЕ) 25, группу блоков элементов И 26, элемент ИЛИ 27, группу входов установИзобретение относится к вычислительной технике и может быть использована в многопроцессорных вычислительных комплексах.

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

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

На схеме обозначены матрица 1 триггеров 2, группа элементов И 3, блоки

4.анализа связности задач группы, мат-30 рица элементов И 5, блоки элементов

ИЛИ 6 и 7, элемент ИЛИ 8, группа элементов ИЛИ-НЕ 9, группа элементов

И 10, группа триггеров 11, элемент

ИЛИ 12, элемент И 13, элемент 14 35 задержки, группа регистров 15, группа блоков элементов И 16, группа элементов ИЛИ 17, группа блоков 18 контроля данных, матрица элементов И 19, матрица элементов ИЛИ 20, группа

40 шифраторов 21, матрица схем 22 сравнения, группа элементов И 23, группа преобразователей 24 кода, блок эле-: ментов И(И-НЕ) 25, группа блоков элементов И 26, элемент ИЛИ 27, группа входов 28 установки в "О", группа входов 29 установки в "1", вход 30 запуска, группа входов 31 номера задачи, группа входов 32 готовности, выход 33 конца работы группа выходов

34 индикации готовности устройства, группа информационных выходов 35 устройства, выход 36 синхронизации устройства, преобразователи 37 кода связности матрицы задач в двоичный . код группы и преобразователь 38 кода готовности процессоров в унитарный код. ки 28 в ноль, группу входов установки 29 в единицу, вход 30 запуска, группы входов 31 номера задачи и

32 готовности, выход 33 конца работы, группу выходов 34 индикации готовности, группу 35 информационных выходов, выход 36 синхронизации устройства, преобразователь 37 кода связности матрицы задачв двоичныйкод группы, преобразователь 38 кода готовности процессоров в унитарный код. Поставленная цель достигается введением новых элементов и связей. 1 ил.

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

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

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

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

На первом этапе производится определение независимых задач. При этом на выходах соответствующих элементов

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

ИЛИ 8, открывает элементы И 3, которые пропускают на выход сигналы выбора блоков 4.

На втором этапе производится выбор среди независимых задач тех, которые, будучи представленными в графе, имеют минимальную связность на полную глубину графа. Сигнал с выхода

KP-го триггера 2 подается на первый вход KP-го элемента И 5 всех блоков

4. На вторые входы элементов И 5 К-й строки К-го блока 4 поступает сигнал с выхода К-ro элемента И 3. Если ему предстоит обслужить очередную задачу. Сигнал с выхода элемента 14 задержки, необходимого для учета времени срабатывания устройства,в совокупности с сигналом с соответствующего выхода преобразователя 24 открывает блок элементов И 26 и пропускает на его выход, т.е. на вход младшего свободного процессора в комплек" се, код номера выбранной задачи и исходные данные для ее выполнения-.

Момент выдачи определяется сигналом на выходе 36 устройства. В том случае, если еще остались независимые задачи (сигнал на выходе элемента

ИЛИ 12 имеет единичное значение) и в комплексе есть свободные процессоры (сигнал на выходе элемента

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

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

Устройство распределения задач по процессорам, содержащее матрицу .. триггеров, три группы элементов И, три элемента ИЛИ, элемент И, элемент задержки, группу элементов ИЛИ-НЕ, группу триггеров, группу регистров, две группы блоков элементов И, группу элементов ИЛИ, группу преобразователей кода связности матрицы задач в двоичный код, матрицу схем сравнения, преобразователь кода готовности процессоров в унитарный код, причем К-й вход установки в "1" новки в "1" триггеров К-й строки матрицы (К = l N где N — число задач), P-й вход (P 1,N) номера задачи устройства подключен к входу

P-ro регистра группы, вход запуска устройства соединен с первым входом первого элемента ИЛИ и входами установки в "0" триггеров группы, К-й вход установки в "0" устройства под5 !594559

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

5 поступают на входы элемента ИЛИ 6

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

На третьем этапе производится распределение выбранных независимых задач по свободным процессорам, выдача процессорам вычислительного комплекса исходных данных для обслуживания за-" 45 дач и установка в нулевое состояние триггеров 2 матрицы 1 тех строк, номера которых соответствуют номерам задач, обслуженных процессорами. выбранный блок элементов И !6 пропус- 50 -УстРонства поключен к входам Устакает на входы элементов ИЛИ 17 код номера задачи и исходных данных для ее выполнения с выхода соответствующего регистра 15. По входам 32 устройства подаются сигналы готовности процес- 55 соров комплекса на входы преобразова-t теля 38, среди которых выбирают млад- ший и оповещают его по соответствующему выходу устройства 34 о том, что

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

r-ro разряда ij=x (i=1,N-l; j=i+1,N) и к вторым входам r-ro разряда ja.-x схем сравнения матрицы, выход признака больше или равно РК-й схемы сравнения матрицы соединен с (К-1)-м входом с К-м входом Р-ro элемента И третьей группы, выход которого подключен к второму входу P ãî элемента И второй группы, выход m-ro блока элементов

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

КР-ro триггера матрицы подключен к

КР-м входам блоков анализа связности задач группы, выход Р-ro элемента

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

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

P-ro элемента ИЛИ второго блока, выход К-ro элемента ИЛИ первого блока соединен с К-м выходом блока анализа связности задач, выход P-го элемента ИЛИ второго К-ro блока анализа связности задач подключен к вторым входам элементов И Р-й строки матрицы (К=l,...,P-l,Ð+1,...,N) °

45 составитель М.Силин

Техред м дн ык Корректор С.Шевкун

Редактор И.Шмакова

Заказ 2831 Тираж Бб9 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

1 ключен к входам установки в "0" триггеров К-й строки матрицы и к (К+1)-му входу первого элемента ИЛИ, ш-й вход готовности устройства (m =1,М, где М " число процессоров в составе вычислительного комплекса) подключен к m-му входу преобразоватех я кода готовности процессоров в нитарный код, выход P-ro элемента

-HE группы подключен к P-му входу . второго элемента ИЛИ и к первым вхо-.

gaM P-х элементов И первой и второй друпп, выход первого элемента ИЛИ соединен с первым входом элемента И и вторыми входами элементов И первой группы, выход P-ro элемента И второй группы соединен с входом установки в

".1" P-го триггера группы и первыми входами элементов И P-ro блока первой группы, выход s-ro (s = 1,S, где

 — разрядность кода номера задачи

Й исходных данных) разряда P-горегистра группы соединен с вторым вхо-. дом s-го элемента и P-ro блока первой группы, выход которого подключен

К P-му входу s-го элемента ИЛИ группы, выход P-ro триггера группы сое, динен с (И+1)-м входом P-го элемента ИЛИ-НЕ группы, выход второго эле— мента ИЛИ подключен к второму входу элемента И и к выходу конца работы устройства, выход элемента И соединен с входом элемента задержки, выход которого подключен к (N+2)-му входу первого элемента ИЛИ, к первым входам элементов И всех блоков второй группы и к выходу синхронизации устройства, выход в-го элемента ИЛИ группы подключен к вторым входам

s-х элементов И всех блоков второй группы, ш-й выход преобразователя кода готовности процессоров в унитарный код подключен к m-му выходу индикации готовности группы устройства, третьим входам элементов И ш-го блока второй группы и к m-му входу третьего элемента ИЛИ, выход которого соединен с третьим входом элемец- . та И, r-й fr =1,R, где К=int(log,,N)) 1p P-го, а выход признака меньше КР-й — .

Устройство распределения задач по процессорам Устройство распределения задач по процессорам Устройство распределения задач по процессорам Устройство распределения задач по процессорам 

 

Похожие патенты:

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

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

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

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

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

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

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

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

Изобретение относится к области вычислительной техники

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и микроэлектронике

Изобретение относится к вычислительной технике и может быть использовано при решении задач информационно-поисковой и логической обработки данных в составе векторных ЭВМ и систем и форматирования данных

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