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

Од Од

Од

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

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

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

Устройство содержит регистр готовности, элемент ИЛИ-И 2, блоки 3 и 4 памяти, счетчики 5 и 6, генераторы 7 и 8 импульсов, триггеры 9 и 10, дешифраторы 11-14, мультиплексоры 15 и 16, элемент И 17, регистр 18 сдвига, регистр 19 заданий и регистр 20 процессоров, а также группу информационных входов 21, вход 22 пуска, вЫ ходы 23 номера заданий, группы входов 24 и 25 освобождения и занятости процессоров, группы входов 26 признака выполнения заданий, выход 27 готовности. При этом регистр I готовности выполнен в виде регистрового блока с общими входами данных и раз- делышми входами записи.

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

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

По построенному графу можно организовать в вычислительной системе последовательный запуск заданий на счет. Задачу определения последовательности запускаемых задс1ний и реша ет предпагаемое устройство. Каждое задание может быть запущено на счет при условии, что все предшествующие ему задания, т.е. задания, выходные данные которых используются данным заданием в качестве исходных,выполнены. Другим условием, разрешающим, запуск задания на счет, помимо наличия всех исходных данных, является

10

fS

20

25

30

35

40

45

50

55

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

Устройство работает циклически. В каждом цикле в случае вьшолнения условия запуска хотя бы для одного г-з заданий на вькодной магистрали 23 формируется номер задания, отправляемого на счет, в сопровождении сигнала на выходе 27 готовности.

При завершении вьшолнения какого- либо задания одним из процессоров в регистр 1 готовности заносится новое слово состояния заданий. Каждому заданию в слове состояния соответствует один или несколько разрядов. Единичное значение разряда означает либо готовность данных с данного задания, либо передачу управления в том или ином направлении. Информация в регистр I заносится с разрядов данных магистрали 21 подачей стробирующих импульсов на входы записи регистра 1, последний из которьк подается на вход записи, связанный с S-входом триггера 9. В результате переключается триггер 9, вьщавая сигнал запуска на генератор 7. Генератор 7 начинает формировать последовательность импульсов, поступающую на синзфовхо- ды счетчика 5 и регистра 18 сдвига. Счетчик 5 последовательно опрашивает блок 3 памя,ти. В нем хранится информационная модель графа. Каждая ячейка блока 3 памяти (одно слово) соответствует, одному заданию. В ячейки памяти записаны маски (по одной маске для каждого задания). Разрядность блока 3 равна разрядности регистра 1 готовности. Каждому разряду регистра I соответствует определенный разряд маски. Каждый разряд регистра 1 соответствует наличию выходных данных или передаче управления на выходе определенного задания. Если для запуска, данного задания требуются данные или управление с некоторого другого задания, то в соответствующем разряде маски устанавливается нулевое значение, если не тре- буются то единичное значение. По мере опроса счетчиком 5 блока 3 памяти ;коды масок поступают на входы элемента ИЛН-И 2. Если при этом все значения разрядов регистра 1 , соответствующие нулевым значениям маски, имеют единичные значения, то на выходе элемента 2 формируется уровень логической 1, что соответствует выполнению условия запуска для соответствующего задания. Если хотя бы один

му коду номера задания на первых ад- рес}1ьгх входах сопоставляется определенный разряд на выходе регистра процессоров 20, при наличии логической 1 на котором для данного номера задания на выходе блока 4 формируется логическая 1. Когда триггер 10 находится в единргчном состоянии, ге

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

разряд имеет нулевое значение, на вы- Q нератор 8 формирует импульсную после15

ходе элемента 2 формируется нулевой уровень. Последовательно формируемые элементом 2 значения вдвигаются в .регистр 18 сдвига импульсами, поступающими с генератора 7. По окончании цикла опроса блока 3 на выходе переноса счетчика 5 формируется сигнал, сбрасывающий триггер 9 и, таким образом, прерывающий синхросерию на выходе генератора 7. После опроса в ре- 2о гистре 1В формируется слово готовности заданий к запуску. Число разрядов регистра 18 равно числу слов в блоке 3 и числу заданий в задаче. Каждому заданию соответствует один разряд, единичное значение которого означает выполнение условия запуска для этого задания.

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

довательность на счетном входе счетчика 6.

Счетчик 6 формирует на адресных входах мультиплексоров 15 и 16 и блока 4 последовательность адресов, в соответствии с которой они последовательно опрашивают соответствующие разряды регистров 18-20. При наличии логических 1 на выходах всех трех, блоков 15, 16, 4 на выходе элемента И 17 формируется логическая 1, по которой сбрасывается триггер 10, генератор 8 обрывает формируемую синхросерию, на выходной магистрали 23

25 фиксируется номер задания, подпежаще- го загрузке. Указанный код номера сопровождается сигналом готовности на выходе 27. Одновременно сигнал с выхода элемента И 17 поступает на стро30 бирующий вход дешифратора 12. Сигнал с вьпсода дешифратора 12 сбрасьшает соответствующий разряд регистра 19, что предотвращает повторный запуск на счет одного и того же задания. При этом сигналы на выходе мультип- лексора 16 и, следовательно, на выходе элемента 17 принимают нулевые значения. После считывания вычислительной системой кода с магистрали 23 подается ответный сигнал на вход 22, по которому триггер 10 устанавливается в 1, снимая сигнал с выхода. 27, счетчик 6 сбрасывается.

При снятии сигнала с входа 22 цикл

35

40

свободных процессоров заданных типов g опроса возобновляется с нулевого адопределяет содержимое регистра 20 процессоров. Наличию свободного процессора данного типа соответствует единичный уровень в определенном раз- ,ряде. Разрядность регистра 20 равна числу типов процессоров в обслуживаемой вычислительной системе. Информация с регистров 18 и 19 поступает на входы мультиплексоров 15 и 16 соответственно. Информация с регистра 20 поступает на входы блока 4. В блок 4 памяти занесена таблица, устанавливающая дпя каждого задания соответствующий тип процессора, Каждо-

50

55

реса. Содержимое регистра 19 заданий может быть изменено извне подачей кода номера задания и стробирующего сигнала на магистраль 26, Код номера задания дешифрируется дешифратором 1 и обеспечивает установку в состояние логической 1 соответствующего разряда регистра 19, разрешая повторный просчет соответствующего задания. По мере занятия и высвобождения в процессе вычислений тех или иных типов процессоров ДОЛЖНО изменяться содержимое регистра процессоров 20, Дпя установки в состояние логической 1

5

о

довательность на счетном входе счетчика 6.

Счетчик 6 формирует на адресных входах мультиплексоров 15 и 16 и блока 4 последовательность адресов, в соответствии с которой они последовательно опрашивают соответствующие разряды регистров 18-20. При наличии логических 1 на выходах всех трех, блоков 15, 16, 4 на выходе элемента И 17 формируется логическая 1, по которой сбрасывается триггер 10, генератор 8 обрывает формируемую синхросерию, на выходной магистрали 23

5 фиксируется номер задания, подпежаще- го загрузке. Указанный код номера сопровождается сигналом готовности на выходе 27. Одновременно сигнал с выхода элемента И 17 поступает на стро0 бирующий вход дешифратора 12. Сигнал с вьпсода дешифратора 12 сбрасьшает соответствующий разряд регистра 19, что предотвращает повторный запуск на счет одного и того же задания. При этом сигналы на выходе мультип- лексора 16 и, следовательно, на выходе элемента 17 принимают нулевые значения. После считывания вычислительной системой кода с магистрали 23 подается ответный сигнал на вход 22, по которому триггер 10 устанавливается в 1, снимая сигнал с выхода. 27, счетчик 6 сбрасывается.

При снятии сигнала с входа 22 цикл

5

0

g опроса возобновляется с нулевого ад50

55

реса. Содержимое регистра 19 заданий может быть изменено извне подачей кода номера задания и стробирующего сигнала на магистраль 26, Код номера задания дешифрируется дешифратором 11 и обеспечивает установку в состояние логической 1 соответствующего разряда регистра 19, разрешая повторный просчет соответствующего задания. По мере занятия и высвобождения в процессе вычислений тех или иных типов процессоров ДОЛЖНО изменяться содержимое регистра процессоров 20, Дпя установки в состояние логической 1

того или иного разряда регистра 20 на магистраль 24 подается код соответствующего типа процессора и стро- бирующий сигнал. Указанный код дешифрируется дешифратором 13. Аналогично для установки в ноль используются магистраль 25 и дешифратор 14. При использовании предлагаемого устройства следует также иметь в виду следующее. Если в какой-то момент условия запуска выполняются для нескольких заданий, то на счет запускается задание, имеющее меньший код, поскольку опрос осуществляется счетчиком 6 в порядке возрастания с нулевого кода. Таким образом, заданиям с наивысшими приоритетами следует присваивать минимальные значения кодов.

Следует иметь в виду, что во время работы генератора 7 содержимое регистра 18 сдвига изменяется и в это время нельзя вестд опрос мультиплексора 15. Поэтому на это время сигналами с выхода триггера 9 счетчик 6 удерживается в нулевом состоянии, а элемент 17 блокируется нулевым уровнем на первом входе. Поскольку переключение в единицу триггера 9 приводит к сбросу счетчика 6, триггер 9 допустимо переключать только при нулевом уровне на выходе 27.

1

, Структура графа заданий определя- iется содержимым блока 3. Если структура алгоритма неизменна, то блок 3 памяти выполняется в виде ПЗУ. Если устройство рассчитано на обработку различных задач,.то блок 3 выполняется в виде ОЗУ и дополняется цепями загрузки информации. При этом в блоке 3 памяти могут загружаться задачи, число заданий в которых не превышает числа ячеек в блоке 3. Дпя исключения влияния неиспользуемых ячеек резервируется один из разрядов регистра 1 , которому присваивается нулевое значение, при этом одноименным разрядам масок в неиспользуемых ячейках также присваиваются нулевые значения. Аналогично и второй блок 4 памяти может выполняться в виде ОЗУ или ПЗУ. Если обслуживаемая предлагаемым устройством вычислительная система содержит процессоры только одного типа, то блок 4 вместе с регистром 20 и дешифраторами 13 и 14 могут быть исключены из состава устройства.

р м у л а

и

6

3 о

р е т е к и я

очереди, содержащее блок памяти,

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

входом сброса первого триггера и

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

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

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

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

расширения области применения за цессоров устройства,

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