Ассоциативный матричный процессор

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскикСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(61) Дополнительное к авт. свид-ву(22) Заявлено 02.09.81 (21) 3348227/18-24 Р 11 М Кл з 606 Р 15/00 с присоединением заявки Нов Государственный комитет СССР ио делам изобретений и открытийДата опубликования описания 150383 4) АССОЦИАТИВНЫИ ИАТРИЧНЫИ ПРОЦЕССО вычислиь испольаботки ин тел зов фор нформации прх элементах хо ем. Изобретение относится кьной технике и может бытано для параллельной обрмацки.Известен ассоциативный матричныйпроцессор, содержащий три матрицы ассоциативной памяти, выполненные на специальных ассоциативных запоминающих элементах, местное устройство уп равления внешнее устройство управления и входные устройства с регистрами опроса, записи н считывания 1.Однако в настоящее время подобные процессоры не находят практическогоприменения из-за дороговизны специальных элементов, громоздкости ассоциативной памяти, а значит и всего процессора, и большой потребляемой мощности.Известен также ассоциативный ма. тричный процессор, который содержит устройство управления, блок параллельного ввода-вывода, ассоцйативный матричный модуль, содержащий матрицу памяти, обрабатывающие элементы на каждую строчку памяти, перестановочную сеть мультиплексор - блок коммутации 21.Преобразование и оис - дит в обрабатывающи пут,последовательного вынесения разрядного среза из матрицы памяти. Выборкаразрядного среза осуществляется с помощью сложной перестановочной сети,составляющей 80 стоимости матрицыпамяти,Недостатком данного процессора является необходимость передачи информации как в режиме записи в память,так и в режиме выборки через сложнуюперестановочную сеть, что приводит кзначительному снижению быстродействияпроцессбра, а также и надежности процессора в целом, так как перестановочная сеть состоит из большого количества элементов.Цель изобретения - сокращение объема оборудования и повышение произво 20 днтельности процессора.Поставленная цель достигается тем,что в ассоциативный матричный процессор, содержащий блоки памяти, арифметико-логические блоки по.числу бло-фков памяти,. блок управления , входной и выходной блоки коммутаторов,причем выходы блоков памяти соединеныс информационными входами соответствующих арифметико-логических блокови информационными входами входногоблока коммутаторов, введены первыйТираж 704 И Государственного делам изобретейий 5, Москва, Ж, Р одписно омитета ССС открытийущская наб 4/5 130 илиал ППП ффПатентф, г. ужгород, ул. Проектная, 4 Составитель Г, ВиталиевРедактор Л. Алексеенко Техред М,теперКорректор Е,Рошкои второй блоки буферной памяти и. две группы коммутаторов, общее число которых равно числу блоков памяти, при этом первые и вторые информационные входи блоков буферной памяти подключены соответственно к информационному 5 входу процессора и выходу входного блока коммутаторов, первые информационные выходы первого и второго блоков буферной памяти соединены соответственно с первым и вторым информацион ными входами выходного блока коммутаторов, выход которого подключен к информационному выходу процессора, вторые информационные выходы первого и второго блоков буферной памяти соеди нены с первыми информационными входа-, .ми коммутаторов соответственно первой и второй групп, вторые информационные входы коммутаторов подключены к информационным выходам соответствующих арифметико-логических блоков, а выходы этих коммутаторов соединены с управляющими входами соответствующих блоков памяти, первый вход и выход пеРеноса каждого арифметико-логического блока подключены соответственно к второму выходу и входу переноса соседнего арифметико-логического блока, а первый, второй, третий, четвертый, пятый, щестой и седьмой выходы блока управления соединены соответственно с управляющими входами блока коммутаторов, первого и второго блоков буферной памяти и коммутаторов первой и.второй групп, адресными входами блоков памяти и управляющими входами 35 арифметико-логических блоков и выходного блока коммутаторов.При этом блок управления содержит генератор синхросигналов, регистр достояния, память управляющих команд, 40 .память микрокоманд, регистр управляющих команд, регистр микрокоманд, две . группы элементов И; группу элементов ИЛИ, дешифратор и три элемента И, причем первый и второй выходы регист ра состояния соединены соответственно с первыми входами элементов И пер-. вой группы и входом генератора синхросигналов, ервые входы элементов И второй группы подключены к первому выходу регистра управляющих команд, второй выход которого соединен с входом памяти микрокоманд, вторые входы элементов И первой и второй групп подключены соответственно к первому и второму выходам генератора синхросигналов, третий, четвертый и.пятый выходы которого соединены соответственно с управляющими входами регистра управляющих команд, регистра микрокоманд и первыми входами первого, вто- бО ,рого и третьего элементов И, первые и вторые входы элементов ИЛИ группы подключены к выходам элементов И соответственно первой и второй групп,а их выходы соединены с входом памяти управляющих команд, выходы памяти микрокоманд и памяти управляющих команд подключены к информационнымвходам соответственно регистра микрокоманд и регистра управляющих команд,первый, второй, третий, четвертый,пятый, шестой и седьмой выходы ре"гистра микрокоманд соединены соответ.ственно с первым выходом блока, вторыми входами первого и второго эле-ментов И, четвертым выходом блока,входом дешифратора, вторым входомтретьего элемента Й и седьмым выходом блока, а выходы первого, второго,и третьего элементов И подключенысоответственно к второму, третьему ишестому выходам блока.На фиг.1 приведена структурнаясхема ассоциативного матричного процессора; на фиг.2 вфункциональныесхемы блоков буферной памяти и комму.таторов; на фиг.З - разбиение коммутаторов на нечетные и четные группыс целью подключения их к регистрамблоков буферной памяти; на фиг.4принципиальная схема выходного блокакоммутаторов; на фиг.5 - функциональная схема блока управления; на фиг.бпринципиальная схема арифметико-логического блока; на фиг.7 - таблица истинности арифметико-логического блока,Процессор содержит (фиг.1) матрицупамяти, состоящую из ю блоков 1 - 3(оперативной) памяти с произвольнымдоступом, арифметико-логические блоки 2 - 2, блок 3 управления, входной блок 4 коммутаторов, выходнойблок 5 коммутаторов, первый и второйблоки б и 7 буферной памяти, коммутаторы 8 - 8 р. Вход 9 процессора,имеющий и разрядов, соединен с параллельными входами блоков б и 7 буферной памяти, параллельные выходы которых соединены с соответствующимивходами выходного блока 5 коммутаторов, а последовательные выходи - скоммутаторами 8 А - 8 я, сгруппированными определенным образом в нечетныеи четные группы по и коммутаторов вкаждой группе (фиг,З), последовательные входы блоков б и 7 соединены свыходами входного блока 4 коммутаторов. Выход каждого коммутатора 8 соединен с информационным входом соответствующего блока 1 памяти, выходкоторого соединен с соответствующимблоком 2 и информационным входом бло.ка 4 коммутаторовПервые вертикальные вход и выход каждого блока 2 подключены соответственно к вторым вер.тикальным выходу и входу предыдущегоблока З,а первые вертикальные вход ивыход блока 2( соединены соответственно с вторым вертикальным выходоми входом блока 21. Горизонтальный выход первого и последнего блоков 2 соединены соответственно с одним из1005065 та НЕ 27, а вторые входы вторых элементов И 25, а также вход элемента НЕ 27 объединены и подключены к выходу 16 у управляющего выхода 16 блока 3. Управляющие входы всех ком" мутаторов 22( - 22 н, 23 - 23 в объединены и подключены к управляющим выходам 16 - 16, где Ф=Вор и Выходы элементов 24 и 25 всех. групп подключены к входам элементов 26, выходы которых являются выходами 17( 17), блока 5.Блок 3 управления (фиг.5) состоит из узла 30 микропрограммного управления, генератора 31 синхросигналов.и регистра состояния 32, причем узел 30 входов первого и последующего коммутаторов 8. Управляющие входы всех блоков процессора соединены с выходами 10-16 блока 3 управления. Выход 17 выходного блока 5 коммутаторбв являет, ся выходом процессора. 5Каждый из блоков 6 и 7 буферной памяти состоит (фиг,2) соответственно из регистров 64 - бпи 7 - 7 и сдвига, количество и разрядность которых определяются разрядностью входа 9 про цессора. При этом параллельные входы регистров 6 - 6 и 74 - 7 в объединены и являются параллельными входами Э - 9 и процессора.Коммутаторы 8 - 8 щ (фиг.2) содер жат элемент НЕ 18, два элемента И 19 и 20,элемент ИЛИ 21,вхбпы которого соединены с выходами элементов 19 и 20, Вторые входы элементов 19 всех коммутаторов 8 подключены к выходу 13 блока 3 управления, к которому через элементы 18.также подключены первые входы элементов 20 всех коммутаторов, Первые входы элементов 19 всех первых и последующих коммутаторов нечет ных групп, например 8 - 8, 81 н+4 8 и т.д.,объединены и подключены последовательному выходу соответст" венно первого и последующего регистров сдвига.блока 6,например входы коммутаторов 88 + и т.д. объединены и подключены к последовательному выходу регистра 6,.Аналогично подключаются первые входы элементов 19 коммутаторов четных групп к регистрам.сдвига блока 7, например входы коммутаторов 8 я+,(,8 я85 п+4 .и т.д.объединены и подключены к последовательному выходу регистра 7.,Второй вход элемента 20 каждого коммутатора 8 подключен к горизонтальному выходу соотО ветствующего блока 2. микропрограммного управления содержит память 33 управляющих команд, память34 микрокоманд, регистр 35 управляющих команд, регистр 36 микрокоманд,группы логических элементов, каждаяиз которых состоит из двух элементовИ 37 и 38 и одного элемента ИЛИ 39,и дешифратор 40. При этом входы элементов ИЛИ ЗЭ подключены к выходамэлемевтов И 37 и 38, а выходы - кадресным входам, памяти 33,выход которой подключен к информационным входам регистра 35. Первая группа выхо-дов этого регистра подсоединена кадресным входам памяти 34, а втораяк первым входам вторых элементов 38всех групп. Первые входы всех элемен тов 37 подключены к первой группе вы.;ходов регистра 32, а вторая группа его выходов подключена к входу генератора.31, к четырем выходам которого соответственно подключены вторыевходы элементов 37 и 38 всех групп нуправляющие входы регистров 35 и 36.Информационные входы регистра 36 подключены к выходу памяти 34. Пятаягруппа выходов регистра 36 подключенак входу дешифратора 40. Все выходы регистра 36, за исключением пятойгруппы выходов и последнего выхода,выходы дешифратора 40, а также пятыйвыход генератора 31 являются выходами 10 - 16 блока 3 управления. Арифметико-логический блок 2и 43, элемент ИЛИ 44, триггеры 45,46и 47, арифметико-логический модуль 48, горизонтальные входную ивыходную шины 49 и 50. Входыэлемента 44 подключены к выхоМам элементов 41, 42 и 43, первыевходы которых подсоединены соответственно к вертикальной входной шине 51,горизонтальной входной шине 49 и вер"тикальной входной шине 52, а вторыевходы - соответственно к выходам 1515 ъ и 153 блока 3 управления. Модуль 48 имеет входы 53 - 61 и выходы 62 и 63. Входы 53, 55 и 57 модуля 48 объединены и подключены к выходу 154 блока 3, а объединенные вхоВыходной блок 5 коммутаторов (Фиг.4) содержит две группы коммутаторов 22) - 22и 234 - 23 Н, И групп логических элементов, каждая из кото-. рых состоит из двух элементов И 24 и 25 и одного элемента ИЛИ 26, и эле- .мент НЕ 27.При этом одноименные информационные входы первой группы комму" таторов 22. - 22 и через входные ин- О формационные шинй 28 - 28 подключены к параллельным выходам соответ-. ствующих регистров 6 - 6 я блока 6, а одноименные информационные входы второй группы коммутаторов 23 - 23 в .55 через входные информационные шины 294 - 29 подключены к параллельным выходам соответствующих регистров 7 М - 7 д блока 7. Выходы первой и второй групй коммутаторов подключены 60 соответственно к первым входам первых "и вторых элементов И 24 и 25 всех групп :логических элементов., в которых. вторые входы первых элементов И 24 объединены и подключены к выходу элемен-уды 54, йб и 58 подключены к выхо ду 15 блока 3. Вход 59 модуля 48 объ.единен с входом триггера 45 и подсоединен к выходу элемента 44, вход 60к выходу триггера 45, а вход 61 - квыходу триггера 47. Входы триггеров46 и 47 соответственно подключены квыходам 62 и 63 модуля 48, управляющиевходы 64 - 68 которого подключены соответственно к выходам 156 - 15 рблока 3. Выходы 15, . - 15 блока 3 10подключены соответственно к управляющим входам триггеров 45, 46 и 47. Выход триггера 46 подсоединен к первойи второй вертикальным выходным шинами к шине 50 блока 21 В5функционирование ассоциативногоматричного процессора осуществляетсяследующим образом,Ввод И-разрядных слов в матрицупамяти осуществляется через два блока б и 7, причем вначале с управляющего выхода 11 блока 3 на все регистры блока б подается кодовая комбинация, которая настраивает их на режимпараллельного приема. За пеРвые Итактов осуществляется последовательное занесение И-разрядной информацииВ И РегистРов б - би, В это вРемЯ изблока 3 в регистры блока 7 по выходу 12 поступает кодовая комбинация,которая в течение первых .И тактовудерживает эти регистры в режиме хранения. По истечении итактов управляющие сигналы с выходов 11 и 12 блока 3переводят регистры блока 6 в режимпоследовательного сдвига, а регистры 35блока 7 - в режим параллельногозанесения. Так чередуются заполнение регистров блока б и считывание из регистров блока 7, а затем - считываниеиз блока б и заполнение блока 7. Информация, считываемая иэ регистровблока б, передается в соответствующие и коммутаторов одновременно всехнечетных групп, например 81 - 8 и,8 и+ - 8, а из регистров блока 7 - 45в соответствующие и коммутатороводновременно всех четных групп, например 8 +л - 82 р, 8+ - 8 ц.Сигнал лог.,еской 11 на выходе 13 блока 3 разрешает прохождениеинформации из блоков б и 7 через коммутаторы 8 в блоки 1. При этом вовсех блоках 1 происходит выборка одинаковых адресов в соответствии с Кразрядной, где К=90 р у Р-разрядностьячейки памяти, кодовой комбинацней,поступающей с выхода 14 блока 3. Запись информации в соответствующуюгруппу из И блоков 1 происходит строго в соответствии с управляющими сигналами на том же выходе 14, 60Таким образом каждое И-разрядноеслово, записанное за один такт в регистры сдвига, заносится в соответствующий блок 1 последовательно поразрядам за И тактов. Но так как за 65 грузка происходит одновременно вблоков 1, то эа эти И тактов происходит ввод и слов в матрицу памяти. Взависимости от разрядности блока 1можно организовать одну, две или бо-лее эон. Обычно вводится одновременно 16 или 32 разряда, а в качествеблока 1 берется блок оперативной памяти с произвольной выборкой на 256или более бит разрядностью в одинбит. Так можно организовать многозонную матрицу памяти. Обработка информации, хранящейся в матрицах памяти,осуществляется в блоках 2, в которыхнабор арифметических и логическихопераций определяется модулем 48. Вкачестве модуля 48 применяется серийно выпускаемая микросхема К 155 ИПЗ,предназначенная для логической и арифметической обработки двух четырехразрядных операндов. Однако с целью органиэации однобитовых (одноразрядных):арифметических операций три младшихего входа 53, 55 и 57 одного операндаобъединены и подключены к выходу 15СОИМ О блока 3, а три младшихвхода 54, 56 и 58 второго операндаобъединены и подключены к выходу 15СОИМ 1 блока 3. Таким образом,обрабатываемые биты двух операндовпоступают на два старших входа 59и 60 модуля 48,В зависимости от кодовой комбинации на выходах 15 6 - 15 р блока 3 вблоке 2 может быть выполнена одна иэшестнадцати арифметических или логических функций в соответствии с таблицей (фиг.7)Выбор режима логической или арифметической обработки информации осуществляется при помощивыхода 156 блока 3. При наличии наэтом выходе логического О блок 2выполняет логические операции, в противном случае - арифметические. Триггер 45 служит для запоминания одногоиз операндов при работе с двумя операндами, триггер 46 - для запоминаниярезультата выполнения той или инойоперации, триггер 47 - для запоминания переноса при выполнении логических операций. Все триггеры запоминаютпоступающую на их первые входы информацию при поступлении на их вторыевходы синхросигналов с выходов 15 15 Ъ блока 3.Первоначально один бит первого.операнда считывается иэ матрицы памяти и записывается в триггер 45, выходкоторого подключен к старшему входу 60одного из операндов модуля 48, Затемсчитывается один бит второго операнда, которыйминуя триггер 45, поступает на старший вход 59 второго операнда. Результат обработки двух битокдвух операндов считывается с выхода 62 )раций на выходе 62 не зависит от состояния трех пар младших входов 53-58Это достигается передачей с выхода 156 блока 3 на вход 64 модуля 48 соответствующего логического уровня,При наличии сигнала переноса, переда ваемого с триггера 47 на вход 61 модуля 48, при выполнении арифметической операции предшествующей пары битов этот перенос суммируется со значениями, постоянно подаваемыми на 10 младшие входы 53 - 58 модуля 48 и передается к паре старших входов 59 н .60, на которые поступают обрабатываемые биты двух операндов.Присутствие логической 1 на 5 одном из выходов 15 - 15 блока 3 обеспечивает прием информации блока 2 соответственно с трех направлений: либо с предыдущего блока 24по шине 51 при сдвиге информации вниз, либо из блока 1 по шине 49, либо с последующего блока 2+4 по шине 52 при сдвиге информации вверх,Таким образом, операция обработки двух операндов в блоках 2 осуществляется в три этапа. Вначале из блока 1 считывается один бит информации первого операнда, который записывается в триггер 45. Затем из блока 1 считывается одйн бит информации второго операнда, при этом с выходов 156-15, 30 поступает код выполняемой операции, и синхросигналом с выхода 15 в триггер 47 записывается перенос. На третьем этапе результат операции с триггера 46 записывается в соответствующий блок 1.При обработке одного операнда, - например, в поисковых операциях очередной бит считывается иэ блока 1 и передается в блок 2, который уже на строен на соответствующую операцию.Результат фиксируется в триггере 46 и затем переписывается в соответствующий блок 1. Результат арифметических и логических операций над масси вами данных из блоков 2 записывается в матрицу памяти,откудаон может быть, считан с целью вывода его иэ процессора, Для этого блок 4 по сигналам управления на выходе 10 блока 3 осуществляет коммутацию считываемой из матрицы памяти информации для записи ее сначала в один блок буферной памяти, а затем в другой. Заполнение всех регистров каждого из блоков 6 и 7 осуществляется последовательно по разрядам. Вывод информации иэ процессора происходит через блок 5. Примером реализации регистров сдвига блоков 6 и 7 является серийно выпускаемая микросхема К 155 ИР 13. 60Предлагаемый процессор прост в изготовлении и имеет высокое быстродействие, В известном процессоре, выполненном на быстродействующей серии по . ЭСЛ-технологии, время обращения к памяти составляет примерно 120 нс(по 40 нс для считывания или записиинформации в память и для прохождениямультиплексора и перестановочной сети). В предлагаемом процессоре время-обращения к матонце памяти в,процессореобработки данных составляет примерно40 нс за счет того, что информацияиз матрицы памяти непосредственно заносится в арифметико-логическне блоки,Загрузка Ии-разрядных слов в дан-,ный процессор осуществляется за ФФитактов. Первые И тактов необходимозатратить на первоначальную загрузкурегистров одного иэ блоков буфернойпамяти, В известном процессоре загрузка данных в Ю блоков памяти происходит за уи тактов. Однако в каждый иээтих тактов входит время, котороенеобходимо затратить на прохождениемультиплексора и перестановочной сети, Так например для матрицы памятив 1024 слова по 256 разрядов в известном процессоре зто время составляет122,9 мкс, а в предлагаемом -51,2 мкс. Таким образом с увеличениемобъема памяти эффективность предлагаемого устройства ввода информациив матрицу повышается.Важным отличием данного процессораот известного является то, что 16илн 32-разрядные слова поступают свхода процессора непосредственно впамять. В известном процессоре производится предварительное формирование 256-разрядных слов с помощьювнешней перестановочной сети.Особенностью данного процессораявляется также то, что вертикальныесдвиги информации в двух направленияхв комбинации с записью в матрицу памяти по произвольному адресу позволяют,йроизводить сложные операции над массивами данных, такие как перестановка, сортировка, транспозиция и др,Формула изобретения1, Ассоциативный матричный процессор, содержащий блоки памяти, арифметико-логические блоки по числу блоков памяти, блок управления, входной н выходной блоки коммутаторов, причем выходы блоков памяти соединены с информационными входами соответствующих арифметико-логических блоков и информационными входами входного блока коммутаторов, о т л и ч а ю щ и й с я тем, что, с целью увеличения производительности, он содержит первый и второй блоки буферной памяти и две группы коммутаторов, общее число которых равно числу блоков памяти, при этом первые и вторые информационные входы блоков буферной памяти подключены соответственно к информационномувходу процессора и выходу входного блока, коммутаторов, первые информационные выходы первого и второго блоков бу" ферной памяти соединены соответственно с перв и валоры инфор ационными 5 входами выходного блока коммутаторов, выход которого подключен к информаци онному выходу процессора, вторые информационные выходы первого и второго блоков буферной памяти соединены с первыми информационными входаю коммутаторов соответственно первой и второй групп, вторые информационные входы коммутаторов подключены к информационным выходам соответствующих арифметико-логических блоков,а выходы этих коммутаторов соединены с управляющими входами соответствующих блоков памяти, первый вход и выход переноса каждого арифметико-логического блока подключены соответственно 20 к второму выходу н входу переноса соседнего арнфметико-логического блока, а первый, второй, третий, четвертый, пятый, шестой и седьмой выходы блока управления соединены соответственно с 25 управляющими входами входного блока коммутаторов, первого и второго блоковбуферной памяти и коммутаторов первой и второй групп, адресными входами блоков памяти и управляющими входами арифметико-логических блоков и выходного блока коммутаторов.2. Процессор по п.1, о т л н ч а - ю щ и й с я тем, что блок управления содержит генератор синхросигналов, регист" состояния, память управляю-. щих команд, память микрокоманд, регистр управляющих команд, регистр мнкрокоманд, две группы элементов И, группу элементов ИЛИ, дешифратор и три элемента И, причем первый и вто рой выходы регистра состояния соедине. ны соответственно с первыми входами элементов И первой группы и входомгенератора синхросигналов, первые вхо.ды элементов И второй группы подключены к первому выходу регистра управляющих команд, второй выход которого соединен с входом памяти микрокоманд,вторые входы элементов И первой и второй групп подключены соответственно кпервому и второму выходам генераторасинхросигналов, третий, четвертый ипятый выходы которого соединены соответственно с управляющими входами регистра управляющих команд, регистра, второго и третьего элементов И, первыеи вторые входы элементов ИЛИ группыподключены к выходам элементов И соответственно первой и второй групп, а ихвыходы соединены с входом памяти управляющих команд, выходы памяти микрокоманд и памяти управляющих командподключены к информационным входамсоответственно регистра микрокоманди регистра управляющих команд, первый,второй, третий, четвертый, пятый,шестой .и седьмой выходы регистра микрокоманд соединены соответственно спервым выходом блока, вторыми входамипервого и второго элементов И, четвертым выходом блока, входом дешифратора, вторым входом третьего элемента И и седьмым выходом блока, а выходы первого, второго н третьего эле"ментов И подключены соответственно квторому, третьему и шестому выходамблока. Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР9479114, кл. 606 15/00, 1975 .2, Патент США Р 3800289,кл, 340-172.5, опублик. 1974 (прото,тип) .