▶ 目录 ← 首页
CS61C

Flynn's Taxonomy

Learning Outcomes

  • Explain what “parallelizing a program” means.
  • Identify the four different categories of Flynn’s Taxonomy: SISD, SIMD, MISD, and MIMD.
🎥 Lecture Video

Can we be more efficient in writing sequential C code on a serial processor? We discussed some optimizations in an earlier section. We can write assembly code and do better with “micro” optimizations like loop unrolling—but in general, compilers are pretty good nowadays and it’s not that easy to beat them. We can rewrite our programs to make better use of the memory hierarchy, like we explored with our cache blocking exercise earlier.

But how do we leverage hardware improvements? That is the topic of this section.

Parallelism: Software vs. Hardware

Because of the abrupt shift in processor design towards parallelism, there are a LOT of closely related terms when it comes to paralellism. #tab-hw-sw-parallelism is an adaptaion of P&H 6.1 to clarify the terms used in software versus hardware. The biggest confusion is often between concurrency and parallelism.1

Notes:

  • Software is inherently sequential or concurrent.
  • Hardware is serial or parallel.
  • Concurrent software can run on serial and parallel hardware; similarly, sequential software can run on serial and parallel hardware.
  • “Parallelizing” a program colloquially means figuring out how to write a software program to run efficiently on parallel hardware. This can involve making naturally sequential software have high performance on parallel hardware, or to make concurrent processors have high performance on multicore systems as the number of cores (processors) increases.

The last of these points is the most important.

Flynn’s Taxonomy

Now let’s shift towards classifying serial and parallel hardware using Flynn’s Taxonomy.2 There are four entries in #tab-flynn-taxonomy that classify different levels of parallelism based on data streams and instruction streams.

  • SISD (Single Instruction, Single Data, pronounced “SIS-dee”): A serial computer that exploits no parallelism in either the instruction or data streams.
  • SIMD (Single Instruction, Multiple Data, pronounced “SIM-dee”): Computer that applies a single instruction stream to multiple data streams for operations that may be naturally parallelized.
  • MISD (Multiple Instruction, Single Data, pronounced “MIZ-dee”): Exploits multiple instruction streams against a single data stream for data operations that can be naturally parallelized.
  • MIMD (Multiple Instruction, Multiple Data, pronounced “MIM-dee”): Multiple autonomous processors simultaneously executing different instructions on different data.

Toggle the tabs below to discover examples of each type of architecture.

SISD

Flynn taxonomy SISD diagram with a data pool on the left and an instruction pool on the top that both feed into a processor unit box in the center.

SISD: Single Instruction/Single Data Stream

SISD Uses

A sequential processor steps through the instruction pool, matches it with the data in memory, and processes each instruction-data pair one at a time.

  • Our RISC-V processor (single-cycle or five-stage pipeline)
  • (out of scope) Superscalar processors because the programming model is sequential
SIMD

Flynn taxonomy SIMD diagram a data pool on the left that feeds into four parallel processor unit boxes in the center. A single instruction pool at the top similarly feeds into the four parallel processor units.

SIMD: Single Instruction/Multiple Data Stream

SIMD Uses

Issue one instruction (e.g., “add”) that operates on multiple data pairs at the same time. Useful for neural nets, imaging, and scientific applications.

  • Intel SIMD instruction extensions (see later section on Intel intrinsics)
  • NVIDIA Graphics Processing Unit (GPU)3
MISD

Flynn taxonomy MISD diagram with a single stream data pool that feeds into one processor unit and then the other, and an instruction pool that feeds into both processor units in parallel.

MISD: Multiple Instruction/Single Data Stream

MISD Uses

None nowadays.

  • Historical significance, e.g., certain kinds of array processors
  • Professor Nikolic: “It’s like whether you’d like your eggs scrambled or sunny side up and saying, ‘both’.”
MIMD

Flynn taxonomy MIMD diagram with a data pool that feeds four streams of data through four parallel processor units and then another four parallel processor units, and an instruction pool that feeds the first set of processor units in parallel and the second set of four processor units in parallel with a second instruction stream.

MIMD: Multiple Instruction/Multiple Data Stream

MIMD Uses

Anything system involving multiple processors operating concurrently.

  • Multicore processors (e.g., modern laptops)
  • Warehouse Scale Computers (e.g., datacenters)

Over the next few lectures, we will explore these architectures and write programs that exploit the hardware parallelism available. Stay tuned!!!

Footnotes

  1. For more about concurrency and parallelism, see StackOverflow. ↩

  2. Professor Michael J. Flynn was Professor Emeritus at Stanford University. In 1962, he proposed a taxonomy of computer architectures. Flynn’s taxonomy is still used today to describe modern processors. Wikipedia ↩

  3. See NVIDIA Graphics Cards. ↩

  4. For what it’s worth, most programs written today assume a SPMD (single program, multiple data) model. With SPMD, we write a single program that uses multiple degrees of parallelism across processors of a MIMD computer with some cross-processor coordination. ↩