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

(22) Заявлеко 03,01,77 (21)2440108 Кл,8 Р 15/20 исоедииекием заявки И Гвсударетааакьй аакатат СИР аа делам кзабратала и аткрютан3) Приорите бликовако 05,09,79, Бюллетень .% 3 та опубликования описания 10,09,79 53) УДК 681.1(088.8) В, М, Глушков, В, А. Вышинский, 1 С Л,Иваськов и 3, Л. Рабинович 2) Авторы изобретения на Ленина Институт кибернетики АН Украинской ССР) Заявитель ЦИАЛИЗИРОВАННЫЙ ПРОЦЕССОР результатов, управляющие входы-выходы которых соединены с входом-выходом блока управления, блок памяти, сумматор-вычптатель, умножитель, причем выходы регистров исходных данных соединены с соответствующими входами умножителя и сумматора-вычитателя, выход которого соединен со входом первого регистра результата, выход блока памяти соединенпервыми входамп регистров исходных дных 11. м такой машины являетс Недостате низкая п и больш конечном счете приходится иметь дело с системами линейных уравнений с очень большим числом переменных (до 10 переменных), В результате возникает необходимость в выполнении операций над ля рицами того же порядка, что и решаемые системы уравнений, т,е, порядка 10бВычисление значения суммы а; Ь традиционными л 1 етодали в этом случае требует значительных вреленных затрат. не ицу в ий су 20 кой сушциализи- и на 2, нных и лее бли зк им по техн иче изобретению является сп ост ронная счетная ма истры исходных д ованная эле шая р сод Изобретение относится к области вычислительной техники и может быть использовано при построении высокопроизводительных специализированных ИВМ, предназня ченных для реализации преобразований линейной алгебры, в частности умножения5 матрицы на матрицу.Известно арифметическое устройство специализированной вычислительной машины, работающей в системе счисления оста 1 а точных классов 1и реализующей пре. образование линейной алгебры, в частности умножения матрицы на матрицу. Недостатком такого АУ является сравнительно невысокое быстродействие и повышенный15 расход, оборудования, вызываемый тем,что, в частности, умножение матрицы на матр м связано с вычислением значе,с. Ь зводительность. При решечисла прикладных задач в684550 20с 2. Рабинович 3, Л, и др, Специализированная электронная счетная машинаСЭСМ, Киев, изд, АН УССР, 1961,3. Акумский И. Я. и др, Машинная 077, арифметика в остаточных классах, М.Сов, радио", 1968. Составитель И, Хазоваактор Л, Утехина Техред Н, Бабурка Корректор Ю. Макаренко Зака з 52 89/4 3П 1 1 ИИП Тираж 780 Государственног делам изобретен осква, Ж, Ра илиал ППП "Патент", г. Ужгород, ул. Проектная,выход сумматорФвычитателя соединенвходом-выходом блока управлении,Источники информации, принятые вовнимание при экспертизе1, Авторское свидетельство480кл, 5 06 Я 7/50, 1975,Подпикомитета СССРй и открытийушская наб., д, 4/56845Пелью изобретения является повышениепроизводительности устройства,Поставленная дель достигается введением в предложенный процессор дешифрятора констант "нулевизации, дешифратора"свертывания латрицы дешифратора промежуточных преобразований "развертывания" матрицы, дешифратора "развертывания" матрицы и второго регистра результата, При,етом выходы первого и второго 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 49 и дешифрятоо 6 соответственно, каналы 26 - 30, по которым информация из регистра 3 поступает в регистр 1 и 2, дешифратор 5, сумматор-вычитатель 9 и ум.ножитель 10 соответственно, каналы 31- 35, по которым информация поступает из регистра 4 в регистры 1 и 2, дешифратор 5, сумматор-вычитатель 9 и умножитель 10 соответственно, канал 36, по которому информация с дешифратора 6 поступает ня регистр 7, каналы 37, 38, по которым информация из сумматора-вычитателя 9 поступает на регистры 7 и 11 соответственно канал 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 поступает на вход дешифратора 12.Для данного специализированного процессора принципиально важное значение имеет выбор способа представления перерабатываемой информации. В качестве такого способа использована система счисленияя остаточных классов (ССОК ) . Главным преимуществом ССОК в данном процессоре являются удобство выполнения преобразования. исходной матрицы к отвечающему ей действительному числу, простота выполнения умножения и удобство перехода от действительного числа к отвечающей ему матрице.В соответствии с выбором ССОК каждый из дешифраторов 5, 6, 8 и 12 представляет собой некоторый набор дешифраторов по каждому из модулей .;Р выбран ной ССОК. Сумматор-вычитатель 9 содержит 1 модульных сумматоров-вычитателей, выполняющих сложение (вычитание) по соотВетствующим модулям РЯо 1 Умножитель 10 содержит к множительных схем и модулям РР. Регист 1оы 1-4, 7 и 1 1 рассчитаны на прием и хра нение чисел представленных в ССОК, с диапазоном, состоящим из М модулей, Бифря по кяждомч зябадч такой ССОК представ68455 лена в двоичной системе счисления, ДлиО О 2 31п 1 12 22 32 п 2 45 С 1 Оп 2 п Ьп оп 50 Преобразование исходной матРицы к видУ обеспечивающему эффективное выполнение55 операции умножения матриц, связацо с использованием двух стандартных операций- операции свертывания" строк и операции "свертывания столбцов. ца регистра и соответственно схем сумматора-вычитателя, умножителя и дешифратор в рассчитана ня рабочий диапазон смодулями, удовлетворяющий условиюпредставления матрицы - результата умножения в виде одного действительного числа. Этот диапазон обычно определяетсяЪп 1 т 1 двоичными разрядами, где д -порядок матрицы, а гп - количество дво Оичных разрядов представления элементовчисел л 1 атрицы.Процессор работает в трех основныхрежимах;- преобразование исходных матриц к 15чиду обеспечивающему эффективное выполнение собственно операции умножения,- умножение матриц,- преобразование некоторого специального способа представления матрицы, явля ющейся результатом умножения матриц, кисходному виду,Кроме того ца осц.вации предлагаемого устройства в случае необходимости мсжет быть также выполнено преобразование 25исходной информации из позиционной системы счисления в ССОК и из ССОК в позиционную систему счисления, а также изССОК одного типа в ССОК другого типа(операция расширения представления чиЭОсел в ССОК).Работа процессора в режиме преобразования исходных матриц к виду, обеспечивающему эффективное выполнение операции ул 1 ножеция, состоит в следующем,35Предположим что числовая информация,представляющая элементы исходных матриц,записана в блок памяти в ССОК диапазона. Предположил; также, что преобра 40зовывается матрица М следующего вида:о6Сущность операции "свертывания" строк покажем ця примере свертывания двух Ьерхних строк матрицы 1 й , В качестве Исходной для преобразования информации используем квадратную матрицу М 1 второго порядка, являющуюся некоторым элементом двух рассмотренных строк матрицы (Й:21 Мф22При выполнении операции "свертывания строк элементы О О 1, л 1 атрицы М записываются соответственно в регистры 3 и 4 процессора.Действительные числа, представляющие элементы с 1,и Скак и все11 числа, представляющие остальные элементы матрицы М заданы в диапазоне 1. В результате операции "свертывания строк, выполняемой цад матрццей 1 й элементы с 41 и а,2 заменяются одним элементом - действительным числол 1 диапазона Я ) РДля этого элементы с 1 и С 1 также должны11быть предварительно представлены в этол 1 диапазоне Я . Такое представление в процессоре выполняется ца основе регист-, ров 1-7, сумматора-вычитателя 9 и дешифратора 5. При этом используется известный алгоритм (так называемый алгоритм нулевизации"), описанный, например в выражении (3).Для реализации этого алгоритма требуется С - 1 сложение, где Я - количество модулей ССОК диапазона РРасширенное представление элементова 11 и азаписывается соответственно в регистры 1 и 2. На их место в ре- гистры 3,4 записывается следующая пара элементов 1221 и с 122 матрицы М1После получения расширенного представления элементов с 11 ц а 2 цачицаеч ся выполнение собственно операции свер- тывания" строк, При вь 1 полцеции этой операции информация из регистров 1,2 подается на дешифратор 6. Дешифратор 6 реализует таблицу соответствия такого типа, при котором паре входных чисел а 1.1 О 12 ставится в соответствие действцгельное число, отвечающее комплексному числу вида О + О 1,11 12,5 1 Йерехог от комп.и.ксного .ислв к действиетсыюму может быть выполнен, например,В соотве ствии с пр 1 Вилвми, описаннымиВ выражении (3), И)формация с выходадешифрвторв 6 поступает на регистр 7. Изрегистре 7 она переписывается в блок памяти. Действительное число, с помощьюкоторого заменяется комплексное число,требует для своего представления в дввраза больше количества двоичных элемен- Отов блока памяти, чем этого требуют действительная и мнимая части комплексногочисла. Из этого следует, что замена комплексного числа действительным никакихизменений объема блока памяти не требует 5Те ячейки, которые использовались дляхранения комплексного числа, теперь используются для хранения действительногочисла,Числа с , сМ 12 с регистров 3,2соответствейно подаются на сумматорвычитвтель 9 (сложение выполняется вдиапазоне), и полученная нв его выходе сумма ( с 321 + с 11 ) записывв 25ется в регистр 7 с последующей перезапись(ъ(в регистр 3,Числа а,г,г и о 11 с регистров 4 и1 соответственно подаются на сумматорвычитатель 9 (число а 1 вычитается изчясла 1г . Полученная на его выходе раз 30ность записывается в регистр 7 с последующей( перезаписью в регистр 4.Проведенные преобразования соответствуют представлению исходной квадратнойматрицы в следующем виде:35 с 4 (ог - с 14) 41а-(о 1" 1 г а 42 О О+АО а- Д",а 41 1 Й 11 45 Нартнойих стр 50 Этой матрице ставится в соответствие действительное число, отвечающее матр иц Р 1 ) Р 2п 2 ) ( Р 1 21 1) Ы 2 Х 11 ЗЙ аа, а -с 2 О(а г)5й 11 О(с"г 2 1) Как уже отмечалось, матрица евмеияется действительным числом этом кончается первый цикл ствнд операции "свертывания двух верхи матрицы МДальнейшее преобразование мвт связано с использованием матрицы Этй ) 1 Т(И Ц(1 ПО.1 У ОН 1 т )К, 1 Ев ( СС=(И Л(- вого столбца В)ят ненулевой столб(.ц )торого слагаемого в выражении (3). И качестве правого столбца использованы элементы а 11 1) двух верхних строк матрицыч,Применим преобразования к матрице (4), аналогичные тел, которые имели место в первом цикле стандартной операции свертывания строк проводимой нвд мвтрицей (2). Третий цикл преобразований связан сиспользованием матрицы вида правый столбец которой олучен допиоьванием к левому столбцу, полученному при выполнении второго цикла, очередных элементов ц 41, О 42 двух верхних строк матрицы,й . После реализации некоторого числа циклов преобразований промежуточной матрицы в конечном счете получим матрицу вида где А , А н - члены, учитывающие результаты предыдущих преобразований. От этой матрицы в соответствии сописаинымц аьпде преобразованиями осуществляется переход к матрице+ А соотве ения этих элеменеся в регис лок памяти. к первой и, повторяется д, строкам. цы М нечетПроцедура, п второй строкам затем к 3 и 4, Причем если по ный, добавляетс которой приним имененная матрицы М 5 и 6 ит ядок матри атрице исходного вид ни 0 се элеменначение,я строка,ают нулев цця не используются. дстввленны.выполняетсл 4 ноженцяпредлагаемо вух я в ССОРв регистрультвт умня 10 звпц 3, вгтыво -ц, таким образом, в полученное представление матрицы М вносится некотораяпогрешность. Замегим (это важно прцвыполнении обратного представления формыпредстввлецця результата умножения кматрице исходного порядка), что заменаматрицы эквивалентна рописыва рой строках исходной м тов -о; - яц йп 2ственно. Числовые зна тов с их знаками, находя рах 12, переписываются В результате применения описанной процедуры ко всем строкам матрицы М получается некоторая новая матрица с вдвое меньшим числом строк,.полученная40 матрица представляет исходную матрицу М с погрешностью, определяемой введением дополнительного столбца в матрицу Миз соответствующих дополнительных элементов, получаемых в результате чказанных преобразований строк. Если описанную процедуру преобразования строк применить теперь (соответствующим образом) к столбцам, их число также будет уменьшено вдвое. Особенность использования описанной процедуры состоит в том что теперь уже берутся не две верхних строки матрицы М, а два ее крайних столбца - первый и второй, И алементы, над которыми выполняется циклическая операция, выбираются от верхних к нижним. Полученная таким образом матрица представляет исходную с погрешностью, эквивалентной введению в исходную матрицу М некоторой дополнительной строки с элементвмц, получаемыми в результате преобразования столбцов. Эта дополнительная строка в матрице записывается как ее нижняя строка, Итак, в результате выполнения описанных преобразований матрицы"справа налево" и сверху вниз, исходная матрица порядка П сводится к матрице порядкаи Последовательное применение этого преобразования позволяет свести с некоторбй погрешностью исходную матрицу произвольного порядка, к матрице первого порядка т.е, заменить с чекоторой погрешностью исходную матрицу некоторым действительным числом. В результате выполнение операций над матрицами может быть сведено к операциям над действительными числами, В частности, умножение двух матриц может быть заменено умножением двух действительных чисел, Возникающая здесь погрешность результата цз-за пог решности сведения исходных матриц к действительным числам может быть ликвидирована при обратном преобразовании действительного числа - результата умножеВ случае, когда выполняется умножение двух матриц ( например матрицы Я нв матрицу Ь ), мвтрица-множимое Й преобразуется, начиная со строк, а матрица- множитель Ь - начиная со столбцов. Дополнительная строка матрицы Л и дополнительный столбец матрицы Ь в образовании элементов искомой матрццы-произведения не используется, и, таким образом, эти строка и столбец в образовании. погрешности не участвуют, Прц выполнении описанных преобразований матриц элементы дополнительной строки матрицымножцмого и элементы дополнительного столбца матрицы-множителя в блоке памяти не запоминаются и в процессе вычислеУмножение матриц, предействительными числамиизвестными методами передействительных чисел. Бпроцессоре оно выполняетсно из чисел записываетсявторое - в регистр 4. Режения с выхода умножцтеется в блок памяти,) )исли г ) препстявлеццье в С( ОК,комплексцьй диапазон которой имеет норму Я, записываются в регистр 11,откуда они подаются ця дешифратор 12.Этот дешифратор построен тяк, что каждой пере ) и г ня его выходе появляются действительная сМ и мнимая бчасти наименьшего вычета комплексного.числе по комплексному модулю, норме ко торого равна Ю 1, Итак, с выхода дешифратора 12 с и а 2 соответственно записываются в регистры 1 и 2. Выполненное преобразование действительногочисла О можно условно рассматриватьквк развертывание" действитег.ного числа, представляющего .результат умноженияисходных матриц, в матрицу вида Расс) )отрцм работу предлагаемого) процессоре в режиме обратного преобразования специального представления матрицы к исходному виду, т,е. в режиме, когда от действительцого числа, представляюшего некоторую матрицу, осуществляется переход к этой матрице, Указанный переход от числя к матрице связан и в случае "свертывания" матрицы к числу с использованием двух стандартных операцийопеоации развертывания" столбцов и операции "развертывания" строк. Действительное число (обозначим его через И. ) из блока памяти записывается в регистр 7. Определяем комплексное число СфДкоторое соответствует этому действительному числу 4 . Переход от действительного числа к: Комплексному числу может быть выполнен, например, с правилами, описанными в выражении (3),(7)а ц е О Полезной информацией для нахождения искомой матрицы является часть матрицы(7), я именно верхняя ее строка. Нижняястрока является избыточной, в результатечего онв может быть опушена, Итак, описанное выше преобразование позволилопоставить в соответствие действительное 30число с матрице (8). о а ,Дальнейшее развертывание" матрицы (8)35 связано с выполнением стандартной операции "развертывания" строк матрицы,с (п Р 2(2) где ", и б соответственно действительная и мнимая части рассматриваемого комплексного числя (в данном случае комплексное число 01 имеет только действительную часть, которая совпадает сО О =О мнимая часть равна нулю,2 4. т,е. ЬО ), Величина ( Р + Я )- норма комплексного числа-дивпязона, поИ45 которому определяется наименьший вычет комплексного числа О; С выхода дешифряторв 8 числа Г , Р подаются нарегистры 3 и 4) где их представление с помошью сумматора-вычитателя 9, регист 50 ров 1 и 2 и дешифрятора 5 расширяется от диапазона представления в ССОК сч компле)4 сцыми модулями с нормои ( Р + 2 ).до диапазона с нормой М ( р 2 Ф я ), где К удовлетворяет 55 условиюИ 2 и2 2 МИз регистра 7 число ц .поступает нв дешифратор 8, в котором структурно зафиксирована таблица переходе от действительного числа к числам Г и Г , удовлетворяющим условию(5)1 Сущность этой операции состоит в следующем, Возьмем число с 2 из регистра 2. При этом учитывается то что число а ( Я Это условие накладывает отпечаток на описанную процедуру тем, о2чт ССОК, в которой проводятся преобразования, имеет диапазон, в двв раза меньший, чем диапазон при развертывании числя с (здесь сравнение диапазонов осушествляется в логарифмическом масштабе). Вы - полнимним над этим числом аналогичную описанной выше процедуру замен его комплексным числом. Затем о комплексного числа,соответствуюшего О 2 цереидем к матрице видаСпециализированный процессор содержащий регистры исходных данных и результатов, управляющие входы-выходы которых соединены с входом-выходом блока управления, блок. памятируммвтор-вычитатель и умножитель, причем выходы регистров исходных данных соединены с соответствующими входами умножителя и сумматора-вычитателя, выход которого соединен со входом первого регистра результата, выход блока памяти, соединен с первыми входами регистров исходных данных, о т л и ч а ю ш и й с я тем, что, с целью повышения производительности, в него введены дешифратор констант "иулевизвции, дещифратор "свертывания" матрицы, дешифратор промежуточных преобразований развертыванияматрицы, дешифратор развертывания матрицы и второй регистр результата, причем выходы первого и второго регистров исходных данных через дешифратор "свертывания" матрицы соединены с первым входом второго регистра результата, второй вход которого соединен с выходом сумматоравычитателя, выход .умножителя соединен с третьим входом второго регистра результата и вторым входом второго регистра исходных данных, четвертый вход второго регистра результата соединен с выходом блока памяти, а выход - с входом блока памяти, вторыми входами третьего и четвертого регистров исходных данных и через дешифратор промежуточных преобразований развертывания" матрицы - с третьими входами третьего и четвертого регистров исходных данных, выходы которых соединены с третьим и четвертым входами первого и второго регистров исходных данных и через дешифратор констант нулевизвции" с пятым входом сумматора-вычитателя, выход первого регистра результата соединен через дешифратор .развертыванияматрицы с пятыми входами первого и второго регистров исходных данных, выходы которых соединены с входом блока памяти, управляющий вход 17 6845модульных операций в то время квк классический метод перемножения матриц требует думножений и п сложенийдействительных чисел,Лппаратурные затраты в предлагаемомпроцессоре определяются аппаратурнымизатратами на п 2. процессоров с диапазоном до 30 двоичных разрядов,Общий объем ЗУ этих процессоров, измеряется объемом, необходимым для хранения перемножаемых матриц в их обычномисходном представлении. Однако можноввести избыточность в процессор, котораяпозволить не учитывать погрешность итогда происходит дополнительное повышение производительности, В этом случаетребуется выполнение одной операции умножения и (4 СОд П ) ) сложений действительных чисел в ССОК,Увеличение объема блока памяти процессора позволяет отказаться от выполненения операций расширения (нулевизации)представления Р и Г. при "развертывании" чисел в матрице и комплексных со 25стввляюших 04 и 42 при "сворачиванииматрицы в действительное число. Тогдадля умножения матриц потребуется однаоперация умножения и 4 й сложенийдействительных чисел в ССОК.30Следует отметить, что в предложенномпроцессоре с целью экономии аппаратурыможно не "сворачивать" матрицу до однЬго действительного числа, а лишь сократить ее порядок, тогда в процессоре при35перемножеиу матриц добавится еше выполнение 1 х операций умножения и(;) операций сложения, где к - число, показывающее во сколько раз уменьшается порядок матриц,40Производительность в этом случаерастет по кубическому закону, а аппаратурные затраты - по квадратному законупо сравнению с изменением коэффициента сокрашения порядка матрицы. Твк 45если процессор сокращает порядок матрицы в 2 раза, то при этом производительность повышается в 8 раз а аппаратурные затраты - в 4 раза. Если порядокматрицы сокращается в 8 раз, соответсчвенно производительность повышается в512 рвз и затраты на аппаратуру - в 64раза и т,д,Необходимо отметить, что предложенное сокращение количества операций умно жения и сложения приводит к увеличениюразрядности обрабатываемых чисел, Возникает трудность, состоящая в реализации этих операций в огромном диапазоне. 50 18Однако использование в вычислениях ССОКпозволяет ликвидировать этот недостаток,сведя, например, время выполнения операции умножения (в этом случае) ко времени умножения двух остатков по модулю,двоичное представление которого измеряется обычно 8-16 разрядами. формула изобретения