Generating Efficient Programs for Two-Level Memories from Tensor-products.
Sandeep K. S. Gupta, Zhiyong Li, John H. Reif · 1995
This paper presents a framework for synthesizing efficient outof -core programs for block recursive algorithms such as the fast Fourier transform (FFT) and Batcher's bitonic sort. The block recursive algorithms considered in this paper are described using tensor (Kronecker) product and other matrix operations. The algebraic properties of the matrix representation are used to derive efficient out-of-core programs. These programs are targeted towards a two-level disk model which allows HPF supported cyclic(B) data distribution on a disk array. The effectiveness of our approach is demonstrated through an example out-of-core FFT program implemented on a work-station. Keywords: Parallel I/O, parallelizing compilers, tensor product, FFT computation. 1. Introduction Massively parallel computers intend to provide solutions for the large-scale scientific applications such as the Grand Challenge Problems like computational fluid dynamics and seismic signal processing. These applications requ...