Parallel Algorithms for Networks of Processsors

In CRC Handbook of Algorithms and Theory of Computation, 1999,
M.J. Atallah, ed., pp. 46:1-46:19.

Algorithmic Techniques for Networks of Processors

Russ Miller
Dept. of Computer Science, State University of New York at Buffalo

Quentin F. Stout
EECS Department, University of Michigan

Abstract: This chapter is concerned with designing algorithms for machines constructed from multiple processors. In particular, we discuss algorithms for machines in which the processors are connected to each other by some simple, systematic, interconnection pattern. For example, consider a chess board, where each square represents a processor (for example, a processor similar to one in a home computer) and every generic processor is connected to its 4 neighboring processors (those to the north, south, east, and west). This is an example of a mesh computer, a network of processors that is important for both theoretical and practical reasons.

The focus of this chapter is on algorithmic techniques. Initially, we define some basic terminology that is used to discuss parallel algorithms and parallel architectures. Following this introductory material, we define a variety of interconnection networks, including the mesh (chess board), which are used to allow processors to communicate with each other. We also define an abstract parallel model of computation, the PRAM, where processors communicate with memory instead of with each other. We then discuss several parallel programming paradigms, including the use of high-level data movement operations, divide-and-conquer, pipelining, and master-slave. Finally, we discuss the problem of mapping the structure of an inherently parallel problem onto a target parallel architecture. This mapping problem can arise in a variety of ways, and with a wide range of problem structures. In some cases, finding a good mapping is quite straightforward, but in other cases it is a computationally intractable NP-complete problem.

Keywords: parallel algorithms, parallel computing, parallel architecture, mesh computer, hypercube, pyramid, pipelineing, distributed memory, shared memory, NUMA, global operations, stepwise simulation, mapping problem, weak embedding, supercomputing, computer science

Full paper (Postscript)
Full paper (PDF)

Links To Related Work in Parallel Computing

A modest explanation of parallel computing.
A tutorial on parallel computing.
An overview of our work, and relevant papers.