Специализированный процессор

Специализированный процессор

Иллюстрации

Показать все

Реферат

 

ИФ

Союз Советск их

Социалистических

Республик (6I ) Дополнительное к авт. свид-ву (22) Заявлено 03.01.77 (21 )2440108/18-24 с присоединением заявки И (23) Приоритет

Опубликовано05.09.79. Бюллетень .% ЗЗ

Дата опубликования описания 10.09.79 (5f)M. Кл.

S 06 Р 15/20

Гвсударстааааьй ааиатат

СИР аа делам кзабратака» и ата ютан (53) УД1(681,14 (088.8) В, М. Глушков, В. А. Вышинский, Ki Л,Иваськов и 3, Л. Рабинович (72) Авторы изобретения

Ордена Ленина Институт кибернетики АН Украинской ССР (7I ) Заявитель (54) СПЕЦИАЛИЗИРОВАННЫЙ ПРОЦЕССОР

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

5 матрицы на матрицу.

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

15 расход, оборудования, вызываемый тем,что, в частности, умножение матрицы на матрицу в нем связано с вычислением значений суммы $ Q Ь„.

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

Недостатком такой машины является ее низкая производительность. При решении большого числа прикладных задач в конечном счете приходится иметь дело с системами линейных уравнений с очень большим числом переменных (до 10 переменных}. В результате возникает необходимость в выполнении операций над матрицами того же порядка, что и решаемые системы уравнений, т,е, порядка 10

Вычисление значения суммы go; Ь1 традиционными методами в этом случае требует значительных временных затрат.

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

"свертывания матрицы, дешифратора промежуточных преобра зова н ий "развертывания" матрицы, дешифратора "развертывания" матрицы и второго регистра результата, При,етом выходы первого и второго 1О регистров исходных данных через дешифратор "свертывания" матрицы соединены с первым входом второго регистра результата, второй вход которого соединен с выходом сумматора-.вычитателя, Выход умно- жителя соединен с третьим входом второго регистра результата я вторым входом второго регистра исходных данных. Четвертый вход второго регистра результата соединен с выходом блока памяти, а выход — с вхо- о дом блока памяти, вторыми входами третьего и четвертого регистров исходных данных и через дешифратор промежуточных преобразований развертывания матрицы с

25 третьими входами третьего и четвертого регистров исходных данных, выходы которых соединены с третьим и четвертым входами первого и второго регистров исходньц данных и через дешифратор констант "ну—

30 левизации" с пятым входом сумматора-вычитателя. Выход первого регистра результата соединен через дешифратор "развертывания" матрицы с пятыми входами первого и второго регистров исходных данных, выходы

35 которых соединены с входом блока памяти.

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

Структурная схема специализированного процессора показана на чертеже . Процессор содержит регистры 1 — 4 исходных данных, дешифратор 5 констан" "нулевизации", дешифратор 6 "свертывания" матрицы, второй регистр 7 результата, дешифратор 8 промежуточных преобразований развертывания" матрицы, сумматор-вычитатель 9, умножитель 10, первый регистр

11 результата, дешифратор 12 "развертывания" матрицы, блок памяти 13, блок 14 управления, каналы 15 - 19, по которым информация из блока памяти 13 поступает в регистры 1 -4 и 7 соответственно, каналы

20 — 22, по которым информация из регистра 1 поступает в дешифратор 6, блок памяти 13 и сумматор-,.вычитатель. 9 соответственно, каналы 23 - 25, по которым информация из регистра 2 поступает в блок памяти 13, с мматор-вычитатель

50 4

9 и дешифратор 6 соответственно, каналы

26 — 30, по которым информация из регистра 3 поступает в регистр 1 и 2, дешифратор 5, сумматор-вычитатель 9 и умножитель 10 соответственно, каналы 3135, по которым информация поступает из регистра 4 в регистры 1 и 2, дешифратор

5, сумматор-вычитатель 9 и умножитель

10 соответственно, канал 36, по которому информация с дешифратора 6 поступает на регистр 7, каналы 37, 38, по которым информация из сумматора-вычитателя 9 поступает на регистры 7 и 1 1 соответственно, канал 39, по которому информация с выхода дешифратора 5 поступает на вход сумматора-вычитателя 9, каналы 40, 41, по которым информация с выхода умножителя 1 0 поступает на входы регистров 7 и 2 соответственно, каналы 44 — 43, по которым информация с выхода регистра 7 гоступает на вход блока памяти 13,, вход дешифратора 8 и входы регистров 3 и 4 соответственно, каналы 46,47, по которым информация с выхода дешифратора 8 поступает на входы регистров 3 и 4 соответственно, каналы 48, 49, по которым информация с выхода дешифратора 12 поступает на входы регистров 1 и 2 соответственно, канал 50, по которому информация с выхода регистра 11 поступает íà вход деш ифр атора 1 2.

Для данного специализированного процессора принципиально важное значение имеет выбор способа представления перерабатываемой информации. B качестве такого способа использована система счисления остаточных классов (ССОК ) . Главным преимуществом ССОК в данном процессоре являются удобство выполнения преобразования исходной матрицы к отвечающему ей действительному числу, простота выполнения умножения и удобство перехода от действительного числа к отвечающей ему матрице.

В соответствии с выбором ССОК каждый из дешифраторов 5, 6, 8 и 12 представляет собой некоторый набор дешифраторов по каждому из модулей ...,Р выбран ной ССОК. Сумматор-вычитатель

9 содержит k модульных сумматоров-вычитателей, выполняющих сложение (вычитание) по соответствующим модулям р .,Я

1) k

Умножитель 10 содержит k множительных схел ï модулям P ... Т . Регист ) т оы 1-4, 7 и 11 рассчитаны на прием ихранение чисел представленных в ССОК, с диапазоном, состоящим из k модулей, Инфра по каждом n ri nv такой ССОК представ»

68455 лена в двоичной системе счисления, Дли021 ОУ ...Оп, 12 22 32 п2

45

О Cl О п 2п Ъп пп

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

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

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

Ъn m двоичными разрядами, где n— порядок матрицы, а гп — количество дво- 1О ичных разрядов представления элементовч исел м ат рицы.

Процессор работает в трех основных режимах;. — преобразование исходных матриц к 15 чиду, обеспечиваюшему эффективное выполнение собственно операции умножения, умножение матриц, — преобразование некоторого специального способа представления матрицы, явля-20 юшейся результатом умножения матриц, к исходному виду, Кроме того, на основании предлагаемого устройства в случае необходимости мс жет быть также выполнено преобразование 25 исходной информации из позиционной системы счисления в ССОК и из ССОК в позиционную систему счисления, а также из

ССОК одного типа в ССОК другого типа (операция расширения представления чиЭО сел в ССОК).

Работа процессора в режиме преобразования исходных матриц к виду, обеспечивающему эффективное выполнение операции умножения, состоит в следующем, 35

Предположим, что числовая информация, представляюшая элементы исходных матриц, записана в блок памяти в ССОК диапазона . Предположим также, что преобра40 зовывается матрица М следующего вида: о

Сушность операции "свертывания" строк покажем ня примере свертывания двух верхних строк матрицы /Й . В качестве исходной для преобразования информации используем квадратную матрицу М второго порядка, являющуюся некоторым элементом двух рассмотренных строк матрицы (Й:

11

М= аде (2) гистры 3,4 записывается следующая пара элементов 1 и с матрицы М

После получения расширенного представления элементов а „„ и а„ начинаегся выполнение собственно операции свертывания" строк. При выполнении этой операции информация из регистров 1,2 подается на дешифратор 6. Дешифратор 6 реализует таблицу соответствия такого типа, при котором паре входных чисел с 11

О 2 ставится в соответствие действигельное число, отвечающее комплексному числу вида

0 + 0 (, 11 12

При выполнении операции "свертывания«

f строк элементы a с1, матрицы М записываются соответственно в регистры

3 и 4 процессора.

Действительные чигла, представляющие элементы а и а, как и все

1Ъ числа, представляюшие остальные элементы матрицы М заданы в диапазоне 9

В результате операции "свертыващщ строк, выполняемой над матрицей

1 элементы сМ11 и O> > заменяются одним элементом — действительным числом диапазона Q ) Р.,Для этого элементы с1 и а „также должны

11 быть предварительно представлены в этом диапазоне Я . Такое представление в процессоре выполняется на основе регист-, ров 1-7, сумматора-вычитателя 9 и дешифратора 5. При этом используется известный алгоритм (так называемый алгоритм нулевизации"), описанный, например в выражении (3) .

Для реализации этого алгоритма. требуется С - 1 сложение, где Я вЂ” кОЛИчЕство модулей ССОК диапазона Р

Расширенное представление элементов а11 и с „записывается соответственно в регистры 1 и 2. На их место в ре7 (6м1;;, Эта (1 1T((нU(I полу 1оlfа тf(к, l1 Kа !с(..тfй л(» вого столбца взят ненулевой столб.ц второго слагаемого в выражении (3). И качестве правого столбца использованы элементы а11 1 а двух верхних строк матрицы M

Г(ер lxoff oT ко;,(плексного -кисла к действительному может быть выполнен, например, В COOTBe f ствин С flpc(BHJIQMB, OIIHCAHHbfMH в выражении (3), Информация с выхода дешифратора 6 поступает на регистр 7. Из регистре 7 она переписывается в блок памяти. Действительное число, с помощью которого заменяется комплексное число, требует для своего представления в два раза больше количества двоичных элемен- 10 тов блока памяти, чем этого требуют действительная и мнимая части комплексного числа. Из этого следует, что замена комплексного числа действительным никаких изменений объема блока памяти не требует15

Те ячейки, которые использовались для хранения комплексного числа, теперь используются для хранения действительного числа, Числа с121, с11 с регистров 3,2 соответствейно подаются на сумматорвычитатель 9 (сложение выполняется в диапазоне 1 ), и полученная на его выходе cyMMa (с32.1 + с11 ) записыва25 ется в регистр 7 с последующей перезапись в регистр 3.

Числа а и о11 с регистров 4 и

1 соответственно подаются на сумматор вычитатель 9 (число а1„вычитается изчяс. лай2 . Полученная на его выходе раз30 ность записывается в регистр 7 с последующей перезаписью в регистр 4.

Проведенные преобразования соответствуют представлению исходной квадратной матрицы в следующем виде:

Применим преобразования к матрице (4), аналогичные тем, которые имели место в первом цикле стандартной операции свертывания строк проводимой над матрицей (2).

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

С1 (Ф22 С114) 41 а -(с1 1 42) а42 правый столбец которой получен дописыванием к левому столбцу, полученному при выполнении второго цикла, очередных элементов А41 О42 двух верхних строк матрицы,й .

После реализации некоторого числа циклов преобразований промежуточной матрицы в конечном счете получим матрицу вида

4„где А, А 1 - члены, учитывающие результаты предыдущих преобразований. От этой матрицы в соответствии сописаинымн выщэ преобразованиями осуществляет ем переход к матрице

Как уже отмечалось, матрица

041 О1а

12 11

45 заменяется действительным числом. На этом кончается первый цикл стандартной операции свертывания двух верхних строк Этой МВТрНае ставится в соответствие матрицы М действительное число, отвечающее матриДальиейшее преобразование матрицы Я связано с использованием матрицы

Р1 ) Р2

) (Р1

21 12) Ы (4 )

22 11) ЗЙ

)») и, таким образом, в полученное представление матрицы M вносится некоторая погрешность. Замегим (это важно при выполнении обратного представления формы представления результата умножения к матрице исходного порядка), что замена матрицы

f(a„)+A ) 0

L (о„-А) о нв мвтрицу

20 эквивалентна дописыванию в первой и второй строках исходной матрицы И элементов -а 2 — А" К а 4 + А соответп2 rI4 ственно. Числовые значения этих элемен25 тов с их знаками, находящиеся в регистрах 1,2, переписываются в блок памяти.

Процедура, примененная к первой и второй строкам матрицы М, повторяется З0 затем к 3 и 4, 5 и 6 и т.д. строкам, Причем если порядок матрицы М нечетный, добавляется строка, все элементы которой принимают нулевое . значение.

В результате применения описанной процедуры ко всем строкам матрицы М получается некоторая новая матрица с вдвое меньшим числом строк,.(»олученная

40 матрица представляет исходную матрицу.

М с погрешностью, определяемой введением дополнительного столбца в матрицу

М, из соответствующих дополнительных элементов, получаемых в результат . чказанных преобразований строк. Если описанную процедуру преобразования строк применить теперь (соответствующим об» разом) к столбцам, их число также будет уменьшено вдвое. Особенность использования описанной процедуры состоит в том, что теперь уже берутся не две верхних строки матрицы М, а два ее крайних столбца - первый и второй. И алементы, над которыми выполняется циклическая операция, выбираются от верхних к нижним. Полученная таким образом матрица представляет исходную с погрешностью, эквивалентной введению в исходную матрицу М некоторой дополни »с льной строки с элел|ентами, получаемыми в результате преобразования столбцов. Эта дополнительная строка в матрице записывается как ее нижняя строка. Итак, в результате выполнения описанных преобразований матрицы

"справа налево" и сверху вниз, исходная матрица порядка 0 сводится к матрице порядка и

2.

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

B случае, когда выполняется умножение двух матриц (например, матрицы A на матрицу Ь ), матрица-множимое A преобразуется, начиная со строк, а матрицамножитель Ь вЂ” начиная со столбцов. Дополнительная строка матрицы Л и дополнительный столбец матрицы Ь в образовании элементов искомой матрицы-произведения не используется, и, таким образом, эти строка и столбец в образовании. погрешности не участвуют, При выполнении описанных преобразований матриц элементы дополнительной строки матрицымножимого и элементы дополнительного столбца матрицы-множителя в блоке памяти не запоминаются и в процессе вычисления не используются.

Умножение матриц, представленных действительными числами. выполняется известными методами перел4ноже»»ия двух действительных чисел. Б предлагаемом процессоре оно выполняется в CCOK — одно из чисел записывается в регистр 3, в второе — в регистр 4. Результат умнстжения с выхода умножителя 10 записывается в блок памяти 8455u !псла и г, представленнь!е в ССОК, комплекснь!й диапазон которой имеет норму Я„, записываются в регистр 11, откуда они подаются на дешифратор 12.

Этот дешифратор построен тяк, что каждой пере " и !" ня его выходе появляются действительная сМ! и мнимая б части наименьшего вычета комплексного. числе по комплексному модулю, норма ко10 торого равна Nf . Итак, с выхода дешифратора 12 ! и 02 соответственно записываются в регистры 1 и 2. Выполненноее преобразование действительного числа О можно условно рассматривать как развертывание действител ного числа, представляющего .Результат умножения исходных матриц, в матрицу вида этому действительному числу 4 . Переход от действительного числа к: комплексному числу может быть выполнен, например, с правилами, описанными в выражении (3). а (77

С!

?О

Полезной информацией для нахождения ис25 комой матрицы является часть матрицы (7), я именно верхняя ее строка. Нижняя строка является избыточной, в результате чего она может быть опушена. Итак, описанное выше преобразование позволило поставить в соответствие действительное

30 число а матрице (8) .

Г azz) (Ь) дальнейшее развертывание матрицы (8)

35 связано с выполнением стандартной операции "развертывания" строк матрицы. Р-с!,(под P2 ! 2) где С! и Ь - соответственно действи-! тельная и мнимая части рассматриваемого комплексного числя (в данном случае комп-40 лексное число Qf имеет только действительную часть, которая совпадает с

0 (О =О мнимая часть равна нулю, !

Z 3. т.е, Q О ). Величина (P + Я )норма комплексного числа-диапазона, по !

45 которому определяется наименьший вычет комплексного числа а; С выхода дешифрятора 8 числа с Р подаются на ! регистры 3 и 4, где их представление с помошью сумматора-вычитателя 9 регист50 ров 1 и 2 и дешифрятора 5 расширяется от диапазона представления в ССОК с комплексными модулями с нормои (P + Q ) до диапазона с нормой

М (p2 Ф я ), где К удовлетворяет 55 условию

II

Н I

2 2

N„> p w c

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

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

Е ействительное число (обозначим его через И. ) из блока памяти записывается в регистр 7. Определяем комплексное число Qf g (f>J которое соответствует

Иэ регистра 7 число ц .поступает не дешифратор 8, в котором структурно зафиксирована таблица переходе от действительного числа к числам Г и Г, удовf летворяюшим условию

f- a 9+b,q,(«P +% )

2 2

Р= (5)

Сущность этой операции состоит в следуюшем. Возьмем число а2 иэ регистра

2. При этом учитывается то что число а (Я Это условие накладывает отпечаток на описанную процедуру тем, о

f чт

ССОК, в которой проводятся преобразованияя, имеет диапазон, в два раза меньший, чем диапазон при развертывании числя а (здесь сравнение диапазонов осушествляется в логарифмическом масштабе). Вы— полним ним над этим числом аналогичную описанной выше процедуру замены его комплексным числом. Затем о комплексного числа,соответствуюшего Q 2 переидем к матрице вида

13 684550

Поскольку сЕ является элементом краелеее Содержимое регистров 3,4 подается на

2 го правого столбца развертываемой матри- умножитель 10. Результат умножения зацы (8), то правый столбец матрицы (9) писывается в регистр 2, Содержимое реотбрасывается и для дальнейших преобра- гистров 2 и 1 подается на сумматор-вы-. зований рассматоивается матрица читатель(содержимое регистра 2 вычитается нз содержимого регистра 1). Ре!!

Далее число се< также заменяется комплексным числом, которое соответствует матрице

СЕ - СЕ

1 И

f Е!

1 се а

2О

Суммируем матрицу (10) с матрицей (11) так, что матрица-результат будет иметь вид („1 1/) 25

Указанное суммирование выполняется с помощью регистров 1-4 и 7 и сумматора.,зо вычитателя 9. На этом оканчивается один! цикл стандартной операции "развертывания стрОк матреецы.

Полученная матрица (12) соответствует действительному числу Ct Если это

35 действительное число Ц рассматривать как частный случай матрицы, то число ц есть матрица первого порядка. Описанная процедура позволила перейти от матриц первого порядка к соответствующей еи матрице второго порядка (1? ). Для учета погрешности, возникающей в представлении результата умножения из-за погрешности сведения исходных матриц к действительным числам элементы полученной матрицы !

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

Для учета поправки к элементу. Се, запишем из блока памяти в регистры 3, 4 соответственно числа Q r> и Ь представляюшие столбец и строку исходных матриц, записанных для коррекции. зультат операции записывается в регистр

7 с последующей перезап1лсью в or.åpàòèèную память, !

Для учета поправки к элементу а перепишем этот элемент из блока памяти в регистр 1. В регистр 3 -àïè:øå,ì Ьг столбца мнОжимогО! запелсанного В oirepQ тивнуЕО память на этапе пряелого преобразован! я исходной матрицы в чеесло для коррекции. Содержих.ое регистров 3,4 (соответственно числа слг, 6 .1 ) подаются на умножитель 10. Результат умножения записывается в регистр 2. Содержпллое регистров 2 вычитается из содержимого регистра 1 на сумм торе-вычитателе. Результат опер ацеги зап и сы в ается е регистр

7 с последующей перезаписью в блок памят.1. Аналогично корректируются элемен! ты Ь и 6, матрицы, причем при

f 1 корректировке Ь вычисляется поправ1 ка СЕ Е °, Ь ?, а при корректировке 5< — поправка се б г

Таким образом, результатом описанных преобразований явлчется откорректированная матрица второго порядка вида лЕ 2f лг еде ле, е- f2, !2л и С22 — оч корректи рован ные зн аче ния элементов матрицы

Q(!! I! а Ь„ дальнейшие преобразования связаны с переходом от матрицы (13) второго порядка к матрице четвертого порядка. Если описанную циклическую операцию преобразования строк (их разверть вание применить теперь соответствуюшикл образом к столбцам матрицы (13), то их число буде.. увеличено вдвое. Особенность использованич описанной операции состоит в том, что теперь берутся для чзвертыванеея не эл () 8 4, . ) 5 0 д2 П2 (4m 1)4,. 4 сложений и умножений..,Я)лт),l строк, а элементы столбцов. Элемеfl I Il EIQQ которы" и(Bblполняется эте циклическая операция выбираются от нижних

1 элементов столбце к верхним. Применение операции развертывания Ко всем столбцам матрицы (13) преобразует ее к матрице с удвоенным числом столбцов.

Применим теперь к полученной матрице циклическую операцию развертывания" строк, Эге операция увеличит число строк 10 в матрице в два раза. Таким образом поочередное применение к матрице (13) циклических операций развертывания" столбцов и строк позволило нам перейти от матрицы второго порядка (13) к мат рице четвертого порядка. Для полученной матрицы, кек и для матрицы второго порядка, производим ликвидацию погрешности, которая имеет место при переходе от работы с матрицами четвертого порядка к >0 работе с матрицами второго порядке. С этой целью производим с элементами полученной матрицы четвертого порядка аналогичные операции ликвидации погрешности, которые имели место при ликвидации погрешности с элементами матрицы второго порядке (1 3) .

Применяя к полученной матрице четвертого порядка указанные циклические опе.рации "развертывания столбцов и строк, и 30 а также операции ликвидеции погрешности, перейдем от матрицы четвертого порядка к метрице восьмого порядка. Аналогично переходим от матрицы восьмого порядка

3» к матрице 16 порядка и т.д. до порядка, повпедающего с порядком исходных матРнц.

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

При умножении матриц и -го поряд20 ка в предложенном матрично-векторном процессоре требуется

Z(02Д ФЕ 6 40 Л Ф ФЛ аМ) М

q 2 fl 7 72" дг операций расширения цндставле ия чисел (оперений нулевизацни), l где д — операция нулевиз:)цни чисел

2. элементов кв щратной л агрицы порядке число слагаемых в скобках выражения (14) равно

fog

- операция нулевизации чиселfl элементов прямоугольной матрицы с длиной строки q и длиной столбца

Если П1 — число модулей ССОК, в которой представляются элементь квадратной матрицы порядка П, то указанные операции нулевизации для своей реализации требуют следующего числа сложений: для нулевизации Ь требуется (rn-1)

Il сложений, для нулевизеции -- — (2m -1) сло2.

П жений, для нулевизации Ь >- (4IT) -1) слс жений, а для нулевизации д ° -(fl и -1) слоl 2 жений.

Подставив приведенные выше выражения в (14) увидим, что количество,Я/ операций сложения, имеющее место при кулевизациях, независимо от рассл.атриваемого порядка матрицы и диапазоне представления чисел равно п2 р 2(п (п -1))» > (2 m-1)» (ц,„ ) (0,f-f) д2(Pl-1) сложении, а при Гг) =2 (типичный случай pl (4EOg р П ) г1

Итого для умножения матриц в предла"аемом процессоре требуется умножений п »(2)» (О) 4,, 4 ) y g I)2 сннженнд (Н aj>n) и + 4n æ(4 ЕОЯнП)н

Всего для реализации операций Умножения двух матриц в предлагаемом процессоре требуется

-(43og П )f)2» 1,6 п2

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

"иулевизации, дешифратор "свертывания матрицы, дешифратор промежуточных преобразований развертывания матрицы, дешифратор развертывания матрицы и второй регистр результата, причем выходы первого и второго регистров исходных данных через дешифратор "свертывания" матрицы соединены с первым входом второго регистра результата, второй вход которого соединен с выходом сумматоравычитателя, выход .умножителя соединен с третьим входом второго регистра результата и вторым входом второго регистра исходных данных, четвертый вход второго регистра результата соединен с выходом блока памяти, а выход - с входом блока памяти, вторыми входами третьего и четвертого регистров исходных данных и через дешифратор промежуточных преобразований развертывания" матрицы - с третьими входами третьего и четвертого регистров исходных данных, выходы которых соединены с третьим и четвертым входами первого и второго регистров исходных данных и через дешифратор констант нулевизации с пятым входом сумматора-вычитателя, выход первого регистра результата соединен через дешифратор .развертывания матрицы с пятыми входами первого и второго регистров исходных данных, выходы которых соединены с входом блока памяти, управляющий вход17 6845 модульных операций, в то время как классический метод перемножения матриц требует n умножений и п сложений действительных чисел, Лппаратурные затраты в предлагаемом процессоре onределяются аппаратурными затратами на п2. процессоров с диапазоном до 30 двоичных разрядов.

Общий объем ЗУ этих процессоров, измеряется объемом, необходимым для хра- 10 нения перемножаемых матриц в их обычном исходном представлении. Однако можно ввести избыточность в процессор, которая позволить не учитывать погрешность и тогда происходит дополнительное повышение производительности. В этом случае требуется выполнение одной операции умножения и (4 cog> f1 ) fl сложений действительных чисел в ССОК, Увеличение объема блока памяти процессора позволяет отказаться от выполненения операций расширения (нулевизации) представления Р и Г . при "развертывании" чисел в матрице и комплексных со2S ставляюших а< и ag при "сворачивании матрицы в действительное число. Тогда для умножения матриц потребуется одна операция умножения и 4й сложений действительных чисел в ССОК.

Следует отметить, что в предложенном процессоре с целью экономии аппаратуры можно не "сворачивать" матрицу до однЬго действительного числа, а лишь сократить ее порядок, тогда в процессоре при

35 перемножении матриц добавится еще вы попНеННе 4 операций умножения и (ф) операций сложения, где k — число, показывающее во сколько раз умень шается порядок матриц.

Производительность в этом случае растет по кубическому закону, а аппаратурные затраты — по квадратному закону по сравнению с изменением коэффициента сокрашения порядка матрицы. Так 4 если процессор сокращает порядок матрицы в 2 раза, то при этом производительность повышается в 8 раз, а аппаратурные затраты — в 4 раза. Если порядок матрицы сокращается в 8 раз, соответсч 50 венно производительность повышается в

512 раз и затраты на аппаратуру — в 64 раза и т.д.

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

50 18

Однако использование в вычислениях ССОК позволяет ликвидировать этот недостаток, сведя, например, время выполнения операции умножения (в этом случае) ко времени умножения двух остатков по модулю, двоичное представление которого измеряется обычно 8-16 разрядами.

Формула изобретения : . 9 выход сумматор В вычитателя соединен входом-выходом блока управлении.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство Ие 480 кл. Gi 06 F 7/50, 1975.

684550 20 с 2. Рабинович 3. Л. и др. Специализированная электронная счетная машина

СЭСМ. Киев, изд, АН УССР, 1961.

3. Акумский И. Я. и др. Машинная

077,g арифметика в остаточных классах, М., Сов. радио", 1 96 8.

Составитель И, Хазова

Редактор Л, Утехина Техред Н, Бабурка Корректор Ю. Макаренко

Зака з 52 89/4 3 Тираж 780 Подписное

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

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

Филиал ППП Патент, г. Ужгород, ул. Проектная, 4