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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИН

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

Н ASTOPCHQ5AV СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4149088/24-24 (22) 17.11.86 (46) 23.12.88. Бюл. Р 47 (72) В.А.Аврутин и В.Е.Подтуркин (53) 681.3 (088.8) (56) Авторское свидетельство СССР

Р 1001101, кл. О 06 F 15/20, 1981.

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

11 940164, кл. 0 06 Р 15/20, 1980. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОЧЕРЕДИ (57) Изобретение. относится к .цифровой вычислительной технике и может быть использовано в мультипроцессор" ных вычислительных системах. Целью

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

1 s .n. ф-лы. 1

1446626

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

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

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

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

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

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

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

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

При завершении выполнения какоголибо задания одним из процессоров в регистр 1 готовности заносится новое слово состояния заданий. Каждому заданию в слове состояния соответствует один или несколько разрядов. Единичное значение разряда означает либо готовность данных с данного задания, либо передачу управления s том или ином направлении. Информация в регистр I заносится с разрядов данных магистрали 21 подачей стробирующих импульсов на входы записи регистра 1, последний иэ которых подается на вход записи, связанный с S-входом триггера 9. В результате переключается триггер 9, выдавая сигнал запуска на генератор 7. Генератор 7 начинает формировать последовательность импульсов, поступающую на синхровходы счетчика 5 и регистра !8 сдвига.

Счетчик 5 последовательно опрашивает блок 3 памяти. В нем хранится информационная модель графа. Каждая ячейка блока 3 памяти (одно слово) соответствует.одному заданию. В ячейки памяти записаны маски (по одной маске для каждого задания). Разрядность блока 3 равна разрядности регистра 1 готовности. Каждому разряду регистра 1 соответствует определенный разряд маски. Каждый разряд регистра 1 соответствует напичию выходных данных или передаче управления на выходе определенного задания. Если для запуска данного задания требуются данные или управление с некоторого другого задания, то в соответствующем разряде маски устанавливается нулевое значение, если не требуются то единичное значение, По мере опроса счетчиком 5 блока 3 памяти коды масок поступают на входы элемен14466 та ИЛИ-И 2. Если при этом все значения разрядов регистра 1, соответствующие нулевым значениям маски, имеют единичные значения, то на выходе элемента 2 формируется уровень логи5 ческой "1", что соответствует выполнению условия запуска для соответствующего задания, Если хотя бы один разряд имеет нулевое значение, на вы- 10 ходе элемента 2 формируется нулевой уровень. Последовательно формируемые элементом 2 значения "вдвигаются" в регистр 18 сдвига импульсами, поступающими с генератора 7. По окончании цикла опроса блока 3 на выходе переноса счетчика 5 формируется сигнал, сбрасывающий триггер 9 и, таким образом, прерывающий синхросерию на выходе генератора 7. После опроса в ре- ZO гистре 18 формируется слово готовности заданий к запуску. Число разрядов регистра 18 равно числу слов в блоке 3 и числу заданий в задаче. Каждому заданию соответствует один раз- 25 ряд, единичное значение которого означает выполнение условия запуска для этого задания. . После того как сформировано слово готовности заданий, необходимо при- З0 нять решение о запуске того или иного задания на счет. При, этом для каж. дого задания необходимо выполнение следующих двух условий. Задание не должно быть уже выполненным и, кроме того, для выполнения задания в вычис" лительной системе должен иметься свободный процессор необходимого типа. — Слово состояния заданий хранится в регистре 19 заданий. Не запущенным на счет заданиям в регистре 19 соответствуют единичные значения, а число разрядов регистра 19 соответствует числу заданий. Наличие в системе свободных процессоров заданных типов 45 определяет содержимое регистра 20 процессоров. Наличию свободного процессора данного типа соответствует единичный уровень в определенном разряде. Разрядность регистра 20 равна числу типов процессоров в обслуживаемой вычислительной системе. Информация с регистров 18 и 19 поступает на входы мультиплексоров 15 и 16 соответственно. Информация с регистра

20 поступает на входы блока 4. В блок 4 памяти занесена таблица, устанавливающая для каждого задания соответствующий тип процессора. Каждо26

«у коду номера задания на первых адресных входах сопоставляется определенный разряд на выходе регистра процессоров 20, при наличии логической

"1" на котором для данного номера задания на выходе блока 4 формируется логическая "!". Когда триггер 10 находится в единичном состоянии, генератор 8 формирует импульсную последовательность на счетном входе счетчика 6.

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

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

При этом сигналы на выходе мультип- . лексора 16 и, следовательно, на выходе элемента 17 принимают нулевые значения. После считывания вычислительной системой кода с магистрали 23 подается ответный сигнал на вход 22, по которому триггер 10 устанавливается в "1", снимая сигнал с выхода 27, счетчик 6 сбрасывается.

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

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

При использовании предлагаемого устройства следует также иметь в виду следующее. Если в какой-то момент условия заПуска выполняются для нескольких заданий, то на счет запускается задание, имеющее меньший код, поскольку опрос осуществляется счет15 чиком 6 в порядке возрастания с нулевого кода. Таким образом, заданиям с наивысшими приоритетами следует присваивать минимальные значения кодов.

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

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

35 ао влияния неиспользуемых ячеек резервируется один из разрядов регистра 1, которому присваивается нулевое значение, при этом одноименным разрядам масок в неиспользуемых ячейках также присваиваются нулевые значения. Лналогично и второй блок 4 памяти может

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

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

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

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

Редактор А.Ворович Техред Л.Сердюкова Корректор О. Кравцова

Заказ бj50/54 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

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

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

И, первая и вторая группы адресных входов которого соединены соответственно с группой выходов первого счетчика и группой входов занятости процессоров устройства.