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

 

СОЮЗ СОВЕТСНИХ . СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

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

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4206413/24-24 (22) 06.03.87 (46) 23,09.88. Бюл, и 35 (7.2) В.И. Писаренко и Ю.А. Надедов (53) 681. 325 (088. 8) (56) Авторское свидетельство СССР

R. 620976, кл. G 06 F 7/02, 1977.

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

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

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

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

„.зо„„щщг у (50 4 G 06 F 9/46 содержит сдвигающий регистр, первый элемент И, первый триггер, схему сравнения, элементы ИЛИ-НЕ, первые элементы НЕ, ИЛИ и в него введены элемент НЕ, сдвигающий регистр, блок памяти, второй счетчик, дешифратор, блок регистров, а в каждый канал введены вторые элементы НЕ, элементы И и ИЛИ, вторые триггеры. Сущность изобретения состоит в использовании элементов НЕ на выходе кольцевых сдвигающих регистров,,которые формируют инверсные коды времени выполнения задач по сигналам с регистра управления таким образом, что в блок регистров устройства заносятся позиционные коды номеров задач с минимальным и максимальным временем выполнения. Применение новых элементов позволяет организовать работу устройст-. ва в режиме поиска минимального и максимального кодов, группировать задачи по процессорам таким образом, чтобы общее вр мя выполнения всех задач было минимальным. 1 табл. 1 ил.

1425671

Изобретение относится к вычислительной технике и может быть использовано при организации вычислительного процессора в многопроцессорной (МПС) или в многомашинной (ММС) вычислительной системе.

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

iCOPOM.

На чертеже изображено предлагаеое устройство.

Устройство содержит сдвигающие

Регистры 1, элементы HE 2, элементы

3, элементы И 4,элементы ИЛИ 5, лементы И 6, триггеры 7, триггеры 8, лементы И 9, элементы И 10, элемен гы ИЛИ 11, схемы 12 сравнения, элеенты ИЛИ-HE 13, первые элементы НЕ

,14, элементы ИЛИ 15, элемент ИЛИ 16, 1 егистр 17, блок элементов И 18, счетчик 19, элемент НЕ 20, сдвигающий25 егистр 21, блок 22 памяти, счетчик

3, дешифратор 24, блок 25 регистров, синхронизирующие входы 26,27, 28 и 29 стройства, входы 30 кода управления стройства, вход 31 установки устрой- 30

6тва, выходы 32 устройства.

Работа устройства начинается с . приведения в исходное состояние элементов схемы.

В блок 22 заблаговременно записываются коды управления: система диагностирования МПС (MMC) выставляет на входы 30 адрес чтения блока 22, который соответствует числу исправных процессоров, в результате чего в pes""èñòð 21 записывается рабочий код управления; с первого синхронизирующего входа 26 устанавливаются в нулевое состояние триггеры 8; с синхронизирующего входа 27 приводятся в нулевое состояние информационные разряды регистра 17; приводятся в исходное состояние (нулевое) счетчики 19 и 23; с входа 29 через элементы И 10 и ИЛИ устанавливаются в единичное

50 состояние триггеры 7; с входа 29 подается сигнал на сдвиговый вход регистра 21 управления, в результате чего на его информационном выходе появляется первый разряд кода управ- . ления; с четвертого синхронизирующе55 го входа 29 подается сигнал на счетчик 23, в результате чего с него считывается пергое кодовое число, дешифрация которого приводит к возбуждению первой выходной шины дешифратора 24; с входа 31 в регистры 1 заносятся коды, соответствующие длительности решения задач в МПС (NMC), таким образом, чтобы нумерация задач соответствовала нумерации регистра 1, количество решаемых задач М.

Работа устройства осуществляется в двух режимах: поиска минимального кода времени выполнения. задачи и поиска максимального кода времени выполнения (далее по тексту соответственно минимальный и максимальный код).

Количество разрядов кода управления соответствует числу выполняемых задач на МПС (MMC). Если МПС содержит

Н процессоров и Н с M число кодов управления равняется Н-2 (случаи, когда Н=М и Н=1 не рассматриваются, так как при этом назначение однозначное и не возникает оптимизационной задачи). Таким образом, при фиксированном числе выполняемых на МПС задач, в случае отказов процессоров, возникает Н-2 процедур оптимизации загрузки процессоров по времени выполнения. И поэтому в блоке 22 записываются Н-2 кодов, считывание которых происходит при подаче на вход 30 устройства с системы диагностирования (СД) KIC адреса, соответствующего состоянию ПМС (по числу исправных процессоров). Рабочий ход управления записывается в регистр 21 управления. При последовательном считывании с выхода регистра 21 разрядов кода управления устройство работает в режиме поиска минимального кода или максимального. Если с регистра 21 считывается "0", то устанавливается режим поиска минимального кода, При этом на выходе элемента

НЕ 20 появляется единичный сигнал, разрешающий прохождение инверсного кода с регистра 1, через элемент НЕ 2 и на второй вход второго элемента

И 3, и далее через второй элемент

ИЛИ 5 на первый элемент И 6. Если с регистра 21 считывается "1", то устанавливается режим поиска максимального кода. При этом подается единичный сигнал на третий элемент И 4, разрешая тем самым прохождение прямого кода на первый элемент ИЛИ 5. !

Как указывалось, вид кода управления определяется количеством исправных процессоров в МПС (ММС) и при

1425671

М

М» N>

М вЂ” >N 2

У!

N=2.

45 его формировании рассматриваютсяследующие соотношения между числом процессоров и количеством задач М:

Для описания алгоритма формирования кодов управления рассмотрим информационное поле ПЗУ в виде таблицы.

Значение каждого разряда строки ("О" и "1") соответствует одному из режимов работы устройства. Для поиска только максимального кода необходимо строку j заполнить всеми 2О единицами. Если необходимо работать только в режиме поиска минимального кода, строка j заполняется нулями.

Для оптимального распределения задач на процессоры MIIC (MMC) код управления 25 режимами работы необходимо формировать следующим образом:

Случай 1. M > Н -— с

Определяется номер i позиции 3р строки j начиная с которой записываются чередующиеся нуль и единица (в сторону уменьшения номеров задач):

Остальные позиции заполняются единицами.

Случай 2. — . Н 2.

Определяется номер i позиции стро- 4О ки 3, начиная с которой записываются чередующиеся единица и нуль (в сторону уменьшения номеров задач):

Остальные позиции заполняются нулями, Случай 3, Н = 2.

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

55 различного числа решаемых на МПС задач. С учетом вышесказанного для считывания из блока 22 в регистр 21 рабочей строки адрес, подаваемый на вход 30 устройства, должен учитывать число решаемых задач (номер таблицы) н число исправных процессоров.

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

При считывании с регистра 21 первого разряда кода управления устанавливается режим поиска минимального или максимального кода путем разрешения прохождения инверсного кода с регистра 1 на первый элемент И 6 через элементы HE 2,. И 3, ИЛИ 5 (в случае нулевого первого разряда) или прямого кода через элементы И ч и

ИЛИ 5 (в случае единичного первого разряда) ° Так как в исходном состоянии на выходах всех триггеров 7 присутствует высокий потенциал, то сигнал с выхода триггера старшего разряда (эти триггеры не показаны) регистра 1; (i = 1,М) через первый элемент

И 6 поступает на вход элемента ИЛИ

16, на выходе которого возникает сигнал, если в сравниваемых разрядах хотя бы одного из кодов имеется единица. Этот сигнал поступает на первые входы каждой схемы 12 сравнения, на выходах которых возникает сигнал сброса соответствующего триггера 7, в том случае, если информация в сравниваемом разряде совпадает с нулем.

С триггера 7 на первый элемент И 6 поступает запрещающий (низкий) потенциал перед началом сравнения следу. ющих разрядов кода (инверсного или прямого).

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

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

19. Сигнал переполнения счетчика 19 поступает на первый вход блока элементов И 18, выходы которого подсоединены к входам регистра 17. К моменту появления сигнала переполнения на выходе счетчика 19 заканчивается процесс определения максимального кода (или кодов, если их несколько) °

Фактически, если устройство работает

1425671 в режиме поиска минимального кода, данный, найденный инверсный максимальный код соответствует минималь.ному коду,- записанному в соответствующем регистре 1; В режиме поиска

1 ,максимального кода это максимальный

1 код. При одновременном, единичном состоянии нескольких триггеров 7 в

,регистре 17 и на его выходах появ ляется один единичный сигнал т.е.

,предпочтение отдается той задаче, порядковый номер которой наибольший

1 среди задач, имеющих одинаковое требуемое время для решения. Это достигается за счет наличия элементов

13 — 15.

Таким образом, позиционный код номера минимального или максимального кода фиксируется в регистре 2р ,17 и подается на информационные

1 входы блока 25 регистров, а также

,обеспечивает .сброс соответствующего второго триггера 8 в нулевое состо-!

, яние. 25

При приведении устройства в исход ное состояние на выходе счетчика 23 ,устанавливается код, обеспечивающий после дешифрации на дешифраторе 24 ! подачу сигнала разрешения записи ко-! да в первый регистр блока 25 регистров. В дальнейшем при каждой подаче сигнала на вход 29 на выходе счетчика устанавливается такой код, кото:рый обеспечивает активизацию второго, :третьего, ... и т.д. выходов дешиф35 ратора 24. В результате чего после:дующие позиционные коды номеров задач соответственно заносятся во второй, третий, ... регистры блока 25 реги- 40 стров.

После занесения в регистр блока 25 регистров позиционного кода номера выбранной задачи по входу 27 подается сигнал сброса регистра 17 в исходное нулевое состояние, по входу

29 сигнал установки тех триггеров 7 в единичное состояние, в канал которых триггер 8 еще находится в единичном состоянии (не было выбора соответствующей задачи). С входа 29 син-. хронизирующим сигналом происходит сдвиг на один разряд кода управления в регистре 21 (установка следующего режима поиска) и установка на счетчике 23 следующего кода, в результате чего на выходе дешифратора 24 активизируется очередная шина, с которой поступает сигнал разрешения записи в следующий регистр блока 25 регистров:

Далее по входу 28 подается серия сигналов сдвига, в результате чего обеспечивается процесс определения номера очередной задачи для записи в блок 25 регистров и последующего назначения. Так как триггер 7 канала, где произошел выбор задачи, сигналом с входа 29 переведен в нулевое состояние (через элементы И 10 и ИЛИ

11), то код задачи, записанный в соответствующем регистре 1, не участвует в дальнейшем процессе сравнения, Таким образом, в результате работы предлагаемого устройства в блоке 25 регистров записаны позиционные коды номеров всех задач, предназначенных для выполнения íà MIIC времена выполнения которых (минимальное или максимальное) чередуются в порядке следования нулей и единиц в коде управления. При выборе первого максимального кода, максимальным становится следующий за ним код. Аналогично и для минимального кода, Зная порядок, в котором записаны коды номеров задач, и имея ввиду, что они также записаны в блоке 25 регистров в виде удобном для назначения, установим несложный алгоритм распределения задач между процессорами, который может быть реализован процессором управления МПС.

Считывание кодов номеров выбранных задач осуществляется с выходов 32 устройства.

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

Устройство для распределения задач процессорам, содержащее элемент ИЛИ, регистр, блок элементов И, первый счетчик, m каналов (m — число решаемых задач), каждый из которых, кроме первого и m-ro каналов, содержит, сдвиговый регистр, первый элемент И, первый триггер, схему сравнения, эле,мент ИЛИ-НЕ, первый элемент НЕ и первый элемент ИЛИ, первый канал содержит сдвигающий регистр, первый элемент И, первый триггер, схему сравнения и элемент ИЛИ-НЕ, à m-й канал содержит сдвигающий регистр, первый элемент И, первый триггер и схему сравнения, причем информационные входы сдвигающих регистров каждого канала соединены со своими выходами, сдвиговые входы сдвигающих регистров всех каналов соединены с первым син1425671 хронизирующим входом устройства и счетным входом первого счетчика,прямой выход первого триггера кажпого канала соединен с первым входом пер5 ваго элемента И, выход которого соединен с первым входом схемы сравнения и через первый элемент НŠ— с первым входом элемента ИЛИ-НЕ этого же канала и с соответствующим входом элемента ИЛИ, выход которого соединен с вторыми входами схем сравнения каждого канала, первый вход первого элемента И каналов с второго до

1(тп-1)-го соединен с первым входом первого элемента ИЛИ своего канала, второй вход первого элемента ИЛИ и элемента ИЛИ-НЕ каждого канала,кроме (m-1)-ro, соединен с выходом первого элемента ИЛИ следующего канала, второй вход первого элемента ИЛИ и элемента ИЛИ-НЕ (m-1)-ro канала соединен с первым входом первого элемента И m-го канала и первым управ- . ляющим входом блока элементов И, ос- 25 тальные управляющие входы которого соединены с выходами элементов ИЛИ-НЕ, группа информационных входов блока элементов И соединена с выходами первого счетчика, выходы блока элемен ЗО тов И соединены с входами регистра, вход сброса которого соединен с вторым синхронизирующим входом .устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет равномерного времени распределеяия задач процессорами, в него введены элемент НЕ, сдвигающий регистр, блок памяти, второй счетчик, дешифратор, блок регистров, а в каждый канал введены второй элемент НЕ,. второй, третий, четвертый и пятый элементы И, второй и третий элементы ИЛИ, второй триггер, причем выход сдвигающего регистра каждого канала соединен с первым входом второго элемента И и через второй элемент НŠ— с первыми входами третьих элементов И каналов, вторые входы вторых элементов И каналов соединены с выходом сдвигающего регистра и входом элемента НЕ„ выход которого соединен с вторыми входами третьих элементов И каналов, выходы второго и третьего элементов И каждоro канала, кроме первого, соединены соответственка с первым и вторым входами второго элемента ИЛИ и в первом канале выходы второго и третьего элементов И соединены соответственна с первым и вторым входами первого элемента ИЛИ, выход которого и выходы вторых элементов ИЛИ остальных каналов соединены с. вторыми BxoJIHMH первых элементов И своих каналов, единичный вход первого триггера соединен с выходом четвертого элемента

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

И своего канала.

1425б71

Число процессоров

1 2 ... 1 ... m

Ч п-l,õ и-1 и-2

gn-?,>

Ч и-гд

Чн-I,i

Ч и->,<

Ч п-I,2

Ь-К=2

Ч2,m

Поле кодов управления

Адресное поле

П р и м е ч а н и е. j = 1, K — число исправных про цессоров, Составитель М. Кудряшов

Техред А.Кравчук Корректор А, Обручар

Редактор Г. Гербер

Заказ 4771/47

Тираж 704

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

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

Подписное

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

ln- <,i

Чн-х, Номера задач

ХТ I

Чп-, Ч п-д,