Устройство планирования вычислительного процесса в мультипроцессорной системе

 

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

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

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

РЕСПУБЛИК

„SU„„1434451 (51)4 G 06F 15 20

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4138914/24-24 (22) 14. 07.86 (46) 30.10.88.Áþë. 11- 40 (71) Минский радиотехнический институт (72) А.В.Чиж, В.П.Пискун, О.В.Герман и В.А,Вишняков (53) 681 ° 325 (088.8) (56) Авторское свидетельство СССР

В 877553, кл. G 06 F 15/20, 198 1.

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

II 940164, кл. G 06 F 15/20, 1982. (54) УСТРОЙСТВО ПЛАНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА В МУЛЬТИПРОЦЕССОРНОА СИСТЕМЕ (57) Устройство относится к вычислительной технике и предназначено для функционирования в составе мультипроцессорной ЭВМ для автоматического выбора очередной задачи нз множества задач со структурой, заданной ацикличным ориентированным графом, и для автоматического синтеза расписаний работ, Целью изобретения являет" ся расширение функциональных возможностей устройства эа счет переназначения выполнения задач через фиксированные кванты времени. Устройство содержит матрицу триггеров, две группы элементов ИЛИ-НЕ, пять групп элементов И, три группы счетчиков, две груп" пы триггеров, регистр выбранных вершин, регистр приоритета, шифратор, блок управления, состоящий из генератора тактовых импульсов, элемента И, схемы начального пуска, элемента ИЛИ Я и триггера, регистр текущих обрабатываемых задач, элемент ИЛИ, счетчик . тактовых импульсов, регистр кванта, генератор тактовых импульсов, входывыходы. 1 ил.

1434451

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

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

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

Устройство содержит матрицу 1 триггеров 2, группу элементов ИЛИ-НЕ 3, по числу строк матрицы, группу элементов И 4 по числу столбцов матрицы, группу счетчиков 5, группу триг геров 6, группу элементов И 7, группу счетчиков 8, группу триггерон 9, группу элементов И 10, регистр 11 ныб 25 раиных вершин, реализованно на триггерах 111, регистр 12 приоритета, группу элементов И 13, шифратор 14, блок управления, состоящий из генератора 15 тактовых импульсов, элемента

И 16, схемы l7 начального пуска, элемента ИЛИ 18, триггера 19, вход 20 пуска устройства, вход 21 записи в регистр 11, информационный выход 22 устройства, блок 23 управления в сос" тане указанных схем 15 — 19, группу элементов И 24, группу счетчиков 25, группу элементов ИЛИ-НЕ 26, регистр

27 текущих обрабатываемых задач, элемент ИПИ 28, счетчик 29 тактовых импульсов, регистр 30 кванта, генератор 31 тактовых импульсов, вход 32 признака обрабатываемой задачи устройства, вход 33 записи в счетчик 29, пусковой вход 34 генератора 31„ выходы 35, 36 запроса на прерывание устройства. Для записи в регистры 12, 27 используются соответственно вход 21 и один из входов 32. Шифратор !4 представляет комбинационную схему, обеспечивающую возбуждение одного или нескольких своих выходов, cGoTветствующих максимальному коду, хранящемуся н одноименных счетчиках 8.

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

Первоначально в матрицу 1 заносится информация о топологии моделируемого графа. При этом триггеры 2;1 (1, l,п), которые являются формирователями дуг, устанавливаются в единччные состояния, если есть информационная связь из i-й вершины н j-ю.

Соответствующий триггер 2; определяется пересечением i-й строки и

j-ro столбца. Другие триггеры 2; а также триггеры 6,9,19, счетчикй 8, регистры 11, 12, 27 находятся н нулевом состоянии (цепи установки н начальные состояния и записи н регистры и триггеры не показаны). В счетчики 5 и 25 соответствующих вершин графа заносятся числа импульсов, дополняющие "веса" вершин до полной емкости счетчиков, н регистр 30 заносится код, дополняющий квант времени до полной емкости счетчика 29.После занесения исходной информации на выходах элементов ИЛИ-НЕ 3, объединяющих выходы триггеров 2 и строках, соответствующих конечным вершинам графа будут высокие потенциалы, поскольку принято, что граф ацикличен и для конечных вершин соответствующие триггеры 2 обнулены. Первоначальна в устройстве происходит определение величин максимальных путей,связывающих данные вершины с конечными (формируются значения уровней нер" шин). При этом пусконой сигнал на входе 20 схемы 17 начального пуска запускает генератор 15, с выхода которого импульсы поступают на входы элементов И 4 и 7, а далее на нсе счетчики 8, так как н исходном состоянии все триггеры 6 находятся в нулевом состоянии, управляющие входы элементов И 7 подключены к инверсным выходам триггеров 6." Кроме того, счетные импульсы поступают через эле-, менты И 4 на те счетчики 5, для которых триггеры 2 одноименной строки матрицы 1 находятся в нулевом состоянии.

Поэтому на.выходе соответствующих элементов ИЛИ-НЕ 3 появляется высокий потенциал, благодаря чему на управляемом входе одноименного элемента И 4 будет высокий потенциал, Отсчитав число импульсан, пропорцHQHальное "весу" моделируемой вершины, счетчик 5 переполняется, сигнал переполнения устанавливает в единичное состояние соответствующий триггер

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

С учетом состояния регистра 27 устанавливается нулевой уровень на выхо- . де тех элементов ИЛИ-НЕ 26 дополнительной группы, которые соответствуют обрабатываемым задачам, тем самым эти задачи временно исключаются" из поля зрения ЗВМ-диспетчера. После того как готовые задачи будут назна) чены на процессоры, ЭВМ-диспетчер загружает в счетчик 29 дополнение ве" личины кванта времени до полной емкости счетчика из регистра 30 кванта управляющим сигналом, подаваемым на вход 33 устройства, и запускает генератор 31 тактовых импульсов путем подачи импульса на вход 34 устройства.

Сигналы с генератора 31 подаются на вход счетчика 29, а также через элементы И 24 на входы тех счетчиков 25 и вычитающие входы тех счетчиков 8, для которых соответствующие разряды регистра 27 установлены в "1". По окончании выделенного кванта времени (счетчик 29 переполняется) или по завершении выполнения одной или нескольких задач (переполняется соот" ветствующий счетчик 25) соответствующий сигнал переполнения через элемент

ИЛИ 28 сбрасывает регистр 27 текущих обрабатываемых задач и генератор 31, а также поступает на выход 35 устройства и далее на вход запроса на прерывание ЗВМ-диспетчера, сигнализируя о необходимости выбора следующих задач. Далее производится новый цикл .назначения. Как только какая-либо из

1 задач будет выполнена полностью, происходит переполнение соответствующего счетчика 25, при этом сигнал переполнения устанавливает в единицу соответствующий разряд регистра выбранных вершин 11. В результате на выходе элемента И 13 будет высокий потенциал, по которому триггер 9 пере ходит в единичное состояние; подача кода уровня данной задачи со счетчика 8 на входы шифратора 14 прекращается и на регистре 12 записывается другой код, по которому ЭБМ-диспетчер выбирает нереализованные задачи.

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

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

5 вершины до конечной вершины интерпретирующего графа.

Рассмотренные действия повторяются до тех пор, пока на выходах всех триггеров 6 не будут присутствовать низкие потенциалы. На выходе элемента ИЛИ 18 будет низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 15 через элемент И 16 на информационные входы элементов И 4,7, С выхода триггера 19 высокий потенциал подается на вход оповещения, ЭВМ и управляющий вход шифратора 14, который обеспечивает появление высокого 20 потенциала на одном или нескольких из и своих выходов, которые соответствуют максимальному коду, хранящемуся в одноименном счетчике 8 при условии, что на первый управляемый вход 25 элементов И 10 подается высокий потенциал с выходов элементов ИЛИ-НЕ 26.

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

ЭВМ-диспетчер ведет информацию о текущих выполняемых задачах, что позволяет распознавать подобные ситуации).Кроме того, при наличии несколь- 45 ких единиц в регистре 12 требуется последовательная выборка задач на обработку (например, первой выполняется задача с минимальным номером разряда в регистре 12), причем после того,50 как выбор текущей задачи сделан, ЭВМдиспетчер по входам 32 устройства ус-. танавливает в регистре 27 текущих обрабатываемых задач код, наличие "1" в в i-м разряде которого определяет, что i-я задача обрабатывается. При этом установка такого кода не должна разрушать ранее установленных единиц, соответствующих выбранным для

Устройство планирования вычислительного процесса в мультипроцессорной системе, содержащее матрицу (пхп) 5

1 4344 триггеров, блок управления, группу элементов ИЛИ-НЕ, две группы счетчиков, две группы триггеров, регистр . выбранных вершин, регистр приоритета, четыре группы элементов И, шифратор

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

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

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

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

1434451

Составитель Е.Устинов

Редактор М.Циткина Техред М.Дидык Корректор М.Максимишинец

Тираж 704 Подписное

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

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

Заказ 5557/52

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