10.7. Оптимальная аппаратурная реализация алгоритма БПФ с основанием 2

Теперь логично перейти к рассмотрению возможности перекрытия циклов обращения к памяти и циклов выполнения арифметических операций, так как эти действия выполняются различными устройствами. Отметим сначала, что при правильной адресации коэффициенты и  не нужно извлекать из памяти в АУ для каждой базовой операции, поскольку они могут быть одинаковыми на протяжении нескольких циклов АУ. Следовательно, в верхней строке табл. 10.1 можно убрать два цикла обращения к памяти, а в двух нижних — по одному. Для систем, указанных во второй и третьей строках таблицы, нужно обеспечить временное перекрытие четырех циклов обращения к ЗУ с работой АУ. «Оптимальная» временная диаграмма для такого режима работы приведена на фиг. 10.19.

Фиг. 10.19. Временные диаграммы для «оптимальной» системы с основанием 2.

Комплексные слова  и  вводятся в АУ; после выполнения половины вычислений в АУ вводятся числа для следующей базовой операции (предполагается, что для этого в АУ имеются специальные буферные регистры). После окончания первой базовой операции ее результаты возвращаются в ЗУ и сразу же начинается следующая базовая операция. Из диаграммы видно, что в такой «согласованной» системе длительность базовой операции должна быть равна четырем циклам обращения к ЗУ. Поскольку и ЗУ и АУ работают без пауз, данную структурную схему можно считать «оптимальной». То, что принятый способ синхронизации наилучшим образом обеспечивает согласование ЗУ и АУ, следует из того, что при уменьшении быстродействия одного из этих устройств общее быстродействие системы понизится, тогда как увеличение быстродействия только одного из них не приведет к повышению быстродействия всей системы.

Для оценки возможного быстродействия данной оптимальной схемы рассмотрим случай, когда , а цикл обращения к ЗУ составляет нс. Полное время, затрачиваемое на выполнение БПФ по 1024 отсчетам, будет равно  мс. Для обеспечения согласования между АУ и ЗУ необходимо, чтобы время выполнения базовой  операции составляло нс. Современный уровень технологии ИС вполне обеспечивает такое быстродействие.

Сравнение оптимальной схемы с другими схемами, приведенными в табл. 10.1, показывает, что при переходе от простейшего варианта одной и той же схемы к наиболее совершенному число циклов удается сократить от 28 до 4. Напомним, что время, затрачиваемое на вызов команд, не учитывалось. Если программа будет храниться в том же ЗУ, что и числа, то время выполнения БПФ значительно возрастет. Однако во многих современных ЦВМ имеется несколько блоков памяти с многоканальным доступом, что позволяет совмещать во времени обработку данных с подготовкой команд. Кроме того, не рассматривались дополнительные операции, используемые во всех алгоритмах БПФ. Они обеспечивают изменение коэффициентов и переход от этапа к этапу. Опыт показывает, что на все эти дополнительные операции (включая еще не упоминавшиеся операции ввода—вывода) тратится 20—70% от общего времени работы.