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

 

Изобретение относится к области вычислительной техники и может быть использовано .в устройствах шифрования , кодирования, декодирования и распознавания сигналов, а также в устройствах обобщенного спектрального анализа и фильтрации, основанных на алгоритмах быстрых дискретных преобразований . Цель изобретения - повышение производительности устройства. Цель изобретения достигается за счет введения в процессор блока выбора режима работы,имеющего сложную структуру , с соответствующими связями между ним и известными блоками процессора . Применение в изобретении параллельно-последовательной конвейерной структуры вычислений по методу быстрых дискретных преобразований позво- Q ляет достичь положительного эффекта. ® 2 з.п. ф-лы, 15 нл. (D

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ с

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМ .Ф СВИДЕТЕЛЬСТВУ (21) 3777276/24-24 (22) 25.07.84 (46) 23.05.86. Бюл. Ф 19 (71) Институт физики полупроводников

СО АН СССР (72) А.В. Ржанов, Н.Д. Новоселов, Г.А. Кухарев и E.È. Черепов (53) 681.325(088.8) (56) Авторское свидетельство СССР

Ф 478306, кл. С 06 F 15/20, 1973.

Патент Франции Ф 2484672, кл. G 06 F 15/332, опублик. 1981. (54) МАТРИЧНЫЙ ПАРАЛЛЕЛЬНЫЙ ПРОЦЕССОР (57) Изобретение относится к области вычислительной техники и может быть использовано,в устройствах шифрования, кодирования, декодирования и рас. SU„„1233169 А 1

G 06 F 15/347 познавания сигналов, а также в устройствах обобщенного спектрального анализа и фильтрации, основанных на алгоритмах быстрых дискретных преобразований. Цель изобретения — повьппение производительности устройства.

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

2 э.п. ф-лы, 15 ил.

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

Цель изобретения — повьш ение производительности устройства, 19

На фиг. 1 представлена схема матричного параллельного процессора быстрых дискретных преобразований в базисе Уолша-подобных функций; на фиг. 2 — структурная схема вычислительного модуля; на фиг. 3 — структура операционного элемента (03) на фиг. 4 — функциональная схема блока выбора режима работы и его связь с коммутаторами операционных элементов одного из вычислительных модулей (элементы коммутации изображены по одному разряду); на фиг. 5 — таблица состояний коммутаторов четырех операционных элементов одного из вычислительных модулей в зависимости. от значений управляющих сигналов с блока выбора режима работы и блока управления и синхронизации; на фиг, 6-11 класс выполняемых вычислительным ма- ЗО дулем преобразований; на фиг. 12 (таблицьг некоторых матриц В„ выполняемого преобразования; на фиг. 1315 — временные диаграммы работы ОЭ, вычислительного модуля и процессора в конвейерном режиме (при этом на фиг. 15д — полный цикл работы процессора, когда одновременно можно обрабатывать восемь потоков данных, гУ вЂ” режим 4, при котором данные не проходят обработки в процессоре, и

6 — режим, когда один из уровней операционных элементов в вычислительном модуле находится:s состоянии прямого пропускания).

11 5

Процессор содержит шестнадцать информационных входов 1, шестнадцать выходов 2, два столбца четырехвходовых вычислительных модулей (ВМ) 3

r" О по четыре в каждом, блок 4 управления и синхронизации (БУС), блск 5 выбора режима работы (БВРР), входы 6-9 кода режима работы устройства, с первого по восьмой выходы 10-17 БВРР 5. Входы 6-9 подключены к соответствующим выходам БУС. Выходы с 10 по 17 БВРР через одноименные шины подключены соответственно к входам кода операции вычислительного модуля с первого по восьмой. Входы ВИ первого столбца соединены с входами 1 процессора, первьй, второй, третий и четвертый выходы каждогс i го (i=1,4) ВМ rгepвого столбца — соответственно с каждым 1-м информационным входогл первого, второго, третьего и четвертого

BN второго столбца, а выходы ВМ второго столбца — с выходами 2 процессора. BN содержит четыре информационных входа 18, четыре выхода 19, четыре одинаковых 03 20, образующих матрицу

2х2, первые два входа 18 подключены к информационным входам ОЭ первого столбца первой строки, третий и чет— вертый входы 18 — к информационным входам 03 первого столбца второй строки, а первый и второй выходы

1(— ro (К = 1,2) 03 первого столбца соединены соответственно с К-информационными входами 03 первой и второй строки (столбца). Выходы 03 первой строки второго столбца подключены к первому и второму выходам 19, а вы— ходы 03 второй строки второго столбца — к третьему и четвертому выходам

i9. Выходы 10 и 11 подключены соответственно к первому и второму входам .кода операции 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 <,<1 ционному входу реги<.трл 27, третий ных<>д — к информационному входу регистра 29, первый выход 42 коммутатора

26 — к информационному входу регистра 34, второй выход 4 1 — к информа— ционному входу регистра 30, а третий выход 40 — к информационному входу регистра 28, при этом вход 12 (13) кода операции ОЭ соединен с входом чтения записи регистра 30, инверсный 1О выход которого подключен к первому, а выход регистра 29 — к второму ин— формационным входам сумматора 32, вход младшего разряда которого подключен к четвертому входу кода one- 15 рации ОЭ. Выходы регистров 27 и 28 подключены к входам сумматора 31, выходы сумматоров 31 и 32 — соответственно к информационным входам ре— гистров 33 и 34, выходы которых 35 20 и 36 соответственно являются первым и вторым входами ОЭ. Коммутаторы 25 и 26 имеют выходы 37-42.

Блок выбора режима работы содержит элементы И вЂ” НЕ с первого по четвертый 43 — 46, первый 47 и второй 48 элементы ИЛИ-НЕ, первый 45 и второй

50 элементы HE. Вход 6 подключен к первому входу первого элемента ИЛИ-НЕ, инверсному входу первого и прямому входу второго элементов И-НЕ, вход 7 к прямому входу первого, инверсному входу второго элементов И-НЕ и второму входу первого элемента ИЛИ-HE вход 8 — к первому входу второго

35 элемента ИЛИ-НЕ, инверсному входу третьего и прямому входу четвертого элементов И-HF. вход 9 — к второму входу второго элемента

ИЛИ-НЕ, прямому входу третьего элемента И-НЕ и инверсному входу четвер-40 того элемента И-НЕ, инверсный выход первого элемента ИЛИ-НŠ— к выходу

10 и входу первого элемента НЕ, выход которого подключен к выходу 11.

Инверсные выходы первого и второго 45 элементов И-HE соединены с выходами

12 и 13, инверснь<й выход второго элемента ИЛИ вЂ  — с выходом 14 и входом второго элемента НЕ, выход которого подключен к выходу 15, инверсные вы- 5п ходы третьего и четвертого элементов

И-НŠ— к выходам 16 и 17.

Коммутаторы представляют собой линейку двух 51 и трехвходовых 52 элементов И, иа один из входов кото55 рой подается значение операнда, а на другие три — <.игналы управления.

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

На вх<1дь> 21 и 22 ре1 и< тр<>н 3 и

24 входных данных поступлют выходные операнды а и < соответственно. С выхода регистра 23 операнд с> поступает нл инф<.рмационный вход коммутато— рл 25 и под действием управляк>шпх сигналов, поступлн>щих нл входы 10-12, либо проходит на прямую с вь>хода 37 коммутатора 25 нл вход регистра 33 внходных данных, либо идет с выхода

38 на вход выходного регистра 27 сумматора, либо с. выходов 38 и 39 поступает на входы регистров 27 и 29 соответственно. Аналогично операнд 8 с выхода регистра 24 поступает на информационный выход коммутатора.26 и под дейстнием тех же управляющих сигналов, поступающих на входы 10-12, лиоо проходит с выхода 42 коммута— тора 26 на вход регистра 34, либо идет с выхода 41 на вход входного регистра 30 сумматора, либо с выходов 40 и 41 поступает на входы регистров 28 и 30 соответственно. При значении упранляющих сигналов, поступающих на входы 6 и 7 (или 8 и 9), т.е. сигналов, инициирующих работу двух ОЭ одного столбца, равных 00, входные операнды а,l3, с, d прохоцят через оба ОЭ одного столбца без изменений, управляющие сигналы, поступающие на входы 10-12 ОЭ первого столбца первой строки и на входы 10, 11 и 13 ОЭ первого столбца второй строки равны "101" (фиг. 8 и 9),что соответствует прямому прохождению операндов а и Ь через коммутаторы

25 и 26 и их выходы 37 и 42 на входы регистров 33 и 34 соответственно °

При значении управляющих сигналов, поступающих на входы 6 и 7 (или 8 и 9), равных "01" или "10", либо первый, либо второй ОЭ одного столбца пропускает данные на выход без изменения, а с выходов второго либо первого ОЭ того же столбца выдаются значения (о. + с ) и (а — 8 ) . Управляющие сигналы, поступающие на входы

10 — 12 ОЭ первого столбца первой строки (пусть на нходах 6 и 7 будет

"10"), равнь< "011" (например, фиг.8), а сигналы на входах 10 11 и 13 ОЭ первого столбца второй строки — "010". т, е. ОЭ первого столбца первой строки вычлет нл своих выходах значения (с+ Б) и. (д — ь ), а ОЭ первого ь стол<>ца второй строки пропускает вхопные операнды на снои выходы.

Операнды <>, и 6 через выходы 38, 39

1 2 1 1l)9

1 0 0 0 1 1 0 0 а+Ь+с+ 1

1 100

1 — 100

0011

0 01-1 (а+Ь)-(c+d) (a-Ь)+(с-d) (а-Ь)-(с-d) t-1 00

0001

0100001

0001

001 — 1

Х"1= (Z 0B,) Х

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

Это позволяет, управляя состоянием

03 выполнять В модулях целыи ряд преобразований (фиг. 6 — 11). Например, при подаче на входы 6 — 9 управ- 10 ляющих сигналов "1111" все модули процессора выполняют преобразование

Уолша-Пэли, В этом случае данные

Х и Х„ „,:поступающие. на первый

4 Е О и второи вход ОЭ первого столбца пер- 15 вой строки каждого ФППЭ первого столбца Г -й строки, сложатся и появятся на первом выходе ОЭ первого столбца первой строки, а их разность — на втором выходе этого 03. Таким образом,20 на первом выходе 03 первого столбца первой строки каждого модуля нервого столбца г, -й строки получаем Х Е + Е+о

+ Х, +,, а на втором выходе — Х Е+ О

Х„, „.

Ф .

ОЭ первого столбца второй строки каждого модуля первого столбца Г -й строки выполняет аналогичные операции

Данными X e H X I+ постУпившими на его первый и второй входы соответственно, в результате чего на первом . его выходе образуется сумма X +Х Е -Ы а на втором выходе — разность Х чЕ+ Е з 35

С первых выходов ОЭ первого столбца первой и второй строк результаты поступают на первый и второй входы где а, Ь, с и d — входные данные, поступающие на информационные входы модуля. В общем случае каждый модуль

4 может выполнить 2 =16 преобразований вида

Ь

Y= B„г г где В„- матрица выполняемого преобразования (примеры в таблице 2,фиг., фиг. 12) . соответственно ОЭ второго столбца пер вой строки каждого модуля, на первом вьгходе которого образуется их сумма (Х + Х ) + (Х + X ), e„ЧЕ+1 Е+г „e » а на втором выходе — результат их вычитания

Полученные результаты передаются далее на первый и второй выходы модуля соответственно. Результаты с вторых выходов ОЭ первого столбца „первой и второй строк поступают на первый и второй информационные входы соответственно ОЭ второго столбца второй строки, где выполняются опера" ции и их результат выдается на первый и второй выходы ОЭ второй строки второго столбца, а с него — на третий и четвертый выходы модуля. Результаты на выходах модуля первого столбца f -й строки появляются одновременно, на этом заканчивается первая итерация быстрого дискретного преобразования, выполняемого процессором.

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

На первой итерации алгоритма быстрого преобразования процессор выполняет с учетом вида матрицы В операции где I — единичная матрица 4-го порядка;

Q») — символ кронекеровского перемножения матриц;

12 (11(Ii

i it х вектор размера 16xi, компОненты которого определены в соответствии со структурой матриц В,.

Результаты выходов каждого модуля первого столбца (— и строки передаются далее на f -тые входы модуля второго столбца, где над ними совершаются 1д операции, аналогичные указанным, а в целом выполняется вторая итерация алгоритма быстрого преобразования

Результаты на выходе модуля второ:го столбца являются результатами вы:полненного быстрого преобразования и передаются на выходы процессора.

Если принять условно время сложения в сумматоре равным 2t хранения-выборки регистров, то в процессоре в общем случае можно одновременно обрабатывать восемь потоков данных (по два потока в каждом ОЭ и, следова—

25 тельно, по четыре потока в каждом модуле. Работа ОЭ, вычислительного модуля и процессора в конвейерном режиме отражена на временных диаграммах (фиг,13 — 15). Функционирование отдельных элементов процессора происходит синхронно по синхросигналам, инициируемым блоком 4, Применение в предложенном процессоре параллельно †последовательн 35 конвейерной структуры вычислений по

i методу быстрых дискретных преобразований позволяет повысить его производительность.

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

1. Иатричный параллельный процессор, содержащий матрицу размером

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

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

t вой, второй, третьей, четвертой строк

55 матрицы, первые выходы вычислительных модулей первого столбца второй, третьей и четвертой строк матрицы подключены соответственно к второму,1 тр(ть ему и чет !! ортом у 11 нфii!1! I;1 i1(1(О11111 I; I входам Вичислит е ьн ОГ(t мо, 15 . я 11t 1)

Roti cTpoI(H BT(t()o((! столбца

ТЗыходы вь(чк(литeл!>ных моду!!о!1 !Зто110! о столбца матра™ы, подключены к информационным выходам процессора, о т л и ч а к! шийся тем, что, с целью повышения производительности, он дополнительно содержит блок выбора режима работы, причем первый, второй, третий, четверть!й входы блока выбора режима работы подключены к соответст:-.5ëîùHM входам кода режима процессора, первьп", второй, третий, четвертьй, пятый., шестой„ седьмой и восьмой выходы блока выбора режима работы соединены соотг ветственно с первым, вторым, третьим, четвертым, пятым, шестым, седьмым и восьмым входами кода операции всех вычислительных (J = 1,2,3,4) вычислитепьного модуля х-й строки первого столбца матрицы подключен к i-му информационному входу вычислительного модуля j -й строки второго столбца матрицы (i = 1,2,3,4), причем каждый вы гислительный модуль содержит матрицу размером 2х2 операционных элементов, при этом информационные входы операционных элементов первой строки первого столбца матрицы подключены соответственно к первому и

pTopoMv информационным входам модуля, информационные входы операционных элементов второй строки первого столбца матрицы подключены к третьему и четвертому информационным входам модуля, первые информационные выходы операционных элементов первого столб— ца первой и второй строк матрицы подключены соответс.твенно к первому и второму информационным входам операционного элемента первой строки первого столбца матрицы, а вторые информационные выходы операционных элементов первого столбца первой и вто— рой строк матрицы подключены соответственно к первому и второму информационным входам олерационнь1х элементов второго столбца второй строки матрицы, выходы операционных элементов первой строки второго столбца матрицы подключены к первому и второму информац!(онным выходам модуля, а выходы операционного элемента второй строки второго столбца матрицы — к третьему и четвертому информационным

1 э

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

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

50 выходам четвертого и третьего буферных регистров, выходы первого и второго сумматоров подключены к.входам

Г! E p В О Г О ! B т Ор О Г О р е Г и с T p о Б 3 ых o jl н ых данных q выходы KotophIx подклю ! lthl к первому и второму информационным выходам операционного элемента, первый:, второй и третий входы кода опе- рации которого подключены соответственно к первым, вторым, третьим управляющим входам коммутаторов, при10 чем третии вход кода операции операционного элемента подключен также к входу чтения/записи второго буферного регистра, а четвертый — к второму информационному входу младшего разря15 да второго сумматора.

3. Процессор по п.1, о т л и— ч а ю шийся тем, что блок выбора режима работы содержит четыре элемента И-НЕ, два элемента ИЛИ-НЕ

20 и два элемента НЕ, причем первьК! вход первого элемента ИЛИ-HE соединен с инверсным входом первого элемента

И-НЕ H прямым входом второго элемента И-НЕ и является первым входом блока, второй вход первого элемента

ИЛИ-НЕ соединен с прямым входом первого элемента И-НЕ и инверсным входом второго элемента И-НЕ и является вторым входом блока, выход первого элемента ИЛИ-НЕ соединен с входом первого элемента НЕ и является первым выходом блока, выход первого элемента HE является вторым выходом блока, выходы первого и второго эле5 ментов И-НЕ являются соответственно третьим и четвертым выходами блока, первый вход второго элемента ИЛИ-НЕ соединен с инверсным входом третьего элемента И-HE и прямым входом чет0 вертого элемента И-НЕ и является третьим входом блока, второй вход второго элемента ИЛИ-НЕ соединен с прямым входом третьего элемента И-НЕ и инверсным входом четвертого эле5 мента И-HE и является четвертым входом блока, выход второго элемента ИЛИ-НЕ соединен с входом второ"о элемента НЕ и является пятым выходом блока, выход второго элемента НЕ является шестым выходом блока, выходы третьего и четвертого элементов И-HE являются соответственно седьмым и восьмью выходами блока.

1?33169

3, l 233169

Комму покия РР урсбип Хоииуо!оция Е 03 о уроЬ@

1А т с 823 1Ьпл с 829 !бит с I123 1дапп с 029

1дилтс 029 Ыитс 823 1оимо 829 1дмт с 023

Маинучаиия Оз ура!!м ноииутация Е 03 уробия

Фиг. !!

1 Р" 51 fЧ

Г с

Ъ (1

С-4

c- df

1 1

"1" 7" Ф 7 "1" а"

1Z 33 69

1:

II p ugly

"1" "0"

Ъ" "0 Фиг. М Ъ" д"

° „б „.7 8 „„ азсг, 6ыиюилены

РН?МОЮТ ЯЬИЦЯРИ

c8utew"

96_#_QM 7qbfll

Ы 66ЦХПОН?ЧН базисе ДЯ Р длерациц аль еноеа а дычт ддллгаж иае Щ да нере юса

1 Маично - индер

ЯРСБУРИ96КП ФОН ( 7

1233169

7, ц б28, 1, ЗЗ, Фиг. 15

1233169

)уробел процессора

g я уробвиь прпцессо,од

f уродясь лроцессора

2ф0068и

77РЗЦЕСС Ч

7У ЮРгмв

)ЮЦРССОЩ

2 Дюйма

ЩЮЦРССО)И Фма Б

Составитель В. Смирнов

Техред O.Cîïêü

Корр ек тор Л. Пилипенко.

Редактор С. Саенко

Заказ 2772j51 Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, г, Ужгород, ул, Проектная, 4