Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,737

ВЫЧИСЛЕНИЕ ПОКАЗАТЕЛЬНОЙ ФУНКЦИИ НА ПЛИС

Попов С.Д. 1 Опадчий Ю.Ф. 1
1 Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «МАТИ – Российский государственный технологический университет имени К. Э. Циолковского»
В данной работе рассматривается оптимизация табличного метода для вычисления значения показательной функции. Главный недостаток табличного метода заключается в том, что на практике объем информации, который необходимо хранить в таблице, оказывается чрезмерно большим, что влечет высокие аппаратные затраты. Предложен способ разбиения двоичного представления аргумента, позволяющий свести задачу к чтениям из нескольких маленьких таблиц, содержащих по 4 строки. Предложенный метод подробно рассмотрен на примере вычисления значения экспоненциальной функции. На примере ПЛИС серии Stratix III фирмы Альтера проведено сравнение предложенного метода и алгоритма, встроенного в САПР Quartus II фирмы Альтера. При ограниченном диапазоне изменения аргумента рассмотренный алгоритм обладает явным преимуществом как по затратам аппаратных ресурсов ПЛИС, так и по быстродействию.
табличный метод
показательная функция
алгоритм вычисления
ПЛИС
1. Демидович Б. П., Марон И. А. Основы вычислительной математики. – Изд-во «Наука», Москва, 1966. – 664 с.
2. Люстерик Л. А., Червоненкис О. А., Янпольский А. Р. Математический анализ. Вычисление элементарных функций. М.: Физматгиз, 1963. – 248 с.
3. Опадчий Ю. Ф., Чумакова Е. В. Реализация на ПЛИС вычисления элементарных математических функций // Проектирование и технология электронных средств. – Владимир. – 2005. – № 4. – С. 7–12.
4. Пан В. Я. О способах вычисления значений многочленов // Успехи математических наук. – 1966. – Т. 21. – № 1. – С. 103–134.
5. Стешенко В. Б. ПЛИС фирмы Altera. Проектирование устройств обработки сигналов. – М.: Додека-XXI, 2000. – 128 с.

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

Последний из перечисленных табличный метод является наиболее универсальным, однако при повышении точности вычисления он требует значительных аппаратных ресурсов, используемых для хранения исходных таблиц. Так при абсолютной погрешности вычисления функции в диапазоне порядка 2.3Е-10, что соответствует 32 точным разрядам результата, требуется хранить не менее табличных значений функции. Этот недостаток может быть частично компенсирован за счет использования дополнительной обработки табличных данных, например, методом линейной интерполяции [3]. Однако и в этом случае сохраняется необходимость в хранении значительных объемов информации.

Используя одно из основных свойств показательной функции, а именно – соотношение:

, (1)

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

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

Представим аргумент в виде:

,

где ; , и т.д. – соответствующие разряды ; – целые числа, составленные из соответствующих разрядов .

Тогда, используя (1), для рассматриваемой функции можно записать:

.

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

На рис. 1 приведен соответствующий данному случаю граф алгоритма вычисления.

Рис. 1. Алгоритм вычисления при разрядности аргумента – 16 бит

Реализация данного алгоритма требует 3-х ярусов умножения, то есть суммарное время вычисления будет равно:

, (2)

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

Анализируя граф на рис. 1, нетрудно получить общую формулу для вычисления значения :

, (3)

где – число разрядов аргумента .

Для определения разрядности табличных значений функции воспользуемся известным правилом, согласно которому при перемножении двух приближенных чисел их относительные погрешности складываются. Тогда, используя полученную, согласно [1], связь между относительной ошибкой и числом верных разрядов приближенного числа (, где – число разрядов дробной части числа), для числа верных разрядов произведения двух чисел можно записать:

,

где и – минимальная разрядность дробной части и разность разрядностей сомножителей соответственно.

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

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

На рис. 2 приведены временные диаграммы моделирования рассмотренного алгоритма в среде САПР Quartus II фирмы Альтера [5], а в таблице – расшифровка полученных результатов.

Рис. 2. Временные диаграммы моделирования рассмотренного алгоритма

Таблица. Результаты тестирования проекта

Аргумент

Результат вычисления

Абсолютная ошибка

Число верных разрядов

H”0CCC”

H”868FA17AB”

5.69E-11

35

H”2666”

H”94B6C0896”

1.04E-10

34

H” 4083”

H”A4AF21F41”

6.01E-11

34

H”5A1C”

H” B6009EE90”

1.1E-10

34

H”73B6”

H” C9251FACB”

1.59E-10

33

H”8D4F”

H” DE4C2E8B7”

1.27E-10

33

H”B172”

H” FFFFE807D”

1.73E-10

33

При реализации проекта на ПЛИС серии Stratix III потребовалось 27 комбинационных таблиц (ALUTs) и 28 18-битных DSP блоков. Максимальное время вычисления не превосходит 27 nS. Анализ результатов тестирования показал, что во всем диапазоне изменения аргументов получено не менее 33 верных разрядов результата, что подтверждает правильность выбора точности табличных значений функции.

Следует отметить, что увеличение разрядности аргумента, согласно выражениям (2) и (3), не сильно скажется на времени вычисления. Так, при разрядности аргумента не более 32 в графе на рис. 1 появится еще только один дополнительный ярус умножения, то есть время вычисления увеличится на время . Значительно изменится ширина графа, то есть количество одновременно выполняемых операций.

Согласно данным из User Guide для мегафункции altpf_exp фирмы Альтера, вычисление функции при числе верных разрядов результата 23 требует: комбинационных блоков (ALUTs) – 631 шт, специализированных регистров (DLRs) – 521 шт, модулей ALMs – 445 шт, 18-ти разрядных DSP блоков – 19 шт. Общее время вычисления для ПЛИС той же серии составляет 62 nS. Следует отметить, что мегафункция altpf_exp работает с данными, представленными, согласно стандартам IEEE 754, что делает ее более универсальной. Однако при ограниченном диапазоне изменения аргумента рассмотренный алгоритм обладает явным преимуществом как по затратам аппаратных ресурсов ПЛИС, так и по быстродействию.

Рецензенты:

Волков Н.Н., д.т.н., профессор Московского государственного технического университета им. Н. Э. Баумана (МГТУ им. Н. Э. Баумана), кафедра «Информационные системы и телекоммуникации», г.Москва.

Шевцов Д.А., д.т.н., профессор Московского авиационного института (национального исследовательского университета), кафедра № 306 «Микроэлектронные электросистемы», г.Москва.


Библиографическая ссылка

Попов С.Д., Опадчий Ю.Ф. ВЫЧИСЛЕНИЕ ПОКАЗАТЕЛЬНОЙ ФУНКЦИИ НА ПЛИС // Современные проблемы науки и образования. – 2013. – № 5.;
URL: http://science-education.ru/ru/article/view?id=10145 (дата обращения: 21.08.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252