Browse Prior Art Database

SYNCHRONOUS PARALLEL COMPUTATION

IP.com Disclosure Number: IPCOM000128248D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 11 page(s) / 40K

Publishing Venue

Software Patent Institute

Related People

Uzi Vishkin: AUTHOR [+3]

Abstract

This survey is motivated by the fact that the tremendous potential power of microstructure technology can be realized only if we find effective parallel architectures and algorithms for utilizing large ` numbers of small but powerful processors. Many groups, including the very active tJYU -Ultraeomputer group , are considering the pragmatic questions involved in the choice of effective parallel architectures. Theoretical studies, like that on which this presentation focuses, can buttress this pragmatic work in two ways: by finding parallel algorithms that use such machines effectively, and by defining abstract models of parallel computing thereby clarifying the "design space" within which the computer architect can make choices.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SYNCHRONOUS PARALLEL COMPUTATION

- A Survey

by

Uzi Vishkin

Courant Institute New York University

(April 1983)

Ultracomputer Note #53 Technical Report - #71 Courant Institute of Mathematical Sciences New York University Department of Computer Science 251 Mercer Street New York, New York Synchronous Parallel Computation - A Survey

Uzi Vishkin Courant Institute, New York Univesity

(April 1983)

I Introduction

This survey is motivated by the fact that the tremendous potential power of microstructure technology can be realized only if we find effective parallel architectures and algorithms for utilizing large ` numbers of small but powerful processors. Many groups, including the very active tJYU -Ultraeomputer group , are considering the pragmatic questions involved in the choice of effective parallel architectures. Theoretical studies, like that on which this presentation focuses, can buttress this pragmatic work in two ways: by finding parallel algorithms that use such machines effectively, and by defining abstract models of parallel computing thereby clarifying the "design space" within which the computer architect can make choices.

These two research directions are in fact closely related. An abstract model of parallel computation is appropriate if it allows many "typical" problems to be handled by parallel algorithms that are as efficient (or very nearly as efficient) as those available in other, perhaps slightly different, models of parallelism. To the extent that such algorithms can be found, an abstract model of parallel computation is justified, and can serve as a basis for the selection of ,optimal architectures. Once such a basis is available, the problem becomes that of implementing the abstract model by machine designs conforming to technological reality. Physical limitations of currently available technologies suggest one, but only one, basic constraint: in a machine built as an assemblage of a large number of processing elements, each processor can be connected only to a fixed number of other processors, and this in a fixed pattern. Each of the research groups working on particular ultraparallel machines has chosen some particular design, conforming to this constraint, that seems to its designers to be particularly advantageous. However, these ad-hoc approaches may ignore design possibilities that are just as attractive as those seized upon. Hence an attempt to elucidate the problems of parallel architecture starting from a more robust theoretical basis is desirable.

New York University Page 1 Dec 31, 1983

Page 2 of 11

SYNCHRONOUS PARALLEL COMPUTATION

The work outlined below reflects this point of view. Existing high-efficiency parallel algorithms are mentioned in the next section. We propose to use these algorithms to discern the significance of differences between abstract models of parallelism. This point is expanded in Section 3 where studies regarding l...