Диссертация (1150736), страница 3
Текст из файла (страница 3)
Основным отличием между параллельными специализированными схемами и процессорами общего применения является дисциплинаобращения к памяти. Алгоритмы для процессоров подразумевают произвольный доступ как к памяти данных, так и к памяти кода, для реализации которого требуются сложные и энергозатратные аппаратные механизмы, в то времякак алгоритмы для специализированных схем используют память специальной структуры, оптимизированную по энергопотреблению и площади и фиксированный вычислительный блок для вычисления бабочек. Таким образом,10при требовании параллелизма специализированные схемы оказываются более энергоэффективными, поскольку не требуют специальных модификацийаппаратуры для обеспечения произвольного доступа к памяти и выборки кода программы для вычислений и адресации памяти.
Существующие алгоритмы реализации БПФ на специализированной аппаратуре можно разделить поасимптотике времени вычислений (1), (ln ), (), ( ln ). Выбор алгоритма зависит от способа применения блока вычисления БПФ. При дополнительном условии переиспользования ресурсов и управляемой длины преобразования, которые часто встречаются в реальных задачах с длинными БПФ,более эффективными оказываются алгоритмы с временем работы ( ln ) ипамятью с произвольным доступом, поскольку они обеспечивают гибкость подлине БПФ и используют библиотечную память.
К таким алгоритмам относится поточный БПФ Джонсона [6]. При повышении параллелизма БПФ засчет увеличения основания более 2, алгоритмы БПФ по чистому основаниютеряют эффективность, и требуется производить вычисления по смешанномуоснованию.Алгоритм Джонсона применим только для чистых оснований или, снебольшими модификациями, для смешанного основания без параллелизмабабочек. Модификация алгоритма Джонсона, предложенная Джо и Санву [7]специализирована для оснований 2/4.
Применение для других смешанных оснований требует модификации алгоритма.Во многих задачах более эффективными являются самосортирующие алгоритмы БПФ к таким алгоритмам относятся реализации Джонсона-Буруса иТемплтона [8]. Алгоритм Джонсона-Буруса сформулирован для однобанковойпамяти с произвольным доступом, его применение с другим типом памятитребует адаптации. Алгоритм Темплтона является строго последовательным исформулирован для скалярных процессоров.Также требуется алгоритмическая адаптация под наиболее эффективнуюархитектуру памяти, предоставляемую библиотекой компонентов, например,однопортовую память.
Такие адаптации для алгоритмов БПФ без копированияпока не рассматривались в литературе.Разработка потоковых алгоритмов БПФ с ограничением на доступ к памяти по существу является задачей составления расписания для синхронного11графа потока данных. Результаты расчета каждой бабочки записываются на теже места, с которых считывались для нее входные данные. В многобанковойпамяти все крылья каждой бабочки должны оказаться в разных банках, иначевозникает конфликт. При этом общее количество ячеек памяти минимально равно длине БПФ. Комбинаторные задачи нахождения начальных распределений, гарантирующие отсутствие конфликтов для стадий БПФ с произвольными основаниями, составляют основное содержание главы 3.Другим часто используемым классом алгоритмов в цифровой обработкесигналов является факторизация тёплицевых и обратных к тёплицевымматриц.
Необходимость в этом возникает при решении уравнений Юла-Уокерапри построении оптимальных неупреждающих линейных фильтров. Задачиэтого типа и большой размерности часто возникают в акустических задачахэхо- и шумоподавления и разделения источников сигнала. Это связано с малой скоростью распространения звука и реверберацией.
Для решения задачи факторизации обычно используются алгоритмы Левинсона и Шура, имеющие асимптотику сложности (2 ), где - длина вектора автокорреляций. Длязадач большой размерности могут использоваться быстрый алгоритм Шура,предложенный Аммаром и Греггом [9] и Воеводиным и Тыртышниковым [10]со сложностью ( ln2 ), или предобусловленный метод сопряженных градиентов со сложностью итерации ( ln ).
Оба алгоритма основаны на использовании БПФ и могут использоваться как пример энергоэффективной реализации сложных алгоритмов с БПФ.Быстрый алгоритм Шура описан в ряде статей и имеет вид длинной совокупности алгебраических инструкций, содержащих свертки матричных многочленов и рекуррентные вызовы функций. Было подсчитано количество сложений и умножений, а также требуемая память.В данной работе было исследовано влияние параллелизма на сложностьреализации алгоритма, выраженную в энергозатратах, описанных в главе 1.Для этого потребовалось представить алгоритм в виде способа обхода нагруженного графа.
В главе 4 на основе исследования данного графа улучшено значение требуемой памяти, а также вычислена длина критического путиотносительно операций чтения и записи. Далее найден оптимальный коэф-12фициент параллелизма для быстрого алгоритма Шура на 4096 отсчетов привыполнении на поточном акселераторе БПФ, который оказался равным = 4.Целью данной работы является разработка алгоритмов для минимизациисложности расчетов, характерных для статистической обработки сигналов.Сложность измеряется энергоэффективностью, которая моделируется в главе 1. Она зависит, в частности, от длины таблиц при расчете стандартныхэлементарных функций, от доступа к памяти в реализации БПФ, от самосортировки БПФ, от параллелизма в быстром алгоритме обращения тёплицевыхматриц.Для достижения поставленной цели необходимо было решить следующиезадачи:1.
Сформулировать функционал сложности и другие требования, предъявляемые к алгоритмам для их эффективной реализации в аппаратуре;2. Разработать эффективные целочисленные алгоритмы вычисления элементарных функций с заданной точностью и минимальной длиной таблицы;3. Разработать расписание для реализации графа потока данных для БПФна многобанковой памяти;4. Исследовать параллелизм быстрого алгоритма Шура.Основные положения, выносимые на защиту:1.
Метод качественной оценки мощности и выбора оптимального параллелизма для энергоэффективных специализированных КМОП вычислительных блоков.2. Метод вычисления элементарных функций при помощи почти гладкогочетырехзвенного квазисплайна и оценка точности полиномиальной аппроксимации с коэффициентами с фиксированной точкой, ограниченнойна равномерной сетке.3. Теорема о размещении данных БПФ в многобанковой памяти при вычислении по произвольным смешанным основаниям.134. Теорема о размещении данных и порядке вычисления самосортирующегося БПФ.5.
Теорема о размещении данных и порядке вычисления БПФ для однопортовой памяти.6. Анализ энергоэффективности алгоритма факторизации вещественных тёплицевых матриц на сверточном акселераторе для задачи эхокомпенсации при помощи быстрого алгоритма Шура.Научная новизна:1. Разработана модель энергопотребления для малопотребляющей цифровой схемы, выполняющей известный вычислительный алгоритм. Модельвключает динамические и статические потери энергии и возможностьотключения во время простоя.
Решена задача выбора оптимального параллелизма в данной модели.2. Задача минимизации энергопотребления при расчёте значений стандартных функций сведена к минимизации длины таблиц. Разработаны новые методы аппроксимации квазисплайнами с неравномерным табулированием, удобные для аппаратной реализации, при помощи которыхудалось сократить длины таблиц всех основных стандартных функцийпо сравнению с известными аналогами, что привело к существенномууменьшению энергопотребеления и увеличению скорости аппаратныхвычислительных блоков.3. Доказана теорема о размещении данных БПФ в многобанковой памятипри вычислении по произвольным смешанным основаниям, гарантирующая гомогенность графа синхронного потока данных для вычислений,что обеспечивает максимальную скорость вычислений при заданном параллелизме и нулевой размер буферной памяти.
Получены явные формулы БПФ в виде произведений Кронекера по стадиям произвольныхпорядков.144. Доказана теорема о самосортирующейся модификации БПФ в многобанковой памяти по смешанным основаниям, а также аналогичная теоремадля вычислительного устройства с однопортовой памятью.5. Для быстрого алгоритма Шура найден минимальный объём памяти, вычислена длина критического пути и проведена оценка оптимального параллелизма.Практическая значимость диссертационной работы обеспечивается сокращением площади и энергопотребления рассмотренных элементов и повышением их универсальности, что вносит существенный вклад в улучшениеэнергоэффективности автономных беспроводных устройств, реализуемых набазе специализированных полупроводниковых логических схем.Достоверность изложенных в работе результатов обеспечивается практической реализацией предложенных схем и алгоритмов в виде полупроводниковых схем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
