Table of Contents

Computer Generation of Fourier Transform Libraries for Distributed Memory Architectures

Tuesday Oct. 13, 2009
Hamerschlag Hall D-210
4:00 pm

Vas Chellappa
Carnegie Mellon University


High-performance discrete Fourier transform (DFT) libraries are an important requirement on many computing platforms. The complexity of manually writing and tuning DFT libraries to target architectures is the motivation for the Spiral project, which can automatically generate platform-adapted libraries.

However, current techniques in Spiral don't work well for all target platforms. In particular, several emerging target platforms incorporate a distributed memory parallel processing paradigm, where the cost of accessing non-local memories is relatively high. Traditionally used only in supercomputing environments, the paradigm is now also finding its way into desktop computing (e.g., IBM's Cell processor), GPGPUs, and embedded processors.

The goal of this work is to enable computer generation of high-performance DFT libraries for a wide range of distributed memory parallel processing systems, given only a high-level de-scription of a DFT algorithm and some platform parameters. The main challenges include generating code for multiple target programming paradigms that delivers load balanced parallelization across multiple layers of the compute hierarchy, orchestrates explicit memory management, and overlaps computation with communication.

We attack the problem by building algorithm components that describe parallelization, streaming, and data exchange in a domain-specific declarative mathematical language. We then rewrite existing DFT algorithms to expose these components, which are guaranteed to “fit” the target architecture and extract maximum performance.


Vas Chellappa is a PhD candidate in the Electrical and Computer Engineering department. He works with the SPIRAL group, and is advised by Prof. Markus Püschel. His research interests include pa-rallel and distributed systems, automatic code gen-eration, operating systems, virtualization, and com-puter architecture.

Back to the seminar page