Диссертация (Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти)
Описание файла
Файл "Диссертация" внутри архива находится в папке "Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти". PDF-файл из архива "Синтез алгоритмов обработки сигналов с ограничениями на минимальный параллелизм и объём памяти", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст из PDF
Санкт-Петербургский государственный университетНа правах рукописиСАЛИЩЕВ СЕРГЕЙ ИГОРЕВИЧСинтез алгоритмов обработки сигналов с ограничениями наминимальный параллелизм и объём памятиСпециальность 01.01.09 — дискретная математика иматематическая кибернетикаДиссертация на соискание учёной степеникандидата физико-математических наукНаучный руководитель:доктор физико-математических наук, профессор СПбГУБарабанов Андрей ЕвгеньевичСанкт-Петербург – 2016ОглавлениеВведение . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71 Факторы энергоэффективности . . . . . . . . . . . . . . . . . . . .171.1 Общая модель энергопотребления тактируемых логических схем 241.2 Мощность КМОП устройств . . . . . . . . . . . . . . . . . . . .251.3 Методы оптимизации энергопотребления . . . . . .
. . . . . . .271.4 Методы логического синтеза . . . . . . . . . . . . . . . . . . . .291.5 Типичная архитектура акселератора . . . . . . . . . . . . . . . .311.5.1Оценка рассеиваемой мощности акселератора при фиксированном размере задачи . . .
. . . . . . . . . . . . . .1.5.232Асимптотическая скорость роста мощности при ростеразмера задачи . . . . . . . . . . . . . . . . . . . . . . . .351.6 Выбор оптимального типа памяти . . . . . . . . . . . . . . . . .361.7 Выбор оптимальной ширины и представления числовых данных371.8 Рематериализация данных . .
. . . . . . . . . . . . . . . . . . . .421.9 Влияние перспективных технологий на энергоэффективность .431.9.1Схемы с пороговым напряжением питания . . . . . . . .1.9.2Память на основе фазового перехода и магниторезистивная память . . . . . . . . . . . . . .
. . . . . . . . . . . .43451.10 Влияние архитектуры программного обеспечения на энергоэффективность . . . . . . . . . . . . . . . . . . . . . . . . . . . . .451.10.1 Операционные системы с поддержкой страничной памяти 491.10.2 Операционные системы без поддержки страничной памяти 501.10.3 Cреды управляемого исполнения . . . . . . . . .
. . . . .511.11 Формальная верификация как средство повышения энергоэффективности . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2532 Аппаратное ускорение вычисления элементарных функций припомощи специализированных вычислительных блоков . . . . . .592.1 Постановка задачи аппроксимации с заданной точностью . . . .612.2 Задача уменьшения размера таблиц . . . . .
. . . . . . . . . . .622.3 Оценка точности аппроксимации на одном сегменте . . . . . . .642.3.1Погрешность аппроксимации интерполяционным полиномом с ограничениями типа неравенства . . . . . . . . .2.3.264Погрешность квадратичной и кубической аппроксимации интерполяционным полиномом . . . . . . . . . . . .662.4 Расчёт таблиц при помощи целочисленного линейного программирования . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .682.4.1Целочисленная аппроксимация на одном сегменте . . . .692.4.2Случай квазисплайна . . . . . . . . . . . . . . . . . . . .702.4.3Оптимизационная задача . . . . . . . . . . . . . . . . . .712.5 Результаты прототипирования . . .
. . . . . . . . . . . . . . . .753 Поточный алгоритм БПФ на многобанковой памяти . . . . . . .783.1 Общий подход к разработке поточных акселераторов БПФ . . .813.1.1Синхронные графы потоков данных . . . . . . . . . . . .813.1.2Расщепляющее правило БПФ . . . .
. . . . . . . . . . . .843.1.3Инверсия индексов . . . . . . . . . . . . . . . . . . . . . .863.1.4Формула БПФ произвольной размерности во временнойобласти . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1.588Формула БПФ произвольной размерности в частотнойобласти . . . . . .
. . . . . . . . . . . . . . . . . . . . . .91Реализация круговой свёртки . . . . . . . . . . . . . . . .953.2 Организация многобанковой памяти . . . . . . . . . . . . . . . .963.1.63.2.1Постановка задачи . . . . . . . . . . . . . . . . . . . . . .3.2.2Акселератор БПФ по смешанному основанию с 1r1w памятью . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .3.2.39799Акселератор БПФ по смешанному основанию с 1rw памятью . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1073.3 Самосортирующиеся БПФ . . . . . . . . . . . . . . . . . . . . . 11033.3.1Акселератор самосортирующего БПФ с 1r1w памятью . 1113.4 Результаты прототипирования . . .
. . . . . . . . . . . . . . . . 1174 Ускорение решения уравнений Юла–Уокера . . . . . . . . . . . . . 1184.1 Подавление дальнего эха с помощью линейного фильтра с длинной импульсной характеристикой . . . . . . . . . . . . . . . . . 1184.2 Обращение тёплицевой матрицы при помощи многочленов Сегёи Шура . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1214.2.1Многочлены Сегё и факторизация обратной матрицы ктёплицевой . . . . . . . . . . . . . . . . . . . . . . . . . . 1214.2.2Проблема коэффициентов Шура . . . . . . . . . . . . . . 1244.2.3Спектральные плотности и функции Шура . . . .
. . . . 1264.2.4Связь многочленов Сегё и Шура . . . . . . . . . . . . . . 1284.3 Быстрый алгоритм Шура . . . . . . . . . . . . . . . . . . . . . . 1314.3.1Транзитивность многочленов Шура . . . . . . . . . . . . 1314.3.2Преобразование коэффициентов функций Шура . . . .
. 1324.3.3Структура бинарного дерева при расчёте параметров Шура1334.3.4Расчёт многочленов Шура по параметрам Шура . . . . . 1344.3.5Расчёт остаточных членов . . . . . . . . . . . . . . . . . . 1364.3.6Формулировка быстрого алгоритма Шура . . . . . . . . . 1394.4 Сложность расчёта многочленов Шура . . . . . . . . .
. . . . . 1434.4.1Общая оценка количества операций . . . . . . . . . . . . 1434.4.2Общая оценка количества адресуемой памяти . . . . . . 1484.5 Оценка оптимального параллелизма и времени вычисленийбыстрого алгоритма Шура на устройстве с аппаратным ускорением БПФ . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . 1504.5.1Оценка количества комплексных чтений в вещественномалгоритме Шура . . . . . . . . . . . . . . . . . . . . . . . 1524.5.2Оценка длины критического пути . . . . . . . . . . . . . 1554.5.3Оценка времени вычислений быстрого алгоритма Шурадля вещественных данных на 2 конвейерных процессорах1574.5.4Оценка оптимального параллелизма . . . . . . . . .
. . . 1594.6 Гибридный алгоритм фильтрации с малой задержкой . . . . . . 1644Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166Список иллюстраций . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168Список таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169Литература . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 170A Методы оптимизации энергопотребления . . . . . . . . . . . . . . 180A.1 Уменьшение напряжения питания . . . . . . . . . . . . . . . . . 180A.2 Несколько напряжений питания . . . . . . . . . .
. . . . . . . . 181A.3 Масштабирование транзисторов . . . . . . . . . . . . . . . . . . 181A.4 Сдвиг потенциала подложки . . . . . . . . . . . . . . . . . . . . 182A.5 Несколько сигналов тактирования . . . . . . . . . . . . . . . . . 182A.6 Отключение тактирования . . . . . .
. . . . . . . . . . . . . . . 182A.7 Уменьшение переходных процессов . . . . . . . . . . . . . . . . 183A.8 Стекирование транзисторов . . . . . . . . . . . . . . . . . . . . . 183A.9 Вентили с различными пороговыми напряжениями . . . . . . . 183A.10 Дупликация блоков .
. . . . . . . . . . . . . . . . . . . . . . . . 184A.11 Конвейеризация . . . . . . . . . . . . . . . . . . . . . . . . . . . 185A.12 Распределение ресурсов . . . . . . . . . . . . . . . . . . . . . . . 185A.13 Оптимизация представления данных . . . . . . . . . . . . . . . .
185A.14 Арифметические оптимизации . . . . . . . . . . . . . . . . . . . 186A.15 Мультиплексирование ресурсов по времени . . . . . . . . . . . . 186A.16 Отключение питания . . . . . . . . . . . . . . . . . . . . . . . . . 187A.17 Динамическое управление частотой и напряжением питания . . 188A.18 Использование параллельных алгоритмов . . . . . . . . . . . . . 188B Полиномиальная интерполяция . . .
. . . . . . . . . . . . . . . . . 189B.1 Интерполяционные полиномы . . . . . . . . . . . . . . . . . . . 189B.2 Погрешность интерполяционных полиномов . . . . . . . . . . . 191B.3 Интерполирование производных . . . . . . . . . . . . . . . . . . 194B.4 Погрешность аппроксимации интерполяционным полиномом . 195C Задача смешанного целочисленного линейного программирования 1985C.1 Выбор алгоритма решения задачи линейного программирования 199C.2 Метод ветвей и границ для решения задачи смешанного целочисленного линейного программирования . .
