A taxonomy first introduced by Flynn [FLYN72] is still the most common way of
categorizing systems with parallel processing capability. Flynn proposed the following
categories of computer systems:
• Single instruction, single data (SISD) stream: A single processor executes a
single instruction stream to operate on data stored in a single memory.
Uniprocessors fall into this category.
• Single instruction, multiple data (SIMD) stream: A single machine instruction
controls the simultaneous execution of a number of processing elements on a
lockstep basis. Each processing element has an associated data memory, so
that each instruction is executed on a different set of data by the different
processors. Vector and array processors fall into this category, and are discussed
in Section 18.7.
• Multiple instruction, single data (MISD) stream: A sequence of data is transmitted
to a set of processors, each of which executes a different instruction sequence.
This structure is not commercially implemented.
• Multiple instruction, multiple data (MIMD) stream: A set of processors simultaneously
execute different instruction sequences on different data sets. SMPs,
clusters, and NUMA systems fit into this category.
With the MIMD organization, the processors are general purpose; each is able
to process all of the instructions necessary to perform the appropriate data transformation.
MIMDs can be further subdivided by the means in which the processors
communicate (Figure 17.1). If the processors share a common memory, then each
processor accesses programs and data stored in the shared memory, and processors