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

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

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

, . Длина входного массива есть = =0 . Память разделена на банков памяти и число есть наименьшее общее кратное оснований ( )=0 . На каждом такте вычисляется одна или несколько бабочек сзаписью результата в тех же ячейках памяти, из которых были считаны исходные данные для выполнения бабочек.Требуется найти распределение входных данных по банкам (), при котором на каждом такте выбирается ровно по одному отсчёту из каждого банка, а также все наборы одновременно выполняемых бабочек на стадии , если < .Далее наибольший общий делитель произвольного набора натуральных чисел ( )=0 обозначим (( )=0 ), а наименьшее кратное набора —(( )=0 ). По определению, = (( )=0 ).Пусть в алгоритме БПФ последовательно выполняются стадии по основаниям 0 , 1 , . .

. , . Если индексы входного массива имеют цифровое пред99ставление = , где = ( , . . . , 0 ), = ( , . . . , 0 ),и бабочка -й по порядку стадии БПФ содержит отсчёты, номера которыхотличаются только компонентой , то алгоритм БПФ назовём начинающимсяс младших разрядов мультииндекса .Если индексы входного массива имеют цифровое представление = с = (0 , . . . , ), = (0 , . . .

, )и бабочка -й по порядку стадии БПФ содержит отсчёты, номера которыхотличаются только компонентой , то алгоритм БПФ назовём начинающимсясо старших разрядов мультииндекса .Основной результат данного раздела представлен в следующей теореме.Теорема 8 Пусть в алгоритме БПФ последовательно выполняются стадиипо основаниям 0 , 1 , . .

. , . Если алгоритм БПФ начинается с младших разрядов, то определим = ( , . . . , 0 ) и цифровое представление номера компоненты входного массива = = ( , . . . , 0 ). Если алгоритм БПФначинается со старших разрядов, то определим = (0 , . . . , ) и цифровоепредставление номера компоненты входного массива = = (0 , . . . , ).∏︀Входной массив размерности = =0 записывается в банков данных, где = (0 , . .

. , ) — наименьшее общее кратное оснований бабочек.Для каждого = 0, 1, . . . , введём обозначения = (( )=0 ), =,−1, =,( , ), =,,−1,0 ≤ < ,с доопределением −1 = −1, = 1.Определим номер банка (), в который помещается элемент входногомассива с номером при = 0, 1, . . . , − 1, по формуле() =∑︁ =0где = и = / .100mod ,Определим набор бабочек, выполняемых одновременно. На стадии при0 ≤ ≤ одновременно выполняются все бабочки с номерами ℓ, в цифровом представлении которых совпадают следующие величины: целые части⌊ /, ⌋ при 0 ≤ < и целые части ⌊ / ⌋ при < ≤ .Тогда при выполнении алгоритма БПФ не возникает конфликтов памятии на каждом такте задействованы все банков памяти.Доказательство теоремы разделено на несколько вспомогательных утверждений, которые сформулированы и доказаны ниже.

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

Рассмотрим БПФ, содержащий бабочки типов ℱ иℱ . Такой алгоритм принято называть БПФ по основанию /. Следствиемиз теоремы 8 является следующее утверждение.На каждой стадии входным массивом каждой бабочки является набор отсчётов, цифровые представления которых отличаются только одной из компонент. Пусть это компонента . Тогда набор оставшихся компонент определяет номер бабочки ℓ внутри этой стадии следующим образом:ℓ = ( ) , = (−1 , . . . , +1 , −1 , . .

. , 0 ),где = (, . . . , , ) при 1 ≤ ≤ −1 и = (, . . . , ) при = 0.Теорема 9 Предположим, что в алгоритме БПФ по основанию / номеракомпонент входного вектора записаны в системе счисления, порождённоймультииндексом = (, . . . , , ) длины . Номер банка памяти () для101входного отсчёта с номером и номер такта (ℓ) выполнения бабочки ℓ настадии определим, как() =(︃ −1∑︁)︃ + 0mod ,⎧ =1⎨ ℓ,1 ≤ ≤ − 1,⌊︁ ⌋︁ (ℓ) =⎩ ℓ , = 0.Такой выбор порядка обхода и функции распределения по банкам обеспечивает отсутствие конфликтов для архитектуры потокового акселераторадля БПФ по основанию / с банками 1r1w памяти, независимо от того,начинается ли он со старших или с младших разрядов.Доказательство. Применим теорему 8.

Пусть БПФ начинается с младшихразрядов: 0 = и = при 1 ≤ ≤ − 1. Тогда 0 = / = и = 1при 1 ≤ ≤ − 1. Поэтому распределение по банкам памяти () такое же,как в теореме 8.Для расчёта номера такта выполнения бабочек заметим, что если длинабабочки на некоторой стадии есть , выполняется всего одна бабочка, поэтомуконфликта памяти не происходит.Пусть = 0. Из определения следует, что 0 = , 1 = / = и = 1при > 1. В соответствии с утверждением теоремы 8 одновременно выполняются бабочки, у которых совпадают целые части ⌊1 /⌋ и все числа при ≥ 2. Поскольку компонента 1 является младшим разрядом в представленииномера бабочки ℓ, то номер такта выполнения этой бабочки есть ⌊ℓ/⌋, что иуказано в заключении теоремы 9.Пусть БПФ начинается со старших разрядов.

Тогда в обозначениях теоремы 8 = при 0 ≤ ≤ − 2 и −1 = . На стадиях обработки с номерами ≤ −2 выполняется только одна бабочка за такт, поэтому конфликта памятине происходит.Пусть = −1. Из определений следует, что ,−1 = при всех ≥ 0.Однако −1,−1 = 1, поэтому ,−1 = 1 при 1 ≤ ≤ −1 и 0,−1 = . Всоответствии с утверждением теоремы 8 одновременно выполняются бабочки,у которых совпадают целые части ⌊−1 /⌋ и все числа при 1 ≤ ≤ − 2.102Величины 1 и −1 входят симметрично в формулу для распределения памяти() по банкам данных.

Поэтому при замене −1 на 1 в формуле для (ℓ)конфликтов памяти не возникает.Для доказательства теоремы 8 введём ряд обозначений.Фиксируем номер стадии , 0 ≤ ≤ . С учётом обозначений, введённыхв теореме 8, определим, = ( , ),0 ≤ ≤ .Величины , , , и , обладают следующими свойствами, вытекающимииз их определений: = , , ,, =∏︁0 ≤ ≤ ,, ,, ==0,, = 1.Лемма 10 Для каждого = 0, 1, .

. . , и для произвольных целых неотрицательных чисел < , и ≤ , − 1 определим целочисленную функциюℎ ( , ( )=0 )= , +∑︁=0.Тогда остатки от деления ℎ ( , ( )=0 ) на все различны и составляютвсе целые числа от 0 до − 1.Доказательство. Количество этих остатков равно,∏︁, = , , = .=0Поэтому из того, что они различны, следует, что они заполняют всё множествоостатков от деления целых чисел на : от 0 до − 1.Поскольку оператор взятия остатка линеен по переменным и ( )=0 , тоединственность остатка равносильна тривиальности ядра этого оператора: изусловияℎ ( , ( )=0 ) = 0следует, что = 0 и = 0 при 0 ≤ ≤ .103mod Докажем тривиальность ядра по индукцией по .

Пусть = 0. Поскольку0, = 0, и 0 = 0 , то0 ≤ 0 < 0, ,ℎ0 (0 , 0 ) = 0 0, + 0 ,0 ≤ < 0, .Если ℎ0 (0 , 0 ) = 0, то 0 = 0, как остаток от деления на 0, . Следовательно,0 0, = 0 и 0 = 0, так как 0, ≥ 1.Докажем индукционный шаг. Пусть 1 ≤ ≤ и утверждение доказано для − 1. Докажем его для . Число = ( , ) делится на −1 = (−1 , ),так как число делится на −1 . Обозначим , = , /−1, . Тогда =, ,== , , .−1−1, −1,Число меньше, чем , = , −1, .

Поэтому его можно представить единственным способом в виде0 ≤ −1, < −1, , = , −1, + ,0 ≤ < , .Выполним преобразования:ℎ ( , ( )=0 )−1∑︁∑︁ −1= , + + = , +=0=0−1∑︁−1= (, −1 + )−1, , + + =0(︃)︃−1∑︁−1+ −1 −1, += −1, , + =0= −1, , + + ℎ−1 (−1 , ( )−1=0 ).По индукционному предположению равенство ℎ−1 (−1 , ( )−1=0 ) = 0 возможно только при нулевых аргументах. Поэтому достаточно доказать, что из делимости числаследует, что = = 0.

= −1, , + на при 0 ≤ < , , 0 ≤ < ,Пусть делится на = , , . Сначала докажем, что числа / и ,взаимно просты. Действительно, по общим свойствам наименьшего общего104кратного для любых натуральных чисел и пара чисел (, )/ и (, )/взаимно простая. Поскольку = (−1 , ), то число / взаимно простос числом /−1 = = , , и, следовательно, с числом , .Если делится на , , то из определения следует, что число /также делится на , .

Но < , по определению, а число / взаимнопросто с , . Следовательно, , = 1.Из неравенства < , = 1 следует, что = 0 и , = . Отсюда = −1, и < , . Поскольку делится на = , , то для завершения доказательства леммы осталось установить, что числа −1 и , взаимнопросты.По общим свойствам наибольшего общего делителя, для любых натуральных чисел и пара чисел /(, ) и /(, ) взаимно простая.

Применимэто свойство к числам = −1 и = , = ( , ). Вычислим(−1 , , ) = (−1 , ( , )) = (−1 , , ) = (−1 , ) = −1, .Следовательно, пара чисел−1 =−1=,−1,(, ), =,=−1,(, )является взаимно простой.Следствие 4 Для произвольных целых неотрицательных чисел < и ≤, − 1 при 0 ≤ ≤ − 1 определимℎ(( )=0 )=∑︁=0.Тогда остатки от деления ℎ(( )=0 ) на все различны и составляют всецелые числа от 0 до − 1.Доказательство. Утверждение получается из леммы 10 подстановкой =. Действительно, в формулировке леммы 10 , = 1 и поэтому = 0.Остаётся заменить на новую переменную из данного следствия, а такжеподставить , = / и , = .105Лемма 11 При 0 ≤ ≤ определим множество⎧⎪⎪⎨ {0, 1, .

. . , , − 1}, 0 ≤ < , ={0, 1, . . . , − 1}, = ,⎪⎪⎩ {0, 1, . . . , − 1}, < ≤ .На прямом произведении множеств =ℎ() =∑︁ ∏︀=0 определим функцию = ( )=0 .mod ,=0Тогда ℎ является биекцией на множество {0, 1, . . . , −1}.Доказательство. Докажем более общее утверждение по индукции: при ≤ ≤ отображениеℎ () =∑︁=0 ,является биекцией мнжества=( )=0∈∏︁mod ,=0∏︀=0 на {0, 1, . .

. , −1}. Тогда при = получим утверждение леммы, так как = . Поскольку количество эле∏︀ментов в =0 равно количеству вычетов по модулю , то достаточнодоказать тривиальность ядра отображения ℎ .База индукции при = доказана в следствии 4. Докажем индукционный∏︀шаг. Пусть утверждение доказано для − 1 ≥ . Пусть = ( )=0 ∈ =0 .∏︀−1Выберем все компоненты, кроме последней: ̃︀ = ( )−1∈=0=0 . Тогдаℎ () = ℎ−1 (̃︀) + ,0 ≤ < .Пусть ℎ () = 0. Тогда / делится на . Для любых натуральных чисел и числа (, )/ и (, )/ взаимно просты.

При = −1 и = получим, что (, ) = по определению. Следовательно, числа /−1 = и / взаимно просты. Поскольку / делится на и 0 ≤ < ,то = 0. Отсюда ℎ−1 (̃︀) = 0 и по индукционному предположению ̃︀ = 0.Доказательство теоремы 8.106Рассмотрим стадию с номером , 0 ≤ ≤ , по основанию .

Будемиспользовать цифровое представление ( , . . . , 0 ) номеров отсчётов входногомассива в системе счисления, порождённой мультииндексом = ( , . . . , 0 ).Каждая бабочка обрабатывает все отсчёты, номера которых имеют одинаковые значения компонент ( , .

. . , +1 , −1 , . . . , 0 ), составляющих цифровоепредставление номера ℓ этой бабочки, а компонента пробегает все допустимые значения от 0 до − 1.Рассмотрим все отсчёты, участвующие в бабочках, выполняемых одновременно. В соответствии с правилом из теоремы 8 компоненты цифрового представления этих отсчётов могут быть записаны в следующем виде:⎧⎪⎪⎨ ¯ , + , 0 ≤ < , , < , = ,0 ≤ < , = ,⎪⎪⎩ ¯ + , 0 ≤ < , < ≤ ,¯ = 0.где (¯ )=0 — фиксированные числа и Эти отсчёты записаны в банках памяти, номера которых в соответствии сопределением из теоремы 8 равны(︃ )︃∑︁() = + ¯mod ,¯ =−1∑︁=0=0¯ , +−1∑︁¯ .=0По лемме 11 остатки от деления первой суммы на различны и пробегаютвсё множество остатков от 0 до −1. Добавление числа ¯ не меняет этогомножества остатков.

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

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