Диссертация (1150736), страница 18

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

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

Таким образом, все отсчёты берутся из разных банковпамяти и количество этих отсчётов равно .3.2.3Акселератор БПФ по смешанному основанию с 1rw памятьюМодифицируем архитектуру из раздела 3.2.2 для использования 1rw памяти, в которой чтение и запись в один банк памяти не могут производитьсяза один такт. Для этого задействуем 2 банков памяти и потребуем, чтобызапись и чтение осуществлялись в непересекающиеся множества банков.Рассмотрим архитектурный шаблон рис.

3.5, отражающий наличие многобанковой однопортовой памяти.107Рис. 3.4: Архитектура блока потокового вычисления БПФ с 1rw памятью.CARWRW0MRExpMWRW1IRMulFPIW...RW2NРис. 3.5: Архитектурный шаблон блока потокового вычисления БПФ c 1rwпамятью.108Здесь - счетчик, - блок вычисления комплексных экспонент, - генератор адресов чтения и записи, - порты чтения/записи, - векторный комплексный умножитель, - блок вычисления бабочки, , генераторы номеров банков, , - управляемые коммутаторы.Модифицируем алгоритм БПФ для реализации на архитектурном шаблонерис. 3.5.Теорема 10 Пусть длина конвейера нечетна, mod 2 = 1.

Рассмотримследующий порядок обхода и функцию распределения индексов по банкам:{︃(), = 0,2 () =, > 0,[︃(︃ −1)︃]︃∑︁( 0 ) = . . . , + ¯1 + ¯1mod ,)︃(︃ (︃ −1=2∑︁2 () = 2 + 0 − (0)︃mod 2)mod 2.=1Такой выбор порядка обхода и функции распределения по банкам обеспечивает отсутствие конфликтов для архитектуры потокового БПФ акселератора с 2 банками 1rw памяти при выполнении одной бабочки за такт.Доказательство. Пусть — номер стадии по основанию . За один тактобрабатывается ровно одна бабочка. Старший разряд номеров всех отсчётоводной бабочки одинаковый. Чётность этого разряда определяет группу из банков памяти, из которых производится считывание на данном такте.

Старший разряд вместе с группой из банков памяти меняются на каждом тактев соответствии с определением () и разложения номера в системе счисления, порождённой мультииндексом ⋆ . Поскольку длина конвейера нечётна,то на каждом такте записать результатов ”на месте” осуществляется не в тугруппу банков, из которой производится считывание. Поэтому не происходитконфликта памяти между операциями считывания и записи.Для того чтобы номера банков двух отсчётов совпадали, 2 () = 2 (ℓ)требуется, чтобы совпадали номера () = (ℓ) из теоремы 9 и, кроме того,чтобы совпадала чётность младшей компоненты в системе счисления, порождённой мультииндексом ⋆ .109На стадии по основанию порядок обхода бабочек тот же, что и в теореме9.

Следовательно, конфликта памяти при считывании не возникает по теореме9.На каждой стадии один элемент памяти участвует только в одной бабочке.Младшим разрядом номера бабочки является число 0 , определяющеечётность номера банка памяти. Чётность номера такта совпадает с чётностьюномера банка памяти в операции считывания. Если запаздывание по записинечётное, то операция записи выполняется в банки памяти с противоположнойчётностью.

Отсюда не возникает конфликта операций считывания и записи.3.3Самосортирующиеся БПФИнверсия индексов в алгоритме БПФ требует дополнительного прохода по памяти. Поскольку точки с инвертированными индексами могут лежатьв одном банке памяти, то из-за конфликтов обращения к памяти время этого прохода равно времени выполнения двух стадий БПФ. При этом во многихалгоритмах, использующих БПФ, задействовать на этом проходе вычислительные блоки невозможно.

Такой простой не является энергоэффективным, и егожелательно избегать.Для решения этой проблемы существует класс самосортирующих алгоритмов БПФ, не требующих явного шага инверсии индексов. Для этого была разработана модификация самоcортирующего алгоритма Джонсона-Буруса [8]. Валгоритме БПФ Джонсона-Буруса стадия по малому основанию выполняетсяпосредине. С точки зрения потоковой архитектуры этот алгоритм может бытьпредставлен следующим образом:ℱ =−1∏︁ ,=0где — матрицы стадий, определяемые как⎧⎪−1⎪0 (/ ⊗ ℱ )0 ,⎪⎪⎨ −1 (/ ⊗ ℱ ) , =−1⎪+1 −1⎪ (/ ⊗ ℱ ) ,⎪⎪⎩ ˆ−1 (/ ⊗ ℱ ) ˆ ,110 = 0,0 < < ⌊ +12 ⌋,⌊ +12 ⌋ ≤ < − 1, = − 1,и — перестановка двух цифр и−1 = ( )−1 .⌊ +1= ,2 ⌋Половина стадий не вычисляется на месте. Однако если рассматриватьгруппы бабочек по элементов, то они выполняются на месте.

Для отсутствия конфликтов предшествования между бабочками в одной группе достаточно, чтобы внутренний конвейер вычислительного блока удовлетворял условию ≥ − 1.В данном разделе излагается обобщение алгоритма Джонсона-Буруса наБПФ с выполнением малой стадии в начале.3.3.1Акселератор самосортирующего БПФ с 1r1w памятьюДля реализации этого алгоритма на архитектурном шаблоне рис. 3.2 достаточно изменить функции адресации и увеличить длину внутреннего конвейера.Лемма 12 Пусть и — квадратные матрицы, и матрицы = ⊗ , = ⊗ имеют одинаковый размер .Тогда если делится на , то = .Доказательство.

Размер матрицы обозначим , а размер матрицы —ℓ. Из условия следует, что = = ℓ. По условию, = / — целоечисло. Отсюда= ,Поэтому = ℓ ⊗ и = ⊗ и=== ℓ. = (ℓ ⊗ ( ⊗ ))( ⊗ ( ⊗ )) = ⊗ ⊗ , = ( ⊗ ( ⊗ ))(ℓ ⊗ ( ⊗ )) = ⊗ ⊗ .Пусть = −1 и последовательность стадий БПФ определяется мультииндексом = (−1 , . .

. , 0 ),0 = ,111 = ,1 ≤ ≤ −1,так что малая стадия по основанию = / выполняется в начале. В алгоритмах БПФ как во временной, так и в частотной области, индексы компонентвходного массива записываются в системе счисления, порождённой мультииндексом ⋆ = (, , . . . , ).По теореме 6 алгоритм БПФ в частотной области описывается формулойℱ = −1, −2, · · · 0, ,где — перестановка компонент вектора в соответствии с инверсией мультииндекса .

Цель самосортирующегося алгоритма состоит в замене начальнойперестановки на постепенные частные перестановки на каждой стадии, осуществляемые при минимальной длине конвейера.Введём оператор перестановки начальной и конечной цифр в индексе произвольного вектора.

Пусть вектор имеет длину и число делится на 2 ,где ≥ 1. Тогда матрица перестановки определяется уравнениями (, ⊗ ℓ,/2 ⊗ , ) = , ⊗ ℓ,/2 ⊗ , ,0 ≤ , < ,0 ≤ ℓ < / 2 .Теорема 11 Пусть = −1 , где = . Определим матрицы перестановок⎧⎪,⎪⎪⎪⎨ −1 ⊗ ⊗ −−1 , =⎪/2−1 ⊗ ⎪ ⊗ /2−1 ,⎪⎪⎩2+1−−−1 ⊗ [(2− ⊗ )] ⊗ −−1 , = 0,1 ≤ ≤ ⌊ −12 ⌋, = 2 ,⌈ +12 ⌉ ≤ ≤ − 1.Тогдаℱ = −1 · . .

. · 0 ,где = , .Доказательство. При ≥ 1 из определения следует, что = − и/ = −1 . Матрицу , можно преобразовать к виду, = −1 ⊗ , = [+1 (−1 ⊗ ℱ ) ,+1 ,+2 ].Докажем, что , = , при 0 ≤ < ≤ −1. Пара матриц −1 ⊗ и ⊗−−1 при любой матрице размера удовлетворяет условиям леммы12, так как число−1 · −−1 = −1+(−−1)112делится нацело на = −1 . Поэтому произведение пары матриц −1 ⊗ и ⊗ −−1 перестановочно. Матрицы имеют вид ⊗ −−1 при любом, поэтому , = , при 0 ≤ < ≤ − 1.

Отсюда−1 · . . . · 0 = −1 −1, −2 −2, · . . . · 1 1, 0 0,= (−1 −2 · . . . · 0 ) · (−1, · 0, ) = (−1 −2 · 0 )−1 ℱпо теореме 6. Остаётся доказать, что−1 −2 · . . . · 0 = .Все входящие в эту формулу матрицы осуществляют перестановки элементов векторов, а произведению матриц соответствует композиция перестановок. Поэтому достаточно доказать, что композиция перестановок индексов влевой части приводит перестановки инверсии индексов .Входной вектор БПФ имеет длину = −1 . В дальнейшем числа от0 до − 1 будем представлять в разных системах счисления, порождающиемультииндексы которых содержат только числа или = /. При этом обозначение компоненты ¯ с одной верхней чертой будет означать, что соответствующая компонента порождающего мультииндекса равна , а обозначение¯ с двумя верхними чертами — что равна .Пусть индекс элемента некоторого вектора длины имеет цифровоепредставление0 = (¯0 ,¯1 , ¯1 , .

. . ,¯−1 , ¯−1 ).Изобозначений(, , , . . . , , ).Вследует,чтопорождающийсистемесчисления,мультииндекспорождённойестьмультииндексом⋆ = (, , . . . , ) этот же индекс имеет представление ⋆ = (0 , 1 , . . . , −1 ),где 0 = ¯0 и = ¯ + ¯ при 1 ≤ ≤ − 1.Пусть = ⌊(−1)/2⌋. Преобразования ( ·. . .·0 ) сводится к замене индекса, цифровая форма которого есть 0 , на индекс, цифровая форма которогоесть1 = (¯0 , ¯1 ,¯1 , . . . , ¯ ,¯ ,¯+1 , ¯+1 , . . .

,¯−1 , ¯−1 ).1. Пусть число нечётное. Тогда в векторе 1 первые пар имеют вид(¯− , ¯−+1 ) при = , −1, . . . , 1. Затем в векторе 1 следует число ¯ ,затем ещё пар вида (¯+ , ¯+ ) при = 1, . . . , .113Преобразование + при = 1, . . . , сводится к следующей перестановке в цифровой форме индексов:(. . .

,¯− , ¯−+1 , . . . ,¯+ , ¯+ , . . .) → (. . . ,¯+ , ¯+ , . . . , ¯−+1 ,¯− , . . .),где многоточием отмечены цифры, которые не меняются при перестановке. Врезультате преобразование (−1 · . . . · +1 ) переставляет цифровую запись1 к виду2 = (¯−1 , ¯−1 , . . . ,¯+1 , ¯+1 ,¯ , ¯ ,¯−1 , . . . ,¯1 , ¯1 ,¯0 ),что в системе счисления, порождённой мультииндексом , имеет цифровоепредставление (−1 , .

. . , 1 , 0 ), являющееся инверсией входного цифровогопредставления ⋆ . Поэтому −1 · · · 0 = .2. Пусть число чётное. Тогда +1 = /2 и оператор /2 выполняетследующее преобразование цифровой формы индексов:(. . . ,¯ ,¯+1 , ¯+1 , . . .) → (. . . ,¯+1 , ¯+1 ,¯ , . . .).Многоточием отмечены цифры, не меняющиеся при перестановке. С левойстороны это пар цифр вида (¯− , ¯−+1 ) при = , −1, . . . , 1.

С правойстороны это пар цифр вида (¯+ , ¯+ ) при = 1, . . . , . Как и в случае нечётного , операция + переставляет эти пары цифр и инвертируетпорядок в правой паре. В результате снова получается вектор 2 .Последовательность выполнения бабочек на каждой стадии определяетнеобходимый объём внутренней памяти и длину конвейера. Последовательность выполнения бабочек в самосортирующемся алгоритме должна быть изменена для избежания конфликтов при обращении к памяти.Пусть = (−1 , . .

. , 1 , 0 ) = (, . . . , , ) — мультииндекс, указывающий на последовательность выполнения стадий БПФ, начиная со стадии сбабочками по основанию 0 = и до стадии с бабочками по основанию−1 = . В соответствии с теоремой 6, номера элементов входного векторазаписываются в системе счисления, порождённой обратным мультииндексом⋆ = (, , .

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

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

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