Раздел: Документация

0 ... 3 4 5 6 7 8 9 ... 78

Метод дискретного преобразования Фурье требует умножения матрицы на вектор, для того чтобы сформировалось одномерное преобразование Фурье g2, и получения внешнего векторного произведения для двумерного преобразования Фурье. Метод т-срезов соответствует формированию асимметричного внешнего векторного произведения с последующим матричным умножением. Временному интегрированию соответствует формирование поэлементного векторного произведения, асимметричного внешнего векторного произведения, а затем умножения слева на теплипеву матрицу. Структура пространственного интегратора соответствует взвешиванию столбцов матрицы с. последующим умножением справа на ганкелеву матрицу.

Необходимое время вычислений может быть значительно уменьшено введением нескольких расширителей магистрали, а также выбором конфигурации устройств памяти, позволяющим избежать необходимости последовательной записи строк или столбцов промежуточных матриц в память интерфейсных устройств. Кроме того, потребуется разбиение матриц на блоки, если число ячеек, на которые разбиваются анализируемые диапазоны задержек и частот, превышает размер процессорной решетки.

2.3.8. Умножение блочных матриц

Часто требуется, чтобы с помощью процессора со структурой размера NX XN можно было выполнять умножение матриц размера больше, чем NXN. Алгебра таких операций элементарна. Используя блочное умножение матриц, как это показано в выражении

N NN NNN

N		в\	N	(И
N	\С	в)	N

I АЕ + BG

~ \ СЕ + DG

AF 4- ВН

CF + DH

(2.20)

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

По этой причине желательно дополнить встречно-поточный процессор, изображенный на рис. 2.3, "вертикальной памятью" с адресацией, ортогональной к плоскости структуры, так что полную матрицу размера NXN можно хранить и впоследствии перегрузить за один период обращения к памяти. При такой вертикальной памяти время записи и воспроизведения, необходимое для реализации блочного умножения матриц (2.20), пренебрежимо мало, а время умножения матрицы размера 1NX1N примерно в 8 раз больше времени умножения или умножения-сложения матриц размера N AN. Разбиение матриц на блоки можно продолжать, чтобы иметь дело с матрицами еще больших размеров, и оно ограничивается только допустимым пространством вертикальной памяти. Несмотря на то, что известны методы умножения матриц размера 2NX2N, при которых осуществляется менее 8 операций умножения (AX.Vi-матриц, они менее устойчивы в вычислительном отношении и, по-видимому, требуют значительно большего объема памяти для хранения промежуточных результатов.

2.3.9. Умножение матриц за время Лг встречно-ьоточиым процессором с использованием Л расширителей магистрали

Ранее упоминалось, что скалярное произведение не меняется при циклической перестановке произведений, которые должны суммироваться. Это свойство используется для осуществления умножения матриц с помощью усовершенствованного встречно-поточного процессора, все ячейки которого в течение всего времени находятся в действии. Такой результат обычно достигается только тогда, когда возможна конвейеризация при обработке данных. Если в выражении (2.7) индекс суммирования интерпретировать как целое по модулю N, то значение суммы не изменяется, когда индекс суммирования циклически сдвигается на/, как в выражении

Л 1N -1

с» = Е ha* = I ЬА/+.в/+о у(2-21)

s-Оя-0

где С = ВА.

Реализация такого метода достигается следующим образом:

1)параллельной загрузкой А(°) =А из локальной вертикальной памяти;

2)параллельной загрузкой В(°), где BJ°£ = Ьц, ч*;рез N расширителей магистрали строк встречно-поточного процессора;

3)продвижением А наверх после каждого цикла умножения-сложения,

т.е. А:1) = А<?> , •

4)параллельной загрузкой В", где Вдг =£>д/+и. Управление адресами обычно осуществляется с помощью счетчиков по

модулю Л, для того чтобы имелся доступ к адресу каждой строки В. Следует заметать, что /-я строка В*") таким образом представляет расширенную п-ю диагональ матрицы В. Это достигается осуществлением циклического сдвига в адресных регистрах, используемых для загрузки строк В.

2.3.10. Обращение матриц

Гексагональная систолическая процессорная структура может быть использована для разложения матриц в произведение нижней и верхней треугольных матриц [в], являющегося, по существу, прямым ходом в методе Гаусса. Такая структура содержит процессоры для вычисления скалярных произведений совместно с одной особенной граничной процессорной ячейкой, необходимой для выполнении операции деления. Было обнаружено [3,7], что если к прямоугольной структуре добавить дополнительные диагональные связи между элементами, как показано на рис. 2.8, то она сможет функционировать как гексагональная структура. Также показано [6], что линейная систолическая структура с одним процессорным элементом, расположенным на границе, способным выполнять операцию деления, может служить для решения системы линейных уравнений с треугольной матрицей коэффициентов (т.е. для обратного хода при осуществлении метода Гаусса). Таким образом, структура (рис. 2.8), содержащая NXN процессорных

41

---

п

Процессор скалярного произведения для матричного умножения и деления

Рис. 2.8. Комбинированная прямоугольно-гексагональная структура При ш нГГС -олькоРве

элементов с диагональными связями между элементами и А/граничными процессорами, может осуществлять обращение матриц размера АХА за время 0(A) вначале как процессор гексагональной структуры, а затем - как А л инейных процессо ров.

2.3.11. Использование встречно-поточного процессора для обращения блочных матриц

Требования при обращении блочных матриц с помощью встречно-поточного процессора аналогичны требованиям при умножении блочных матриц, однако необходимо рассмотреть два дополнительных фактора: 1) существуют ли требуемые обратные блоки; 2) увеличивается ли необходимый объем памяти в результате использования блочного алгоритма обращения?

Пусть матрица r размера 2/VX2A разбита на блоки размера АХА следующим образом:

к-(с о)(2ЗД

Тогда обратная матрица в предположении, что оба блока а и d обратимы, определяется выражением [22]

, /V1 +а~1вд-1са-1 -авд-Л

R "У -д-са-а- )•<"3)

где д = d- са-1 в. Во многих случаях применения к обработке сигналов r является симметричной и положительно определенной матрицей. Здесь обратимость r влечет обратимость а и d. Если используется последовательность вычислений, соответствующая рис. 2.9, то легко видеть, что встречно-поточный процессор, содержащий ЛХА aneiww™. ~ --ртикальной памятью,

Й + мт

S - МД"1

т

1реоования к памяти и расчет числа операций, необходимых для обращения блочной матрицы (2 операции обращения, 6 операций матричного умножения и умножения-сложения)

42

А	R-A-1	я	R	R	R	R +MT
В	В	М = RB	М	М	М	м
С	с	с	с	Q = CR	Т = Д"1о	т
°1	D 1	А - D -СМ	л-1	д-1	Д"1	д-1

может вычислить обратную матрицу размера 2NX2N за время, примерно в восемь раз превышающее время, необходимое для обращения матрицы размера АХА, без увеличения емкости памяти, за исключением той, которая необходима для хранения представленной в блочном виде (2АХ2А)-матрицы.

2.3.12. ДПФ с использованием встречио-поточного процессора

Встречно-поточный процессор, содержащий процессорную матрицу размера АГХА, может быть использован для вычисления БПФ в системе счисления с основанием А и параллелизмом А2. Это будет показано для ДПФ длиной А2, определяемого формулой

Gk = I g„ е -i2mkm , k = 0, 1,..., N2 - 1.(2.24)

n = 0

Лексикографическое упорядочение индексов в выражении n = n.N + n2), , . ..(2.25а)

k = k1+k2N\n»n"k»k*=0U"N-U(2-256)

позволяет интерпретировать длинное одномерное ДПФ как частичное ДПФ, за которым следует поэлементное матричное умножение, за которым, в свою очередь, следует частичное ДПФ в ортогональном направлении [23]:

Gkl + k2 N = Y Y e i2nk2"2"e "k"Ng„lN+„2. (2.26)

«2 = 0 ni =0

Если эти действия выполняются с помощью комплексного встречно-поточного процессора, содержащего АХА элементов с вертикальной памятью и А расширителями магистрали, то требуется примерно 2А арифметических тактов для вычисления ДПФ длиной А2 или при Л/=А2 время вычислений составляет примерно 2М0,5 при использовании М процессорных ячеек.

Поскольку операции умножения на е /2як«2 могут быть выполнены параллельно в течение одного арифметического такта, они потребуют ничтожно малого времени по сравнению с временем операций матричного умножения, и поэтому дальнейшее усовершенствование этого процессора, по-видимому, только усложнит получение результата, не обеспечивая существенного выигрыша в скорости.

2.4. ЗАКЛЮЧЕНИЕ

Показано, что новая систолическая архитектура - встречно-поточный процессор - обеспечивает эффективное перемножение заполненных матриц. Рассмотрены два типа усовершенствованных встречно-поточных процессоров: с трехмерной организацией памяти для хранения результатов промежуточных вычислений и с расширителем магистрали для параллельной загрузки в процессор строки или столбца матриц. Показано, что такие

---

процессоры эффективно выполняют умножение и обращение блочных матриц, одно- и двумерное дискретное преобразование Фурье, а также вычисление функции неопределенности.

СПИСОК ЛИТЕРАТУРЫ

[I] J. М. Speiser, and Н. J. Whitehouse, "Architectures for Real-Time Matrix Operations,"

Proc. 1980 Government Microcircuits Appl. Conf., Houston, Nov. 1980, pp. 19-21. [2] J. M. Speiser, H. J. Whitehouse, and K. Bromley, "Signal Processing Applications for

Systolic Arrays," 14th Asilomar Conf. Circuits, Syst. Comput., Pacific Grove, Calif., Nov.

17-19, 1980, IEEE Catalog 80CH1625-3, pp. 100-104. [3] S. Y. Kung, "VLSI Array Processors for Signal Processing," MIT Conf. Adv. Res. VLSI,

Cambridge, Mass., Jan. 1980. [4] J. J. Dongarra, et al, UNPACK Vsers Guide, SIAM, Philadelphia, 1979. [5] B. S. Garbow, et al, Matrix Eigensystem Routines-EISPACK Guide Extensions,

Springer-Verlag, New York, 1977.

[6] H. T. Kung, "Systolic Arrays for VLSI," in I. S. Duff and G. W. Stewart, eds., Sparse Matrix Proceedings, 1978, SIAM, Philadelphia, 1979.

[7] S. Y. Kung, et al., "Wavefront Array Processor: Language, Architecture, and Application," IEEE Trans. Compute, Special Issue on Parallel and Distributed Computers, C-37(ll): 1054-1066 (Nov. 1982).

[8] G. A. Frank, J. Blackmer, and P. Kuekes, "A 200 MOPS Systolic Processor," Proc.

SPIE Symp., Vol. 298: Real-Time Signal Processing IV, San Diego, Aug. 1981. [9] J. Symanski, et al., "A Systolic-Array Processor Implementation," Proc. SPIE Symp., Vol. 298: Real-Time Signal Processing IV, San Diego, Aug. 1981. [10] S. Y. Kung, and Y. H. Hu, "A Highly Concurrent Algorithm and Pipelined Architectures for Solving Toeplitz Systems," IEEE Trans. Acoust. Speech Signal Process., .?/(l):66~76 (Feb. 1983).

[11] W. M. Gentleman, and H. T. Kung, "Matrix Triangularization by Systolic Arrays," Proc. SPIE Symp., Vol. 298: Real-Time Signal Processing IV, San Diego, Aug. 1981.

[12] A. M. Finn, F. T. Luk, and С Pottle, "Systolic-Array Computation of the Singular Value Decomposition," Proc. SPIE Symp., Vol. 341: Real-Time Signal Processing V, Arlington, Va., May 1982.

[13] R. P. Brent and F. T. Luk, "A Systolic Architecture for Almost Linear-Time Solution of the Symmetric Eigenvalue Problem," Cornell University Tech. Rep. TR82-525, Aug. 1982.

[14] S. Y. Kung and R. J. Gal-Ezer, "Eigenvalue, Singular Value and Least Squares Solvers via the Wavefront Array Processors," in L. Synder et al, eds., Algorithmically Specialized Computer Organizations, Academic Press, New York, 1983.

[15] B. Widrow, et al., "Adaptive Noise Cancelling: Principles and Applications," Proc. IEEE,63:im-1716 (Dec 1975).

[16] L. J. Griffiths, "A Continuously-Adaptive Filter Implemented as a Lattice Structure," 1977 IEEE Int. Conf. Acoust. Speech Signal Process., IEEE Catalog 77СШ197-3, pp. 683-686.

[17] R. A. Monzingo and T. W. Miller, Introduction to Adaptive Arrays, Wiley, New York, 1980, Chap. 6: "Direct Inversion of the Sample Covariance Matrix."

[18] S. Haykin, ed., Nonlinear Methods of Spectral Analysis, Springer-Verlag, New York, 1979.

M9] C. L. Lawson and R. i. Hanson, Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, NJ., 1974. [20] L M. Speiser, H. J. Whitehouse, and N. J. Berg, "Signal Processing Architectures Using Convolutional Technology," Proc. SPIE Symp., Vol. 154: Real-Time Signal Processing,

1978, pp. 66-80,

[21] A. W. Rihaczek, Principles of High-Resolution Radar, McGraw-Hill, New York, 1969.

[22] E. Bodewig, Matrix Calculus, 2nd ed., North-Holland/Interscience, New York, 1959.

[23] H. J. Whitehouse and J. M. Speiser, "Linear Signal Processing Architectures," in Aspects of Signal Processing, with Emphasis on Underwater Acoustics, Part 2, D. Reidel, Dordrecht, The Netherlands, 1977.

3

СПЕКТРАЛЬНЫЙ АНАЛИЗ: ОТ ОБЫЧНЫХ МЕТОДОВ К МЕТОДАМ С ВЫСОКОЙ РАЗРЕШАЮЩЕЙ СПОСОБНОСТЬЮ

С. Гун, Д. Рао, К. Аруи1

3.1. ВВЕДЕНИЕ

Спектральный анализ составляет основу большинства методов обработки сигналов, используемых обычно для выделения представляющих интерес сигналов, а также для получения информации из соответствующих данных. Задача классического спектрального анализа состояла в оценке энергетического спектра по конечному числу зашумленных отсчетов дискретного стохастического процесса или по нескольким значениям оценки его корреляционной функции. Задача современного спектрального анализа в некоторых практических случаях, например в радио- и гидролокации, при обработке сигналов в фазированных антенных решетках, где спектр является линейчатым, состоит в оценке положения спектральных линий. Как результат этого понятия смещения и дисперсии, которые прежде относились к оценке формы спектра, теперь относятся к оценке частоты. Другой качественной характеристикой классического спектрального анализа является разрешающая способность по частоте, которая определяет степень детальности исследования спектра [1]. В современной постановке разрешающая способность есть способность различать и идентифицировать спектральные линии, которые расположены близко по частоте [2]. Во многих современных случаях применения спектральный анализ приходится производить, имея в распоряжении короткие записи данных (в радиолокации, например, в каждом отраженном импульсе может содержаться всего несколько отсчетов), но тем не менее необходимы опенки с высоким разрешением, малыми смещением и дисперсией.

1 Университет Южной Калифорнии, Лос-Анжелес, Калифорния.

0 ... 3 4 5 6 7 8 9 ... 78