CaltechAUTHORS
  A Caltech Library Service

Portable programming within a message-passing model: the FFT as an example

Walker, David W. (1988) Portable programming within a message-passing model: the FFT as an example. In: C3P Proceedings of the third conference on Hypercube concurrent computers and applications. Vol.2. ACM , New York, NY, pp. 1438-1450. ISBN 0-89791-278-0. http://resolver.caltech.edu/CaltechAUTHORS:20170104-151346384

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170104-151346384

Abstract

This paper describes a portable programming environment for MIMD concurrent processors based on an object-oriented, message-passing paradigm. The basis of this environment is the Virtual Machine Loosely Synchronous Communication System (VMLSCS) which is designed to be used for loosely synchronous problems. VMLSCS is structured to make efficient use of hierarchical memory, and permits communication and calculation to be overlapped on certain concurrent processors. As an example, the use of VMLSCS in performing both one-dimensional and multi-dimensional fast Fourier transforms (FFTs) on concurrent multiprocessors is described. It is shown that all necessary interprocessor communication can be performed by a single routine, vm_index. Thus the construction of a portable concurrent FFT rests on the implementation of vm_index on the target machines. In the multi-dimensional algorithm a strip decomposition is applied to each of the directions in turn so that each of the FFTs performed in a particular direction are done in one processor. This allows fast sequential one-dimensional FFTs to be exploited. The implementation of vm_index on both homogeneous and inhomogeneous hypercubes, and shared memory multiprocessors is discussed.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/63047.63100DOIArticle
http://dl.acm.org/citation.cfm?doid=63047.63100PublisherArticle
Additional Information:© 1988 ACM. The support of the Department of Energy, under grant number DE-FG03-85ER25009, is gratefully acknowledged. I would also like to acknowledge helpful comments by Ed Felten. John Salmon and Stuart Anderson contributed to my understanding of parallel FFT algorithms. Finally, I would like to thank Geoffrey Fox for reading a earlier draft and making valuable suggestions.
Funders:
Funding AgencyGrant Number
Department of Energy (DOE)DE-FG03-85ER25009
Record Number:CaltechAUTHORS:20170104-151346384
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170104-151346384
Official Citation:D. W. Walker. 1989. Portable programming within a message-passing model: the FFT as an example. In Proceedings of the third conference on Hypercube concurrent computers and applications - Volume 2 (C3P), Geoffrey Fox (Ed.), Vol. 2. ACM, New York, NY, USA, 1438-1450. DOI=http://dx.doi.org/10.1145/63047.63100
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73227
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:04 Jan 2017 23:39
Last Modified:04 Jan 2017 23:39

Repository Staff Only: item control page