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

1277

Устройство Содержит матричную модель 1 рафа, составленную из триггеров 2,j , группу элементов ИЛИ 3, - 3,,

группу элементов И 4 , 12

,- «. 17, 18,

группу счетчиков 5,, - 5,, группу

12,, элементы И 14,

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

Цель изобретения - повышение надежности за счет сокращения аппаратных затрат,

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

Устройство содержит матричную модель 1 графа в составе пхп триггеров 2.-; (ioj П,.ооп) по числу столбцов матрицы группу элементов ШШ 3,,..,, 3j, первую группу элементов И 4,.o. 4 5 группу счетчиков 5 ,,,,5, группу схем 6 э - 6 сравнения , первую группу триггеров 7p..os7, третью группу элементов И 8, „.о,8,, вторую группу триггеров 9,..., регистр 10 выбранных вершин, регистр 11 приоритета, вторую группу элементов И 12 S „. , 512 5 блок 13 поиска максимального кода, второй элемент И 14, счетчик 15, триггер 16, третий 17 и первый 18 элементы И, генератор 19 тактовых импульсов, входы 20 гд 21, выходы 22 и 23.

Блок поиска максимального кода содержит входные элементы И 24,;, элементы ИЛИ-НЕ 25,„,,,25, (где га - разрядность сравниваемых кодов)э группы 26, , „ , 1,26„ поразрядных уз,ло:о сравнения, состоящие из элементов ИЛИ 27 и элементов И 28, вых.оды 29, ,о„ 529 и вхо,ды 30 и .31 .

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

Первоначально в матричную модель графа заносится информация о тополе-

схем сравнения 6 , - 6 , группы триггеров 7 - 7,, 9 - 9 , регистры, генератор 19 тактовых импульсов, счетчик 15 и блок 13 поиска максимального кода,состоящий из элементов И, элементов ИЛИ-НЕ и элементов ИЛИ.2 ил.

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

пересечением 1-й строки и j-ro столб- ца. Триггеры 2;j , вторая группа триггеров 9j , триггер 16, группа счетчиков 5j, счетчик 15, регистр 10 выбранных вершин и регистр 11 приоритета устанавливаются в нулевое состояние. С появлением пускового сигнала по входу 20 импульсы с выхода генератора 19 Тактовых импульсов через открытый первый элемент И 18 (второй вход третьего элемента И 17 подсоединен к об- ратному вьшоду триггера 16) поступают на вход счетчика . 5 и через открытые элементы И 4 . первой группы на входы

.счетчиков ) : группьи При этом импульо

сы не проходят через элементы И 4j первой группы тех столбцов, все триггеры которых находятся в нулевом состоянии. Далее содержимое каждого счетчика группы в обратном коде поступает на первый вход схемы 6- сравнения группы, на второй вход которой поступает обратный код с выхода счетчика 15, а на третий - сигнал с инверсного выхода первого элемента И 18.

При несовпадении показаний счетчи

ка 5j групп ы и счетчика 15 в схеме 6 сравнения группы вырабатьюается

импульс несравнения, который далее перебрасывает в единичное состояние триггер 7j первой группы.

Высокий noTeHLi an с выхода триггера 7j первой группы поступает на i-й вход второго элемента И 14 и на установочные входы триггеров 2-- i-й строId

ки матричной модели 1 графа. После

этого с выхода генератора 19 такто- Bbfx импульсов на входы счетчиков группы и счетчика 15 поступает очередной импульс и т.д.

Вычислительный процесс продолжает- s ся до тех пор, пока происходит сравнение в схемах 6j сравнения группы, т.е. до переброса всех триггеров 7 j первой группы в единичное состояние. Это свидетельствует о том, что все О узлы моделируемого графа распределены по рангам. При этом высокий потенциал с выхода второго элемента И 14 поступает на синхронизирующий вход блока 13 поиска максимального кода, на выходы5 23, сигнализируя о готовности устройства к выбору задачи, и вход триггера 16, который перебрасывается в единичное состояние, в результате чего прекращается подача импульсов с выхода ;0 генератора 19 тактовых импульсов че- рез первый элемент И 18 на входы счетчиков 5j группы и счетчика 15.

Число импульсов, зафиксированное ,на счетчиках 5 ,- группы, соответствует J

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

Далее начинается непосредственное определение и назначение очередной задачи для решения на освободившемся процессоре (вычислительной маиины). Для этого коды с выходов счетчиков 5 J группы поступают через элементы И 8 j третьей группы на входы блока 13 поиска максимального кода. Функционирование блока 13 поиска максимального кода начинается после появления единичного сигнала на выходе второго элемента И 14 (вход 31 на фиг.2). В первый момент анализируются старшие разряды чисел в группе 26 поразрядных узлов сравнения, поступаюище с

Ю

40

50

ВЫХОДОВ счетчиков 5j группы. Если хотя бы один из старших разрядов чисел (входы 30 ( , ,...,n|) равен 1, то на выходе элемента 25, ИЛИ- НЕ формируется О., который служит сигналом запрета для анализа остальных разрядов. При этом, если старпшй разряд i-ro числа (i (l,.. .nj , п - число сравниваемых кодов) равен О, то все i-e разряды не проходят через элементы И 28 i-й группы 26 пораз- рядного узла сравнения.

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

SS

s О ы5;0

,Ю

0

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

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

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

I

После выбора одной из программ набора для реализации в вычислительной системе супервизор записывает в соответствующий номеру (например it {l,...,n) выбранной программы разряд регистра 10 выбранных вершин единицу. В результате на выходе элемента

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

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

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

ка максимального кода, регистр выб-- ранных вершин5, регистр приоритета, первую группу элементе И, группу счетчиков, первую группу триггеров, вторую группу элементов И, группу триггеров, третью группу элементов И, генератор тактовых импульсов, выход KOTopoi o Соединен с первым входом первого элемента И, первый выход которого подключен к первым входам элементов И первой группы, выходы элементов И первой группы соединены соответственно с входами счетчиков группы, выход i--ro триггера первой группы (i (15 .,. ,n l) подключен к i-му входу, втррого элемента И, вы- ход которого соединен с входом триггера, входы регистра выбранных вершин являются группой входов устройства, выходы регистра выбранных вершин соединены с первыми входами соответствующих элементов И второй группы, вторые входы которых являются группой выходов устройства и подключены к

выходам регистра приоритета,, входы

которого соединены с выходами блока поиска максимального кода, информа- 1щонные входы которого подключены к выходам элементов И третьей группы, первый вход i-ro элемента И третьей группы соединен с выходом триггера второй группы, вход i-ro триггера второй группы подключен к выходу элемента И второй групп ., о т

j 5 0

5

О

1066

лью повьшюния надежности за счет сокращения аппаратных затрат в него введены Третий элемент И, группа элементов ИЛИ и группа схем сравнения, вход счетчика подключен к первому выходу первого элемента И, второй выход которого соединен со стробируюш 1- мк входами схем сравнения группы, первые информационные входы которых подключены к выходу счетчика, выходы счетчиков группы соответственно соединены с вторыми информационными входами схем сравнения группы и вторыми входами эле 5антов И третьей группы, выходы схем сравнения группы подключены к входам триггеров первой группы, выход i-ro триггера первой группы соединен с входа; да триггеров i-й строки матричной модели графа, выходы триггеров столбца матричной модели графа подключены к соответствую- тум входам i-ro элемента ИЛИ группы, выходы элементов ИЛИ группы соединены соответственно с вторыми входами элементов И первой группы, выход триггера соединен с первым входом третьего элемента И, второй вход которого является входом пуска устройства, выход третьего элемента И подключен к второму входу первого элемента И , выход второго элемента И подключен к синхронизирующему входу блока поиска максимального кода и к ВЕ)ГХОду готовности устройства .

J/ 0„т ЗОпз 0„г Oni

I I I I i I

30fy Off

I I

29n

f29i

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

Заказ 6667/42Тираж 671Подписное

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

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

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

фиг..

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

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

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