Устройство для разбиения матриц

 

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

ГОСУ APC

ПО И БРЕТЕ

ПРИ Т тельн вано ных у реше

Из тельн вано ных у реше являе ва по

Ц функц однов ходно

На схема ональ ного на фи тельн функ з ации ритма перво (61) (21) 22) 46)

А.Н.Б

В. Г. (53) (56 ) № 135 (54 ) (57) СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ вЂ” РЕСПУБЛИК

ТНЕНКЫЙ КОМИТЕТ

НИЯМ И ОТКРЫТИЯМ

СССР

354206

496698/24-24

1 ° 10.88

3.1!.90. Бюл. ¹ 43 .В.Демидов, А.В.Моисеев, идар ь, А. Н. Семашко, иневич и С. Г, Седухин

81. 35 (088. 8) торское свидетельство СССР

206, кл. G 06 F 15/347, 1986.

СТРОАСТ8О ДЛЯ РАЗБИЕНИЯ МАТРИЦ зобретение относится к вычис-,ий технике и может быть использори построении специализирован-. тройств, предназначенных для я систем линейных уравнений. бр ет ение относится к вычислий технике, может быть использори построении специализировантройств, предназначенных для я систем линейных уравненич, и ся усовершенствованием устройставт,св, ¹ 1354206. ь изобретения — расширение ональных возможностей за счет еменного транспонирования исматрицы. фиг. 1 показана функциональная устройства; на фчг. 2 — функциая схема M-го выччслительблока (11-1)К-й строки;

3 — схема первого вычислиго блока K-й строки; на фиг,4 ональная схема блока синхрониФа фиг, 5 — блок-схема алгофункционирования устройства в. режиме. (51)5 0 06 Е !5/347

Цель изобретения — расширение функциональных возможностей устройства за счет одновременно ro транспортиров ания исходной матрицы, Устройство содержит матрицу вычислительных блоков, причем первый вычислительный блок К-й строки матрицы содержит два регистра, арифметическое устройство и коммутатор. Устройство работает в двух режимах. В первом режиме ввод элементов матрицы осуществляется по строкам и так.-.м образом и ходная матри=!а транспонируется. Во втором режиме ввод исходной матрицы осуществляется го столбцам и устройство функционирует аналогично прототипу, 5 ил, У строй ство содержит вы числит ел ьный блок 1 и блок 2 синхронизации, Вычислительный блок (фиг. 2) содержит регистры 3 и 4, .арифметическое устройство 5, коммутатор 6, сумматор 7, регистр 8, первый 9, второй

10, третий 11 и четвертый 12 входы синхронизации, Вычислительный блок (фиг. 3) содержит регистры 13 и 14, арифметическое устройс:во 15, коммутатор 16, входы 17-21 синхронизации, I

Блок 2 синхронизации (фиг. 4) содержит генер атор 22 импульсов, элемент И 23, счетчик 24, триггер 25, блок 26 постоянной памяти, выходы 2730 синхронизации.

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

1608б90 аа" а .. =а, ° 10

iê > tj ц 9 где k I 2...,, р) левую L и верхнюю правую V такие, что L 7=А, причем на главной диагонали матрицы 7 стоят единицы. Преобразование матрицы А= )„а Д выполняется )) по алгоритму исключения Гаусса, в процесс".. которого получаются элементы

1, иы, : ().) (K-<) а „ =а,, А

11 ) (к- i\ а кк () .11 . (- 1 15

Х,) с 1, k+2 в ° ° э 1 kj (z )) 5 1$

Р u = э 1 а ° акк

Для простоты описания работы без, потери общности положим Р=4. Условим . ся, что прием информации во все ре- 2С гистры осуществляется по заднему фронту синхроимпульса, т. е, в конце такта.

Устройство имеет два режима функционирования: в первом режиме ввод и 25 обработка элементов разбиваемой матрицы А осуществляется по строкам; во втором режиме функционирования - по столбцам.

Поступление исходных данных в пер-, 30 вом режиме функционирования организовано следующим образом. На первый вход М-ro вычислительного блока 1 первой строки поступает И-я строка разбиваемой матицы А, Строки подаются со сдвигом на один такт, т.е. элементы второй строки подаются, «ачиная с второго такта, третьей строкиначиная с третьего такта и т.д.

Устройство работает следукщим об- 40 разом.

В первом такте регистр 13. 1. 1 ус- . танавливается в положение "1", .причем 1=и((, элемент а«принимается в регистр 14, 1, 1, причем а« =1< (ь)

Во втором такте элемент и „, =1 принимается в регистр 4. 1.2, элемент с.(ь) принимается в регистр 3. 1. 2, арифметическое устройство 15. 1. l выполняет операцию деления a, /a 1„и 50 (ь) (o) на его выходе формируется частное, равное и которое в конце такта принимается в регистр 13. I.,1.

В третьем такте элемент и равный единице, принимается в регистр

4 ° 1.3Ф элемент а31 — в регистр 3 1.3 ° (о) арифметическое устройство 5. 1.3 выполняет операп ю умножения и íà его выходе формируется произведение 1У (ь)

I(а, равное 1с которое в конце так2! 4) та при.".имается в регистр 8. 1.2 част (о) (о)

° ° ф ное a /а„, равное и<<, принимается в регистр 3, 1.2, арифметическое устройство 15, 1.1 выполняет деление и на его выходе формируется частное (о) у (о) а, /а,, равное и <, которое в кон,це такта прин:)мается н регистр 13.1. 1 °

В четвертом. такте регистр 13.2.2 устанавливается в единичное состояние, причем 1=по, на выходе сумматора

7, 1, 2 получается величина а -а а„ / (о)

2т=1 22 которая в конце прйж мается в регистр 14. 2. 2, величи- на и< =1 принимается в регистр 4.1.4, элемент a4, - в регистр 3. 1,4, вели(о) чина 1 a ) =1,, полученная на выходе арифметического устройства 5. 1.3 в конце такта, принимается в регистр (о) (о)

8. 1.3, величина а2 /а „„и элемент (о)

2) а принимаются соответственно в регистры 4, 1.3 и 3.1.3, частное а< /

/a „) =u 4 с выхода арифметического устройства 15.1. 1 принимается в регистр 13. 1. 1, величина а /а, и эле" (î1 (о) (ь)

19 мент а принимаются соответственно в регистры 4. 1. 2 и 3. l, 2.

В пятом такте величина u =-1 принимается в регистр 4.2. 3, арифметическое устройство 5. !. 3 выполняетс@ (ь) (о) (о) умножение и величина а =а -а, а, /

/а(ь), которая формируется на выходе сумматора 7.1,3 в конце такта, записывается в регистр 3.2. 3, арифме- тическое устройство 15.2.2 выполняет деление и частное а /a =u в (j)/ (л) конце такта принимается в ре;истр

13.2.2, значение произведения

1 а4, = 14, принимается в ре<о) гистр 8, l 4 с выхода арифметического устройства 5 . 1 . 4 величина а /а и (о) (0)

<о)

М 1 элемент: а4. принимаются соответственно в регистры 4 .4 и 3.1.4, а /а,ц и а („- соответственно в регистры

4.1.3 и 3.1,3, а, /a)4 и à 2+ — соот(ь) (о) Ф) ветственно в регистры 4, 1.2 и 3.1.2, частное О/аф =0 записывается в регистр 13. 1.! .

В щестом-десятом тактах устройство работает аналогичным образом.

Поскольку каждый элемент матрицы А в каждом процессорном элементе используется один раз, можно выполнять LVраз ду го щей дую сче, сос

23,, рат дер все вхо адр п 111 тор щее ма ных рой вес что

К-й с б при во ся

15. мен

) дов фор

13,.

5 160 ожение потока матриц, Каждую слеую матрицу можно подавать с И+1акта после начала подачи предыдуматрицы. лок 2 синхронизации работает слем образом. По с:.иналу пуска чик 24 устанавливается в нулевое ояние и открывается элемент И опуская импульсы с выхода генера 22 на вход счетчика 24. Соимое счетчика 24 поступает на кроме одного, разряды адресного а блока 26. На оставшийся разряд ского входа блока 26 поступает или "0" с выхода триггера 25, кой устанавливается в соответствуюсостояние сигналом выбора режиункционирования. С информационвыходов блока 26 сигналы синхроции подаются на входы синхронизавсех блоков 1. о втором режиме предлагаемое усттво функционирует аналогично изному. Отличие заключается в том, в первых вычислительных блоках строки по сигналам синхронизации ока 2 синхронизации блокируется м зл ементо в р аз бив ае мой матрицы торые регчстры 14. р, q, блокчруетабота арифметических устройств .q и разрешаетс:- прохождение элеов с первых информационных выхочерез коммутаторы 16.р,с; на инационные входы,пе", вых регистров

aqэ

8690 6

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

Устройство дпя разбиения матриц

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

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

25 которого подключен к информационному входу первого регистра, выход второго регистра подключен к входу второго операнда арифметического устройства, выход которого подключен к второму

-„0 чнфэ .;,.«;,-:очномy =хо„-,,i комм,- атора ч. ..1ерть: .. и iiRTb! 1 . хо:,ы с. 1-= ронжа ац ".4

Быч 1с ительного элОк и":"кл:0 :с- ьь) оот " в, тственно к у:.:равля .. г1.; в> оду ко: -- . мутатора н к входу у. раьления режимом

"Умно. кение-деление" арифме тичес:;.ого

35 ус:"ройства, 20

2f!

608690 ф у 11

27

И

39

1e0S690

<Ра.4.1.2»:=1; <Р„3.1. 2»: =а г), (о) а Ь.)3.1.! )(= а)г/а = (г)г д

<Рг.4.П :1; <Рг.3.1.3 :-аД;

<Ргй И»=.1-(2 „-4); <Рг412М=а)г /а)г, <Рг 3.127:=агг; (о) .. (о) (о) (о) (2)3 /а)! <)1,3 (о) о) (о) (2) ()) ф

<Ра!3221)=!=иге; <%)4221.=агам=а, аг,/а(„=агг -1

<Рг.4.1.41--1; < г.Л).4) (=а„; (о)

<РгВ13>:=) аз) =Ъ; <Рг.413):=а:о/)а((о); <Рг, 3 j3)(=<2г()

<Рг. 1321) =а (о)/а(;) = ()„, .

<Рг.91.2p:=(г)3/а)), <Рг 312 ):=аг3 (о) (о). . (О) <Рг((23):=1; <Рг32Ъ)=азг аз)-а)г,са), =а (o)„(o) (о);о) () )

<Р )322»(аф< ф o) „() а(() ° (cA8 g 4) t ((pj =)о()<М(4). а)Яа Д(Рг 314»= йФи - б)) -, <Рг.Ъ|З:= ао ;

<Рг).3,ry : =(о(а(о)((о) (о)) (о) ())

6 г3»:=аг(гl/а()| <)М23):=аД

) (о) (») ()) (())

)(а(т М 17 а г@(агг

314». а<о) . г3 13»:=аго,2):= У.г !

"33 33 <) )43» - =()оз (("г"-„ 2 g:=(1ð3= 151:

2(():=Ра го(Ог;<Е2(/У":= ЗГС1, (&324):=-аФ)-аО,.6)3/& =а„., Хг»: g4/агг, <ФЛ23),":,, — ы -) о а, = а

21):= ф; (о) ((о)... (о)

)М:=а /Iа о ° <Рг 3 )4» =. Q, 13»:= У; <Рал13>)=Ф,9 ге — — а,„. (г) s» (о ) ))

59/ абаз го), „(о) гай) а (i). оо |

34» =a4 () (t)344), 1 ((< Р 1444> а (г) а(г) (г/ (г) а Р

<Рг4.3)((=2 ; <Рг,3З.41-=-Ф

Составитель Кухаре2-.ко

Техред 1. .4оргентал ор Н. Тупица

КорректоР С. 2Чекмар ч 378

Тираж 571

Подписное

Государственного комитета по изобретениям и открытиям при ГКНТ СССР

1130."»5, Москва, Ж-35, Раушская наб., д. (2/5 одственно-издательс кий комбинат "Патент" „г, Ужгород, ул. Гагарина, 101

Устройство для разбиения матриц Устройство для разбиения матриц Устройство для разбиения матриц Устройство для разбиения матриц Устройство для разбиения матриц 

 

Похожие патенты:

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

Изобретение относится к вычислительной технике и может быть использовано в универсальных и специализированных арифметических узлах

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

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

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных процессорах для обработки больших массивов данных

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных матричных вычислителей

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных матричных вычислителях

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

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

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных системах для вычисления сверстки

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных системах для вычисления двумерной свертки

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных системах для вычисления собственных значений матрицы (n n)

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

Изобретение относится к области спектрального анализа и может быть использовано при классификации квазипериодических сигналов

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

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