Устройство для асинхронной ассоциативной загрузки многопроцессорной вычислительной системы Советский патент 1988 года по МПК G06F15/16 

10

15

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

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

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

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

Блок дешифрации и анализа признаков содержит дешифратор признаков 1, включающий регистр шифра признака 2, дешифратор 3 и буферный регистр Цри- 25 знака 4, схему опроса 5, состоящую из блока 6 генератора тактовых импульсов, логического элемента И 7 и регистра 8 циклического сдвига, узел хранения и сравнения признаков 9, CLO-эп Держащий га групп регистров хранения признаков lOj. по К регистров 11 в каждой группе, модуль счета 12,включающий m X К групп счета 13, вклю- 1 чающих., в свою очередь, счетчик с ... . .

20

тановочными входами 14, элемент РШИ 15, RS-триггер 16, модуль сравнения

17,содержащий m х К групп сравнения

18,включающих схему сравнения 19 и логический элемент И 20, входы/выходы 21-25.

Блок стековой памяти состоит из группы регистров 26, содержащих m групп регистров хранения стеков 27, по г регистров хранения 28 в каждом группы элементов И 29, включающей m X г групп логических .элементов И 30 по d элементов в каждой группе 31, группы элементов ИЛИ 32, содержащей г групп логических элементов ИЛИ 38 по г элементов ШШ 34 в каждой группе, входов/выходов 35 и 36.

Блок регистровой памяти содержит регистр готовности процессоров 37, логический элемент ИЛИ 38 на п входов и п групп регистров памяти 39, включающих г х п групп логических элементов И 40 по d элементов И 41 в каждой группе, и г регистров 425груп35

40

45

50

55

0

5

5 п

0

5

0

5

0

5

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

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

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

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

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

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

в входную шину 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. На установочные ВХОДВ1 счетчика 14 поступит число использования данного признака в программе в обратном коде. Число, поступившее на. установочные входы рчетчика 14, через элемент ИЛИ 15, разрядность которого равна разряд- ности счетчика 14, установит RS-триг гер 16 в единичное положение, который будет держать 1 на первом входе соответствующего элемента И 20. Генератор тактовых импульсов 6 схемы опроса 5 выдает тактовый импульс на регистр циклического сдвига 8 че- рез элемент И 7, который открывается 1, поступившей из блока регистровой памяти. Тактовьй импульс сдвигает записанную 1 в регистре циклического сдвига 8, и она подается на каждый элемент И 20 группы срав- . нения 18. Один из элементов И 20, на входе которого все 1, выдает

j 0 5 0 5

0

5

0

5

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

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

Поразрядное параллельное считьша- ние стека происходит следуюш 1м образом, 1 сравнившихся признаков из блока дешифрации и анализа признаков поступает на соответствующий вход группы входов 25 и подается на первые входы всех элементов И 31 г групп логических элементов И 30, оснося- щихся к одной группе регистров хранения стеков 27. Каждая группа регистров хранения стеков 27 содержит один стек. Стек записывается в регистры хранения 28 через программный вход устройства 35, а на вторые входы всех элементов И 31 г групп логическ их эле- элементов И 30 подается инфдрмация из одной группы регистров хранения стеков 27, Т,е. происходит считывание требуемого стека из регистров 28 через элементы И 31, причем информация из одного регистра 28 считывается через одну группу логических элементов И 30, Всего в считьшании одного стека принимает.участие г k d элементов И 31, где d - число разрядов регистра 28, т.е, каждый разряд считывается через свой элемент И 31 и через свой элемент ИЛИ 34, которых в блоке всего г х d, т,е, один эле- мент на соответствующий разряд. Каждый элемент ИЛИ 34 имеет m входов по числу стеков или групп регистров хранения стеков 27. Каждый логический элемент ИЛИ 34 соединен с j-м разрядом, (j 1, d) всех групп реги- стров хранения стеков 27 через логические элементы И 31, Всего в схеме логических элементов ИЛИ 32 находится г групп логических элементов ИЛИ 33 по числу регистров 28 в каждой группе регистров хранения стеков 27 и d элементов ИЛИ 34 в каждой группе 33. Таким образом, получается поразрядное параллельное считывание стека в выходную шину блока стековой памяти, каждый j-й разряд стека поступает на j-й выход группы выходов 36, где j (1, г X d).

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

Загрузка стеков в регистровую память осуществляется следующим образом. На группу входов 45 подается информация о свободных процессорах в регистр 37. На группу входов 36, где г X d количество входов, подается стек, каждый разряд по своему входу. Затем этот стек подается на вторые входы элементов И 41 групп логических элементов И 40 следующим образом. Каждый разряд подается на п элементов И 41, на один соответствующий элемент И 41 группы логических элементов И 40, т.е. на один элемент в каждой группе регистров 39. Это означает, что стек поступает на все группы регистров 39, но запишется в регистры 42 только в той группе, элементы И 41 которой будут открыты. С прямых выходов регистра 37 единица готовности i-ro процессора поступает

на первые входы всех элементов И 41,

всех групп логических элементов И 40 принадлежащей i-й группе регистров

39. А также единица готовности процессора поступает на i-й вход элемента ИЛИ 38 и через него на вход 24

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

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

Q процессор занят.

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

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

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

5

0

5

0

5

714

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

100538

3. Устройство по п.

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

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

элементов ИЛИ группы, выходы которых являются выходом блока.

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

21 22 75 35

45

г

/7o/i eu/i/- poifau а

/7pt/3HCff(ff

2

4

Ъ6

&/7C7/

/aesacmf ffSffti гтамяти

uo

B

фиг. 1

Фаг2

- Qoo25

Ы

l/g.3