Synthesis of the fast Fourier transform algorithm by functional language program transformation

Author

Sharp, David ; Cripps, Martin

Author_Institution

Dept. of Comput., Imperial Coll. of Sci., Technol. & Med., London, UK

fYear

1993

fDate

27-29 Jan 1993

Firstpage

136

Lastpage

143

Abstract

Presents a technique for systematically synthesizing parallel algorithms starting from a high-level specification of the problem to be solved and a functional abstraction of the target architecture. We show how functional language program transformation can be used to generate various algorithms that match the characteristics of the target architecture and demonstrate the technique by synthesizing various fast Fourier transforms for various parallel architectures from a specification of the discrete Fourier transform

Keywords

fast Fourier transforms; formal specification; functional programming; parallel algorithms; parallel architectures; parallel languages; program processors; discrete Fourier transform; fast Fourier transform algorithm synthesis; functional abstraction; functional language program transformation; high-level problem specification; parallel algorithm synthesis; parallel architectures; target architecture; Biomedical imaging; Computer architecture; Concurrent computing; Discrete Fourier transforms; Educational institutions; Fast Fourier transforms; Parallel algorithms; Parallel architectures; Parallel machines; Signal processing algorithms;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1993. Proceedings. Euromicro Workshop on

Conference_Location

Gran Canaria

Print_ISBN

0-8186-3610-6

Type

conf

DOI

10.1109/EMPDP.1993.336410

Filename

336410