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

(511 4 С 5 347 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ИСАНИЕ ИЗОБРЕТОРСНОМУ СВИДЕТЕЛЬСТВ(71) Институт проблем моделирования в энергетике АН УССР и Львовский ордена Ленина политехнический институт им. Ленинского комсомола (72) В. А. Гуляев, А. И. Стасюк, В. М. Чаплыга и Ю. Н. Спиченков (53) 681,325(088.8)(56) Авторское свидетельство СССР 9 623204, кл. С 06 Р 7/52, 1978.Авторское свидетельство СССР Н 1056192 е клф С 06 Р 7/70 ф 1983.Стасюк А. И, Однородные многофункциональные матричные процессоры. Киев, (препринт АН УССР, институт элек тродинамики, Р 351, 59 с.),1983, с. 45-49, рис. 14-16.(54) ОДНОРОДНАЯ ПАРАЛЛЕЛЬНАЯ ВЫЧИСЛИТЕЛЬНАЯ СТРУКТУРА ДЛЯ ВЫЧИСЛЕНИЯПРОИЗВЕДЕНИЯ МАТРИЦЫ НА ВЕКТОР(57) Изобретени е относится к вычислительной технике и позволяет сократитьвремя вычислений произведения матрицына вектор. Одновременная параллельнаявычислительная структура для вычисления произведения матрицы на вектор .содержит матрицу (т, ц) блоков сумматоров, причем каждый блок сумматоровсодержит ш сумматоров. В общем случаеизобретение позволяет вычислять. выражение вида Ь + А В, где Ь и В - первый и второй векторы; А - матрица,Результат вычислений формируется навыходах соответствующих блоков сумматоров последнего столбца матрицы.2 ил.. 23Изобретение относится к вычисли-тельной технике и может испольэоваться автономно или в комплексе с цифровой вычислительной машиной для решения систем линейных алгебраических уравнений, обращения матриц и др.Целью изобретения является поныщенке быстродействия эа счет уменьшения числа тактов до одного, 17С,=. а, Ь 1шу 1 О 6500 2шиной устройства (при ш = 3, соотнетстненно 8-10) .Работа однородной параллельнойструктуры для вычисления произведения матрицы А на вектор В, когда каждый компонент результата произведений А Ь С вектора С = (С С,С) формируется какг де а " - элементы матрицы А11ФЬ; - компоненты вектора Ь;С - компоненты вектора С,осуществляется следующим образом.Для организации дднородной вычислительной структуры запишем компоненты С;, Ь; векторов С, Ь и элементы а, матрицы А в разрядной форме как Однородная параллельная вычислительная структура для вычисления про.изведения матрицы на вектор (фиг. ) содержит блоки сумматоров 1, К".разрядов 1 входных шин1, 2, , и) (при К щ 1-3) соотнетственно 2 , 3 4 ; (ш+) входных шин (при" 1-3), соответственно 5 7 и ш выходных шин 8 1 О и К, ь. входных шинщ ш (при ш щ 3), соответственно 11-19. Блоки сумматоров 1 сформированы в виде матрицы размерностью (ш, и), причем каждый блок сумматоров 1 (фиг, 2) содержит ш двухвходовых сумматоров 20, выход каждого -го из которых соединен со входом первого слагаемого (+1)-го сумматора 20. Выход ш-го двухвходоного сумматора 20 -го блока сумматоров 1 К-й строки матрицы соединен со сдвигом 2 со входом первого слагаемого перного двухвходового сумматора 20 (+1)-го блока сумматоров 1 этой же строки матрицы, входы Вторых слагаемых -х двухвходовых сумматоров 20 всех блоков сумматорон 1 К-й строки матрицы объединены и соединены с (К, )-й входной шиной устройства, Управляющие входы -х двухнходовых сумматоров 20 каждого блока сумматоров 1 1-го столбца матрицы объединены и подключены к 1-му разряду К-й входной шины устройства. Вход первого слагаемого первого двухвходового сумматора 20 -го блока сумматоров 1 первого столбца матрицы соединен с (ш+)-й входной шиной (при ш = 3, соответственно 5 7) . Выход ш-го,цвухвходового сумматора 20 -го блока сумсумматоров 1 последнего столбца матрицы соединен с (2 ш+)-й выходной леменА мпонентами Ь; компоненты ве где ко то торов Ь ,.Ьектора С = (С определены н рентных выраж ся -еТогда кч2 ф фффффОСНОВЕний омпоненты С;С, ) могут быследующих рек На фиг. 1 представлена схема однородной параллельной вычислительной структуры для вычисления произведения матрицы на вектор при ш щ 3, ищ 4; на фиг. 2 схема блока сумма торов К-й строки 1-го столбца матрицы е и сформируем матрицу бипар тон нида и векторы бипарных элементов соотвственно(4) О реализуется выражение Ь + АЬ, когда1., = 1, = Ь 2 = О, то вычисляетсятолько произведение матрицы А навектор Ь (каждый двухвходовый сумматор 20 блока сумматороввыпо 2(нен на интегральной схеме и реализует операцию суммирования, когда наего управляющем входе единичный сигнал, и пропускает информац:(ю с первого входа на выход без иэменеыия,когда на его управляющем входе нулевой сигнал)После подачи исходнойинформации в схеме устройства протекает переходной процесс, по окончании которого на выходах первого,второго и третьего блоков сумматоровпервого столбца по выражению (5)вычисляются значения(к) (и-к) ( "(к)С; + 2 АЬщСУ(О) (МС =О С =СкК О 1 29и 1112 фк(2 ЗО Однородная параллельная вычислительная система для вычисления про изведения матрицы на вектор (фиг. 1) работает следующим образом. На входные шины 11-13 подаются элементы ач а, , а, матрицы А соответственно. На входйые шины 14-19 подаются знаЧЕНИЯ ЭЛЕМЕНТОВ а, а 22, а гк а(, а , аки матрицы А. Кроме того, на первый 2 , второй 2, третий 2 и четвертый 2 разряды первой входной шины подаются значения разрядов с 45 первого по четвертый Ь Ь Ь и Ь, соответственно первого компонента Ь, вектора Ь, а также на первый 3 , 4 вторые 3 4 , третий 3 , 4 и четвертые разряды 34, 4 второй и тре 50 тьей входных шии подаотса значения первых разрядов Ьг, Ь вторых - Ьг,Ф4 Ъ, третьих Ь , Ь и четвертых Ь2 Ф Ь второго Ь и третьего Ьз компонентов вектора Ь . Если иа входные 55 шины 5 7 подаются значения компонентов Ь Ь 2, Ь некоторого вектора Ь (Ь 1 2, Ь ), то в устройстве4 4ггЬ 2 + а 2 Ь) Сг ,2 (аг Ъ,2 (а,Ъ,соответственно каждое из которых поступает со сдвигом 2 на первый входпервого двухвходового сумматора 20соответственно первого, второго итретьего блоков сумматоров 1 второго столбца. В каждом блоке сумматоров 1, начиная с первого, второгостолбца, матрицы вычисляются по выражению (5) соответственно значения С, +2(аЬ, +а Ь +а,Ь)=С,; ) . З З 2 з (2)+аЬ) =С каждое из которых подается со сдвигом 2 на первый вход двухвходового сумматора 20 соответствующего блока сумматоровтретьего столбца матрицы, На выходе последнего двухвходового сумматора 20 первого, второго и третьего блока сумматоровтретьего столбца матрицы, по выражению ,5)образуются значения С, Ф С г У С ) у(и (з) которые со сдвигом 2 подаются на первые входы первых двухвходовых сумматоров 20 соответственно первого, второго и третьего блоков сумматоров 1 последнего столбца матрицы. И, наконец, на выходах первого, второго и третьего блоков сумматоров 1 послед. него столбца матрицы по выражению (5)образуются значения компонент С 1С С 2 = С С = С искомого произведения матрицы А на вектор Ъ, т.е,АЪС - (С,у С, Сэ)Формула изобретенияОднородная параллельная вычисли 0 тельная структура для вычисления произведения матрицы на вектор, содержащая матрицу (ш, тд блоков сумматоров, причем каждый блок сумматоров содержит два сумматора, выход первого15 сумматора подключен к входу первого слагаемого второго сумматора, о тл и ч а ю щ а я с я тем, что, с целью повышения быстродействия эа счет уменьшения числа тактов до одного, в20 каждый блок сумматоров введены дополнительно (ш) сумматоров, причем выход -го (з щ 3, ш"1) сумматора подключен к входу первого слагаемого25 (1+1)-го сумматора, выход ш-го сум-матора блока сумматоров 1-го столбца= Т, и) и К-й строки (К = 1, ш) матрицы поцключен со сдвигом на один раэряц в сторону старших разрядов к вхоцу первого слагаемого первого сумматора блока сумматоров (+1) -го столбца К-й строки матрицы, входы вторых слагаемых К-х сумматоров блоков сумматоров К-й строки матрицыобъединены и образуют К-ю входную шину значений элементов матрицы структуры, входы управления операцией двухвходовых сумматоров блоков сумматоров 1-го столбца матрицы объ единены и подключены к 1-му разряду к-й входной шины задания первого вектора структуры, входы первого слагаемого первых сумматоров блоков сумма торов первого столбца матрицы подключен к входной шине задания второго вектора структуры, выход щ сумматоров блоков сумматоров последнего столбца матрицы образуют выходную шину резулътата структуры.Тираж 67 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий