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

 

Союз Советских

Социалистическими

Республик

O П k С А Н И Е < 1оо11о1

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6I ) Дополнительное к авт. свил-ву (22) Заявлено 14.09.81 (2l ) 3335704/1 8-24 (51)М. Кл.

5 06 Р 9/46 с присоединением заявки №

Государственный квинтет (23)Приоритет

lIo делем изобретений н открытий

Опубликовано 28.02.83. Бюллетень № 8

Дата опубликования описания 02.03.83 (53) УДК 681.325 (088.8) В.А.Титов, А.Л.Гайдуков, B.Ë.Ãàéäóêîâ и С.В 1 Назаров . (72) Авторы изобретения (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ

ПРОЦЕССОРАМ

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

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

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

Наиболее близким к предлагаемому по технической сущности является устрой ство для распределения заданий процесс рам, содержащее матрицу триггеров, генератор тактовых импульсов, первый и второй элементы И, схему начального пуска, второй триггер, шифратор, по числу столбцов матрицы третьи элементы И, третьи триггеры, первые счетчики, чет- вертые элементы И, четвертые триггеры, lO вторые счетчики, группы пятых элементов И, пятые триггеры (2).

Недостатком известного устройства является низкая надежность.

11ель изобретения - повышение быст15

Ф родействия устройства.

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

И, первую группу элементов ИЛИ-НЕ, три грутпты триггеров, две группы счетчиков, генератор импульсов, два эле3 100i:L мента И и два триггера, причем группа входов считывания блока памяти соединена с выходами переполнения одноименных счетчиков первой группы и входами одноименных триггеров первой группы выходы которых соединены с первыми входами одноименных элементов И первой группы и с входами первого элемента И, выход которого соединен с входом первого триггера, выход которого 30 соединен с входом сброса второго триггера и с управляющим входом шифратора, информационные выходы которого соединены с единичными входами одноименных триггеров второй группы, выход пер- iS вого из которых является первым информационным выходом группы информационных выходов устройства и соединен с входом первого триггера третьей группы, выход которого и выходы всех остальных 2а триггеров третьей группы соединены с первыми входами одноименных элементов

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

40 блока памяти, выходы элементов И первой группы соединены со счетными входами одноименных счетчиков второй группы, тактовый вход устройства соединен с тактовыми входами триггеров второй группы, введены группа элементов ИЛИ и вторая группа элементов ИЛИ-НЕ, причем единичные выходы первого и второго триггеров второй группы соединены с входами соответствующего элемента ИЛИ группы, выход каждого i -го элемента

ИЛИ группы соединен с первым входом (i +1)-го элемента ИЛИ-НЕ второй группы и с первым входом (i +1)-ro элемента ИЛИ группы, вторые входы ) -х элементов ИЛИ группы, начиная с второго, соединены с единичными выходами (i +1)-х триггеров второй группы, ну» левые выходы триггеров второй группы соединены с вторыми входами соответ- s ствующих элементов ИЛИ-НЕ второй группы, выходы элементов ИЛИ-НЕ второй группы соединены с входами одноименных триггеров третьей группы и являются сс. ответствующими выходами группы информационных выходов устройства.

На чертеже представлена структурная схема устройства. 1

Устройство содержит группу информационных выходов 1 устройства, блок 2 памяти, группу элементов ИЛИ-НЕ 3, группу элементов И 4, группу счетчиков

5, группу триггеров 6, .группу элементов

И 7, группу счетчиков 8, группу триггеров 9, группу элементов И 10, группу триггеров 11, группу элементов ИЛИ 12, группу элементов ИЛИ«НЕ 13, шифратор

14, тактовый вход 15 устройства, генератор 16 импульсов, элемент И 17, триггер 18, элемент И 19, триггер 20,вход

21 запуска устройства.

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

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

3 будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель конечные вершины не. содержат выходящих ветвей.

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

Отсчитав число импульсов, пропорни нальное весу моделируемой вершины, счетчик 5 переполняется, устанавливает в единичное состояние соответствующий триггер 6. Переброс триггера 6 в единич-s ное состояние обеспечивает прекращение подачи счетных импульсов через элемент

И 7 на вход регистрирующего счетчика

8. Вычислительный процесс продолжается до тех пор, пока на выходах всех трщ Ю геров 6 не будут присутствовать низкие потенциалы. На выходе элемента И 19 будет низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 16 через элемент И 17 на входы элементов И 4 и 7.

С выхода триггера 20 высокий потенциал подается на управляемый вход шифратора 14, который обеспечивает появль- 20 нее высокого потенциала на одном или нескольких своих выходах, который соответствует макс мальному коду, хранящемуся на одноименном счетчике 8. На вход шифратора 14 коды со счетчиков 8 25 подаются через элементы И 10, на первые входы которых подается высокий потенциал с нулевых выходов триггеров 9.

В результате на триггерах 11 устанавливается код, содержащий набор нулей и ЗЕ .одной или нескольких единиц. Наличие элементов ИЛИ 12 и элементов ИЛИ-НЕ 13 . обеспечивает появление высокого потенциала только на одном из выходов устройства, что необходимо при появлении единичного сигнала одновременно на нескольких триггерах 11. Высокий потенциал на выходе соответствует позиционному номеру очередной задачи информационно связанно о пакета, которая должна > затем решаться процессором вычислительной системы. Одновременно в единичное состояние перебрасывается соответствую» щий триггер 9.

4S

После выбора одной из программ набора для реализации в вычислительной системе на вход 15 устройства подается высокий потенциал, по которому все триггеры 11 перебрасываются в нулевое состояние. Далее подача кода со счетчиков 8 на вход шифратора 14"прекращаеься и на триггерах 11 записывается другой код, по которому на выходах определяются позиционные номера очередных решаемых задач.

Применение предлагаемого изобрете»ния позволяет повысить быстродействие и надежность работы устройства.

61 6

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

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

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

7 1001101 8 триггеров второй группы соединены с группы, выходы элементов ИЛИ-НЕ втовходами соответствующего элемента ИЛИ рой группы соединены с входами одногруппы, выход каждого 3 -го (=l...„именных триггеров третьей группы и й, где и — число запросов) элемента являются соответствующими выходами

ИЛИ группы соединен с первым входом группы информационных выходов устрой(1 + 1 )-го элемента ИЛИ-НЕ второй ства. группьt и с первым входом (i +1)-ro элемента ИЛИ группы, вторые входы 1 -х Источники информации, элементов ИЛИ группы, начиная с второ- принятые во внимание при экспертизе

ro, соединены с единичными выходами 36 1. Авторское свидетельство СССР (j +1)-х триггеров второй группы, ну- % 664175, кл. 5 06 F 15/20, 1976. левые выходы триггеров второй группы 2. Авторское свидетельство СССР соединены с вторыми входами соответ-. по заявке N 3222438/18-24, ствующих элементов ИЛИ-НЕ второй кл. С, 06 F 15/20, 1980 (прототип).

1001101

RHHHllH Закаэ 1 ЗР7/56 Тираж. 704 Попписное

Филиал ППП Патент, г. Чжгороп, ул. Проектная, 4