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

 

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

СОЮЗ СОВЕТСКИХ

СО14ИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„.SU 1410053 A 1 (50 4 G 06 F 15/20

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

К A STOPCKOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4144500/24-24 . (22) 05. 11. 86 (46) 15.07.88. Бюл. М 26 (72) Ю. Н.Долгин, С.А.Дрижчаный и Д.Г.Ивин (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1022164, кл. G.06 F 9/00, 1983.

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

Ф 976442, кл. G 06 F 9/00 1982. (54) УСТРОЙСТВО ДЛЯ АСИНХРОННОЙ АССОЦИАТИВНОЙ ЗАГРУЗКИ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕИЫ (57) Изобретение относится к области вычислительной техники и может быть использовано для организации асинхронного вычислительного процесса в многопроцессорных вычислительных системах с распределенной памятью.

Целью изобретения является повышение производительности за счет поразрядного параллельного считывания информации. Считывание стеков производится в результате сравнения их ассоциативных признаков с признаками иницирования и по готовности процессоров к загрузке. Схема предусматривает возможность многопрограммной загрузки одних и тех же стеков в различные моменты времени в зависимости от общей программы. 2 s.ï. ф-лы, 4 ил.

1410053

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

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

Устройство содержит блок дешифрации и анализа признаков, блок стековой памяти, блок регистровой памяти.

Блок дешифрации и анализа признаков содержит дешифратор признаков 1, включающий регистр шифра признака 2, дешифратор 3 и буферный регистр Йри- 25 знака 4, схему опроса 5, состоящую иэ блока 6 генератора тактовых импульсов, логического элемента И 7 и регистра 8 циклического сдвига, узел хранения и сравнения признаков 9, со- >0 держащий m групп регистров хранения признаков 10, по К регистров 11 в каждой группе, модуль счета 12,включающий m x К групп счета 13, включающих,, в свою очередь, счетчик с установочными входами 14, элемент ИЛИ 15, RS-триггер 16, модуль сравнения ! 17, содержащий m x К групп сравнения (; 18, включающих схему сравнения 19 и логический элемент И 20, входы/выхо ды 21-25.

Блок стековой памяти состоит из группы регистров 26, содержащих m групп регистров хранения стеков 27, . по г регистров хранения 28 в каждом группы элементов И 29, включающей

m x r групп логических .элементов И

30 по с1 элементов в каждой группе 31, группы элементов ИЛИ 32, содержащей

r групп логических элементов ИЛИ 38 по r элементов ИЛИ 34 в каждой груп в 50 пе, входов/выходов 35 и 36.

Блок регистровой памяти содержит регистр готовности процессоров 37, логический элемент ИЛИ 38 Hà и входов и и групп регистров памяти 39, 55 включающих г х и групп логических элементов И 40 ио и элементов И 41 в каждой группе, и г регистров 42,группу логических элементов ИЛИ 43, по и элементов ИЛИ 44 в группе.

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

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

На вход устройства 21 подается шифр признака, назначенного на выполнение в блоке дешифрации и анализа признаков, шифр дешифрируется, и полученный признак сравнивается с признаками, хранящимися в блоке в узле хранения и сравнения признаков. Сравнившиеся признаки выдают сигнал о сравнении в входную шину блока стековой памяти. Сигнал разрешает поразрядную запись стеков в блок регистровой памяти. По входу устройства 35 в блок стековой памяти записываются стеки, необходимые для выполнения данной программы. По входу устройства 45 поступает информация о готовности i-ro, (i = 1,п) процессора к загрузке в блок регистровой памяти, где в регистровую память освободившегося процессора записывается назна ченный на выполнение стек. Задание на процессоры поступает с информационных выходов устройства 46. После загрузки задания в регистровую память блок регистровой памяти подает сигнал на вход блока дешифрации и анализа признаков, который разрешает поиск и сравнение следующего признака.

Вход устройства 22 служит для записи в блок дешифрации и аиализа признаков всех используемых признаков.

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

Блок дешифрации и анализа признаков при помощи схемы дешифрации 1 обеспечивает дешифрование поступившего признака. Узел хранения и сравнения признаков 9 обеспечивает сравнение признака, поступившего из схемы дешифрации и анализа с признаком, хранящимся в узле, и выдачу сигнала

10053 4

1О

3 14 в входную шину 25 блока стековой памяти. Схема опроса 5 обеспечивает поочередный опрос всех признаков, хранящихся в узле хранения и сравнения признаков 9, для поочередного считывания сигнала о сравнившихся признаках в блок стековой памяти.

Дешифрирование, сравнение и считывание единицы сравнившихся признаков осуществляется следующим образом. На вход 21 поступает шифр признака, В дешифраторе признаков 1 шифр поступает на входы регистра 2, куда он записывается. Из регистра 2 шифр считывается в дешифратор 3, где он дешифрируется и поступает на входы регистра 4. Выходы регистра 4 соединены со всеми элементами сравнения 19 узла хранения и сравнения признаков 9, схемы сравнения 17, групп сравнения

18. В каждом регистре 11 записан свой признак. В каждой группе регистров

10 находятся К регистров по количеству признаков, всего m групп — по количеству используемых стеков, причем

К признаков приходится на один стек.

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

1.1 признак поступает на соответствующий элемент сравнения 19 группы сравнения 18, схемы сравнения 17. В той группе 18, где признаки сравнятся, на второй вход логического элемента И 20 поступит "1". На устаковочные входи счетчика 14 поступит число использования данного признака в программе в обратном коде. Число, поступившее на. установочные входы счетчика 14, через элемент ИЛИ 15, разрядность которого равна разрядности счетчика 14, установит RS-триггер 16 в единичное положение, который будет держать "1" на первом входе соответствующего элемента И 20.

Генератор тактовых импульсов 6 схемы опроса 5 выдает тактовый импульс на регистр циклического сдвига 8 через элемент И 7, который открывается "1", поступившей из блока регистровой памяти. Тактовый импульс сдвигает записанную "1" в регистре циклического сдвига 8, и она подается на каждый элемент И 20 группы срав-, нения 18. Один из элементов И 20, на входе которого все "1", выдает импульс, который поступает на тактовый вход счетчика. Таким образом, вычитается единица из записанного числа в счетчике. Тот же импульс пос-. тупает в выходную шину блока дешифрации и анализа признаков ка одну из групп входов 25 блока стековой памяти.

Блок стековой памяти при помощи схемы логических элементов И 29 обеспечивает поразрядное параллельное считывание через схему логических элементов ИЗИ 32 стеков в блок регистровой памяти из группы регистров хранения стеков 27 группы регистров 26.

Поразрядное параллельное считывание стека происходит следующим образом. 1" сравнившихся признаков из блока дешифрации и анализа признаков поступает на соответствующий вход группы входов 25 и подается на первые входы всех элементов И 31 r групп логических элементов И 30, осносящихся к одной группе регистров хранения стеков 27. Каждая группа регистров хранения стеков 27 содержит один стек. Стек записывается в регистры хранения 28 через программный вход устройства 35, а на вторые входы всех элементов И 31 г групп логических элеэлементов И 30 подается информация из одной группы регистров хранения стеков 27. Т.е. происходит считывание требуемого стека из регистров

28 через элементы И 31, причем информация из одного регистра 28 считывается через одну группу логических элементов И 30. Всего в считывании одного стека принимает участие r. х и элементов И 31, где и — число разрядов регистра 28, т.е. каждый разряд считывается через свой элемент И 31 и через свой элемент ИЛИ 34, которых в блоке всего r х d, т.е. один элемент на соответствующий разряд. Каждый элемент ИЛИ 34 имеет m входов по числу стеков или групп регистров храненыя стеков 27. Каждый логический элемент ИЛИ 34 соединен с j-м разрядом, (j = 1, r х d) всех групп реги-стров хранения стеков 27 через логические элементы И 31. Всего в схеме логических элементов ИЛИ 32 находится r групп логических элементов ИЛИ

33 по числу регистров 28 в каждой группе регистров хранения стеков 27 и d элементов ИЛИ 34 в каждой груп5

5 14 пе 33. Таким образом, получается по разрядное параллельное считывание стека в выходную шину блока стековой памяти, каждый j-й разряд стека поступает на j-й выход гууппы выходов 36, где j = (1, r x d).

Блок регистровой памяти с помощью регистра готовности процессоров 37 обеспечивает запись стека, назначенного на выполнение в i-ю группу регистров 39, если i-й процессор свободен, где i = (1,п), а n — число процессоров. Через элемент. ИЛИ 38 разрешается загрузка следующего стека в группу регистров 39, соответствующую свободному процессору.

Загрузка стеков в регистровую память осуществляется следующим образом. На группу входов 45 подается информация о свободных процессорах в регистр 37. На группу входов 36, где

r x d количество входов, подается стек, каждый разряд по своему входу.

Затем этот стек подается на вторые входы элементов И 41 групп логических элементов И 40 следующим образом.

Каждый разряд подается на п элементов И 41, на один соответствующий элемент И 41 группы логических элементов И 40, т.е. на один элемент в каждой группе регистров 39. Это означает, что стек поступает на все группы регистров 39, но запишется в регистры 42 только в той группе, элементы И 41 которой будут открыты. С прямых выходов регистра 37 единица, готовности i-ro процессора поступает на первые входы всех элементов И 41, ! всех групп логических элементов И 40 принадлежащей i-й группе регистров . 39. А также единица готовности процессора поступает. Hà i-й вход элемента ИЛИ 38 и через него на вход 24 блока дешифрации и анализа признаков.

С инверсных выходов регистра 37 подается нулевой потенциал на все группы регистров 39 на третьи входы соответствующих элементов И 41 ° Это позволяет производить запись стеков в i-ю группу регистров 39, i =(1 n) с меньшим порядковым номером. В случае, если свободны сразу два или более процессоров, информация через элементы И 41 записывается в регистры 42 соответствующей группы регистров 39 ° В каждой группе регистров 39 содержится г регистров 42, имеющих

d входов, r групп логических элемен10053 6 тов И 40 по d элементов И 41 в каждой группе, Информация из регистров

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

ИЛИ 44 группы логических элементов

ИЛИ 43. Всего п элементов ИЛИ 44 по количеству групп регистров 39.и каждый элемент 44 имеет разрядность, равную d. Как только информация считалась в i-ю группу регистров 39, сигнал через схему ИЛИ 44 пошел на

i-й инверсный вход регистра 37, что будет означать, что загрузка в i-ю группу регистров. 39 произошла и -й процессор занят.

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

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

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

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

2f Т Z5 И фиг 7 выход совпадения признаков которого является выходом блока, вход запуска схемы опроса является входом запуска блока, выход схемы опроса соединен

5 с входом синхронизации узла хранения и сравнения признаков, информационный вход которого соединен с выходом дешифратора признаков, вход которого является первым информационным входом блока, информационный

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

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

1410053 410053

Составитель Е.Устинов

Редактор О.Спесивых Техред А.Кравчук Корректор М.Васильева

Подписное

Тираж 704 Заказ 3482/4б

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

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

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