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

РГ6 од

7 гллц. «1-Г.^ САИКТ-ЛЕТЕРЕУРШШЙ

( ^тосу&ьиггвтш элтротвтгшиШ уштегситет

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

Мохамдд Бассам Исмаил

РАЗРВДНО-ПАРАЛЛЕЛи!ЫВ ИРОЩЯСОРУ ОБРАБОТКИ

комшшш чида

Специальность 05.13.05 - элемента и устройства вычислительной техншда и систем управления

АВТОРЕФЕРАТ

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

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

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

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

Официальные оппоненты: доктор технических наук, профессор КУПРИЯНОВ М.С. кандидат технических наук БАКЛАН Б.А.

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

Защита диссертации состоится «//" ШЗНЛ1993 г. а часов на заседания специализированного совета К 063.36.04 Санкт-Петербургского государственного электротехнического" университета по адресу; 197376, Санкт-Петербург, ул.проф.Попова, 5.

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

Автореферат разослан "(9 " /МлХЛ-^ 1993 г.

Учений секретарь специализированного совета

ШЮЗ ».В.

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

Актуальность темы исследования

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

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

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

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

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

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

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

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

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

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

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

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

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

Предметом исследования являются аппаратурные способы интерпретации раэрядно-пвраллельных вычислений над комплексна«! числаыи, представленными в позиционной СС и в остаточных клао-сах.

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

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

На з.эдит5 выносятся следующие научные результата

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

- жонвейерно-зтеравдонЕнЯ алгоритм бескоординатного двоичного предст&алетгя целого комплексного числа;

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

штора и умноиателя двоичных'Комплексных чисел и суша тора вещественных остатков комплексных чисел в системе комплексных оснований не основе матричного умножителя;

- формула для вычисления ранга операции сложения //-ксма~ лексных чисел в непозшдиолной СС.

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

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

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

- машинные программы обработки комплексных чисел.

Внедрение результатов работа. Полученные в диссертационной работе тооретические и практические результаты использовались при проведении научно-исспедователъских работ на кафедре ВТ СПбГЭУ им.В.И.Ульянова (Ленина).

Апробация работы. Основниэ результаты работы докладывались и обсуадались на научно-технических конференциях профес-сорско-Ареподавательского состава СЦбГЭУ им.В.И.Ульянова (Ленина), г.Санкт-Петербурге в 1990-1992 гг.

Публикации: одна статья и двое тезисов.

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

КРАТКОЕ СОДЕРЖАНИИ РАШ№

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

Еескоординатное представление ц.к.ч. в ЭВМ традиционной архитектуры связывается с выбором двоичной СС с основанием (-1+ I ). Предлагается модификация известного способа преобразования ц.к.ч. в двоичный код, описываемые слздуицйш» формулами :

ьа =

~>о — |

1 =

ч=

<*.> * Ь, | ; <£. - I - а0 + Еа

Я 1 '

—+4 н—§—

ГГ)

_-__ , оч ц

где Ь, _ исходные значения действительной и мнимой частей ц.к.ч.; ¿L ~ с -тея компонента двоичного кода ц.к.ч.

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

На рис.1 приведены экспериментальные оценки эффективности бескпордннатной формы представления ц.к.ч. в сравнении с координатной, построенные посредством моделирования алгоритма (I) на ПЭВМ в С++ среде.

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

Время работы Тп преобразователя определяется преимущественно временем работы сумматора

Я ^ % « п. '] [

где п > - соответственно разрядность и количество склады- . васмых чисел.

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

Би/п

о

Рг

/ '

Х^' У

• /-7114 К>!1 -о\ У

л г з н ^ б ? ,1 5 ю « к 13 и (6 (? 19 ¿£> степей*

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

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

0 <¿.2' +с(.2'+.... + о? .

1 Юл

а 2 Я 9. 1 г

в»ж

а. Л О* Л о ^ 0П""' (2)

В„ = о + а,.,2 +— ;

» 1

Б* В* = Л.-2 - А;2 ^ ... • + Яо- 2 1" _ *

где = ■ является арифметическим

весом разрядного среза (РС).

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

к-*.с, барн-Х результата определяются как

1 Яо) , Р- « Кво.о)>

я!*, Р.

(з)

£ - иА*.й-.);

5К в | р„.(|а , К = ^ + 1 г .

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

Согласно формулам (2), (3) разрядио-параллельный суша-тор ц.к.ч. яыеэт счотчвко-таблвчную структуру. Время сложения, а шесте о ним в условие "останова" его работы, определяется неравенством

п„.А ^ т; 4 <4>

где - каксшальвая длина отеранда ва /V одновременно

складывпешх.

Работа комплекснозначного двоичного умножителя строится на формировании косоугольной матрицы частично* произведений я рззрядяо-параллольном сложении ее столбцов. Время работы оценивается формулой

п,+пь 4 V 4 + (5)

где И, и Лг - длины множимого и множителя, пм1, - ^х.).

Машинное моделирование алгоритмов разрядно-параллелыюго сложения и умножения ц.к.ч. на выборко из 100 чисел показало работоспособность форлул (4), (5).

Разрабатываются два варианта построения структуры вычи-тателя - непосредственный (с таблицей вычитания) и косвенный (посредством умножения вычитаемого на (-1) и сложения). С точки зрения удобства разрядно-параллельной интерпретации предпочтение отдается второму варианту.

Аналогичное построение имеет место и для делителя ц.к.ч. -через вычитание, через вычисление мультипликативно обратного элемента 1/Х, где X - модуль ц.к.ч., и умножение. В соответствии о этим разрабатывается конвейерная разрядно-параллельная структура устройства для вычисления этой функции. Величина ускорения вычислений по сравнений с известная итерационным способом линейно зависит от числа п. двоичных разрядов операнда X.

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

- приведение комплексных вычетов к вещеотвеннда; - - построение таблиц изоморфизма;

- преобразование ц.к.ч. в остатках в позиционное представление;

- вычисление рангов чисел;

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

Для устранения таких вычислительных недостатков известных способов преобразования ц.к.ч. в вещественные остатки, ках наличие длинных' операций укнояенвя, деления, вычисления обратных

- а -

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

Этими же алгоритмами и на этоз же структуре преобразователя реализуются операции построения таблиц изоморфизма комплексных вычетов вещественным. Построение указанных таблиц автоматизировано посредством разработки программного обеспечения на языке С44.

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

Шираясь на теорему Гаусса об изоморфизме комплексных вычетов вещественным доказывается оледущее утверждение.

Утверждение I. Если в системе с комплексными основаниями

ш,. -¡-(п, и диапазоном |ш< гп2 ■ т„|| задщны числа

о рангами п гц •• -» ^ соответственно, то ранг еушы чц-пел равен '

Яг = I

- г Ъ - £ I.

где - лесовоз коэффициент ^ -той компоненты ортогонального базиса системы 13.

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

Розрядно-параллельная обработка вещественных вычетов ц.к.ч. опирается на тпбличчцо операции, что при удовлетворении требования однородности соотвотствувдих вычислительных структур обеспечивает и хорошее быстродействие. Однако при модулях высоких порядков, особенно при составных модулях, затраты памяти и временные затрать, но начисление отношения изоморфизма становятся ощутимыми. Для устранения этого препятствия предлагается вести вычисления о комплексными вычетами, представленными в свотеме с основанием (-1+1). Это приводит :с алгоритмической и структурной однородности разрядно-парвллельных процессоров обработки ц.к.ч.

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

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

Применение ТТЛ-технологии при построении раэрядно-парал-лельного сумматора-16-ти 16-ти разрядных двоичных к.ч. позволяет оцонить его скоростные характеристики величина! Т ^ 15,2 ис6к.

Память шерандов, работающая по принципу "трубопровода", строится на сдвйгакюих регистрах.' Чтение и эшгасъ часея в та-

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

Основные элементы устройства ТТЛ - технология KI55, К555 {-задержки КЫШ - технология 56 4, К 176 серии t- задержки

Рг-ры ОЗУД, Рг РС (ИР 10) 15/10 не 110/200 но

С А (Ж?) 15/10 не 110/200 но

С П (ИЕ7) 15/10 не 110/200 но

ПЗУ (128 сл х 9 р) 50 но 150 не

Рг Р (ИР 10) 15/10 не 110/200 не

куп память производится по РС.

Общие аппаратурные затраты при реализации памяти процессора покч могут быть оценены по формуле

а=

где £ - количество операндов; 9 - количество микросхем, необходимое для хранения одного операнда; К- - число блоков ОЗУ данных.

Разрабатываются форматы команд и структура УУ с жесткой логикой. Моделирование работы основных блоков процессора выполнено на ПЭВМ "Макинтош" в среде С+*.

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

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

2. Разработан конвейерно-итерационный алгоритм беско'ор-динатного двоичного представления целых комплексных чисел.

3. Определены правила работы и построены структуры раз-рядно-параллельного сумматора и умножителя двоичных комплексных чисел и сумматора вещественных чисел на основе матричного умножителя.

4. Предложена форлула для вычисления ранга результата операции сложения Ы -комплексных чисел в ненозиционной СС.

5. Построены раарядно-пораллельнне структуры ариЗметиче-1 ских устройств и прших и обратных преобразований комплексные чисел в позиционной и непозиционной СС.

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

7. Дянн оценки эффективности разработанных алгоритмов п отрукгур.

8. Проведена экспериментальная проверка работоспособности предложенных разрядао-параллельных алгоритмов и структур.

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

1. Мохамад Б. и др. Расширение функциональных возможностей типовых матричных умножителей. Л.: Известия ЛЭТИ. 1990. Вш.423. С.22-27.

2. Мохамад 5. Разрядно-параллелькый процессор вычисления элементарных функций. Доклад на конференции: Актуальные проб-лет развития радиотехники," электроники в связи. Материала 47 научно-технической конференции, посвященной да» рдвдо. СП6./Л9Д. 0-во Знание России-. С. 53.

3. Мохамад Б. Разрядно-параллельный суша тор двоичных лош-локспых чисел о основанием (-1+1). Доклад на 48-й научно-технической конференции, посвященной Дню радио. СПб. 1993. С.94-95»

ГГодп. к аеч" Т05Г53 Фориа» БШГВ5 Г7ТЕ7 Офсетная печать Печ.л. 1,0: уч.-иэд.л. 1,0. . Тирая 100 зкэ. Зак. »93. Беошиуно.

Ро5алрия1- С.-Йб.ГЭИ 197376, Санкт-Петербург, ул. Проф. Попова, 5.