10.10. Параллельные структуры для алгоритмов БПФ с основаниями 2 и 4, использующие ЗУ с произвольным доступом

В данном разделе рассматриваются вычислительные структуры, в которых используется параллелизм со следующими отличительными особенностями:

1. Обращения к памяти и вычислительные операции полностью совмещаются во времени. Такая структура является согласованной в том смысле, что при ее проектировании и на ЗУ, и на АУ накладываются одинаковые ограничения.

2. Числа хранятся в ЗУ с произвольным доступом, слова которого состоят из  комплексных чисел, где  — основание алгоритма БПФ, не изменяющееся в процессе счета.

Алгоритм с основанием 2, соответствующий такой структуре, иллюстрируется на фиг. 10.8. Блок-схема аппаратурной реализации этого алгоритма и соответствующие временные диаграммы представлены на фиг. 10.21. ЗУ с произвольным доступом состоит из  регистров, каждый из которых рассчитан на два комплексных числа. Номера регистров ЗУ соответствуют их адресам. Чтобы система была согласованной, нужно, чтобы циклы считывания следовали друг за другом без пауз. Поэтому последовательные циклы считывания должны перекрываться с циклами вычислительных операций. Более того, поскольку запись результатов возможна лишь после завершения по крайней мере двух циклов вычислений, из временной диаграммы (фиг. 10.21) видно, что записи должны предшествовать четыре последовательных цикла считывания. Отсюда следует, что АУ должно иметь поточную схему с тем, чтобы выполнение второй базовой операции начиналось до завершения первой.

Если АУ не успевает выполнить свои функции за два цикла обращения к ЗУ, можно применить схему с более продолжительной поточной обработкой, занимающей шесть циклов обращения к ЗУ, причем схема по-прежнему остается согласованной. Временные диаграммы ее работы приведены на фиг. 10.22. Такая схема представляет собой расширенный вариант схемы фиг. 10.21, а, содержащий шесть буферных регистров, включенных между шестью элементарными арифметическими устройствами. Если вычисления могут выполняться быстрее, некоторые из элементарных АУ фактически будут отсутствовать. Они будут обеспечивать лишь соединение соседних буферных регистров.

Фиг. 10.21. Блок-схема и временные диаграммы устройства БПФ с основанием 2 и регистрами двойной длины.

Фиг. 10.22. Другой вариант временных диаграмм для схемы фиг. 10.21.  

Предлагаем читателю  самому разработать структурную схему и построить временные диаграммы для случая, когда одно АУ работает совместно с двумя ЗУ с произвольным доступом.

На фиг. 10.23 изображены блок-схема реализации алгоритма БПФ с основанием 4 и ее временные диаграммы. Время счета здесь равно четырем циклам обращения к памяти; сначала выполняются подряд восемь циклов чтения из ЗУ, а за ними следуют восемь циклов записи. Вычисления, проводимые поточным методом, завершаются матричной перестановкой (4×4) результатов, выполняемой с помощью четырех регистров, показанных на фиг. 10.23, причем каждый из регистров содержит результат базовой операции алгоритма БПФ с основанием 4.

 Фиг. 10.23. Блок-схема параллельного устройства с основанием 4 и соответствующие временные диаграммы.

Метод использования параллелизма, представленный в данном разделе, основан главным образом на идее согласования длительности обращения к памяти и продолжительности выполнения базовой операции. Предполагалось, что используется алгоритм с постоянным основанием и что при основании  создается -кратный параллелизм. Алгоритм с основанием  состоит из  этапов. На каждом из них ко всем  регистрам приходится обращаться дважды — для считывания входных чисел базовой операции и для записи ее результатов. Таким образом, количество циклов обращения к памяти, затрачиваемых на выполнение БПФ, составляет

,                                                   (10.26)

так что на один входной отсчет приходится

                                              (10.27)

циклов. Соотношение (10.27) определяет наибольшую частоту дискретизации, при которой возможна обработка в реальном времени, если известна длительность выполнения базовой операции или цикла обращения к памяти. Например, если  и , то ; таким образом, при длительности выполнения базовой операции в 100 не можно обрабатывать сигнал, дискретизуемый с частотой 1 МГц.