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

 

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

союз советских социАлистических

РЕСПУБЛИК (51)з 6 06 F 9/46

ГОсудАРстВенный комитет

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4873526/24 (22) 10.10.90 (46) 30,07.92, Бюл. ¹ 28 (71) Московский институт инженеров гражданской авиации (72) С. Ж, Кишенский, С. В. Каменский, Е, Н, Надобных и О, Ю. Христенко (56) Авторское свидетельство СССР № 1269136, кл. G 06 F 9/46, 1982, Авторское свидетельство СССР

¹ 1509895, кл. G 06 F 9/46, 1988. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычислитель- . ной технике и может быть использовано s многопроцессорных системах для .операI

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

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

ИЛИ, вторые входы которых подключены к информационным выходам блока регистров, синхронизирующий вход устройства соединен с вторым входом элемента И, так Ж 1751760 А1 тивного распределения заданий процессорам. Цель изобретения — расширение области применения устройства за счет обеспечения возможности решения задачи на конкретном процессоре. Устройство содержит блок регистров, два блока элементов И, блок элементов ИЛИ, коммутатор, два дешифратора, элемент ИЛИ и каналы, каждый из которых содержит, триггер, регистр, два блока элементов И, два элемента ИЛИ и два элемента И. Настоящее устройство позволяет распределять задания и в том случае, когда процессоры являются специализированными. не предназначенными для решения всех типов задач. 1 з. и. ф-лы, 2 ил. товым входом блока регистров и входами первых элементов И блоков всех каналов, выходы блоков элементов И каналов являются группами информационных выходов устройства.

Недостатки известного устройства— низкое быстродействие и узкая область применения.

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

ИЛИ, первый и второй блоки элементов И, три элемента ИЛИ, элемент И, причем группа информационных входов устройства подклЮчена к группам информационных входов первого и второго блоков элементов И, выходы первого блока элементов И подключе1751760

50 ны к группе информационных входов блока регистров, выходы второго блока элементов

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

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

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

30 первого элемента ИЛИ, прямой вход второго элемента ИЛИ соединен с сигнальным выходом блока регистров.

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

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

На фиг. 1 приведена структурная схема устройства; на фиг. 2 — структурная схема второго дешифратора.

Устройство содержит N каналов, в каждом канале содержатся триггер 1, блоки элементов И 2, 3, элемент И 4, элементы ИЛИ

5, 6, регистр 7. Устройство содержит общие для каналов блок 8 регистров, блок 9 элементов ИЛИ, блоки элементов И 10, 11, дешифратор 12, элемент ИЛИ 13, дешифратор

14 и коммутатор 15. Группа 16 входов кода типа задачи соединена с входами блоков 10 и 15, Группа 17 информационных входов кода задачи соединена с входами блоков 10 и 11, В каждом канале ответный вход 18 соединен с нулевым входом триггера 1 и с входом элемента ИЛИ 5. Выходы 19 блоков

6 и выходы 20 блоков 1 всех каналов соединены с входами блока 12, выходы 21 которого соединены с соответствующими каналами — с единичным входом триггера, с входом элемента 5, с входами блока 2, с входом второго элемента И. Выход 22 блока

12 соединен с входом элемента ИЛИ 13, Входы 23 регистров каналов являются установочными входами устройства, выходы 24. блоков 2 — информационными выходами устройства. Синхровход 25 устройства соединен с тактовым входом блока 8 с входами элементов И 4 всех каналов, Выходы 26 кода типа задачи и выходы 27 кода задачи от блока регистров 8 соединены соответственно с входами коммутатора 15 и блока элементов ИЛИ 8. В каждом канале содержится

1751760 также элемент И 28, выход которого является сигнальным выходом устройства.

Дешифратор 12 (фиг, 2) содержит группу элементов И 29, группу элементов HE 30, группу элементов И 31 и элемент ИЛИ-НЕ

32.

Устройство для распределения заданий процессорам работает следующим образом, В исходном состоянии триггеры 1 всех

10 каналов обнулены, блок 8 регистров не содержит никакой информации, на его информационных и сигнальных выходах — нулевые сигналы. Цепи установки устройства в исходное состояние не показаны. До начала 15 работы устройства в регистры 7 заносятся . для каждого типа задач "1", если данный тип задач решается процессором, и "0", если данный процессор не предназначен для выполнения данного типа задач, Синхровходы

r згистров 7 не выделены из общей совокупности информационных (установочных) входов 23, Сущность работы устройства заключа20

2S ется в следующем: все возможные задачи разделены на ряд типов; информационный код каждой задачи, выдаваемый источником (входы 17) сопровождается кодом ее типа (входы 16). При поступлении задачи в

30 устройство анализируется ее тип и наличие свободных процессоров, предназначенных для решения данного типа задач. Если такие (такой) процессоры есть, задача направляется устройством в один из них, Если в те35 кущий момент времени таких процессоров нет, задача временно записывается в блок регистров, работающий в соответствии с дисциплиной обслуживания, "первым пришел — первым обслужен", где ждет освобож40 дения соответствующего процессора

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

Так как в начальном состоянии на входах 16 и 17 устройства — нулевые сигналы; то в блоке 12 закрыты все элементы 29 (так как на первых входах элементов И 3 всех каналов — нули, на их выходах — тоже нулевые ная задача загружается в процессор и во 45 главе очереди становится (если она есть) . следующая задача, и т,д.

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

Поскольку блок 8 пуст в исходном состоянии, единичный сигнал с его сигнального выхода, поступая на коммутатор 15, коммусигналы, и нулевые сигналы на всех выходах

19), закрыты все элементы И 31, и на выходе элемента 32 (выходе 22) — единичный сигнал, таким образом, элементы блока 11 закрыты, а элементы блока 10 открыты.

На входы 17 устройства поступают коды задач для распределения по процессорам, на входы 16 — одновременно коды типов этих задач, Поступление кодов задач и кодов их типов сопровождается (синхронизируется) последовател ьностью синхроимпульсов на входе 25, сдвинутых относительно сигналов на входах 16 и 17, т.е. сигналы на входах 16 и 17 появляются до появления очередного синхроимпульса и снимаются до появления следующего синхроимпульса, Код типа задачи по входам 16 поступает через коммутатор 15 на дешифратор 14, преобразующий двоичный код в позиционный код, который с выхода дешифратора 14 поступает на входы блоков 3 каналов. Если данный тип задачи решается процессором, .то "единица" в позиционном коде типа данной задачи совпадает на соответствующемэлементе И 3 с "единицей" (по данному типу задачи), хранящейся в регистре 7, и с выхода соответствующего элемента И 3 сигнал поступает на вход элемента ИЛИ 6, на выходе которого формируется положительный потенциал, Если данный процессор свободен (а в начальный момент времени свободны все процессоры), тО на инверсном выходе триггера соответствующего канала "единица", срабатывает элемент И 29, чем запрещает срабатывание последующие каналов нулевым сигналом с соответствующего элемента НЕ 30, Таким образом, на выходе 21 дешифратора 12 формируется позиционный код номера канала, соответствующего процессору, в который может быть загружена данная задача, причем это канал с минимальным номером среди всех каналов, соответствующих процессорам. предназначенным для решения данной задачи. На выходе 22 блока 12 появляется нулевой сигнал, вызывающий появление нулевого сигнала на выходе элемента 13, который закрывает блок 10 и открывает блок 11, через который код задачи поступает на блок

9 и далее на все блоки 2 каналов.

Положительный сигнал о принятии задачи соответствующим процессором с выхода 21 блока 12 поступает в соответствующий канал. В канале этот сигнал формирует единичный потенциал на единичном входа триггера, через элемент ИЛИ 5 открывает элемент И 4, открывает группу элементов И

2 и выдает сигнал на сигнальном выходе 19, по которому соответствующий процессор

1751760 принимает задачу с выходов 24 устройства.

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

После этого в устройстве происходит переключение (в случае наличия свободных процессоров, предназначенных для решения данной задачи} дешифратора 12, подго- тавливающее срабатывание следующего процессора для данной задачи, однако его включение не происходит, так как задача (коды на входах 16 и 17) снимается до прихода следующего синхроимпульса.

Уточним, что сигнал о принятии задачи в процессор формируется в течение длительности синхроимпульса на выходе соответствующего элемента 23.

Очередные задачи поступают в устройство аналогично при наличии свободных процессоров, предназначенных для решения соответствующих типов задач.

Б том случае, когда поступающая задача (зэдача некоторого типа) не может быть непосредственно принята к обслуживанию (все процессоры для решения задач данного типа заняты), при поступлении кода типа задачи в устройство на всех выходах 21 блока 12 — нулевые сигналы, а на выходе 22— единичный сигнал, закрывающий блок 11 и открывающий блок 10. Поступающий синхроимпульс записывает код задачи (и код ее типа) в первый регист,;à регистров 8.

Блок регистров заявляемого устройства полностью идентичен блоку регистров прототипа.

Прй записи задачи в блок регистров (и во все интервалы времени, когда в блоке регистров хранится хотя бы одна задача) на сигнальном выходе блока регистров — единичный сигнал, который персключает коммутатор 15 в состояние, при котором на его выходы коммутируются входы 26- тип задачи, стоящей первой в очереди. На выходах

27 одновременно — код самой задачи, который поступает на элементы 2 через блок 9.

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

Как только один иэ процессоров освобождается, он выдает единичный сигнал на вход 10 данного канала устройства, чем вызывает появление единичного сигнала на нулевом входе триггера и открытие элемента И 4, С приходом синхроимпульса по его заднему фронту устанавливается в нулевое состояние триггер 1,фиксируя освобождение соответствующего процессора, Если освободившийся процессор предназначен для решения задачи (по типу ее), первой стоящей в очереди, то работа устройства по ее обслуживанию аналогична описанной с единственным отличием — задача берется не с входов 16 и 17, а с выходов

26 и 27 блока регистров. И, кроме того, в данном случае по заднему фронту синхроимпульса происходит сдвиг совокупности задач в блоке регистров таким образом, что на его выходах — код следующей по очереди

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

22, т. е. устройство остается в состоянии ожидания.

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

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

1. Устройство для распределения зада-, ний процессорам, содержащее блок регистров, два блока элементов И, блок элементов

ИЛИ, элемент ИЛИ и каналы, каждый из

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

К-входом триггера, выход первого блока элементов И канала является информационным выходом канала устройства, о т л и ч аю щ е е с я тем, что. с целью расширения области применения устройства за счет обеспечения решения задачи на- конкретном процессоре, в устройство введены коммутатор и два дешифратора, а в каждйй канал — регистр, второй блок элементов И, два элемента И и два элемента ИЛИ, причем информационный вход устройства соединен с первым информационным входом коммутатора, управляющий вход которого соединен с выходом признака заполнения блока регистров, информационный выход которого соединен с вторым информационным входом коммутатора, выход которого— с входом первого дешифратора, выход которого — с первыми входами вторых блоков элементов И всех каналов устройства, второй вход элемента ИЛИ соединен с входом записи блока регистров и сигнальным выходом второго дешифратора, К-й информационный выход которого (К=1„М; М вЂ” число каналов) соединен с J-входом триггера, первыми входами первого элемента И, первого элемента ИЛИ, вторым входом первого блока элементов И, выходы вторых элементов

ИЛИ всех каналов устройства соединены с первой групйой входов второго дешифратора, вторая группа входов которого соединена с инверсными выходами триггеров всех каналов устройства, в каждом канале вход установки канала устройства соединен с информационным входом регистра канала, выход которого соединен с вторым входом второго блока элементов И канала, выход которого соединен с входом второго эле5 мента ИЛИ канала, ответный вход канала устройства соединен с вторым входом первого элемента ИЛИ канала, выход которого соединен с первым-входоМ второго элемента И канала, выход которого соединен с син10 хровходом триггера канала, выход первого элемента И канала является сигнальным выходом канала устройства, тактовый вход устройства соединен с вторыми входами первый и вторых элементов И всех каналов

15 устройства.

2. Устройство по й, 1, о т л и ч а ю щ е ес я тем, что второй дешифратор содержит две группы элементов И, группу элементов -

20 НЕ и элемент ИЛИ-НЕ; выход которого является сигнальным выходом дешифратора, первая группа входов которого соединена с первыми входами элементов И первой группы, вторые входы которых соединены с вто25 рой группой входов дешифратора, выход

1-го элемента И первой группы (i=1, M — 1) соединен с входом I-ro элемента HE группы, выход которого соединен с входами с первого по 1-й i-ro элемента И второй группы, 30 выход первого элемента И группы является первым выходом дешифратора и первым входом элемента ИЛИ вЂ” НЕ, выходы элементов И второй группы соединены с входами элемента ИЛИ-НЕ с второго по М-й и явля35 ются выходами дешифратора с второго по

M-й, выход j-го элемента И первой группы (j=2,Ì) соединен с j-м входом i-ro элемента

И второй группы.

1751760

1751760

Составитель С.Кишенский

Техред M.Моргентал Корректор Н,Бучок

Редактор M.Öèòêèíà

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

Заказ 2692 Тираж Подписное

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

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