Диссертация (1150736), страница 2
Текст из файла (страница 2)
. . . . . . . . . . . 200D Реализация специальных видов БПФ . . . . . . . . . . . . . . . . . 203D.1 Комплексный алгоритм Radix-2 . . . . . . . . . . . . . . . . . . . 204D.2 Комплексный алгоритм Split-Radix в частотной области . . . . . 206D.3 Вещественный алгоритм Radix-2 во временной области . . . . . 207D.4 Вещественный алгоритм Split-Radix в частотной области . . .
. 207D.5 Двойная вещественная интерполяция . . . . . . . . . . . . . . . 2086ВведениеЭнергоэффективность является одной из основных характеристик полупроводниковых беспроводных устройств, поскольку она определяет время работы устройства от батареи и его тепловой режим. Время работы от батареии рабочая температура определяют сценарии работы устройства и, зачастую,его общую применимость.В современных беспроводных малопотребляющих устройствах наблюдается увеличение требований к вычислительной мощности при сохранении высокой автономности и компактности.
Это обусловлено изменением способаиспользования устройства в сторону постоянного интерактивного взаимодействия с окружением и информационной средой. В устройствах появляетсяподдержка низкоэнергетических беспроводных протоколов передачи данныхс высокой пропускной способностью, таких, как ZigBee,WiFi, Bluetooth. Кроме того, становится востребованной непрерывная обработка аудио- и видеоданных, необходимая для реализации дополненной реальности и голосовогоуправления устройством в режиме “свободные руки”. В связи с этим возникают новые требования к энергоэффективности устройств, поскольку трактпредварительной обработки данных c сенсоров и беспроводное соединениедолжны быть постоянно активны.Предварительная обработка может включать такие компоненты, как адаптивное формирование луча в микрофонной решетке, адаптивное шумоподавление, адаптивное подавление дальнего и ближнего эха, обнаружение голоса,распознавание ключевых слов и ключевых событий с других сенсоров, упаковка сигнала для передачи по беспроводной сети на последующую обработку в облако, выделение признаков (коэффициентов кепстра, коэффициентовлинейного предсказания, дескрипторов особенностей для видеоизображенийи т.п.), идентификация диктора по голосу и распознавание базовых команд7управления устройством, идентификация отпечатков пальцев и других биометрических признаков пользователя.Последующая обработка данных может включать такие вычислительносложные алгоритмы, как распознавание речи, распознавание объектов и семантический анализ с учетом контекста (предыдущие действия пользователя,географическое положение, аудиовизуальная информация, другие данные сенсоров).
Однако эти алгоритмы начинают работать только после обнаруженияречи или объекта интереса и аутентификации пользователя на этапе предварительной обработки. В текущем поколении устройств они реализованы воблаке. Поэтому их вклад в энергопотребление устройства на текущем этаперазвития техники относительно невелик. Однако есть запрос на перенос этихалгоритмов на устройство без уменьшения времени автономной работы с целью уменьшения зависимости от подключения к беспроводной сети передачиданных и увеличения приватности пользователя.
Это приводит к необходимости оптимизации алгоритмов и их аппаратной реализации по энергопотреблению.Стандартные модели энергопотребления полупроводниковых схем учитывают только активную мощность, затрачиваемую на переключение логическихэлементов. Таким образом, оценка для затрат энергии алгоритмом пропорциональна его сложности в элементарных операциях, и задача оптимизации энергопотребления не имеет самостоятельного смысла.Такие модели соответствуют практике для схем с литографическими нормами более 45 нм. Для более мелких литографических норм на первый планвыходят потери энергии в результате токов утечки, которые пропорциональныплощади схемы, подключенной к питанию, и не зависят от вычислительнойсложности алгоритма. Площадь схемы складывается из размера памяти и количества параллельных вычислительных элементов.
Таким образом, требуется более сложная модель оценки расхода энергии, учитывающая параллелизмвычислений и размер используемой памяти. Вопрос оптимального выбора параллелизма для минимизации энергопотребления при моделировании ускорения с помощью закона Амдала рассматривался Ву и Ли [Woo, 2008] для многоядерных суперскалярных процессоров. В отличие от рассматриваемой нами8задачи, процессоры работают на высокой частоте и при высоком напряжениипитания, что позволяет не учитывать энергопотребление памяти.В первой главе описывается новая модель энергопотребления и исследуется оптимизация ее параметров.
Также в главе рассматривается влияние наэнергопотребление других факторов, таких как архитектура памяти, представление числовых данных, архитектура процессора и операционной системы,использование языков управляемого выполнения (Java, C# и т.п.), моделей параллельных вычислений и средств автоматической верификации.В качестве сквозного примера, имеющего практическую значимость и демонстрирующего предложенный подход к оптимизации энергоэффективности,была рассмотрена задача адаптивного эхоподавления дальнего эха в системах конференцсвязи с помощью линейной фильтрации с длинной импульснойхарактеристикой.
Для решения задачи используется сверхбыстрый алгоритмШура для факторизации тёплицевых матриц, основанный на БПФ.Базовыми алгоритмическими блоками для алгоритмов цифровой обработки сигналов являются сумматоры, умножители и запоминающие устройства.Далее в иерархии сложности можно расположить процедуры вычисления√элементарных функций, таких как ln, exp, sin, cos, , 1/. Эти функции частовстречаются в алгоритмах цифровой обработки сигналов, и энергоэффективность и скорость их вычисления могут существенно влиять на энергоэффективность устройства в целом. Для вычисления могут использоваться итерационные методы, табулирование, аппроксимация функций при помощи многочленов или их комбинации.
Сплайны различного вида можно рассматривать как комбинацию табулирования и полиномиальной аппроксимации. Возможно вычисление различными методами с использованием инструкций программируемого процессора. Оно не является наиболее энергоэффективнымметодом для специализированной аппаратуры и может применяться тольков случае однократных вычислений, существенно не влияющих на сложностьалгоритма.
Наиболее медленным методом вычислений в аппаратуре является алгоритм CORDIC [1], вычисляющий один бит значения за такт с помощью операций суммирования и сдвига. Следующая группа методов основана на двудольных таблицах [2] и вычисляет сразу группу битов за такт. Также как и в CORDIC используются только операции суммирования и сдвига.9При этом размер таблиц быстро растет с увеличением требуемой точности.Для вычислений с более высокой точностью обычно используется кусочнополиномиальная аппроксимация.
Проблемой аппаратной реализации методакусочно-полиномиальной аппроксимации является оптимальный баланс между точностью, размером таблиц и степенью многочлена, определяющей энергозатраты на вычисления. Для элементарных функций таблицы являются избыточными и могут быть существенно сокращены используя гладкость функций. В работе Стролло [3] предложен метод сокращения таблиц на 40% безсущественного увеличения вычислений за счет использования двузвенногогладкого сплайна, однако вопрос точности решается эмпирическим путем, припомощи тестирования на всех допустимых данных, что делает метод в описанном виде неприменимым для высоких точностей.В главе 2 описаны способы сокращения таблиц, необходимых для расчета элементарных функций с заданной точностью, существенно улучшающиерезультат Стролло.Из более сложных базовых алгоритмов обработки сигналов наиболее частоиспользуется Быстрое Преобразование Фурье.
Под БПФ понимается группаалгоритмов для вычисления дискретного преобразования Фурье с вычислительной сложностью ( ln ), где - длина БПФ. Основные исследования вобласти оптимизации БПФ идут в направлениях минимизации общего числаопераций, оптимизации для выполнения на процессорах с поддержкой векторных операций общего назначения и оптимизации для специализированныхполупроводниковых схем. Наиболее быстрым по количеству операций на сегодня является алгоритм Джонсона [4], основанный на split-radix алгоритме.Для коротких БПФ часто применяется нерекурсивный алгоритм Соренсенатого же типа [5].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
