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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области вычислительной техники и предназна чено для функционирования в составе мультипроцессорной ЭВМ для автоматического выбора очередной программы из множества программ со. структурой, заданной ацикличным ориентированньпч графом, а также для автоматического синтеза расписаний работ, и являетс.я усовершенствованием устройства по а.с. № 940164. Цель изобретения - оптимизация распределения .заданий с учетом совместимости задач, входящих в данное задание. Для достижения данной цели в устройство введены регистр текущей задачи, группа элементов И и матрица формирователей совместимости задач, причем каждая ячейка матрицы формирователей совместимости задач содержит элемент 2И-ИПИ, каждая ячейка, лежащая на диагонали и под диагональю матрицы формирователей совместимости, содержит триггер , Сущность изобретения заключается в обобщении реализуемь:х моделей диспетчеризации связанных задач. Помимо отношения предшествования задач, заданного графом, вводится отношение совместимости, определяющее возмож ность или невозможность одновременного использования задачами ресурсов системы. 1 ил. (П

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

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

РЕСПУБЛИК (51)4 G 06 F 15 20

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

H А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 940164 (21) 4016478/24-24 (22) 28.01.86 (46) 15.02.88. Бюл. № 6 (71) Минский радиотехнический институт (72) О.В. Герман и А.М..Суходольский (53) .681.325(088.8) (56) Авторское свидетельство СССР

¹ 940164, кл. G 06 F 15/20, 1980 (прототип). (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

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

„„SU„„1374238 А 2 усовершенствованием устройства по а.с. № 940164. Цель изобретения— оптимизация распределения заданий с учетом совместимости задач, входящих в данное задание. Для достижения данной цели в устройство введены регистр текущей задачи, группа элементов И и матрица формирователей совместимости задач, причем каждая ячейка матрицы формирователей совместимости задач содержит элемент 2И-ИЛИ, каждая ячейка, лежащая на диагонали и под диагональю матрицы формирователей совместимости, содержит триггер. Сущность изобретения заключается в обобщении реализуемых моделей диспетчеризации связанных задач. Помимо отношения предшествования задач, заданного графом, вводится отношение совместимости, определяющее возмож ность или невозможность одновременно-. го использования задачами ресурсов системы. 1 ил. устанавливаются в единичное состояние, если есть информационная связь из одной вершины в другую. Соответствующий триггер 2 определяется пересечением строки и столбца. Аналогично устанавливаются в единичное сос- . тояние триггеры 26, если соответствующие задачи совместимы.

Триггеры 2 и 26, а также триггеры 6, 9 и 19 и счетчики 8 находятся в нулевом состоянии (цепи установки начальных состояний не указаны). В счетчики 5 соответствующих вершин графа заносятся числа импульсов, дополняющие веса до полной емкости счетчиков.

После занесения исходной информации на входах элементов ИЛИ-НЕ 3, объединяющих выходы триггеров 2 в строках, соответствующих конечным вершинам графа, будут "1".

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

15, с выхода которого импульсы поступают на входы элементов И 4 и 7, а далее на все счетчики 8, так как в исходном состоянии все триггеры 6 находятся в нулевом состоянии, а соответствующие входы элементов И 7 под35 ключены к нулевым выходам триггеров 6.

Кроме того, счетные импульсы поступают через элементы И 4 на те счетчики 5, для которых триггеры 2 одно4 именной строки матрицы 1 находятся в нулевом состоянии. Поэтому на выходе соответствующих элементов ИЛИ-HE 3 появляется высокий потенциал, благодаря чему на соответствующем входе одноименного элемента И 4 будет "1".

Отсчитав число импульсов, пропорциональное весу моделируемой вершины, счетчик 5 переполняется, сигнал переполнения устанавливает в единичное состояние соответствующий триггер 8, а все триггеры 2 в данном столбце матричной модели сети 1 — в нулевое состояние. Переброс триггера 6 в единичное состояние обеспечивает прекращение подачи счетных импульсов через элемент И 7 на вход счетчика 8, в котором фиксируется код максимального пути из данной вершины до конечной вершины графа.

1 1374238

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

Целью изобретения является оптимизация распределения заданий с учетом совместимости задач, входящих в данное задание. 15

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

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

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

Устройство содержит матричную мо- 30 дель 1 сети в составе триггеров 2, .группу элементов ИЛИ-НЕ 3, группу элементов И 4, группу счетчиков 5, группу триггеров 6, группу элементов

И 7, группу счетчиков 8, группу триг геров 9, группу элементов И 10, регистр 11 выбранных вершин, регистр

12 приоритета, группу элементов И 13 шифратор 14, генератор 15 тактовых импульсов, элемент И 16, схему 17 начального пуска, элемент И 18, триг

rep 19, пусковой вход 20 устройства, информационные входы 21 устройства, выход 22 устройства. Генератор 15, элементы И 16 и 18, схема 17 начального пуска и триггер 19 образуют блок 23 управления. Кроме того, устройство содержит регистр 24 текущей задачи, матрицу 25 формирователей совместимости задач, состояющую из триггеров 26, элементов И-ИЛИ 27, группу элементов И 28, входы 29 устройства, ячейки 30 матрицы 25. Устройство работает следующим .образом.

Первоначально в модель 1 заносит55 ся информация о топологии моделируемого графа. При этом триггеры 2, которые являются формирователями дуг, 1374238

Рассмотренные действия продолжаются до тех пор, пока на выходах .всех триггеров 6 не будут присутствовать низкие потенциалы. На выходе элемента 18 будет низкий потенциал, 5 в результате чего прекращается подача счетных импульсов с выхода генератора 15 через элемент И 16 на входы элементов И 4 и 7.

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

40 ведет информацию о текущих выполняе-. мых задачах, что позволяет распознавать подобные ситуации. Кроме того, при наличии нескольких единиц в регистре 12 требуется последователь45 ная выборка задач на обработку, например, первой выбирается задача с минимальным номером разряда в регистре 12, причем после того,как выбор текущей задачи сделан, ЭВМ-диспетчер по вторым входам усройства устанавливает в регистре 24 текущих обрабатываемых задач код, наличие единицы в соответствующем разряде которого определяет, что задача обрабатывается.

С учетом состояния регистра 24 устанавливается нулевой уровень на выходе тех элементов И 28 пятой группы, которые определяют несовместные по отношению к обрабатываемым задачи, тем самым эти задачи временно исключаются из поля зрения ЭВМ-диспетчера, Затем ЭВМ-диспетчер записывает в соответствующий номеру выбранной saдачи разряд регистра 11 выбранных вершин единицу. В результате на выхо" де элемента 13 будет высокий потенциал, по которому триггер 9 переходит в единичное состояние, подача кода, соответсвующего выбранной задаче счетчика 8, на входы шифратора 14 прекращается и на регистре 12 записывается другой код, по которому ЭВМдиспетчер выбирает нереализованные программы. Изменение состояния регистра 24 должно выполняться также после каждого очередного завершения обрабатываемой задачи.

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

Устройство для распределения sagaний процессорам по авт.св. У 940164, о т л и ч а ю щ е е с я тем, что, с целью оптимизации распределения заданий с учетом совместимости задач, входящих в данное задание, в устройство введены регистр текущей задачи, пятая группа элементов И и матрица формирователей совместимости задач, каждая ячейка матрицы формирователей. совместимости задач содержит элемент 2И-ИЛИ, каждая ячейка, лежащая на диагонали и под диагональю матрицы формирователя совместимости задач, дополнительно содержит триггер, выход регистра текущей задачи соединен с инверсным входом первого элемента И каждого элемента 2И-ИЛИ одноименной строки матрицы формирователей совместимости задач и с первым входом второго элемен" та И того же элемента 2И-ИЛИ, выход триггера каждой ячейки каждого столбца матрицы формирователей совместимости задач соединен с вторым входом второго элемента И элемента 2И-ИЛИ своей ячейки, выход триггера ij-й ячейки матрицы соединен с вторым входом второго элемента 2И-ИЛИ ij-й ячейки матрицы, где i=1 n — номер столбца матрицы формирователей совместимости задач; j-2, ..., и — номер строки матрицы формирователя совместимости задач, выходы элементов 2И-ИЛИ каждого столбца матрицы формирователей совместимости задач

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

Составитель M. Кудряшов

Редактор Е. Копча ТехредП.Сердюкова Корректор A. Тяско

Заказ 604/46 Тираж 704 Подписное

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

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

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