CaltechAUTHORS
  A Caltech Library Service

Optimal communication algorithms for regular decompositions on the hypercube

Fox, G. C. and Furmanski, W. (1988) Optimal communication algorithms for regular decompositions on the hypercube. In: C3P Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues. Vol.1. ACM , New York, NY, pp. 648-713. ISBN 0-89791-278-0. http://resolver.caltech.edu/CaltechAUTHORS:20161024-160633284

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:20161024-160633284

Abstract

We discuss optimal communication and decomposition algorithms for a class of regular problems on concurrent computers with a hypercube topology, using a general technique we call the method of cube geodesics. We address the calculation of various transformations (convolutions, functionals etc.) of data distributed over the hypercube; examples are the Fast Fourier Transform, matrix algorithms, global scalar products and vector sums, sorting. These all involve long distance inter-node interactions and require more intricate communication that the simple local problems with static spatial decomposition such as partial differential equations. We believe that our library of optimal communication routines is applicable to these and many other problems. The simple example of a database application is sketched. We implement the algorithms on the Caltech/JPL Mark II hypercube and present a detailed performance analysis.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/62297.62389DOIPaper
http://dl.acm.org/citation.cfm?doid=62297.62389PublisherPaper
Additional Information:© 1988 ACM. Work supported in part by DOE grant DE-FG03-85ER25009, the Program Manager of the Joint Tactical Fusion Office, and the ESD division of the USAF, as well as grants from IBM, and SANDIA.
Funders:
Funding AgencyGrant Number
Department of Energy (DOE)DE-FG03-85ER25009
Joint Tactical Fusion OfficeUNSPECIFIED
U.S. Air ForceUNSPECIFIED
IBMUNSPECIFIED
Sandia National LaboratoriesUNSPECIFIED
Record Number:CaltechAUTHORS:20161024-160633284
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20161024-160633284
Official Citation:G. C. Fox and W. Furmanski. 1988. Optimal communication algorithms for regular decompositions on the hypercube. In Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues - Volume 1 (C3P), Geoffrey Fox (Ed.), Vol. 1. ACM, New York, NY, USA, 648-713. DOI=http://dx.doi.org/10.1145/62297.62389
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71418
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:24 Oct 2016 23:16
Last Modified:24 Oct 2016 23:16

Repository Staff Only: item control page