Матричный параллельный процессор

,123316 Р 15/34 АНИЕ ИЭ РЕТЕНИ ВТОРСНОМУ ЕТЕЛЬСТВУ водник ел СССР1973. 981.РОЦЕССОобласти бытьроваи рас. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Институт физики полупроСО АН СССР(57) Изобретение относится квычислительной техники и можиспользовано,в устройствах виния, кодирования, декодирова познавания сигналов, а также в устройствах обобщенного спектрального анализа и фильтрации, основанных на алгоритмах быстрых дискретных преобразований. Цель изобретения - повьппение производительности устройства. Цель изобретения достигается за счет введения в процессор блока выбора режима работы, имеющего сложную структуру, с соответствукицими связями между ним и известными блоками процессора, Применение в изобретении параллельно-последовательной конвейерной структуры вычислений по методу быстрых дискретных преобразований позволяет достичь положительного эффекта. Е 2 э.п. ф-лы, 15 ил.васг, 6 ыпюилеРАМОМ ЯЬВЦЯИ адараю Й дфИЧРЧГЧй даюсе ДЯРЯдинна - индерЯРЮБУРИ 66 КП ФОНТи Госуд лам и осквааж 671 Подписрстзенного комитета СССРобретений и открытийЖ, Раущская наб., д. 4/5Р.зобретение относится к вычислительной технике и может быть использовано в устройствах шифрования,кодирования,декодирбвания и распознаваниясигналов,а также в устройствах обобщенного спектрального анализа и Фильтрации, основанных на алгоритмах быстрых дискретных преобразований,Цель изобретения - павьшение производительности устройства,1 Оца Фиг. 1 представлена схема матричного параллельного процессорабыстрых дискретных преобразований вбазисе Уолша-подобных Функций; нафиг. 2 - структурная схема вычислительного модуля; на фиг. 3 - структура операционного элемента (ОЭ); нафиг, 4 - функциональная схема блокавыбора режима работы и его связь скоммутаторами операционных элементоводного из вычислительных модулей(элементы коммутации изображены поодному разряду); на Фиг, 5 - таблицасостояний коммутаторов четырех операционных элементов одного из вычислительных модулей в зависимости. отзначений управляющих сигналов с блока выбора режима работы и блока. управления и синхронизации; на Фиг, 6-11класс выполняемых вычислительным ма- ЗОдулем преобразований; на фиг, 12таблицы некоторых матриц В выполняемого преобразования; на Фиг. 1315 - временные диаграммы работы ОЭ,вычислительного модуля и процессорав конвейерном режиме (при этом наФиг. 15 о - полный цикл работы процессора, когда одновременно можнообрабатывать восемь потоков данных,8 - режим 4, при котором данные непроходят обработки в процессоре, в6 - режим, когда один из уровней операционных элементов в вычислительноммодуле находится в состоянии прямого пропускания),4 Я Процессор содержит шестнадцать информационных входов 1, шестнадцать выходов 2, два столбпа четырехвходовых вычислительных модулей (ВМ) 3" о по четыре в каждом, блок 4 управления О и синхронизации (БУС), блок 5 выбора режима работы (БВРР), входы 6-9 кода режима работы устройства, с первого по восьмой выходы 10- 17 БВРР 5. Входы 6-9 подключены к соответствующим выходам БУС. Выходы с 10 по 17 БВРР через одноименные шины подключены соответственно к входам кода операции вычислительного глодуля с первого по восьмой. Входы ВИ первого столбца соединены с входами 1 процессора, первьй, второй, третий и четвертый выходы каждогс г.-го (1=1,4) ВМ первого столбца - соответственно с каждым 1-м информационным входом первого, второго, третьего и четвертого ВМ второго столбца, а выходы ВМ второго столбца - с выходами 2 процессора. ВМ содержит четыре инФормационных входа 18, четыре выхода 19, четыре одинаковых 03 20, образующих матрицу 2 х 2, первые два входа 18 подключены к информационным входам ОЭ первого столбца первой строки, третий и четвертый входы 18 - к информационным входам 03 первого столбца второй строки, а первый и второй выходы К - го (К = 1,2) 03 первого столбца соединены соответственно с К-информационными входами 03 первой и второй строки (столбца). Выходы 03 первой строки второго столбца подключены к первому и второму выходам 19, а выходы ОЭ второй строки второго столбца - к третьему и четвертому выходам 19. Выходы 10 и 1 1 подключены соответственно к первому и второму входам .кода операции 03 первого столбца, выходы 12 и 13 - соответственно к третьим входам кода операции ОЭ первого столбца первой и второй строк, выходы 14 и 15 - соответственно квторому и первому входам кода операции 03 второго столбца, выходы 16 и 17 - ссответственно к третьим входам кода операции 03 второго столбца первой и второй строк. ОЭ содержит первый 21 и второй 22 информационные входы, первый 23 и второй 24 регистры входных данных, первый 25 и второй 26 коммутаторы, первый 27, второй 28, третий 29 и четвертьпл 30 буферные регистры, первый 31 и втарои 32 сумматорьгр нервыи 33 и втарои 34 регистры выходных данных, первый и второй информационные выходы 35 и 36 соответственно. Входы 10 - 12 (13) подключены соответственно к первому, второму, третьему управляющим входам коммутаторов 25 и 26, входы 21 и 22 к информационным входам регистров 23 й 24 соответственно, выходы которьгх подключены к информационным входам коммутаторов 25 и 26 соответственно, Первыйл выход 37 коммутатора 25 подключен к информационному входу регистра 33, второй выход 38 - к информа 1233,цциаццаму входу реги:тра 27, третий выход - к информационному входу регистра 29, первый выход 42 коммутатора 26 - к информационному входу регистра 34, второй выход 4 1 - к ицформа - 5 циоцному входу регистра 30, а третий выход 40 - к информационному входу регистра 28, при этом вход 12 (13) кода операции ОЭ соединен с входам чтения записи регистра 30, инверсный О выход которого подключен к первому, а выход регистра 29 - к второму ин - формационным входам сумматора 32, вход младшего разряда которого подключен к четвертому входу кода опе рации ОЭ. Выходы регистров 27 и 28 подключены к входам сумматора 31, выходы сумматоров 31 и 32 - соответственно к информационным входам регистров ЗЗ и 34, выходы которых 35 20 и 36 соответственна являются первым и вторым входами ОЭ. Коммутаторы 25 и 26 имеют выходы 37-42.Блок выбора режима работы содержит элементы И-НЕ с первого по чет вертый 43-46, первый 47 и второй 48 элементы ИЛИ-НГ, первый 45 и второй 50 элементы НЕ, Вход 6 подключен к первому входу первого элемента ИЛИ-НЕ, инверсному входу первого и прямому входу второго элементов И-НЕ, вход 7 к прямому входу первого, инверсному входу второго элементов И-НЕ и второму входу первого элемента ИЛИ-НЕ, вход 8 - к первому входу второго35 элемента ИЛИ-НЕ, инверсному входу третьего и прямому входу четвертого элементов И-НЕ, вход 9 - к второму входу второго элемента ИЛИ-НЕ, прямому входу третьего элемента И-НГ и инверсному входу четвертого элемента И-НЕ, инверсный выход первого элемента Ю 1 И-НЕ - к выходу 10 и входу первого элемента НГ, выход которого подключен к выходу 11. Инверсные выходы первого и второго 45 элементов И-НЕ соединены с выходами 12 и. 13, инверсный выход второго элемента ИЛИ-НЕ - с выходом 14 и входом второго элемента НЕ, выход которого подключен к выходу 15, инверсные вы ходы третьего и четвертого элементов И-НЕ - к выходам 16 и 17.Коммутаторы представляют собой линейку двух 51 и трехвходовых 52 элементов И, ца адин из входов кото 55 рой подается зцачецие операнда, а ца другие три - игцалы управления,Устройство работает следуюшим образом. На входы 21 и 22 ре 1 итрон 3 и24 входцых данных поступают ныхадцысоперанды а, и а соответствецца. С выхода регистра 23 операнд о поступает ца информационный вход каммутато -ря 25 и пад действием управляющихсигналов, поступающих на входы 10-12,либо проходит на прямую с вьхода 37коммутатора 25 ца вход регистра 33внхадных данных, либо идет с вь 1 хода38 ца вход выходного регистра 27 сум.матара, либо с. выходов 38 и 39 поступает на входы регистров 27 и 29 соответственно. Аналогично операнд б свыхода регистра 24 поступает на информационный выход коммутатора 26 ипод действием тех же управляющихсигналов, поступающих на входы 10-12,либо проходит с выхода 42 коммута -тора 26 ца вход регистра 34, либоидет с выхода 41 на вход входногорегистра 30 сумматора, либо с выходов 40 и 41 поступает на входы регистров 28 и 30 соответственно. Призначении управляющих сигналов, поступающих на входы 6 и 7 (или 8 и 9),т.е. сигналов, инициирующих работудвух ОЭ одного столбца, равных 00,входные операнды а, б, с,с 1 прохоцятчерез оба ОЭ одного столбца без изменений, управляющие сигналы, поступающие на входы 10-12 ОЭ первогостолбца первой строки и на входы 10,11 и 13 ОЭ первого столбца второйстроки равны "101" (фиг. 8 и 9),чтосоответствует прямому прохождениюоперандов о и 6 через коммутаторы25 и 26 и их выходы 37 и 42 на входырегистров 33 и 34 соответственно1 ри значении управляющих сигналов,поступающих на входы 6 и 7 (или 8и 9), равных "01" или "10", либопервый, либо второй ОЭ одного столбца пропускает данные на выход без изменения, а с выходов второго либопервого ОЭ того же столбца выдаютсязначения (о. + с ) и (а - с ) . Управляющие сигналы, поступающие на входы10 - 12 ОЭ первого столбца первойстроки (пусть ца входах 6 и 7 будет"10"), равны "011" (например, фиг,8),а сигналы на входах 1 О, 11 и 13 ОЭпервого столбца второй строки - "010",т,е. ОЭ первого столбца первой строки выпает ца своих выходах значения (с+ Б) и. (а - ь ), а ОЭ первогофстолбца второй строки пропускаетвхапцые операнды на свои вьходы.Операнды с, и 6 через выходы 38, 39модуля управляющих сигналов одинаковые ОЭ модулей могут либо выполнять операции сложения-вычитания поступивших на их информационный вход, либо пропускать данные с входа на выход. Это позволяет, управляя состоянием ОЭ, выполнять в модулях целый ряд преобразований (фиг. 6 - 11). Например, при подаче на входы 6 - 9 управ- гО ляющих сигналов "1111" все модули процессора выполняют преобразование Уолша-Пэли, В этом случае данные Х и Х , поступающие. на первыйеаи второи вход ОЭ первого столбца пер вой строки каждого ФППЭ первого столбца Г -й строки, сложатся и появятся на первом выходе ОЭ первого столбца первой строки, а их разность - на втором выходе этого ОЭ. Таким образом,20 на первом выходе ОЭ первого столбца первой строки каждого модуля первого столбЦа г: -й стРоки полУчаем Х Е о+ро + Х, а на втором выходе - Хе+ оХ,+.25.ОЭ первого столбца второй строки каждого модуля первого столбца Г -й строки выполняет аналогичные операцииданными Х и Х ф поступившими на его первый и второй входы соответственно, в результате чего на первом . его выходе образуется сумма Х +Хче а ефьф а на втором выходе - разность Хче+2Кеъ 35С первых выходов ОЭ первого столбца первой и второй строк результаты поступают на первый и второй входы 1 О 0 01 1 0 0 а+Ь+с+Д 1 100 1 - 1000011 О 01-1(а+Ь) -(с+0) (а-Ь)+(с-сг) (а-Ь)-(с-сг) 1-1 00 0001 0100 001 0001 0 0 г - 1 На первой итерации алгоритма быст О рого преобразования процессор выполняет с учетом вида матрицы В опера- ции 55 где о, Ь, с и сг - входные данные,поступающие на информационные входымодуля, В общем случае каждый модульможет выполнить 2 =16 преобразованийвида о 1ЬВ,где В- матрица выполняемого преобразования (примеры в таблице 2,фиг,,фиг. 12). соответственно ОЭ второго столбца первой строки каждого модуля, на первомвыходе которого образуется их сумма(Х + Х ) + (Х + Х ), е+а че+1 елг е. ф а на втором выходе - результат ихвычитания Полученные результаты передаются далее на первый и второй выходы модуля соответственно. Результаты с вторых выходов ОЭ первого столбца первой и второй строк поступают на первый и второй информационные входы соответственно ОЭ второго столбца второй строки, где выполняются опера" ции и их результат выдается на первый и второй выходы ОЭ второй строки второго столбца, а с него - на третий и четвертый выходы модуля. Результаты на выходах модуля первого столбца Г -й строки появляются одновременно, на этом заканчивается первая итерация быстрого дискретного преобразования, выполняемого процессором,Каждый вычислительный модуль выполняет вычисления также по процедуре быстрого дискретного преобразования, что можно отразить в следующем виде: где 1 - единичная матрица 4-го порядка;Я) - символ кронекеровского пере.множения матриц;вектор размера 16 х(, компоненты которого определечы В соответствии со структурой матриц В,.Результаты выходов каждого модуля первого столбца 1 - й строки передаются далее на 1 -тые входы модуля второ. го столбца, где над ними совершаются 1 ц операции, аналогичные указанным, а в целом выполняется вторая итерация алгоритма быстрого преобразованияЯт, )Результаты на выходе модуля второ:го столбца являются результатами вы:полненного быстрого преобразованияи передаются на выходы процессора.Если принять условно время сложенияв сумматоре равным 2 хранения-выборки регистров, то в процессоре в общем случае можно одновременно обрабатывать восемь потоков данных (подва потока в каждом ОЭ и, следова 25тельно, по четыре потока в каждоммодуле. Работа ОЭ, вычислительногомодуля и процессора в конвейерномрежиме отражена на временных диаграммах (фиг,13 - 15). Функционированиеотдельных элементов процессора происходит синхронно по синхросигналам,инициируемым блоком 4,Применение в предложенном процессоре параллельно в последовательн 35конвейерной структуры вычислений пометоду быстрых дискретных преобразований позволяет повысить его производительность.40Формула изобретения1, Иатричный параллельный процессор, содержащий матрицу размером 4 х 2 вычислительных модулей, причем информационные входы вычислительных модулей первого столбца матрицы подключены к Информационным входам процессора, первый, второй, третий.,четвертый выходы вычислительного модуля51) первого столбца первой строки матрицы подключены к первым и нформаци онным входам вычислительных модул ей второго столбца соответственно перв ой , второй , третьей , четвертой строк55 матрицы, первые выходы вычислительных модулей первого столбца второй, третьей и четвертой строк матрицы подключены соответственно к второму,1 т Р е т ке м У и ч ет в е 1) т и м У 15 1( ф1)и;111( 511111, 1; 1 ВХПЯМ ВЫЧИСЛИТ ЕЛЬНОГ( МС)ДУ)1)5 11 е 1) - в О Й с 5 ) О к и В т О 1) О г с т О и б ця и а т 5(1 И 1, Выходы Вь(числител(ных моду(1 е(5 1)то 1)О 1 Р столбца матриы, подключены к ии(115)рмапионным выходам процессора, О т л ич а к) щ и й с я тем, что, с целью повышения производительности, Он дополнительно содержит блок выбора режима работы, причем первый, второй, третий, четверть)й входы блока Выбора режима работы подключены к соответствующим входам кода режима процессора, первьп, второй, третий, четвертьй, пять(Й., шестой седьмой и восьмой выходы блока выбора режима работы соединены соотгветственно с первым, вторым, третьим, четвертым, пятым, шестым, седьмым и восьмым входами кода операции всех вычислительных модулей, 1-й (1 = 1,2,3,4) вычислитепьного модуля х-Й строки первого столбца матрицы подключен к 1-му инФормационному входу вычислительного модуля 3 -й строки второго столбца матрицы , = 1,2,3,4), причем каждый вычислительный модуль содержит матрицу размером 2 х 2 операционных элементов, при этом информационные входы операционных элементов первой строки первого столбца матрицы подключены соответственно к первому и Второму информационным входам модуля, информационные входы операционных элементов второй строки первого столбца матрицы подключены к третьему и четвертому информационным входам модуля, первые информационные выходы операционных элементов первого столбца первой и второй строк матрицы подключены соответс.твенно к первому и второму инйормационным входам операционного элемента первой строки перВого столбца матрицы, а вторые информационные выходы Операционных элементов первого столбца первой и вто -рой строк матрицы подключены соответственно к первому и второму информационным входам операционных элементов второго столбца второй строкиматрицы, выходы операционных элементо)в первой строки второго столбца мат.рицы подключены к первому и второму информационным выходам модуля, а выходы Операционного элемента второй строки второго столбца матрицы - к третьему и четвертому информационным25 выходам модуля, причем первый и второй входы кода оерации модуля подключены соответственно к первому и второму входам кода операции операционных элементов первого столбцаматрицы, третий и четвертый входы кода операции модуля подключены к третьим входам кода операции операционных элементов первого столбца соответственно первой и второй строки матрицы, пятый и шестой входы кода операции модуля подключены соответственно к первым и вторым входам кода операции операционных элементов второго столбца матрицы, седьмой и восьмой входы кода операции модуля подключены к третьим входам кода операции операционных элементов второго столбца соответственно первой и второй строк матрицы.2. Процессор по п.1, о т л и ч а ю щ и й с я тем, что операционный элемент содержит первый и второй сумматоры, первый и второй регистры входных данных, первый и второй регистры выходных данных, четыре буферных регистра, первый и второй коммутаторы, причем первый и второй информационные входы операционного элемента подключены к входам первого и второго регистров входных данных, выходы которых подключены к информационным входам первого и второго коммутаторов соответственно, первые выходы которых подключены соответственно к входам первого и второго регистров выходных данных, вторые выходы первого и второго коммутаторов соединены соответственно с информационными 4 входами первого и второго буферных регистров, третьи выходы первого и второго коммутаторов соединены соответственно с входами третьего и четвертого буферных регистров, выходпервого и инверсный выход второго буферных регистров подключены к первым входам соответственно первого и второго сумматоров 1 вторые входы которых подключены соответственно к50 выходам четвертого и третьего буферных регистров, выходы первого и второго сумматоров подключены к.входам Г е Р В О Г О и В т ОР О Г О Р е Г и с т 1. о Б3 ых ОД н ыхданныхВыходы которых подклюе ык первому и второму информационнымвыходам операционного элемс нта, первы:, второй и третий входы кода опе-рации которого подключены соответственно к первым, вторьп, третьим управляющим входам коммутаторов, при О чем третии вход кода операции операционного элемента подключен также квходу чтения/записи второго буферного регистра, а четвертый - к второмуинформационному входу младшего разря да второго сумматора.3. Процессор по п.1, о т л и -ч а ю щ и й с я тем, что блок выбора режима работы содержит четыреэлемента И-НЕ, два элемента ИЛИ-НЕ 20 и два элемента НЕ, причем первыйвход первого элемента ИЛИ-НЕ соединенс инверсным входом первого элементаИ-НЕпрямым входом второго элемента И-НЕ и является первым входом блока, второй вход первого элементаИЛИ-НЕ соединен с прямым входом первого элемента И-НЕ и инверсным входомвторого элемента И-НЕ и являетсявторым входом блока, выход первогоэлемента ИЛИ-НЕ соединен с входомпервого элемента НЕ и является первым выходом блока, выход первогоэлемента НЕ является вторым выходомблока, выходы первого и второго элементов И-НЕ являются соответственнотретьим и четвертым выходами блока,первый вход второго элемента ИЛИ-НЕсоединен с инверсным входом третьего элемента И-НЕ и прямым входом четвертого элемента И-НЕ и являетсятретьим входом блока, второй входвторого элемента ИЛИ-НЕ соединен спрямым входом третьего элемента И-НЕи инверсным входом четвертого элемента И-НЕ и является четвертымвходом блока, выход второго элемента ИЛИ-НЕ соединен с входом второгоэлемента НЕ и является пятым выходомблока, выход второго элемента НЕ является шестым выходом блока, выходытретьего и четвертого элементов И-НЕявляются соответственно седьмым ивосьмью выходами блока.12331 б 9 Коммупация аОураип Хоииувоция Е ОЗ 1 Ат с РЛ Яиачс ЯЛ 1 бит с ЯЛ 7 дсюп с Ю омюужщияг",уроню