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

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

ш

Мо Чжо Чо

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

Специальность:05.13.05 - Математическое моделирование, численные методы и комплексы программ

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

Москва - 2009г

003479691

Работа выполнена в ГОУ ВПО «МАТИ» - Российском государственном технологическом университс имени К.Э. Циолковского.

Научный руководитель: доктор технических наук

Опадчий Юрий Федорович

Официальные оппоненты: доктор технических наук,

профессор

Руфицкий Михаил Всеволодович

кандидат физико-математических наук доцент

Чумакова Екатерина Витальевна Ведущая организация: ОАО «НПО «ЛЭМЗ»

Защита состоится « 17 » _ ноябрь _2009 г. в ч. 00 мин, на заседании диссс

тационного совета Д 212.110.08 при «МАТИ» - Российском государственном технологическом унивс ситете им К.Э. Циолковского по адресу:121552, Москва, ул. Оршанская, д. 3, ауд. 612а.

С диссертацией можно ознакомиться в библиотеке «МАТИ» - Российского государственного технол гического университета имени К.Э. Циолковского.

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

Телефон для справок 8 (499) 141-94-55

Автореферат разослан « Р> » окТЯЬРЬ 2009 г.

Ученый секретарь диссертационного совета Д212.110.08 Кандидат физико-математических наук

т

Спыну М.В.

ая характеристика работы.

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

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

Значительно сократить затраты и время проектирования можно при построении таких устройств рименением ПЛИС. Данный класс ИС позволяет в короткие сроки реализовать практически любой оритм обработки информации. Этому способствует наличие соответствующих САПР электронных ■м, включающих большое число стандартных мегафункций, предназначенных для проектирован™ онченных узлов устройства. В этом случае разработчику нет необходимости полностью разрабаты-ь схему всего устройства. Достаточно собрать его структуру из уже имеющихся блоков.

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

реализации на ПЛИС. К тому же при их разработке не учитываются вопросы, связанные с обеспечен» требуемой точности вычисления, а именно вопросы минимизации остаточной погрешности, погреип стей округления и действия. Вследствие этого вопросы, связанные с разработкой алгоритмов вычис.) ния специальных математических функций, ориентированные на разработку мегафункций стандарт! I библиотеки известных САПР электронных схем являются весьма актуальными.

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

Задачи исследования. Для достижения поставленной цели необходимо решить следующие за;

чи:

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

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

Разработать алгоритм вычисления функции ехр(х) для произвольного диапазона изменен аргумента и произвести его оптимизацию с точки зрения минимизации требуемых аппар* ных ресурсов ПЛИС и времени счета.

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

Разработать пакет прикладных программ необходимый для разработки мегафункции выч! ления функции ехр(х) и проанализировать полученные программы с точки зрения обесг чения требуемой точности и аппаратных затрат ПЛИС на их реализацию.

Научная новизна: К новым результатам проведенных исследований по теме диссертации от!

сятся:

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

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

ного времени получения результата.

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

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

- Оптимизированный применительно к реализации на ПЛИС алгоритм выполнения операции арифметического умножения, и рекомендации по области его применения, гарантирующие относительно стандартных алгоритмов, реализованных в САПР Quartus II фирмы Altera как

уменьшения требуемых на реализацию аппаратных ресурсов ПЛИС, так и сокращение вр менны вычисления.

- Алгоритм построения аппроксимирующего многочлена высокой степени, предназначен!!! для численного вычисления экспоненциальной функции, обеспечивающий при реализации ПЛИС оптимальное разбиение аргумента на расчетные интервалы, что при произволык диапазоне изменения аргумента и требуемой точности вычисления позволяет минимизир вать как аппаратный затраты, так и время вычисления.

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

Апробация работы и публикации

Основные результаты работы докладывались на Международной молодежной научной конф ренции «Гагаринские чтения» 2006 и 2007 годов, III научной международной конференции «Совремс ные проблемы науки и образования», г. Москва, 13-15 мая 2008г, Всероссийской научно-техническ конференции «Новые материалы и технологии», Москва 11-13 ноября 2008г и международной научи конференции «Технические науки и современное производство», Китай (Пекин), 26 ноября - 4 декаб 2008 г.

Основные результаты работы опубликованы в 9 научных трудах, включая 1 работу [9] опублик ванную в журнале, рекомендованном ВАК .

Структура диссертационной работы.

Диссертация состоит из введения, 5-и глав, заключения, списка использованных источников приложений. Объем диссертации 185 страниц машинописного текста, приложений 16 страниц, 129 р сунков и 72 таблицы. Список литературы включает 62 наименования.

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

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

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

- Метод разложения в степенной ряд;

- Методы ортогональных и других многочленных разложений, к которым можно отне разложение по многочленам Чебышева или Лежандра;

- Метод многочленного приближения;

Метод разложения в цепные дроби;

Метод рациональных приближений;

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

Метод разложения в степенной ряд использует представление функции в виде:

00 х"

ехр(х)= .

/7=0

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

Для данного метода найдена зависимость относительной ошибки вычисления (г) от количества членов (к) ряда (рис.1). Показано, что погреш-

,к) 100

, 10 1,1)1 1

IX) I 0.1 0.01

1*10 1*10* 1*ш"

1*10 1.10":10

ч^--»-^ (исходная

\ ^К 1 / гГШ

сценка ос тате ч коп? V гНШ

члена 1.9; X; N. Ч

кХ \

г2(х,к) х--

/ У ч

сценка ос •агочнего X >

члена 1.11 ч

II

Рис.1

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

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

СО

ехр(а-х) = 10(а)+^1п(а)-Тп(х)>

Л=1

где: значения 1§(а) и 1„(а) - функции Бесселя мнимого аргумента порядка и. Данное выражение справедливо для диапазона изменения аргумента < 1 Показано, что суже-е диапазона изменения аргумента позволяет значительно поднять точность вычисления функции, ого можно добиться при использовании замены переменных в многочлене Чебышева вида:

i-x-l 1

-+ —

J-i j-i

где: 1ИJ - целые числа.

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

ехр(х) = ехр\ -

«4,

'■J

+ 2 -1/А

к=\

J_

Tk(i-x-\)

Исследования показали, что увеличение параметра у фактически приводит к повышению степ ни аппроксимирующего многочлена, то есть позволяет уменьшить относительную ошибку вычислени а увеличение параметра I так же снижает относительную ошибку вычисления, но достигается это и тем сужения реального диапазона изменения аргумента. Показано, что для каждого диапазона измен ния переменной существует некоторое оптимальное с точки зрения повышения точности соотношеш параметров 1 и]. Так если 0 < х < 1п2, то оптимальными являются значения]=2 и ¡=2.86.

На рис.2, приведены зависимост

ол^з-—, модулей относительной ошибки вы

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

0.01 1х10~3 и 1х10"4 IxlO"3

ж.

1x10"

1x10"

» Исходное выражение ■

¿L

щ

модифициров

)ван^е Bt

выражение 1=2.1=2.

0.1

0.2

0.3

0.4

0.5

Рис.2.

Общий вид разложения в ряд произвольной функции /(х) по многочленам Лежандра опред

ляется выражением:

f(x)=^an-Pn(x),

п=О

где: ви ]f(x)-Pn(x)-dx и Р„(х) = -Ц• ^(х2 — ЖJ*

^ 2 ■ fi! их

Показано, что при выполнении условия 0 < х < 1 максимальное значение относительной ошиб соответствует значению х = 1 .На рис 3 приведена полученная с использованием данных выражеш зависимость относительной ошибки вычисления от числа членов разложения. Следует отметить, чт параметр п фактически равен степени реализуемого аппроксимирующего многочлена.

100 10

.п)| 1

0.1

0.01 3

10

10"4

ш"5

10~б

ю-7

ш"*

\ !

1 \

! V

1

1 \

1 \

1

10

Метод многочленного приближения базируется на работах Чебышева о минимизации равномерной нормы сходимости. Обычно многочлен наилучшего приближения для известного интервала ищется по значениям аппроксимирующих точек в виде степенного ряда:

к

Рис.3.

ехр(х)-А- £ак -хк к=0

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

Метод разложения в цепные дроби базируется на использовании выражения вида: /(*) =-^-•

1 + -

а,+-

а7 + -

аЛ+.

где: коэффициенты а, и Ь, есть некоторые многочлены относительно аргументы искомой функ-

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

выражением: /(х)П = ^ ^ ^ . Известно достаточно большое число разложений экспоненциальной нкции в цепные дроби. Однако большинство из них приводят к выражению:

р(*)=—«—Ц— •

1-Е--——

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

9

аргумента.

Таблица 1

Значение константы п

Подходящая дробь

12+ 6-х + х

12- 6-х + х

-(120+ 12х2 + 60х + X3)

(-120) - 12-х2 + 60-Х+ х3

1680+ 180х2 + 840х + 20х3 + х4

1680+ 180х2 - 840х - 20-х3 + х4

~(з0240+ ЗЗбОх2 + ЗОх4 + 15120х+ 420х3 + х5) (-3024С) - ЗЗбОх2 - ЗОх4 + 15120Х+- 420х3 + \

665280+ 75600х2 + 840х" + 332640х+ 10080х3 + 42-х5 + х 665280+ 75600х2 + 840х4 - 332640х- 10080х3 - 42-х5 + хб

1

0.1

|г1(х)| 0-91

—

|г2(х) | МО-) — 1 1-10., |й(*)| МО-, — 1-10.'

Ш

!:!§: 1 -10 "

!

п=1 '

1

1 П=2 _

У __——" _.____■

/ * | п=3

/ ^^ : __-

/ / п=4

/

1 / п=5

/ ^ 1

/ /

./ . .У _ ... .. ' ...!

0.2

0.4

Рис.4.

0.6

0.8

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

гочленов и нахождением их отношения.

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

ехр(х)'

2л" -хк

. *=О_

к=0

где: с, =

(2 п-к)\ (п-к)Ш'

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

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

ультата. В таблице 2 для рассмотренных методов вычисления перечислены типы и количества вы-няемых операций, необходимые для получения заданной точности вычисления. (№ - количество жений, №г1 - количество умножений, N<1 - количество делений)

Таблица 2

Относительная ю-1 ю-2 КГ* 10"4 10"4 10"6 10"' 10"8 ю-у ю-10

погрешность % % % % % % % % % %

N8 5 6 7 8 9 10 И 12 13 14

Степенной ряд Ыт 8 10 12 14 16 18 20 22 24 26

N(1 0 0 0 0 0 0 0 0 0 1

N8 4 5 6 7 8 9 10 10 11 12

пенной ряд с остаточным

Ыт 6 8 10 12 14 16 18 18 20 24

членом

N(1 0 0 0 0 0 0 0 0 0 0

Многочлены № 5 8 11 15 19 19

Чебышева N171 6 8 12 16 21 21

Выр-е 1.23 N(1 0 0 0 0 0 0

Многочлены № 4 6 9 9 12 16 20 20

Чебышева Ыт 3 6 8 8 12 16 21 21

Исходное выражение Ш 0 0 0 0 0 0 0 0

Многочлены

№ 2 2 4 6 6 9 9 12 12 16

Чебышева

Ыт 2 2 4 7 7 9 9 13 13 17

дифицированное выраже- N(1 0 0 0 0 0 0 0 0 0

0

ние

№ 6 7 9 10 12 13

Многочлены

Ыт 9 11 13 15 17 19

Лежандра т 0 0 0 0

0 0

Многочленное № 3 4 5 5 6 7 7 8 9 9

приближение Ыт 5 7 9 9 11 13 13 15 17 17

N<1 0 0 0 0 0 0 0 0 0 0

№ 4 4 4 5 5 6 6 6 7 7

Цепная дробь Ыт 10 10

4 4 4 6 6 8 8 8

Ыс1 1 1 1 1 1 1 1 1 1 1

N8 6 6 6 8 8 8 8

Рациональное

Ыт 8 8 8 11 И 11 11

приближение Ы(1 1 1 1

1 1 1 1

Анализ данных таблицы 2 показывает, что эффективность того или иного метода зависит от тре-

емой точности вычисления. Однако, в общем случае можно утверждать, что наиболее эффективным,

II

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

Во второй главе для основных математических операций, реализованных в САПР Quartus фирмы Altera, исследуется взаимосвязь между разрядностью аргумента, ресурсами ПЛИС, и времен их выполнения. Исследования проведены для двух семейств ПЛИС: Cyclone II и STRATIX II.

Для реализации операции сложения-вычитания в САПР Quartus II фирмы Altera использует мегафункция Ipm_add_sub. Исследование этой мегафункции показало, что аппаратные затраты на реализацию прямо пропорциональны разрядности аргумента, причем для обоих семейств аппаратш затраты практически одинаковы. Данная мегафункция предполагает оптимизацию получаемого техн ческого решения либо по критерию минимизации скорости вычисления (параметр Maximize_Speed=l либо требуемых аппаратных затрат (параметр Maximize_Speed=0) - логических блоков (ЛБ) ПЛИ Проведенные исследования показали, что для выбранных семейств ПЛИС (Cyclone II и STRATIX II) обоих случаях результат практической реализации получается одинаковым.

Для семейства Stratix II количество логических блоков ЛБ (№16), необходимое для реализащ сумматора с разрядностью п равно:

Ылб = п+ 1.

Для семейства Cyclone II при п<48 справедлива аналогичная зависимость. При большем чиш членов она приобретает вид:

№i6 = n + 3.

Для реализации блока умножения в САПР Quartus II используется стандартная мегафункщ lpm_mult, которая, так же как и мегафункция lpm_add_sub предполагает оптимизацию умножите либо по критерию минимизации скорости вычисления (параметр Maximize_Speed=10), либо по крит рию уменьшения требуемых аппаратных затрат (параметр Maximize_Speed=0). Кроме этого, для реат зации операции умножения могут быть использованы либо только логические блоки ПЛИС (ЛБ), ли специализированные аппаратные умножители, включенные в состав упомянутых семейств ПЛИС, работе исследованы все возможные варианты реализации умножителей.

Исследования показали, что при реализации умножителя только с использованием ЛБ для ПЛИ семейства Stratix II оптимизация по параметру Maximize_Speed не дает различия в числе ЛБ и време! вычисления. Для ПЛИС семейства Cyclone II увеличения параметра Maximize_speed ведет к уменьш нию времени вычисления и увеличению аппаратных затрат на реализацию. Зависимость числа ЛБ разрядности аргумента носит квадратичный характер. В работе получены соответствующие аналитич ские зависимости. Для ПЛИС Cyclone II:

при параметре maximize_speed = 0 NOcycLB( п) = 1.035 -л2 + 7.275 ■ п -13.655. при параметре maximize_speed = 10 N\QcycLB(n) = 2.062- «2 -1.015 -и+ 3.064.

Для для ПЛИС семейства Stratix II NstrlB(n) = 0.75-п2 +1.562-и-0.327.

Анализ результатов полученных для случая применения встроенных умножителей показывает, оптимизация проекта по критерию speed для обоих типов ПЛИС не приводит к изменению требуе-аппаратных затрат и при увеличении разрядности сомножителей требуемое число дополнительных для ПЛИС семейства Stratix II меньше, чем для ПЛИС семейства Cyclone II.

На рис.5 показаны полученные зависимости числа необходимых ЛБ (LB(n)) и встроенных умно-елей (М(п)) от разрядности сомножителей (п). Из приведенных графиков следует, что искомые зави-ости носят кусочно-линейных характер. При этом точками разрыва графиков являются переходы [у числами разрядов 9 • / и 9 • / +1, что вполне объяснимо, так как в структуре ПЛИС использова-аппаратные умножители разрядности 9X9 бит. Отметим так же, что для четных значений i (напри, переход от 18 к 19 разрядам, или от 36 к 37 разрядам) сопровождается значительно большим уве-ением требуемых аппаратных ресурсов, чем при нечетных i (9 разрядов —>10 разрядов, или 27 разря--»28 разрядов).

ПЛИС Cyclone II б) ПЛИС Stratix II

Рис.5

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

Полученные результаты подтверждают выдвинутую А. Н. Колмогоровым гипотезе п2 о том, что жность операции умножения, то есть количество простых операций выполняемых для получения изведения, пропорциональна квадрату разрядности сомножителей. Попытки уменьшить число про-ix операций при реализации умножения привели в разработке, так называемых методов быстрого южения (метод "Divide and Conquer", его другие названия "Принцип Дихотомии", "Binary Splitting", .п.) является в настоящее время основой для построения различных алгоритмов быстрого вычисле-различных функций. В работе с использованием этого подхода разработана программа для реализа-

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

тов в виде суммы двух чисел А = А\ + 2к • А2 и В = В1 + 2к -В2, где А\, А2, 51, В2— значные числа и применения выражен

А-В = А1-В\ + 2к -((А\ + А2)-(В1 + В2)-{А1-В\ + А2 -В2)) + 2гк-А2-В2

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

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

<kz = mox{tdataa ( п), tdalah (n)}+tadd(2-n + 2) + tadd(4-n),

гда: ldmab (Ч> = 'mul, (n) + 'add С1'") И ¡dataaf») = <add(n) + *mult (n + V'.

tadd (n), lmui, (n) - соответственно времена выполнения операций сложения и умножения н

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

а) ПЛИС Cyclone II б) ПЛИС Stratix II

Рис.6.

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

выми, последовательно включенными сумматорами. Результаты эксперимента показаны на рис.6 оторых Тхоп, ТХ1]и - соответственно времена вычисления с одним и двумя последовательно вклю-лми сумматорами. Очевидно, что расстояние между приведенными зависимостями практически не сиг от разрядности аргументов. Отсюда следует вывод, что реально оценить время выполнения той иной операции можно только путем проведения соответствующего эксперимента, так как времена дачи сигнала в ПЛИС соизмеримы с временем выполнения собственно операции.

Для операции целочисленного деления в САПР (^иаШк II существует мегафункцией 1рт_с1еуШе. 1сследование показало, что число ЛБ для реализации можно определить, используя следующие ап-симирующие выражения:

Шас1(п) = 1.021 • п2 + 2.397 • п +1.07 ШасЦп ) = 1.001-п2 +3.207-л -5.842

Реализация выполняется только на ЛБ, причем число этих блоков примерно на два порядка пре-ают ресурсы, необходимые для выполнения операции сложения-вычитания. При использовании ко логических блоков требуемые аппаратные ресурсы на выполнения операций деления (мегафунк-1рт_(1е¥Ше) и умножения (мегафункция 1рт_тиИ) соизмеримы, однако время выполнения опера-деления примерно на порядок превосходит время выполнения операции умножения, что говорит о ледовательном алгоритме работы.

Проведенные исследования позволяют заключить, что при вычислении функции ехр(х) с по-ью ПЛИС следует избегать алгоритмов, требующих выполнения операции деления и из двух вы-нных в главе 1 методов предпочтение следует отдать методу, основанному на использовании много-нов Чебышева.

В третьей главе рассмотрены способы организации вычисления, позволяющие уменьшить как мя вычисления так и аппаратные затраты на реализацию вычислителя при произвольном диапазоне енения аргумента. Показано, что для повышения точности вычисления аргумент целесообразно раз-ать на две части: постоянную и расчетную. Окончательный вариант получается компиляцией значе-I функции для этих двух частей. Предложено два варианта реализации данного подхода. Первый с.7.а) предполагает выделение из аргумента целой и дробной частей. Значение функции от целой ти хранится в блоке памяти, а значение от дробной части (внутренний аргумент) вычисляется вы-лителем. Окончательный результат формируется умножением двух сомножителей. Второй вариант с.7.6) базируется на свойстве позиционной системы умножать или делить записанное число на осно-ие системы счисления сдвигая его на требуемое число разрядов вправо или влево. В случае двоич-1 системы счисления это требует, чтобы постоянная часть аргумента была кратна 1п 2, а расчетная ала в диапазоне 0 < х < 1п 1 ~ 0.693.

В работе второй способ признан более предпочтительным. (Во-первых, дополнительный ум! житель, заменяется на сдвиговый регистр, и, во-вторых, сужается расчетный диапазон изменения ар| мента, что повышает точность вычисления.)

Рис.7

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

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

Таблиц

Степень многочлена 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Число ярусов умножения 2 3 3 4 4 4 4 5 5 5 5 5 5 5 5 6

Число ярусов сложения 1 1 2 2 2 3 3 3 3 3 3 3 4 4 4 4

Число операций сложения 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Число операций умножения 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33

С использование предложенной процедуры построен граф вычислительного процесса для на ждения значения многочлена четвертой степени, соответствующего разложению функции по многоч нам Чебышева при оптимизированной замене аргумента (¡=2.86, \=2). Представленный граф содерж!

3322

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

* во-первых, значительно сократить

аппаратные затраты ПЛИС на реализацию, во-вторых, уменьшить время вычисления, и, в- третьих , значительно повысить точность вычисления.

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

с 1

с 2

сЗ

с 4

с 5

сб

аз-х-1 +а0

Рис. 8.

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

Р(у) = ехр(а-х) = (а0+агу + а2-у2 +а3-у3 +а4-у^, де: а0=2-ехр(а)-[0.5-10(а)-12(а) + 14(а)]-а1=2-ехр(а)\1х(а)-Ъ-1ъ(а)\, а2=4-ехр(а)-[12(а)-А-1А(а)}\ аъ=Ъ-ехр(а)-1ъ(а)\ аА = \6-ехр(а)- 14(а).

В этом случае зависимость предельной абсолютной погрешности вычисления от параметров гочлена может быть представлена в виде:

дг(у)

8ап

А? (яо)+

атЫ

да-.

дах Д л(а3)+

Дл(о,)+ дР(у)

дР{у)

да.

да2 •А п(а4)+

А п{а2)+

дР(у(х))

дх

■Ап(х)

Для определения степени влияния абсолютных ошибок представления коэффициентов и ар1 мента функции на абсолютную ошибку вычисления предположим, было сделано предположение, 1 все исходные ошибки представления одинаковы (Лобц(). В этом случае полученное выражение мож переписать в следующем виде:

А П Ол ) = А общ • (^Да„ + + ^Да2 + ^ДаЗ + ^Да4 + ^х )>

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

Полученное выражение позволило определить весовые коэффициенты влияния на погрешно для следующих модификаций переменных в многочленах Чебышева: у=х; у=2х-1; , у=2.8 1^=1, у=Зх-1; }=2, у=2х-1; ]=2, у=2.86х-1; ]=2, у=Зх-1. Для каждого из рассмотренных случаев получе значения весовых коэффициентов, позволившие определить оптимальные, с точки зрения точности числения, соотношения разрядностей представления аргумента и используемых коэффициентов проксимирующего многочлена.

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

100

.30.677.

61152(03,г) 10 421 £(0,1) 1

83Щ0.7.1) й41Е(0,г) 01 «22Е(0,г)

0.01

432Е(0.7,г) М2Е(0,1) 1*10"3

1х10"4

.2х10"3.

1x10 0 10 20 30 40

А ' .40.

Рис.9.

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

кч

к ^ ¡=1. У=х

У

/]=1.У=2х-1

1=1, у=Зх-1 ч

¡=1, у=2.8Вх-1—^

^И=2,у=2х-1

р2 е_2 86х-1 1г2, у=Зх-1—

Для структуры вычислителя рис.7.б предложено два варианта выполнения блока подготовки ых. Первый (рис. Ю.а) использует два дополнительных умножителя и реализует прямой метод пре-ования. Это позволяет максимально сократить время получения результата. Второй (рис. 10.6) поен на последовательном принципе, что сокращает необходимые ресурсы ПЛИС, но ведет к увели-ю времени вычисления. В приложении работы представлены, написанные на языке АЬГОЬ про-мы для реализации обоих вариантов построения.

Шелая часть аргумента I Дробная часть аргуиента I Умножитель! 1/1п2

О

Data in .

целая часть числа дробная часть числа

я часть-сдвиг результата | Дробная часть • промежуточный аргумент |

О

\7

в блок формирования результата

О

MS RG If 5ив

б)

в блок вычисления функции

а)

Рис.10

В таблице 4 приведены рассчитанные с использованием результатов главы 4 рекомендуемые со-шения между разрядностями представления аргументов (Я) и коэффициентов аппроксимирующего гочлена. С использованием графа рис.8 и рекомендаций таблицы 4 на языке АНБЬ была разработа-рограмма для вычисления экспоненциальной функции при условии 0 < х < 1п2. Данная программа ись основой для проведения вычислительного эксперимента с целью подтверждения полученных в те теоретических положений.

Таблица 4.

зел графа dataA dataB Result

1м1 al—>(R+1) INPUT—> (R) (R)+l

1м2 INPUT—» (R) INPUT— (R) (R-l)+2

2м1 a2—(R+l) 1M2—»(R-l)+2 (R-l)+2

2м2 1M2—► (R-l)+2 1M2—> (R-l)+2 (R-2)+2

2мЗ 1M2—» (R-l)+2 INPUT—» (R) (R-l)+2

3с1 1M1—> (R)+l 2M1—»(R-l)+2 (R-l)+2

3м1 2M2—»(R-2)+2 a4—(R) (R-2)+2

Зм2 2M3—♦ (R-l)+2 a3-(R) (R-l)+l

4с1 3S1— l+(R-l)+2 aO—»(R+2) (R)+2

4с2 3M1—(R-2)+2 3M2—»(R-l)+l (R-2)+2

5с1 4S1—► (R)+l 4S2—> l+(R-2)+2 (R-l)+2

6м 1 5S1—► (R-l)+2 5S1— (R-l)+2 REZ—»(R-2)+2

В работе для всех рассмотренных ранее случаев (/=], у=х; у=2х-1; 3=1, у=2.86х-1;3=1, у=3х-

=2, у=2х-1; ¡=2, у=2.86х-1; ¡=2, у=Зх-1) определены значения коэффициентов аппроксимирующего

гочлена и получены зависимости ошибки вычисления от значения аргумента. Для случая ]=2,

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

19

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

В таблице 5 приведены основные результаты вычислительного эксперимента. В графе «Чи разрядов результата» приведено количество правильных разрядов результата, соответствующее дан

му методу аппроксимации. Таблица 5

Метод замены Число разрядов Относительная ошибка % Число ЛБ Число умножителей Время счета

аргумент результат

.¡=1, У=х 17 12 5.25-10"' 72 14 29.25п8

1=1, у=2х-1 18 16 3.08-10"5 214 26 33.75п8

¡=1, у=Зх-1 23 18 9.66-10"6 1322 26 48.54п8

}=1,у=2.86х-1 23 19 4.05-10"6 1290 26 47.15п8

.¡=2, У=2х-1 25 21 1.9-10"6 1696 36 60,02п8

¡=2, у=2.86х-1 29 23 3.18-10"' 3552 36 76.61п8

Г2, у=Зх-1 28 22 7.05-10'7 3304 36 72.85п8

В этой же таблице приведено число необходимых для реализации логических блоков и встро ных умножителей ПЛИС. Эксперимент показал, что нехватка для реализации выбранного алгори встроенных умножителей ведет к резкому возрастанию числа необходимых логических блоков и в мени вычисления. В таблице 6 приведены результаты вычислительного эксперимента для случая ] у=2.86х-1 при условии, что ПЛИС содержит требуемое число встроенных умножителей.

Таблица 6

Число разрядов Время счета Число логических блоков (ЬВ2) Число 9 бит умножителей (М2)

29 61,56 nS 875 64

27 60,01 nS 786 62

24 57,62 nS 655 56

22 55,55 nS 543 56

20 54,09 nS 457 56

18 44,25 nS 236 37

16 33,85 nS 50 16

14 33,79 nS 44 16

12 33,68 nS 38 16

10 32,76 nS 32 16

8 30,38 nS 26 8

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

Выводы по работе

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

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

от отрицательного аргумента соотношения ехр(—х) =

ю хп

2. Для разложения функции в степенной ряд вида ехр(х)= V— предложена методика полу-

и-о*'

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

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

4. Показано, что с точки зрения реализации на ПЛИС, наиболее перспективным является метод использующий многочлены Чебышева, с оптимизированной под заданный диапазон изменения аргумента заменой переменных. Предложена методика модификации переменной в многочлене Чебышева из условия получения максимальной точности вычисления при заданном диапазоне изменения аргумента. На основе предложенной методики найдено, что для диапазона изменения аргумента 0<х<1п2 оптимальной является подстановка переменной в

„ (2.86 - х -1 1 > ^

многочлене Чебышева вида у = I ---1--. Это при минимизации аппарат-

V 2-2.86 2-2.86J

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

5. Для стандартных мегафункций САПР Quartos II lpm_add_sub и lpm_mult, реализующих операции сложения-вычитания и умножения, получены аналитические зависимости, связывающие необходимые аппаратные ресурсы ПЛИС и время выполнения операции с разрядностью операндов.

1/

/ ехр( х )'

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

7. Разработаны алгоритмы вычисления, позволяющие вычислять значение функции при пр вольном диапазоне изменения аргумента. Получены зависимости точности вычисления и личества выполняемых математических операций от расчетного диапазона изменения а мента. Показано, что с точки зрения обеспечения требуемой точности вычисления при тре вании минимизации аппаратных ресурсов ПЛИС на реализацию, оптимальным является четный диапазон изменения аргумента, определяемый условием 0< х <1п2.

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

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах:

1. Мо Чжо Чо. Особенности организации вычисления экспоненциальной функции на ПЛИС -Тезисы докладов Международной молодежной научной конференции «XXXII Гагаринские чтения», том 4, секция 29 стр. 90, 2006 г.

2. Мо Чжо Чо. Организация вычисления экспоненциальной функции на ПЛИС - Тезисы докладов Международной молодежной научной конференции «XXXIII Гагаринские чтения», том 4, секция 20 стр. 138, 2007 г.

3. Мо Чжо Чо. Вычисления экспоненциальной функции на ПЛИС - Журнал «Современные наукоемкие технологии» Российская академия естествознания, № 4, стр. 113.. 114,2008г.

4. Мо Чжо Чо. Особенности организации операции умножения на ПЛИС - Журнал «Современные наукоемкие технологии» Российская академия естествознания, № 4, 2008г. стр. 99.

5. Мо Чжо Чо. Опадчий Ю.Ф. Алгоритм вычисления показательной функции на ПЛИС. - Сб. трудов Всероссийской научно-технической конференции «Новые материалы и технологии» том.З Москва., 11..13 ноября 2008г. сгр. 113...115

6. Мо Чжо Чо. Опадчий Ю.Ф. Оптимизация алгоритма операции умножения на ПЛИС. - Сб. трудов Всероссийской научно-технической конференции «Новые материалы и технологии» том.З Москва., 11.. 13 ноября 2008г. стр. 115.. 116.

7. Мо Чжо Чо. "Optimization algorithm of exponential function calculation at CPLD" Пекин 26.11 — 04.12 2008. Материалы конференции международной научной конференции «Технические науки и современное производство», Китай (Пекин), 26 ноября - 4 декабря 2008 г.

8. Мо Чжо Чо. Оптимизация алгоритма вычисления показательной функции на ПЛИС ПЛИС -Журнал «Современные наукоемкие технологии» Российская академия естествознания, № 11, 2008г. стр. 61-62.

9. Мо Чжо Чо. Опадчий Ю.Ф. Мониторинг температурных режимов работы автономных объектов. Измерительная техника. 2009, № 9, стр. 26...28.

Подписано в печать ЗО ОС) 2009. Объем 1,5 пл., тираж 100 экз. Ротапринт МАТИ, 109240, г. Москва, Берниковская наб., 14

Введение.

ГЛАВА 1. Методы вычисления показательной функции.

1 Л.О.бщие свойства показательной функции.

1.2.Методы вычисления натуральной показательной функции.

1.3.Метод разложения в степенной ряд.

1.3.1 .Исходная формула разложения.

1.3.2.Повышение точности вычисления.

1.4.Методы ортогонального приближения.

1.4.1 .Многочлены Чебышева.

1.4.2.Многочлены Лежандра.

1.5.Метод многочленного приближения.

1 .б.Метод разложения в цепные дроби.

1.7.Метод рациональных приближений.:.

1.8.Метод БВЕ.

1.9.Сравнительный анализ различных методов вычисления.

Выводы по главе 1.56 »■>

ГЛАВА 2. Аппаратная реализация основных математических операций.

2.1 .Реализация операций сложения-вычитания.

2.2.Реализация операции умножения.

2.2.1.Реализация умножителя на логических блоках.

2.2.2.Реализация умножителя с использованием встроенных блоков.'.

2.3.Понятие сложности вычисления произвольной функции f(x).

2.4.Методы быстрого умножения.

2.4.1.Алгоритм умножения методом Карацубы.

2.4.2.Граф алгоритма быстрого умножения.

2.4.3.Программная реализация алгоритма быстрого умножения.

2.5.Сравнение умножителей реализующих мегафункцию lpmmult и метод быстрого умножения.

2.5.1.У множите ль на основе только логических блоков.

2.5.2.Умножитель, использующий встроенные модули.

2.5.3.Временные соотношения метода быстрого умножения.

2.6.Реализация операции деления.

Выводы по главе 2.

ГЛАВА 3.Особенности организации алгоритма вычисления показательной функции.

3.1.Методы сокращения диапазона изменения значения аргумента.

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

3.3.Алгоритмы вычисления многочленов Чебышева.

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

Чебышева.

3.4.1 .Оптимизация расчетного выражения.

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

3.5.Процедура построения графа вычислительного процесса.

Выводы по главе 3.

ГЛАВА 4.Вопросы обеспечения точности вычисления экспоненциальной функции на

ПЛИС.

4.1 .Основные положения.

4.2.Понятие числа верных знаков приближенного числа.

4.3.Правила округления.

4.4.Связь относительной погрешности с числом верных знаков числа.

4.5.Определение погрешности при выполнении основных математических операций.

4.5.1.Определение погрешности суммы.

4.5.2.0пределение погрешности разности.

4.5.3.Определение погрешности произведения.

4.5.4.Определение погрешности частного.

4.5.5. Определение погрешности возведения в степень.

4.5.6. Определение погрешности извлечения корня.

4.6.0пределения количества верных знаков результата.

4.7.0бщая задача определения погрешности вычисления.

4.8.Исследование связи между погрешностями аргументов и вычисляемой функции. 132 4.8.1 .Исходный многочлен Чебышева при j=l и у=х.

4.8.2.Многочлен Чебышева при j=l и у=2х-1.

4.8.3.Многочлен Чебышева при j=l и у=Зх-1.

4.8.4.Многочлен Чебышева при j=2 и у=2х-1.

4.8.5.Многочлен Чебышева при j=2 и у=Зх-1.

4.8.6.Многочлен Чебышева при j=l и у=2,8бх-1.

4.8.7.Многочлен Чебышева при j-2 и у=2,86х-1.-.

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

Выводы по главе 4.

ГЛАВА 5.Практическая реализация алгоритма вычисления.

5.1.Блок схема вычислителя.

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

5.2.1 Операция умножения.

5.2.20перация возведения в степень.

5.2.30перация сложения.

5.3.Блок подготовки данных.

5.3.1. Реализация блока подготовки данных на умножителях.

5.3.2 Определение разрядности используемых аргументов.

5.3.3. Реализация блока на сумматоре.

5.4. Блок вычисления ЕХР(х).

5.4.1.Реализация алгоритма 4.8.1 (многочлен Чебышева при j-1 иу=х).

5.4.2.Реализация алгоритма 4.8.2 (многочлен Чебышева при j=l и у=2х-1).

5.4.3.Реализация алгоритма 4.8.3 (многочлен Чебышева при j=l и у=Зх-1).

5.4.4.Реализация алгоритма 4.8.6 (многочлен Чебышева при j=l и у=2.86х-1).

5.4.5.Реализация алгоритма 4.8.4 (многочлен Чебышева при j=2 и у=2-х-1).

5.4.6.Реализация алгоритма 4.8.5 (многочлен Чебышева при j=2 и у=3-х-1).

5.4.7.Реализация алгоритма 4.8.7 (многочлен Чебышева при j=2 и у=2.86-х-1).

5.4.8. Анализ результатов эксперимента.

Выводы по главе 5.

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

В основу построения компьютера были положены принципы, сформулированные в 1945 году Джоном фон Нейманом. К основным из них относятся представление алгоритма обработки информации в виде последовательности управляющих команд и поочередному выполнению этих команд одними и теми же техническими средствами. Другими словами, при решении различных задач аппаратные средства компьютера остаются неизменными. Использование этих принципов позволило разработать универсальное устройство способное решать широкий круг практических задач, Смена задачи требовала только изменения последовательности выполняемых стандартных операций, то есть смены используемой программы. Поэтому такое устройство становилось универсальным. Вследствие этого смена поколений ЭВМ, связанная с совершенствованием технологии изготовления аппаратной части ЭВМ (путь от электронных ламп к БИС и СБИС), практически не коснулась идеологии их построения.

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

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

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

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

По существу ПЛИС [47, 49, 50] является СБИС, содержащей последовательно 1 соединенные матрицы логических элементов И и ИЛИ, допускающие программирование внутренних межэлементных связей, дополнительно укомплектованные триггерными и буферными элементами, причем вид внутренних соединений между ними может задаваться с использованием внешних управляющих сигналов. Таким образом, в ПЛИС принципиально заложена возможность аппаратной реализации любой функции цифровой логики, то есть выполнения произвольного алгоритма обработки входной информации. Емкость современных ПЛИС превышает 10б эквивалентных базовых логических элементов (2И-НЕ), что предполагает аналогичное число внутренних программируемых межсоединений. Очевидно, что программирование такого кристалла не может быть выполнено без применения соответствующих САПР электронной аппаратуры (EDA -Electronic Design Automation).

В настоящее время основными производителями ПЛИС, занимающими до 80% рынка производства и являющимися главными разработчиками идеологии их построения и применения являются созданные в середине 80-х годов фирмы Altera Corporation, Xilinx Inc. и Actel Corporation. Каждая их этих фирм, кроме самих ПЛИС, внедряет и свой EDA продукт, предназначенный для проектирования устройств с применением тех или иных языков описания аппаратуры (IIDL - Hardware Description Languages). При этом значимость EDA составляющей постоянно увеличивается. Существовавший в прошлом веке подход к проектированию, базировавшийся на описании проекта с использованием графического редактора и библиотеки 1 стандартных логических примитивов (простейшие узлы комбинационной и последовательностной логики, такие как мультиплексоры, дешифраторы, счетчики, регистры и т.д.) все больше вытесняется описанием с использованием таких HDL как VHDL Verilog HDL, или специально разработанными фирмами изготовителями языков, учитывающих особенности реально существующей элементной базы. Таким примером является разработанный фирмой Altera язык AHDL (Altera Hardware Description Languages) [46, 48].

Рост сложности ПЛИС привел к тому, что кроме непосредственно фирм изготовителей интегральных схем, вопросами программной поддержки проектирования в настоящее время занимается большое число различных фирм. С целью координации этих работ в 1995 г была создана программа поддержки партнеров-разработчиков мегафункций (Altera Megafunction Partners Program). Это привело к разработке большого числа готовых модулей и мегафункций, предназначенных для реализации стандартных микропроцессоров и микроконтроллеров, устройств обслуживания различных шин (например, ISA и PCI), сетевых контроллеров, устройств, реализующих быстрое преобразование Фурье, фильтры конечной и бесконечной импульсной характеристики (КИХ и БИХ-фильтры) и т.д.[1].

Стандартные пакеты EDA содержат так же мегафункции, позволяющие реализовать основные математические операции. На рис.В.1 приведен перечень мегафункций, содержащихся в САПР Quartus II фирмы Altera и предназначенных для выполнения основных математических операций. Здесь присутствуют все основные математические операции (сложение, вычитание, умножение, деление, извлечение корня, модуль и т.д.)

В й Installed Plug-Ins Altera SO PC Builder В fil arithmetic

7] ALTACCUMULATE /j ALTFPMULT J ALTMEMMULT A ALTMULT.ACCUM (MAC) /] ALTMULTADD A ALTSQRT LPMABS A LPMADDSUB 7} LPMCOMPARE A LPMCOUNTER A LPMDIVIDE

7) LPMMULT

PARALLELEDD [£] ARM-Based Excalibur i±j gates в Ш 1/0

EE! §Й memory compiler

2) SignalTap II Logic Analyzer W fcil storage ffl Ш IP MegaStore

Рис.В.1

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

Из сказанного следует, что ПЛИС является идеальной элементной базой для разработки устройств, основными требованиями к которым наряду с высоким быстродействием является обеспечение высоких массо-объемных показателей, высокой надежности и малой стоимости. При этом обеспечивается крайне короткий и полностью автоматизированный цикл проектирования. Проиллюстрируем сказанное заимствованным из [2] типовым маршрутом проектирования устройства цифровой обработки сигнала (ЦОС) на основе ПЛИС фирмы Xilinx.

1. Используя программный продукт компании Math Works (MATLAB и Simulink) разрабатывается и проверяется модель устройства ЦОС;

2. Используя программный продукт Xilinx SystemGenerator, генерируется синтезируемое HDL описание, соответствующее функциональным возможностям, описанным в Simulink/System модели;

3. Используя средство синтеза САПР Xilinx ISE, компилируется проект и генерируется программный код для ПЛИС.

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

Возвращаясь к оговоренному ранее классу задач, связанных с вопросами ориентации в пространстве [3.9, 52, 53], вне зависимости от того решаются ли вопросы управления летательным аппаратом, кораблем, автомобилем или роботом, алгоритмы работы таких систем требуют вычисления специальных математических функций: тригонометрических или других (экспоненциальных, логарифмических). Однако в наборе стандартных мегафункций существующих САПР ПЛИС реализация таких алгоритмов не предусмотрена.

Применительно в традиционным ЭВМ значения элементарных математических функций вычисляются с использованием стандартных подпрограмм. В них, как правило, реализуется одно из известных разложений требуемой функции в степенные ряды вида [10. 14]: п 0

При этом сам алгоритм вычисления строится, как правило, по схеме Горнера [15]: п f(x) = Yuan =(-(arn -x + a^-x + .-. + a^-x + ciQ . о

Суммарное время требуемое для вычисления функции приблизительно можно оценить выражением: h -m-{tmult+tadd)^ где: ш - степень полинома; tmuit - время выполнения операции умножения; tadd " вРемя выполнения операции сложения-вычитания.

Для вычисления значение у = л[х обычно используется итерационный метод Герона: r<+i=°-5{yt+/y,) причем используемые алгоритмы различаются только выбором начального приближения у0 .

Существуют итерационные методы и для вычисления функций ехр(х) и 1п(х) [16]. Вычисление выполняется в два этапа. На первом этапе аргумент функции 1п(х) представляется в виде: 1

П& + 5.-2-')' i= 1 а функции exp(x) в виде: i где: n - разрядность вычисляемой функции;

- коэффициент, принимающий значения 0 и 1 или-1,+1.

На втором этапе, на основании найденного на предыдущем этапе набора значений , определяется величина вычисляемой функции. Это выполняется либо путем суммирования слагаемых вида //?(l + • 2-'где i-oe слагаемое соответствует i-ому произведению первого этапа, либо с помощью вычисления произведения (l + *2-/ ], где i-ый член произведения соответствует i-ому слагаемому, используемому на первом этапе. Каждый этап вычисления выполняется за п шагов и представляет собой итерационный процесс, состоящий в построении последовательности xl — f{xtj) с шагом итерации 5,- = хг- — Хг|. Каждая итерация первого этапа состоит в определении значения ^ на основании знака 8г-. На каждой итерации второго этапа определяется очередной член последовательности х{, сходящийся к вычисляемой функции.

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

В силу итерационного метода вычисления и заложенной в стандартные ЭВМ фон Неймановской архитектуры, непосредственное использование описанных алгоритмов применительно в ПЛИС не позволяет минимизировать время получения результата.

В [17,18] описаны алгоритмы вычисления тригонометрических функций sin(x), cos(x), arcsin(x) и arctg(x) с использованием ПЛИС. Рассмотрены различные виды аппроксимации этих функций степенными рядами и применение табличного метода с линейной интерполяцией. Проведен сопоставительный анализ данных методов с точки зрения компромисса между получением максимального быстродействия, точностью вычисления и затратам аппаратных ресурсов на реализации. Приведены последовательно-параллельные графы рассмотренных алгоритмов. Показано, что наиболее рациональным при вычислении функций sin(x), cos(x), arctg(x) является табличный метод с линейной интерполяцией.

Оптимальный метод вычисления функции arcsin(х) зависит от требуемого диапазона изменения аргумента. Однако в приведенных работах отсутствует исследование погрешностей

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

Следует отметить, что работы, аналогичные [17, 18] применительно к функциям ехр(х) и 1п(х) полностью отсутствуют.

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

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

Задачи исследования. Для достижения поставленной цели необходимо решить следующие задачи:

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

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

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

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

- Разработать пакет прикладных программ необходимый для разработки мегафункции

1 вычисления функции ехр(х) и проанализировать полученные программы с точки зрения обеспечения требуемой точности и аппаратных затрат ПЛИС на их реализацию.

Научная новизна: К новым результатам проведенных исследований по теме

11 диссертации относятся:

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

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

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

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

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

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

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

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

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

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

Достоверность полученных результатов, выводов и рекомендаций, сформулированных в работе, подтверждается использованием для их получения апробированного математического аппарата и средств формального описания цифровых устройств, а так же результатами вычислительного эксперимента, выполненного с использованием общепринятых в промышленности систем автоматизированного проектирования электронных средств (EDA), а именно, системы проектирования Quartus II фирмы Altera.

Основные положения, выносимые на защиту:

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

- Алгоритм построения аппроксимирующего многочлена высокой степени, предназначенный для численного вычисления экспоненциальной функции, обеспечивающий при реализации на ПЛИС оптимальное разбиение аргумента на расчетные интервалы, что при произвольном диапазоне изменения аргумента и требуемой точности вычисления позволяет минимизировать как аппаратный затраты, так и время вычисления.

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

Апробация работы и публикации

Основные результаты работы докладывались на Международной молодежной научной конференции «Гагаринские чтения» 2006 и 2007 годов, III научной международной конференции «Современные проблемы науки и образования», г.Москва, 13-15 мая 2008г, Всероссийской научно-технической конференции «Новые материалы и технологии», Москва 11-13 ноября 2008г и Международной научной конференции «Технические науки и современное производство» Пекин 26 ноября - 4 декабря 2008 г .Основные результаты работы опубликованы в 9 научных трудах.

Структура диссертационной работы.

Диссертация состоит из введения, 5-и глав, заключения, списка использованных источников и приложений.

Выводы по главе 5

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

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

3. Выполнен вычислительный эксперимент для различных способов модификации исходных многочленов Чебышева и показано, что оптимальным, с точки зрения точности вычисления является случай использование замены j=2 и у=2.86х-1.

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

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

Заключение

Проведенные исследования позволили получить следующие результаты: 1. Проведен сопоставительный анализ известных методов численного определения значения экспоненциальной функции и выявлена зависимость остаточной погрешности вычисления от вида аппроксимирующего многочлена. Показано, что все известные методы могут быть сведены к вычислению многочлена высокого порядка. При этом повышение точности требует сужения диапазона изменения аргумента и использовании для вычисления значения функции от отрицательного аргумента соотношения ехр(—х) = • х"

2. Для разложения функции в степенной ряд вида ехр(х)—^— предложена методика получения корректирующего коэффициента, компенсирующего остаточную погрешность, обусловленную ограничением числа членов расчетного степенного ряда. Получены аналитические выражения для корректирующего коэффициента при 5 членах ряда, позволяющие на 3 порядка повысить точность вычисления функции.

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

4. Показано, что с точки зрения реализации на ПЛИС, наиболее перспективным является метод использующий многочлены Чебышева, с оптимизированной под заданный диапазон изменения аргумента заменой переменных. Предложена методика модификации переменной в многочлене Чебышева из условия получения максимальной точности вычисления при заданном диапазоне изменения аргумента. На основе предложенной методики найдено, что для диапазона изменения аргумента Q<x<ln2 оптимальной является подстановка переменной в многочлене Чебышева (2.86-х-1 1 ^ вида у ■ 2-2.86 2-2.86.

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

183 что для случая аппроксимирующего многочлена четвертого порядка более чем на три порядок повышает точность вычисления функции. Повышение порядка исходного аппроксимирующего многочлена приводит к еще большему выигрышу по точности вычисления.

5. Для стандартных мегафункций САПР Quartus II Ipmaddsub и lpmmult, реализующих операции сложения-вычитания и умножения, получены аналитические зависимости, связывающие необходимые аппаратные ресурсы ПЛИС и время выполнения операции с разрядностью операндов.

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

7. Разработаны алгоритмы вычисления, позволяющие вычислять значение функции при произвольном диапазоне изменения аргумента. Получены зависимости точности вычисления и количества выполняемых математических операций от расчетного диапазона изменения аргумента. Показано, что с точки зрения обеспечения требуемой точности вычисления при требовании минимизации аппаратных ресурсов ПЛИС на реализацию, оптимальным является расчетный диапазон изменения аргумента, определяемый условием 0 < х < In 2 .

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

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

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

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

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

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

1. В.Б.Стешеико. EDA Практика автоматизированного производства радиоэлектронных устройств- М.: Издатель Молгачева С.В., Издательство «Нолидж», 2002г. - 768с.

2. В.А.Хацук. Реализация ЦОС на ПЛИС структуры РРОА:высокая производительность и низкая стоимость реализации. «Электроника инфо» №6, 2004г., стр. 23.26.

3. О.А. Бабич Обработка информации в навигационных комплексах. М.Машиностроение, 1991 г.-512 с.

4. Воробьев Л.М. Воздушная навигация. М.: Машиностроение, 1984. - 256с., ил.

5. Фарина А., Студер Ф. Цифровая обработка радиолокационной информации. Сопровождение целей: Перев.с англ. М.: Радио и Связь, 1993. — 320с., ил.

6. Матричный метод стандартных кинематических связей при разработке алгоритмов управления в системах угловой ориентации. / Волков Н.Н., Волков А.Н.// ICA'97 II Международный Аэрокосмический Конгресс. -М., Сентябрь 1997. Сб. докладов, -с. 193196.

7. Харин Е.Г. Комплексная обработка информации навигационных систем летательных аппаратов. Опыт многолетнего практического применения. Учебное пособие. М.: Изд-во МАИ, 2002.-264с.: ил.

8. Беляевский Л.С., Новиков B.C., Олянюк П.В. Обработка и отображение радионавигационной информации. М.: Радио и связь, 1990. - 233 е.: ил.

9. Виноградов А.П. Основы обработки радиолокационной информации. 4.2 Вторичная обработка радиолокационной информации. СПб: Издание ВУ ПВО (филиал) 2002г.

10. Бут Э., Бут К. автоматические цифровые машины. М.,Физматгиз, 1959 г.

11. Ленский В.П. Вычисление элементарных функций на автоматических цифровых машинах. В сб, «Вычислительная математика»., вып.2 1957 г.- с90.119.

12. Kogbetliants E.G., Computation of eN for — со <N < +oo using an electronic computer., IBM Journal Research and Development 1. №2 1957 p.110. 115.

13. Kogbetliants E.G., Computation of arctan N for — со < N < +oo using an electronic computer., IBM Journal Research and Development 2. № 1958 p.43.53.

14. Kogbetliants E.G., Computation of sin(N), cos(N) and using an electronic computer.,

15. M Journal Research and Development 3. №2 1959.

16. Благовещенский Ю.В. Теслер Г.С. Вычисление элементарных функции на ЭВМ. ,Киев, из-во «Техника», 1977г.

17. Байков В.Д., Смолов В.Б. Аппаратурная реализация элементарных функций t в ЦВМ., Ленинград, Изд-во Ленинградского университета, 1975 г.17.