Simple Parallel Computer Architectures

• SISD - Single Processor/Single Data (von Neumann)

• SIMD- Single Instruction/Multiple Data

- each instruction broadcast to all processing elements

- all processors must operate in lock-step (such as add two numbers)

- good for vector and array problems

- comes in both shared and distributed memory configurations

• MIMD - Multiple Instruction/Multiple Data

- Shared Memory Multiprocessor

- each processor can run at its own speed

- parallel execution of threads, one per processor

- shared memory space is an advantage for ease of programming

- contention is possible on the shared interconnect and on the shared memory

- maintaining cache coherency

•  Distributed Memory Parallel Computer (multicomputer)
• no contention for distributed memory
• possible contention for interconnection network
• overhead for sending messages between computers
• message preparation time
• message transmission time

• Definitions
• Connectivity - how many processors are directly connected
• Diameter - distance to the furthest processor in terms of intermediate links
• Broadcast time - in terms of how many links must be traversed for a message to go from one processor to all the others

Shared Bus Interconnection

• All messages compete for time on the bus
• Most common architecture - ethernet
• Crossbar switches reduce contention - becoming very popular
• Broadcast time is one link, if no contention
• If contention, keep trying

Ring Interconnection Network

• Messages typically travel in only one direction.
• For n processors the average transmission delay (diameter) is n/2.
• Delay for broadcast and aggregation is n.
• Structure

Mesh Interconnection Network

• Can send messages only to neighbors. Messages to other processors must be send indirectly, with additional transmission overhead.
• In 2D mesh, connectivity is 2 to 4 and diameter is 2*(sqrt(n)-1)

3D Mesh Interconnection

• Connectivity is 3 to 6
• Diameter is 3*(cuberoot(n)-1)

A Torus Interconnection System

• Connectivity is 4
• Diameter is sqrt(n)

3D Cube Interconnection

• Connectivity is 3
• Diameter is 3

4D Hypercube Interconnection

• Connectivity is 4
• Diameter is 4
• General Hypercube: Connectivity and Diameter are log n