Searching for the best FFT formulas with the SPL compiler

Jeremy Johnson; Robert W. Johnson; David A. Padua; Jianxin Xiong

doi:10.1007/3-540-45574-4_8

Searching for the best FFT formulas with the SPL compiler

Jeremy Johnson, Robert W. Johnson, David A. Padua, Jianxin Xiong

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper discuss an approach to implementing and optimizing fast signal transforms based on a domain-specific computer language, called SPL. SPL programs, which are essentially mathematical formulas, represent matrix factorizations, which provide fast algorithms for computing many important signal transforms. A special purpose compiler translates SPL programs into efficient FORTRAN programs. Since there are many formulas for a given transform, a fast implementation can be obtained by generating alternative formulas and searching for the one with the fastest execution time. This paper presents an application of this methodology to the implementation of the FFT.

Original language	English (US)
Title of host publication	Languages and Compilers for Parallel Computing - 13th International Workshop, LCPC 2000, Revised Papers
Editors	Jeanne Ferrante, Samuel P. Midkiff, Jose E. Moreira, Manish Gupta, Siddhartha Chatterjee, Jan Prins, William Pugh, Chau-Wen Tseng
Publisher	Springer
Pages	112-126
Number of pages	15
ISBN (Print)	3540428623, 9783540455745
DOIs	https://doi.org/10.1007/3-540-45574-4_8
State	Published - 2001
Event	13th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2000 - Yorktown Heights, United States Duration: Aug 10 2000 → Aug 12 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2017
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2000
Country/Territory	United States
City	Yorktown Heights
Period	8/10/00 → 8/12/00

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/3-540-45574-4_8

Library availability

Discover UIUC Full Text

Cite this

Johnson, J., Johnson, R. W., Padua, D. A., & Xiong, J. (2001). Searching for the best FFT formulas with the SPL compiler. In J. Ferrante, S. P. Midkiff, J. E. Moreira, M. Gupta, S. Chatterjee, J. Prins, W. Pugh, & C.-W. Tseng (Eds.), Languages and Compilers for Parallel Computing - 13th International Workshop, LCPC 2000, Revised Papers (pp. 112-126). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2017). Springer. https://doi.org/10.1007/3-540-45574-4_8

Searching for the best FFT formulas with the SPL compiler. / Johnson, Jeremy; Johnson, Robert W.; Padua, David A. et al.
Languages and Compilers for Parallel Computing - 13th International Workshop, LCPC 2000, Revised Papers. ed. / Jeanne Ferrante; Samuel P. Midkiff; Jose E. Moreira; Manish Gupta; Siddhartha Chatterjee; Jan Prins; William Pugh; Chau-Wen Tseng. Springer, 2001. p. 112-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2017).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Johnson, J, Johnson, RW, Padua, DA & Xiong, J 2001, Searching for the best FFT formulas with the SPL compiler. in J Ferrante, SP Midkiff, JE Moreira, M Gupta, S Chatterjee, J Prins, W Pugh & C-W Tseng (eds), Languages and Compilers for Parallel Computing - 13th International Workshop, LCPC 2000, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2017, Springer, pp. 112-126, 13th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2000, Yorktown Heights, United States, 8/10/00. https://doi.org/10.1007/3-540-45574-4_8

Johnson J, Johnson RW, Padua DA, Xiong J. Searching for the best FFT formulas with the SPL compiler. In Ferrante J, Midkiff SP, Moreira JE, Gupta M, Chatterjee S, Prins J, Pugh W, Tseng CW, editors, Languages and Compilers for Parallel Computing - 13th International Workshop, LCPC 2000, Revised Papers. Springer. 2001. p. 112-126. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45574-4_8

Johnson, Jeremy ; Johnson, Robert W. ; Padua, David A. et al. / Searching for the best FFT formulas with the SPL compiler. Languages and Compilers for Parallel Computing - 13th International Workshop, LCPC 2000, Revised Papers. editor / Jeanne Ferrante ; Samuel P. Midkiff ; Jose E. Moreira ; Manish Gupta ; Siddhartha Chatterjee ; Jan Prins ; William Pugh ; Chau-Wen Tseng. Springer, 2001. pp. 112-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d0146457b46649ee85bfb261e32d4573,

title = "Searching for the best FFT formulas with the SPL compiler",

abstract = "This paper discuss an approach to implementing and optimizing fast signal transforms based on a domain-specific computer language, called SPL. SPL programs, which are essentially mathematical formulas, represent matrix factorizations, which provide fast algorithms for computing many important signal transforms. A special purpose compiler translates SPL programs into efficient FORTRAN programs. Since there are many formulas for a given transform, a fast implementation can be obtained by generating alternative formulas and searching for the one with the fastest execution time. This paper presents an application of this methodology to the implementation of the FFT.",

author = "Jeremy Johnson and Johnson, {Robert W.} and Padua, {David A.} and Jianxin Xiong",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 13th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2000 ; Conference date: 10-08-2000 Through 12-08-2000",

year = "2001",

doi = "10.1007/3-540-45574-4_8",

language = "English (US)",

isbn = "3540428623",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "112--126",

editor = "Jeanne Ferrante and Midkiff, {Samuel P.} and Moreira, {Jose E.} and Manish Gupta and Siddhartha Chatterjee and Jan Prins and William Pugh and Chau-Wen Tseng",

booktitle = "Languages and Compilers for Parallel Computing - 13th International Workshop, LCPC 2000, Revised Papers",

address = "Germany",

}

TY - GEN

T1 - Searching for the best FFT formulas with the SPL compiler

AU - Johnson, Jeremy

AU - Johnson, Robert W.

AU - Padua, David A.

AU - Xiong, Jianxin

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - This paper discuss an approach to implementing and optimizing fast signal transforms based on a domain-specific computer language, called SPL. SPL programs, which are essentially mathematical formulas, represent matrix factorizations, which provide fast algorithms for computing many important signal transforms. A special purpose compiler translates SPL programs into efficient FORTRAN programs. Since there are many formulas for a given transform, a fast implementation can be obtained by generating alternative formulas and searching for the one with the fastest execution time. This paper presents an application of this methodology to the implementation of the FFT.

AB - This paper discuss an approach to implementing and optimizing fast signal transforms based on a domain-specific computer language, called SPL. SPL programs, which are essentially mathematical formulas, represent matrix factorizations, which provide fast algorithms for computing many important signal transforms. A special purpose compiler translates SPL programs into efficient FORTRAN programs. Since there are many formulas for a given transform, a fast implementation can be obtained by generating alternative formulas and searching for the one with the fastest execution time. This paper presents an application of this methodology to the implementation of the FFT.

UR - http://www.scopus.com/inward/record.url?scp=23044531966&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23044531966&partnerID=8YFLogxK

U2 - 10.1007/3-540-45574-4_8

DO - 10.1007/3-540-45574-4_8

M3 - Conference contribution

AN - SCOPUS:23044531966

SN - 3540428623

SN - 9783540455745

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 112

EP - 126

BT - Languages and Compilers for Parallel Computing - 13th International Workshop, LCPC 2000, Revised Papers

A2 - Ferrante, Jeanne

A2 - Midkiff, Samuel P.

A2 - Moreira, Jose E.

A2 - Gupta, Manish

A2 - Chatterjee, Siddhartha

A2 - Prins, Jan

A2 - Pugh, William

A2 - Tseng, Chau-Wen

PB - Springer

T2 - 13th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2000

Y2 - 10 August 2000 through 12 August 2000

ER -

Searching for the best FFT formulas with the SPL compiler

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this