10.11. Общие вопросы построения поточных схем БПФ

Если еще раз обратиться к схемам фиг. 10.1—10.8, то можно заметить, что, хотя они и описывают многие свойства алгоритма, последовательность выполнения базовых операций во времени все еще остается неопределенной. В самом деле, существует много различных последовательностей, которые приводят к одинаковым результатам. Так, на первом этапе алгоритма фиг. 10.1 пары отсчетов 0и8,1и9 ит.д. можно обрабатывать в любом порядке. Это же справедливо и для остальных этапов. Достоинством некоторых вариантов последовательностей выполнения операций может оказаться легкость аппаратурной реализации или программирования, но сама структура алгоритма принципиальных ограничений не вносит. Так, для перехода ко второму этапу вовсе не обязательно, чтобы первый этап был завершен. Действительно, если в начале первого этапа обрабатываются отсчеты 0 и 8, а затем 4 и 12, то после этого уже можно начать выполнение второго этапа.

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

Чтобы проиллюстрировать уровень параллелизма в поточной схеме БПФ, рассмотрим в качестве примера БПФ с основанием 2 массива из 1024 отсчетов, которое выполняется за 10 этапов. В большинстве универсальных ЦВМ имеется только одно устройство умножения. В поточной схеме БПФ для выполнения базовых операций может быть использовано 10 независимых арифметических устройств, что соответствует 40 умножителям действительных чисел (так как каждая базовая операция включает комплексное умножение, состоящее из четырех действительных умножений). Таким образом, если предположить, что эффективность поточной схемы БПФ совпадает с эффективностью универсальной ЦВМ, запрограммированной на выполнение алгоритма БПФ, то скорость выполнения БПФ в поточном устройстве будет в 40 раз больше, чем в универсальной ЦВМ. Оказалось, что в поточной схеме БПФ аппаратура используется в 2—20 раз эффективнее, чем при выполнении БПФ на любой из известных универсальных ЦВМ. Таким образом, в поточной схеме алгоритм БПФ выполняется на 2—3 порядка быстрее. Из-за большой эффективности и относительной простоты управления поточные схемы БПФ представляются сейчас наиболее перспективными при построении специализированных высокопроизводительных процессоров БПФ.