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

 

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

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

СОЦИАЛИСТИчЕСКих

РЕСПУБЛИК (я)ю G 06 F 15/20, 9/46

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

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

ПРИ ГКНТ СССР

°

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4627340/24 (22) 27.12.88 (46) 30.01.91. Бюл. М 4 (72) И.Ф. Скорлупин, Ю,В. Тюменев и А,В. Мателев (53) 681.325(088.8) (56) Авторское свидетельство СССР

N- 1013963, кл. G 06 F 15/20, 1983, Авторское свидетельство СССР

М 1275464, кл. G 06 F 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

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

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

На фиг.1 представлена структурная схема устройства для распределения заданий процессорам; на фиг.2 — структурная схема блока выбора заданий.

Устройство (фиг,1) содержит каналы, в каждом из которых группа триггеров 1, группы триггеров 2, группу элементов И 3, группу элементов И 4, группу элементов НЕ 5, группу элементов И 6, группу блоков элементов И 7. Устрсйство содержит группу элементов ИЛИ 8, группы элементов И 9, 10,,,Я3,, 1624473 А1 даний процессорам в многопроцессорной вычислительной системе (МВС) класса

МКМД при вертикальном распараллеливании программ. Цель изобретения — повышение быстродействия устройства, Устройство содержит каналы, а в каждом канале три группы элементов И, группу блоков элементов И, группы элементов НЕ, две группы триггеров. Устройство содержит группу элементов ИЛИ, блок выбгt.е заданий. счетчик, группу триггеров, элемент ИЛИ, элемент И, дешифратор. При освобождении любого процессора очередное задание распределяется сразу до окончания текущего задания, 2 ил, группу триггеров 11, элемент ИЛИ 12, блок 13 выбора заданий, элемент И 14, счетчик 15, дешифратор 16, тактовый вход 17 устройства, вход опроса 18 устройства, сигнальные входы 19 устройства, информационные выходы 20 устройства, входы 21, 22 бока 13, выхода 23, 24 блока 13.

Блок выбора заданий (фиг.2) содержит каналы 25, в каждом из которых триггеры 26 группы, группу элементов И 27, группу элементов И вЂ” НЕ 28, группу элементов И 29, блок выбора заданий содержит группу элементов ИЛИ 30, группу элементов ИЛИ 31 и узел 32 приоритета, Устройство работает следующим образом, В исходном состоянии есе триггеры находятся в нулевом состоянии. Первоначально в матрицу триггеров 1 заносится

1624473 информация о топологии пройденных путеи (установочные входы на схеме не показаны), В триггеры 2 заносится информация аналогичная, за и-ключением информации о последних вершинах, По управляющему сигналу, который поступает на вход 17, в триггеры 11 заносится информация о свободных процессорах по гходам 19 устройства. Если свободен хотя бы один процессор, то единичный сигнал, пройдя через элемент

ИЛИ 12, подается на элемент И 14 и на группу элементов И 9. На вход 18 устройства подается управляющий сигнал, частота которого больше астоты управляющего сигнала, который подается на вход 17 устройства. Единичный сигнал с выхода элемента И 14 подается на счетчик 15 и с него на дешифратор 16, с выхода дешифра ора сигналы подаются иа первые входы элементов И группу 6, На вторые входы этих элементов подается информация с триггеров 1, Единичные сигналы с триггеров 1 проходит через элементы И 6, элементы ИЛИ 8, элементы И 9 и подаются на входы блока 1.",.

Блок 13 работает следующим образом.

Сигналы, поступающие на входы 21 блока, проходят через узел 32, который выделяет один сигнал. Выделенный си нал поступает на вход элемента И группы 27. На второй вход элемента поступает сигнал с соответствующего триггера 11, Если триггер 11 находится в единичном состоянии, го сигнал с узла 32 поступает на вход установки в "1" триггера 26 группы. Если триггер 11 находится в нулевом состоянии, то сигнал проходит через элементы И вЂ” НЕ 28 и И 29 групп для установки следующего триггера

26 группы. Сигнал с выхода триггера 26 группы поступает на входы элементов ИЛИ

31 и ИЛИ 30 групп. С выхода элементов ИЛИ

31 группы единичный сигнал поступает на вход установки в "0" соответству.ощего триггера 11. Это говорит о том, что процессор начал обработку соответствующей вершины. Одновременно сигнал с выхода элемента ИЛИ 30 группы поступает на элсменты НЕ 5. С выхода элементов НЕ 5 сигнал подается на вход элемента И 4 группы.

На вторые входы элементов И 4 группы подаются сигналы с инверсных выходов триггеров 1. С выхода элемента И 4 группы сигнал поступает на вход установки в "0" триггера

2 группы. С выхода триггеров 2 группы сигнал подается на входы управления блоко 7, который разрешает прохождение едии1чных сигналов с остальных триггеров 1, Сброс триггера 2 свидетельствует обокончании обработки соответствующей вершины.

Ъ:

«l »

5К

Формул; и-:обретения

Устройство для распределения заданий процессорам, содержащее группу триггеров, элемент И, элемент ИЛИ, счетчик, блок выбора заданий, две группы элементов И, группу блоков элементов И, группу элементов ИЛИ, каналы, а в каждом канале пеовую группу трип еров, c т л и ч а о щ е е с я тем, что. с целью повь гпения быстродействия, устройство содержи де ли«»ратор, а в каждом канале вторую -oynny триггеров, три групп. эле;агентов» И и группу элементов НЕ, причем nрямой выходка:кдо"о триггера первой группы кажг ого канала соединен с перBblM вхо, 1м одноименного элемента И пеовой группы вос;о канаг:а, выходы элеме тoB И (pBCA ðynnü v . до -э канала соединены с инфг им:цио «»ыми входами одноименного блока м,.ментов И, втс рой вход л, ждого элс:лента 1 первой группы во все>. каналах соединен с одноименным выходом дешифра-ор=, входы которого соедииеиь; с выходами счетчика, счетный вход ко орого соединен с вь .ходом элемента И, первый вход ксторсгG соединен с входом опроса устройства управляющий вход каждого блока эл::ме гов И гоуппы соедииги с вь»ходом,ервого триггерэ второй группы одноименного канала, выход первого элемента И -;.:рвой групг,ы в каждом канале с,едииен с гервым входом одноименного элемента И в-орой группы данного знал; первые . ходы элементов И второй гр ппы, начиная с второго в каждом

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

i.анапа, выход первого элемен а И первой группы каждого канала и выходы каждого ,iJlQKG элементов И групгы соединены с входами одноименного элемента ИЛИ группы, ьь.ход каждого элемента ИГ1И группы соединен с первь м входом одноименного элемента И первой группы, в орые входы которых соединены с выходом элемента ИЛИ и вторым входом элемента И, входы элемента

ИЛИ соединены с входами триггеров группы, входы сброса которь;х сосдинены с первой группой выходов блока выбора заданий, вторая группа выходов которого является группой информационных выходов устройства, каждый и ко1орых соединен с вторыми входами элементов И второй группы одноименного канала и в атом канале через элементы НЕ группы с пеовыми входами элементов И третьей группы, в каждом канале выход элемента И второй группы соед.ливи с входом сброса эдноименного триггера первой груг.пы, инверсный выход триггера первой группы, кг.эме по»;леднего, 1624473 соединен в своем канале с вторым входом одноименного элемента И трет ей группы, выход Yàæäçãî элемент: И трет е, группы соединен с входом сброса одноименного триггера второй группы свое о канала, sblходы элементов ИЛИ группы соединен с информационными входами блока выбора заданий, входы запуска которого соединены с выходами триггеров группы, единичные входы которых соединены с выходами

5 элементов И второй группы и входами сброса блока выбора заданий.

1624473

Составитель M.Êóäðÿøoâ

Редактор АДолинич Техред М.Моргентал Корректор А.Долинич

Заказ 192 Тирвж Подписное

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

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

Проиэводственно-издательский комбинат "IlsTBHT, г, Ужгород, ул.Гагарина, 1р1