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

-з; АНИЕ ИЗОБРЕТЕНИЯ с вания в составе ВМ для автоматидной программы мм со. структурой, ориентированным автоматического абот, и является ционир орной а очер програ чено для фун мультипроцес ческого вы из множест н аданнои аци рафом, а та интеза расп е дляаний СУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ А ВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССРУ 940164, кл. С 06 Р 15/20, 1980(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯЗАДАНИЙ ПРОЦЕССОРАМ(57) Изобретение относится к областивычислительной техники и предназна,80137423 усовершенствованием устройства поа.с. Р 940164. Цель изобретения -оптимизация распределения заданийучетом совместимости задач, входящих в данное задание. Для достиженияданной цели в устройство введены регистр текущей задачи, группа элементов И и матрица формирователей совместимости задач, причем каждая ячейка матрицы формирователей совместимости задач содержит элемент 2 И-ИЛИ, каждая ячейка, лежащая на диагонали и под диагональю матрицы формирователей совместимости, содержит триггер, Сущность изобретения заключается в обобщении реализуемых моделей диспетчеризации связанных задач. По- ф мшчо отношения оредшеотнояания задач, Я заданного графом, вводится отношение совместимости, определяющее возмож С ность или невозможность одновременного использования задачами ресурсов системы. 1 ил. Фейустанавливаются в единичное состояние, если есть информационная связь из одной вершины в другую. Соответствующий триггер 2 определяется пересечением строки и столбца. Аналогично устанавливаются в единичное сос- . тояние триггеры 26, если соответствующие задачи совместимы.Триггеры 2 и 26, а также триггеры 6, 9 и 19 и счетчики 8 находятся в нулевом состоянии (цепи установки начальных состояний не указаны). В счетчики 5 соответствующих вершин графа заносятся числа импульсов, дополняющие веса до полной емкости счетчиков.После занесения исходной информации на входах элементов ИЛИ-НЕ 3, объединяющих выходы триггеров 2 в строках, соответствующих конечным вершинам графа, будут "1".Первоначально в устройстве происходит определение величин максимальных путей, связывающих данные вершины с конечными (формируются значения уровней вершин). При этом пусковой сигнал на входе 20 схемы 17 начального пуска запускает генератор 15, с выхода которого импульсы поступают на входы элементов И 4 и 7, адалее на все счетчики 8, так как в исходном состоянии все триггеры 6 находятся в нулевом состоянии, а соответствующие входы элементов И 7 подключены к нулевым выходам триггеров 6,Кроме того, счетные импульсы поступают через элементы И 4 на те счетчики 5, для которых триггеры 2 одно именной строки матрицы 1 находятся внулевом состоянии. Поэтому на выходесоответствующих элементов ИЛИ-НЕ 3появляется высокий потенциал, благодаря чему на соответствующем входе одноименного элемента И 4 будет "1". Отсчитав число импульсов, пропорциональное весу моделируемой вершины,счетчик 5 переполняется, сигнал переполнения устанавливает в единичноесостояние соответствующий триггер 6,а все триггеры 2 в данном столбцематричной модели сети 1 - в нулевоесостояние. Переброс триггера 6 в единичное состояние обеспечивает прекращение подачи счетных импульсов черезэлемент И 7 на вход счетчика 8, в котором фиксируется код максимальногопути из данной вершины до конечнойвершины графа. 1 1374238Изобретение относится к вычислительной технике и предназначено дляфункционирования в составе мультипроцессорной ЭВМ для автоматическоговыбора очередной программы из множества программ со структурой, заданной ацикличным ориентированным графом, а также для автоматического синтеза расписаний работ и является дополнительным к авт. св. У 940164.Целью изобретения является оптимизация распределения заданий с учетом совместимости задач, входящих вданное задание. 15Сущность изобретения заключаетсяв обобщении реализуемых моделей диспетчеризации связанных задач благо.даря введению матрицы совместимости,регистра текущих обрабатываемых . 20задач и пятой группы элементов И.Помимо отношения предшествованиязадач, заданного графом, вводитсяотношение совместимости, определяющее возможность или.невозможность 25одновременного использования задачами ресурсов системы.На чертеже изображена структурная схема устройства,Устройство содержит матричную модель 1 сети в составе триггеров 2,.группу элементов ИЛИ-НЕ 3, группуэлементов И 4, группу счетчиков 5,группу триггеров 6, группу элементовИ 7, группу счетчиков 8, группу триггеров 9, группу элементов И 10, регистр 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 заносит 55ся информация о топологии моделируемого графа. При этом триггеры 2, которые являются формирователями дуг, 1374238Рассмотренные действия продолжаются до тех пор, пока на выходах .всех триггеров 6 не будут присутствовать низкие потенциалы. На выходе элемента 18 будет низкий потенциал,5 в результате чего прекращается подача счетных импульсов с выхода генератора 15 через элемент И 16 на входы элементов И 4 и 7.С выхода триггера 19 высокий потенциал подается на управляющий вход шифратора 14, который обеспечивает появление высокого потенциала на од- . ном или нескольких своих выходах, которые соответствуют максимальному коду, хранящемуся на одноименном счетчике 8 при условии, что соответствующая этому счетчику задача совместима с каждой из текущих выполняю щихся задач (в противном случае выдача кода счетчика блокируется нулевым сигналом на третьем входе соответствующих элементов И 10). В результате в регистре 12 устанавлива ется код, определяющий задачи (если таковые есть), которые могут выполняться с учетом ограничений на совместимость. Если в регистре 12 имеется хотя бы одна единица, то это значит, что задача, определяемая номером данного единичного разряда, может назначаться на обработку (информация из регистра 12 поступает на выход 22 и далее на вход ЭВМ-диспетчера). Если в регистре 12 нулевой код, то при отсутствии текущих выполняемых задач это значит, что обработка графа завершена, т.е. предполагается, что ЭВМ-диспетчер постоянно40 ведет информацию о текущих выполняе-, мых задачах, что позволяет распознавать подобные ситуации. Кроме того, при наличии нескольких единиц в регистре 12 требуется последователь 45 ная выборка задач на обработку, например, первой выбирается задача с минимальным номером разряда в регистре 12, причем после того,как выбор текущей задачи сделан, ЭВМ-диспетчер по вторым входам усройства устанавливает в регистре 24 текущих обрабатываемых задач код, наличие единицы в соответствующем разряде которого определяет, что задача обрабатывается. С учетом состояния регистра 24 устанавливается нулевой уровень на выходе тех элементов И 28 пятой группы, которые определяют несовместные по отношению к обрабатываемым задачи, тем самым эти задачи временно исключаются из поля зрения ЭВМ-диспетчера, Затем ЭВМ-диспетчер записывает в соответствующий номеру выбранной задачи разряд регистра 11 выбранных вершин единицу. В результате на выхо" де элемента 13 будет высокий потенциал, по которому триггер 9 переходит в единичное состояние, подача кода, соответсвующего выбранной задаче счетчика 8, на входы шифратора 14 прекращается и на регистре 12 записывается другой код, по которому ЭВМ- диспетчер выбирает нереализованные программы. Изменение состояния регистра 24 должно выполняться также после каждого очередного завершения обрабатываемой задачи.Формула и з о б р е т е н и яУстройство для распределения заданий процессорам по авт.св. У 940164, о т л и ч а ю щ е е с я тем, что, с целью оптимизации распределения заданий с учетом совместимости задач, входящих в данное задание, в устройство введены регистр текущей задачи, пятая группа элементов И и матрица формирователей совместимости задач, каждая ячейка матрицы формирователей. совместимости задач содержит элемент 2 И-ИЛИ, каждая ячейка, лежащая на диагонали и под диагональю матрицы формирователя совместимости задач, дополнительно содержит триггер, выход регистра текущей задачи соединен с инверсным входом первого элемента И каждого элемента 2 И-ИЛИ одноименной строки матрицы формирователей совместимости задач и с первым входом второго элемен" та И того же элемента 2 И-ИЛИ, выход триггера каждой ячейки каждого столбца матрицы формирователей совместимости задач соединен с вторым входом второго элемента И элемента 2 И-ИЛИ своей ячейки, выход триггера Ц-й ячейки матрицы соединен с вторым входом второго элемента 2 И-ИЛИ Ц-й ячейки матрицы, где 1=1 и - номер столбца матрицы формирователей совместимости задач; 3-2, , и - номер строки матрицы формирователя совместимости задач, выходы элементов 2 И-ИЛИ каждого столбца матрицы формирователей совместимости задач1374238 соединены с входами одноименного элемента И пятой группы, выходы которых Составитель М. Ку едактор Е. Копча ТехредЛ.Сердюковаректор А. Тяско аказ 604/4 одписноСР ого комитетаий и открытийРаушская наб п 3 фическое предприятие, г. Ужгород, ул. Проектная,оизводственно-п Тираж 704 Государстве елам изобрет Москва, Жсоединены с третьими входами одноименных элементов И второй группы.