Introduction to MIMD Architectures

Shared Memory: Bus-based

Shared Memory: Extended

Shared Memory: Hierarchical

Distributed Memory: Introduction

Distributed Memory: Hypercube

Distributed Memory: Mesh

Introduction to MIMD Architectures

Multiple instruction stream, multiple data stream (MIMD) machines have a number of processors that function asynchronously and independently. At any time, different processors may be executing different instructions on different pieces of data. MIMD architectures may be used in a number of application areas such as computer-aided design/computer-aided manufacturing, simulation, modeling, and as communication switches. MIMD machines can be of either shared memory or distributed memory categories. These classifications are based on how MIMD processors access memory. Shared memory machines may be of the bus-based, extended, or hierarchical type. Distributed memory machines may have hypercube or mesh interconnection schemes.

Shared Memory: Bus-based

MIMD machines with shared memory have processors which share a common, central memory. In the simplest form, all processors are attached to a bus which connects them to memory. This setup is called bus-based shared memory. Bus-based machines may have another bus that enables them to communicate directly with one another. This additional bus is used for synchronization among the processors. When using bus-based shared memory MIMD machines, only a small number of processors can be supported. There is contention among the processors for access to shared memory, so these machines are limited for this reason. These machines may be incrementally expanded up to the point where there is too much contention on the bus.

Shared Memory: Extended

MIMD machines with extended shared memory attempt to avoid or reduce the contention among processors for shared memory by subdividing the memory into a number of independent memory units. These memory units are connected to the processsors by an interconnection network. The memory units are treated as a unified central memory. One type of interconnection network for this type of architecture is a crossbar switching network. In this scheme, N processors are linked to M memory units which requires N times M switches. This is not an economically feasible setup for connecting a large number of processors.

Shared Memory: Hierarchical

MIMD machines with hierarchical shared memory use a hierarchy of buses to give processors access to each other's memory. Processors on different boards may communicate through internodal buses. Buses support communication between boards. Wiuth this type of architecture, the machine may support over a thousand processors.

Distributed Memory: Introduction

In distributed memory MIMD machines, each processor has its own individual memory location. For data to be shared, it must be passed from one processor to another as a message. Since there is no shared memory, contention is not as great a problem with these machines. It is not economically feasible to connect a large number of processors directly to each other. A way to avoid this multitude of direct connections is to connect each processor to just a few others. This type of design can be inefficient because of the added time required to pass a message from one processor to another along the message path. The amount of time required for processors to perform simple message routing can be substantial. Systems were designed to reduce this time loss and hypercube and mesh are among two of the popular interconnection schemes.

Distributed Memory: Hypercube Interconnection Network

In an MIMD distributed memory machine with a hypercube system interconnection network containing four processors, a processor and a memeory module are placed at each vertex of a square. The diameter of the system is the minimum number of steps it takes for one processor to send a message to the processor that is the farthest away. So, for example, the diameter of a 2-cube is 2. In a hypercube system with eight processors and each processor amd memory module being placed in the vertex of a cube, the diameter is 3. In general, a system that contains 2^N processors with each processor directly connected to N other processors, the diameter of the system is N. One disadvantage of a hypercube system is that it must be configured in powers of two, so a machine must be built that could potentially have many more processors than is really needed for the application.

Distributed Memory: Mesh Interconnection Network

In an MIMD distributed memory machine with a mesh interconnection network, processors are placed in a two-dimensional grid. Each processor is connected to its four immediate neighbors. Wraparound connections may be provided at the edges of the mesh. One advantage of the mesh interconnection network over the hypercube is that the mesh system need not be configured in powers of two. A disadvantage is that the diameter of the mesh network is greater than the hypercube for systems with more than four processors.