Accession Number : ADA534686


Title :   Computer Generation of Fourier Transform Libraries for Distributed Memory Architectures


Descriptive Note : Doctoral thesis


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING


Personal Author(s) : Chellappa, Srinivas


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a534686.pdf


Report Date : Dec 2010


Pagination or Media Count : 160


Abstract : High-performance discrete Fourier transform (DFT) libraries are an important requirement for many computing platforms. Unfortunately, developing and optimizing these libraries for modern complex platforms has become extraordinarily difficult. To make things worse, performance often does not port, thus requiring permanent re-optimizations. Overcoming this problem has been the goal of SPIRAL, a library generation system that can produce highly optimal DFT code from a high level specification of algorithms and target platforms. However, current techniques in SPIRAL cannot support 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, and handling data movement is exposed to the programmers. Traditionally used only in supercomputing environments, this paradigm is now finding its way in the form of multicore processors into desktop computing. The goal of this work is the computer generation of high-performance DFT libraries for a wide range of distributed memory parallel processing systems, given only a high-level description of a DFT algorithm and some platform parameters. The key 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 this problem by first developing a formal framework to describe parallelization streaming, and data exchange in a domain-specific declarative mathematical language. Based on this framework, we develop a rewriting system that structurally manipulates DFT algorithms to match them to a distributed memory target architecture and hence extracts maximum performance.


Descriptors :   *COMPUTER ARCHITECTURE , *FOURIER TRANSFORMATION , DISTRIBUTED DATA PROCESSING , TARGET ACQUISITION , DISCRETE FOURIER TRANSFORMS , THESES , MEMORY DEVICES , MICROCOMPUTERS , LIBRARIES , INFORMATION EXCHANGE , ALGORITHMS , MULTIPLE TARGETS


Subject Categories : Numerical Mathematics
      Computer Hardware


Distribution Statement : APPROVED FOR PUBLIC RELEASE