Диссертация (1150736), страница 16
Текст из файла (страница 16)
Формула получается транспонированием выражения из теоремы4.Следствие 3 Пусть = ( , . . . , 0 ) — набор натуральных чисел и =∏︀∏︀.Длякаждого=0,...,определим==0=0 . Тогда(︃ℱ = −1∏︁)︃̂︀ , ,=0̂︀ , матрицы с меньшими индексами стоят слегде в произведении матриц ва,̂︀ , = −1 ̂︁ (/ ⊗ ℱ ) ,0 ≤ ≤ ,̂︁ определяются раматрицы перестановок и диагональные матрицы венствами = / ⊗ ,̂︁ = / ⊗ .Доказательство. Из определения матрицы ℱ следует, что она симметрична: ℱ = (ℱ ) . Заключение следствия получается транспонированием формулы в утверждении теоремы 4 и подстановкой очевидных равенств −1 = −1 , ( ) = и ( ) = .В следующей теореме представлена формула алгоритма БПФ в частотной области, в которой порядок выполнения стадий задан основаниями0 , .
. . , .Теорема 5 Пусть = ( , . . . , 0 ) — набор натуральных чисел и =∏︀∏︀=0 . Для каждого = 0, . . . , определим == . Тогдаℱ = ∏︁=092̃︀ , ,̃︀ , матрицы с меньшими индексами стоят спрагде в произведении матриц ва,̃︀ , = −1 ̃︁ (/ ⊗ ℱ ) ,0 ≤ ≤ ,̂︁ определяются раматрицы перестановок и диагональные матрицы венствами = / ⊗ ,̃︁ = / ⊗ .Доказательство.
Определим = ⋆ = (0 , . . . , ), так что = −при 0 ≤ ≤ . Тогда −1 = ⋆ = и в обозначениях следствия 3: =∏︁=0− =∏︁ = − ,0 ≤ ≤ .=−̂︁ = ̃︁− , = − и, следовательно, ̂︀ , = ̃︀ −, .Отсюда Цифровое представление индексов входного сигнала БПФ, согласованноес алгоритмом из теоремы 5, определяется мультииндексом ⋆ со старшимиразрядами, соответствующими основанию 0 . Результат БПФ получается сцифровым представлением индексов, записанным в системе счисления, по̃︀ , в алгоритме теоремы 5 нарождённой мультииндексом . Стадии БПФ чинаются с обработки старших разрядов.Реализация БПФ в частотной области по теореме 5 умножение на комплексные экспоненты в диагональной матрице выполняются после ба̃︀ , .
Однако в целях повышения точности расчётовбочки на каждой стадии желательно вычислять бабочку после умножения, так как внутренняя памятьпроцессора имеет более длинную мантиссу. Такой порядок операций существенно повышает точность вычислений [75]. Кроме того, этот порядок вычислений позволяет использовать архитектурный шаблон рис. 3.2 для вычисления БПФ в частотной области. В следующем утверждении представленамодификация теоремы 5, в которой на каждой стадии БПФ сначала производится умножение, а затем бабочка.Пусть , , — натуральные числа. Определим диагональную матрицу,, размера = уравнениями(ℓ+),, (, ⊗ , ⊗ ℓ, ) = 93(, ⊗ , ⊗ ℓ, )при 0 ≤ < , 0 ≤ < , 0 ≤ ℓ < .Теорема 6 Пусть = ( , .
. . , 0 ) — набор натуральных чисел и =∏︀∏︀.Длякаждого=0,...,определим==0= . Тогдаℱ = ∏︁, ,=0где в произведении матриц , матрицы с меньшими индексами стоят справа,̃︀ ,, = −1 (/ ⊗ ℱ )0 ≤ ≤ ,̃︀ определяются раматрицы перестановок и диагональные матрицы венствами = / ⊗ ,̃︀ = / ⊗ , , ,+1+20 ≤ ≤ ,с доопределением +1 = +1 = +2 = 1.Доказательство. В формуле БПФ из теоремы 5 между соседними бабочками (/+1 ⊗ ℱ+1 ) и (/ ⊗ ℱ ) при 0 ≤ ≤ −1 стоит произведение+1̃︁ = (/ ⊗ = +1 −1 +1 )(/ ⊗ +1 )(/ ⊗ ).+1̃︀ +1 −1 , после чего утверждение теоремы получаетсяДокажем, что = ̃︀ ,перераспределением множителей в формуле для ℱ . При = стадия не содержит умножения на комплексные экспоненты, так как = и = — единичная матрица.Пусть 0 ≤ ≤ − 1. По свойствам произведения Кронекера и по лемме 5̃︁ = / ⊗ ( ) = / ⊗ ( )−1 +1+1 +1−1= (/ ⊗ )(/ ⊗ +1 ) = (/ ⊗ +1 ) .+1Поскольку общий множитель / в произведениях Кронекера можно вынести за скобки, то остаётся доказать, что+1+1( ⊗ +1 )+1 = +1 , ,−1 ( ⊗ +1 ).94Пусть 0 ≤ +2 < +2 , 0 ≤ < , 0 ≤ +1 < +1 .
Тогда0 ≤ +1 +2 + +2 < +1 , и поэтому компоненты левой части данногоуравнения есть+1( ⊗ +1 )+1 ( , ⊗ (+1 ,+1 ⊗ +2 ,+2 )) (+1 +2 ++2 )= (+1 +2 ++2 )= +1( , ⊗ +1 (+1 ,+1 ⊗ +2 ,+2 ))( , ⊗ +2 ,+2 ⊗ +1 ,+1 )= ,+1 ,+2 ( , ⊗ +2 ,+2 ⊗ +1 ,+1 )+1= ,+1 ,+2 ( ⊗ +1 )( , ⊗ (+1 ,+1 ⊗ +2 ,+2 )),что завершает доказательство.3.1.6Реализация круговой свёрткиПри реализации алгоритма круговой свёртки сначала выполняется прямоеДПФ, затем покомпонентное умножение и затем обратное ДПФ. В этом случаепрямое ДПФ выполняется в частотной области, а обратное ДПФ — во временной области, а перестановки инверсии друг друга сокращают и могут бытьудалены из алгоритма расчёта.Как известно, ДПФ является унитарным преобразованием с точностью домножителя:1 *11ℱ = ℱ = ℱ ,где черта сверху обозначает комплексное сопряжение.
Введём операцию поℱ−1 =−1компонентного умножения векторов: . * = = ( )=0 , если = ,−1 −1где = ( )=0 , = ( )=0 .Теорема 7 Пусть = ( , . . . , 0 ) — набор натуральных чисел и =∏︀ −1 −1=0 . Пусть = ( )=0 — круговая свёртка векторов = ( )=0 и−1 = ( )=0 .Определим матрицы , и ,⋆ , как в теоремах 4 и 6. Тогда=(︃ 1 ∏︁)︃, (. * ),=095где(︃=∏︁)︃,⋆, =(︃ ∏︁)︃,⋆=0=0и во всех произведениях множители с меньшими индексами стоят справа.Доказательство. Определим = ⋆ = ( , . . . , 0 ) = (0 , . . . , ). Тогдапо теореме 6 результат ДПФ от вектора естьℱ = (, · · · 0, ) = ,и аналогично, ℱ = . Оператор перестановки , очевидно, обладает свойством дистрибутивности относительно покомпонентного произведениявекторов:( ).
* ( ) = (. * ).Поскольку круговая свёртка соответствует покомпонентному произведениюпреобразований Фурье, то = ℱ−1 [(ℱ ). * (ℱ )] = ℱ−1 (. * ) =1ℱ (. * ).Подставляя формулу БПФ из теоремы 4, получим=1, · · · 0, (. * ),что совпадает с заключением теоремы, так как ⋆ = −1 .В формуле из теоремы 7 векторы, поступающие на вход как прямого БПФ,так и обратного БПФ, записаны в цифровом представлении, порождённоммультииндексом .
Однако порядок выполнения стадий разный: начиная состарших разрядов во внутренних БПФ и начиная с младших разрядов во внешнем БПФ.3.2Организация многобанковой памятиПредположим, что БПФ требуется реализовать с памятью, количество ячеек которой совпадает с количеством входных данных. Кроме того, ячейки разбиты на банки памяти, которые устанавливают дополнительные ограниченияна чтение и запись.96Рассмотрим более детальный архитектурный шаблон рис. 3.3, отражающий наличие многобанковой двухпортовой памяти.CARR0MRExpW0MWAWW1R1IRMulFIW......RNWNРис. 3.3: Архитектурный шаблон блока потокового вычисления БПФ c 1r1wпамятью.Здесь - счетчик, - блок вычисления комплексных экспонент, , - генераторы адресов чтения и записи, , - порты чтения и записи, - векторный комплексный умножитель, - блок вычисления бабочки, , - генераторы номеров банков, , - управляемые коммутаторы, - конвейер.Модифицируем алгоритм БПФ для реализации на архитектурном шаблонерис.
3.3.3.2.1Постановка задачиРассмотрим алгоритм БПФ на =∏︀−1=0 точек, причём — порядокбабочки на стадии с порядковым номером . Пусть — наименьшее общеекратное набора чисел ( )−1=0 , так что = / — целые числа.Предположим, что за один такт процессор выполняет бабочки с общимколичеством крыльев . Это значит, что на –й стадии одновременно выполняются бабочек, каждая порядка .
Кроме того, все данные хранятся в 97ячейках, распределённых по банкам памяти. Каждый банк памяти за одинтакт может выполнить только одну операцию чтения и одну операцию записи.Требуется распределить входные данные по банкам памяти таким способом, чтобы на каждом такте процессор был загружен полностью и обрабатывал отсчётов. Для этого, очевидно, на каждом такте входные отсчёты всехбабочек должны находиться в разных банках, а результаты должны записываться в те же ячейки, откуда отсчёты считывались. Требование отсутствияконфликтов эквивалентно гомогенности синхронного графа потока данных вопределении архитектурного шаблона.Основные частные случаи — это одинаковые основания бабочек, = при всех , а также случай = −1 , где число делит .
В последнемслучае алгоритм принято называть БПФ по основанию /. Широко распространён алгоритм Radix-2, в котором = 2, а также алгоритм Radix-4 пооснованию 2/4.Результат каждой бабочки записывается по тем же адресам, из которыхбыли взяты чисел, и в стандартном порядке, определяемым показателямикомплексных экспонент в множителях . Входной массив чисел длины надо распределить по банкам таким способом, чтобы на каждой стадии в одновременно выполняемых бабочках участвовало ровно по одному отсчёту изкаждого банка.
Ситуация, в которой это не так, называется конфликтом. Требуется найти распределение входного массива чисел, при котором отсутствуютконфликты на всех стадиях.Решение данной задачи известно при = [6]. В [7] сформулированалгоритм распределения без конфликтов для БПФ по основанию 2/4.В [76] сформулирован алгоритм для произвольных смешанных основанийс запуском одной бабочки за такт, что не полностью использует пропускнуюспособность памяти.В данном разделе сформулирован и доказан алгоритм распределения безконфликтов для произвольного набора ( )−1=0 делителей числа с максимальным использованием пропускной способности памяти.Пусть — номер отсчёта во входном массиве чисел. Распределение по банкам памяти определяется номером банка () и номером ячейки () внутрибанка.98На каждой стадии с номером выполняется несколько бабочек.
Упорядочим эти бабочки по номеру крыла с единичным множителем. Последовательность выполнения бабочек обозначим набором целых чисел (), где — порядковый номер операции, а () — номер бабочки, обрабатываемой наэтой операции.Для обеспечения необходимого темпа параллельных вычислений вычислительный блок имеет внутренний конвейер длиной . Первой операцией будетчтение, последней – запись. Длина конвейера — количество тактов выполнениябабочки, не включая запись.
Запись не включается, поскольку она перекрывается с чтением по времени для обеспечения максимальной производительности. При этом одновременное чтение и запись в одном такте одной ячейкипамяти выдает корректный результат.Если операции чтения и записи не перекрываются, максимальный темпвычислений падает в два раза до одной бабочки в два такта.3.2.2Акселератор БПФ по смешанному основанию с 1r1wпамятьюПредположим, что алгоритм БПФ последовательно выполняет бабочки по∏︀рядков 0 , 1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
