Автореферат (1150735), страница 3

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

Текст из файла (страница 3)

. . , 1 , 0 ) = (, . . . , , ) — мультииндекс, указывающий на последовательность выполнения стадий БПФ. Цифровая форманомера есть = (0 , 1 , . . . , −1 ), где⋆ = = −1 + (−2 + . . . + (1 + 0 ) . . .),и 0 ≤ 0 < и 0 ≤ < при 1 ≤ ≤ − 1. Разобьём каждую компоненту: = ¯ + ¯ , где 0 ≤ ¯ < , 0 ≤ ¯ < = /.12Пусть ≥ (+1)/2 — номер стадии БПФ. При цифровом представлении номеров компонент массива = (¯0 , ¯1 ,¯1 , . .

. , ¯−1 ,¯−1 )в системе счисления, порождённой мультииндексом = (, , , . . . , , ), навход каждой бабочки на стадии подаётся набор отсчётов, у номеров которых все компоненты ¯ и ¯ одинаковые, кроме компонент (¯ ,¯ ), которыепробегают все возможные значения. Поэтому естественным номером бабочки является = ( )0 , где 0 = (, , , . . . , , ) короче вектора на двекомпоненты и = (¯0 , ¯1 ,¯1 , . . . , ¯−1 ,¯−1 , ¯+1 ,¯+1 , . . . , ¯−1 ,¯−1 ).Определим операцию перестановки этой пары в конец мультииндекса номера бабочки = ( )0 : ( ) = (¯0 , ¯1 , . . . , ¯−1− ,¯− , .

. . , ¯−1 ,¯−1 , ¯+1 ,¯+1 , . . . , ¯−1 ,¯−1 , ¯− ,¯−1− )при ≥ (+1)/2.Теорема 4 Пусть > 2 и функция распределения входного вектора побанкам данных () определяется теоремой 2. Порядок обхода бабочекна -й стадии БПФ зададим номером такта () реализации бабочки сномером = ( )0 :⎧ ⌊︁ ⌋︁⎪ = 0,⎨ , () = ,1 ≤ ≤ ⌊ −12 ⌋,⎪⎩+1 0( ) , ⌊ 2 ⌋ ≤ ≤ − 1.Предположим, что длина конвейера удовлетворяет условию ≥ − 1.Тогда такой выбор порядка обхода и функции распределения побанкам обеспечивает отсутствие конфликтов при работе самосортирующего алгоритма для архитектуры потокового БПФ акселератора с банками 1r1w памяти при выполнении одной бабочки размера или бабочек размера за такт.В четвертой главе рассмотрено аппаратное ускорение решения уравнений Юла–Уокера на основе быстрого алгоритма Шура с использованиемаппаратного блока вычисления БПФ на примере системы эхоподавления.13В данной работе используется модель эхоподавления при помощивнутренней отрицательной обратной связи, которая сводится к решению вреальном времени системы уравнений Юла-Уокера ℎ = , где - тёплицева, положительно определенная матрица.

Длина вектора ℎ — 104 и более.Для обращения матрицы используется быстрый алгоритм Шура [Ammar, Gragg, 1987] для факторизации −1 на основе БПФ.Лемма 3 Для реализации быстрого алгоритма Шура длины = 2 достаточно () = 4 ячеек памяти, вещественных или комплексных взависимости от типа входных данных.Будем рассматривать реализацию алгоритма Шура для акселератораБПФ в форме антимашины Хартенштейна.Лемма 4 Количество операций чтения 1 (2 ) в рассматриваемой реализации быстрого алгоритма Шура удовлетворяет неравенствам 1 (2 )− ≤1 (2 ) ≤ 1 (2 )+ , где1 (2 )− = 1.25 · 2 2 + 7.25 · 2 ,1 (2 )+ = 1.25 · 2 2 + 9.75 · 2 .Лемма 5 Количество операций чтения (2 ) на критическом путив реализации быстрого алгоритма Шура удовлетворяет неравенствам (2 )− ≤ (2 ) ≤ (2 )+ , где (2 )− = 13 · 2 − 2 − 4, (2 )+ = 17 · 2 − 2 − 4.Лемма 6 Пусть = 2 и конвейер имеет длину .

Тогда время исполнения быстрого алгоритма Шура 2 () для вещественных данных на 2−+процессорах удовлетворяет неравенству 2() ≤ 2 () ≤ 2(), где−2() = 2− (13 · 2 − 1.5 + 1.252 − 1.25 2 − 7.75)+( − 1)(13 · 2 − 2 − 4),+2() = 2− (17 · 2 − 1.5 + 1.252 − 1.25 2 − 2.75)+( − 1)(17 · 2 − 2 − 4).В качестве примера был проведен анализ оптимального параллелизмаи типа памяти акселератора БПФ при вычислении адаптивного линейногофильтра эхоподавления на 4096 отсчетов в реальном времени.Были получены оценки мощности с помощью закона Амдала и прямойоценки времени работы при данном параллелизме .

Обе оценки хорошо согласуются друг с другом. Минимальное значение мощности достигается при14использовании однопортовой памяти и = 4, что приводит к уменьшениюпотребляемой мощности на 27%.В заключении приведены основные результаты работы, которые заключаются в следующем:1. Разработан метод качественной оценки мощности и выбора оптимального параллелизма для энергоэффективных специализированных КМОПвычислительных блоков для параллельных вычислений.2. Разработан метод вычисления элементарных функций при помощи почти гладкого четырехзвенного квазисплайна и оценка точности полиномиальной аппроксимации с коэффициентами с фиксированной точкой,ограниченной на равномерной сетке.3. Доказана теорема о размещении данных БПФ в многобанковой памятипри вычислении по произвольным смешанным основаниям.4. Доказана теорема о размещении данных и порядке вычисления самосортирующегося БПФ.5. Доказана теорема о размещении данных и порядке вычисления БПФдля однопортовой памяти.6.

Проведен анализ энергоэффективности алгоритма факторизации вещественных тёплицевых матриц на сверточном акселераторе для задачиэхокомпенсации при помощи быстрого алгоритма Шура.Публикации автора по теме диссертации1. Салищев С.И. Вычислительные аспекты компенсации акустическогоэха // Гироскопия и навигация. 2005. № 1. с. 90.2. Салищев С.И. Быстрый алгоритм Шура в задаче подавления акустического эха // Вестник молодых ученых.

Серия: прикладная математика и механика. 2005. Т. 3. С. 77–87.3. Салищев С.И. Кусочно-полиномиальная аппроксимация с сокращенными таблицами и гарантированной точностью // Компьютерныеинструменты в образовании. 2012. № 5. С. 3–10.4. Салищев С.И. Шеин Р.Е. Новые алгоритмы для конвейерного вычисления БПФ по смешанному основанию без копирования на многобанковой памяти с произвольным доступом // Компьютерные инструменты в образовании.

2013. № 2. С. 18–30.155. 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/elib/browse.cfm?elib=11191.6. Salischev S. Computational aspects of real-time acoustic echo cancellation //7th international conference: Computer data analysis and modeling. Vol. 2.2004. P.

146–149.7. Салищев С.И. Ушаков Д.С. Использование языков и сред управляемогоисполнения для системного программирования // Системное программирование. 2009. Т. 4. С. 198–216.8. The Moxie JVM experience. Technical Report TRCS-08-01: Tech. Rep.: /S. I. Salishev, S. M. Blackburn, M. Danilov et al.: Australian NationalUniversity, Department of Computer Science, 2008. Jan.9. Demystifying Magic: High-level Low-level Programming / S.

I. Salishev,D. Frampton, S. M. Blackburn et al. // Proceedings of the 2009 ACMSIGPLAN/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.10. Static analysis method for deadlock detection in SystemC designs / S. Salishev, M. Moiseev, A. Zakharov et al. // System on Chip (SoC), 2011International Symposium on. 2011.

Oct. P. 42–47.11. Salishev S., Glukhikh M., Moiseev M. A Static Analysis Approach for Verification of Synchronization Correctness of SystemC Designs // Proceedingsof 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.12. Salishev S. Continuous-flow conflict-free mixed-radix fast fourier transformin multi-bank memory. 2014.

jul. WO Patent App. PCT/IB2013/000,446.URL: http://google.com/patents/WO2014108718A1.16.

Характеристики

Список файлов диссертации