Автореферат (Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти)

На правах рукописиСалищев Сергей ИгоревичСИНТЕЗ АЛГОРИТМОВ ОБРАБОТКИ СИГНАЛОВС ОГРАНИЧЕНИЯМИ НА МИНИМАЛЬНЫЙ ПАРАЛЛЕЛИЗМИ ОБЪЁМ ПАМЯТИ01.01.09 — дискретная математикаи математическая кибернетикаАВТОРЕФЕРАТдиссертации на соискание учёной степеникандидата физико-математических наукСанкт-Петербург2016Работа выполнена в Санкт-Петербургском государственном университетеНаучный руководитель:доктор физико-математических наук,БАРАБАНОВ Андрей ЕвгеньевияОфициальные оппоненты: КОЛЕСОВ Николай Викторовичдоктор технических наук, профессор,ГНЦ РФ АО «Концерн «ЦНИИ «Электроприбор»,главный научный сотрудникЛОБАНОВ Игорь Сергеевичкандидат физико-математических наук,Санкт-Петербургский национальныйисследовательский университет информационныхтехнологий, механики и оптики, доцентВедущая организация:Федеральное государственное автономноеобразовательное учреждение высшего образования«Санкт-Петербургский государственныйэлектротехнический университет «ЛЭТИ»им.

В. И. Ульянова (Ленина)»Защита состоится 01 марта 2017 г. в 16 часов на заседании диссертационного совета Д 212.232.29 на базе Санкт-Петербургского государственногоуниверситета по адресу: 199178, Санкт-Петербург, 10 линия В.О., д. 33/35,ауд. 74.С диссертацией можно ознакомиться в Научной библиотеке им. М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9 и на сайтеhttps://disser.spbu.ru/files/disser2/disser/4Ph9sRhxtR.pdfАвтореферат разослан "____"____________2016 года.Ученый секретарьдиссертационного совета Д 212.232.29доктор физико-математических наук,профессорНежинский В.М.Общая характеристика работыАктуальность темы. Энергоэффективность - одна из основных характеристик полупроводниковых беспроводных устройств, определяющая времяработы устройства от батареи и его тепловой режим. Стандартные моделиэнергопотребления учитывают только активную мощность, в которой оценказатрат энергии пропорциональна сложности в элементарных операциях.

Длясхем с литографическими нормами 45 нм и менее на первый план выходятпотери энергии в результате токов утечки, которые не зависят от вычислительной сложности. Они складываются из размера памяти и количества параллельных вычислительных элементов. Оптимальный параллелизм для минимизации энергопотребления рассматривался Ву и Ли [Woo, 2008] для многоядерных суперскалярных процессоров.

В отличие от рассматриваемой намизадачи, процессоры работают на высокой частоте и при высоком напряжениипитания, что позволяет не учитывать энергопотребление памяти. Одним избазовых блоков для алгоритмов цифровой обработки сигналов является вы√числение элементарных функций ln, exp, sin, cos, , 1/ и т.п.

Для аппаратных блоков вычислений с точностью 22 бита и выше обычно используетсякусочно-полиномиальная аппроксимация. Проблемой энергоэффективной аппаратной реализации метода является оптимальный баланс между размеромтаблиц и степенью многочлена. Для элементарных функций таблицы являются избыточными и могут быть сокращены, используя гладкость функций.В работе [Strollo, 2011] предложен метод сокращения таблиц на 40% безсущественного увеличения вычислений за счет использования двузвенногогладкого сплайна, однако вопрос точности решается эмпирически, при помощи тестирования на всех допустимых данных, что делает метод в описанномвиде неприменимым для высоких точностей.

Из более сложных алгоритмовнаиболее часто используется Быстрое Преобразование Фурье. Существующие алгоритмы БПФ на специализированной аппаратуре можно разделитьпо асимптотике времени вычислений (1), (ln ), (), ( ln ). Притребовании переиспользования ресурсов и программно управляемой длиныпреобразования часто наиболее энергоэффективными оказываются аппаратные блоки БПФ с временем работы ( ln ) и памятью с произвольнымдоступом. К таким алгоритмам относится поточное БПФ [Johnson, 1992],которое может быть реализовано на реконфигурируемом вычислительномустройстве антимашине Хартенштейна [Hartenstein, 1991] Разработка поточных алгоритмов БПФ с ограничением на доступ к памяти может бытьсведена к задаче составления расписания для синхронного графа потока данных [Parhi, Messerschmitt, 1991]. Алгоритм Джонсона применим только для3чистых оснований и для смешанного основания без параллелизма бабочек.Модификация алгоритма Джонсона, предложенная [Jo, Sunwoo, 2005], специализирована только для оснований 2/4.

Во многих задачах более эффективными являются самосортирующие алгоритмы БПФ, такие, как алгоритмДжонсона-Буруса и Темплтона [Hegland, 1994], которые сформулированытолько для однобанковой памяти. Также требуется модификация под наиболее эффективную архитектуру памяти, предоставляемую библиотекой компонентов, например, однопортовую память. Такие адаптации для алгоритмовБПФ без копирования пока не рассматривались в литературе. Другим частоиспользуемым классом алгоритмов является факторизация тёплицевых иобратных к тёплицевым матриц. Задачи этого типа и большой размерностивозникают в акустических задачах эхо- и шумоподавления и разделения источников сигнала. Для решения задачи факторизации обычно используютсяалгоритмы Левинсона и Шура, имеющие асимптотику сложности (2 ), где- длина вектора автокорреляций.

Для задач большой размерности может использоваться быстрый алгоритм Шура, предложенный [Ammar, Gragg, 1987;Воеводин, Тыртышников, 1987] со сложностью ( ln2 ), который рассматривается как пример энергоэффективной реализации сложных алгоритмов сБПФ.Целью данной работы является разработка алгоритмов для минимизации сложности расчетов, характерных для статистической обработки сигналов. Сложность измеряется энергоэффективностью.

Она зависит, в частности, от длины таблиц при расчете стандартных элементарных функций, отдоступа к памяти в реализации БПФ, от самосортировки БПФ, от параллелизма в быстром алгоритме обращения тёплицевых матриц.Для достижения поставленной цели необходимо было решить следующие задачи:1. Сформулировать функционал сложности и другие требования, предъявляемые к алгоритмам для их эффективной реализации в аппаратуре;2. Разработать эффективные целочисленные алгоритмы вычисления элементарных функций с заданной точностью и минимальной длиной таблицы;3. Разработать расписание для реализации графа потока данных для БПФна многобанковой памяти;4.

Исследовать оптимальный параллелелизм и размер памяти быстрого алгоритма Шура.Основные положения, выносимые на защиту:41. Метод качественной оценки мощности и выбора оптимального параллелизма для энергоэффективных специализированных КМОП вычислительных блоков (Лемма 1, Лемма 2).2. Метод вычисления элементарных функций при помощи почти гладкогочетырехзвенного квазисплайна и оценка точности полиномиальной аппроксимации с коэффициентами с фиксированной точкой, ограниченнойна равномерной сетке (Теорема 1).3.

Теорема о размещении данных БПФ в многобанковой памяти при вычислении по произвольным смешанным основаниям (Теорема 2).4. Теорема о размещении данных и порядке вычисления самосортирующегося БПФ (Теорема 4).5. Теорема о размещении данных и порядке вычисления БПФ для однопортовой памяти (Теорема 3).6. Анализ энергоэффективности алгоритма факторизации вещественных тёплицевых матриц на сверточном акселераторе для задачи эхокомпенсации при помощи быстрого алгоритма Шура (Лемма 3, Лемма 4,Лемма 5, Лемма 6).Научная новизна: Все представленные результаты являются новыми.1. Разработана модель энергопотребления для малопотребляющей цифровой схемы, выполняющей известный вычислительный алгоритм.

Решеназадача выбора оптимального параллелизма в данной модели.2. Задача минимизации энергопотребления при расчёте значений стандартных функций сведена к минимизации длины таблиц. Разработаны новыеметоды аппроксимации квазисплайнами с неравномерным табулированием, удобные для аппаратной реализации.3. Доказана теорема о размещении данных БПФ в многобанковой памятипри вычислении по произвольным смешанным основаниям, что обеспечивющая максимальную скорость вычислений при заданном параллелизме. Получены явные формулы БПФ в виде произведений Кронекера постадиям произвольных порядков.4.

Доказана теорема о самосортирующейся модификации БПФ в многобанковой памяти по смешанным основаниям, а также аналогичная теоремадля вычислительного устройства с однопортовой памятью.55. Для быстрого алгоритма Шура найден минимальный объём памяти, вычислена длина критического пути и проведена оценка оптимального параллелизма.Практическая значимость диссертационной работы состоит в сокращении площади и энергопотребления рассмотренных элементов и повышенииих универсальности, что вносит существенный вклад в улучшение энергоэффективности автономных беспроводных устройств, реализуемых на базеспециализированных полупроводниковых логических схем.Достоверность изложенных в работе результатов обеспечиваетсяпрактической реализацией предложенных схем и алгоритмов в виде полупроводниковых схем. Практическая реализация включала разработку моделей наязыке SystemC, автоматическую верификацию с помощью системы “Aegis forSystemC”, логический синтез полупроводниковых схем уровня вентилей дляакселераторов из моделей SystemC, логическое моделирование работы схеми синтез виртуальной топологии для малопотребляющего процесса производства полупроводниковых кристаллов с геометрическими нормами 22 нм.Апробация работы.

Основные результаты работы докладывались на:Международной конференции Общества Инженеров Акустиков (AES) (Россия, Санкт-Петербург, 2003), международной конференции по компьютерному анализу и моделированию (CDAM) (Беларусь, Минск, 2004), конференции молодых ученых “Гироскопия и Навигация” (Россия, Санкт-Петербург,2004), семинаре кафедры теоретической кибернетики СПбГУ (Россия, СанктПетербург, 2015, 2016), семинарах лаборатории Intel Labs (2013 - 2015).Личный вклад. Результаты, выносимые на защиту, получены авторомсамостоятельно.Публикации.

Основные результаты по теме диссертации изложеныв 12 печатных публикациях [1–12], в том числе 4 [1–4] — в журналах,рекомендованных ВАК, 5 [5,6,9–11] — в тезисах докладов на международныхконференциях на английском языке, из них 3 [9–11] индексируются Scopus,[12] заявка на патент США.Работы [4, 5, 7–11] написаны в соавторстве.

В работе [4] автору принадлежит постановка задачи, формулировка всех теорем и их доказательство,кроме доказательства теоремы 4. В работе [8, 9] автору принадлежит раздел, посвященный практическому опыту реализации. В [7] автору принадлежит постановка задачи, анализ существующих систем для выделения общихтребований, раздел по использованию Java в системном программировании.В [10, 11] автору принадлежит постановка задачи и разработка алгоритмаобнаружения ошибок синхронизации с помощью анализа достижимости.