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

РГ6 од

,, 0 г) и ,-САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ' ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

На правах рукописи

АльМассри Мухаммад Исмаил

РАЗРфЩО-ПАРАЛЛЕЛЬШЕ ПРОЦЕССОРЫ ОБРАБОТКИ ВЕЩЕСТВЕННЫХ ЧИСЕЛ В НЕП03ИЩ0НШХ СИСТЕМАХ СЧИСЛЕНИЯ

Специальность: 05.13.05 - Элементы и устройства вычислительной техники и сиетем управления

АВТОРЕФЕРАТ диссертации на соискание ученая степени кандидата технических ноук

Санкт-Петербург - 1993

Работа выполнена в Санкт-Петербургском Государственно] электротехническом университете

•Научный руководитель -доктор технических наук КОКАЕВ О.Г.

Официальные оппоненты: доктор технических наук, профессор Куприянов Ы.С.. кандидат технических наук Баклан Б.А.

Ведущая организация - Санкт-Петербургский институт

точной механики и оптики

Защита диссертации состоится щ1$83 г.

в /часов на заседании специализированного совете К 063.36.04 Санкт-Петербургского Государственного влекротех-нического университета по адресу: .197376, Санкт-Петербург, ул. Проф. Попова,' Б.

О диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан " •/ " ^ 0 1993 г*

Ученый секретарь

специализированного совета Юрков г

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Эти решения связаны, как правило, с большими ппаратурными затратами, что делает необходимым поиск новых этрадиционных . методов и алгоритмов представления, реобравования и обработки данных. Таким компромиссным между астродействием и аппаратурными затратами методом явлг.этся рименение разрядно-параллельной обработки чисел, при которой ргументами операций выступают не сами числа, а их разрядные резы (РС), т.е. одноименные разряды. А нетрадиционным ме-эдом повышения точности ВУ является применение для представ-эния и обработки чисел системы счисления в остаточных классах ЗСОК), в которой отсутствует межразрядный перенос между ачетами чисел по разным модулям и отсутствует необходимость кругления результатов.

До сих пор метода разрядно-параллельных и'Ш вычислений ад множествами операндов и обработки вещественных чисел в ЗОК развивались независимо друг от друга, что выразилось на элысо в отсутствии разрядно-параллельных структур роцесссров, предназначенных для работы в ССОК, но и в

отсутствии алгоритмов контроля и коррекции результате многоопершццшх вычислений в ССОК. Из сказанного и внчокак цель, предмет я методика диссертационного исследования.

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

В соответствии с поставленной целью основными 3aÄa40N работы являются:

анализ особенностей безошибочных вычислений (БОВ) представления и обработки вещественных чисел в непоз® ционных системах счисления в разрядно-параллельном виде;

- классификация РП арифметических устройств построение обобщенной структуры процессора БОВ;

- разработка и оценки эффективности РП алгоритмов структур устройств прямого и обратного преобразований дробе в целые числа, вычисления наименьшего целого частного (н.ц.ч и мультипликативно обратного элемента (МОЭ) числа по мода лю, преобразования целых чисел из двоичной системы счисленк •(2-й CG) в COOK и обратно, контроля и коррекции результате арифметических операций в GGOK, включая вычисление ранге чисел, их суммы и произведения;

- блочный синтез структуры процессора, определен! областей его практического применения и решение прикладнъ задач.

Предметом исследования являются аппаратурные спосоС "интерпретации РП вычислений над вещественными числами в ССОН

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

Научная новизна заключается в разработке алгоритмичес ких и структурных основ построения разрядно-параллальни арифметических процессоров для обработки вещественных чисе (ВЧ) в непозиционных системах счисления (РППСОК).

Да защиту выносятся следующие научные результаты:

- сформулированы и доказаны утверждения о ранге суш

I-чисел и произведения двух чисел, а также об однозначном 1рямом и обратном преобразованиях дробей Фарея (ДФ) в целые гисла и построены на их основа соответствующие алгоритмы;

- разработаны алгоритмы одновременного выравнивания юрядков N-позиционных дробей, вычисления целой части, ранга i обратного элемента числа по модулю, прямого и обратного преобразований целых чисел из 2-й CG в ССОК:

- приведены разработанные алгоритмы вычисления и треобразования ВЧ ' в ССОК к разрядно-параллельной форме.

Практическую ценность работы представляют:

- структуры разрядно-параллельных арифметических устройств ■ выравнивания порядков N-позиционных дробей, вычисления целой части, вычета, ранга и МОЭ числа по модулю и прямого и эбратного преобразований целых чисел из ССОК в 2-ю СС;

- оценки эффективности разработанных структур;

- пакет прикладных программ преобразования и обработки вещественных чисел и обращения матриц в ССОК.

Внедрение результатов работы. Полученные в диссертационной, работе теоретические и практические результаты использовались при проведении

научно-исследовательских работ студентов на кафедре ВТ СПбГЭТУ.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на научно-технических конференцйях профессорско-преподавательского состава во Львовском политехническом институте в 1589 г. ив СПбГЭТУ в 1990-1992 гг. •

Цубликации. По теме диссертации опубликовано 4 печатных работы.

Структура ц объем работы. Диссартационнай работа состоит из введения, трех глав с выводами, заключения, списка литературы, включающего Б4 наименования. Основная часть работы изложена на 179 страницах машинописного текста. Работа содержит 29 рисунков и 4 таблицы. Приложения изложены на' 29 страницах и содержат I рисунок и 10 таблиц.

- Л -

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматриваются определение, особенности и практическое применение БОВ'для точного решения плохо-обусловленных задач и алгоритмов, не допускающего ошибок округления. Подробно анализируются принципы и особенности пред-ота'ления, преобразования и обработки в ССОК разных множест! вещественных чисел, включающих как целые, так и рациональные, как ' положительные, так и отрицательные, приводятся определения основных величин и констант, необходимые для обработка вещественных чисел в ССОК, к которым относятся: диапозон системы, елементы ортогональных базисов с соответствующими m весами, аддитивно обратный элемент (АОЭ) и МОЭ и ранг числе по модулю и др. Обсуждаются принципы представления рациональных вещественных чисел в р-адической системе в виде бесконечного р-адического полинома или конечного его отрезка (кода Гензеля). Эта система эквивалентна одаомодульной ССОК сс степенным модулем, в которой как и в ССОК отсутствуют ошибки округления, но как и в позиционных системах счисления (ПСС) присутствует меяфазрядный перенос между членами полинома.

Охарактеризуем основные достоинства ССОК, к которые можно отнести:

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

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

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

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

Здесь же приводятся анализ РП обработки чисел и класси-

Ьикация известных РП арифметических устройств. Предпринимавт-:я попытка объединить достоинства РП вычислений и ССОК и на юновании отмачешшх в результате их анализа и классификации 1ринципов разработать соответствующие вычислительные структуры. Эти принципы включают:

- таблично-алгоритмическую обработку множества чисел;

- матричную интерпретацию обработки PC;

- использование ПЗУ в качества элементной поддержки зычислительных структур;

- формирование двоично-взвешэнного значения переноса;

- коррекцию результатов вычислений посредством вычисления их рангов;

- временное совмещение вычислений над операндами и их рангами;

- замену дробных чисел их эквивалентными целочисленными представлениями.

В этой главе также разрабатывается обобщенная структура РППСОК, основу которого составляет вычислительное ядро (ВЯ), аппаратно. реализующее основные функции процессора и включающее следующие блоки:

- входной преобразователь (ПрБ), обеспечивающий выравнивание порядков N-позиционных дробей, прямое и обратное преобразование ДФ в целые числа, вычислений целой части частного по модулю и перевод целых чисел из 2-й CG в ССОК;

- блок коррекции результатов вычислений (БКр) и выходной преобразователь, обеспечивающий вычисление рангов чисел, ранга суммы N-чисел и произведения двух чисел, а также перевод чисел из ССОК в 2-ю СС;

вычислительный блок (ВБ), обеспечивающий выполнение РП многооперандной операции сложения, умножения и вычисление МОЭ числа по модулю. Он же выполняет вычислительную часть алгоритмов преобразования данных и коррекции результатов их обработки.

Архитектура РППСОК относится к типу СКВД - одиночный поток команд, множественный поток данных.

Кроме вычислительного ядра в состав РППСОК входят центральное устройство управления и память операндов

4 А ... а™

... с£ 9

^ а? Ф т и. ¿г ... (Х^,

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

Главной особенностью устройства выравнивания порядко; 'позиционных дробей является одновременное приведение порядко! Л-позиционных дробей к единому (самому старшему) порядку. Имея матрицу порядков дробей

1 =

в которой в общем случае

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

V 3, 3=ТТш а* « а| - ... - а*. (I)

В работе предлагается следующий алгоритм выравнивания: берется 3-й разрядный срез матрицы порядков (начиная сс старшего) и анализируется, если в нем выполняется условие (I), то осуществляется переход к следующему РС, в противно* случае к младшим разрядам порядков, имеющих в анализируемом РС нули, прибавляются единицы и одновременно с этим га мантиссы сдвигаются на один разряд в сторону старших разрядов. Процедура повторяется, пока условие (I) не выполнится для 3-го анализируемого и всех РС матрицы Ъ.

Устройство выравнивания, порядков Я-позиционных дробей состоит из счетчиковой памяти порядков К счетчиков о разрядностью п-[1об ш]+ I, памяти мантисс на регистрах одвига*, элемента эквивалентности (ЭЭ) для проверю! условия (I) в двух групп элементов И для стробирования на ЭЭ разрядов РС порядков и управления сдвигом регистров мантисс и счетными входами счетчиков.

Максимальное число циклов работы устройства, необходимое для выравнивания матрицы порядков оценивается как Т = (2т - I

Суть операции' вычисления аддитивно-обратного элемента

гасла по модулю (системе модулей) заключается в нахоадении

числа Ь, дополняющего заданное до величины модуля (диапоаона.

системы, модулей) и равного сумме модуля (диапозона системы

модулей) с дополнительным кодом заданного числа

Ь = р + ъ „ . - г доп

Вычисление мультипликативно-обратного элемента числа по этому, модулю (системе модулей) сводится к определению числа Ъ~1, вычет произведения которого на заданное число Ь по модули (диапозону системы модулей) равен единице

ПЛ-'иоар-1 • <2>

В атом разделе предлагаются два алгоритма вычисления ЫОЭ о применением метода подбора значений. В первом в интервале [2,р-1] подбирается число к=Ъ~1, удовлетворящее условию (2). Во втором - в интервале [2,Ь-13 подбирается число к, удовлетворяющее вытекающему из (2) условию:

(1 + кР)п.о1Ъ = 0' (3>

то которому и определяется Ь"1 по формуле

г.мф Ь - [ -Т

где [ ] - обозначает, частное от деления (I + кр) на Ь, к -целое положительное число, значение которого подбирается, пока не выполнится условие (3).

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

Во множестве вещественных чисел важное место занимает подмножество 0 рациональных чисел, округление позиционного ■ представления и результатов обработки которых приводит к значительным ошибкам. Такие ошибки не имеют место в ССОК, гдэ рациональные числа преобразуются в эквивалентные целые, обрабатываются, в результаты преобразуются обратно в соответствующую дробь. Поэтому важным является поиск таки^ полезных подмножеств рациональных чисел, имеющих однозначное прямое и обратное преобразования в целые числа и охватывавших как можно больше дробей, чем и является подмножество Р дробей Фарея, определяемое следующим образом:

Pw - ía/b e Q:' (a,b)»I, O < |a| < w, Ó < |b| < w), где w>0 - целое число, называемое порядком дробей Фарел i определяемое в соответствии с неравенством:

2W2 + I < р .

Таблица I

Число b Обратный элемент Чиоло итераций 2-го алгоритма Число итераций 1-го алгоритма

2 10 I 10

3 13 2 13

4 5 I Б

Б 4 I 4

6 16 Б • 16

7 II 4 II

8 12 Б 12

9 17 8 17 "

ю 2 I 2

II - 7 4 7

12 8 Б 8

. i3 3 2 3

14 16 II • 15

• 15 14 II 14 . ".

16 6 Б 6

17 9 8 9

18 18 17 18

P¿V<2>- 91 1к2 Р"1 di 2 к}1170 1=2 Г

В отличие от известных алгоритмов прямого и обратно! преобразований дробей Фарея в целые числа, таких как алгорэт Евклида, предполагвпций определить мнокество; решений выделить в атом множестве единственно правильное, в алгорзи преобразования дробей Фарея в целые числа черев обратш элемент, который выполняется в двух шагах:

1 - определение обратного элемента знаменателя ш модуле Ь~1

2 - вычисление вычета по модулю произведения обротног элемента аваменателя на числитель

В работе разработаны альтернативные алгоритмы, преобразования, основанные на расширений алгоритма определения МОЭ о применением метода ШДбора значенийь Суть этих алгоритмов содержится в следугацеМ утверйДении:

Однозначное прямое и обратной преобразования дробей Фаре я а/Ъ порядка V» в целые числа М овеществляется следувдим образом:

1. Если заданная дробь | является цеЛНМ числом 0 < | •= а < ш, то ее целочисленгое представление совпадает с эе значением

М=а.

2. Если -V? < а •• | < 0 , то М - р - а.

3. Если дробь а/Ь являйтся положительной, то ее целочисленное представление вычисляется как

м - рЦ-5] ,

где С 1 - целая часть частного, к - целое положительное число, подбираемое в интервала [1,от-1] и удовлетворяющее условии

* а)шо1 ь "

4» Если дробь а/Ь являегой отрицательной , то

н . ре^-е] ,

гдэ к с (I,»-И а удэвлэтворяет уеяоаии

(кр + р - &)той ь * о. Б. Еслй заданная дробь (ее целочйелвййоэ представление) не удовлетворяет ни одному из перечйолешш четырех условий, то ета дробь не является дробью Фаре я . (целым представлением какой-либо дробй Фарея).

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

^т«- ктах" Я ~

а при преобразовании целых чисел в дроби Фарея равняется

Ч^Г

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

памяти числа 2*р (1=1,п), которые суммируются на N-арном сумматоре, образуя число kp + I, (кр + а, кр + р - а). Вычет атого числа проверяется в устройстве вычисления н.ц.ч. и если он будет равен нулю, то на второй выход устройства выводится целая часть как отыскиваемое значение, и работа устройства заканчивается, иначе повторяется процедура для другого к.

Алгоритм и структура вычисления н.ц.ч. и вычета числа по модулю сдираются на табличное представление частичных н.ц.ч. и вычетов чисел 21, 1=1.п по модулю, хранящихся ь двух, блоках памяти. Соответствующие строки 8тих таблиц возбуждаются единичными разрядами заданного числа, находящегося в линейке индикаторов, после чего частичные н.ц.ч/ и вычеты суммируются на отдельных N-арных сумматорах. Полученный промежуточный вычет заносится в линейку индикаторов для повторения процедуры, а промежуточное ц.ч. суммируется с полученным его значением на предыдущем шаге. Эта процедура повторяется пока промежуточное ц.ч. не будет равным нулю, тогда проверяется промежуточный вычет, и если он больше модуля, то к целой части прибавляется еушица, а на выходы устройства выводятся н.ц.ч. и вычет числа по заданному модулю, иначе они выводятся без изменения.

Максимальное, число циклов работы устройства вычисления н.ц.ч. будет составлять

Т =

П2 zhaoü р

1=0_____

Р

+ I, п - разрядность исходного числа А.

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

а затем вычисляется н.ц.ч. и вычет Аи по диапазону

системы г„=

а

■ш-

Апсс = Аи (mod

Структура устройства вычисления ранга числа и его позиционного представления состоит из m таблиц N-арного

сумматора. Время работы устройства определяется, преимущественно временем суммирования m матриц порядком птаэсх

(qmM+nmax), где п™" - разрядность числа В™", qmax - разрядность числа а™**.

Во втором разделе также разрабатываются алгоритмы контроля и коррекции результатов многооперандных арифметических операций, выполняемых в ССОК над ВЧ посредством вычисления р^.гов результатов по рангам обрабатываемых операндов, что не рассматривалось в известной литературе.

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

Утверждение £s. Если в нормированной (для которой mm=I) ССОК с основаниями р., р , системой

* с Ш

ортогональных базисов B1t В2,..., Вп

с соответствующими весами •га1, т2,..., тт и диапозоном P« П р^ заданы числа А^а], а^,. ... , а,},), А2=(а*, а*, ... ,

а^).....А1Г(аЧ» ^.....ат) 0 Ра®'ами ri' тг.....^ » со_

ответственно, то ранг суммы этих N-чисел вычисляется как

n

н m

tv = 2 г, - S 2 1=1 1 з=1

2. а*

i=i

rai

При вычислении ранга произведения двух чисел возможны два подхода:

1. Посредством умножения векторного. представления множимого на скалярную величину множителя.

2. Посредством вычисления векторного произведения сомножителей.

Ввиду сложности решения этой задачи в общем виде (2) и простоты практического ее решения в виде (I) в работе рассматривается первый подход и формулируется и доказывается следующее утверждение.

Утверждение Z^: Если в нормированной ССОК с основаниями

р1< р2..... рю, системой ортогональных базисов В,, В2,..., Вш

о ^соответствующими весами m1, т2,..... тт и диапозоном Р» Пр^ заданы числа .А,-(а], ... , а^), А^Ц. а|.....

Оц,) с рангами rt, rg, соответственно, то ранг произведения этих чисел вычисляется как.

га а 12

- 12 -

ш г а\к

= Г,А„ - 2 i 2

1 2 3=1 L "Р^

ш Г азА1

= г„А. - 2

2 1 3=1 L "Pj

т3 или

га3

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

Третья глава посвящена функциональной и структурной организации РППСОК, структуры его вычислительного ядра, устройства управления, памяти и формата операндов и практического применения процессора для решения прикладных задач. К устройствам ВЯ относятся следующие:

1. Устройство вычисления н.ц.ч. и вычета п-разрядного двоичного числа по модулю (2-я CG -> ССОК).

2. Устройство преобразования дробей Фарея в целые числа.

3. Устройство преобразования целых чисел в дроби Фарея.

4. Устройство одновременого выравнивания порядков N-позициошшх дробей.

Б. Рьзрядно-параллельное суммирующее устройство (РПСУ). 6. Матрично-множительно-суммирующее устройство (ММСУ). 7'. Устройство вычисления обратного элемента числа по модулю.

8. РП устройство вычисления ранга числа и перевода его из ССОК в 2-ю СС.

9. Устройство вычисления .ранга суммы N-чисел и ранга произведения двух чисел.

Устройства ВЯ работают по РП принципу, поэтому основу ВЯ составляет РПСУ, которое в зависимости от формы обработки многоразрядного переноса может быть выполнено в разных вариантах.

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

затраты памяти для больших разрядностей таблиц могут оказаться большими, в ВЯ включен матричный умножитель (МУ) с расширенными функциональными возможностями для выполнения в нем вместе с операцией умножения двух операндов и операции двоичного суммирования N-операндов, количество единиц всех PC которых одновременно вычисляются в суммирующих счетчиках, после чего суммируются за один такт на суммирующих элементах МУ. Число сталируемых на МУСУ операндов N и их разрядность должны удовлетворять следующим неравенствам:

n sS'q2 и Clogg N1 + I £ q1, где q1, q2 - разрядность ино-^тоого и множителя МУ. соответственно.

Дополнительные аппаратурные затраты при этом составляют Удоп = Ч^2(Триг + ЗЛЭ), Триг - Д-триггер; ЛЭ - логический элемент типа И, ИЛИ.

Время умножения двух чисел остается неизменным и определяется временем распространения переноса в сумматоре равным

Ту = «Ii + Чг "

где тр — время формирования сигнала переноса в одноразрядном сумматоре-.

Время суммирования N n-разрядных чисел будет равно

т = т + т сум у *ст*

где Тст - время работы счетчика подсчета чиола единиц в разрядном срезе.

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

Выбрано ассоциативное микропрограммное устройство управления (АМПУУ) с унитарным кодированием состояний, операторную схему алгоритма которого можно преобразовать в сетевую, позволяющую . отдельно минимизировать- управляющую и информационную части микропрограмм. АМПУУ обладает вдвое лучшей характеристикой, • чем устройство управления, построенное на основе ПЗУ.

Разработаны следующие два формата данных:

- формат целых чисел,' состоящий из вычета (ов) числа по модулю(ям) системы и ранга етого числа;

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

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

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

В качестве примера применения РППСОК рассматривается задача решения системы линейных алгебраических уравнений (СЛАУ) о использованием преобразования матриц. Так СЛАУ, представленная в матричной форме

Ах=С,

где A(mxn) - матрица коэффициентов при неизвестных, х - п-вектор неизвестных, С - ш-вектор постоянных, имеет разного рода решения:

1. х= А-1С, если матрица А квадратная, невырожденная, где А-1

- обратная матрица для А, вычисляемая из условия

А-1А = АА"1 - I, где I - единичная матрица.

2. х= А"С + (I -А~А)г, если А -прямоугольная или вырожденная матрица, где А- - g-обратная матрица для А, г - произвольный вектор.

Среди известных g-обратных матриц в атом разделе вычисляется g-обратная матрица Мура-Пенроуза как наиболее полезная и гарантирующая единственное решение совместной а единственное нормальное псевдорешение несовместной СЛАУ. Эта

матрица вычисляется методом Эрмита по следующей матричной формуле:

А* = ATMrAAT ,

т R

где А - транспонированная матрица для А, М- - g-обратная рефлексйЁная матрица для А. Разработан и промоделирован в среде С алгоритм вычисления g-обратной матрицы Мура-Пенроуза в COOK. Головная программа включает функции:транспонирования, окаймления, умножения, разокаймления вещественных матриц, вычисления МОЭ , метод исключения Гаусса, прямое и обратное преобразования ДФ в целые числа.

Был произведен ориентировочный расчет аппаратурных затрат разработанных арифметических устройств в К-МОП технологии, в библиотечных элементах и временных затрат в числе тактов на логическом элементе. Основные результаты проведенных расчетов сведены в следующую таблицу:

Таблица 2

J* п. . Название устройства Объем аппар.' затрат в БЭ Число циклов рвботы уст-ва

X РПСУ шестнадцати 16-разрядных элементов 805 20

2 Устройство выравнивания порядков

.16-дробей III9 16-31

3 Устройство вычисления н.ц.ч. 16-разряд-

ных чисел по модулю 3 2355 1-9

4 Устройство вычисления МОЭ 16-разряд-

ного числа по модулю 105 3320 I-I03

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

порядка w=7 в целые числа 3332 I-S

6 Устройство преобразования целых чисел в

дроби Фаре я порядка '.т=7 Б891 1-42

7 Устройство вычисления ранга тлела и

перевода его из ССОК с основаниями

(3,5,7) в двоичную СС 5674 I

8 Матрично-множятельно-сукмируюЕев

устройство 16x16 4560 Т X

В приложении сравниваются табличные, алгоритмические и таблично-алгоритмические методы построения процессоров. Освещаются примеры, иллюстрирующие предложенный в работе механизм вычисления ранга суммы Л-чисел и произведения двух чисел. Дорабатывается структура устройства, выполняющего эти вычисления, и приводятся оценки его эффективности. Даются необходимые рекомендации в вычислении и определении таблиц констант, независящих от входных данных с целью автоматизации процесса проектирования процессоров СОК. Так, например, 1 построены таблицы вычетов чисел 21(1=0,15) по простым модулям (2 - 100), таблицы ортогональных базисов и весов этих базисов нормированных систем (3,5,7), (3,5,7,13), (5,11,13,17,59), (3,5,7,11,13,17,19,29), таблицы вычетов взвешенных сумм разрядных срезов в системе модулей (3,5,7,13).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЧ

В результате проведенного исследования были получены следующие результаты:

1. Показана практическая целесообразность применения РП вычислений в безошибочной обработке вещественных чисел в ССОК и построения РП арифметического процессора СОК.

2. Сформулированы и доказаны утверждения о ранге . суммы Л-чисел и произведения двух чисел и также об однозначном прямом и обратном преобразованиях дробей Фарея в целые числа.

3. Разработаны и приведены к разрядно-параллельной форма алгоритмы выравнивания Л-позиционных дробей, прямого и обратного преобразований дробей Фарея в целые числа и целых чисел из 2-й СС в ССОК и обратно, вычисления обратного элемента, ранга и целой части числа по модулю, определения ранга суммы Л-чисел и произведения двух чисел.

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

5. Разработаны формат и память данных.

6. Построены таблицы независящих от структуры данных основных констант некоторых конкретных нормированных ССОК, позволяема автоматизировать процесс проектирования РППСОК.

7. Разработан с среде С пакет прикладных программ для

преобразования и обработки вещественных чисел . и обращения матриц в ССОК.

ПУБЛИКАЦИИ ПО ТЕМЕ'ДИССЕРТАЦИИ

1. АльМассри М.И., Голембо В.А., Кокаев О.Г. и др. Контроль разрядно-параллельных арифметических операций в системе остаточных классов // Технические средства автоматизации измерений и руководства научными исследованиями. Сб. науч.-тр., Львов: Вестник ЛПИ. - Вып. 267.- 1992.- С. 3-8.

2. АльМассри М.И., Голембо В.А., Кокаев О.Г. Расширение функциональных возможностей матричных умножителей // Контрольно-измерительная техника. - Республ. межвуз. н.-т. сб., Львов: Изд. при ЛГУ, "Вица школа".- Вып.49.- 1993.- С. 82-85.

3. АльМассри' М.И. и др. Расширение функциональных возможностей матричных умножителей // Структура и математическое обеспечение специализированных комплексов. -Сб. науч. тр. (Изв. Ленингр. влектротех. ин-та). Вып. 423. -Л., 1990. - С. 22-27.

.4. АльМассри .М.И., Бура А.Т., Голембо В.А. О представлении и . минимизации . дискретного описания сложных символов // • Контрольно-измерительная техника. - Республ. межвуз. н.-т. сб.- Львов:Изд. при ЛГУ, "Вища школа",- Вып.48. - 1992.- С. I3I-I34.

Поди, к печ. 23.11.93 Формат 60x84 1/16.

Офсетная печать. , Печ.л. 1,0; уч.-изд.л., 1,0. Тираж 100 экз. Зак. 254 Бесплатно.

Ротапринт С.-Ш.ГЭТУ 197376, Санкт-Петербург, ул.Проф.Попова, 6