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

00

4; to

оо

00

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

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

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

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

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

устанавливаются в единичное состояние, если есть информационная связь из одной вершины в другую. Соответствующий триггер 2 определяется пере- сечение м строки и столбца. Аналогично устанавливаются в единичное сое- тояние триггеры 26, если соответствующие задачи совместимы.

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

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

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

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

И 7, группу счетчиков 8, группу триг-, ветствующие входы элементов И 7 под- геров 9, группу элементов И 10, ре- ключены к нулевым выходам триггеров 6.

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

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

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

5

п

0

5

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

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

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

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

Устройство для распределения за ний процессорам по авт.св. № 94016 отличающее ся тем, что с целью оптимизации распределения заданий с учетом совместимости за дач, ВХОДЯ1ЦИХ в данное задание, в устройство введены регистр текущей задачи, пятая группа элементов И и матрица формирователей совместимос ти задач, каждая ячейка матрицы фо мирователей, совместимости задач с держит элемент 2И-ШШ, каждая ячей ка, лежащая на диагонали и под дн гональю матрицы формирователя совм тимости задач, дополнительно содер жит триггер, выход регистра текущей задачи соединен с инверсным вх дом первого элемента И каждого эле мента 2И-ИЛИ одноименной строки ма рицы формирователей совместимости дач и с первым входом второго элем та И того же элемента 2И-ИЛИ, выхо триггера каждой ячейки каждого ст ца матрицы формирователей совмести мости задач соединен с вторым вход второго элемента И элемента 2И-ИПИ своей ячейки, выход триггера ij-й

40

по вторым входам усройства устанавли- ячейки матрицы соединен с вторым

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

обрабатьшаемой

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

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

о обрабатьшаемой

5

0

Устройство для распределения заданий процессорам по авт.св. № 940164, отличающее ся тем, что, с целью оптимизации распределения заданий с учетом совместимости задач, ВХОДЯ1ЦИХ в данное задание, в устройство введены регистр текущей задачи, пятая группа элементов И и матрица формирователей совместимости задач, каждая ячейка матрицы формирователей, совместимости задач содержит элемент 2И-ШШ, каждая ячейка, лежащая на диагонали и под дна- - гональю матрицы формирователя совместимости задач, дополнительно содержит триггер, выход регистра текущей задачи соединен с инверсным входом первого элемента И каждого элемента 2И-ИЛИ одноименной строки матрицы формирователей совместимости за;- дач и с первым входом второго элемен та И того же элемента 2И-ИЛИ, выход триггера каждой ячейки каждого столЬ- ца матрицы формирователей совместимости задач соединен с вторым входом второго элемента И элемента 2И-ИПИ своей ячейки, выход триггера ij-й

0

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