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

сл

С

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

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

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

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

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

0

sJ О О

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

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

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

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

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

типы задач. Это ограничивает область его применения.

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

На фиг. 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. В каждом канале содержится

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

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

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

В исходном состоянии триггеры 1 всех каналов обнулены, блок 8 регистров не содержит никакой информации, на его информационных и сигнальных выходах - нулевые сигналы. Цепи установки устройства в исходное состояние не показаны. До начала работы устройства в регистры 7 заносятся для каждого типа задач 1, если данный тип задач решается процессором, и О, если данный процессор не предназначен для выполнения данного типа задач. Синхровходы Г згистров 7 не выделены из общей совокупности информационных (установочных) входов 23.

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

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

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

Поскольку блок 8 пуст в исходном состоянии, единичный сигнал с его сигнального выхода, поступая на коммутатор 15, коммутирует на его выходы входы 16 устройства. Так как в начальном состоянии на входах 16 и 17 устройства - нулевые сигналы, то в блоке 12 закрыты все элементы 29 (так как на первых входах элементов И 3 всех каналов - нули, на их выходах - тоже нулевые

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

На входы 17 устройства поступают коды задач для распределения по процессорам, на входы 16 - одновременно коды типов этих задач. Поступление кодов ьадач и ко0 дов их типов сопровождается (синхронизируется)последовательностью синхроимпульсов на входе 25, сдвинутых относительно сигналов на входах 16 и 17, т.е. сигналы на входах 16 и 17 появляются

5 до появления очередного синхроимпульса и снимаются до появления следующего синхроимпульса.

Код типа задачи по входам 16 поступает через коммутатор 15 на дешифратор 14,

0 преобразующий двоичный код в позиционный код, который с выхода дешифратора 14 поступает на входы блоков 3 каналов. Если данный тип задачи решается процессором, то единица в позиционном коде типа дан5 ной задачи совпадает на соответствующем элементе И 3 с единицей (по данному типу задачи), хранящейся в регистре 7, и с выхода соответствующего элемента И 3 сигнал поступает на вход элемента ИЛИ 6, на выходе

0 которого формируется положительный потенциал Если данный процессор свободен (а в начальный момент времени свободны все процессоры), то на инверсном выходе триггера соответствующего канала едини5 ца, срабатывает элемент И 29, чем запрещает срабатывание последующие каналов нулевым сигналом с соответствующего элемента НЕ 30, Таким образом, на выходе 21 дешифратора 12 формируется позиционный

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

5 предназначенным для решения данной задачи. На выходе 22 блока 12 появляется нулевой сигнал, вызывающий появление нулевого сигнала на выходе элемента 13, который закрывает блок 10 и открывает блок 11,

0 через который код задачи поступает на блок 9 и далее на все блоки 2 каналов.

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

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

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

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

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

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

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

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

При записи задачи в блок регистров (и во все интервалы времени, когда в блоке регистров хранится хотя бы одна задача) на сигнальном выходе блока регистров - единичный сигнал, который переключает коммутатор 15 в состояние, при котором на его выходы коммутируются входы 26 - тип задачи, стоящей первой в очереди На выходах 27 одновременно - код самой задачи, который поступает на элементы 2 через блок 9. Эти коды находятся на данных шинах до тех пор, пока не освободится какой-либо соответствующий процессор и не примет данную задачу. Таким образом реализуется (аналогично прототипу) соответствие очередности решения по мере их поступления.

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

нулевом входе триггера и открытие элемента И 4. С приходом синхроимпульса по его заднему фронту устанавливается в нулевое состояние триггер 1 .фиксируя освобождение соответствующего процессора

0 Если освободившийся процессор предназначен для решения задачи (по типу ее), первой стоящей в очереди, то работа устройства по ее обслуживанию аналогична описанной с единственным отличием - за5 дача берется нес входов 16и 17, а с выходов 26 и 27 блока регистров. И, кроме того, в данном случае по заднему фронту синхроимпульса происходит сдвиг совокупности задач в блоке регистров таким образом, что

0 на его выходах - код следующей по очереди задачи.

Если же освободившийся процессор не предназначен для решения задачи, первой стоящей в очереди, то его освобождение не

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

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

5 загрузка следующей задачи (например, сто я щей первой в очереди) осуществляется в

этот процессор (если он предназначен для

решения задач данного типа) следующим

тактовым импульсом.

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

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

5 которых содержит первый блок элементов И и триггер, причем информационный вход устройства соединен с первыми входами первого f второго блоков элементов И, тактовый вход устройства - с синхровходом

0 блока регистров, информационный выход которого соединен с первым входом блока элементов ИЛИ, второй вход и выход которого соединены соответственно с выходом первого блока элементов И и первыми вхо5 дами первых блоков элементов И всех каналов устройства, выход второго блока элементов 14 соединен с информационным входом блока регистров, выход признака заполненности которого соединен с первым входом элемента ИЛИ, выход которого соединен с вторыми входами первого и второго блоков элементов И, а в каждом канале выход первого блока элементов И является информационным выходом канала устройства, ответный вход которого соединен с К-входом триггера, выход первого блока элементов И канала является информационным выходом канала устройства, отличающееся тем, что, с целью расширения области применения устройства за счет обеспечения решения задачи на конкретном процессоре, в устройство введены коммутатор и два дешифратора, а в каждый канал - регистр, второй блок элементов И, два элемента И и два элемента ИЛИ, причем информационный вход устройства соединен с первым информационным входом коммутатора, управляющий вход которого соединен с выходом признака заполнения блока регистров, информационный выход которого соединен с вторым информационным входом коммутатора, выход которого - С входом первого дешифратора, выход которого - с первыми входами вторых блоков элементов И всех каналов устройства, второй вход элемента ИЛИ соединен с входом записи блока регистров и сигнальным выходом второго дешифратора, К-й информационный выход которого ( М - число каналов) соединен с J-входом триггера, первыми входами первого элемента И, первого элемента ИЛИ, вторым входом первого блока элементов И, выходы вторых элементов ИЛИ всех каналов устройства соединены с первой группой входов второго дешифратора, вторая группа входов которого соединена с инверсными выходами триггеров всех каналов устройства, в каждом канале вход установки канала устройства соединен с информационным входом регистра канала, выход которого соединен с вторым входом второго блока элементов И канала, выход которого соединен с входом второго элемента ИЛИ канала, ответный вход канала устройства соединен с вторым входом первого элемента ИЛИ канала, выход которого соединен с первым входом второго элемента И канала, выход которого соединен с синхровходом триггера канала, выход первого элемента И канала является сигнальным выходом канала устройства, тактовый вход устройства соединен с вторыми входами первый и вторых элементов И всех каналов

устройства.

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

выход первого элемента И группы является первым выходом дешифратора и первым входом элемента ИЛИ-НЕ, выходы элементов И второй группы соединены с входами элемента ИЛИ-НЕ с второго по М-й и являются выходами дешифратора с второго по М-й,выход j-ro элемента И первой группы ,М) соединен с j-м входом 1-го элемента И второй группы.

Фи.1

Фиг.1

20. N