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

 

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

СОЮЭ СОВЕТСНИХ

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

РЕСПУБЛИН (19) (1!) (58 4 G 06 Р 9 46

) 1

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

ГОсудАРстненный НоМНТЕТ сссР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21 ),3 768 993/? 4-24 . (22) 20. 07, 4 (46) 15.12.86. Вюл. 1(- 46 (72) В.M.Êðèêóíoâ, В.А.Титов, В.А.Щербак и Е.Н. Серегина (53) 68 1.333 (088.8) (56) Авторское свидетельство СССР ((664175, кл . G 06 F 15/20, 1976.

Авторское свидетельство СССР

В 940164, кл. С 06 F 9/46, 1980. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

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

1277106

Устройство содержит матричную модель графа, составленную из триггеров

2,„, группу элеменгов ИЛИ 3, — 3,, группу элементов И 4, — 4, 8, — 8„, 12 — 12,„, элементы И 14„. 17, 18, группу счетчиков 5,, — 5», группу схем сравнения б. — б группы триг»1 1 герон 7 „— 7„, 9 — 9, регистры, генератор 19 тактовых импульсов, счетчик 15 и блок 13 поиска максимального кода, состоящий из элементов И, элементов ИЛИ-НЕ и элементов ИЛИ. 2 ил.

Изобретение относится к вычислительной технике и может быть использовано при автоматизации выбора очередной программы из информационно-связанного набора программ, описываемого графом без циклов, для решения его в многопроцессорной (многомашинной) вычислительной системе, Цель изобретения — повышение надежности за счет сокращения аппарат- 1Q ных затрат.

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

Устройство содержит матричную модель I графа в coc,ãÿâå пхп триггеров

2", (i, j 1,...и ) по числу столбцов матрицы группу элементог ИЛИ 3„,..., 3„. первую группу элементов N 4,..., ро группу счетчиков 5 „...,5,, групп пу схем б . ..6 сравнения, первую

19 а а ф 9 группу триггеров 7,...,7, третью группу элементов И 8,....,8 „ вторую .группу триггеров 9,,...,9,, регистр

10 вь1бранных вершин, регистр 11 приоритета, вторую группу элементов И

12,, 12„, блок 13 поиска максимар льного кода, второй элемент И 14„ счетчик 15, триггер 16, третий 17 и первый 18 элементы И, генератор 19 тактовых импульсов, входы 20 и 21, выходы 22 и 23, Блок поиска максимального кода со-держит входные элементы И 24,, элементы ИЛИ-HE 25,...,.„25, (где m — раз35 рядность сравниваемых кодов), группы

26,, :,>26„, поразрядных узлов сравнения, состоящие из элементов ИПИ 27 и элементов N 28, выходы 29,.„.,29„

1 У О О 9»1 4О и вхоцы 30 и 31.

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

Первоначально в матричную модель графа заносится информация о тополо- . гии моделируемого графа сети решаемых задач. При этом триггеры 2..(i,jg j1, 1J ...,и)) матричной модели графа, которые являются формиоователями дуг, устанавливаются в единичное состояние, если есть информационная связь из i-й вершины в j-ю вершину. Соответствующий триггер 2 определяется

1J пересечением i-й строки и j-го столбца. Триггеры 2;„, вторая группа триггеров 9„, триггер 16, группа счетчиков 5„., счетчик 15, регистр 10 выбранных вершин и регистр 11 приоритета устанавливаются в чулевое состояние.

С появлением пускового сигнала по входу 20 импульсы с выхода генератора

19 тактовых импульсов через открытый первый элемент И 18 (второи вход третьего элемента И 17 подсоединен к обратному выходу триггера 16) поступают на вход счетчика 5 и через открытые элементы И 4 первой группы на входы

1 счетчиков 5 „- группы. При этом импульсы не проходят через элементы И 4„. первой группы тех столбцов, все триггеры 2,„ которых находятся в нулевом состоянии. Далее одержимое каждого счетчика 5> группы в обратном коде поступает на первый вход схемы 6.! сравнения группы, на второй вход которой поступает ооратный код с выхода счетчика 15, а на третий — сигнал с инверсного выхода первого элемента

И 18.

При несовпадении показаний счетчика 5„ группы и счетчика 15 в схеме

6 „ сравнения группы вырабатывается ю пульс несравнения, который далее перебрасывает в единичное состояние триггер 7„. первой группы. Высокий потенциал с выхода триггера 7, первои группы поступает íà i-й вход второго элемента И 14 и на установочные входы триггеров 2 i-й строки матричной модели 1 графа. После

127

7106 4 элементы И 28 i-и группы 26, первого поразрядного узла сравнения. На выходе элементов И 28 формируются прямые коды чисел, начиная с второго этого с выхода генератора 19 такто— вых импульсов на входы счетчиков 5

J группы и счетчика 15 поступает очередной импульс и т.д °

Вычислительный процесс продолжает- ся до тех пор, пока происходит сравнение в схемах 6„ сравнения группы, т.е, до переброса всех триггеров 7„ первой группы в единичное состояние.

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

13 поиска максимального кода, на выходы5

23, сигнализируя о готовности устройства к выбору задачи, и вход триггера

16, который перебрасывается в единичное состояние, в результате чего прекращается подача импульсов с выхода :0 генератора 19 тактовых импульсов через первый элемент И 18 на входы счетчиков 5 „ группы и счетчика 15.

Число импульсов, зафиксированное на счетчиках 5 „ группы, соответствует номеру ранга каждой вершины в графе (приоритету каждой задачи решаемого пакета задач в вычислительной системе).

Далее начинается непосредственное определение и назначение очередной задачи для решения на освободившемся процессоре (вычислительной машины).

Для этого коды с выходов счетчиков

5 группы поступают через элементы

И 8 „третьей группы на входы блока

13 поиска максимального кода. Функционирование блока 13 поиска максимального кода начинается после появления единичного сигнала на выходе второго 40 элемента И 14 (вход 31 на фиг.2). В первый момент анализируются старшие разряды чисел в группе 26 поразряд- ных узлов сравнения, поступающие с выходов счетчиков 5 „ группы. Если хотя бы один из старших разрядов чисел (входы 30;,, ic {1,... n ) равен

"1", то на выходе элемента 25, ИЛИНЕ формируется "0":, который служит сигналом запрета для анализа осталь- 0 ных разрядов. При этом, если старший разряд i-ro числа (i Е(1,...п, п число сравниваемых кодов) равен "0", то все i-e разряды не проходят через элементы И 28 i-и группы 26 пораз1 рядного узла сравнения.

Если старший разряд i-ro числа равен "1", то i-e число проходит через по и-й °

Вторым элементом ИЛИ-НЕ 25 сова местно с элементом ИЛИ 27 группы 26 поразрядного узла сравнения анализируются вторые по старшинству разряды таким образом, как и старшие разряды и т.д. Позиционный код номера экспериментального числа получается путем совпадения всех сигналов запрета, сформированных в каждой i-й группе

26 поразрядного узла сравнения. В результате на регистре 11 приоритета будет установлен код, содержащий набор нулей и одной или нескольких единиц. Этот код подается по выходным шинам 22 на супервизор вычислительной системы (не показан), который выбирает для реализации очередную программу, для которой в соответствующем разряде регистра 11 приоритета имеется единица. При наличии в регистре

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

После выбора одной из программ набора для реализации в вычислительной системе супервизор записывает в соответствующий номеру (например

iC.11,...,п)1) выбранной программы разряд регистра 10 выбранных вершин единицу. В результате на выходе элемента

12 И второй группы присутствует высокий потенциал, который перебрасывает триггер 9„ второй группы в единичное состояние, после чего подача обратного кода с выхода счетчика 51 группы на входы блока 13 поиска максимального кода прекращается и на регистре 11 приоритета записывается другой код, по которому супервизор выбирает нереализованные программы.

Работа устройства прекращается после. появления единичных сигналов на всех триггерах регистра 10 выбранных вершин.

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

Устройство для распределения заданий процессорам, содержащее матричную модель графа размерностью и х и (где и — число вершин моделируемого графа), каждый узел которой содержит триггер, а также счетчик, блок поис1277106 ращения аппаратных =-атрат, в него введены третий элемент И, группа элементов ИЛИ и группа схем сравнения, вход счетчика подключен к первому выходу первого элемента И, второй выход которого соедине.н со стробирующими входами схем сравнения группы, первые информационные входы которых подключены к выходу счетчика, выходы счетчиков группы соответственно соединены с BTopblMH информационными входами схем сравнения группы и вторыми входами элементов И третьей группы, выходы схем сравнения группы подключены к входам тригг ров первой группы, выход i ão триггера первой группы соединен с входами триггеров i-й строки матричной модели графа, выходы триггеров i-го столбца матричной модели графа подключены к соответствующим входам i-ro элемента ИЛИ группы, выходы элементов ИЛИ группы соединены соответственно с вторыми входами элементов И первой группы, выходтриггера соединен с первым входом третьего элемента И, втсрой вход которого является входом пуска устройства, выход третьего элемента И подклю— чен к второму входу первого эле— мента И, выход второго элемента

И подключен к синхронизирующему входу блока поиска максимального кода и к выходу готовности устройства единены соответственно с входами счетчиков группы, выход i-го триггера первой группы (iF 1,...,п ) подключен 15 к i-му входу второго элемента 4, вы.ход которого соединен с входом триггера, входы регистра выбранных вершин являются группой входов устройства, выходы регистра выбранных вершин 20 соединены с первыми входами соответствующих элементов И второй группы, вторые входы которых являются группой выходов устройства и подключены к выходам регистра приоритета., входы которого соединены с выходами блока поиска максимального кода, информационные входы которого подключены к выходам элементов И третьей группы, первый вход х-го элемента И третьей . О группы соединен с вьгходом i-го триггера второй группы, вход -го триггера второй группы подключен к выходу

i-го элемента И второй групп ., о е л и ч а ю щ е е с я тем, "-ITQ с цека максимального кода, регистр выбранных вершин„ регистр приоритета, первую группу элементов И, группу счетчиков, первую группу триггеров, вторую группу элементов И, вторую группу триггеров, третью группу элементов И, генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И, первый выход которого подключен к первым входам элементов И первой группы, выходы элементов И первой группы солью повьш|ения надежности з: e". coK

1277106

Юру / Л2 А71

Составитель И.Загорбинина

Техред И.Попович Корректор М.щароши

Редактор Е.Копча

Заказ 6667/42 Тираж 671

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

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

Подписное

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