Algorithms and Parallel Computing

3.2 PARALLEL COMPUTING

We attempt in this section to show the different design options available to construct a parallel computer system. The most famous processor taxonomy was proposed by Flynn [26] based on the data and the operations performed on this data:

1. Single instruction single data stream (SISD). This is the case of the single processor.

2. Single instruction multiple data stream (SIMD). All the processors execute the same instruction on different data. Each processor has its own data in a local memory, and the processors exchange data among themselves through typically simple communication schemes. Many scientific and engineering applications lend themselves to parallel processing using this scheme. Examples of such applications include graphics processing, video compression, medical image analysis, and so on.

3. Multiple instruction single data stream (MISD). One could argue that neural networks and data flow machines are examples of this type of parallel processors.

4. Multiple instruction multiple data stream (MIMD). Each processor is running its own instructions on its local data. Examples of such parallel processors are multicore processors and multithreaded multiprocessors in general.

Flynn’s classification is a bit coarse, and we would like to explore more the space of parallel computers, which comprises the SIMD and MIMD categories, in more detail. The issue of synchronization among processors was not part of the classification criteria used by Flynn. ...