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

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и)955078 Союз СоветскихСоциалистическихРеслубликОпубликовано 30.08.82. Бюллетень32Дата опубликования описания 30.08.82 хе делам кзебретеннй к еткрытий(72) Авторы изобретения Тбилисский научно-исследовательский инстит и средств автоматизации НПО(54) АССОЦИАТИВНЫЙ ЛАРА,ЛЛЕЛЬНЫЙ ПРОЦЕССОР 1Изобретение относится к вычислительной технике и может быть использовано для параллельной обработки массивов информации.Известен ассоциативный процессор, который содержит запоминающее устройство, логическое устройство и устройство управления 1.Известен также универсальный ассоциативный процессор на интегральных микросхемах, который содержит матрицу из однотипных элементов. Наращивание системы как по словам, так и по разрядам обеспечивается добавлением ассоциативных интегральных микросхем памяти по вертикали и горизонтали, Система представляет собой матричный процессор с распределенной логикой 2.Однако данные процессоры имеют недостаточно высокую производительность.Наиболее близким к предлагаемому по технической сущности является ассоциативный параллельный процессор, содержащий блок управления и ассоциативные процессорные элементы, каждый из которых содержит матрицу ассоциативных запоминающих элементов, входной и выходной регистры,коммутатор опроса, первую, вторую и третью группы элементов И по числу строк матрицы ассоциативных запоминающих элементов, при этом первый выход блока управления подключен к управляющим входам коммутатора опроса и первым входам элементов И первой, второй и третьей групп, выходы выходных регистров соединены с соответствующими информационными входами входных регистров, выходы которых подключены 1 Ок разрядным входам опроса и записи ассоциативных запоминающих элементов соответствующих столбцов матрицы. Разрядные выходы ассоциативных запоминающих элементов соединены с соответствующими входами выходного регистра, выходы элементов 15 И первой, второй и третьей групп подключены соответственно ко входам опроса ассоциативных запоминающих элементов соответствующей строки соседнего ассоциативного процессорного элемента и входам разрешения записи и считывания коммутатора опроса данного ассоциативного процессорного элемента, выходы опроса ассоциативных запоминающих элементов каждой строки матрицы соединены с соответствующими входами опроса коммутатора опроса данного3ассоциативного процессорного элемента, выходы опроса этого коммутатора подключены ко вторым входам соответствующих элементов И первой группы, выходы разрешения записи и считывания каждого коммутатора опроса соединены со входами разрешения записи и считывания ассоциативных запоминающих элементов соответствующих строк матрицы данного процессорного элемента и вторыми входами элементов И соответственно второй и третьей групп соседнего ассоциативного процессорного элемента 3.Однако данный процессор имеет- недостаточно высокую производительность из-за того, что ввод нового массива данных в ассоциативную матрицу и вывод из матрицы результатов происходит последовательно по словам, что занимает много времени, а также ограниченные функциональные возможности из-за ограничений по связям между матрицами. Цель изобретения - увеличение производительности процессора.Поставленная цель достигается тем, что в ассоциативный параллельный процессор, содержащий блок управления и ассоциативные процессорные элементы, каждый из которых содержит матрицу ассоциативных запоминающих элементов, входной и выходной регистры, коммутатор опроса, первую, вторую и третью группы элементов И по числу строк матрицы ассоциативных запоминающих элементов, при этом первый выход блока управления подключен к управляющим входам коммутаторов опроса и первым входам элементов И первой, второй и третьей групп, выходы выходных регистров соединены с соответствующими информационными входами входных регистров, выходы которых подключены к разрядным входам опроса и записи ассоциативных запоминающих элементов соответствующих столбцов матрицы данного ассоциативного процессорного элемента, разрядные выходы этих ассоциативных запоминающих элементов соединены с соответствующими входами выходного регистра данного ассоциативного процессорного элемента, выходы элементов И первой, второй и третьей групп подключены соответственно ко входам опроса ассоциативных запоминающих элементов соответствующей строки матрицы соседнего ассоциативного процессорного элемента и входам разрешения записи и считывания коммутатора опроса данного ассоциативного процессорного элемента, выходы опроса ассоциативных запоминающих элементов каждой строки матрицы соединены с соответствующими входами опроса коммутатора опроса данного ассоциативного процессорного элемента, выходы опроса этого коммутатора подключены ко вторым входам соответствующих элементов И первой группы данного ассоциативного процессорного элемента,4выходы разрешения записи и считывания каждого коммутатора опроса соединены со входами разрешения записи и считывания ассоциативных запоминающих элементов соответствующих строк матрицы данного ассоциативного процессорного элемента и вторыми входами элементов И соответственно второй и третьей групп соседнего ассоциативного процессорного элемента, введены два буферных запоминающих устройстваи выходной коммутатор, а каждый ассоциативный процессорный элемент содержит также четвертую и пятую группы элементов И, причем вход процессора подключен к первым входам буферных запоминающих устройств, управляющие входы которых соединены со вторым выходом блока управления, первые выходы буферных запоминающих устройств подключены к соответствующим входам выходного коммутатора, выход которого соединен с выходом процессора, первые входы элементов И четвертой и пятой групп подключены к первому выходу блока управления, выходы элементов И четвертой группы и вторые входы элементов И пятой группы соединены соответственно со входами разрешения записи и выходами опроса коммутатора опроса данного ассоциативного процессорного элемента, а выходы элементов И пятой группы и вторые входы элементов И четвертой группы подключены соответственно ко вторым входам и выходам буферных запоминающих устройств.зо Кроме того, блок управления содержитрегистр микрокоманд, генератор синхросигналов, накопитель микропрограмм, накопитель номеров микропрограмм, линию задержки, регистр номеров микрокоманд и дешифратор, причем выходы регистра микрокоманд соединены с первым и вторым выходами блокавходы регистра микрокоманд подключены к первым выходам накопителя микропрограмм, а управляющий вход регистра микрокоманд - к выходу генератора 40 синхросигналов, второй выход накопителямикропрограмм соединен со входом накопителя номеров микропрограмм, выход которого подключен ко входу линии задержки, выход линии задержки соединен со входом регистра номеров микрокоманд, выход ко торого подключен ко входу дешифратора,а выход дешифратора соединен со входом накопителя микропрограмм.При этом каждое буферное запоминающее устройство содержит входной регистр, выходной регистр, формирователь адресов строк и регистры сдвига по числу строк матрицы ассоциативных запоминающих элементов каждого ассоциативного процессорного элемента, причем первый вход устройства подключен ко входу входного регистра, выходы входного регистра соединены с информационными входами регистров сдвига, информационные выходы которых подключе= ны ко входам выходного регистра, управляющие входы - к выходам формирователя адресов строк, а последовательные входы и выходы - соответственно ко вторым входам и выходам устройства, управляющий вход устройства соединен со входом формирователя адресов строк, а выход выходного регистра - с первым выходом устройства.На фиг. 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 -25 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 соединены со входами раз решения записи и считывания элементов 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 соединены с первым . и вторым 8 выходами блока 1. Входы регистра 13 подключены к первым входам накопителя 15, а управляющий вход регистра 13 - к выходу генератора 14. Второй выход накопителя 15 соединен со входом накопителя 16, выход которого подключен ко входу линии 7 задержки, выход линии 17 задержки соединен со входом регистра 18. Выход регистра 8 подключен ко входу дешифратора 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 вырабатывается единичный сигнал, если на этот разряд наложена маска или когда информация, содержащаяся в триггере, 9550785 1 О 15 20 совпадает со входной информацией, поступающей от одноименного разряда регистра опроса, входящего в состав регистра 2.2. Ввод новых данных в процессор осуществляется по входу 6 в одно из буферных устройств 3 в зависимости от сигналов на входе 7 устройства. Другое буферное устройство 3 в это время может выдавать информацию. Буферные запоминающие устройства выполнены на универсальных сдвиговых регистрах 23, которые могут принимать или выдавать К-разрядные слова по информационным входам и выходам последовательно по словам и параллельно по разрядам, а по последовательным входам и выходам - последовательно по разрядам и параллельно по словам группами по гп слов. Ввод и вывод по информационным входам и выходам массива данных занимает т тактов, а ввод- вывод по последовательным входам и выходам - К тактов, причем а ) К, где т = 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,1 настраиваются на реализацию заданного алгоритма. На втором этапе проводится одновременное выполнение задач в предварительно настроенных строках элементов 2.1 и операции по обмену данными. Настройка сводится к записи в отдельные строки элементов 2.1 признаков типов вычислений, обеспечивающих реализацию в этих строках заданного множества операций, которое определяется заданным адгоритмом решаемых в этих строках задач, а также к записи признаков типа связей, обеспечивающих 25 30 35 40 45 50 55 пересылки чисел между отдельными строками матрицы элементов 2.1, или между матрицами и устройствами 3, или между устройствами 3 и внешним вычислительным устройством в соответствии с алгоритмами решаемых задач.Благодаря введенным блокам и связям можно организовать независимую работу всех матриц, выполняя одновременно в разных матрицах различные операции, например обработку данных, процедуры пересылок внутри матриц, ввод новых массивов данных в одно из устройств 3, вывод полученных результатов из другого устройства 3, или же организовывая различные комбинации связей матриц и устройств 3, реализовать по- точное выполнение вычислительного процесса и обмена данными,Предлагаемый процессор может быть использован при решении задач типа быстрого преобразования Фурье, распознавания образов, решении дифференциальных уравнений, расчета корреляционной фнкции, управления воздушным движением и т. п. Формула изобретения1. Ассоциативный параллельный процессор, содержащий блок управления и ассоциативные процессорные элементы, каждый из которых содержит матрицу ассоциативных запоминающих элементов, входной и выходной регистры, коммутатор опроса, первую, вторую и третью группы элементов И по числу строк матрицы ассоциативных запоминающих элементов, при этом первый выход блока управления подключен к управляющимвходам коммутаторов опроса и первым входам элементов И первой, второй и третьей групп, выходы выходных регистров соединены. с соответствующими информационными входами входных регистров, выходы которых подключены к разрядным входам опроса и записи ассоциативных запоминающих элементов соответствующих столбцов матрицы данного ассоциативного процессорного элемента, разрядные выходы этих ассоциативных запоминающих элементов соединены с соответствующими входами выходного регистра данного ассоциативного процессорного элемента, выходы элементов И первой, второй и третьей групп подключены соответственно ко входам опроса ассоциативных запоминающих элементов соответствующей строки матрицы соседнего ассоциативного процессорного элемента и входам разрешения записи и считывания коммутатора опроса данного ассоциативного процессорного элемента, выходы опроса ассоциативных запоминающих элементов каждой строки матрицы соединены с соответствующими входами опроса коммутатора опроса данного ассоциативного процессорного элемента, выходы опроса этого коммутатора подключены ко вторым входам соот9ветствующих элементов И первой группы данного ассоциативного процессорного элемента, выходы разрешения записи и считывания каждого коммутатора опроса соединены со входами разрешения записи и считывания ассоциативных запоминающих элементов соответствующих строк матрицы данного ассоциативного процессорного элемента и вторыми входами элементов И соответственно второй и третьей групп соседнего ассоциативного процессорного элемента, отличающийся тем, что, с целью увеличения производительности процессора, он содержит два буферных запоминающих устройства и выходной коммутатор, а каждый ассоциативный процессорный элемент содержит также четвертую и пятую группы элементов И, причем вход процессора подключен к первым входам буферных запоминающих устройств, управляющие входы которых соединены со вторым выходом блока управления, первые выходы буферных запоминающих устройств подключены к соответствующим входам выходного коммутатора, выход которого соединен с выходом процессора, первые входы элементов И четвертой и пятой групп подключены к первому выходу блока управления, выходы элементов И четвертой группы и вторые входы элементов И пятой группы соединены соответственно со входами разрешения записи и выходами опроса коммутатора опроса данного ассоциативного процессорного элемента, а выходы элементов И пятой группы и вторые входы элементов И четвертой группы подключены соответственно ко вторым входам и выходам буферных запоминающих устройств.2. Процессор по п. 1, отличающийся тем, что блок управления содержит регистр микрокоманд, генератор синхросигналов, накопитель микропрограмм, накопитель номеров микропрограмм, лини,о задержки, регистр номеров микрокоманд и дешифратор, причем 10выходы регистра микрокоманд соединеныс первым и вторым выходами блока, входырегистра микрокоманд подключены к первымвыходам накопителя микропрограмм, а управляющий вход регистра микрокоманд -к выходу генератора синхросигналов, второйвыход накопителя микропрограмм соединенсо входом накопителя номеров микропрограмм, выход которого подключен ко входулинии задержки, выход линии задержкисоединен со входом регистра номеров микро 10 команд, выход которого подключен ко входудешифратора, а выход дешифратора соединен со входом накопителя микропрограмм.3. Процессор по и. 1, отличающийся тем,что каждое буферное запоминающее устроиство содержит входной регистр, выходной5регистр, формирователь адресов строк ирегистры сдвига по числу строк матрицыассоциативных запоминающих элементовкаждого ассоциативного процессорногозапоминающего элемента, причем первый20 вход устройства подключен ко входу входного регистра, выходы входного регистрасоединены с информационными входамирегистров сдвига, информационные выходыкоторых подключены ко входам выходногорегистра, управляющие входы - к выходам2 формирователя адресов строк, а последовательные входы и выходы - соответственноко вторым входам и выходам устройства,управляющий вход устройства соединен совходом формирователя адресов строк, а30выход выходного регистра - с первым выходом устройства.Источники информации,принятые во внимание при экспертизе1. Патент Великобритании1323612,кл. б 06 Г 13(00, 1973.2. Патент США3757312,кл. б 11 С 15/00, 1973,3. Авторское свидетельство СССР479114, кл. б 06 Г 15/00, 1975., г, Ужгород, ул. ВНИИПИ Госуда по делам и 113035, Москва, Ж илиал ППП Патент