空間 - 時間共享的可組態式快速傅立葉轉換架構設計

Spatio-Temporally-Shared Recon gurable Fast Fourier Transform Architecture Design

彭竣陽(Jun-Yang Peng)

指導教授 ： 熊博安

國立中正大學/工學院/資訊工程學系/碩士(2013年)

摘要

近年來，快速傅立葉轉換（Fast Fourier Transform）是一個在通訊、影像處理以及數位信號處理中應用最廣泛使用的計算核心。這些通訊應用需要高運算能力、高靈活性、及高擴充性的能力。而在靈活性、實現的複雜度和能源效率的取捨上，可組態式架構(reconfigurable)是一個最有彈性的架構。傳統的FFT 架構在設計上可以分為兩類：管線式(pipeline-based)與記憶體式(memory-based)架構。管線式具有較高的吞吐量(throughput)和控制器的設計較為簡單的優點。但是所佔用的硬體面積較大。而記憶體式具有相反的優點和缺點。

憑藉部分動態可組態式架構(partial dynamic reconfiguration)技術的靈活性和可擴展性，並整合管線式與記憶體式的架構，我們提出一個新的具有高擴充性的FFT 架構，稱為空間 - 時間共享的可組態式快速傅立葉轉換（STARFFT）架構。STARFFT 可以同時運算多個64 到8192 點的可變長度FFT，涵蓋了現今最常用的通訊標準。STARFFT 支援多個管道式架構，並採用radix-2 運算硬體單元，透過分時多工的方式切換多種應用，顯著地達到節省硬體資源。STARFFT 的資源分配(resource allocation)會同時考慮並滿足各種應用在時間與空間上的限制。最後我們提出了兩種演算法以提高硬體資源利用率。實驗顯示，在多個應用下與傳統的管線式FFT 架構相比，可以減少近50％的資源消耗，降低功耗約60％。

關鍵字

現場可程式化閘陣列 ； 可組態式 ； 快速傅立葉轉換 ； 管線式架構

並列摘要

In recent years, the fast Fourier transform (FFT) has become one of the most widely-used computation kernels in many modern systems, such as for communication, image processing, and digital signal processing applications. These wired/wireless communication applications demand high-performance, flexibility, and scalability. The reconfigurable architectures make excellent tradeoff between flexibility, implementation complexity, and energy efficiency. The traditional FFT structure can be classified into two categories: pipeline-based and memory-based architectures. The former has the strengths of higher throughput and easier controller design, but the hardware area is larger. The latter has the opposite strengths and weaknesses.

Leveraging on the partial dynamic reconfiguration technology for flexibility and scalability and on the integration of pipeline-based and memory-based architectures, we propose a novel scalable FFT architecture called Spatio-Temporally-shared Reconfigurable Fast Fourier Transform (STARFFT) architecture. STARFFT can support the simultaneous computation of multiple FFTs of varying sizes from 64 to
8192 points, covering most frequently used modern computing standards. It supports multiple pipelines based on the radix-2 hardware computation blocks that are time-multiplexed among multiple applications such that significant savings in hardware resources are achieved. Both spatial and temporal constraints of applications are all satisfied by STARFFT through resource allocation. Specifically, we propose two algorithms to improve the resource utilization and our experiments show that the algorithms can reduce resources by nearly 50\%. Besides, the results show that reductions in power consumption can reach about 60\% when compared with traditional pipelined-based FFT in multiple applications.

並列關鍵字

FPGA ； Reconfiguration ； Fast Fourier Transforms (FFT) ； Pipeline-based architecture ； Radix-2

參考文獻

[37] S. Christian, H. Bastian, and B. J¨urgen. Reconfiguration techniques for self-X power and performance management on Xilinx Virtex-II/Virtex-II-pro FPGAs. International Journal of Reconfigurable Computing, 2011:1:1–1:12, January 2011.

[3] C. L. Wey, S. Y. Lin, P. Y. Tsai, and M. D. Shieh. Reconfigurable Homoge¬nous Multi-core FFT Processor Architectures for Hybrid SISO/MIMO OFDM Wireless Communications. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E94-A(7):1530–1539, January 2011.

[4] Y. W. Lin and C. Y. Lee. Design of an FFT/IFFT Processor for MIMO OFDM Systems. IEEE Transactions on Circuits and Systems, 54(4):807–815, April 2007.

[9] J. Lee and H. Lee. A High-speed Two-parallel Radix-24 FFT/IFFT Processor for MB-OFDM UWB Systems. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E91-A(4):1206–1211, April 2008.

[11] S. He and M. Torkelson. Design and Implementation of a 1024-point Pipeline