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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и позволяет сократить время вьгаислений произведения матрицы на вектор. Одновременная параллельная вычислительная структура для вычисления произведения матрицы на вектор . содержит матрицу (т, t блоков сумматоров , причем каждый блок сумматоров содержит m сумматоров. В общем случае изобретение позволяет вычислять, выражение вида L + А Б, где L и В - первый и второй векторы; А - матрица. Результат вычислений формируется на выходах соответствующих блоков сумматоров последнего столбца матрицы. 2 ил. (Л с го С/д Oi ел

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

СО|.1ИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (!9) (!!) (5!) 4 С 06 Р 15/347

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

К А BT0PCHOMV СВИДЕТЕЛЬСТВУ

? ", \

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3818952/24-24 (22) 30,11.84 (46) 07.06.86. Бюл. 9 21 (71) Институт проблем моделирования в энергетике AH УССР и Львовский ордена Ленина политехнический институт им. Ленинского комсомола (72) В. А. Гуляев, A. И. Стасюк, В. М. Чаплыга и Ю. Н. Спиченков (53) 681.325(088.8) (56) Авторское свидетельство СССР

1!? 623204, кл. G 06 F 7/52, 1978.

Авторское свидетельство СССР

11? 1056192, кл. С 06 Р 7/70, 1983.

Стасюк А. И. Однородные многофункциональные матричные процессоры. Киев, (препринт АН УССР, институт электродинамики, Р 351, 59 с.),1983, с. 45-49, рис. 14-16. (54} ОДНОРОДНАЯ ПАРАЛЛЕЛЬНАЯ ВЫЧИСЛИТЕЛЬНАЯ СТРУКТУРА ДЛЯ ВЫЧИСЛЕНИЯ

ПРОИЗВЕДЕНИЯ МАТРИЦЫ НА ВЕКТОР (57) Изобретени е относится к вычислительной технике и позволяет сократить время вы числений произведения матрицы на вектор. Одновременная параллельная вычислительная структура для вычисления произведения матрицы на вектор . содержит матрицу (m, zj) блоков сумматоров, причем каждый блок сумматоров содержит m сумматоров. В общем случае изобретение позволяет вычислять. выра жение вида L + A В, где Ь и В - первый и второй векторы; А — матрица.

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

2 ил.

6500 2 шиной устройства (при m = 3, соотнетстненно 8-10) .

Работа однородной параллельной структуры для вычисления произведения матрицы А на вектор В, когда каждый компонент результата произведений

А Ь С вектора С = (C,, С ...„С,„) формируется как

171

С; = а;;Ь,, J =1

1, ш, Однородная параллельная вычислительная структура для вычисления про.изведения матрицы на вектор (фиг. 1) содержит блоки сумматоров 1, К".разрядов j входных шин (j 1, 2, ..., v) (при К 1-3) соотнетственио 2, 3

4 (m+i) входных шин (при i 1-3), соответственно 57 и ш выходных шин

8 1О и К, i. входных шин i !...„m (при ш 3), соответственно 11-19.

Блоки сумматоров 1 сформированы в виде матрицы размерностью (m, и), причем каждый блок сумматоров I (фиг, 2) содержит m двухвходовых сумматоров 20, выход каждого -го из которых соединен со входом первого слагаемого (i+I)-го сумматора 20.

Выход m-го двухвходоного сумматора

20 j-ro блока сумматоров 1 К-й строки матрицы соединен со сдвигом

2 со входом первого слагаемого nept ного двухвходового сумматора 20 (j+I)-го блока сумматоров 1 этой же

40 строки матрицы, входы Вторых слагаемых i-х двухвходовых сумматоров 20 всех блоков сумматорон 1 К-й строки матрицы объединены и соединены с (К, j)-й входной шиной устройства, 45

Управляющие входы i-х двухнходовых сумматоров 20 каждого блока сумматоров 1 j-го столбца матрицы объединены и подключены к j-му разряду К-й входной шины устройства. Вход перного слагаемого первого двухвходового сумматора 20 i-ro блока сумматоров

1 первого столбца матрицы соединен с (m+I)-й входной шиной (при ш = 3, соответственно 5 7) . Выход m-го,цвухвходового сумматора 20 i-ro блока сумсумматоров I последнего столбца матрицы соединен с (2m+i)-й выходной и; =(а;

Ь

I (2) бипарных элемени сформируем матрицу тон нида (3) 1 ° m

501 е

1. I23

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

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

На фиг. 1 представлена схема однородной параллельной вычислительной структуры для вычисления произведения матрицы на вектор при m 3, и

4; на фиг. 2 схема блока сумматоров К-й строки j-ro столбца матрицы ° где a" - элементы матрицы А

lI ! Ь; — компоненты вектора Ь;

С - компоненты вектора С, осуществляется следующим образом.

Дпя организации дднородной вычислительной структуры запишем компонен ты С;, Ь, векторов С, Ь и элементы а матрицы А в разрядной форме как

tj и векторы бипарных элементов соответ» ственно е 1 где компонентами b; вектора„Ье являются i-e компоненты векторов Ь, ... Ь,„, v о ° е . щ °

Тогда компоненты С; вектора С = (С,, v v

С, ...,С„) могут быть определены на основе следующих рекурентных выраже» ний з

-in-l)

2 А,Ьи + 2 А,b„ +

+ 2 А,Ъ +...+2 А,Ь +

+ 2АЬ, С,;

2 А2Ь„+ 2 .А Ь„-1 + и -(n-0

+ 2 А2Ь„+ °, Ф 2А2Ь2+

+ 2АЪ =С

2 2»

-и -(n- )

2 А;B„+ 2 А Ъи- +

-(n-2) L

-2

+ 2 A2b„2+ °,.+2 A b +

+ 2АЬ, =С;; !

» ш» или соответственно

)236500 (4) t0!

5 реализуется выражение L + Ab, когда

?.< = ?.2 = !.» = О, то вычисляется только произведение матрицы А на вектор Ь (каждый двухвходовый сумматор 20 блока сумматоров выпоггнен на интегральной схеме и реализует операцию суммирования, когда на его управляющем входе единичный сигнал, и пропускает информац: ю с первого входа на выход без иэменеыия» когда на его управляющем входе нулевой сигнал) ° После подачи исходной информации в схеме устройства протекает переходной процесс, по окончании которого на выходах первого, второго и третьего блоков сумматоров ! первого столбца по выражению (5) вычисляются значения

v (к1 (и- к) (, +2Abk

V (o) v ч (и)

С, =О, С, С,;

v (к) -(n-к) ) " (ки)

С2 + 2 А2Ьи-к = С2

v (о)

С2 О, С2 = С;

"(к»1)

1 ° (5) 25

«(к) .(и-к) ь ч („„)

С; +;b „С .«(01 «(nl

С =О С =С °» (;»

0 ° 1» 2» ° ° ° » D !» > 1» 2» ° ° ° »1»1 °

Однородная параллельная вычислительная система для вычисления произведения матрицы на вектор (фиг. 1) работает следующим образом. На входные шины 11-13 подаются элементы а« а,, а, матрицы А соответственно.

На входйые шины 14-19 подаются зна- 40 чения элементов а,, а 2, а, а а, а матрицы А. Кроме того, на первый 2, второй 2, третий 2 и четвертый 2 разряды первой входной

Ф шины подаются значения разрядов с 45 первого по четвертый Ь,, b,, Ь< и Ь, соответственно первого компонента Ь, вектора Ь, а также на первый 3, 4

1 вторые 32, 4, третий 3, 4 и четвертые разряды 3, 4 второй и тре 50 тьей входных шии подаются значения первых разрядов Ь2, Ь вторых - Ь

Ф Ъ 4

Ъ, третьих Ь, Ь и четвертых Ь

Ф

2»

Ь второго Ь и третьего Ь компонентов вектора Ь . Если иа входные 55 шины 57 подаются значения компонентов L,, L2, L> некоторого вектора L О,, L 2, L ), то в устройстве

4 4 (s) а„Ь2 + агЬ,) - С,;

2 (а2 Ъ, 2 (а,Ъ, соответственно каждое из которых поступает со сдвигом 2 на первый вход первого двухвходового сумматора 20 соответственно первого, второго и третьего блоков сумматоров второ го столбца. В каждом блоке сумматоров 1, начиная с первого, второго столбца, матрицы вычисляются по выражению (5) соответственно значения

С, +2 (а„Ь, +а Ь +а Ь) С,> (и з з р з (М, Э

+a Ь

2к 2

+ а Ь

+ а.Ъ )=С,; (>) +,bç) = С каждое из которых подается со сдвигом 2 на первый вход двухвходового сумматора 20 соответствующего блока сумматоров третьего столбца матрицы. На выходе последнего двухвходового сумматора 20 первого, второго и третьего блока сумматоров третьего столбца матрицы, по выражению 5) образуются значения С»» С » С, (ъ> и д) которые со сдвигом 2 подаются на

1 первые входы первых двухвходовых сумматоров 20 соответственно первого, второго и третьего блоков сумматоров

1 последнего столбца матрицы. И, наконец, на выходах первого, второго и третьего блоков сумматоров 1 последнего столбца матрицы по выражению (5) 123б500 образуются значения компонент С1

С,, С2 = С, С = С искомого произведения матрицы А на вектор Ъ, т.е.

АЬ С (С,, С, Сэ) °

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

Однородная параллельная вычисли10 тельная структура для вычисления произведения матрицы на вектор, содержащая матрицу (m, и) блоков сумматоров, причем каждый блок сумматоров содержит два сумматора, выход первого

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

20 каждый блок сумматоров введены допол™ иительио (m- 2) сумматоров, причем выход i-ro (i * 3, ш"1) сумматора подключен к входу первого слагаемого

25 (i+1)-го сумматора, выход ш-го сумI матора блока сумматоров j-го столбца (j = Г, и-1) и К-й строки (К = 1, m) матрицы поцключен со сдвигом на один раэряц в сторону старших разрядов к вхоцу первого слагаемого первого сумматора блока сумматоров (j+I) -го столбца К-й строки матрицы, входы вторых слагаемых К-х сумматоров блоков сумматоров К-й строки матрицы объединены и образуют К-ю входную шину значений элементов матрицы структуры, входы управления операцией двухвходовых сумматоров блоков сумматоров j-ro столбца матрицы объ единены и подключены к 1-му разряду к-й входной шины задания первого вектора структуры, входы первого слагаемого первых сумматоров блоков сумма торов первого столбца матрицы подключен к входной шине задания второго вектора структуры, выход ш сумматоров блоков сумматоров последнего столбца матрицы образуют выходную шину резулътата структуры.

l236500

Составитель Д, Хан-Магомедов

Редактор П. Коссей Техред Г.Гербер .Корректор М. Максимишинец

Тираж 67! Подписное

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

1!3035, Москва, Ж-35, Рауыская наб., д. 4/5

Заказ Зд93/53

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