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

санкт-петербургскш государственный электротехнический университет

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

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

РАЗРЯДНО-ПАРАЛЛЕЛЬНЫЕ ПРОЦЕССОРЫ ОБРАБОТ1Ш ВЕЩЕСТВЕННЫХ ЧИСЕЛ В НЕПОЗИОДОННЫХ СИСТЕМАХ СЧИСЛЕНИЯ

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

Автореферат

диссертации на соискание ученой степени кандидата технических наук

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

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

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

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

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

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

Защита диссертации состоится 1293

Г.

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

О диссертацией можно ознакомиться в библиотеке университета.

Г

Автореферат разослан " у " —.. 1993 г.

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

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

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

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

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

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

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

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

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

В соответствии с поставленной целью основными задачами работы являются:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- Л -

краткое содержание работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

•» 1 _2 _.тп

х1 а1 ... а1

г =

<*2 а| . ... а™ 1 „г

< 4 -

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

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

V 3, 3=ТТт а3 = а| - ... = а3. (I)

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

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

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

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

ь = р + ь .

- г доп

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

1ЬЬ_11шо<1р= 1 • <а>

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

(1 + ^тоЛ ъ " <3)

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

1+кр

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

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

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

Fw - {a/b e Q: (a,b)-I, □ < |a| < w, ü < |b| < w), где w>0 - целое число, называемое порядком дробей Фар-jfl в определяемое в соответствии с неравенством:

2W2 + I < р .

Таблица I

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

2 10 I 10

3 13 2 13

4 Б 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 Б . в

. 13 3 2 3

14 15 II • 1Б

■ 15 14 II 14 .

16 6 Б 6

17 9 8 9

18 18 17 18

PsV<2)- 91 1=2 Х Р-1 Щ 2 к| 170 1=2 ■

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

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

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

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

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

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

М=а.

2. Если -w $ а - | < 0 , то М - р - а.

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

м - р-р] ,

где I ] - целая часть частного, к - целое положительное число, подбираемой в интервале tl.w-Il и удовлетворяющее условию

(кр + B)mod b - 0.

4. Если дробь а/ъ являемся отрицательной , то

м» ре-^-э] ,

где к t tl,w=ll а удовлетворяй® условию

(кр + р - a)ft6d b - о. 5> Если аадишая дробь (ее целочйСЛЗйное представление) не удовлетворяет ни оДйому из перечйСЛЭШШХ четырех условий, то эта дробь не является дробью Фарея - (целым представлением какой-либо дроби Фарея).

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

^шаж- W W " б при преобразовании целых чисел в дроби Фарея равняется

hnex- <WtaM> - "<» ~ I>-Структуры устройств вычисления МОЭ прямого и обратного преобразований ДФ в целые числа построены на основе ассоциативной памяти н содержат суммиругсдай счетчик (линейку индикаторов), в котором подбирается число к. Единичные разряды числа к возбуждают соответствуйте? хранящиеся в

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

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

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

Т =

*2 2^0(1 р 1=о__

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

Алгоритм вычисления ранга гА числа А=(а1, а2..... ат)

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

АИ

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

системы г,=

А

■14

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

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

(qmBX+nm<uc), где nma* - разрядность числа В^", qma* - разрядность числа а™**.

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

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

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

1 - d. га

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

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

сф,..., Aj-ia^, ... , а^) с рангами г,, г2,..., г^ ,. соответственно, то ранг суммы этих N-чисел вычисляется как

N

N m

Гу = 2 г, - S ^ 1=1 1 3-1

±h 1

md

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

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

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

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

" ; Утверждение iL . Если в нормированной ССОК с основаниями Pji pg,..., pm, системой ортогональных базисов В,, В2,..., 13

ш

с соответствующими весами га,, т_,..т и диапозоном

ш > . 1 с . п

,2

П р^ заданы числа А^Са], а^.....а^), А2=(а*. а|, ... ,

с рангами г1, г2, соответственно, то ранг произведения этих чисел вычисляется как

Vs " V2

ГА_А. = Г2А1

- 12 -

ш Г

2 -А-

L Pj

m Г CljA.

s

J=1 L PJ

m^ или

rai

2 1

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

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

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

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

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

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

Б. Разрядно-параллельнов суммирующее устройство (РПСУ).

6. Матрично-мнокительно-суммирующее устройство (ММСУ).

7. Устройство вычисления обратного элемента числа по модулю.

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

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

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

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

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

п « и Ио^ И] + I < , где q1, q2 - разрядность множимого и множителя МУ. соответственно.

Дополнительные аппаратурные затраты при этом составляют

7доп - Ч^^ТР"- + ЗЛЭ>-Триг - Д-триггер; ЛЭ - логический элемент типа 2И, 2ИЛИ.

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

Ту = <41 + Ча -

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

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

т е Ф + Т сум Ау ^ст*

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

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

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

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

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

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

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

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

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

Ах=С,

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

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

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

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

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

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

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

А+ = АТМЙААТ ,

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

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

Таблица 2

й Объем Число

аппар." циклов

п. . Название устройства затрат работы

в БЭ уст-ва

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

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

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

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

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

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

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

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

порядка уг=7 в целые числа 3332 1-6

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

дроби Фарея порядка 5891 1-42

7 Устройство вычисления ранга числа и перевода его из ССОК с основаниями

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

8 Матрично-г>яохеттольно-суг-?лгрующее

устройство 16x18 45еч I

В приложении сравниваются табличные, алгоритмические и таблично-алгоритмические методы построения процессоров. Освещаются примеры, иллюстрирующие предложенный в работе механизм вычисления ранга суммы N-чисел и произведения двух чисел. Дорабатывается структура устройства, выполняющего вти вычисления, и приводятся оценки его эффективности. Даются необходимые рекомендации в вычислении и определении таблиц констант, независящих- от входных данных с целью автоматизации процесса проектирования процессоров СОК. Так, например, • построены таблицы вычетов чисел 2i(i=Q,I5) по простым модулям (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. Сформулированы и доказаны утверждения о ранге. суммы N-чисел и произведения двух чисел и также об однозначном прямом и обратном преобразованиях дробей Фарея в целые числа.

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

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, Санкт-Петербург, ул.Проф.Попова, Б