Parallel Computer Hardware

Introduction

Networks of workstations, massively parallel supercomputers, and multiprocessor workstations are just a few of the dozens of different parallel architectures. We need to get a handle on all of these architectures without making a career out of the analysis. To turn this into a manageable task, we will organize parallel systems into a coherent and simple taxonomy.

Our primary interest in parallel computer taxonomies is to help us understand the pertinent issues raised by parallel computer hardware. An additional motivation, however, is to support completeness arguments. To make an argument about the general applicability of a technology (e.g. an algorithm or a programming model), you need some way to quantify completeness. By analyzing the technology against each leaf in a complete taxonomy, you can quantify completeness.

Flynn's Taxonomy

By far the most commonly used taxonomy is that due to Flynn [Flynn]. He categorizes all computers according to how many instruction streams and data streams they can be said to have. In Flynn's taxonomy, there are four possibilities:

• SISD: Single Instruction, Single Data. The standard von Neumann model.
• SIMD: Single Instruction, Multiple Data. The original systems from Thinking Machines or MasPar.
• MISD: Multiple Instruction, Single Data: No well known systems fit this designation.
• MIMD: Multiple Instruction, Multiple Data: MPPs, workstation clusters, shared-memory SMPs.

The advantage of the Flynn taxonomy is that it is very well established. Every parallel programmer is familiar with the terms MIMD and SIMD. It also meets most of our other criteria.

There are, however, some serious problems with Flynn's system. The biggest problem is that he only provides four slots to plug systems into. This granularity doesn't give us enough ways to separate systems. The problem is further exacerbated by the inapplicability of MISD and the demise of SIMD systems. In some ways, Flynn's system is akin to dividing all computers into the two categories, parallel and sequential.

Our Parallel Hardware Taxonomy

Unfortunately, computer scientists haven't converged on a single taxonomy for parallel computers. The only consensus is to use Flynn's taxonomy [Flynn72] as a starting point. There also seems to be wide agreement on the following additional points:

• There is no need to further break down the SIMD category
• MIMD systems can be divided coarsely based on memory organization:

• Shared Memory
• Distributed Memory

For most cases, this is enough. When it is necessary to break it down further, there is no clear consensus. We propose the following approach:

• Shared-memory systems can be divided into the following three categories:

• SMP: Symmetric multiprocessing. The memory is physically shared, and all processors access the memory equally at equal speeds.
• NUMA: Non-uniform memory access. The memory is physically shared, but not distributed in a 1:1 relation with the processors. Access to different portions of the memory may require significantly different times.
• DSM: Distributed shared memory. The memory is distributed among the processors, but the system gives the illusion that it is shared.

• Distributed-memory systems can be divided into the following three categories:

• Fixed: The number of connections is fixed as more processors are added (e.g., Ethernet-connected workstations, since the Ethernet interconnection is a single resource that all processors share).
• Linear: The number of connections grows linearly with the number of nodes (e.g., mesh-connected multicomputers such as the Intel Paragon).
• Scalable - number of connections grows as P log P or greater (e.g., hypercubes such as the Intel iPSC/860).

This results in the following taxonomy of parallel systems:

To help us make sense of this taxonomy, here are some examples of common systems mapped onto the taxonomy.