Computer generation of fast fourier transforms for the cell broadband engine

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computer generation of fast fourier transforms for the cell broadband engine

Full text

Pdf (420 KB)

Source

International Conference on Supercomputing archive
Proceedings of the 23rd international conference on Supercomputing table of contents

Yorktown Heights, NY, USA

SESSION: Applications of the cell processor table of contents

Pages 26-35

Year of Publication: 2009

ISBN:978-1-60558-498-0

Authors

Srinivas Chellappa	Carnegie Mellon University, Pittsburgh, PA, USA
Franz Franchetti	Carnegie Mellon University, Pittsburgh, PA, USA
Markus Püeschel	Carnegie Mellon University, Pittsburgh, PA, USA

Sponsors

ACM: Association for Computing Machinery
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 28, Downloads (12 Months): 71, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1542275.1542285 What is a DOI?

ABSTRACT

The Cell BE is a multicore processor with eight vector accelerators (called SPEs) that implement explicit cache management through direct memory access engines. While the Cell has an impressive floating point peak performance, programming and optimizing for it is difficult as it requires explicit memory management, multithreading, streaming, and vectorization. We address this problem for the discrete Fourier transform (DFT) by extending Spiral, a program generation system, to automatically generate highly optimized implementations for the Cell. The extensions include multi-SPE parallelization and explicit memory streaming, both performed at a high abstraction level using rewriting systems operating on Spiral's internal domain-specific language. Further, we support latency and throughput optimizations, single and double precision, and different data formats. The performance of Spiral's computer generated code is comparable with and sometimes better than existing DFT implementations, where available.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. A. Bader and V. Agarwal. FFTC: Fastest Fourier transform for the IBM Cell Broadband Engine. In IEEE Intl. Conference on High Performance Computing, pages 172--184, 2007.
	2	S. Chellappa, F. Franchetti, and M. Püschel. FFT program generation for the Cell BE. In International Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA), 2008.
	3	A. C. Chow. Fast Fourier transform SIMD code generators for synergistic processor element of Cell processor. In Workshop on Cell Systems and Applications, 2008.
	4	A. C. Chow, G. C. Fossum, and D. A. Brokenshire. A programming example: Large FFT on the Cell Broadband Engine. Technical report, IBM, May 2005.
	5	L. Cico, R. Cooper, and J. Greene. Performance and Programmability of the IBM/Sony/Toshiba Cell Broadband Engine Processor. In Proc. of (EDGE) Workshop, 2006.
	6	FFTW on the cell processor. http://www.fftw.org/cell/.
	7	F. Franchetti, D. McFarlin, F. de Mesmay, H. Shen, T. W. Wlodarczyk, S. Chellappa, M. Telgarsky, P. A. Milder, Y. Voronenko, Q. Yu, J. C. Hoe, J. M. F. Moura, and M. Pueschel. Program generation with Spiral: Beyond transforms. In High Performance Embedded Computing (HPEC), 2008.
	8	Franz Franchetti , Yevgen Voronenko , Markus Püschel, Formal loop merging for signal transforms, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
	9	Franz Franchetti , Yevgen Voronenko , Markus Püschel, FFT program generation for shared memory: SMP and multicore, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188575]
	10	F. Franchetti, Y. Voronenko, and M. Püschel. A rewriting system for the vectorization of signal transforms. In High Performance Computing for Computational Science (VECPAR), volume 4395 of Lecture Notes in Computer Science, pages 363--377. Springer, 2006.
	11	M. Frigo and S. G. Johnson. The design and implementation of FFTW3. Proc. of the IEEE, special issue on "Program Generation, Optimization, and Adaptation", 93(2):216--231, 2005.
	12	J. Greene and R. Cooper. A parallel 64K complex FFT algorithm for the ibm/sony/toshiba cell broadband engine processor. In Global Signal Processing Expo (GSPx), 2005.
	13	IBM. Fast Fourier Transform Library Programmer's Guide and API Reference, 3.0 edition, 2008.
	14	Michael Kistler , Michael Perrone , Fabrizio Petrini, Cell Multiprocessor Communication Network: Built for Speed, IEEE Micro, v.26 n.3, p.10-23, May 2006 [doi>10.1109/MM.2006.49]
	15	M. Püschel, J. M. F. Moura, J. Johnson, D. Padua, M. Veloso, B. Singer, J. Xiong, F. Franchetti, A. Gacic, Y. Voronenko, K. Chen, R. W. Johnson, and N. Rizzolo. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation," 93(2):232--275, 2005.
	16	Charles Van Loan, Computational frameworks for the fast Fourier transform, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
	17	Yevgen Voronenko , Frédéric de Mesmay , Markus Püschel, Computer Generation of General Size Linear Transform Libraries, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.102-113, March 22-25, 2009 [doi>10.1109/CGO.2009.33]