Ассоциативный параллельный процессор

 

О П И С А Н И Е (1955078

ИЗОБРЕТЕН ИЯ

Союз Советских

Социалистических

Реслублик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 25.11.80 (21) 3231798/!8-24 с присоединением заявки №вЂ” (51) М. Кл.з

G 06 F 15/00

Гаеуюрстееккый кеиитет (23) Приоритет—

СССР (53) УДК 681.325 (088.8) Опубликовано 30.08.82. Бюллетень № 32

Дата опубликования описания 30.08.82

eo aemw кзебретеннй к еткрытий (72) Авторы изобретения

Д. А. Тодуа, Т. А. Клдиашвили, Г. А. Бакши, В. К. Хачатуров, Н. H. Шабурова, Н. А. Шемягин, О. Е. Жуковская и Г. М.: Попова :

Тбилисский научно-исследовательский инстит и средств автоматизации НПО « (71) Заявитель (54) АССОЦИАТИВНЫЙ ЛАРА,ЛЛЕЛЬНЫЙ ПРОЦЕССОР

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

Известен ассоциативный процессор, который содержит запоминающее устройство, логическое устройство и устройство управления (1) .

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

Однако данные процессоры имеют недостаточно высокую производительность.

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

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

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

955078

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

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

Цель изобретения — увеличение производительности процессора.

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

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

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

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

40 синхросигналов, второй выход накопителя микропрограмм соединен со входом накопителя номеров микропрограмм, выход которого подключен ко входу линии задержки, выход линии задержки соединен со входом регистра номеров микрокоманд, выход ко4 торого подключен ко входу дешифратора, а выход дешифратора соединен со входом накопителя микропрограмм.

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

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

Ассоциативный параллельный процессор !

5 содержит блок 1 управления и ассоциативные процессорные элементы 2 (фиг. 1). Каждый из элементов 2 содержит матрицу ассоциативных запоминающих элементов 2.1, входной регистр 2.2, выходной регистр 2.3, коммутатор 2.4 опроса, первую, вторую и третью группы 2.5 — 2.7 элементов И по числу строк матрицы элементов 2.1 (фиг. 2). При этом первый выход 1.1 блока 1 подключен к управляющим входам коммутаторов 2.4 и первым входам элементов И групп 2.5—

2.7, выходы регистров 2.3 соединены с соответствующими входами регистров 2.2, выходы которых подключены к разрядным входам 2.8 опроса и разрядным входам 2.9 записи элементов 2.1 соответствующих столбцов матрицы данного элемента 2. Разрядные выходы 2.10 элементов 2.1 соединены с соответствующими входами регистра 2.3 данного элемента 2, выходы элементов И групп 2.5—

2.7 подключены соответственно ко входам

2.11 опроса элементов 2.1 соответствующей строки матрицы соседнего элемента 2 и вхо- з5 дам 2.12 и 2.13 разрешения записи и считывания коммутатора 2.4 данного элемента 2.

Выходы 2.14 опроса элементов 2.1 каждой строки матрицы соединены с соответствующими входами опроса коммутатора 2.4 данного элемента 2, выходы 2.15 опроса этого коммутатора подключены ко вторым входам соответствующих элементов И группы 2.5 данного элемента 2. Выходы 2.16 и 2.17 разрешения записи и считывания каждого коммутатора 2.4 соединены со входами раз- 45 решения записи и считывания элементов 2.1 соответствующих строк матрицы данного элемента 2 и вторыми входами элементов И групп 2.6 и 2.7 соседнего элемента 2. Кроме того, процессор содержит два буферных запоминающих устройства 3 и выходной коммутатор 4, а каждый элемент 2 содержит четвертую и пятую группы 2.18 и 2.19 элементов И, причем вход 5 процессора подключен к первым входам 6 устройств 3, управляющие входы 7 которых соединены

55 со вторым выходом 8 блока 1 управления.

Первые выходы 9 устройств 3 подключены к соответствующим входам выходного ком6 мутатора 4, выход которого соединен с выходом 10 процессора. Первые входы элементов И групп 2.18 и 2.19 подключены к первому выходу 1.1 блока 1. Выходы элементов

И группы 2.18 и вторые входы элементов И группы 2.19 соединены соответственно со входами 2.12 и выходами 2.15 коммутатора

2.4 данного элемента 2, а выходы элементов И группы 2.19 и вторые входы элементов И группы 2.18 подключены соответственно ко вторым входам 11 и вторым выходам 12 устройств 3.

Блок 1 содержит (фиг. 1) регистр 13 микрокоманд, генератор 14 синхросигналов, накопитель 15 микропрограмм, накопитель

16 номеров микропрограмм, линию 17 задержки, регистр 18 номеров микрокоманд и дешифратор 19. Выходы регистра 13 соединены с первым 1.1 и вторым 8 выходами блока 1. Входы регистра 13 подключены к первым входам накопителя 15, а управляющий вход регистра 13 — к выходу генератора 14. Второй выход накопителя 15 соединен со входом накопителя 16, выход которого подключен ко входу линии !7 задержки, выход линии 17 задержки соединен со входом регистра 18. Выход регистра 18 подключен ко входу дешифратора 19, а выход дешифратора соединен со входом накопителя 15.

Каждое буферное запоминающее устройство 3 содержит входной регистр 20, выходной регистр 21, формирователь 22 адресов строк и регистры 23 сдвига по числу строк матрицы элементов 2.1 каждого процессорного элемента 2 (фиг. 3). Первый вход 6 устройства 3 подключен ко входу регистра 20, выходы которого соединены с информационными входами регистров 23. Информационные выходы регистров 23 подключены ко входам регистра 21, управляющие входы— к выходам формирователя 22, а последовательные входы и выходы — соответственно ко входам 11 и выходам !2 устройства 3.

Управляющий вход 7 устройства 3 соединен со входом формирователя 22, а выход регистра 21 — с первым выходом 9 устройства 3.

Коммутатор 2.4 (фиг. 4) содержит запоминающие элементы (в данном случае триггеры) 24 по количеству строк матрицы элементов 2.1, элементы И 25, мультиплексоры 26, элементы И 27 и линии 28 задержки.

Ассоциативный параллель ь|й процессор работает следующим образом.

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

2.1 вырабатывается единичный сигнал, если на этот разряд наложена маска или когда информация, содержащаяся в триггере, 955078

1О

l5

20 совпадает со входной информацией, поступающей от одноименного разряда регистра опроса, входящего в состав регистра 2.2.

Ввод новых данных в процессор осуществляется по входу 6 в одно из буферных устройств 3 в зависимости от сигналов на входе

7 устройства. Другое буферное устройство 3 в это время может выдавать информацию.

Буферные запоминающие устройства выполнены на универсальных сдвиговых регистрах 23, которые могут принимать или выдавать К-разрядные слова по информационным входам и выходам последовательно по словам и параллельно по разрядам, а по последовательным входам и выходам — последовательно по разрядам и параллельно по словам группами по m слов. Ввод и вывод по информационным входам и выходам массива данных занимает m тактов, а вводвывод по последовательным входам и выходам — К тактов, причем m >) К, где

m = 500 — 1000 и К = 8 — 16. Введение групп 2.!8 и 2.19 элементов И позволяет объединять элементы 2.1 в группы, первую со второй, третьей и т. д., а также организовывать совместную работу каждого устройства 3 с любой матрицей через вторые входы и . выходы буферных запоминающих устройств 3, коммутируемые введенными группами элементов И. На входы 2.9 опроса из регистров 2.2 к элементам 2.1 подается число, которое содержит код опроса. По коду опроса находятся строки, содержащие заданный набор признаков. При этом с выходов 2.16 и 2.17 коммутатора 2.4 на входы разрешения записи или разрешения считывания элементов 2.1 выбранной строки поступает единичный сигнал. Подавая на входы опроса и записи в определенной последовательности коды ассоциативных слов, можно выполнять групповые арифметические и логические операции параллельно над парами чисел, размещенных в отдельных строках матрицы элементов 2.1 и производить последовательно по словам считывание чисел из матрицы в регистры 2.3 с последующей передачей этих слов в любую другую или в свою же матрицу элементов 2.! (перестановка слов).

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

З0

55 пересылки чисел между отдельными строками матрицы элементов 2.1, или между матрицами и устройствами 3, или между устройствами 3 и внешним вычислительным устройством в соответствии с алгоритмами решаемых задач.

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

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

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

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

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

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

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

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

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

10 выходы регистра микрокоманд соединены с первым и вторым выходами блока, входы регистра микрокоманд подключены к первым выходам накопителя микропрограмм, а управляющий вход регистра микрокоманд— к выходу генератора синхросигналов, второй выход накопителя микропрограмм соединен со входом накопителя номеров микропрограмм, выход которого подключен ко входу линии задержки, выход линии задержки соединен со входом регистра номеров микроip команд, выход которого подключен ко входу дешифратора, а выход дешифратора соединен со входом накопителя микропрограмм.

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

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

Источники информации, принятые во внимание при экспертизе

1. Патент Великобритании № 1323612, кл. G 06 F 13/00, 1973.

2. Патент США № 3757312, кл. G 11 С 15/00, 1973.

3. Авторское свидетельство СССР № 479114, кл. G 06 F 15/00, 1975.

955078

11

1Я (pub. У с

ЕЧ (!

1! ( (1 (I

Составитель Г. Виталиев

Редактор Ю. Ковач Техред А. Бойкас Корректор О. Билак

Заказ 6171/54 Тираж 731 Подписное

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

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

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4