Диссертация (1150736), страница 19
Текст из файла (страница 19)
. , ¯−1 ,¯−1 )в системе счисления, порождённой мультииндексом = (, , , . . . , , ). Навход каждой бабочки подаётся набор отсчётов, у номеров которых все компоненты ¯ и ¯ одинаковые, кроме компонент (¯ ,¯ ), которые пробегаютвсе возможные значения. Поэтому естественным номером бабочки является = ( )0 , где 0 = (, , , . .
. , , ) короче вектора на две компоненты и = (¯0 , ¯1 ,¯1 , . . . , ¯−1 ,¯−1 , ¯+1 ,¯+1 , . . . , ¯−1 ,¯−1 ).Номер такта, на котором выполняется бабочка на стадии с номером =( )0 , обозначим ().Операция состоит в инвертировании пары (¯−1− , ¯− ) и перестановкеполученных компонент с парой (¯ ,¯ ).
Определим операцию перестановкиэтой пары в конец мультииндекса номера бабочки = ( )0 : ( ) = (¯0 , ¯1 , . . . , ¯−1− ,¯− , . . . , ¯−1 ,¯−1 , ¯+1 ,¯+1 , . . . , ¯−1 ,¯−1 , ¯− ,¯−1− )при ≥ (+1)/2.Если число чётное и > 2, то операция при = /2 состоит вперестановке:(¯−1 ,¯ , ¯ ) → (¯ , ¯ ,¯−1 ).Поэтому определим перестановку в цифровом представлении номера бабочки: ( ) = (¯0 , ¯1 , . . . , ¯−2 ,¯−2 , ¯+1 ,¯+1 , .
. . , ¯−1 ,¯−1 , ¯−1 ,¯−1 ).Теорема 12 Пусть > 2 и функция распределения входного вектора по банкам данных () определяется теоремой 9. Порядок обхода бабочек на -йстадии БПФ зададим номером такта () реализации бабочки с номером = ( )0 : () =⎧ ⌊︁ ⌋︁⎪⎪⎨ , = 0,,1 ≤ ≤ ⌊ −12 ⌋,⎪⎪⎩ ( )0 , ⌊ +1 ⌋ ≤ ≤ − 1.2115Предположим, что длина конвейера удовлетворяет условию ≥ − 1.Тогда такой выбор порядка обхода и функции распределения по банкамобеспечивает отсутствие конфликтов при работе самосортирующего алгоритма для архитектуры потокового БПФ акселератора с банками 1r1wпамяти при выполнении одной бабочки размера или бабочек размера затакт.Доказательство.
Начальная стадия 0 = 0, та же, что и в теореме 9.Поэтому она не вызывает конфликтов даже без конвейера. Бабочки остальныхстадий БПФ имеют размер , и поэтому все элементы входного одной бабочки находятся в разных банках памяти. Требуется доказать, что на каждойстадии запись результатов бабочек в каждую ячейку памяти происходит послесчитывания из этой ячейки на этой стадии.В стадиях = , при 1 ≤ ≤ ⌊(−1)/2⌋ перестановка меняеттолько индекс , который не входит в номер бабочки. Поэтому эти стадиитакже выполняются на месте и не вызывают конфликта по обращению к памяти даже без конвейера.Пусть ( + 1)/2 ≤ ≤ − 1.
Разобьём все бабочки –й стадии на последовательные группы по штук в соответствии с порядковыми номерами ().Тогда в каждой группе обрабатываются все бабочки, в номерах которых компоненты ¯− , ¯−1− пробегают все возможные значения, а остальные компоненты цифрового представления фиксированы. По определению перестановки , именно в этот набор ячеек памяти записываются результаты обработкигруппы из бабочек. При длине конвейера ≥ −1 запись происходит послесчитывания.Если число чётное и = /2, то группа из бабочек определяется компонентами ¯−−1 ,¯−1− , которые пробегают все возможные значения.
Важно,что порции по бабочек, определяемые компонентой ¯−1− , обрабатываются полностью для каждого значения ¯−−1 . Именно в память, считываемую вбабочках этих малых порций, происходит запись результата в соответствии сопределением операции /2 .1163.4Результаты прототипированияПрототипирование показало, что при использовании регистрового файла сшириной 16 бит на вещественное значение и вычислительного блока с размером бабочки 4 площадь памяти составляет при размере 128 Кибит порядка80% площади акселератора.
Изменение адресной арифметики для использования двухпортовой памяти не меняет существенно площадь вычислительногоблока. Таким образом, уменьшение площади памяти в 2 раза за счет использования статической двухпортовой памяти позволяет уменьшить площадь акселератора на 40%, а уменьшение в 6 раз за счет использования встроеннойдинамической памяти на 67%, при пропорциональном уменьшении статического энергопотребления. Был проведен синтез виртуальной топологии длямалопотребляющего процесса производства полупроводниковых кристалловс геометрическими нормами 22 нм.117Глава 4Ускорение решенияуравнений Юла–УокераВ данной главе будет рассмотрено аппаратное ускорение решения уравнений Юла–Уокера на основе быстрого алгоритма Шура с использованиемаппаратного блока вычисления БПФ.Сначала описывается прикладная задача, в которой быстрое обращениетёплицевых матриц имеет большое значение.4.1Подавление дальнего эха с помощью линейного фильтра с длинной импульсной характеристикойВ системах конференцсвязи терминал имеет и микрофон, и динамик; динамик воспроизводит речь удаленного диктора, а микрофон принимает какречь локального диктора так и сигнал из динамика.
Таким образом, возникаетположительная обратная связь.При этом окружение диктора обычно создает акустическое эхо. Различают ближнее эхо, создаваемое локальным окружением диктора, и дальнее эхо,возникающее при воспроизведении речи диктора на удаленном терминале.Ближнее эхо является допустимым, дальнее эхо участвует в формированииобратной связи и должно быть скомпенсировано.118Для компенсации дальнего эха обычно используется многополосный адаптивный эквалайзер. Поскольку эквалайзер не учитывает фазы сигнала, то возникает эффект полудуплекса, когда речь говорящего невозможно прервать, поскольку голос локального диктора подавляется эквалайзером.Для того чтобы избежать этого эффекта, требуется точно оценить передаточную функцию эха, для обеспечения передачи голоса локального дикторабез искажений.В данной работе используется модель эхоподавления при помощи внутренней отрицательной обратной связи, как изображено на рис.
4.1.ewz-m-H(z)A(z)yz-k’z-kw'z-m’-H’(z)A’(z)Рис. 4.1: Модель эхоподавленияЗдесь - сигнал локального диктора, - эхосигнал, - сигнал с удаленноготерминала. () - передаточная функция фильтра эхоподавления, () - передаточная функция фильтра, моделирующего акустическую обратную связь.Передаточная функция () неизвестна, − - задержка вывода звука на отсчетов, − - задержка канала передачи данных.Предполагается, что сигналы и некоррелированны. В этом случаеоптимальный фильтр равен и, таким образом, компенсирует обратнуюсвязь.Обозначим = + - сигнал с микрофона.119В стандартной задаче синтеза оптимального фильтра требуется по задан−1 −1ным последовательностям = (())=0 и = (())=0 , а также числу ≪ найти такую последовательность чисел ℎ = (ℎ )−1=0 , что достигаетминимума функционал качества(ℎ) =∑︁+−1|() − (ℎ * )()|2 ,=0где ℎ * обозначает свёртку, а значения () и () при < 0 или ≥ считаются нулевыми.Если и являются выборочными реализациями стационарного случайного процесса, то оптимальная последовательность ℎ близка при больших к импульсной характеристике оптимального линейного фильтра.Задача решается по методу наименьших квадратов.
Вектор ℎ определяетсяиз уравнения ℎ = ,−1где матрица = ( ),=0и вектор = ( )−1=0 имеют компоненты −11 ∑︁()( − + ), = =0 −11 ∑︁ =()( − ). =0Для эргодических процессов выборочная матрица стремится к автокорреляционной матрице, а вектор — к значениям кросс-корреляции между и. В этом случае синтезированный фильтр можно применять для оцениванияпроцесса по и в следующие моменты времени, то есть, при > .При малых задача легко решается обращением матрицы . Однако прибольших значениях сложность нахождения вектора коэффициентов фильтраℎ и вычисления свёртки ℎ * становится определяющей для возможностирасчёта в реальном времени.Для обращения матрицы используется быстрый алгоритм Шура [9] дляфакторизации −1 на основе БПФ.
Для свертки используется алгоритм Гарднера [77], также на основе БПФ.1204.2Обращение тёплицевой матрицы при помощимногочленов Сегё и ШураВ этом разделе излагаются основные основные математические результатыоб обращении тёплицевых матриц [9,10], которые потребуются в дальнейшемдля подсчёта сложности алгоритмов и их ускорения.4.2.1Многочлены Сегё и факторизация обратной матрицык тёплицевойТребуется быстро решить линейное уравнение = 0 относительно = ( )=0 ∈ R+1 , в котором 0 = (1, 0, .
. . , 0)* — первый орт, а квадратная матрица тёплицева,⎛0 12⎜⎜ 1 01⎜⎜ = ⎜ 2 10⎜....⎜ ..⎝ −1 −2···⎞⎟. . . −1 ⎟⎟⎟. . . −2 ⎟ ... ⎟.... ⎟⎠· · · 0В приложениях эта матрица обычно невырождена и положительно определена. В частности, так происходит, когда числа ( )=0 являются значениямикорреляционной функции некоторого регулярного стационарного процесса. Вэтом случае есть решение уравнения Юла–Уокера. При малых размерностях это решение можно вычислить обычным методом Левинсона–Дурбина, чтои выполняется при кодировании речи в мобильных телефонах. В частности, = 10 в стандарте GSM.В дальнейшем для краткости формул будем предполагать, что 0 = 1. Любая тёплицева матрица сводится к этому случаю умножением на −10 .При уменьшении размерности в уравнении достаточно произвести усечение матрицы и уменьшить размерность 0 . Усеченную матрицу размерности + 1 будем обозначать , а усеченную правую часть — вектором 0, .Предположим, что 0 ̸= 0 при всех , и обозначим = 0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
