Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Салищев, Сергей Игоревич

• Салищев, Сергей Игоревич
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Салищев, Сергей Игоревич

Оглавление

Введение

1 Факторы энергоэффективности

1.1 Общая модель энергопотребления тактируемых логических схем

1.2 Мощность КМОП устройств

1.3 Методы оптимизации энергопотребления

1.4 Методы логического синтеза

1.5 Типичная архитектура акселератора

1.5.1 Оценка рассеиваемой мощности акселератора при фиксированном размере задачи

1.5.2 Асимптотическая скорость роста мощности при росте размера задачи

1.6 Выбор оптимального типа памяти

1.7 Выбор оптимальной ширины и представления числовых данных

1.8 Рематериализация данных

1.9 Влияние перспективных технологий на энергоэффективность

1.9.1 Схемы с пороговым напряжением питания

1.9.2 Память на основе фазового перехода и магниторезистив-

ная память

1.10 Влияние архитектуры программного обеспечения на энергоэффективность

1.10.1 Операционные системы с поддержкой страничной памяти

1.10.2 Операционные системы без поддержки страничной памяти

1.10.3 Cреды управляемого исполнения

1.11 Формальная верификация как средство повышения энергоэффективности

2 Аппаратное ускорение вычисления элементарных функций при помощи специализированных вычислительных блоков

2.1 Постановка задачи аппроксимации с заданной точностью

2.2 Задача уменьшения размера таблиц

2.3 Оценка точности аппроксимации на одном сегменте

2.3.1 Погрешность аппроксимации интерполяционным полиномом с ограничениями типа неравенства

2.3.2 Погрешность квадратичной и кубической аппроксимации интерполяционным полиномом

2.4 Расчёт таблиц при помощи целочисленного линейного программирования

2.4.1 Целочисленная аппроксимация на одном сегменте

2.4.2 Случай квазисплайна

2.4.3 Оптимизационная задача

2.5 Результаты прототипирования

3 Поточный алгоритм БПФ на многобанковой памяти

3.1 Общий подход к разработке поточных акселераторов БПФ

3.1.1 Синхронные графы потоков данных

3.1.2 Расщепляющее правило БПФ

3.1.3 Инверсия индексов

3.1.4 Формула БПФ произвольной размерности во временной области

3.1.5 Формула БПФ произвольной размерности в частотной области

3.1.6 Реализация круговой свёртки

3.2 Организация многобанковой памяти

3.2.1 Постановка задачи

3.2.2 Акселератор БПФ по смешанному основанию с памятью

3.2.3 Акселератор БПФ по смешанному основанию с памятью

3.3 Самосортирующиеся БПФ

3.3.1 Акселератор самосортирующего БПФ с памятью 3.4 Результаты прототипирования

111

4 Ускорение решения уравнений Юла-Уокера

4.1 Подавление дальнего эха с помощью линейного фильтра с длинной импульсной характеристикой

4.2 Обращение тёплицевой матрицы при помощи многочленов Сегё

и Шура

4.2.1 Многочлены Сегё и факторизация обратной матрицы к тёплицевой

4.2.2 Проблема коэффициентов Шура

4.2.3 Спектральные плотности и функции Шура

4.2.4 Связь многочленов Сегё и Шура

4.3 Быстрый алгоритм Шура

4.3.1 Транзитивность многочленов Шура

4.3.2 Преобразование коэффициентов функций Шура

4.3.3 Структура бинарного дерева при расчёте параметров Шура

4.3.4 Расчёт многочленов Шура по параметрам Шура

4.3.5 Расчёт остаточных членов

4.3.6 Формулировка быстрого алгоритма Шура

4.4 Сложность расчёта многочленов Шура

4.4.1 Общая оценка количества операций

4.4.2 Общая оценка количества адресуемой памяти

4.5 Оценка оптимального параллелизма и времени вычислений быстрого алгоритма Шура на устройстве с аппаратным ускорением БПФ

4.5.1 Оценка количества комплексных чтений в вещественном алгоритме Шура

4.5.2 Оценка длины критического пути

4.5.3 Оценка времени вычислений быстрого алгоритма Шура

для вещественных данных на 2к конвейерных процессорах

4.5.4 Оценка оптимального параллелизма

4.6 Гибридный алгоритм фильтрации с малой задержкой

Заключение

Список иллюстраций

Список таблиц

Литература

A Методы оптимизации энергопотребления

А.1 Уменьшение напряжения питания

А.2 Несколько напряжений питания

А.3 Масштабирование транзисторов

А.4 Сдвиг потенциала подложки

А.5 Несколько сигналов тактирования

А.6 Отключение тактирования

А.7 Уменьшение переходных процессов

А.8 Стекирование транзисторов

А.9 Вентили с различными пороговыми напряжениями

А.10 Дупликация блоков

А.11 Конвейеризация

А.12 Распределение ресурсов

А.13 Оптимизация представления данных

А.14 Арифметические оптимизации

А.15 Мультиплексирование ресурсов по времени

А.16 Отключение питания

А.17 Динамическое управление частотой и напряжением питания

A.18 Использование параллельных алгоритмов

B Полиномиальная интерполяция

B.1 Интерполяционные полиномы

В.2 Погрешность интерполяционных полиномов

В.3 Интерполирование производных

В.4 Погрешность аппроксимации интерполяционным полиномом

C Задача смешанного целочисленного линейного программирования

C.1 Выбор алгоритма решения задачи линейного программирования

C.2 Метод ветвей и границ для решения задачи смешанного целочисленного линейного программирования

D Реализация специальных видов БПФ

D.1 Комплексный алгоритм Radix-2

D.2 Комплексный алгоритм Split-Radix в частотной области

D.3 Вещественный алгоритм Radix-2 во временной области

D.4 Вещественный алгоритм Split-Radix в частотной области

D.5 Двойная вещественная интерполяция

Введение диссертации (часть автореферата) на тему «Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти»

Введение

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

В современных беспроводных малопотребляющих устройствах наблюдается увеличение требований к вычислительной мощности при сохранении высокой автономности и компактности. Это обусловлено изменением способа использования устройства в сторону постоянного интерактивного взаимодействия с окружением и информационной средой. В устройствах появляется поддержка низкоэнергетических беспроводных протоколов передачи данных с высокой пропускной способностью, таких, как ZigBee,WiFi, Bluetooth. Кроме того, становится востребованной непрерывная обработка аудио- и видеоданных, необходимая для реализации дополненной реальности и голосового управления устройством в режиме "свободные руки". В связи с этим возникают новые требования к энергоэффективности устройств, поскольку тракт предварительной обработки данных c сенсоров и беспроводное соединение должны быть постоянно активны.

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

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

По следующая обработка данных может включать такие вычислительно сложные алгоритмы, как распознавание речи, распознавание объектов и семантический анализ с учетом контекста (предыдущие действия пользователя, географическое положение, аудиовизуальная информация, другие данные сенсоров). Однако эти алгоритмы начинают работать только после обнаружения речи или объекта интереса и аутентификации пользователя на этапе предварительной обработки. В текущем поколении устройств они реализованы в облаке. Поэтому их вклад в энергопотребление устройства на текущем этапе развития техники относительно невелик. Однако есть запрос на перенос этих алгоритмов на устройство без уменьшения времени автономной работы с целью уменьшения зависимости от подключения к беспроводной сети передачи данных и увеличения приватности пользователя. Это приводит к необходимости оптимизации алгоритмов и их аппаратной реализации по энергопотреблению.

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

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

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

В первой главе описывается новая модель энергопотребления и исследуется оптимизация ее параметров. Также в главе рассматривается влияние на энергопотребление других факторов, таких как архитектура памяти, представление числовых данных, архитектура процессора и операционной системы, использование языков управляемого выполнения (Java, C# и т.п.), моделей параллельных вычислений и средств автоматической верификации.

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

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

Далее в иерархии сложности можно расположить процедуры вычисления элементарных функций, таких как ln, exp, sin, cos, л/х, 1/ж. Эти функции часто встречаются в алгоритмах цифровой обработки сигналов, и энергоэффективность и скорость их вычисления могут существенно влиять на энергоэффективность устройства в целом. Для вычисления могут использоваться итерационные методы, табулирование, аппроксимация функций при помощи многочленов или их комбинации. Сплайны различного вида можно рассматривать как комбинацию табулирования и полиномиальной аппроксимации. Возможно вычисление различными методами с использованием инструкций программируемого процессора. Оно не является наиболее энергоэффективным методом для специализированной аппаратуры и может применяться только в случае однократных вычислений, существенно не влияющих на сложность алгоритма. Наиболее медленным методом вычислений в аппаратуре является алгоритм CORDIC [1], вычисляющий один бит значения за такт с помощью операций суммирования и сдвига. Следующая группа методов основана на двудольных таблицах [2] и вычисляет сразу группу битов за такт. Так же как и в CORDIC используются только операции суммирования и сдвига.

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

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

Из более сложных базовых алгоритмов обработки сигналов наиболее часто используется Быстрое Преобразование Фурье. Под БПФ понимается группа алгоритмов для вычисления дискретного преобразования Фурье с вычислительной сложностью 0(п ln п), где п - длина БПФ. Основные исследования в области оптимизации БПФ идут в направлениях минимизации общего числа операций, оптимизации для выполнения на процессорах с поддержкой векторных операций общего назначения и оптимизации для специализированных полупроводниковых схем. Наиболее быстрым по количеству операций на сегодня является алгоритм Джонсона [4], основанный на split-radix алгоритме. Для коротких БПФ часто применяется нерекурсивный алгоритм Соренсена того же типа [5]. Основным отличием между параллельными специализированными схемами и процессорами общего применения является дисциплина обращения к памяти. Алгоритмы для процессоров подразумевают произвольный доступ как к памяти данных, так и к памяти кода, для реализации которого требуются сложные и энергозатратные аппаратные механизмы, в то время как алгоритмы для специализированных схем используют память специальной структуры, оптимизированную по энергопотреблению и площади и фиксированный вычислительный блок для вычисления бабочек. Таким образом,

при требовании параллелизма специализированные схемы оказываются более энергоэффективными, поскольку не требуют специальных модификаций аппаратуры для обеспечения произвольного доступа к памяти и выборки кода программы для вычислений и адресации памяти. Существующие алгоритмы реализации БПФ на специализированной аппаратуре можно разделить по асимптотике времени вычислений 0(1), 0(1п п), О(п), 0(п 1п п). Выбор алгоритма зависит от способа применения блока вычисления БПФ. При дополнительном условии переиспользования ресурсов и управляемой длины преобразования, которые часто встречаются в реальных задачах с длинными БПФ, более эффективными оказываются алгоритмы с временем работы 0(п 1п п) и памятью с произвольным доступом, поскольку они обеспечивают гибкость по длине БПФ и используют библиотечную память. К таким алгоритмам относится поточный БПФ Джонсона [6]. При повышении параллелизма БПФ за счет увеличения основания более 2, алгоритмы БПФ по чистому основанию теряют эффективность, и требуется производить вычисления по смешанному основанию.

Алгоритм Джонсона применим только для чистых оснований или, с небольшими модификациями, для смешанного основания без параллелизма бабочек. Модификация алгоритма Джонсона, предложенная Джо и Санву [7] специализирована для оснований 2/4. Применение для других смешанных оснований требует модификации алгоритма.

Во многих задачах более эффективными являются самосортирующие алгоритмы БПФ к таким алгоритмам относятся реализации Джонсона-Буруса и Темплтона [8]. Алгоритм Джонсона-Буруса сформулирован для однобанковой памяти с произвольным доступом, его применение с другим типом памяти требует адаптации. Алгоритм Темплтона является строго последовательным и сформулирован для скалярных процессоров.

Также требуется алгоритмическая адаптация под наиболее эффективную архитектуру памяти, предоставляемую библиотекой компонентов, например, однопортовую память. Такие адаптации для алгоритмов БПФ без копирования пока не рассматривались в литературе.

Разработка потоковых алгоритмов БПФ с ограничением на доступ к памяти по существу является задачей составления расписания для синхронного

графа потока данных. Результаты расчета каждой бабочки записываются на те же места, с которых считывались для нее входные данные. В многобанковой памяти все крылья каждой бабочки должны оказаться в разных банках, иначе возникает конфликт. При этом общее количество ячеек памяти минимально -равно длине БПФ. Комбинаторные задачи нахождения начальных распределений, гарантирующие отсутствие конфликтов для стадий БПФ с произвольными основаниями, составляют основное содержание главы 3.

Другим часто используемым классом алгоритмов в цифровой обработке сигналов является Ьи факторизация тёплицевых и обратных к тёплицевым матриц. Необходимость в этом возникает при решении уравнений Юла-Уокера при построении оптимальных неупреждающих линейных фильтров. Задачи этого типа и большой размерности часто возникают в акустических задачах эхо- и шумоподавления и разделения источников сигнала. Это связано с малой скоростью распространения звука и реверберацией. Для решения задачи факторизации обычно используются алгоритмы Левинсона и Шура, имеющие асимптотику сложности 0(п2), где п- длина вектора автокорреляций. Для задач большой размерности могут использоваться быстрый алгоритм Шура, предложенный Аммаром и Греггом [9] и Воеводиным и Тыртышниковым [10] со сложностью 0(п 1п2 п), или предобусловленный метод сопряженных градиентов со сложностью итерации 0(п 1п п). Оба алгоритма основаны на использовании БПФ и могут использоваться как пример энергоэффективной реализации сложных алгоритмов с БПФ.

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

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

фициент параллелизма для быстрого алгоритма Шура на 4096 отсчетов при выполнении на поточном акселераторе БПФ, который оказался равным р = 4.

Целью данной работы является разработка алгоритмов для минимизации сложности расчетов, характерных для статистической обработки сигналов. Сложность измеряется энергоэффективностью, которая моделируется в главе 1. Она зависит, в частности, от длины таблиц при расчете стандартных элементарных функций, от доступа к памяти в реализации БПФ, от самосортировки БПФ, от параллелизма в быстром алгоритме обращения тёплицевых матриц.

Для достижения поставленной цели необходимо было решить следующие задачи:

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

2. Разработать эффективные целочисленные алгоритмы вычисления элементарных функций с заданной точностью и минимальной длиной таблицы;

3. Разработать расписание для реализации графа потока данных для БПФ на многобанковой памяти;

4. Исследовать параллелизм быстрого алгоритма Шура.

Основные положения, выносимые на защиту:

1. Метод качественной оценки мощности и выбора оптимального параллелизма для энергоэффективных специализированных КМОП вычислительных блоков.

2. Метод вычисления элементарных функций при помощи почти гладкого четырехзвенного квазисплайна и оценка точности полиномиальной аппроксимации с коэффициентами с фиксированной точкой, ограниченной на равномерной сетке.

3. Теорема о размещении данных БПФ в многобанковой памяти при вычислении по произвольным смешанным основаниям.

4. Теорема о размещении данных и порядке вычисления самосортирующегося БПФ.

5. Теорема о размещении данных и порядке вычисления БПФ для одно-портовой памяти.

6. Анализ энергоэффективности алгоритма Ьи факторизации вещественных тёплицевых матриц на сверточном акселераторе для задачи эхоком-пенсации при помощи быстрого алгоритма Шура.

Научная новизна:

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

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

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

4. Доказана теорема о самосортирующейся модификации БПФ в многобанковой памяти по смешанным основаниям, а также аналогичная теорема для вычислительного устройства с однопортовой памятью.

5. Для быстрого алгоритма Шура найден минимальный объём памяти, вычислена длина критического пути и проведена оценка оптимального параллелизма.

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

Достоверность изложенных в работе результатов обеспечивается практической реализацией предложенных схем и алгоритмов в виде полупроводниковых схем. Практическая реализация включала разработку моделей на языке SystemC, автоматическую верификацию с помощью системы "Aegis for SystemC", логический синтез полупроводниковых схем уровня вентилей для акселераторов из моделей SystemC, логическое моделирование работы схем и синтез виртуальной топологии для малопотребляющего процесса производства полупроводниковых кристаллов с геометрическими нормами 22 нм.

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

Личный вклад. Автор предложил модель энергопотребления для малопо-

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

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

Публикации. Основные результаты по теме диссертации изложены в 12 печатных публикациях [11-22], в том числе 4 [11-14] — в журналах, рекомендованных ВАК, 5 [15,16,19-21] — в тезисах докладов на международных конференциях на английском языке, из них 3 [19-21] индексируются Scopus, 1 [22] заявка на патент США.

Работы [14,15,17-21] написаны в соавторстве. В работе [14] автору принадлежит постановка задачи, формулировка всех теорем и их доказательство, кроме доказательства теоремы 4. В работе [18,19] автору принадлежит раздел, посвященный практическому опыту реализации. В [17] автору принадлежит постановка задачи, анализ существующих систем для выделения общих требований, раздел по использованию Java в системном программировании. В [20,21] автору принадлежит постановка задачи и разработка алгоритма обнаружения ошибок синхронизации с помощью анализа достижимости. В работе [15] автор выполнял математическое моделирование.

Объем и структура работы. Диссертация состоит из введения, четырех глав и заключения. Полный объем диссертации — 209 страниц текста. Объем основного текста — 167 страниц с 9 рисунками, 14 таблицами и 5 приложениями. Список литературы содержит 85 наименований.

Глава 1

Факторы

энергоэффективности

Энергоэффективность является одним из основных параметров беспроводных полупроводниковых устройств.

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

Алгоритмические оптимизации, относящиеся к системному уровню, как правило, рассматриваются в рамках существующих микропроцессорных архитектур и направлены на повышение производительности, а не энергоэффективности.

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

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

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

Ошибки алгоритма, оказавшиеся в аппаратной реализации устройства, невозможно исправить без выпуска новой версии кристалла, что означает высокую стоимость ошибки. Это определяет консервативность в выборе алгоритмов и дополнительные усилия на проверку правильности их работы в процессе разработки аппаратной части устройства, что еще более замедляет процесс разработки. Кроме того, схему невозможно использовать в других аналогичных устройствах, имеющих немного отличающуюся функциональность (например, сотовый телефон, беспроводная гарнитура, наголовное устройство, часы), если эта вариативность не была заложена при разработке. Во-вторых, в чипах, произведенных по современным литографическим процессам, существенную долю потерь энергии создают токи утечки, которые пропорциональны суммарной площади подключенных к питанию элементов на кристалле. Таким образом, для минимизации токов утечки крупные базовые блоки, такие, как умножители, деревья сумматоров, управляемые сдвиговые регистры, регистровая память, статическая память должны максимально переиспользоваться между различными частями алгоритмов и, по возможности, полностью отключаться от питания во время простоя.

Это требование идеологически близко к концепции программируемого процессора. Под программируемостью подразумевается наличие эффективных инструментальных средств разработки программ на языках высокого уровня (С, С++, Fortran и др.) и возможность эффективной компиляции программ, реализующих широкий класс алгоритмов цифровой обработки сигналов.

Разработка на основе программируемого процессора обладает следующими преимуществами перед специализированным непрограммируемым устройством:

1. возможность переиспользования вычислительных ресурсов между частями алгоритма для экономии площади кристалла и улучшения энергоэффективности;

2. переиспользование памяти данных различными частями алгоритмов для уменьшения ее размера и уменьшения необходимости копирования данных, что ведет к улучшению энергоэффективности;

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

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

5. наличие развитых средств программирования (компилятор, отладчик, операционная система, библиотеки) для сокращения времени разработки.

С другой стороны, сигнальные процессоры общего применения во многих случаях оказываются недостаточно производительны и/или энергоэффек-тивны для использования в малопотребляющих автономных устройствах по следующим причинам:

1. дополнительные блоки для реализации программируемости;

2. недостаточный параллелизм, связанный с последовательной структурой программы;

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

4. использование части полосы пропускания памяти для загрузки программы;

5. потери времени на выполнение ветвлений и циклов;

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

Таким образом, разработка специализированных энергоэффективных систем цифровой обработки данных с высокой производительностью и возможностью переиспользования ресурсов представляется наиболее выигрышной стратегией как с точки зрения гибкости, так и с точки зрения энергоэффективности. Общая архитектура для таких вычислительных блоков на базе ОЗУ была предложена Хартенштейном [23] и основана на потоке данных, в отличие от обычных процессоров, управляемых программой (поток управления). Архитектура управляется с помощью шаблонов адресного генератора и конфигураций потока данных, таким образом, она может реализовывать произвольный наперед заданный параллелизм и переиспользование ресурсов без накладных расходов на исполнение программы.

Список литературы диссертационного исследования кандидат наук Салищев, Сергей Игоревич, 2016 год

Литература

1. Voider J. E. The CORDIC Trigonometric Computing Technique // Electronic Computers, IRE Transactions on. 1959. Sept. Vol. EC-8, no. 3. P. 330-334.

2. Das Sarma D., Matula D. W. Faithful bipartite ROM reciprocal tables // Computer Arithmetic, 1995., Proceedings of the 12th Symposium on / IEEE. 1995. P. 17-28.

3. Strollo A. G. M., Caro D. D., Petra N. Elementary Functions Hardware Implementation Using Constrained Piecewise-Polynomial Approximations // IEEE Transactions on Computers. Los Alamitos, CA, USA, 2011. Vol. 60, no. 3. P. 418-432.

4. Johnson S. G., Frigo M. A Modified Split-Radix FFT With Fewer Arithmetic Operations. // IEEE Transactions on Signal Processing. 2007. Vol. 55, no. 1. P. 111-119. URL: "http://dblp.uni-trier.de/db/ journals/tsp/tsp55.html#JohnsonF07".

5. Sorensen H., Heideman M., Burrus C. On computing the split-radix FFT // Acoustics, Speech and Signal Processing, IEEE Transactions on. 1986. Feb. Vol. 34, no. 1. P. 152-156.

6. Johnson L. Conflict free memory addressing for dedicated FFT hardware // Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on. 1992. Vol. 39, no. 5. P. 312-316.

7. Jo B. G., Sunwoo M. H. New continuous-flow mixed-radix (CFMR) FFT processor using novel in-place strategy // Circuits and Systems I: Regular Papers, IEEE Transactions on. 2005. Vol. 52, no. 5. P. 911-919.

8. Hegland M. A Self-sorting In-place Fast Fourier Transform Algorithm Suitable for Vector and Parallel Processing // Numer. Math. Secaucus, NJ, USA, 1994. oct. Vol. 68, no. 4. P. 507-547. URL: "http://dx.doi.org/10.1007/ s002110050074".

9. Ammar G. S., Gragg W. B., Solvers T. The Generalized Schur Algorithm for the Superfast Solution of Toeplitz Systems // in Rational Approximation and its Applications in Mathematics and Physics. Springer, 1987. P. 315-330.

10. В.В.Воеводин Е.Е.Тыртышников. Вычислительные процессы с теплице-выми матрицами. М.: Наука, 1987. с. 320.

11. Салищев С.И. Вычислительные аспекты компенсации акустического эха // Гироскопия и навигация. 2005. № 1. с. 90.

12. Салищев С.И. Быстрый алгоритм Шура в задаче подавления акустического эха // Вестник молодых ученых. Серия: прикладная математика и механика. 2005. Т. 3. С. 77-87.

13. Салищев С.И. Кусочно-полиномиальная аппроксимация с сокращенными таблицами и гарантированной точностью // Компьютерные инструменты в образовании. 2012. № 5. С. 3-10.

14. Салищев С.И. Шеин Р.Е. Новые алгоритмы для конвейерного вычисления БПФ по смешанному основанию без копирования на многобанковой памяти с произвольным доступом // Компьютерные инструменты в образовании. 2013. №2. С. 18-30.

15. Echo Compensation by Equalizer with Precise Spectrum Estimation / S. I. Salischev, A. E. Barabanov, K. M. Putyakov et al. // Audio Engineering Society Conference: 21st International Conference: Architectural Acoustics and Sound Reinforcement. 2002. Jun. URL: http://www.aes.org/e-lib/browse.cfm?elib=11191.

16. S. S. Computational aspects of real-time acoustic echo cancellation // 7th international conference: Computer data analysis and modeling. Vol. 2. 2004. P. 146-149.

17. Салищев С.И. Ушаков Д.С. Использование языков и сред управляемого исполнения для системного программирования // Системное программирование. 2009. Т. 4. С. 198-216.

18. The Moxie JVM experience. Technical Report TRCS-08-01: Tech. Rep.: / S. I. Salishev, S. M. Blackburn, M. Danilov et al.: Australian National University, Department of Computer Science, 2008. Jan.

19. Demystifying Magic: High-level Low-level Programming / S. I. Salishev, D. Frampton, S. M. Blackburn et al. // Proceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments. VEE '09. New York, NY, USA: ACM, 2009. P. 81-90. URL: http://doi.acm.org/10.1145/1508293.1508305.

20. Static analysis method for deadlock detection in SystemC designs / S. Salishev, M. Moiseev, A. Zakharov et al. // System on Chip (SoC), 2011 International Symposium on. 2011. Oct. P. 42-47.

21. Salishev S., Glukhikh M., Moiseev M. A Static Analysis Approach for Verification of Synchronization Correctness of SystemC Designs // Proceedings of the 2013 Euromicro Conference on Digital System Design. DSD '13. Washington, DC, USA: IEEE Computer Society, 2013. P. 89-96. URL: http://dx.doi.org/10.1109/DSD.2013.17.

22. Salishev S. Continuous-flow conflict-free mixed-radix fast fourier transform in multi-bank memory. 2014. jul. WO Patent App. PCT/IB2013/000,446. URL: http://google.com/patents/W02014108718A1.

23. A novel ASIC design approach based on a new machine paradigm / R. W. Hartenstein, A. G. Hirschbiel, M. Riedmuller et al. // Solid-State Circuits, IEEE Journal of. 1991. Vol. 26, no. 7. P. 975-989.

24. G E. Latched carry save adder circuit for multipliers. 1967. sep. US Patent 3,340,388. URL: http://www.google.com/patents/US3340388.

25. Wallace C. A Suggestion for a Fast Multiplier // Electronic Computers, IEEE Transactions on. 1964. Feb. Vol. EC-13, no. 1. P. 14-17.

26. BOOTH A. D. A SIGNED BINARY MULTIPLICATION TECHNIQUE // The Quarterly Journal of Mechanics and Applied Mathematics. 1951. Vol. 4, no. 2. P. 236-240. URL: http://qjmam.oxfordjournals.org/content/4/2/236.abstract.

27. B R. Simultaneous carry adder. 1960. dec. US Patent 2,966,305. URL: http://www.google.com/patents/US2966305.

28. Ladner R. E., Fischer M. J. Parallel prefix computation // Journal of the ACM (JACM). 1980. Vol. 27, no. 4. P. 831-838.

29. Power-efficient system design / P. R. Panda, B. Silpa, A. Shrivastava et al. Springer, 2010.

30. Sherazi Y. Design Space Exploration of Digital Circuits for Ultra-low Energy Dissipation. Ph.D. thesis: Lund University. 2013.

31. Bringing Network-on-Chip links to 45nm / M. Ferraresi, G. Gobbo, D. Lu-dovici et al. // System on Chip (SoC), 2011 International Symposium on. 2011. Oct. P. 122-127.

32. IEEE Std 1666 - 2005 IEEE Standard SystemC Language Reference Manual. 2006.

33. Amdahl G. M. Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities // Proceedings of the April 18-20, 1967, Spring Joint Computer Conference. AFIPS '67 (Spring). New York, NY, USA: ACM, 1967. P. 483-485. URL: http://doi.acm.org/10.1145/1465482.1465560.

34. Woo D. H., Lee H.-H. S. Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era // Computer. Los Alamitos, CA, USA, 2008. dec. Vol. 41, no. 12. P. 24-31. URL: http://dx.doi.org/10.1109/MC.2008.494.

35. Gustafson John L. Reevaluating Amdahl's Law // Communications of the ACM. 1988. T. 31. C. 532-533.

36. T. Grotker E. M., Mauss O. Evaluation of HW/SW Tradeoffs Using Behavioral Synthesis // Proc. Int. Conf. on Signal Processing Application and Technology (ICSPAT). Boston: 1996. oct.

37. Open SystemC Initiative. SystemC Synthesizable Subset Draft 1.4: Tech. Rep.: : IEEE, 2009. URL: "http://www.accellera.org/images/ downloads/drafts-review/SystemC_Synthesis_Subset_ Draft_1_4.pdf".

38. Calypto. Catapult C Synthesis. "[Online; accessed 20-Sep-2016]". URL: "https://www.mentor.com/hls-lp/".

39. Cadence. C-to-Silicon Compiler. "[Online; accessed 20-Sep-2016]". URL: "http://www.cadence.com/products/sd/silicon_compiler/ pages/default.aspx".

40. Cadence. Cynthesizer. "[Online; accessed 20-Sep-2016]". URL: "https: //www.cadence.com/content/dam/cadence-www/global/ en_US/documents/tools/system-design-verification/ cynthesizer-solutioon-ds.pdf".

41. Precision and error analysis of MATLAB applications during automated hardware synthesis for FPGAs. / A. Nayak, M. Haldar, A. N. Choudhary et al. // DATE. 2001. P. 722-728. URL: "http://dblp.uni-trier.de/db/ conf/date/date2001.html#NayakHCB01".

42. Shi C., Brodersen R. W. Automated fixed-point data-type optimization tool for signal processing and communication systems. // DAC / Ed. by S. Malik, L. Fix, A. B. Kahng. ACM, 2004. P. 478-483. URL: "http://dblp. uni-trier.de/db/conf/dac/dac2004.html#ShiB04".

43. Stephenson M., Babb J., Amarasinghe S. P. Bitwidth analysis with application to silicon compilation. // PLDI / Ed. by M. S. Lam. ACM, 2000. P. 108-120. URL: "http://dblp.uni-trier.de/db/conf/pldi/ pldi2000.html#StephensonBA00".

44. Automatic Conversion of Floating Point MATLAB Programs into Fixed Point FPGA Based Hardware Design. / P. Banerjee, D. Bagchi, M. Haldar et al. // FCCM. IEEE Computer Society, 2003. P. 263-264. URL: "http://dblp.uni-trier.de/db/conf/fccm/fccm2003. html#BanerjeeBHNKU03".

45. Sung W., Kum K.-I. Simulation-based word-length optimization method for fixed-point digital signal processing systems. // IEEE Transactions on Signal Processing. 1995. Vol. 43, no. 12. P. 3087-3090. URL: "http://dblp. uni-trier.de/db/journals/tsp/tsp43.html#SungK95".

46. Smart bit-width allocation for low power optimization in a systemc based ASIC design environment. / A. Mallik, D. Sinha, P. Banerjee et al. // DATE / Ed. by G. G. E. Gielen. European Design and Automation Association, Leuven, Belgium, 2006. P. 618-623. URL: "http://dblp.uni-trier.de/db/ conf/date/date2006p.html#MallikSBZ06".

47. Han K., of Texas at Austin T. U. Automating Transformations from Floatingpoint to Fixed-point for Implementing Digital Signal Processing Algorithms. University of Texas at Austin, 2006. URL: "http://books.google.ru/ books?id=VW0htwAACAAJ".

48. Hai Nam N., Menard D., Sentieys O. Novel Algorithms for Word-length Optimization // 19th European Signal Processing Conference (EUSIPCO-2011). Barcelona, Spain: 2011. Sep. URL: "http://hal.inria.fr/ inria-00617718".

49. Holdings A. Cortex-R5 Technical Reference Manual: c0, MPU Type Register. "[Online; accessed 20-Sep-2016]". URL: "http: //infocenter.arm.com/help/index.jsp?topic=/com.arm. doc.ddi0337e/BIHHGADD.html".

50. Holdings A. Cortex-A5 Processor. "[Online; accessed 20-Sep-2016]". URL: "http://www.arm.com/products/processors/cortex-a/ cortex-a5.php".

51. Holdings A. Cortex-R5 Processor. "[Online; accessed 20-Sep-2016]". URL: "http://www.arm.com/products/processors/cortex-r/ cortex-r5.php".

52. Yamauchi H., Wolczko M. Writing Solaris device drivers in Java // Proceedings of the 3rd workshop on Programming languages and operating systems: linguistic support for modern operating systems / ACM. 2006. p. 3.

53. Hunt G. C., Larus J. R. Singularity: Rethinking the Software Stack // SIGOPS Oper. Syst. Rev. New York, NY, USA, 2007. apr. Vol. 41, no. 2. P. 37-49. URL: http://doi.acm.org/10.1145/1243418.1243424.

54. The Jikes research virtual machine project: building an open-source research community / B. Alpern, S. Augart, S. M. Blackburn et al. // IBM Systems Journal. 2005. Vol. 44, no. 2. P. 399-417.

55. Effort J. N. O. S. D. JNode. "[Online; accessed 20-Sep-2016]". URL: "http: //jnode.org/".

56. Cierniak M., Corporation I. The Open Runtime Platform: A Flexible HighPerformance Managed Runtime Environment // Intel Technology Journal. 2003. Vol. 7. P. 5-18.

57. Hertz M., Berger E. D. Quantifying the performance of garbage collection vs. explicit memory management // ACM SIGPLAN Notices / ACM. Vol. 40. 2005. P. 313-326.

58. Bacon D. F., Cheng P., Rajan V. The Metronome: A simpler approach to garbage collection in real-time systems // On the Move to Meaningful Internet Systems 2003: OTM 2003 Workshops / Springer. 2003. P. 466-478.

59. Oracle. Sun SPOT Dev. "[Online; accessed 20-Sep-2016]". URL: "http: //www.sunspotdev.org/".

60. Research M. Micro.NET. "[Online; accessed 20-Sep-2016]". URL: "http: //netmf.codeplex.com/".

61. Foundation A. Apache Public License 2.0. 2004. "[Online; accessed 20-Sep-2016]". URL: "http://www.apache.org/licenses/LICENSE-2. 0".

62. Built-in Self-Test for Digital Integrated Circuits / V. D. Agrawal, C.-J. Lin, P. W. Rutkowski et al. // AT&T Technical Journal. 1994. Vol. 73, no. 2. P. 30-39. URL: http://dx.doi.org/10.1002/j.1538-7305.1994.tb00576.x.

63. Leiserson C. E., Saxe J. B. Retiming synchronous circuitry // Algorithmica. 1991. Vol. 6, no. 1-6. P. 5-35.

64. The synchronous data flow programming language LUSTRE / N. Halbwachs, P. Caspi, P. Raymond et al. // Proceedings of the IEEE. 1991. Vol. 79, no. 9. P. 1305-1320.

65. Berry G., Gonthier G. The Esterel synchronous programming language: Design, semantics, implementation // Science of computer programming. 1992. Vol. 19, no. 2. P. 87-152.

66. Thies W., Karczmarek M., Amarasinghe S. StreamIt: A Language for Streaming Applications // International Conference on Compiler Construction. Grenoble, France: 2002. Apr. URL: http://groups.csail.mit.edu/commit/papers/02/streamit-cc.pdf.

67. Gilles K. The semantics of a simple language for parallel programming // In Information Processing'74: Proceedings of the IFIP Congress. Vol. 74. 1974. P. 471-475.

68. Lee E. A. The Problem with Threads // Computer. Los Alamitos, CA, USA, 2006. Vol. 39. P. 33-42.

69. Netzer R. H. B., Miller B. P. Improving the accuracy of data race detection // Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming. PPOPP '91. New York, NY, USA: ACM, 1991. P. 133-144. URL: http://doi.acm.org/10.1145/109625.109640.

70. SLAM2: static driver verification with under 4E. Bounimova, R. Kumar et al. // Proceedings of the 2010 Conference on Formal Methods in Computer-Aided Design. FMCAD '10. Austin, TX: FMCAD Inc, 2010. P. 35-42. URL: http://dl.acm.org/citation.cfm?id=1998496.1998508.

71. Cousot P. Abstract Interpretation // ACM Computing Surveys. New York, NY, USA, 1996. Vol. 28, no. 2. P. 324-328.

72. Локуциевский О.В., Гавриков М.Б. Начала численного анализа. ТОО "Янус 1995. URL: https://books.google.ru/books?id=-htEywAACAAJ.

73. Synopsys. DesignWare datapath building blocks. "[Online; accessed 20-Sep-2016]". URL: "https://www.synopsys.com/dw/buildingblock. php".

74. Parhi K. K., Messerschmitt D. G. Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding // IEEE Transactions on Computers. 1991. Feb. Vol. 40, no. 2. P. 178-195.

75. Chang W.-H., Nguyen T. On the Fixed-Point Accuracy Analysis of FFT Algorithms // Signal Processing, IEEE Transactions on. 2008. Oct. Vol. 56, no. 10. P. 4673-4682.

76. Hsiao C.-F., Chen Y., Lee C.-Y. A generalized mixed-radix algorithm for memory-based FFT processors // Circuits and Systems II: Express Briefs, IEEE Transactions on. 2010. Vol. 57, no. 1. P. 26-30.

77. Gardner W. G. Efficient convolution without input/output delay // Audio Engineering Society Convention 97 / Audio Engineering Society. 1994.

78. Ammar G. S., Gragg W. B. Numerical experience with a superfast real Toeplitz solver//Linear Algebra and its Applications. 1989. Vol. 121. P. 185-206.

79. Smith S. J. Lebesgue constants in polynomial interpolation // Annales Mathe-maticae et Informaticae / Eszterhazy Karoly College, Institute of Mathematics and Computer Science. 33 no. 109-123. 2006. P. 1787-5021.

80. MATLAB. version 8.0.0 (R2012b). Natick, Massachusetts: The MathWorks Inc., 2012.

81. Dantzig G. Linear programming and extensions. Princeton Univ. Press, 1963. aug. URL: "http://www.amazon.com/exec/obidos/redirect? tag=citeulike07-20&path=ASIN/0691059136".

82. Klee V., Minty G. J. How good is the simplex algorithm? // Inequalities / Ed. by O. Shisha. New York: Academic Press, 1972. Vol. III. P. 159-175.

83. Schrijver A. Theory of Linear and Integer Programming. New York, NY, USA: John Wiley & Sons, Inc., 1986.

84. Karmarkar N. A New Polynomial-time Algorithm for Linear Programming // Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing. STOC '84. New York, NY, USA: ACM, 1984. P. 302-311. URL: "http://doi.acm.org/10.1145/800057.808695".

85. Procedures for Optimization Problems with a Mixture of Bounds and General Linear Constraints / P. E. Gill, W. Murray, M. A. Saunders et al. // ACM Trans. Math. Softw. New York, NY, USA, 1984. Vol. 10, no. 3. P. 282-298. URL: "http://doi.acm.org/10.1145/1271.127 6".