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

На правах тзгбййй

Ж

Попов Святослав Дмитриевич

Разработка математической модели и пакета прикладных программ для нахождения численного значения элементарных функций средствами СБИС программируемой логики

05.13.18 — «Математическое моделирование, численные методы и комплексы программ»

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

12 ДЕК 2013

Москва —2013

005543458

005543458

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

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

Официальные оппоненты:

Ведущая организация:

доктор технических наук Опадчий Юрий Фёдорович

Муравей Леонид Андреевич, д.ф.-м.н., профессор, зав. каф. «Прикладная математика и информационные технологии»,

Николаев Александр Николаевич, к.т.н., Главный конструктор - начальник отдела ОАО «НПО «ЛЭМЗ»

ФГБОУ ВПО «Московский государственный технический университет имени Н.Э. Баумана»

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

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

Автореферат разослан 25 ноября 2013 г.

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

кандидат физико-математических наук Спыну Марина Валерьевна

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

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

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

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

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

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

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

Задачи исследования:

• Адаптация известных математических моделей процесса нахождения численного значения многочлена применительно к СБИС ПЛ и

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

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

• Исследование возможности применения алгоритма на основе метода БВЕ для нахождения численного значения экспоненциальной функции средствами СБИС ПЛ.

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

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

Научная новизна:

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

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

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

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

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

ставления аргумента с точностью от 9-ти до 32-х разрядов дробной части.

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на Всероссийской научно-технической конференции «Новые материалы и технологии» в 2012 году и на Международной молодежной научной конференции «Гагаринские чтения» 2010, 2011 и 2012 годов.

Основные результаты работы опубликованы в шести научных трудах, два из которых — в изданиях, рекомендованных ВАК РФ.

Объём и структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы и одного приложения; общий объём 120 страниц.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

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

Алгоритм схемы Горнера не поддаётся распараллеливанию, поэтому величины и а также величины и С^ совпадают:

Алгоритм универсальной схемы с предварительной обработкой коэффициентов поддаётся распараллеливанию, однако, зависимость количества умножителей от степени многочлена п сохраняет линейный характер. Без учёта нетривиальной предварительной обработки коэффициентов искомые величины С£, ¿п и ^п выражаются следующим образом:

Алгоритм схемы на основе канонической формы многочлена

дальнейшее параллельное попарное суммирование полученных значе-

Гх = С+ = п 11=11 = п.

!к + 2, п = 4к + 1, к + 3, п е [4к + 2,4к + 3}, к + 4, я = 4к + 4,

1+ = Iх + 1

где

предполагает распараллеливание вычисления слагаемых вида а^х и

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

Из полученных выражений для величин и ¿п следу-

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

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

где

шп -

в противном случае.

Рх = X2,

"На"

а21+1х + агь 1 = 0,1, -, 1(п + 1)/2], а21, 1 = \(п + 1)/2], п Л 1 = О,

Р; = Р;-г X Ру-1.

¿ = 0Д,...,[(т;_1 + 1)/2], I = [(т;_! + 1)/2], т^! Л 1 = О,

Рт,0 ~ Рш-1 х Рт-1,1 + Рт-1,0» РпОО = Рт,0»

где т! = ту = [т,21+1],У = 2,т - 1, т = Г1с^2(п + 1)1.

Для разработанной математической модели получены явные аналитические выражения для и

где п 6 И\{1,2}, к = п.1- При л е {1,2} оптимизированная схема совпадает со схемой Горнера.

Ниже на рис. 1 представлены зависимости величин и от степени многочлена п при п е [1,64].

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

где п = 21, I £ М; а£, с£ — целочисленные коэффициенты. В результате специальных преобразований суммирование ряда проводится

С£ = п + к, = п, 1*=1+ = к + 1,

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

— Схема Горнера

— Универсальная схема с предварительной обработкой коэффициентов

— Схема на основе канонической формы многочлена

— Оптимизированная схема

о 20 40 60

Степень многочлена

0 20 40 60

Степень многочлена

¡120 и 100

I

I 80

я о

Щ

£ 60 О

£ 40

о а>

в 20 и

20 40 60

Степень многочлена

а бо

1 5°

к

§ 40

I

а 30

о

|го

20 40 60

Степень многочлена

Рис. 1. Зависимости величин и от степени мно-

гочлена п при п е [1,64].

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

чения экспоненциальной функции средствами СБИС ÜJI ввиду следующих причин:

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

• высокая ресурсоёмкость и низкое быстродействие по сравнению с известными методами;

• неудобная на практике область определения (0,0.25).

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

где К е N\{ 1}; ßt е Z+( f = 2JC-, ßt E [о, 2zi_1) ,i = 3JC.

Пусть аргумент определён на промежутке S конечной длины. Тогда численное значение экспоненциальной функции получается следующим образом:

ехрх = |~~| Mit

где

ki j _

= i — 2,K; kiEN-,

j=o J'

ßi ßi -

P2 = ^p- + infs; Vi = 3>K-

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

ми СБИС ГШ, а также применяются таблицы заранее рассчитанных значений вместо наиболее длинных последовательностей арифметических операций.

Проведён подробный анализ вычисления значений Л/; при п е [9,32], где п — количество разрядов в дробной части аргумента, иными словами, аргумент представлен в памяти СБИС ПЛ с точностью 2~п. Показана необходимость применения таблиц заранее рассчитанных значений М2иМ3 — наиболее громоздких в точки зрения сложности вычисления на СБИС ПЛ. Алгоритм вычисления значений Д/£, I = 4, К, требует применения исключительно целочисленных арифметических операций и поддаётся значительной оптимизации за счёт применения операции записи в память вместо явных сложений.

Проведён подробный анализ разработанной математической модели, в ходе которого получены оценки погрешности вычислений при п 6 [9,32]. Анализ проводился для случая применения таблиц заранее рассчитанных значений М2 и М3, где значения хранятся с точностью 2-1™2, т2 £ М. В рассматриваемых условиях возможны пять комбинаций параметров разработанной математической модели, для каждой из которых получены оценки абсолютной погрешности численного значения экспоненциальной функции.

Для краткости введём Е2 — е2 4124;шр515 которое больше любой величины в таблице заранее рассчитанных значений М2. При п е [9,16], К = 4, к4 = 1 абсолютная погрешность оценивается сверху следующим образом:

Д(ехр х) < Е2(1.0039 • 2~тг + 0.5282 • 2~16) + 1.0646 ■ 2~"Ч Граф соответствующего алгоритма представлен на рис. 2. Например, при 5 = [— 2,2), т2 = 18 верна следующая оценка:

Д(ехрх) < 2

-13

3.2 Рз

У I

(МзЫ)

1 + М

£

1ех2М]

Рис. 2. Граф алгоритма при п е [9,16], К = 4, к4 = 1.

При п 6 [9,16], К = 4, к4 = 2 абсолютная погрешность оценивается сверху следующим образом:

Д(ехрх) < £-2(1.0039 ■ 2~т2 + 0.7015 • 2-26) + 1.06 46 ■ 2_т2. Граф соответствующего алгоритма представлен на рис. 3. Например, при 5 = [—2,2), т2 = 18 верна следующая оценка:

Д(ехрх) < 2-14.

При п е [17,32], К = 5, к4 = 2, /е5 = 1 абсолютная погрешность оценивается сверху следующим образом:

Д(ехрх) < Е2(1.004 • 2'™* + 0.7098 • 2~26) + 1.0 6 46 ■ 2~т Граф соответствующего алгоритма представлен на рис. 4. Например, при Б = [—2,2), т2 = 28 верна следующая оценка:

Д(ехрх) < 2"23.

При п е [17,32], К = 5, к4 = 3, к5 = 1 абсолютная погрешность оценивается сверху следующим образом:

Д(ехр л:) < £2(1-004 • 2~т* + 0.6093 ■ 2-32) + 1.06 46 • 2~т Граф соответствующего алгоритма представлен на рис. 5. Например, при 5 = [—2,2), т2 = 34 верна следующая оценка:

Д(ехрх) < 2-29.

Р2 Рз

Рд

М;[М) (МзЩ)

Р2 Рв Р<

+ V"-

(м2[ц,1) (Щм) (х>—

1 + Рд2 16 + (р4)22 33

Рз

1 + Рб2 3

^-1 + рл2'16 +

р42'10 + (р4)22-33

ехр(х) 1

Рис. 3. Граф алгоритма при п £ [9,16], К = 4, к4 = 2.

1 ехр(х) | Рис. 4. Граф алгоритма при п £ [17,32], К = 5, к4 = 2, к5 = 1. При п е [17,32], К = 5, к4 = 3, к5 = 2 абсолютная погрешность оценивается сверху следующим образом:

Д(ехрх) < £2 (1.004 ■ 2-т* + 0.6156 ■ 2~35) + 1.0646 • 2~т*. Граф алгоритма вычисления представлен на рис. 6. Например, при 5 = [—2,2) , т2 = 34 верна следующая оценка:

Д(ехр х) < 2~30.

Рг Рз _ Р* Р5

(М2М) (МзМ)

Р2 РЗ

®

а

1 + р„2"16 + а -

1 + ра

М2[р,]) (м3[ь]) Ы)*- (х

А

I

1 + р42"16 + а-1_

I ехр(х) I

Рис. 5. Граф алгоритма при

I ехррс) |

Рис. 6. Граф алгоритма при

п е [17,32], К = 5, к4 = 3, к5 = 1. п 6 [17,32], К = 5, к4 = 3, к5 = 2.

Предложены способы оптимизации применения таблиц заранее рассчитанных значений, позволяющие сократить суммарный размер таблиц и расширить область изменения аргумента. Например, при ¿5 = где ¿5 — длина промежутка 5, без оптимизации требуется хранить 80 значений в двух таблицах, тогда как с применением оптимизаций требуется хранить 64 значения в двух таблицах.

Отметим, что при ¿5 = 256 с применением оптимизаций требуется хранить лишь 64 значения в четырёх таблицах. На практике необходимость в столь большой области допустимых значений встречается крайне редко, следовательно, можно говорить о практическом отсутствии необходимости применять методы приведения аргумента.

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

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

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

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

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

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

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

В четвёртой главе проведено моделирование процесса нахождения численного значения экспоненциальной функции с помощью разработанного комплекса прикладных программ. Моделирование проводилось средствами САПР электронной аппаратуры Altera Quartos II 9.0. Моделирование проводилось с целью выяснить фактическую точность и быстродействие вычисления экспоненциальной функции с помощью разработанной математической модели при раз-

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

Для сравнения с известными аналогами выбраны мегафункция altfp_exp, поставляемая в комплекте с САПР электронной аппаратуры Altera Quartus П 9.0, и метод ортогонального приближения с использованием многочленов Чебышёва.

Результаты моделирования подтверждают преимущество разработанной математической модели нахождения численного значения экспоненциальной функции над известными аналогами в плане быстродействия и точности вычислений. Например, предложенный метод при К = 5, /с4 = 3 и /с5 = 2 характеризуется наименьшим быстродействием среди всех рассмотренных в работе комбинаций параметров. При этом он обеспечивает в 1.62 раза больший уровень быстродействия и в среднем большую на 7 верных разрядов точность вычислений по сравнению с мегафункцией altf р_ехр; а по сравнению с методом ортогонального приближения с использованием многочленов Чебышёва предложенный метод при К = 5, к4 — 3 и к5 = 2 обеспечивает незначительный прирост производительности при значительном увеличении точности вычислений: в среднем на 7 верных разрядов больше. Следует отметить, что измерение быстродействия конечного устройства на основе метода ортогонального приближения с использованием многочленов Чебышёва проводилось в чистом виде, т.е. без приведения аргумента.

ВЫВОДЫ

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

для различных математических моделей нахождения численного значения многочлена.

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

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

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

5. Разработан комплекс прикладных программ для нахождения численного значения экспоненциальной функции, позволяющих синтезировать структуру СБИС ПЛ, необходимых для создания соответствующих мегафункций. Проведённое моделирование подтвердило преимущество разработанной математической модели в плане быстродействия и точности вычислений. Например, для наиболее медленного из предложенных вариантов математической модели по сравнению со стандартной мегафункцией а1^р_ехр обеспечивается увеличение быстродействия в 1.62 раза, а результат вычислений содержит в среднем на 7 верных разрядов больше.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Попов С.Д., Опадчий Ю.Ф. Вычисление показательной функции на ПЛИС // Современные проблемы науки и образования. - 2013. -№5; URL: www.science-education.ru/lll-10145 (дата обращения: 14.11.2013).

2. Попов С.Д., Опадчий Ю.Ф. Применение метода БВЕ для вычисления функции ехр х на ПЛИС // Фундаментальные исследования. — 2013. — №10 (часть 5). — С. 1014-1018. URL: www.rae.ru/fs/?section=content&op=show_article&article_id=l 000165 4 (дата обращения: 14.11.2013).

3. Опадчий Ю.Ф., Попов С.Д. Вычисление многочлена на ПЛИС: оптимизация элементной базы // НОВЫЕ МАТЕРИАЛЫ И ТЕХНОЛОГИИ — НМТ-2012. Материалы Всероссийской научно-технической конференции. — М.: МАТИ. — 20-22 ноября 2012 г. — С. 268-269.

4. Попов С.Д. Применение метода БВЕ для вычисления трансцендентных функций на ПЛИС // XXXVI ГАГАРИНСКИЕ ЧТЕНИЯ. Научные труды Международной молодёжной научной конференции в 8 томах. — М.: МАТИ. — 6-10 апреля 2010 г. — Т. 8 — С. 123-124.

5. Попов С.Д. Модификация метода БВЕ для вычисления функции ехр х на ПЛИС // XXXVII ГАГАРИНСКИЕ ЧТЕНИЯ. Научные труды Международной молодёжной научной конференции в 8 томах. — М.: МАТИ. — 5-8 апреля 2011 г. — Т. 4 — С. 249-251.

6. Попов С.Д. Анализ графа алгоритма вычисления многочлена // XXXVIII ГАГАРИНСКИЕ ЧТЕНИЯ. Научные труды Междуна-

родной молодёжной научной конференции в 8 томах. — М.: MATH. — 10-14 апреля 2012 г. —Т. 4 — С. 94-96.

Подписано в печать 25.11.2013 г Формат А5 Бумага офсетная. Печать цифровая. Тираж 100 экз. Заказ № 1791 Типография ООО "Ай-клуб" (Печатный салон МДМ) 119146, г. Москва, Комсомольский пр-т, д.28 Тел. 8(495)782-88-39

«МАТИ — РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К.Э. ЦИОЛКОВСКОГО»

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

04201452345

ПОПОВ СВЯТОСЛАВ ДМИТРИЕВИЧ

РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ И ПАКЕТА

ПРИКЛАДНЫХ ПРОГРАММ ДЛЯ НАХОЖДЕНИЯ ЧИСЛЕННОГО ЗНАЧЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ СРЕДСТВАМИ СБИС ПРОГРАММИРУЕМОЙ ЛОГИКИ

Специальность 05.13.18 — «Математическое моделирование, численные методы и комплексы программ»

ДИССЕРТАЦИЯ на соискание учёной степени кандидата технических наук

Научный руководитель д.т.н. Опадчий Ю.Ф.

Москва 2013

СОДЕРЖАНИЕ

Введение.........................................................................................................................4

Глава 1. Особенности вычисления многочлена на СБИС ПЛ..............................12

1.1. Значение многочленов применительно к вычислениям на СБИС ПЛ......12

1.2. Определения....................................................................................................13

1.3. Схема Горнера.................................................................................................13

1.4. Индивидуальные схемы.................................................................................15

1.5. Универсальные схемы с предварительной обработкой коэффициентов для многочленов четвёртой и шестой степеней..............17

1.6. Универсальная схема с предварительной обработкой коэффициентов для многочлена произвольной степени........................................................22

1.7. Параллельный метод вычисления многочлена средствами СБИС ПЛ.....28

1.8. Сравнительный анализ рассмотренных схем...............................................37

1.9. Выводы.............................................................................................................38

Глава 2. Оптимизация алгоритма вычисления многочлена средствами СБИС ПЛ......................................................................................................................39

2.1. Преобразование и схема вычисления многочлена......................................39

2.2. Анализ алгоритма применительно к СБИС ПЛ...........................................42

2.3. Сравнительный анализ рассмотренных схем...............................................47

2.4. Выводы.............................................................................................................48

Глава 3. Вычисление экспоненциальной функции средствами СБИС ПЛ..........49

3.1. Метод БВЕ.......................................................................................................49

3.2. Применение метода БВЕ для нахождения численного значения экспоненциальной функции...........................................................................51

3.3. Применение метода БВЕ для нахождения численного значения экспоненциальной функции средствами СБИС ПЛ....................................54

3.4. Оптимизированная математическая модель нахождения численного значения экспоненциальной функции применительно к СБИС ПЛ..........57

3.4.1. Определения и вспомогательные утверждения.....................................57

3.4.2. Оптимизированная математическая модель..........................................58

3.4.3. Табличный метод......................................................................................62

3.4.4. Явное вычисление множителей М£.........................................................63

3.4.5. Точность вычислений при п Е [17,32]..................................................67

3.4.6. Точность вычислений при п 6 [9,16].....................................................71

3.4.7. Приведение произвольного аргумента к области определения алгоритма...................................................................................................74

3.4.8. Оптимальное применение табличного метода......................................76

3.4.9. Вычисление показательной функции.....................................................78

3.5. Методика подбора параметров алгоритма...................................................79

3.6. Выводы.............................................................................................................81

Глава 4. Эксперименты.............................................................................................83

4.1. Цель и условия моделирования.....................................................................83

4.2. Результаты эксперимента для конфигурации К = 4, к4 = 1....................84

4.3. Результаты эксперимента для конфигурации К = 4, к4 = 2....................86

4.4. Результаты эксперимента для конфигурации К = 5, к4 = 2, к5 = 1......88

4.5. Результаты эксперимента для конфигурации К = 5, к4 = 3, к5 = 1......91

4.6. Результаты эксперимента для конфигурации /Г = 5, к4 = 3, к5 = 2......93

4.7. Сравнение со стандартной мегафункцией altf р_ехр...............................95

4.8. Сравнение с актуальными методами вычисления экспоненциальной функции............................................................................................................97

4.9. Выводы.............................................................................................................99

Заключение................................................................................................................101

Литература.................................................................................................................102

Приложение...............................................................................................................106

ВВЕДЕНИЕ

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

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

Специализированные вычислители реализуются на основе заказных или полузаказных сверхбольших интегральных схем (СБИС) [24, 33, 31], позволяющих распараллелить алгоритм работы на аппаратном уровне и обеспечить минимизацию массо-объёмных характеристик оборудования при заданном уровне быстродействия. Лучшие показатели быстродействия и массо-

объёмных характеристик обеспечивают заказные СБИС, однако, производство таких СБИС оправдано только в больших объёмах. Применение полузаказных СБИС, например, базовых матричных кристаллов (БМК) [28], позволяет снизить стоимость производства, однако, в случае малых объёмов стоимость производства остаётся высокой, т.к. требуется заводской производственный процесс и отсутствует возможность корректировать конечное устройство.

Сегодня наиболее оптимальным решением для малобюджетных и среднебюджетных проектов являются СБИС программируемой логики (СБИС ПЛ) [1, 5, 7, 14], совмещающие возможность аппаратного распараллеливания алгоритмов и гибкость реализации, как у любых программных решений.

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

Проектирование структуры СБИС ПЛ требует применения соответствующих САПР электронной аппаратуры. В современных САПР используется некоторый язык описания аппаратуры — HDL (Hardware Description Language). Например, универсальный язык VHDL (Verilog HDL), разработанный с целью формального описания логических схем для всех этапов разработки электронных систем, начиная с модулей микросхем и заканчивая крупными вычислительными системами. Универсальный подход в языке VHDL не позволяет учитывать особенности конкретных интегральных схем, поэтому производители аппаратных средств предлагают собственные языки HDL.

Например, фирма Altéra в собственной САПР электронной аппаратуры Quartus II [25], кроме поддержки языка VHDL, предлагает язык AHDL (Altéra Hardware Description Language) [1, 2, 26], учитывающий особенности элементной базы продуктов фирмы Altéra.

Языки HDL позволяют многократно использовать однажды написанный код. Предназначенный для многократного применения код оформляется в виде мегафункций или подключаемых модулей. Благодаря такой возможности появились обширные библиотеки мегафункций, в том числе поставляемых в комплекте с САПР. В виде мегафункций или подключаемых модулей доступны реализации различных микропроцессоров и микроконтроллеров, реализации быстрого преобразования Фурье, различные математические функции и т.д. [27].

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

Решение конкретных практических задач в большинстве случаев требует вычисления значений элементарных математических функций. В составе САПР электронной аппаратуры Quartus II поставляются мегафункции, обеспечивающие синтез универсальных блоков для вычисления различных элементарных функций. Эти блоки работают с данными, представленными, согласно стандарту IEEE-754, в виде 32-битных или 64-битных слов. При решении практических задач часто возникают ситуации, при которых либо точность, либо затраты аппаратных ресурсов на реализацию, обеспечиваемые стандартными мегафункциями, являются чрезмерными.

Таким образом, вопрос нахождения численных значений элементарных математических функций [8, 9, 10, 16], несмотря на известные технические

решения, например, [19], по-прежнему, является весьма актуальным. Решение этого вопроса, на практике, требует вычисления некоторого многочлена, степень которого определяет точность получаемого результата. Известны такие методы вычисления многочлена [3], как схема Горнера [15], или методы, основанные на предварительной обработке коэффициентов. Пан В.Я. предложил универсальную схему вычисления многочлена с предварительной обработкой коэффициентов [20 ... 23], отличающуюся меньшим количеством операций умножения по сравнению со схемой Горнера. Однако, указанные схемы нацелены на использование стандартных для ЭВМ последовательных методов вычисления, что не позволяет минимизировать время вычисления на СБИС ПЛ, предоставляющих возможности для распараллеливания алгоритма работы.

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

Вопрос нахождения численного значения экспоненциальной функции средствами СБИС ПЛ подробно рассмотрен в работах [17, 18]. В работе [18] рассмотрено большинство известных методов, например, [4] и [6]. Среди рассмотренных методов наиболее оптимальным в плане быстродействия СБИС ПЛ признан метод ортогональных приближений с использованием многочленов Чебышёва.

В работе [18] присутствует упоминание предложенного Карацубой Е.А. метода БВЕ [12, 32] (быстрого вычисления Е-функций) — метода быстрого суммирования рядов специального вида. В работе [11] предложен алгоритм нахождения численного значения экспоненциальной функции на основе метода

БВЕ. Однако, вопрос применения этого алгоритма на СБИС ПЛ не был рассмотрен.

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

Задачи исследования:

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

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

• Исследование возможности применения алгоритма на основе метода БВЕ для нахождения численного значения экспоненциальной функции средствами СБИС ПЛ.

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

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

Научная новизна:

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

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

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

Практическая значимость:

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

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

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

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

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

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

• Явные аналитические выражения, полученные для каждой из рассмотренных в работе математических моделей нахождени�