Scalable Design Principles

Here are the organized notes detailing every topic and chapter structure presented in the document:

Bowie State University — Department of Computer Science

Course Lecture: Scalable Design Principles (Instructor: Hoda El-Sayed)

1. Evolution of Computer Architecture

Computers have developed across five distinct generations:

• First Generation: Utilized vacuum tubes and relay memory; programmed using machine and assembly languages.

  
  

• Second Generation: Utilized discrete transistors and core memory; software developed in Algol and Fortran.

  
  

• Third Generation: Introduced Small-Scale Integrated (SSI) circuits and the C programming language.

  
  

• Fourth Generation: Utilized Very Large-Scale Integrated (VLSI) microprocessors, parallelizing compilers, and message-passing libraries.

  
  

• Fifth Generation: Uses Ultra Large-Scale Integrated (ULSI) circuits, Java, and multithreading.

  
  

2. Scalable Computer Architecture Concepts

• Parallelism & Scalability: Parallelism is a standard feature of modern systems. Scalability incorporates parallelism and allows a system to scale up (increase resources to satisfy higher performance/functionality demands) or scale down (reduce resources to cut costs).

  
  

• Requirements of Scalability:

  
  
  

  • Functionality and Performance: Scaling up should yield a near $n$-times increase in computing power when resources are expanded $n$ times.

    
    

  • Scaling in Cost: Costs associated with scaling up must remain reasonable.

    
    

  • Compatibility: Existing hardware, system software, and application components should remain usable with minimal modifications.

    
    

• The Computer Pyramid:

  
  
  

  • Displays the relationship between sales volume, cost, and performance.

    
    

  • Base: Personal Computers (PCs)—lowest cost, lowest performance, and highest sales volume.

    
    

  • Apex: Supercomputers—highest performance, expensive cost, and lowest sales volume.

    
    

3. Operational Models for Parallel Computers (MIMD Focus)

Multiple Instruction, Multiple Data (MIMD) architectures are categorized by memory organization:

• Taxonomy Breakdown:

  
  
  

  • Shared Address Space (Multiprocessors): Includes NUMA (Non-Uniform Memory Access) and COMA (Cache-Only Memory Architecture).

    
    

  • Multiple Address Spaces (Multicomputers / NORMA): No Remote Memory Access.

    
    

• NUMA Model (Non-Uniform Memory Access):

  
  
  

  • Shared-memory architecture where access time varies depending on the physical location of the memory word.

    
    

  • Local memory is physically attached to individual processors but mapped into a global address space accessible by all processors.

    
    

  • Accessing local memory is faster; accessing remote memory attached to other processors incurs delay through the interconnection network.

    
    

• Hierarchical Cluster Model:

  
  
  

  • Combines distributed memories with global shared memory.

    
    

  • System processors are grouped into clusters (each cluster acts as an UMA or NUMA multiprocessor) connected via a Global Interconnection Network.

    
    

  • Three Memory-Access Speed Levels:

    
    
    

    1. Fastest: Local memory access.

       
       

    2. Intermediate: Cluster shared memory access (CSM).

       
       

    3. Slowest: Global shared memory access (GSM / Remote).

       
       

• Distributed-Memory Multicomputer (NORMA):

  
  
  

  • Consists of autonomous processing nodes linked by a message-passing network.

    
    

  • All local memories are strictly private (No Remote Memory Access).

    
    

  • Communication occurs exclusively via message passing (e.g., Intel Paragon, TMC CM-5, PC clusters).

    
    

4. Performance Attributes & Overhead

Parallel applications execute three distinct categories of operations:

1. Computation Operations: Arithmetic/logic operations, local data transfers, control flow.

   
   

2. Parallelism Operations: Process creation, termination, context switching.

   
   

3. Interaction Operations: Process communication and synchronization.

   
   

• Sources of Overhead: Parallelism and interaction operations introduce system overhead categorized into four types:

  
  
  

  • Parallelism Overhead: Incurred by process management.

    
    

  • Communication Overhead: Incurred by exchanging information between processors.

    
    

  • Synchronization Overhead: Incurred during execution of synchronization barriers/primitives.

    
    

  • Load Imbalance Overhead: Incurred when idle processors wait for busy processors to complete execution.

    
    

5. Physical Machine Models

MIMD systems encompass five primary physical models:

1. Parallel Vector Processor (PVP):

   
   
   

   • Uses pipelining, fast processor tech, static memory, and specialized vector registers.

     
     

   • Replaces loop-based array operations with single vector instructions via high-speed interleaved memory.

     
     

   • Contains dedicated functional units for both scalar and vector operations.

     
     

2. Symmetric Multiprocessor (SMP):

   
   
   

   • Centrally shared memory where all processors have equal access to memory, I/O devices, and OS services.

     
     

   • Generally limited to $\le 64$ processors due to central bus and memory scalability bottlenecks.

     
     

3. Massively Parallel Processor (MPP):

   
   
   

   • Asynchronous MIMD systems using commodity microprocessors with physically distributed memory.

     
     

   • Connected via high bandwidth, low-latency interconnects scaling to hundreds or thousands of processing nodes.

     
     

   • Processes run in private address spaces and synchronize via blocking message-passing operations.

     
     

4. Distributed Shared Memory (DSM):

   
   
   

   • Memory is physically distributed among nodes, but software/hardware directory structures present a single, logically shared memory space to the programmer.

     
     

5. Cluster of Workstations (COW):

   
   
   

   • Collection of standalone workstations (processor, cache, memory, disk, OS) linked via low-cost standard networking (e.g., Ethernet, ATM) without standard peripherals like monitors or keyboards.

     
     

6. Scalable Design Principles

Four core principles govern high-performance scalable design:

1. Principle of Independence:

   
   
   

   • System components (hardware and software) should operate with minimal mutual dependence.

     
     

   • Scaling one dimension (e.g., adding nodes or upgrading a CPU) should not require rewriting applications, updating the OS, or altering the network topology.

     
     

   • Examples: The Internet (host/hardware independent) and MPI (uses orthogonal concepts: data types, communication operations, communicators, virtual topologies).

     
     

2. Principle of Balanced Design

   
   
   

   
   

3. Principle of Design Scalability

   
   
   

   
   

4. Principle of Latency Hiding

   
   
   

   
   

7. Performance Issues & Analysis Example

• Performance evaluation for expression: $Y = (a \times b) + (c / d) + e$

  
  
  

  
  
  

  • Sequential Execution ($T_{\text{sequential}}$): 4 cycles

    
    

  • Parallel Execution ($T_{\text{parallel}}$): 3 cycles (across 2 units)

    
    

  • Speedup ($S$): $T_{\text{seq}} / T_{\text{par}} = \frac{4}{3} \approx 1.33$

    
    
    

    
    

  • Efficiency ($E$): $\frac{\text{Speedup}}{\text{Processors}} = \frac{4/3}{2} = 0.66$ ($66\%$)

    
    

  • Throughput: $\frac{4}{3}$ operations per cycle

    
    

8. Parallel Programming Models

Parallel models expose hardware traits to allow efficient mapping while remaining architecture-independent for portability:

• Message Passing Model (e.g., MPI):

  
  
  

  • Concurrent sequential processes running in private address spaces cooperating via explicitly coded send and receive operations.

    
    

  • Generates high communication overhead, particularly for frequent, small messages.

    
    

• Shared Memory Model (e.g., OpenMP):

  
  
  

  • Independent threads operating inside a single, unified address space.

    
    

  • Easy to program (remote vs. local access is transparent), but hard to exploit inherent data locality, leading to unnecessary remote memory requests.

    
    

• Data Parallel Model (e.g., HPF):

  
  
  

  • Single execution stream where individual instructions operate concurrently on large datasets.

    
    

  • Cannot easily handle independent conditional branching within executing processes.

    
    

• Distributed Shared Memory Model (e.g., Unified Parallel C / UPC):

  
  
  

  • Combines the usability of shared memory with the locality control of message passing.

    
    

  • Shared address space is logically partitioned; threads bind to specific memory partitions to avoid unnecessary remote accesses.