Диссертация (1150736)
Текст из файла
Санкт-Петербургский государственный университетНа правах рукописиСАЛИЩЕВ СЕРГЕЙ ИГОРЕВИЧСинтез алгоритмов обработки сигналов с ограничениями наминимальный параллелизм и объём памятиСпециальность 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 Метод ветвей и границ для решения задачи смешанного целочисленного линейного программирования . .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
