Introduction

The major shifts in computing go through the Dawning Age of the 1950s; the Age of Mainframes in the 1960s; the Age of Minis in the 1970s; the Age of Personal Computers in the 1980s; and finally, the Age of Parallel Computers in the 1990s. Today and tomorrow, Experts predict that by the year 2000, parallel computing will be as mainstream as personal computers were in 1989 \cite{[LeEl92]}. Parallel/distributed computing is not only a new technique, but also a new thinking methodology. It requires and trains people to break the limitations of time and space, to cooperate multiple events all at once, to pursue highest efficiency and load balancing in a computing system. It will reinitialize the entire computer science and related fields.

Why parallel programming

There are two reasons to promote parallel programming--limitations due to the laws of physics and economic efficiency.

Technical reason--Physics limitations
A computer is an electronic device manipulating human beings' symbols. The electronic speed could be approximately equal to the speed of light that is 3 x 10^{8} meters per second. Assume that an electronic device can perform 10^{12} operations per second, it takes longer for a signal to travel between two such devices one-half of a millimeter apart (1.6 x 10^{-12} second) than it takes for either of them to process it (10^{-12} second). That is, the electronic speed cannot match the speed of a device which performs 10^{12} operations per second. The further reduction of distance between such devices reaches a point beyond which they begin to interact, thus reducing not only their speed but also their reliability.
On the other hand, a satellite in outer space is collecting data at the rate of 10^{10} bits per second. In order for this information to be used in a timely fashion, it needs to be processed at a speed of at least 10^{13} operations per second. A team of surgeons who wish to view an organ in living detail require a minimum processing speed of 10^{15} operations per second. Clearly, information explosion requires high computing speed, but device speed is limited by the speed of light.
Economic reason---cost/performance ratio
The cost/performance ratio of small computers plus networks (parallel/distributed computers) is better than that of central main frames.
Efforts that are made to beat the limitation of hardware result in the creation of multiprocessors and multicomputers. The new architectures will be summarized in the next chapter.

What is parallel programming

The new architectures of hardware support and require new software. The new programming methods are known as parallel programming.

Parallel programming is partitioning scheduling the execution of these smaller sub-programs (processes) onto multiple processors in parallel to solve the problem. The result of this procedure is a parallel algorithm.

We are going to separate parallel algorithm design into two steps. The first step, partitioning, can be done in a machine-independent manner. Only the second step, scheduling, must be related to a physical computing environment since we need to map the multiprocesses onto a multiprocessor or a multicomputer architecture.

Performance measurements

The purpose of parallel programming is to speed up the execution of a process. The partitioning provides the possibility and the scheduling realizes the speedup. Speedup will be affected by many factors and will be stated later.