Реферат: Название диссертации

Объявление о защите кандидатской диссертации



ФИО

Мо Чжо Чо

Название диссертации

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

Специальность

05.13.05 – Математическое моделирование, численные методы и комплексы программ

Отрасль науки

Технические науки

Шифр совета

Д 212 .110 .08

Телефон учёного секретаря

Диссертационного совета

8-499-141-94-55

E-mail

electron_inform@mail.ru

Предполагаемый срок защиты диссертации

12 ноября 2009г , в 14.00

Место защиты диссертации

ул. Оршанская , 3 , ауд. 612А



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

Диссертационного совета Д 212.110.08

____________________/ Спыну М.В.

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


Мо Чжо Чо


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

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


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

и комплексы программ


Автореферат

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

кандидата технических наук


^ Москва – 2009г


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


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

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


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

профессор

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


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

доцент

Чумакова Екатерина Витальевна


Ведущая организация: ^ ОАО «НПО «ЛЭМЗ»


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


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


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


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


Автореферат разослан «_____» _________________2009 г.


Ученый секретарь диссертационного совета Д212.110.08

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


Спыну М.В.




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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

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

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

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

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

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

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

.

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



Рис.1

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

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

,

где: значения и - функции Бесселя мнимого аргумента порядка .

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

где: i и j – целые числа.

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

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




Рис.2.

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

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

где: и

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



Рис.3.

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



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

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

,

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

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

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

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

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

1



2



3



4



5





Рис.4.

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

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

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

, где: .

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

Сопоставительный анализ всех рассмотренных методов позволяет сделать вывод, что все они сводятся к вычислению некоторого многочлена высокой степени от аргумента. Отличия состоят только в составе и числе выполняемых операций необходимых для достижения требуемой точности получения результата. В таблице 2 для рассмотренных методов вычисления перечислены типы и количества выполняемых операций, необходимые для получения заданной точности вычисления. (Ns – количество сложений, Nm – количество умножений, Nd – количество делений)

Таблица 2

Относительная

погрешность

10-1 %

10-2 %

10-3 %

10-4 %

10-5 %

10-6 %

10-7 %

10-8 %

10-9 %

10-10 %

Степенной ряд

Ns

Nm

Nd

5

8

0

6

10

0

7

12

0

8

14

0

9

16

0

10

18

0

11

20

0

12

22

0

13

24

0

14

26

1

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

Ns

Nm

Nd

4

6

0

5

8

0

6

10

0

7

12

0

8

14

0

9

16

0

10

18

0

10

18

0

11

20

0

12

24

0

Многочлены

Чебышева

Выр-е 1.23

Ns

Nm

Nd

5

6

0

8

8

0

11

12

0

15

16

0

19

21

0

19

21

0













Многочлены

Чебышева

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

Ns

Nm

Nd

4

3

0

6

6

0

9

8

0

9

8

0

12

12

0

16

16

0

20

21

0

20

21

0







Многочлены

Чебышева

Модифицированное выражение

Ns

Nm

Nd

2

2

0

2

2

0

4

4

0

6

7

0

6

7

0

9

9

0

9

9

0

12

13

0

12

13

0

16

17

0

Многочлены

Лежандра

Ns

Nm

Nd

6

9

0

7

11

0

9

13

0

10

15

0

12

17

0

13

19

0













Многочленное

приближение


Ns

Nm

Nd

3

5

0

4

7

0

5

9

0

5

9

0

6

11

0

7

13

0

7

13

0

8

15

0

9

17

0

9

17

0

Цепная дробь


Ns

Nm

Nd

4

4

1

4

4

1

4

4

1

5

6

1

5

6

1

6

8

1

6

8

1

6

8

1

7

10

1

7

10

1

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

приближение

Ns

Nm

Nd

6

8

1

6

8

1

6

8

1

8

11

1

8

11

1

8

11

1

8

11

1










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

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

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

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

Nлб = n + 1.

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

Nлб = 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 .

при параметре maximize_speed = 10 .

Для для ПЛИС семейства Stratix II .

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

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

а) ПЛИС Cyclone II

б) ПЛИС Stratix II

Рис.5

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

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

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

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

,

где: и ;

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

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



а) ПЛИС Cyclone II


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



Рис. 8.

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

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

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

,

где: ;

;

;

;

.

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



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

,

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

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

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



Рис.9.

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

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



а)



б)

Рис.10

В таблице 4 приведены рассчитанные с использованием результатов главы 4 рекомендуемые соотношения между разрядностями представления аргументов (R) и коэффициентов аппроксимирующего многочлена. С использованием графа рис.8 и рекомендаций таблицы 4 на языке AHDL была разработана программа для вычисления экспоненциальной функции при условии . Данная программа явились основой для проведения вычислительного эксперимента с целью подтверждения полученных в работе теоретических положений.

Таблица 4.

Узел графа

dataA

dataB

Result

1м1

a1→(R+1)

^ INPUT→ (R)

(R)+1

1м2

INPUT→ (R)

INPUT→ (R)

(R-1)+2

2м1

a2→(R+1)

1M2→ (R-1)+2

(R-1)+2

2м2

1M2→ (R-1)+2

1M2→ (R-1)+2

(R-2)+2

2м3

1M2→ (R-1)+2

^ INPUT→ (R)

(R-1)+2

3с1

1M1→ (R)+1

2M1→ (R-1)+2

(R-1)+2

3м1

2M2→ (R-2)+2

a4→(R)

(R-2)+2

3м2

2M3→ (R-1)+2

a3→(R)

(R-1)+1

4с1

3S1→ 1+(R-1)+2

a0→(R+2)

(R)+2

4с2

3M1→ (R-2)+2

3M2→ (R-1)+1

(R-2)+2

5с1

4S1→ (R)+1

4S2→ 1+(R-2)+2

(R-1)+2

6м1

5S1→ (R-1)+2

5S1→ (R-1)+2

REZ→ (R-2)+2

В работе для всех рассмотренных ранее случаев (j=1, y=x; j=1, y=2x-1; j=1, y=2.86x-1; j=1, y=3x-1; j=2, y=2x-1; j=2, y=2.86x-1; j=2, y=3x-1) определены значения коэффициентов аппроксимирующего многочлена и получены зависимости ошибки вычисления от значения аргумента. Для случая j=2, y=2.86x-1 получена зависимость ошибки вычисления от числа разрядов аргумента, подтвердившая положение о том, что для каждого случая представления существует некоторое предельное число разрядов аргумента, дальнейшее увеличение которого не ведет к повышению точности вычисления.

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

Метод замены

Число разрядов

Относительная ошибка %

Число ЛБ

Число умножителей

Время счета

аргумент

результат

j=1, y=x

17

12

5.25·10-4

72

14

29.25nS

j=1, y=2x-1

18

16

3.08·10-5

214

26

33.75nS

j=1, y=3x-1

23

18

9.66·10-6

1322

26

48.54nS

j=1, y=2.86x-1

23

19

4.05·10-6

1290

26

47.15nS

j=2, y=2x-1

25

21

1.9·10-6

1696

36

60,02nS

j=2, y=2.86x-1

29

23

3.18·10-7

3552

36

76.61nS

j=2, y=3x-1

28

22

7.05·10-7

3304

36

72.85nS

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

Число разрядов

Время счета

Число логических блоков (LB2)

Число 9 бит умножителей (M2)

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