데이터 재구성 기법을 이용한 고성능 FFT
High-Performance FFT Using Data Reorganization
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
대규모 신호처리 변환을 신속하게 처리하기 위해서는 캐시 메모리를 효과적으로 이용하는 것이 중요하다. 대규모 DFT 계산에서는 stride 액세스로 인한 캐시 충돌 적중 실패로 인하여 캐시 성능이 상당히 떨어지게 되고 이로 인해 전체적인 성능이 저하하게 된다. 본 논문에서는 메모리 계층 구조를 고려한 동적 데이터 재배열(Dynamic Data Layout) 방법을 개발하였다. 제시된 방법은 stride를 가지는 계산 단계(computation stage) 사이에 데이터를 동적으로 재구성을 하여 캐시 적중 실패를 줄이는 것이다. 또한 트리 구조 FFT 계산 방법에서 FFT 크기와 데이터 stride 액세스를 기초로 하여 가능한 모든 인수분해 트리 중에서 최소 실행시간을 가지는 최적의 인수 분해트리를 찾아내는 탐색 알고리즘을 개발하였다. 성능 향상을 확인하기 위하여 제시된 방법을 기존의 FFT 알고리즘에 적용하여 Pentium 4, Alpha 21264, AthlonTM 64, UltraSPARC III에서 실험하였다. 실험 결과에 따르면 기존의 FFT 패키지들과 비교하여 제시된 방법을 적용한 FFT가 최대 3.37배의 성능 향상을 얻을 수 있었다.
Abstract
The efficient utilization of cache memories is a key factor in achieving high performance for computing large signal transforms. Nonunit stride access in computation of large DFTs causes cache conflict misses, thereby resulting in poor cache performance. It leads to a severe degradation in overall performance. In this paper, we propose a dynamic data layout approach considering the memory hierarchy system. In our approach, data reorganization is performed between computation stages to reduce the number of cache misses. Also, we develop an efficient search algorithm to determine the optimal tree with the minimum execution time among possible factorization trees considering the size of DFTs and the data access stride. Our approach is applied to compute the fast Fourier Transform (FFT). Experiments were performed on Pentium 4, AthlonTM 64, Alpha 21264, UltraSPARC III. Experiment results show that our FFT achieve performance improvement of up to 3.37 times better than the previous FFT packages.
참고문헌 (14)
- "Weaving Relations for Cache Performance" (2001)
- "Unfavorable Strides in Cache Memory Systems" (1995)
- "Zur Algorithmischen Zerlegungstheorie Linearer Transformationen mit Symmetire" (1997)
- "FFTW: An Adaptive Software Architecture for the FFT" (1998)
- "Faster FFTs via Architecture Cognizance" (2000)
- "An Investigation of Recursive FFT Implementations" (2000)
- "In Search of the Optimal Walsh-Hadamard Transform" (2000)
- "Real-Time STAP Demonstration on an Embedded High-Performance Computer" (1997)
- "Utilizing the Power of High-Performance Computing" (1998)
- "Computational Frameworks for the Fast Fourier Transform", 10 (1992)
- "An Adaptive Software Library for Fast Fourier Transforms" (2000)
- "Analysis of Memory Hierarchy Performance of Block Data Layout" (2002)
- "Cache Conscious Walsh-Hadamard Transform" (2001)
- "Algorithms for Discrete Fourier Transforms and Convolution" (1997), Springer