Parallel Processing: Computer Organization and Architecture Notes

Fundamental Concepts of Parallel Processing and Stream Classification

• Criteria for Classification: The organization of a computer system is classified based on the number of instructions and data items that can be manipulated simultaneously.
• Instruction Stream: Defined as the sequence of instructions read from the memory.
• Data Stream: Defined as the operation performed on data in the processor.
• Occurrence of Parallel Processing: Parallelism may occur in the instruction stream, the data stream, or both simultaneously.

Flynn’s Taxonomy: Multiple Processor Organizations

• Single Instruction, Single Data Stream (SISD):
  • Instructions are executed sequentially.
  • A single processor executes a single instruction stream to operate on data stored in a single memory.
  • Uniprocessors fall into this category.
  • Architectural components include:
    • CU: Control Unit.
    • PU: Processing Unit.
    • MU: Memory Unit.
    • IS: Instruction Stream.
    • DS: Data Stream.
    • LM: Local Memory.
• Single Instruction, Multiple Data Stream (SIMD):
  • A single machine instruction controls the simultaneous execution of multiple processing elements on a lockstep basis.
  • Each processing element has an associated data memory.
  • Each instruction is executed on a different set of data by different processors.
  • Applications: Specifically used for Vector and Array processing.
  • SIMD with Distributed Memory: Features a single CU directing multiple $PU_n$ blocks, each with its own $LM_n$, through shared Instruction Streams ($IS$) and unique Data Streams ($DS$).
• Multiple Instruction, Single Data Stream (MISD):
  • Consists of a sequence of data transmitted to a set of processors.
  • Each processor executes a different instruction sequence.
  • It is considered to be of theoretical interest only; no practical organization has been successfully constructed, and it is unclear if it has ever been implemented.
• Multiple Instruction, Multiple Data Stream (MIMD):
  • A set of processors simultaneously executes different instruction sequences on different sets of data.
  • Several programs can execute at the same time.
  • Most modern multiprocessors belong to this category.
  • MIMD with Distributed Memory: Also known as loosely coupled systems. Examples include clusters and Nonuniform Memory Access (NUMA) nodes where each unique $CU_n/PU_n$ pair has its own $LM$ and interacts via an interconnection network.
  • MIMD with Shared Memory: Also known as tightly coupled systems. Processors ($PU_n$) and their respective Control Units ($CU_n$) share a common memory through a bus or network.

Taxonomy of Parallel Processor Architectures

• SISD: Uniprocessor.
• SIMD: Vector Processor, Array Processor.
• MISD: (No practical implementation).
• MIMD:
  • Shared Memory (Tightly Coupled): Symmetric Multiprocessor (SMP), Nonuniform Memory Access (NUMA).
  • Distributed Memory (Loosely Coupled): Clusters.

Tightly Coupled Multiprocessors: Symmetric Multiprocessors (SMP)

• General Characteristics:
  • Processors share the main memory and communicate through it.
  • All processors are connected via an interconnection network (typically a shared bus).
  • The system includes shared I/O subsystems and adapters.
• Specific SMP Characteristics:
  • A stand-alone computer with two or more similar processors of comparable capacity.
  • Processors share the same memory and I/O facilities.
  • Internal connection is usually via a bus.
  • Memory Access Time: Approximately the same for each processor.
  • I/O Access: All processors share access to I/O, either through the same channels or different channels providing paths to the same devices.
  • Symmetry: All processors can perform the same functions.
  • Control: The system is controlled by an integrated operating system that provides interaction between processors at the job, task, file, and data element levels.
• Advantages of SMP:
  • Performance: Better performance than a single processor if work can be organized in parallel.
  • Availability: Failure of a single processor does not halt the machine; it continues at reduced performance.
  • Incremental Growth: Users can enhance performance by adding additional processors.
  • Scaling: Vendors can offer products with varying price and performance points based on the number of processors.

Loosely Coupled Multiprocessors: Clusters

• Definition: A group of interconnected, whole computers working together as a unified computing resource, creating the illusion of being a single machine.
• Scale: Can range from tens to hundreds or thousands of machines, where each machine may itself be a multiprocessor.
• Purpose: Spans from general business needs (web-service support) to computation-intensive scientific calculations.
• Architecture Types:
  1. High Performance.
  2. High Availability.
  3. Load Balancing.
• Structure: Includes sequential or parallel applications, cluster middleware (providing a Single System Image and Availability Infrastructure), and nodes (PC/Workstation) containing communication software ($Comm SW$) and Network Interface Hardware ($Net. Interface HW$) connected via a High-Speed Network/Switch.
• Benefits:
  • High Processing Speed: Superior throughput for demanding tasks.
  • Scalability: Both absolute and incremental scalability (adding nodes easily).
  • High Availability: Acts as a backup system in the event of failure.
  • Cost-Effectiveness: Processing power is cheaper compared to a mainframe; superior price/performance ratio.
• Drawback: High cost associated with implementation and maintenance.

Comparison: SMP vs. Clusters

• SMP Pros:
  • Easier to manage and control.
  • Closer to single processor systems in logic.
  • Scheduling is the main software difference.
  • Requires less physical space and has lower power consumption.
• Cluster Pros:
  • Superior incremental and absolute scalability.
  • Lower initial cost for equivalent power.
  • Superior availability and built-in redundancy.

Nonuniform Memory Access (NUMA)

• Definition: A tightly coupled alternative to SMP and Clusters where all processors have access to all parts of memory using load and store instructions.
• Key Distinction: Access time of processors differs depending on the region of memory being accessed.
• Motivation:
  • SMP has a practical limit of between $16$ and $64$ processors due to bus traffic limits.
  • Clusters have nodes with their own memory, meaning applications do not see a large global memory, and coherence is managed by software.
  • NUMA retains the "SMP flavor" (global memory) while allowing large-scale multiprocessing by permitting nodes with their own internal buses.
• Cache Coherent NUMA (CC-NUMA): Cache coherence is maintained among the caches of the various processors using hardware (often involving a Directory to track cache states across the Interconnect Network).
• Pros and Cons of NUMA:
  • Pros: Potentially effective performance at higher levels of parallelism than a standard SMP.
  • Cons:
    • Performance can break down if there is excessive access to remote memory.
    • Requires L1 and L2 cache designs to reduce memory access.
    • Software must exhibit good temporal locality.
    • Not transparent: Changes in page allocation, process allocation, and load balancing can be difficult and are not well-supported by many software environments.