Устройство для распределения задач процессорам Советский патент 1988 года по МПК G06F9/50 

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

I Цель изобретения - расширение фун- 1кциональных возможностей устройства 1за счет обеспечения равномерного по |времени распределения задач процес- ICOPOM.

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

..

Устройство Содержит сдвигающие регистры 1, элементы НЕ 2, элементы И 3, элементы И 4,элементы ИЛИ 5, элементы И 6, триггеры 7, триггеры 8 элементы И 9, элементы И 10, элементы ИЛИ 11, схемы 12 сравнения, эле- ченты ИЛИ-НЕ 13, первые элементы НЕ |14, . элементы ИЛИ 15, элемент ИЛИ 16, Ьегистр 17, блок элементов И 18, |с;четчик 19, элемент НЕ 20, сдвигающий Ьегистр 21, блок 22 памйти, счетчик Р, дешифратор 24, блок 25 регистров ринхронизиругощие входы 26,27,28 и 29 устройства, входы 30 кода управления устройства, вход 31 установки устрой |:тва, выходы 32 устройства. I Работа устройства начинается с Приведения в исходное состояние элементов схемы,

: В блок 22 заблаговременно записы- фаются коды управления: система диаг йостирования МПС (ММС) выставляет на $ходы 30 адрес чтения блока 22, кото рьт соответствует числу исправных процессоров, в результате чего в ре- 1 истр 21 записьтается рабочий код управления; с первого синхронизирующего входа 26 устанавливаются в нулевое состояние триггеры 8j с синхронизирующего входа 27 приводятся в нулевое состояние информационные разряды регистра 17; приводятся в исходное состояние (нулевое) счетчики 19 и 23; с входа 29 через элементы И 10 и ИЛИ устанавливаются в единичное состояние триггеры 7; с входа 29 подается сигнал на сдвигоньй вход регистра 21 управления, в результате чего на его информационном выходе появляется первый разряд кода управления; с четвертого синхронизирующего входа 29 подается сигнал на счет- ч:ик 23, в результате чего с него считывается первое кодовое число.

0

5

5 о

5

0

5

0

5

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

Работа устройства осуществляется в двух режимах: поиска минимального кода времени выполнения.задачи и поиска максимального кода времени выполнения (далее по тексту соответственно минимальный и максимальный код), Количество разрядов кода управления соответствует числу выполняемых задач на МЛС (ММС), Если МПС содержит Н процессоров и , число кодов управления равняется Н-2 (случаи, когда и не рассматриваются, так как при этом назначение однозначное и не возникает оптимизационной задачи). Таким образом, при фиксированном числе вьшолняемых на МЛС задач, в случае отказов процессоров, возникает Н-2 процедур оптимизации загрузки процессоров по времени выполнения. И поэтому в блоке 22 записываются Н-2 кодов, считьшание которых происходит при подаче на вход 30 устройства с системы диагностирования (СД) МПС адреса, соответствующего состоянию ПМС (по числу исправных процессоров). Рабочий ход управления записьшается в регистр 21 управления. При- последовательном считывании с выхода регистра 21 разрядов кода управления устройство работает в режиме поиска минимального кода или максимального. Если с регистра 21 считывается О, то устанавливается режим поиска минимального кода При этом на выходе элемента НЕ 20 появляется единичный сигнал, разрешающий прохождение инверсного кода с регистра 1, через элемент НЕ 2 и на второй вход второго элемента И 3, и далее через второй элемент ШШ 5 на первый элемент И 6. Если с регистра 21 считывается 1, то устанавливается режим поиска максимального кода. При этом подается единичный сигнал на третий элемент И 4, разрешая тем самым прохождение прямого кода на первый элемент ИЛК 5.

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

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

М N I ;

.

N 2.

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

Значение каждого разряда строки j (О и 1) соответствует одному из режимов работы устройства. Для поиска только максимального кода необходимо строку 3 заполнить всеми единицами. Если необходимо работать только в режиме поиска минимального кода, строка j заполняется нулями. Для оптимального распределения задач на процессоры МПС (ММС) код управлени режимами работы необходимо формировать следующим образом:

Случай 1. М Н & .

t

Определяется номер i позиции

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

i м - (п - J)

2.

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

Случай 2. Н 2.

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

i 2 (п - j).

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

Случай 3. Н 2.

Начиная со старшего номера задачи, в строке проставляются чередующиеся единица и нуль.

. По указанному алгоритму составляет ся таблица записей блока 22 для одного .. фиксированного числа задач. Таким же образом составляются таблицы и для различного числа решаемых на МПС задач. С учетом вьш1есказанного для считьтания из блока 22 в регистр 21

15

10

20 5

зо

35

40

45

0

5

рабочей строки адрес, подаваемый на вход 30 устройства, должен учитывать число решаемых задач (номер таблицы) . и число исправных процессоров.

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

При считьшании с регистра 21 первого разряда кода управления устанав- ливается режим поиска минимального или максимального кода путем разрешения прохождения инверсного кода с регистра 1 на первый элемент И 6 через элементы НЕ 2,. И 3, ИЛИ 5 (в случае нулевого первого разряда) или прямого кода через элементы И 4 и ИЛИ S (в случае единичного первого разряда). Так как в исходном состоянии на выходах всех триггеров 7 присутствует высокий потенциал, то сигнал с выхода триггера старшего разряда (эти триггеры не показаны) регистра 1 ; (i 1,М) через .первый элемент И 6 поступает на вход элемента ИЛИ 16, на выходе которого возникает сигнал,если в сравниваемых разрядах хотя бы одного из кодов имеется единица. Этот сигнал поступает на первые входы каждой схемы 12 сравнения, на выходах которых возникает сигнал сброса соответствующего триггера 7, в том случае, если информация в сравниваемом разряде совпадает с нулем. С триггера 7 на первый элемент И 6 поступает запрещающий (низкий) потенциал перед началом сравнения следующих разрядов кода (инверсного или прямого).

После Процедуры сравнения старших разрядов инверсного или прямого кодов происходит подача импульса сдвига на третий синхронизирующий вход 28 устройстваi в результате чего в сдвигающих регистрах 1 происходит сдвиг кодов на один разряд, и процесс сравнения очередных разрядов продолжается, и т.д. до тех пор, пока число таких сдвигов и сравнений не будет равно числу М, о чем свидетельствует сигнал переполнения счетчика 19. Сигнал переполнения счетчика 19 поступает на первьй вход блока элементов И 18, выходы которого подсоединены к входам регистра 17. К моменту появления сигнала переполнения на выходе счетчика 19 заканчивается процесс определения максимального кода (или кодов, если их несколько). Фактически, если устройство работает

в режиме поиска минимального кода, данный, найденный инверсный макси- мальньм код соответствует минимальному коду,- записанному в соответст- вующем регистре 1, В режиме поиска максимального кода это максимальный код. При одновременном, единичном состоянии нескольких триггеров 7 в регистре 17 и на его выходах появ- ляется один единичньй сигнал т.е. предпочтение отдается той задаче, порядковый номер которой наибольший среди задач, имеющих одинаковое требуемое время для решения. Это дос- тигается за счет наличия элементов 13-15.

Таким образом, позиционный код номзра минимального или максимального кода фиксируется в регистре 17 и подается на информационные входы блока 25 регистров, а также обеспечивает .сброс соответствующего второго триггера 8 в нулевое состо- Iяние. .

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

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

0 5

о

5

5

0

5

0

следующий регистр блока 25 регистров Далее по входу 28 подает-ся серия сигналов сдвига, в результате чего обеспечивается процесс определения номера очередной задачи для записи в блок 25 регистров и последующего назначения. Так как триггер 7 канала, где произошел выбор задачи, сигналом с входа 29 переведен в нулевое состояние (через элементы И 10 и ИЛИ 11), то код задачи, записанный в соответствующем регистре 1, не участвует в дальнейшем процессе сравнения. Таким образом, в результате работы предлагаемого устройства в блоке 25 регистров записаны позиционные коды номеров всех задач, предназначенных для выполнения на МПС, времена выполнения которых (минимальное или максимальное) чередуются в порядке следования нулей и единиц в коде управления. При выборе первого максимального кода, максимальным становится еле- .дующий за ним код. Аналогично и для минимального кода. Зная порядок, в котором записаны коды номеров задач, и имея ввиду, что они также записаны в блоке 25 регистров в виде удобном для назначения, установим несложньй алгоритм распределения задач между процессорами, который может быть реализован процессором управления МПС. Считьшание кодов номеров выбранных задач осуществляется с выходов 32 устройства.

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

Устройство для распределения задач процессорам, содержащее элемент ИЛИ, регистр, блок элементов И, первый счетчик, m каналов (т - число решаемых задач), каждый из которых, кроме первого и т-го каналов., содержит.,, сдвиговый регистр, первый элемент И, первый триггер, схему сравнения, эле- , мент ШШ-НЕ, первый элемент НЕ и пер- вьй элемент ИЛИ, первый канал содержит сдвигающий регистр, первьй элемент И, первый триггер, схему сравнения и элемент Ш1И-НЕ, а ш-й канал содержит сдвигающий регистр, первый элемент И, первый триггер и схему сравнения, причем информационные входы сдвигающих регистров каждого канала соединены со своими выходами, сдвиговые входы сдвигающих регистров всех каналов соединены с первым синхронизирующим входом устройства и счетным входом первого счетчика,прямой выход первого триггера каждого канала соединен с первым входом первого элемента И, выход которого- соединен с первым входом схемы сравнения и через первый элемент НЕ - с первым входом элемента ИЛИ-НЕ этого же канала и с соответствующим входом элемента ИЛИ, выход которого соединен с вторыми входами схем сравнения каждого канала, первый вход первого элемента И каналов с второго до )(in-1)-ro соединен с первьм входом первого элемента ИЛИ своего канала, второй вход первого элемента ИЛИ и элемента ИЛИ-НЕ каждого канала,кроме (т-1)-го, соединен с выходом первого элемента ИЛИ следующего канала, второй вход первого элемента ИЛИ и элемента ИЛИ-НЕ (m-l)-ro канала соединен с первым входом первого элемента И тп-го канала и первым управляющим входом блока элементов И, ос- тальные управляюоще входы которого соединены с выходами элементов ИЛИ-НЕ группа информационных входов блока элементов И соединена с выходами первого счетчика, выходы блока элемен тов И соединены с входами регистра, вход сброса которого соединен с вторым синхронизирующим входом устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет равномерного времени распределения задач процессорами, в него введены элемент НЕ, сдвигающий регистр, блок памяти, второй счетчик, дешифратор, блок регист- ров, а в каждый канал введены второй элемент НЕ,, второй, третий, четвертый и пятый элементы И, второй и третий элементы ИЛИ, второй триггер, причем выход сдвигающего регистра каждого канала соединен с первым входом второго элемента И и через второй элемент НЕ - с первыми входами третьих элементов И каналов, йторые входы вторьс; элементов И каналов соединены с выходом сдвигающего регистра и входом элемента НЕ, выход которого соединен с вторыми входами третьих элементов И каналов, выходы второго и третьего элементов И каждого канала.

.-

кроме первого, соединены соответст

Q 2025,

35

45

50

55

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

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

Номера задач

.l-Ii-I:::LLl:::T

n - 1 n - 2

Чп-,

qn-z.i

Чп-(,г Чл-г,7

n -. J

4n-j,7

2 поле

j,( , 2.2

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

Примечание. j 1, К- число исправных продессоров,

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

Составитель М. Кудряшов

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

Заказ 4771/47

Тираж 704

ВНИИПИ Государственного комитета СССР

ПС делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

m

И-l.i

Чп-7,;

Чп-1,ГО Чп-Д,1п

Jn-j,tn

2,m

Подписное