4.8 Оценка быстродействия

В разд. 4.4-4.6 мы построили базовые схемы ДПФ; в разд. 4.7 показали, как их использовать в эффективном алгоритме для некоторых значений . В этом разделе нашей целью являются определение того, насколько быстрым является результирующий алгоритм, и получение сводной таблицы 4.6 соответствующих параметров для всех порядков, реализуемых с помощью сконструированных схем. В качестве основы будем использовать табл. 4.5, в которую сведены параметры разработанных схем. Все параметры ранее были полностью объяснены и указаны на изображении каждой схемы.

Таблица 4.5. Сводка параметров основных схем ДПФ

Рассмотрим алгоритм порядка применяемый к комплексным данным Для каждого из табл. 4.5 выбираются соответствующее число комплексных умножений и комплексных (сложений Нас интересуют две функции этих переменных — общее число вещественных умножений и общее число вещественных сложений для всего алгоритма, реализованного в порядке, предусмотренном (4.142) (фаза 1 схемы реализуется первой; фаза 1 схемы последней). Теперь обратимся к математической формулировке некоторых характеристик алгоритма, структура которого совершенно очевидна из рис. 4.20.

Заметим, что выходом фазы 1 схемы является множество из векторов размерности Каждый из них порождает (на выходе фазы 1 схемы векторов размерности Очевидно поэтому, что

Поскольку каждый из этих векторов поступает на вход фазы 1 схемы указанное в (4.173) число определяет также число схем порядка или, что эквивалентно,

Простейшим применением полученных результатов является определение числа умножений. Пусть — общее число (комплексных) скалярных умножений на фазе 2 алгоритма, реализованного в виде каскада из х ступеней. Перемножаемые переменные являются одномерными векторами полученными на последней ступени каскада Из (4.173) известно, что существует таких членов. Следовательно,

Чтобы получить общее число вещественных умножений (Ж) на весь каскад, отметим, что в каждом из учитываемых умножений только один из двух сомножителей является комплексным, а другой — вещественным или мнимым (см. табл. 4.4). Поэтому

В разд. 4.7 показано, что каждый из полных множителей каскада является произведением схемных множителей, по одному из каждой схемы каскада. Поскольку каждая схема имеет по крайней мере один множитель, значение которого равно 1 или

(см. в табл. 4.5), некоторые из полных множителей будут 1 или I.

Рассмотрение структуры рис. 4.20 показывает, что число таких множителей

Поэтому, если пойти на более сложное программирование, позволяющее выделить эти тривиальных множителей, ДПФ можно будет вычислить с меньшим числом вещественных умножений

В итоговую табл. 4.6 включены оба случая Обратимся теперь к подсчету числа сложений. Пусть будет общим числом (комплексных) скалярных сложений в последовательности из х ступеней. Тогда соответствующее число вещественных сложений

Простейший способ определения состоит в использовании рекурсивных рассуждений. Предположим, что известен результат для последовательности длиной и мы добавляем еще одну ступень. Отсюда вытекают два обстоятельства. Во-первых, сложения на первых ступенях относятся теперь к векторам, размерность которых в раз больше их предшествующих значений. Следовательно, предыдущие 1 сложений превращаются в 1 сложений. К этому необходимо прибавить число сложений на последней ступени. Из (4.174) число схем на последней ступени равно Каждая такая схема требует сложений скалярных величин. Следовательно, число скалярных сложений на последней ступени равно а общее число

Здесь для получения полной системы правил последовательного вычисления добавлено выражение (4.176) в рекурсивном

(кликните для просмотра скана)

представлении и определены начальные условия. Выражение (4.180) дает также явную формулу для Например,

Важным и очевидным следствием (4.181) является то, что в отличие от является также функцией порядка, в котором входят в Поэтому важно найти порядок следования каскадов, минимизирующий

Имея в своем распоряжении (4.175)-(4.180) и табл. 4.5, можем вычислить для всех удовлетворяющих (4.142). В табл. 4.6 представлены результаты таких вычислений, выполненных с помощью простой программы, которая позволяет также получить данные для выбора наиболее эффективного варианта порядка следования каскадов. Эта последовательность показана в последних столбцах табл. 4.6. Здесь в таблице оставлено место для двух последовательностей, так как в некоторых случаях одни и те же значения М и получаются для двух разных последовательностей . В таких случаях окончательный выбор определяется не эффективностью, а другими соображениями.

Справа от каждого значения стоит число в скобках значение из (4.163). Таким образом, табл. 4.6 дает и последовательность схем, которая должна быть реализована, и перестановку, которую надо выполнить во входном квадрате каждой схемы [см. рассуждения, предшествующие (4.168)].

Заметим, что очень важно придерживаться порядка, предписанного табл. 4.6. Например, для таблица определяет значение с предписываемым порядком 3; 16; 5. Если вместо этого выбрать порядок 5; 16; 3, то число вещественных сложений возрастает до 5592, т. е. на 11%.

Обратимся теперь к двум оставшимся столбцам табл. 4.6, а именно, Оба параметра уже упоминались в разд. 4.1. Они требуются для определения выигрыша в скорости в конкретной системе.

Пусть

в рассматриваемой системе. Определим выигрыш данного алгоритма по сравнению с алгоритмом Кули—Тьюки:

— параметры Кули—Тьюки, введенные в (4.1). Очевидно, что — это отношение времени, требующегося для алгоритма Кули—Тьюки, к времени, которое необходимо для алгоритма Винограда. Будем называть его выигрышем в скорости, хотя

следует принимать во внимание, что он отражает только время, занимаемое арифметическими вычислениями. Поэтому этот показатель не отражает большей сложности алгоритма Винограда, которая замедляет выполнение его на универсальной ЭВМ. Однако, когда рассматривается - опециавизированный ДПФ - процессор, эта оценка выигрыша в скорости весьма правдоподобна.

— функция и еще четырех параметров, появляющихся в (4.182). Более удобной формулой, содержащей только два параметра [см. (4.1)], является выражение

где

— это асимптотический выигрыш в скорости, который достигается при больших значениях является полюсом функции при и поэтому определяет вторую асимптоту. Добавление к этим двум параметрам нуля функций при позволяет легко представить себе вид функции и достаточно точно оценить ее. И, наконец, если заменить в (4.182) — (4.185)

М на получим значения, приведенные в столбцах табл. 4.6.

В заключение сделаем несколько замечаний по поводу случая вещественных данных. Число арифметических операций вовсе не составляет половины соответствующего числа в случае комплексных данных. Основная причина этого заключается в том, что, поскольку результат ДПФ вещественного вектора является в общем случае комплексным, некоторые из промежуточных результатов будут комплексными. Например, согласно схеме ДПФ восьмого порядка

и поэтому является комплексным даже для вещественных данных. Это значит, что схема, реализующая имеет на входе комплексные данные.

Другим фактором, который надо учитывать, является то, что представление комплексного числа в виде суммы двух его компонент не означает на самом деле никакого сложения, несмотря на наличие знака плюс. В упомянутом выше примере и являются вещественными, когда вещественны Следовательно, «сложение», появившееся в (4.186), становится фиктивным.