Применение метода БВЕ для вычисления функции exp (x) на ПЛИС

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 021
ПРИМЕНЕНИЕ МЕТОДА БВЕ ДЛЯ ВЫЧИСЛЕНИЯ ФУНКЦИИ EXP (X) НА ПЛИС
Попов С. Д., Опадчий Ю. Ф.
ФГБОУ ВПО «МАТИ — Российский государственный технологический университет имени К.Э. Циолковского», Москва, e-mail: electron_inform@mail. ru
В данной статье рассмотрена модификация метода БВЕ для вычисления экспоненциальной функции применительно к ПЛИС. В целях повышения быстродействия и уменьшения себестоимости метод БВЕ комбинируется с таблицами заранее вычисленных значений. Также рассмотрен способ приведения произвольного аргумента, так как область определения метода БВЕ ограничена промежутком [0, 0,25). Оценки быстродействия и аппаратных затрат проведены с помощью САПР Quartus II фирмы Altera применительно к ПЛИС серии Stratix III. Проведено сравнение предложенного способа вычисления экспоненциальной функции и встроенной в САПР Quartus II мегафункцией altpf_exp, в результате чего показано, что предложенная комбинация табличного метода и метода БВЕ позволяет уменьшить как время вычисления, так и затраты аппаратных ресурсов ПЛИС на реализацию.
Ключевые слова: ПЛИС, алгоритм вычисления, экспоненциальная функция
APPLICATION OF THE FEE METHOD TO CALCULATE EXP (X) FUNCTION ON FPGA Popov S.D., Opadchiy Y.F.
«MATI» — Russian State University of Aviation Technology n.a. K.E. Tsiolkovsky, Moscow, e-mail: electron_inform@mail. ru.
In this article the modification of the FEE method is used to calculate the exponential function on FPGA. FEE method is combined with tables of pre-computed values in order to improve performance and reduce the cost of hardware resources. Also a method of bringing arbitrary argument is considered, as the domain of the FEE method is limited by the interval [0, 0. 25). Evaluation of performance and hardware costs carried by Altera Quartus II software, Altera Stratix III is used as a target FPGA. The proposed method for calculating the exponential function is compared with built into Quartus II software megafunction altpf_exp, whereby is shown that the proposed combination of table method and the FEE method reduces computation time as well as the cost of hardware resources of FPGA.
Keywords: FPGA, algorithm of calculation, exp (x) function
Разработка специализированных вычислителей на ПЛИС часто требует нахождения численного значения элементарных математических функций. Обычно для этого используются имеющиеся в стандартном пакете САПР мегафункции. Так, например, в САПР Quartus II фирмы «Альтера» [5], имеются мегафункции для вычисления основных математических функций, такие как altpf_exp, altpf_log. altpf_sincos. Эти мегафункции работают с данными, представленными согласно стандарту IEEE 754
в формате с плавающей точкой. Допускается использование вычислений с одинарной (1 бит знака, 8 бит — порядок, 23 бита — мантисса), двойной (1 бит знака, 11 бит — порядок, 52 бита — мантисса) и одинарной расширенной (1 бит знака, 31 — 52 мантисса) точностями.
Ниже приведена таблица, заимствованная из документации к САПР Quartus II, характеризующая аппаратные затраты и производительность мегафункции акр^ехр применительно к ПЛИС серии 8йайх III.
Параметры мегафункции altpf_exp
Таблица 1
Точность Задержка (такты) Логические элементы Макс. частота работы, мГц
Таблицы перекодировок (ALUTs) Спец. регистры (DLRs) Модули ALMs 18-битные DSP блоки
Одинарная 17 631 521 445 19 275
Двойная 25 4138 2022 2959 46 257
Согласно приведенным данным, время получения результата при одинарной точности составляет порядка 62 п8, а при двойной точности — порядка 98 п8.
На практике диапазон изменения аргумента заранее известен, и он, как правило,
значительно уже, чем допускает мегафункция. Поэтому практический интерес представляет поиск более гибких решений, обеспечивающих получение требуемой точности вычисления при меньших аппаратных затратах и большем быстродействии.
Нахождение численного значения элементарных функций всегда сводится к вычислению некоторого степенного многочлена. Широко известные методы вычисления многочлена, такие как метод Горнера [2], методы с предварительной обработкой коэффициентов [4], хотя и позволяют ускорить вычисление многочлена, но по своей структуре фактически нацелены на последовательное, итерационное вычисление, свойственное классическим вычислительным машинам.
Применение ПЛИС позволяет произвольно синтезировать структуру вычислителя, широко используя распараллеливание процесса, что предполагает значительное сокращение времени получения результата. Одним из методов, позволяющих реализовать такую возможность, является метод
БВЕ (Быстрое Вычисление Е-функций). Рассмотрим особенности применения этого метода на примере вычисления функции ехр (х).
Алгоритм, описанный в [1], предполагает, что диапазон изменения аргумента удовлетворяет условию 0 & lt- х0 & lt- 0,25 и число верных разрядов результата п & gt- 8. Расчетная разрядность аргумента для требуемого числа верных разрядов результата определяется выражением N = 2к+1, где
к=СЕ1^п/ш
Сгруппируем весовые коэффициенты расчетного аргумента
ХЫ ~ ®3 ' 2
+ (Х4 -2
+ ос5 ¦ 2
по степеням 2 2:
16, , п -«-ЛЬ
%-Зг'-2 + Рз'-2 +04'-2 + - + Р*+Г2
(1)
где
р2=сс3а4, Рз = а5ос6а7а8, Р4 — ®9(r)10®11®12®13®14®15®16'
Р5 — ОС17ОС18ОС19(Х2
.а.
5 17 18 19 20 • • • 32
и так далее. В общем случае есть некоторое целое двоичное число, полная запись которого определяется выражением:
/=о
ехР (РУ ' 2-Г) = 1 +
Используя выражение (1), функцию ехр (х^) можно представить в следующем виде
ехр (х^) = Пехр (р,-Г2').
Выражение (2) позволяет разбить вычислительный процесс определения численного значения функции ехр (х^) на несколько параллельно выполняемых ветвей.
Вычисление каждой ветви выполняется с использованием ее разложения в ряд Мак-лорена:
РУ-2- & amp- (РУ'2−203 (Ру ' 2−2)
1!
2!
3!
п
+ К (Г)& gt-
(3)
причем число членов каждого разложения определяется выражением:
г=Ы- 21_
(4)
Так, например, для вычисления функции с 12 верными разрядами имеем к = 4, N = 32,
^р^+рз^+р^+р^-32-
ехр (х^) = ехрф2 -24) — ехрфз • 2Г8) — ехр (р4 -2"16) — ехр (Р5 • 2"32),
причем число членов в соответствующих разложениях ряда Маклорена определяется из условия (4) следующим образом: г = 16 для ехр (Р22−4), г = 8 для ехр (Р32−8), г = 4 для ехр (Р4−2-16), г = 2 для ехр (Р52 32).
Из приведенного примера видно, что чем больше в (3) значение V, тем меньше членов в соответствующем разложении, то есть тем проще реализация вычислителя.
На рис. 1 приведен граф вычислительного процесса, соответствующий выражению (2) для 12 верных разрядов результата.
ехр (Р5 -2"32) = 1. 0а17а18а19а20а21а22а23а24а25а26а27а28а29аз0а31а32.
Модуль БЬ_Б2 реализует вычисление ехр (Р22−4), модуль БЬ_Б3 — вычисление ехр (Р32−8), модуль БЬ_Б4 — вычисление ехр (Р4−2-16), а модуль БЬ_Б5 — вычисление ехр (Р52−32). Очевидно, что длина графа для каждого модуля будет определяться значением г. Так, ехр (р5−2-32- ~ 1 + р5 -232,
не требует выполнения каких-либо вычислений и сводится к перезаписи соответствующих разрядов аргумента в результат:
Рис. 1. Граф вычислительного процесса, соответствующий выражению (2) для 12 верных разрядов результата
Модуль BL_B3 реализует вычисление согласно выражению:
Ґ. z
exp (?4−2-„)“?$-2
-16
10
+l + ?4 -2
где Р4 = 0. а9а10апа12а13а14а15а16 — число & lt-
Граф процесса, реализованный в данном модуле, показан на рис. 2. Его реализация требует только двух умножителей. Очевидно, что графы, реализованные в модулях ВЬ_В2 и ВЬ_В3, имеют значительно более сложную структуру.
Результаты моделирования проекта в среде Quartus II приведены на рис. 3. Минимальное число верных разрядов результата равно 33, что значительно превосходит исходные требования (12 разрядов). Следовательно, для заданной точности такое решение является избыточным. Аппаратные затраты на реализацию вычислителя сведены в табл. 2.
Анализ полученных результатов показал, что основные затраты аппаратных ресурсов расходуются для реализации модулей ВЬ_В3 и ВЬ_В2. При этом на входах данных модулей соответственно действуют 2 и 4-разрядные аргументы, то есть возможное число выходных значений соответственно равны 4 и 16. В этом случае целесообразно отказать-
1, и A = 1,5.
ся от применения в этих модулях разложения в ряд Маклорена в пользу табличного выбора заранее рассчитанных результатов соответствующих аргументов.
Результат
Рис. 2. Граф модуля BLB3
Nam 50 0 ns 90 0 ns 130(0ns 1700ns 210|0ге 2500 ns 2900 ns 3300 ns 370 0 ns 410−0 ns
50 0 ns J
а, А odoooooo x 1І10 001×2 ?808 000 X 3fFFft*F x bodootod
a REZ 4 000 000 0000b 446 5348C5DD2 Ш В 04АГ8 €Ё700 142 MB 0522D78F07B14 Ho
Рис. 3. Результаты моделирования проекта в среде Quartus II
Таблица 2
Аппаратные затраты на реализацию метода БВЕ
Модуль ALUTs блоки 18 бит DSP блоки
BL B5 0 0
BL B4 26 11
BL B3 72 26
BL B2 271 56
Общие для рис. 1 622 139
Реализация такого подхода в среде Quartus II потребовала 49 ALUTs и 17 DSP блоков. При этом в модулях BL_B2 и BL_ B3 использованы константы с 32 верными разрядами. Суммарное время вычисления не превосходит 30 nS. Минимальное число верных разрядов результата равно 31.
Следует отметить, что, так как константы в модулях BL_B2 и BL_B3 могут быть рассчитаны с произвольным числом верных разрядов, общая точность вычисления
определяется процессами в модулях БЬ_Б4 и БЬ_Б5.
Расчеты показывают, что предельная точность вычисления в модуле БЬ_Б5 по предложенному алгоритму соответствует максимальному значению аргумента и составляет 34 верных разряда результата. Предельная точность вычисления по алгоритму на рис. 2 для модуля БЬ_Б4 составляет
37 верных разрядов. Эти цифры являются определяющими при выборе разрядностей констант в модулях БЬ_Б2 и БЬ_Б3.
Как было отмечено ранее, рассмотренный алгоритм позволяет вычислить значение функции при условии, что аргумент лежит в диапазоне 0 & lt- х0 & lt- 0,25. При больших значениях аргумента результат может быть получен с использованием выражения:
ехр (хРАСЧЕТ + const) = ехр (хРАСЧЕТ) • exp (const),
где хР
'-& quot-РАСЧЕТ
расчетное значение аргумента из диапазона 0 & lt- х0 & lt- 0,25- ехр (соп81) — заранее вычисленная константа.
Это потребует использования дополнительного умножителя и блока памяти с вычисленными значениями ехр (соп81:).
Наиболее просто решить задачу расширения диапазона изменения аргумента при реализации на ПЛИС можно в случае, если изменение аргумента лежит в диапазоне 0 & lt- х & lt- 1п (2) [3]. В этом случае результат при более широком диапазоне изменения аргумента сдвигается влево на величину 5, равную неполному частному от деления действительного аргумента на 1п (2):
5= FLOOR
При таком подходе реализация выражения (5) потребует введения в устройство блока вычисления 5, а сама функция ищется от нового аргумента хрАС, равного:
(5)
ХРАС — Х
= U „. -FLOOR 1п (2)
М2)
ты, удовлетворяющие условию 0 & lt- x & lt- ln (2), что легко обеспечить на практике.
Полученный результат при помощи сдвигового регистра может быть сдвинут на 8 разрядов влево, либо представлен в показательной форме в виде порядка и мантиссы. При этом порядок — целое число, а мантисса всегда содержит один разряд целой части. Очевидно, что такой подход вносит в расчет дополнительную погрешность, обусловленную приближенностью значения
/*111(2). Для ее уменьшения желательно
число верных разрядов констант выбирать большим числа верных разрядов аргумента, как минимум на один.
На рис. 4 приведена заимствованная из [3] структура блока подготовки данных, выделяющая из исходного аргумента порядок и новое расчетное значение аргумента, удовлетворяющее условию 0 & lt- х & lt- 1п (2). Ее реализация требует двух умножителей.
Для использования такого подхода модуль БЬ_Б2 должен содержать все констан-
Рис. 4. Структура блока подготовки данных.
С использованием описанного подхода был разработан вычислитель для функции exp (x), формирующий на выходе порядок и мантиссу. Его основные параметры:
— исходный аргумент 4 разряда целой части + 33 разряда дробной части-
— разрядность порядка — 5 разрядов-
— разрядность мантиссы — 1 разряд целой части + 34 разряда дробной части-
— аппаратные затраты — 117 блоков
ALUTs и 29 DSP блоков-
— максимальное время вычисления на ПЛИС Stratix III не превосходит 45 nS-
— минимальное число верных разрядов на выходе — 30 разрядов.
На рис. 5 приведены временные диаграммы, полученные в результате моделирования вычислителя в среде Quartus II фирмы Altera (A — аргумент, man — мантисса, por — порядок).
Name Value at 2“ 15ns 1 62 us 1. 7us 178 us 186us 194us 2 02 us 2.1 us 2. 18us 226us

0 А И man El _рог НОООО Н 4000 ноо 160(1 000 000 X 1 768 000 000 X 18CC000000 X 1A38000000 X 1B98UOOOOO X 1DOOOOOOOO X 1E66000000 XX»
1Ж 74F112224 IB 761D45DOO Ш 765ED1275 Ш 787E8CDAE ¦ 770 108 146 Hi 79O49D0CD 11 79C1495F6
№ * 10. * 1* * 4 *. 13. Ж Ц. * 15 '- X
Рис. 5. Временные диаграммы, полученные в результате моделирования вычислителя
Из проведенных исследований следует вывод, что комбинация табличного и БВЕ методов делает возможным разработать вычислитель для функции exp (x), который при ограниченном диапазоне изменения аргумента позволяет реализовать устройство с меньшими аппаратными затратами и большим быстродействием. При увеличении точности вычисления достоинства предлагаемого метода становятся более ощутимыми.
Список литературы
1. Карацуба Е. А. Быстрые алгоритмы и метод БВЕ. URL: http: //www. ccas. ru/personal/karatsuba/alg. htm (дата обращения: 19. 04. 2012).
2. Люстерик Л. А., Червоненкис О. А., Янпольский А. Р Математический анализ. Вычисление элементарных функций. — М.: Физматгиз, 1963. — 248 с.
3. Мо Чжо Чо, Опадчий Ю. Ф. Алгоритм вычисления показательной функции на ПЛИС // Новые материалы и технологии: сборник трудов Всероссийской научно-технической конференции (Москва, 11−13 ноября 2008 г.). — М., 2008. — Т. 3. — С. 113−115.
4. Пан В. Я. О способах вычисления значений многочленов // Успехи математических наук. — 1966. — Т. 21. -№ 1. — С. 103−134.
5. Стешенко В. Б. ПЛИС фирмы Altera. Проектирование устройств обработки сигналов. — М.: Додека-XXI, 2000. -128 с.
References
1. Karacuba E.A. Bystrye algoritmy i metod BVE. Available at: http: //www. ccas. ru/personal/karatsuba/alg. htm (accessed 19 April 2012).
2. Ljusterik L.A., Chervonenkis O.A., Janpolskij A.R. Matematicheskij Analiz. Vychislenie Jelementarnyh Funkcij. Fizmatgiz, Moscow, 1963, 248 p.
3. Mo Chzho Cho, Opadchij Yu.F. Algoritm Vychislenija Pokazatelnoj Funkcii na PLIS // Sbornik Trudov Vserossijskoj Nauchno-Tehnicheskoj Konferencii «Novye Materialy i Teh-nologii» (Moscow, 11−13 November 2008). Moscow, 2008, vol. 3, pp. 113−115.
4. Pan V. Ja. O Sposobah Vychislenija Znachenij Mnogochlenov. // Uspehi Matematicheskih Nauk, 1966, vol. 21, no. 1, pp. 103−134.
5. Steshenko V.B. PLIS firmy Altera. Proektirovanie ustro-jstv obrabotki signalov. M.: Dodeka-XXI, 2000, 128 p.
Рецензенты:
Волков Н. Н., д.т.н., профессор Московского государственного технического университета им. Н. Э. Баумана (МГТУ им. Н.Э. Баумана), кафедра «Информационные системы и телекоммуникации», г. Москва-
Шевцов Д. А., д.т.н., профессор Московского авиационного института (Национального исследовательского университета), кафедры № 306 «Микроэлектронные электросистемы», г. Москва.
Работа поступила в редакцию 18. 09. 2013.

ПоказатьСвернуть
Заполнить форму текущей работой