Parallel Computer Architectures Overview

Architectures

• Several types of architectures are mentioned, including SIMD and MIMD.
• Massive parallel systems are discussed.
• Basic components of a parallel computer include processors, an interconnection network, and memory.

General Structure of a Parallel Computer

• Memory stores data and instructions.
• An interconnection network connects processors and memory.
• Processing elements (PEs) are the processors. Multiple PEs are represented in diagrams.

Plan

• A plan for the study of parallel computer architectures is outlined.
• Topics include introductory concepts, SIMD/MIMD architectures, fundamental processors, interconnection networks, memory organization, and examples of parallel computer architectures.

Bibliography

• A list of books and articles relevant to parallel processing is provided.
• Authors and titles of works are listed, including several references on specific architectures.

Classification (1)

• Flynn's taxonomy categorizes computers based on instruction and data streams.
• SISD (Single Instruction stream, Single Data stream)
• SIMD (Single Instruction stream, Multiple Data stream)
• MIMD (Multiple Instruction stream, Multiple Data stream)
• Kuck further classifies systems.

Memory Organization

• Shared memory: A single address space shared by all processors. Access time is less dependent on processor and memory location.
• Distributed memory: Each processor has its own separate address space. Access time depends on both processor and memory location.

Pipeline

• A pipeline breaks down operations into stages for efficient execution.
• Example is a floating-point adder with four stages (exponent subtraction, mantissa alignment, mantissa addition, normalization).
• It is applicable to both floating-point and memory operations.

Pipeline (suite)

• Example code demonstrates parallel calculations.
• Data dependencies and stage lengths for calculations are represented.

Pipeline (suite)

• Mathematical formulas describe execution time.
• Quantities such as T (max time for the stages), n (total operations), and α (fixed overheads) are present.
• There are formulas to help describe theoretical peak speed.

Parallelism Between Functional Units

• Multiple independent functional units can execute instructions concurrently.
• Examples include adders, multipliers, and I/O units.
• Pipeline parallelism can be used as well.

SIMD Machines

• Fundamental principle: All processors execute the same instruction simultaneously on different data.
• Instruction broadcast to all processors.
• Memory is structured in banks.
• Interconnection network used for re-sequencing.
• Operating in blocks of P elements.

SIMD Machines (suite)

• Data layout in different memory banks and parallel execution (SIMD) is described using diagrams.
• Potential issues, such as memory bank conflicts, are recognized and discussed.

SIMD Machines (suite)

• Further explanation on data layout in memory banks.
• Demonstrates potential conflicts if data is not properly allocated.

SIMD Machines (suite)

• Explanation of how data should be structured for SIMD operations to work optimally.

SIMD Machines (suite)

• In the case when an instruction involves a conditional check, the conditional and result operations will be done in parallel for the processors.

SIMD Characteristics Summary

• SIMD's strengths include simplicity, modularity, and high throughput for handling large amounts of data.
• SIMD's weaknesses include limitations in handling various computation tasks, limited flexibility in program design, and specialization of architecture.

MIMD with Shared Memory

• Completely independent processors, with a shared address space.
• Uniform access time to the shared memory.
• Communication relies on the interconnection network, similar to a telephone switchboard.
• Data transfer between processors is not explicit.

MIMD with Distributed Memory

• Fully independent and autonomous processors each with own address space.
• Memory allocated to processors.
• Processors communicate with each other using messages through interconnection network.
• Explicit movement of data between processes.

Topologies for Distributed Memory

• Different network topologies (2D mesh, 3D mesh, torus, and hypercube).
• Diagrams illustrate processor and memory connections.

Topology and Hypercubes

• Hypercubes are a common topology for distributed memory machines.
• Processor and memory connections and communication links are elaborated.
• Diagrams demonstrate details on connections and communication links.

Overview of MIMD Machines with Shared Memory

• Advantages in simplicity and programming and lack of required data movement.
• Disadvantages include potential performance bottlenecks due to shared memory contention or network congestion in certain situations

Overview of MIMD Machines with Distributed Memory

• Advantages include scalability, potential for faster data access, and flexibility in design.
• Disadvantages include the complexity of programming that may be required as well as message communication overhead.

Element Processors (SIMD Case)

• Dedicated processors (1 bit, 4 bits, or those with specialized floating-point units) can reduce control logic complexity.
• Integration of multiple processors onto a single chip is possible.

Element Processors (MIMD Case)

• General-purpose processors are common.
• Modern processors have tools for parallel execution.
• Communication mechanisms (e.g., Direct Connect Routing Module) may be needed.
• Coprocessor support for certain operations (vector operations) can be added or integrated.

Parallel Algorithm

• Using parallelism significantly affects system performance.
• Measuring algorithm efficiency requires considering data size, parallelism degree in an algorithm, and data transfer.

Parallel Algorithm (Definitions)

• Key definitions for assessing parallel execution: Sequential execution time, time using a parallel approach, speedup, and efficiency.

Parallel Algorithm (Properties)

• Important characteristics for parallel algorithms include upper bounds on speedup and efficiency.

Vector Operations

• Operations on multiple values simultaneously
• Examples demonstrate how single-value mathematical operations can be performed on vectors
• Concepts such as vector lengths and incrementing steps are important
• A variety of operations are shown

Vector Operations (Examples)

• Examples of vector operations, including component-wise arithmetic, scalar operations with vectors and reduction operations.

Software View of Vector Operations

• Software instructions sequence to perform vector operations.
• Instructions for storing and loading vector operations steps.

Mask

• Mask (VM) is a vector of bits used to control vector operations.
• When VM is 1, specific element is computed.
• Useful for controlling which elements are modified.
• Useful to filter data in vector operations.

Examples

• Examples that use masks to describe steps in conditional statements operating on vectors.

This quiz covers key concepts in parallel computer architectures, including SIMD and MIMD systems. It explores the general structure of parallel computers, the role of processing elements, and interconnection networks. Additionally, it provides a plan for studying various architectures as well as a bibliography of relevant literature.