HPCA

Unit I
Introduc on
Computer Technology and Architecture

 Rapid progress:

o Computers have improved greatly in the past 70 years.

o A $500 phone today equals the performance of a $50 million supercomputer from 1993.

o Progress comes from both technology and computer architecture.

 Early years (first 25 years):

o Both technology and architecture improved performance by about 25% per year.

 Microprocessor era (from late 1970s):

o Microprocessors used advances in integrated circuits (ICs).

o Performance grew about 35% per year.

o Mass produc on made microprocessors cheaper.

 Two key market changes:

1. Assembly language was replaced by higher-level programming → less need for object-code
compa bility.

2. Standardized OS like UNIX/Linux reduced risk of new architectures.

 RISC (Reduced Instruc on Set Computer):

o Emerged in the early 1980s.

o Used simpler instruc ons for faster execu on.

o Focused on:

 Instruc on-Level Parallelism (ILP): via pipelining and mul ple instruc on issue.

 Caches: for faster data access.

o Forced other architectures to adopt RISC ideas.

 Examples:

o Digital VAX failed to compete → replaced by RISC.

o Intel translated x86 instruc ons internally into RISC-like ones.

o ARM (a RISC architecture) dominated low-power devices like smartphones.

 Performance growth:
 o Architectural and organiza onal improvements led to 17 years of 50% annual growth in
performance.

o Resulted in:

1. Higher compu ng power for users.

2. New computer classes – PCs, worksta ons, smartphones, tablets.

3. Microprocessors domina ng all computer types (servers, mainframes, supercomputers).

4. So ware evolu on – programmers traded performance for produc vity.

 So ware impact:

o Use of managed languages (Java, Scala).

o Rise of scrip ng languages (Python, JavaScript).

o Use of JIT (Just-In-Time) and trace-based compilers.

o Shi to So ware as a Service (SaaS) over the Internet.

 Changing applica ons:

o Focus on speech, sound, image, and video.

o Example: Google Translate – uses phone camera, cloud compu ng, and transla on in real-
me.

 End of the hardware boom:

o Around 2004, two key trends stopped:

1. Dennard Scaling – power density no longer constant; couldn’t keep reducing voltage/current.

2. Moore’s Law – transistor count no longer doubles every two years.

 Consequences:

o Industry shi ed from single fast processors to mul -core processors.

o Focus moved from ILP (Instruc on-Level Parallelism) to:

 DLP (Data-Level Parallelism)

 TLP (Thread-Level Parallelism)

 RLP (Request-Level Parallelism)

o ILP = automa c via hardware/compiler.

o DLP/TLP/RLP = require explicit parallel programming.

 Amdahl’s Law:

o Limits the benefit of parallelism.

o If 10% of a program is serial → maximum speedup = 10×.

 Slowdown a er 2004:
 o Transistors not improving much.

o Power limits fixed.

o Performance doubling slowed to every 20 years (was every 1.5 years earlier).

Classes of computers
Overview

 Compu ng has evolved into five major markets based on usage, technology, and applica on needs:

1. Internet of Things (IoT) / Embedded Computers

2. Personal Mobile Devices (PMDs)

3. Desktop Computers

4. Servers

5. Clusters / Warehouse-Scale Computers (WSCs)

1. Internet of Things (IoT) / Embedded Computers

 Found in everyday machines: microwaves, cars, printers, switches, etc.

 IoT = Embedded computers connected to the Internet, o en wirelessly.

 Have sensors and actuators for “smart” applica ons: smart homes, cars, ci es, etc.

 Wide range of power and cost:

o 8-bit to 32-bit cheap processors (a few cents).

o 64-bit high-end processors (about $100).

 Key design focus:

o Meet required performance at minimum price.

o Price-sensi ve market.

 Examples: ARM processors in phones, routers, etc.

 Quan ta ve performance data for embedded systems is limited, so qualita ve analysis is used.

2. Personal Mobile Devices (PMDs)

 Includes cell phones, tablets, and similar mul media wireless devices.

 Cost and energy efficiency are main concerns.

o Limited by ba ery, packaging (plas c), and no cooling fans.

 Applica ons: Web-based, media-oriented (e.g., Google Translate).

 Storage: Flash memory (not magne c disks).

  Dis nct from embedded devices because they can run third-party so ware.

 Performance requirements:

o Responsiveness and predictability (real- me performance).

o Example: Each video frame must process within a me limit.

o So real- me: Occasional delays are acceptable.

 Other key factors:

o Minimize memory and code size (reduces cost).

o High energy efficiency (ba ery + heat).

3. Desktop Compu ng

 Range: Netbooks (<$300) to high-end worksta ons ($2500).

 Since 2008, most are laptops (ba ery-operated).

 Market trend: Sales declining.

 Main goal: Op mize price-performance (compute + graphics performance).

 Benchmarking: Well-characterized applica ons, though web-based apps add challenges.

 Design focus:

o Latest, cost-reduced microprocessors appear first here.

o Balance between performance and cost.

4. Servers

 Provide large-scale, reliable compu ng services (e.g., ATM, airline systems).

 Replaced tradi onal mainframes in enterprises.

 Key characteris cs:

o Availability: Must run 24/7 with minimal down me.

o Scalability: Must expand with growing demand.

o Throughput: Efficiency measured in transac ons per minute or web pages per second.

 Goal: Handle many requests efficiently at low cost.

 Performance metrics: Overall throughput and reliability.

5. Clusters / Warehouse-Scale Computers (WSCs)

 Support So ware as a Service (SaaS): search, social media, streaming, gaming, etc.
  Clusters: Group of servers or desktops connected by a local area network (LAN) to act as one
computer.

 WSCs: Large-scale clusters (tens of thousands of servers).

 Cost factors:

o Power and cooling = major expenses.

o Example: $40 million per year in compu ng and networking; 10% be er performance saves
$4 million.

 Availability: Cri cal (e.g., Amazon down me costs millions/hour).

 WSC design: Uses redundant, inexpensive components with so ware fault tolerance.

 Scalability: Achieved through network connec ons, not hardware integra on.

 Supercomputers vs. WSCs:

o Supercomputers → High floa ng-point, long batch programs.

o WSCs → Internet-scale, interac ve, storage-heavy systems.

Classes of Parallelism and Architectures

Two Kinds of Parallelism in Applica ons

1. Data-Level Parallelism (DLP) – Same opera on on many data items simultaneously.

2. Task-Level Parallelism (TLP) – Independent tasks executed in parallel.

Four Major Hardware Techniques

1. Instruc on-Level Parallelism (ILP) – Uses pipelining, specula ve execu on (compiler-assisted).

2. Vector/GPU Architectures (SIMD) – Single instruc on, mul ple data processing.

3. Thread-Level Parallelism (TLP) – Mul ple interac ng threads running together.

4. Request-Level Parallelism (RLP) – Many independent tasks handled in parallel (e.g., web requests).

Flynn’s Classifica on (1966)

1. SISD (Single Instruc on, Single Data):

o Tradi onal uniprocessor, sequen al execu on.

o Exploits ILP.

2. SIMD (Single Instruc on, Mul ple Data):

o One instruc on controls mul ple processors using different data.

o An SIMD machine executes a single instruc on on mul ple data values simultaneously using
many processors.
 o Since there is only one instruc on, each processor does not have to fetch and decode each
instruc on. Instead, a single control unit does the fetch and decoding for all processors.

o SIMD relies on the regular structure of computa ons (such as those in image processing).

o It is o en necessary to selec vely turn off opera ons on certain data items.

o For this reason, most SIMD programming paradigms allow for an ``ac vity mask'', which
determines if a processor should par cipate in a computa on or not.

3. MISD (Mul ple Instruc on, Single Data):

o Theore cal; not used commercially.

4. MIMD (Mul ple Instruc on, Mul ple Data):

o Computers in which each processing elements is capable of execu ng a different program

independent of each other processing elements are called Mul ple Instruc on stream,
mul ple data stream (MIMD).

o A simple variant of this model, called single program mul ple data mode (SPMD) relies on
mul ple instances of the same program execu ng on different data.

o The SPMD model has the same expressiveness as the MIMD model since each of the mul ple
programs can be inserted into one large if-else block with condi ons specified by the task
iden fiers.
Aspect SIMD (Single Instruc on, MIMD (Mul ple SPMD (Single Program,
Mul ple Data) Instruc on, Mul ple Data) Mul ple Data)

Hardware Requires less hardware Requires more hardware Can be built from
Requirement because it has only one since each processor has its inexpensive off-the-shelf
global control unit. own control unit. components with rela vely
li le effort.

Memory Requires less memory — Requires more memory as Each processor runs its own
Requirement only one copy of the each processor stores its instance of the same
program is stored. own program and OS. program, so memory usage
depends on system design.

Ease of Moderate — simpler Complex — needs Requires extensive design

Construc on / centralized control. coordina on between effort, leading to longer
Design Effort independent processors. development mes.

Obsolescence Suffers from fast Less affected by processor Depends on component

obsolescence because changes due to availability; generally easier
underlying serial independent design. to update.
processors change
rapidly.

Applica on Less suitable for irregular Suitable for a wide range of Versa le — combines
Suitability or dynamic applica ons. irregular or independent flexibility of MIMD with the
Best for regular, data- tasks. simplicity of SIMD.
parallel tasks.

Examples / Early vector processors; Sun Ultra Servers, SGI Parallel clusters and
Pla orms less common today. Origin Servers, distributed systems
mul processor PCs, commonly used in modern
worksta on clusters, IBM compu ng.
SP.

Defining Computer Architecture

 Computer architect’s task:

o Decide which a ributes ma er for a new computer.

o Design for high performance and energy efficiency within limits of cost, power, and
availability.

o Involves instruc on set design, func onal organiza on, logic design, and implementa on.

o Implementa on includes circuit design, packaging, power, and cooling.

o Requires knowledge from compilers to hardware packaging.

 Earlier meaning of architecture:

 o Meant only instruc on set design.

o Other aspects were called implementa on and considered less important.

o This is incorrect—modern architecture covers more than instruc on sets.

Instruc on Set Architecture (ISA)

 ISA = programmer-visible part of the computer.

 Acts as the boundary between hardware and so ware.

 Examples: 80x86, ARMv8, RISC-V.

 RISC-V:

o Developed at UC Berkeley, open and free.

o Modern RISC design with simplicity, large register set, and easy pipelining.

o Supported by major companies (AMD, Google, IBM, Nvidia, etc.).

Seven Dimensions of an ISA

1. Class of ISA:

o Most are general-purpose register architectures.

o Operands are registers or memory.

o Two main types:

 Register-memory (80x86) – access memory in many instruc ons.

 Load-store (ARMv8, RISC-V) – access memory only via load/store.

o All ISAs since 1985 are load-store.

2. Memory addressing:

o Most use byte addressing.

o Alignment: data access faster when addresses are mul ples of data size.

o ARMv8 requires alignment; 80x86 and RISC-V do not, but it helps performance.

3. Addressing modes:

o Define how memory addresses are computed.

o RISC-V: Register, Immediate, and Displacement.

o 80x86: Many modes (absolute, indexed, scaled index, indirect, etc.).

o ARMv8: Adds PC-rela ve, sum of registers, and auto-increment/decrement modes.

4. Types and sizes of operands:

 o Common sizes: 8-bit, 16-bit, 32-bit, 64-bit integers.

o Floa ng point: 32-bit (single) and 64-bit (double).

o 80x86 also has 80-bit extended precision.

5. Opera ons:

o Categories: Data transfer, Arithme c/logic, Control, Floa ng point.

o RISC-V: simple and easy to pipeline.

o 80x86: larger and more complex instruc on set.

6. Control flow instruc ons:

o All have branches, jumps, procedure calls, and returns.

o Use PC-rela ve addressing.

o Differences:

 RISC-V tests register values.

 ARMv8/80x86 test condi on flags.

 RISC-V/ARMv8 store return address in register.

 80x86 stores return address on stack.

7. Instruc on encoding:

o Fixed length (ARMv8, RISC-V) – all 32 bits; simpler decoding.

o Variable length (80x86) – 1–18 bytes; smaller programs.

o Compact versions (Thumb-2, RV64IC) use mixed 16/32-bit for smaller code size.

Beyond ISA – Genuine Computer Architecture

 Two components of implementa on:

1. Organiza on (Microarchitecture):

 High-level design: memory system, interconnects, CPU pipeline.

 Example: AMD Opteron and Intel Core i7 share ISA but differ in organiza on.

 The term core replaced CPU due to mul core processors.

2. Hardware:

 Actual logic design and packaging.

 Example: Intel Core i7 vs Intel Xeon E7 – same ISA, different hardware for different
uses.

 Architecture includes:
 o ISA, Organiza on, and Hardware.

Architect’s Design Goals

 Meet func onal requirements and balance:

o Performance

o Power

o Cost

o Availability

 Must also:

o Iden fy required features (based on market needs).

o Consider exis ng so ware (compa bility).

o Follow technology trends for future cost and longevity.

Trends in Technology
1. Importance of Adap ng to Technology Changes

 A successful instruc on set architecture (ISA) must survive rapid technology changes.

 Example: IBM mainframe architecture has lasted over 50 years.

 Architects must plan for future technologies to extend computer lifespan.

 Computer life me: usually 3–5 years, so design must an cipate next-genera on technology.

2. Five Key Implementa on Technologies

a. Integrated Circuit Logic Technology

 Transistor density used to increase by 35% per year (Moore’s Law).

 This meant doubling every 18–24 months.

 Moore’s Law is slowing — device count s ll increases but at a decreasing rate.

 Device speed improves more slowly than density.

b. Semiconductor DRAM (Main Memory)

 Earlier: quadrupled every 3 years.

 Growth has slowed significantly.

 Example: 8 Gb DRAM (2014) → 16 Gb DRAM (2019), no 32 Gb planned.

 New memory technologies are being researched to replace DRAM.

c. Semiconductor Flash Memory

  Nonvola le memory, used in portable devices (PMDs).

 Capacity increases 50–60% per year, doubles every 2 years.

 8–10 mes cheaper per bit than DRAM.

 Con nues to grow rapidly in capacity.

d. Magne c Disk Technology

 Before 1990: density ↑ 30%/year (double in 3 years).

 1990–2004: ↑ up to 100%/year.

 A er 2004: slowed to <5% per year.

 Capacity increase limited by number of pla ers (7 per 3.5-inch disk).

 New tech: HAMR (Heat Assisted Magne c Recording)—uses a laser to write data.

 HAMR may extend disk density but has economic and reliability challenges.

 Disks are 8–10x cheaper than Flash and 200–300x cheaper than DRAM.

e. Network Technology

 Depends on switch performance and transmission system.

 Improves rapidly; detailed trends discussed in Appendix F.

3. Impact of Rapid Technology Change

 Designers must plan for upcoming technologies.

 When products ship, newer technology might already be cheaper and faster.

 Tradi onally, cost decreases as density increases.

 Technology progress o en comes in sudden leaps when new thresholds are reached.

4. Technology Thresholds – Examples

 Early 1980s: 25k–50k transistors → single-chip 32-bit microprocessor possible.

 Late 1980s: first-level cache memory placed on-chip.

 Result: be er cost-performance and energy efficiency.

 Modern trend: move toward single-chip mul core processors, even for servers.

 Technology thresholds strongly affect architectural design decisions.

5. Performance Trends – Bandwidth vs Latency

 Bandwidth (Throughput): amount of work per me (e.g., MB/s).

  Latency (Response me): me between start and comple on (e.g., ms).

 Across all technologies: bandwidth grows much faster than latency.

 Example improvements:

o Microprocessors & networks: Bandwidth ×32,000–40,000; Latency ×50–90.

o Memory & disks: Bandwidth ×400–2400; Latency ×8–9.

 Rule of thumb: Bandwidth improves by square of latency improvement.

 Designers must focus on bandwidth op miza on.

6. Scaling of Transistor Performance and Wires

Feature Size

 Smallest size of a transistor or wire on a chip.

 Shrunk from 10 μm (1971) to 0.016 μm (2017) → now called 16 nm.

 Smaller feature size → higher transistor density (quadra c growth).

Transistor Scaling

 Shrinking also reduces ver cal size and opera ng voltage.

 Performance improves linearly with smaller feature size.

 Density improves quadra cally, giving both challenges and opportuni es.

 Enabled evolu on from 4-bit → 64-bit, mul core CPUs, and specula ve execu on.

Wire Scaling

 Wires do not scale well.

 Delay = resistance × capacitance → increases as wires shrink.

 Shorter wires but worse resistance and capacitance per length.

 Occasional improvements (e.g., copper wires) give one- me benefits.

 Wire delay is now a major design challenge, some mes worse than transistor delay.

 Power dissipa on has become an even greater limita on than wire delay.

Trends in Power and Energy in Integrated Circuits

1. Importance of Power and Energy

 Energy is the biggest challenge for all types of computers.

 Power must be supplied and distributed across the chip.

 Power is dissipated as heat and must be removed properly.

2. Power and Energy: A System Perspec ve

 System designers care about three things:

1. Maximum Power

2. Sustained Power (TDP)

3. Energy Efficiency

3. Maximum Power

 Refers to the highest power the processor might need.

 If the processor draws more power than supply can provide, voltage drops → malfunc on.

 Voltage indexing methods help slow down and reduce voltage to stay safe.

 This control reduces performance.

4. Sustained Power (Thermal Design Power – TDP)

 TDP = maximum power that determines cooling requirements.

 Peak power ≈ 1.5× TDP; average power is usually lower.

 Power supply is designed to exceed TDP; cooling system matches it.

 If cooling fails → overhea ng, device failure or damage.

 Modern CPUs handle heat using:

o Thermal thro ling – lowers clock rate as temperature rises.

o Thermal shutdown – powers down chip if thro ling fails.

5. Energy and Energy Efficiency

 Power = Energy / Time (1 wa = 1 joule/second).

 Energy is a be er metric than power.

 Energy to complete a task = Average power × Execu on me.

 Processor comparison:

o Example:

 A uses 20% more power but finishes 30% faster → uses 0.84× energy → more efficient.

 For fixed workloads, comparing energy is best.

 Power is useful only as a constraint (e.g., 100 W air-cooling limit).

6. Dynamic Energy and Power (in CMOS)

 Main source: Switching transistors (dynamic energy).

 Formula:

o E_dynamic ∝ Capaci ve load × Voltage²

o P_dynamic ∝ ½ × Capaci ve load × Voltage² × Switching frequency

 Lowering voltage reduces dynamic power and energy.

 Voltages dropped from 5V → ~1V over 20 years.

 But higher frequency and more transistors increase total power.

 Early CPUs: <1 W; Intel 80386: 2 W; Intel i7 (4 GHz): 95 W.

 Air-cooling limits reached → clock speed growth slowed (since 2003).

7. Modern Energy-Efficiency Techniques

1. Do Nothing Well – Turn off clocks of inac ve modules (e.g., idle cores).

2. Dynamic Voltage-Frequency Scaling (DVFS) –

o Lower frequency and voltage during low ac vity.

o Saves 10–15% power per frequency step.

3. Design for Typical Case –

o Devices (DRAM, disks) enter low-power modes when idle.

o Must return to ac ve mode for access.

o CPUs have emergency slowdown to avoid overhea ng.

4. Overclocking (Turbo Mode) –

o Temporary increase in clock speed for short bursts.

o Example: 3.3 GHz CPU runs at 3.6 GHz briefly.

o May cause variable performance with temperature.

8. Sta c Power and Leakage

 Leakage current flows even when transistors are off.

 Formula: P_sta c ∝ I_sta c × Voltage

 More transistors → more leakage.

 Leakage increases with smaller transistor sizes.

  Power ga ng turns off power to inac ve modules to save energy.

 Leakage target (2011): 25% of total power; actual may exceed 50%.

 Large SRAM caches increase leakage as they need power to retain data.

9. Race-to-Halt Strategy

 Use a faster processor to finish tasks quickly.

 Allows system to enter sleep mode sooner, saving total energy.

10. New Metric

 Earlier: Performance per mm² (silicon area).

 Now: Performance per wa or Tasks per joule.

 Energy efficiency has become the main performance goal.

11. Shi in Computer Architecture (Energy Limits)

 Transistor scaling slowed → energy efficiency becomes priority.

 Dark silicon: not all transistors can be ac ve due to thermal limits.

 Large parts of chip remain unused ("dark") to control heat.

12. Energy and Area Cost Differences

 32-bit floa ng-point add = 30× more energy than 8-bit integer add.

 Area = 60× larger for FP add.

 32-bit DRAM access = 20,000× more energy than 8-bit add.

 SRAM is 125× more efficient than DRAM.

 Shows importance of caches and memory op miza on.

13. Future Trend: Domain-Specific Processors

 Focus on minimizing energy per task.

 Replace wide FP opera ons with narrow integer units.

 Add special-purpose memories to reduce DRAM access.

 10–100× more efficient for specific tasks.

 Future computers = mix of general-purpose and special-purpose cores.

Quan ta ve Principles of Computer Design
1. Overview

 Design decisions in computer architecture depend on performance, cost, dependability, energy, and
power.

 Several principles and equa ons guide how to evaluate design alterna ves.

2. Take Advantage of Parallelism

 Parallelism = Performing mul ple opera ons simultaneously to increase performance.

 Used at system, processor, and circuit levels.

Examples:

1. System-Level Parallelism

o Improves throughput using mul ple processors and storage devices.

o Enables scalability – ability to expand system resources.

o Data-level parallelism: Spread data across mul ple storage devices.

o Request-level and thread-level parallelism: Use mul ple processors/threads (SPECSFS, TPC-
C benchmarks).

2. Processor-Level Parallelism

o Instruc on-Level Parallelism (ILP) – execute instruc ons in parallel.

o Pipelining: Overlaps instruc on execu on stages to reduce total execu on me.

3. Circuit-Level Parallelism

o Set-associa ve caches: Mul ple memory banks searched in parallel.

o Carry-lookahead adders: Parallel carry computa on → faster arithme c.

3. Principle of Locality

 Programs reuse data and instruc ons they recently used.

 Helps predict future accesses → efficient memory system design.

Types of Locality:

1. Temporal Locality: Recently accessed items are likely to be accessed again soon.

2. Spa al Locality: Items near each other in memory are accessed close together in me.

 Rule of thumb: 90% execu on me in 10% of the code.

 Used in cache design and memory hierarchy.

4. Focus on the Common Case

 Most important design principle.

 Allocate resources to frequent cases rather than rare ones.

 Improves performance, dependability, and energy efficiency.

Examples:

 Op mize instruc on fetch and decode (used o en) over mul plier (used rarely).

 Overflow during addi on is rare → op mize for normal (no overflow) case.

 Improvement impact is greater when applied to common opera ons.

Introduc on to Pipelining
 Pipelining is an implementa on technique where mul ple instruc ons are overlapped in execu on.

 It exploits parallelism among the ac ons needed to execute an instruc on.

 It is the key technique for making fast processors.

What is Pipelining?

 A pipeline is like an assembly line. Each stage completes a part of an instruc on.

 Stages are connected; instruc ons enter one end, progress through, and exit the other.

 A pipe stage or pipe segment is one step in the pipeline.

 Throughput is how o en an instruc on exits the pipeline.

 The processor cycle is the me between moving an instruc on one step down the pipeline. It is
determined by the slowest pipe stage.

 The goal is to balance the length of each pipeline stage.

 Ideal speedup equals the number of pipe stages.

 Pipelining reduces the average execu on me per instruc on and the CPI.

 It is not visible to the programmer.

RISC-V Instruc on Set Basics

 RISC-V is a load-store architecture.

 Key RISC proper es:

o Opera ons on data apply only to data in registers.

o Only load and store instruc ons affect memory.

o Instruc on formats are few in number and all instruc ons are typically one size.

o Register specifiers are always in the same place (fixed-field decoding).

A Simple Unpipelined RISC Implementa on

 Every instruc on takes at most 5 clock cycles:

1. IF (Instruc on Fetch): Send PC to memory, fetch instruc on, increment PC by 4.

2. ID (Instruc on Decode/Register Fetch): Decode instruc on, read registers from register file,
sign-extend immediate, compute branch target address.

3. EX (Execu on/Effec ve Address): ALU performs one of:

 Memory reference: Calculate effec ve address.

 Register-Register ALU: Perform ALU opera on.

 Register-Immediate ALU: Perform ALU opera on with immediate.

 Condi onal branch: Evaluate branch condi on.

4. MEM (Memory Access): For load, read memory. For store, write memory.

5. WB (Write-Back): Write result (from ALU or memory) back to register file.

The Classic Five-Stage RISC Pipeline

 Each clock cycle from the unpipelined version becomes a pipe stage.
  A new instruc on is started on each clock cycle.

 Key points for pipeline design:

o Use separate instruc on and data memories/caches to avoid conflicts.

o The register file is used in two stages: read in ID, write in WB. Writes are done in the first half
of the clock cycle, reads in the second half.

o The PC is incremented and stored every clock cycle during IF.

 Pipeline registers are inserted between stages (IF/ID, ID/EX, EX/MEM, MEM/WB) to hold
intermediate results and prevent interference between stages.

Basic Performance Issues in Pipelining

 Pipelining increases instruc on throughput, not the speed of a single instruc on.

 Execu on me per individual instruc on may slightly increase due to control overhead.

 Prac cal limits on pipeline depth come from:

o Pipeline latency: The me for one instruc on to complete.

o Imbalance among pipe stages: Clock speed is limited by the slowest stage.

o Pipeline overhead: The sum of:

 Pipeline register delay (setup me + propaga on delay).

 Clock skew (max delay between clock arrival at any two registers).

 Instruc ons in the pipeline can depend on one another, crea ng hazards.
Pipeline Hazards
 Hazards are situa ons that prevent the next instruc on from execu ng in its designated clock cycle.

 They reduce the ideal performance gain from pipelining.

 There are three classes of hazards:

1. Structural Hazards: Arise from resource conflicts when hardware cannot support all
instruc on combina ons.

2. Data Hazards: Arise when an instruc on depends on the result of a previous instruc on.

3. Control Hazards: Arise from the pipelining of branches and other instruc ons that change the
PC.

 To avoid a hazard, the pipeline may need to be stalled. A stall delays later instruc ons but allows
earlier ones to proceed.

Performance of Pipelines With Stalls

 A stall degrades performance from the ideal.

 Pipelined CPI Formula:

o CPI_pipelined = Ideal CPI + Pipeline stall cycles per instruc on

 o Ideal CPI is usually 1.

 Speedup Formula:

o Speedup = CPI_unpipelined / (1 + Pipeline stall cycles per instruc on)

 If all instruc ons take the same number of cycles (equal to pipeline depth):

o Speedup = Pipeline depth / (1 + Pipeline stall cycles per instruc on)

Data Hazards

 Data hazards occur when the pipeline changes the order of read/write accesses to operands.

 Assume instruc on i occurs before instruc on j and both use register x:

o RAW (Read A er Write): j reads x before i writes it. j gets the wrong value. This is the most
common hazard.

o WAR (Write A er Read): i reads x a er j writes it. i gets the wrong value. Not possible in the
simple 5-stage pipeline.

o WAW (Write A er Write): i writes x a er j writes it. The final value of x is wrong. Not possible
in the simple 5-stage pipeline.

Minimizing Data Hazard Stalls by Forwarding

 Forwarding (or bypassing) is a hardware technique to eliminate some stalls from RAW hazards.

 Key Idea: The result from a previous instruc on is needed a er it is computed, not necessarily a er
it is wri en to the register file.

 How it works: The ALU result from the EX/MEM and MEM/WB pipeline registers is fed back to the
ALU inputs.

 If the forwarding hardware detects that a previous ALU opera on wrote the register a current
opera on needs, it selects the forwarded result as the ALU input instead of the value from the register
file.

 Forwarding can pass a result directly to any func onal unit that requires it, not just the ALU.

Data Hazards Requiring Stalls

 Forwarding cannot solve all data hazards.

 A load instruc on followed immediately by an instruc on that uses its result is a key example.

 The data from the load is not available un l the end of the MEM stage (cycle 4), but the dependent
instruc on (e.g., a SUB) needs it at the beginning of its EX stage (cycle 4).

 A forwarding path would need to operate "backward in me," which is impossible.

 This requires a pipeline interlock.

 A pipeline interlock detects the hazard and stalls the pipeline un l the hazard is cleared.

 The stall introduces a one-cycle bubble (or delay) in the pipeline, increasing the CPI.
Branch Hazards

 Control Hazards arise from the pipelining of branches and instruc ons that change the PC.

 A taken branch changes the PC to the target address. An untaken branch (or not taken) falls through
to PC+4.

 In the simple pipeline, the branch decision is made at the end of the ID stage.

 This can cause a performance penalty as the pipeline may have fetched incorrect instruc ons.

Reducing Pipeline Branch Penal es

 Scheme 1: Freeze/Flush Pipeline

o Stall the pipeline, dele ng instruc ons a er the branch un l the target is known.

o Simple but has a fixed branch penalty.

 Scheme 2: Predicted Not-Taken

o Assume the branch will not be taken and con nue fetching sequen al instruc ons.

o If the branch is taken, turn the fetched instruc ons into no-ops and restart fetching at the
target address.

 Scheme 3: Predicted Taken

o Assume the branch will be taken and immediately start fetching from the target address.

o This can save one cycle if the branch is actually taken.

 Scheme 4: Delayed Branch

o The instruc on immediately a er the branch (in the branch delay slot) is always executed.

o The compiler's job is to place a useful instruc on in this slot.

o Not used in modern architectures like RISC V.

Performance of Branch Schemes

 Pipeline Speedup Formula with Branches:

o Pipeline Speedup = Pipeline Depth / (1 + Branch frequency * Branch penalty)

Reducing Cost with Predic on

 Sta c Branch Predic on

o Predic ons are fixed at compile me.

o Can use profile informa on from earlier program runs to predict based on past behavior.

o Effec veness is limited as branch behavior can change with different inputs.

 Dynamic Branch Predic on

o Predic ons are made at run me based on program behavior.

o Uses a Branch-Predic on Buffer (BPB) or Branch History Table (BHT).

  1-Bit Predictor

o A single bit stores whether the branch was taken last me.

o A weakness: a single mispredic on flips the predic on, causing two mispredic ons for a
mostly-taken branch.

 2-Bit Predictor

o A satura ng counter that must miss twice before the predic on is changed.

o More accurate than a 1-bit predictor.

o The predictor state changes based on whether the branch was taken or not taken.

 Predic on Accuracy

o Accuracy depends on the program. Scien fic programs o en have higher accuracy than
integer programs.

o Increasing the buffer size beyond a certain point (e.g., 4K entries) offers diminishing returns.

o The key to higher accuracy is improving the predic on scheme itself, not just the buffer size.

Unit II
Mul processors and Thread level parallelism: Introduc on
 MIMD Mul processor:

o Uses mul ple processors to execute mul ple independent threads or processes
simultaneously.

o To use an MIMD system with n processors efficiently, at least n threads are needed (or 2–4×
more with mul threading).

 Thread Crea on:

o Threads are created by the programmer or opera ng system.

o Some mes generated by a parallel compiler exploi ng data parallelism.

 Grain Size:

o Amount of computa on assigned to each thread.

o Must be large enough to reduce overhead and improve efficiency.

o Thread-level parallelism (TLP) deals with hundreds to millions of instruc ons per thread.

 Thread-Level vs Instruc on-Level Parallelism (ILP):

o TLP: Iden fied by so ware or programmer at a high level.

o ILP: Extracted automa cally at the hardware level.

 Threads for Data Parallelism:

 o Threads can exploit data-level parallelism, but overhead is higher compared to SIMD
processors or GPUs.

o Parallelism must have a sufficiently large grain size to be efficient.

Classes of Shared-Memory Mul processors

1. Symmetric Mul processors (SMPs)

o Also called Centralized Shared-Memory Mul processors.

o Typically have small to moderate numbers of cores (≤32).

o All processors share a single centralized memory with equal access → called symmetric.

o Common in mul core chips today.

o Also known as Uniform Memory Access (UMA) systems since all processors have equal
memory latency.

o Example issue: Some mul cores use Nonuniform Cache Access (NUCA) – e.g., IBM Power8 –
making them not truly SMP.

o Advantages:

 Simpler to program and manage.

 Equal access me to memory.

o Limita ons:

 As number of processors increases, centralized memory becomes a bo leneck.

 Not scalable for large systems.

2. Distributed Shared Memory (DSM)

o Also called Nonuniform Memory Access (NUMA).

o Memory is physically distributed among processors.

o Each processor has fast local memory and slower remote memory access.

o Access me depends on the loca on of data in memory.

o Used for systems with many processors or mul ple mul core chips.

o Advantages:

 Increases memory bandwidth.

 Reduces local access latency.

o Disadvantages:

 Complex communica on among processors.

  So ware must manage memory placement for efficiency.

o Used in most large-scale mul processors and mul core systems today.

Communica on in SMP and DSM

 Both use a shared address space.

 Any processor can access any memory loca on (if permi ed).

 Called “shared memory” because all processors share the same address space.

Contrast with Clusters and Warehouse-Scale Computers

 Each processor has its own private memory.

 Communica on occurs through message-passing protocols over a network.

 Memory of one processor cannot be directly accessed by another.

Symmetric Shared Memory Architectures

Key Idea

 Large, mul level caches reduce memory bandwidth demand.

 This mo vates centralized shared-memory mul processors (SMPs).

 Originally, processors were single-core and shared memory via a common bus.

 Modern high-performance processors connect memory directly to a chip (backside or memory bus).

 Access to local memory is faster than access to remote memory (asymmetric access).

Memory Access in Mul core Systems

 Memory on a chip is shared among all cores.

 Access from one mul core chip to another’s memory is slower.

 Hence, systems show asymmetric memory access behavior.

Caching in Shared-Memory Systems

 Both private and shared data can be cached.

 Private data → used by one processor only.

o Cached locally to reduce access me and bandwidth.

 Shared data → used by mul ple processors.

o Caching improves performance by lowering latency and conten on.

 o But causes a new issue: Cache Coherence Problem.

What Is Cache Coherence?

 When shared data are cached by mul ple processors, each cache may see different values.

 This causes inconsistent views of memory among processors.

 Occurs because there is a global state (main memory) and local states (individual caches).

 Even in mul cores (private L1/L2, shared L3), the problem persists.

Defini on of a Coherent Memory System

A system is coherent if:

1. Read a er own write:

o A processor’s read returns the value it wrote earlier (if no other writes occurred).

2. Read a er another’s write:

o A processor’s read returns the most recent value wri en by another processor (if enough me
has passed and no new writes occurred).

3. Write serializa on:

o All processors see writes to the same memory loca on in the same order.

o Example: If values 1 then 2 are wri en, no processor should read 2 then later 1.

Importance of Write Serializa on

 Prevents processors from observing writes in different orders.

 Ensures consistent memory behavior across all processors.

Coherence vs Consistency

 Coherence:

o Deals with same memory loca on.

o Ensures all processors see the latest wri en value.

 Consistency:

o Deals with order of opera ons across different loca ons.

o Defines when a wri en value becomes visible to others.

Assump ons for Simplicity

1. A write completes only when all processors see its effect.

2. Processors do not reorder writes with other memory opera ons.

o So, if a processor writes A then B, any processor seeing new B must also see new A.

 These assump ons simplify analysis of memory behavior un l detailed consistency models are
discussed later.

Coherence in Prac ce

 Programs on mul processors o en have mul ple copies of shared data in caches.

 Caches support:

o Migra on: Move data to local cache (reduces latency and bandwidth use).

o Replica on: Keep copies of read-only data in mul ple caches (reduces conten on).

 To maintain correctness, hardware cache coherence protocols are used.

Cache Coherence Protocols

 Maintain consistency among cached copies of shared data.

 Use status bits (valid, dirty, etc.) to track each block’s state.

 Two main types:

1. Directory-Based Protocols

o A directory keeps track of which caches have copies of each memory block.

o In SMPs, a centralized directory may be used.

o In DSM systems, directories are distributed to avoid bo lenecks.

o Used when systems have many processors or mul core chips.

2. Snooping Protocols

o No single directory.

o Each cache monitors (“snoops”) the shared communica on medium (bus or switch).

o Detects when another processor reads or writes data it holds.

o Used in bus-based SMP systems where caches are connected to shared memory.

o S ll used in some mul core or mul chip designs (some mes combined with directory
protocols).

Why Snooping Became Popular

  Early mul processors had a shared bus—easy for all caches to listen (snoop).

 Suitable for single-core systems.

 In mul core architectures, since caches are shared at some levels (e.g., L3),

o Some systems switched to directory protocols for scalability.

 Both snooping and directory protocols are key to maintaining coherence.

Performance of Symmetric Shared-Memory Mul processors

1. Overview

 In mul core systems using snooping coherence protocols, performance depends on:

o Uniprocessor cache miss traffic

o Communica on traffic (invalida ons and coherence-related misses)

 Changing processor count, cache size, or block size affects these components differently.

2. Cache Miss Classifica on

 Three C’s (Uniprocessor Misses):

o Compulsory misses – first- me access to data.

o Capacity misses – cache not large enough to hold all data.

o Conflict misses – same cache set used by mul ple blocks.

 Coherence Misses (Mul processor Misses):

o Arise due to data sharing among processors.

3. Types of Coherence Misses

 True Sharing Misses:

o Caused by actual data sharing between processors.

o Example: one processor writes to a block; others must invalidate or fetch updated data.

 False Sharing Misses:

o Occur when different words in the same cache block are used by different processors.

o Block gets invalidated unnecessarily.

o No real data sharing happens.

o Would disappear if block size = one word.

4. Impact on Performance
  True sharing and false sharing both increase miss rate and memory traffic.

 Their impact is stronger in ghtly coupled applica ons that share user data.

5. Example: Commercial Workload (OLTP)

 Studied on a 4-processor AlphaServer 4100 (300 MHz) with a 3-level cache.

 Workload: Online Transac on Processing (OLTP) using Oracle 7.3.2 (similar to TPC-C).

 Execu on breakdown:

o 71% user mode

o 18% OS mode

o 11% idle (I/O wait)

 Processors stalled 90% of the me.

o Memory accesses = 50% of stalls

o L2 misses = 25% of stalls

6. Effect of L3 Cache Size

 L3 varied from 1 to 8 MiB per processor.

 Performance improved mainly from 1 → 2 MiB.

 Beyond 2 MiB, gains were minimal because:

o True sharing misses remain constant.

o Uniprocessor misses reduce, but coherence misses dominate.

7. Effect of Processor Count

 Increasing processors → increases true sharing misses.

 Results in higher memory access cycles per instruc on.

8. Effect of Block Size (32 to 256 bytes)

 True sharing misses ↓ more than 2× (good locality).

 Compulsory misses ↓ (expected).

 Conflict/capacity misses ↓ slightly.

 False sharing misses ↑ (nearly double).

 Instruc on miss rate not much affected (low spa al locality in OLTP code).
  Larger blocks increase memory traffic, possibly offse ng benefits.

9. Mul programming and OS Workload (Andrew Benchmark)

 Workload: Two compile phases (8 processors, 5.24 sec run me).

 Involves compute, install (I/O heavy), and delete phases.

 Much more I/O- and system-intensive than OLTP.

10. System Configura on

 L1 Instruc on Cache: 32 KB, 2-way, 64-byte block, 1-cycle hit.

 L1 Data Cache: 32 KB, 2-way, 32-byte block, 1-cycle hit.

 L2 Cache: 1 MiB, 2-way, 128-byte block, 10-cycle hit.

 Main Memory: 100-cycle access.

 Disk: 3 ms latency (reduced for test).

11. Execu on Time Breakdown

1. Idle: Processor wai ng (kernel mode)

2. User: User code execu on

3. Synchroniza on: Wai ng for sync variables

4. Kernel: OS code (non-idle)

12. Cache Miss Pa erns

 OS (Kernel) Instruc on Miss Rate:

o 1.7% for 32 KB → 0.2% for 256 KB.

 User instruc on misses: About one-sixth of OS rate.

 OS executes fewer instruc ons but takes more me due to higher miss rates.

13. Reasons for Higher Kernel Miss Rate

1. Page ini aliza on: Increases compulsory misses.

2. Shared data: Causes coherence misses.

3. User processes mainly experience misses when rescheduled on another processor.

14. Effects of Cache and Block Size

 Increasing cache size → reduces user miss rate more.

 Increasing block size → reduces compulsory and capacity misses.

 Coherence misses are fewer, so larger blocks help slightly.

15. Kernel Miss Analysis

 Increasing cache size reduces capacity/conflict misses.

 Increasing block size reduces compulsory misses.

 False sharing effects are minor.

16. Memory Traffic Observa on

 Larger block size → more bytes per miss.

 Kernel traffic doubles when block increases 16 → 128 bytes.

 User traffic also doubles but remains lower overall.

Distributed Shared-Memory and Directory-Based Coherence

1. Snooping Protocol and Its Limita on

 Snooping protocol broadcasts every cache miss to all caches.

 It has no centralized structure, which makes it simple but not scalable.

 High communica on and memory bandwidth are required for many cores.

 Example: i7 processor supports 34 GiB/s, but applica ons may need up to 170 GiB/s.

 Solu on: move to distributed memory to increase bandwidth.

2. Distributed Memory

 Memory is split among processors (local + remote memory).

 Local traffic and remote traffic are separated to reduce bandwidth load.

 But s ll needs an efficient coherence mechanism to avoid broadcasts.

3. Directory-Based Coherence

 Alterna ve to snooping.

 Directory keeps track of each memory block’s state and which caches hold copies.

 Directory helps avoid broadcas ng on every miss.

4. Directory Organiza on

 Each block in memory has a directory entry.

 Directory stores:

o Which caches have the block (bit vector).

o Whether the block is shared, modified, or uncached.

 Within a mul core (e.g., Intel i7), directory is maintained at shared L3 cache.

 For larger systems, directories are distributed with memory (each node has one).

 Each node acts as both home (holds memory + directory) and processor.

5. Advantages of Distributed Directory

 Each block’s status is stored in a single known loca on.

 Avoids broadcast while keeping coherence.

 Scalable for systems up to a few hundred processors.

6. Directory States

 Uncached: no cache has a copy; memory is up to date.

 Shared: mul ple caches have copies; memory is up to date.

 Modified (Exclusive): only one cache has a copy; memory is outdated.

7. Bit Vector Tracking

 Each block has a bit vector represen ng which processors have copies.

 In exclusive state, it also shows which node is the owner.

8. Communica on Between Nodes

 Local node: where request originates.

 Home node: where memory + directory reside.

 Remote node: node that has a cached copy.

 Messages are exchanged between these nodes to maintain coherence.

9. Message Handling Assump ons

 Messages are received in the same order they are sent.

 Invalida ons complete before new messages start.

 Acknowledgments are required for invalida ons and write misses.

10. An Example Directory Protocol

1. Basic Idea

 Directory-based protocols have the same cache states as snooping protocols.

 States: Shared, Modified (Exclusive), Uncached.

 Difference: directory tracks the state of all cached copies of a memory block.

2. State Diagrams

 State transi on diagrams show how cache blocks change states during opera ons.

 Transi ons are caused by:

o Read miss

o Write miss

o Invalidate

o Data fetch

 Each cache also sends read miss, write miss, and invalidate messages to the home directory.

 Read and write misses wait for data replies before changing state.
  Handling of invalida on acknowledgments is done separately.

3. Comparison with Snooping Protocol

 Both have iden cal states and similar triggers.

 In snooping: write miss → broadcast on the bus.

 In directory-based: write miss → selec ve data fetch + invalidate via directory.

 Only caches with the block are contacted, avoiding broadcast.

4. Requirements

 A cache block must be in exclusive state before any write.

 Shared blocks must have up-to-date data matching main memory.

5. Role of Shared L3 Cache

 Many mul cores (Intel i7, AMD Opteron, IBM Power7) have a shared L3 cache.

 L3 maintains coherence among private L1/L2 caches using internal directory or snooping.

 Coherence between mul ple processors is maintained by connec ng through L3.

 This reduces conten on and avoids duplica on of cache tags.

6. Role of Directory

 The directory handles the other half of the coherence protocol.

 When it receives a message:

1. Updates the directory state.

2. Sends messages to nodes to sa sfy the request.

7. Directory States

 Represent the state of all cached copies of a memory block.

 Possible cases:

o Uncached: no node has a copy.

o Shared: mul ple nodes have readable copies.

o Exclusive: one node owns a writable copy.

8. Sharers Set

 Directory maintains a Sharers set to track which nodes have copies.

 Implemented as a bit vector (each bit represents a node).

 For systems with fewer than 64 nodes, this is efficient.

 Directory uses this set to:

o Iden fy nodes to invalidate when needed.

o Update membership when a node reads or writes the block.

11. Directory-Based Cache Coherence

1. Overview

 Directory keeps track of cache blocks and which processors have them.

 Handles requests from processors to maintain coherence.

 Three main requests: Read miss, Write miss, and Data write-back.

 The directory maintains a set called Sharers, showing which nodes have copies.

 Each block can be in one of three states: Uncached, Shared, or Exclusive.

2. When Block is in the Uncached State

 Only memory has the current value.

 Possible requests:

o Read miss:
  Directory sends data from memory to the requester.

 Requester becomes the only sharer.

 Block state changes to Shared.

o Write miss:

 Directory sends data from memory to requester.

 Requester becomes the only owner.

 Block state changes to Exclusive.

 Sharers = reques ng node.

3. When Block is in the Shared State

 Memory holds the latest value.

 Possible requests:

o Read miss:

 Directory sends data from memory.

 Adds requester to Sharers set.

o Write miss:

 Directory sends data to requester.

 Sends invalidate messages to all other sharers.

 Sharers now only includes requester.

 Block state changes to Exclusive.

4. When Block is in the Exclusive State

 Only one node (the owner) has the updated value.

 Possible requests:

o Read miss:

 Directory sends data fetch to owner.

 Owner changes block to Shared and sends data to directory.

 Directory writes data to memory and sends it to requester.

 Adds requester to Sharers.

o Data write-back:

 Owner writes block back to memory (block is being replaced).

  Memory now has updated copy.

 Block becomes Uncached.

 Sharers set becomes empty.

o Write miss:

 Directory sends message to old owner to invalidate and send data.

 Directory forwards data to requester.

 Requester becomes new owner.

 Sharers = new owner.

 State remains Exclusive.

5. Notes on Protocol and Implementa on

 The protocol assumes atomic ac ons (idealized simplifica on).

 Real implementa ons must handle non-atomic memory transac ons.

 Op miza ons:

o Some systems forward data directly from the old owner to the requester (not via directory).

o Adds complexity (possible deadlocks, more message types).

 Real systems use hybrid schemes:

o Example: Snooping within a chip and directory across chips.

o Used in mul processors like AMD Opteron.

12. Directory Ac ons (Per State)

 Uncached state:

o Read miss → send data, mark shared.

o Write miss → send data, mark exclusive, requester becomes owner.

 Shared state:

o Read miss → send data, add requester to Sharers.

o Write miss → send data, invalidate all Sharers, set requester as owner (exclusive).

 Exclusive state:

o Read miss → fetch data from owner, write to memory, share with requester.

o Data write-back → memory updated, Sharers set cleared (uncached).

o Write miss → request old owner to send data + invalidate, requester becomes new owner.

13. Op miza ons

 Data can be forwarded directly from owner to requester (avoiding directory delay).

 Adds complexity and risk of deadlock.

14. Implementa on Challenges

 Same core issues as snooping: ordering, invalida ons, atomicity.

 Addi onal complexi es due to message delays and distributed memory.

 Real systems combine both:

o Snooping within a chip (shared L3 cache).

o Directory across chips for scalability.

15. Hybrid Coherence Examples

 Snooping/Snooping: AMD Opteron.

 Snooping/Directory, Directory/Snooping, Directory/Directory combina ons also exist.

 Using snooping on-chip and directory off-chip simplifies design and improves performance.
UNIT – III
Scope of Parallel Compu ng

 Parallel compu ng has a wide impact across scien fic, engineering, commercial, and system-level
applica ons.

 Cost benefits combined with high performance requirements strongly mo vate the adop on of
parallel compu ng.

 It enables faster execu on, handling of large datasets, and solving complex problems that are
imprac cal with serial compu ng.

Applica ons in Engineering

 Used in airfoil design to op mize li , drag, and stability.

 Applied in internal combus on engine design to op mize charge distribu on and combus on.

 U lized in high-speed circuit design to manage delays and capaci ve/induc ve effects.

 Employed in structural engineering to op mize integrity, design parameters, and cost.

 Plays a key role in the design of MEMS and NEMS (micro- and nano-electro-mechanical systems).

 Supports systems combining quantum phenomena, molecular dynamics, stochas c and con nuum
models, and physical processes such as conduc on, convec on, radia on, and structural mechanics.

 Faces ongoing challenges in geometric modeling, mathema cal modeling, and algorithm
development for parallel pla orms.

 Op miza on algorithms like Simplex, Interior Point Methods, Branch-and-Bound, and Gene c
Programming have been efficiently parallelized and widely used.

Scien fic Applica ons

 Enabled large-scale projects such as human genome sequencing by interna onal consor a.

 Used for func onal and structural characteriza on of genes and proteins.

 Supports bioinforma cs tasks like biological sequence analysis for drug discovery and disease
treatment.

 Many modern parallel compu ng technologies are specifically targeted toward bioinforma cs.

 Advances computa onal physics and chemistry across scales from quantum phenomena to
macromolecular structures.

 Applied in astrophysics for studying galaxy evolu on, thermonuclear processes, and large telescope
datasets.

 Essen al for weather modeling, mineral prospec ng, flood predic on, and other applica ons with
direct societal impact.

Commercial Applica ons

 Mul processors and Linux clusters are widely used as web and database servers.
  Financial ins tu ons handle massive concurrent user sessions and transac on volumes using parallel
pla orms.

 Large-scale transac on data analysis drives data mining for business op miza on and marke ng
decisions.

Applica ons in Computer Systems

 Cri cal for computer security, especially network intrusion detec on with distributed and rapidly
analyzed data.

 Used in cryptography, par cularly in factoring very large integers via Internet-based parallel
compu ng.

 Modern automobiles use mul ple processors working in parallel to op mize handling and
performance.

 Parallel and distributed algorithms are applied for coordina on tasks such as leader selec on and
maximal independent sets.

 Concepts from parallel compu ng extend to ad-hoc, mobile, and faulty environments beyond
tradi onal reliable systems.

Preliminaries
Parallel Algorithms: Basic Ideas

 A sequen al algorithm is a step-by-step procedure for one processor.

 A parallel algorithm is a procedure for mul ple processors.

 Parallel algorithms must specify which steps can run at the same me (concurrency).

What a Parallel Algorithm Must Specify

 Iden fy parts of work that can run concurrently.

 Map concurrent work to mul ple processors.

 Distribute input, output, and intermediate data.

 Manage shared data access among processors.

 Synchronize processors at needed points.

3.1 Preliminaries

Parallel algorithm design involves two main steps:

1. Decomposi on

2. Assignment of parts to processors

3.1.1 Decomposi on, Tasks, and Dependency Graphs

Decomposi on

 Breaking a computa on into smaller parts.

 Some or all smaller parts can run in parallel.

Tasks

 Programmer-defined units of computa on created by decomposi on.

 Tasks are treated as indivisible once defined.

 Tasks may be different sizes.

 Parallelism is achieved by execu ng mul ple tasks simultaneously.

Task Independence

 Some tasks can run in any order (independent tasks).

 Other tasks depend on results of earlier tasks.

Task-Dependency Graph

 A directed acyclic graph (DAG) showing task rela onships.

 Nodes = tasks.

 Directed edges = dependencies (a task cannot start un l all incoming edges' tasks finish).

 Graph may be disconnected or have no edges (like matrix-vector mul plica on).

Example 1: Dense matrix-vector mul plica on

Problem Statement

 We want to compute y = A × b, where:

o A is an n × n dense matrix

o b is an n-element vector

o y is the output vector

 Each element y[i] is the dot product of row i of A with vector b y[i] = Σ A[i, j] × b[j]).

What We Are Trying to Achieve

 We want to speed up matrix-vector mul plica on using parallelism.

 To do this, we must decompose the computa on into independent tasks that can run simultaneously.

 Goal: assign different parts of the computa on to different processors.

How We Are Achieving It

 We treat the computa on of each y[i] as one task.

  Since each y[i] depends only on row i of A and the vector b:

o Tasks do not depend on each other.

o All tasks can run fully in parallel.

 Therefore:

o Task i reads row i of A.

o Task i reads all of vector b.

o Task i writes the single output y[i].

 Total tasks = n tasks (one per row).

Example 2: Database query processing

 Consider the computa ons performed in processing the following query: MODEL="Civic" AND
YEAR="2001" AND (COLOR = "Green" OR COLOR="White")

 The query looks for 2001 Civics that are either green or white.
 There are four intermediate tables involved:

1. All Civics
 2. All 2001-model cars
3. All green cars
4. All white cars

 The computation combines these tables using intersections or unions.

 Each step in the process is a task that creates an intermediate table.
 Arrows between tasks show which tasks depend on others
 There can be multiple ways of drawing the dependency graph for the tables.

Way 1 Way 2

3.1.2 Granularity, Concurrency, and Task-Interaction

 The number and size of tasks into which a problem is decomposed determines the granularity of
the decomposition.
 A decomposition into a large number of small tasks is called fine-grained and a decomposition into
a small number of large tasks is called coarse-grained.
 For example, the decomposition for matrix-vector multiplication would usually be considered fine-
grained because each of a large number of tasks performs a single dot-product.
 A coarse grained counterpart to the dense matrix-vector product example. Each task in this example
corresponds to the computation of three elements of the result vector.
- Granularity
 Refers to the size of tasks in a parallel program.
 Fine granularity means many small tasks.
 Coarse granularity means fewer, larger tasks.
 Degree of Concurrency
 Measures how many tasks can run at the same time.
 Directly affects parallel performance.
- Maximum Degree of Concurrency
 Defined as the maximum number of tasks that can execute simultaneously at any instant.
 Usually less than the total number of tasks.
 Reduced by dependencies between tasks.
 In given task graphs, the maximum degree of concurrency is four.
 Maximum concurrency often appears at the start of execution.
 For task-dependency graphs shaped like trees:
o Maximum degree of concurrency equals the number of leaf nodes.
- Average Degree of Concurrency
 Defined as the average number of tasks executing concurrently over the entire program runtime.
 More useful than maximum concurrency for performance evaluation.
 Reflects how well parallelism is sustained during execution.
- Effect of Granularity on Concurrency
 Smaller (finer) granularity:
o Higher maximum degree of concurrency.
o Higher average degree of concurrency.
 Larger (coarser) granularity:
o Lower degree of concurrency.
 Example:
o Fine-grained matrix–vector multiplication shows high concurrency.
o Coarse-grained decomposition shows lower concurrency.
- Effect of Task-Dependency Graph Shape
 Degree of concurrency depends on graph structure.
 Same granularity does not guarantee the same concurrency.
 Different dependency shapes lead to different concurrency levels.
- Key Observation from Example Graphs
 Two task graphs with the same decomposition can have different average concurrency.
  Example values:
o One graph has an average degree of concurrency of 2.33.
o Another has an average degree of concurrency of 1.88.
 Difference arises due to task dependencies and graph structure, not task size alone.

Critical Path
 A key feature of a task-dependency graph.
 Determines the average degree of concurrency for a given granularity.
Start Nodes and Finish Nodes
 Start nodes:
o Tasks with no incoming edges.
o Can begin execution immediately.
 Finish nodes:
o Tasks with no outgoing edges.
o Complete the computation.
Critical Path Definition
 The longest directed path from any start node to any finish node.
 Represents the unavoidable sequential part of the program.
Critical Path Length
 Defined as the sum of weights of nodes on the critical path.
 Node weight = amount of work or computation time of that task.
Average Degree of Concurrency
 Defined as:
o Average degree of concurrency = Total work / Critical path length
 Shorter critical path:
o Higher average concurrency.
 Longer critical path:
o Lower average concurrency.
Example from Figure 3.5
 Figure 3.5(a):
o Total work = 63 (10+10+10+10+6+9+8)
o Critical path length = 27 – longest dependency chain – (10+9+8)
o Average degree of concurrency = 2.33 – (total work/critical path) – (63/27)
 Figure 3.5(b):
o Total work = 64 (10 + 10 + 10 + 10 + 6 + 11 + 7)
o Critical path length = 34 – longest dependency chain – (10+6+11+7)
o Average degree of concurrency = 1.88 – (total work/critical path) – (64/34)
 Same granularity, different critical paths → different concurrency.
Limits of Increasing Granularity
 Increasing granularity does not guarantee unlimited speedup.
 Every problem has a natural limit on how fine it can be decomposed.
 Example: matrix–vector multiplication
o Requires O(n²) operations.
o Cannot be decomposed into more than O(n²) tasks.
Speedup Limitation
 Speedup = serial execution time / parallel execution time.
 Speedup is bounded due to:
o Limited granularity.
o Limited degree of concurrency.
o Task interactions.
Task Interactions
 Tasks often share:
o Input data.
o Output data.
o Intermediate data.
 Dependencies arise when:
o Output of one task is input to another.
Hidden Interactions
 Some interactions are not visible in the task-dependency graph.
 Example:
o In matrix–vector multiplication:
 Tasks are independent.
  All tasks need access to the same input vector.
 Causes communication overhead in distributed-memory systems.
Task-Interaction Graph
 Models communication and data sharing among tasks.
 Nodes represent tasks.
 Edges represent interaction between tasks.
Graph Properties
 Node weights:
o Amount of computation.
 Edge weights:
o Amount of interaction or communication.
 Edges are usually undirected.
 Directed edges indicate one-way data flow.
Relation to Task-Dependency Graph
 Task-interaction graph edges are usually a superset of dependency edges.
 In some problems:
o Task-interaction graph = task-dependency graph.
 Example:
o Database query processing.

 Problem Definition

 Compute y = Ab.
 A is an n × n sparse matrix.
 b is a dense n × 1 vector.
 y is the output vector.

 Sparse Matrix

 Contains many zero entries.

 Non-zero entries have no fixed pattern.
 Efficient computation avoids operations involving zeros.

 Optimized Computation

 To compute y[i]:
o Multiply only non-zero entries in row A[i, *] with corresponding b[j].
 Ignore all zero entries.
 Example:
o y[0] = A[0,0]·b[0] + A[0,1]·b[1] + A[0,4]·b[4] + A[0,8]·b[8]
 Task Decomposition Strategy

 Partition the output vector y.

 Each task computes one element y[i].
 Task i is responsible for:
o Computing y[i]
o Owning row A[i, *]
o Owning element b[i]

 Data Dependency

 Computing y[i] requires multiple b[j] values.

 Many b[j] values are owned by other tasks.
 Tasks must exchange data.

 Message-Passing Paradigm

 Each task owns one element of vector b.

 Ownership implies responsibility for communication.
 Task i:
o Sends b[i] to all tasks that need it.
o Receives required b[j] values from other tasks.

 Example of Communication

 Task 4 owns b[4].

 Task 4 must:
o Send b[4] to Tasks 0, 5, 8, and 9.
o Receive b[0], b[5], b[8], and b[9] for its own computation.

 Task-Interaction Graph

 Nodes represent tasks.

 An edge exists if two tasks exchange data.
 Graph captures communication patterns, not just dependencies.
 Shown in Figure 3.6(b).
3.1.3 Processes and Mapping
Tasks vs Processes
 A problem is first decomposed into tasks.
 Tasks are executed by processes.
 A process here is an abstract computing agent.
 It is not the strict operating-system definition.
 A process:
o Executes a task’s code and data.
o Produces output in finite time.
o May compute, synchronize, or communicate.
Need for Multiple Processes
 Speedup over sequential execution requires:
o Multiple processes active at the same time.
o Each working on different tasks.
Mapping
 Mapping is the assignment of tasks to processes.
 Example:
o In matrix multiplication, each process computes one submatrix.
 Mapping decides where tasks run.
Role of Task Graphs
 Task-dependency graph:
o Shows execution order constraints.
 Task-interaction graph:
o Shows communication between tasks.
 Both graphs guide the choice of a good mapping.
Goals of a Good Mapping
 Maximize use of concurrency:
o Map independent tasks to different processes.
 Minimize total execution time:
o Ensure critical-path tasks execute as soon as possible.
 Minimize communication overhead:
o Map highly interacting tasks to the same process.
Conflicting Objectives
 These goals often conflict.
  Example:
o One task on one process:
 No communication.
 No idle time.
 No speedup.
 Best performance requires a balanced trade-off.
Why Mapping Matters
 Decomposition determines available concurrency.
 Mapping determines:
o How much concurrency is actually used.
o How efficiently it is used.
 Poor mapping can waste available parallelism.
Example with Figure 3.7
 Total tasks = 7.
 Maximum degree of concurrency = 4.
 Therefore:
o At most 4 processes can be used effectively.
 Remaining tasks must wait due to dependencies.
Mapping Remaining Tasks
 Tasks beyond the concurrency limit:
o Can be assigned arbitrarily.
o Must still respect task dependencies.
 Better choice:
o Map tasks with interaction edges to the same process.
Communication Optimization Insight
 If interacting tasks are on different processes:
o Communication becomes inter-process.
o Higher overhead.
 If interacting tasks are on the same process:
o Communication is local.
o Lower overhead.
3.1.4 Processes versus Processors
Processes
 Logical computing agents.
 Execute tasks in a parallel algorithm.
 Abstract entities, not physical hardware.
 Used to describe and design parallel algorithms.
Processors
 Physical hardware units.
 Perform actual computations.
 Examples: CPUs, cores.
Processes vs Processors
 Processes are conceptual.
 Processors are physical.
 Parallel algorithms are expressed in terms of processes, not processors.
One-to-One Correspondence
 Often:
o One process maps to one processor.
o Number of processes equals number of CPUs.
 This assumption simplifies algorithm design.
Why Separate Processes and Processors
 Needed for:
o Complex algorithms.
o Multiple computation stages.
o Different kinds of parallelism.
 Provides a higher level of abstraction.
Multiple Programming Paradigms
 Some hardware supports:
 o Message passing.
o Shared address space.
 Separating processes from processors helps design for such systems.
Example: Hybrid Parallel Computer
 System structure:
o Multiple nodes.
o Nodes communicate via message passing.
o Each node contains multiple CPUs with shared memory.
Example: Matrix Multiplication
 Best designed in two stages.
Stage 1: Inter-node Parallelism
 Use message-passing paradigm.
 Decompose problem across nodes.
 Each task assigned to a node.
 Tasks communicate using messages.
Stage 2: Intra-node Parallelism
 Each task is itself a matrix multiplication.
 Use shared-memory parallelism inside a node.
 Decompose further among CPUs in the same node.
 Exploit multiple CPUs within each node.
Matrix Multiplication Example
 Original problem is decomposed into tasks.
 Each task performs a smaller matrix multiplication.
 Each task:
 Runs on one node.
 Is further parallelized across CPUs within the node.

Decomposi on Techniques
 Decomposition Techniques are used to solve problems in parallel computing.
 The main goal is to split computations into tasks.
 These tasks are executed concurrently.
 Task execution order is represented using a task-dependency graph.
 Decomposition is a fundamental step in designing a parallel program.
 It helps identify where concurrency is possible.
 This section explains commonly used decomposition techniques.
 The list is not exhaustive.
 A single decomposition technique may not always give the best parallel algorithm.
 Still, these techniques provide a good starting point.
 Often, one or more techniques are combined for better results.
 They work for a large variety of problems.
 Decomposition techniques are classified into four types:
 Recursive Decomposition
 Data Decomposition
 Exploratory Decomposition
 Speculative Decomposition
3.2.1 Recursive Decomposition
 Recursive decomposition is a technique used to induce concurrency in problems that follow the
divide-and-conquer strategy.
 The problem is first divided into a set of independent subproblems.
 Each subproblem is solved by recursively applying the same decomposition.
 Results of subproblems are combined to obtain the final solution.
 Independent subproblems can be solved concurrently.
 Concurrency increases as the recursion progresses.

Divide-and-Conquer and Concurrency

 Divide-and-conquer naturally exposes parallelism.
 Each recursive call represents an independent task.
 Tasks at the same level of recursion can execute in parallel.
 The recursive structure forms a task-dependency tree.

Example: Quicksort
 Quicksort is a divide-and-conquer sorting algorithm.
 A pivot element is selected.
 The array is partitioned into two subsequences:
o 𝐴 : elements smaller than the pivot.
o 𝐴 : elements greater than or equal to the pivot.
  Each subsequence is sorted recursively using quicksort.
 Recursion continues until subsequences contain a single element.
 Partitioning of each subsequence is treated as a task.
 After the first partition, two tasks can execute in parallel.
 Concurrency increases at lower levels of the recursion tree.

Task Graph in Quicksort

 Root task partitions the original array.
 Child tasks partition the resulting subsequences.
 Tasks at the same depth in the recursion tree are independent.
 Task graph forms a tree structure.
 Maximum concurrency occurs at the leaf levels.

Serial Minimum-Finding Algorithm (No Concurrency)

 The serial algorithm scans the entire array sequentially.
 Minimum value is updated step by step.
 No parallelism exists in this approach.
Algorithm 3.1: Serial Minimum

procedure SERIAL_MIN (A, n)

begin

min := A[0];

for i := 1 to n - 1 do

if (A[i] < min) then

min := A[i];

endif;

endfor;

return min;

end SERIAL_MIN

Restructuring for Recursive Decomposition

 Serial algorithms may not expose concurrency.
 Restructuring the computation using divide-and-conquer can introduce concurrency.
 Input data is divided into smaller subsets.
 Each subset is processed independently.
 Partial results are combined to obtain the final result.

Recursive Minimum-Finding Algorithm

 Array is divided into two halves.
 Minimum of each half is found recursively.
 Final minimum is obtained by comparing the two results.
 Recursion terminates when subarray size is one.
 Recursive calls can execute in parallel.
Algorithm 3.2: Recursive Minimum

procedure RECURSIVE_MIN (A, n)

begin
 if (n = 1) then

min := A[0];

else

lmin := RECURSIVE_MIN (A, n/2);

rmin := RECURSIVE_MIN (&(A[n/2]), n - n/2);

if (lmin < rmin) then

min := lmin;

else

min := rmin;

endif;

endif;

return min;

end RECURSIVE_MIN

Task-Dependency Graph for Recursive Minimum

 Each task finds the minimum of a small subset.
 Leaf tasks compare pairs of elements.
 Higher-level tasks compare results from child tasks.
 Task graph forms a binary tree.
 Tasks at the same level can execute concurrently.
3.2.2 Data Decomposition
 Technique to derive concurrency by partitioning data.
 Computation is decomposed based on data partitions.
 Performed in two steps:
o Partition the data.
o Use data partitions to induce task partitions.
 Tasks usually perform similar operations on different data parts.
 Multiple data partitioning strategies exist.
 Best strategy depends on efficiency and natural mapping to computation.
Partitioning Output Data
 Applicable when each output element can be computed independently.
 Output data is divided into multiple partitions.
 Each task computes one partition of the output.
 No dependency between tasks during computation.
 Leads to high concurrency and simple task coordination.
Example: Matrix Multiplication
 Output matrix 𝐶 is partitioned into submatrices.
 Each task computes one submatrix of 𝐶.
 Computation uses corresponding submatrices of 𝐴and 𝐵.
 Tasks execute independently.

Data Decomposition vs Task Decomposition

 Data decomposition does not uniquely determine task decomposition.
 Same data partitioning can produce different task decompositions.
 Number of tasks can vary even with identical data partitions.

Partitioning Input Data

 Used when output cannot be partitioned easily.
 Input data is divided into multiple subsets.
 Each task processes one subset of input data.
 Tasks produce intermediate results.
 Intermediate results must be combined to obtain final output.
Example: Sum of Numbers
 Input numbers are partitioned among tasks.
 Each task computes a partial sum.
 Partial sums are combined to get the final sum.
Example: Itemset Frequency
 Transaction database is partitioned.
 Each task computes frequencies for its subset of transactions.
 Partial frequency counts are combined.

Partitioning Both Input and Output Data

 Both input and output data are partitioned.
 Tasks are assigned specific combinations of input and output partitions.
 Increases degree of concurrency.
 Requires combining partial outputs.
 Increases complexity compared to single partitioning.
Partitioning Intermediate Data
 Used in multi-stage algorithms.
 Intermediate results are partitioned to induce concurrency.
 May require restructuring the original algorithm.
 Intermediate data may not be explicitly stored in serial versions.
Example: Matrix Multiplication
 Intermediate matrix stores partial products.
 Each task computes a portion of the intermediate matrix.
 Final stage adds intermediate results to produce output.
 Increases concurrency.
 Requires additional memory.

Owner-Computes Rule
 Each task performs computations related to the data it owns.
 For input partitioning:
o Task performs all computations using its local input data.
 For output partitioning:
o Task computes all assigned output elements.
 Reduces communication overhead.
 Simplifies parallel program design.

3.2.3 Exploratory Decomposition

  Exploratory decomposition is used for problems that involve searching a space of possible solutions.
 The underlying computation corresponds to exploring different possibilities.
 The search space is partitioned into smaller subspaces.
 Each subspace is searched concurrently by different tasks.
 The goal is to find one or more desired solutions.
 Search terminates when a solution is found.

Key Idea of Exploratory Decomposition

 The problem is viewed as a search problem.
 Different parts of the search space are explored in parallel.
 Tasks are not required to complete their entire assigned work.
 Tasks may terminate early once a solution is found by any task.

Example: The 15-Puzzle Problem

 The puzzle consists of:
o 15 numbered tiles.
o 1 blank tile.
o A 4 × 4 grid.
 A move consists of sliding a tile into the blank space.
 Possible moves: up, down, left, right.
 Initial and final configurations are given.
 Objective:
o Find any valid sequence of moves, or
o Find the shortest sequence of moves from initial to final configuration.
State Space Representation
 The problem is solved using tree-search techniques.
 Each configuration of the puzzle represents a state.
 All possible successor configurations are generated from a state.
 A state may have 2, 3, or 4 successors.
 The collection of all configurations forms a state space graph.
 Nodes represent configurations.
 Edges represent a single valid move.

Parallel Solution Using Exploratory Decomposition

 Initial levels of the search tree are generated serially.
 Generation continues until a sufficient number of leaf nodes are obtained.
 Each leaf node is assigned to a separate task.
 Each task explores its assigned subtree independently.
 Tasks search concurrently for the final configuration.
 As soon as one task finds a solution:
o It reports success.
o Other tasks are terminated.

Task Behavior in Exploratory Decomposition

 Tasks explore different parts of the search space.
 Tasks may not finish their assigned exploration.
 Only one successful task is sufficient to solve the problem.
  Remaining tasks may stop early.

Difference Between Exploratory and Data Decomposition

 In data decomposition:
o All tasks perform useful computation.
o All tasks must complete their work.
 In exploratory decomposition:
o Tasks may terminate early.
o Some tasks may perform unnecessary work.
o Only one task needs to find a solution.

Work Performed: Parallel vs Serial Search

 Amount of work in parallel search can differ from serial search.
 Parallel search may perform:
o Less work than serial search.
o More work than serial search.

Case 1: Solution Found Early

 Solution lies near the beginning of one task’s search space.
 Parallel formulation finds the solution quickly.
 Serial algorithm would have searched other spaces first.
 Parallel version performs less work and achieves speedup.

Case 2: Solution Found Late

 Solution lies deep in one task’s search space.
 Other tasks explore their entire spaces unnecessarily.
 Parallel formulation may perform significantly more work.
 Little or no speedup is achieved.
 a-early, b-late
3.2.4 Speculative Decomposition
 Speculative decomposition is used when a program can follow one of many possible computational
paths.
 The next computation depends on the result of a previous computation.
 While one task computes the result that decides the next step, other tasks speculatively compute
possible next steps.
 Only the computation corresponding to the correct outcome is finally used.
 Other speculative computations are discarded.
 This reduces parallel runtime but introduces wasted computation.

Core Idea of Speculative Decomposition

 Future computation paths are started before the controlling decision is known.
 Assumes multiple possible outcomes.
 Trades extra work for reduced execution time.
 Similar to executing branches of a conditional statement in advance.

Speculative Execution of Conditional Branches

 One task computes the condition (e.g., switch or if statement).
 Other tasks concurrently execute different branches.
 When the condition is resolved:
o Correct branch result is retained.
o Results of incorrect branches are discarded.
 Parallel runtime is reduced by overlapping computation.
Cost of Speculative Decomposition
 Guarantees some amount of wasted computation.
 Aggregate work is greater than the serial algorithm.
 Benefit depends on:
o Cost of evaluating the condition.
o Cost of speculative computations.

Optimized Speculative Decomposition

 Used when one branch is more likely than others.
 Only the most probable branch is speculatively executed.
 If speculation is correct:
o Execution is faster.
 If speculation is incorrect:
o Computation is rolled back.
o Correct branch is executed.
 Reduces wasted computation compared to full speculation.

Multiple Speculative Stages

 Speedup can accumulate across multiple speculative stages.
 Useful in long pipelines or multi-stage computations.
 Effectiveness depends on accuracy of speculation.

Example: Parallel Discrete Event Simulation

 System is modeled as a directed graph or network.
 Nodes represent components.
 Each component:
o Has an input buffer.
o Processes jobs when idle.
o Sends output jobs to neighboring components.
 Processing time and output depend on job type.
 Components may block if output buffers are full.
  Goal:
o Simulate system behavior.
o Compute total completion time and other metrics.

Why the Problem Appears Sequential

 Output of one component is input to another.
 Processing order seems strictly dependent.
 Appears difficult to parallelize directly.

Applying Speculative Decomposition to Simulation

 Speculative tasks simulate parts of the network in advance.
 Each task assumes a possible input scenario.
 When the actual input becomes available:
o If speculation was correct, work is reused.
o If speculation was incorrect, simulation is restarted.
 Enables overlap of dependent computations.

Speculative vs Exploratory Decomposition

Speculative Decomposition
 Input to a branch is unknown.
 Only one branch is correct.
 Serial algorithm knows which branch to take.
 Parallel algorithm performs extra work.
 Aggregate work ≥ serial work.
Exploratory Decomposition
 Output of branches is unknown.
 Multiple branches may need exploration.
 Serial algorithm explores alternatives sequentially.
 Parallel algorithm may perform more, less, or equal work.

Work Comparison with Serial Algorithm

 Speculative decomposition always performs:
o More or equal aggregate work than serial.
 Speedup comes from overlapping future computation.
 Benefit depends on correctness of speculation.

3.2.5 Hybrid Decompositions

 Hybrid decomposition combines two or more decomposition techniques.
 Decomposition techniques are not mutually exclusive.
 Different stages of a computation may benefit from different types of decomposition.
 Hybrid approaches are used to improve efficiency and scalability.
 Commonly applied when a single decomposition technique is insufficient.

Need for Hybrid Decomposition

 Pure decomposition techniques may create:
o Too many tasks.
o Too little effective concurrency.
 Number of tasks may exceed available processes.
 Task sizes may be uneven.
 Hybrid decomposition balances:
o Task granularity.
o Degree of concurrency.
o Resource utilization.

Example: Finding Minimum of n Numbers

  Pure recursive decomposition creates many small tasks.
 Number of tasks may be much larger than number of processors 𝑃.
 Efficient hybrid approach:
o Partition input into 𝑃roughly equal parts.
o Assign each part to one task.
o Each task computes the local minimum.
 Final minimum is obtained by:
o Applying recursive decomposition on the 𝑃local minima.
 Combines:
o Input data decomposition.
o Recursive decomposition.

Hybrid Decomposition Structure (Minimum Finding)

 Stage 1:
o Input is partitioned into 𝑃parts.
o Tasks compute local minima in parallel.
 Stage 2:
o Recursive decomposition combines intermediate results.
 Reduces number of tasks.
 Improves efficiency and scalability.

Example: Parallel Quicksort

 Recursive decomposition alone produces 𝑂(𝑛)tasks.
 Task dependencies reduce effective concurrency.
 First partitioning step takes 𝑂(𝑛)time.
 This step limits achievable speedup.

Hybrid Decomposition for Quicksort

 Recursive decomposition is used for dividing the problem.
 Input data decomposition is applied during the partitioning step.
 Partitioning of lists is done in parallel.
  Results in:
o Higher concurrency.
o Better load balancing.
o Improved parallel performance.

Benefits of Hybrid Decomposition

 Reduces excessive task creation.
 Improves utilization of available processors.
 Balances task sizes.
 Overcomes limitations of single decomposition methods.
 Leads to more scalable parallel algorithms.

3.3 Characteris cs of Tasks and Interac ons

 Decomposition techniques help identify concurrency and generate tasks.
 Next step is to assign tasks to available processes.
 This assignment is called mapping.
 Mapping decisions are influenced by:
o Nature of tasks.
o Interactions among tasks.
 Efficient mapping is crucial for good parallel performance.
 Characteristics of tasks guide the choice of mapping scheme.

3.3.1 Characteristics of Tasks

 Four major characteristics influence task-to-process mapping:
1. Task generation
2. Task sizes
3. Knowledge of task sizes
4. Size of data associated with tasks

1. Task Generation
 Tasks may be generated:
o Statically
 o Dynamically
Static Task Generation
 All tasks are known before execution begins.
 Task-dependency graph is fixed.
 Commonly produced by data decomposition.
 Examples:
o Matrix multiplication
o LU factorization
o Recursive minimum finding
 Enables simpler and predictable mapping.
Dynamic Task Generation
 Tasks are created during execution.
 Task-dependency graph is not fully known in advance.
 Size and shape depend on input data.
 Recursive decomposition can lead to dynamic task generation.
 Example:
o Quicksort
 Same input size may produce different task graphs.
Exploratory Decomposition and Task Generation
 Can generate tasks statically or dynamically.
Static exploratory task generation
 Initial task expands search tree to a fixed depth.
 Generated states become independent tasks.
 Tasks are executed in parallel.
Dynamic exploratory task generation
 Each task expands a state.
 New tasks are spawned during execution.
 Algorithm terminates when solution is found.

2. Task Sizes
 Task size refers to time required to complete a task.
 Tasks can be:
o Uniform
 o Non-uniform
Uniform Tasks
 All tasks take approximately the same time.
 Easier to map to processes.
 Example:
o Matrix multiplication tasks
Non-Uniform Tasks
 Tasks take different amounts of time.
 Harder to balance load.
 Example:
o Quicksort tasks
 May lead to load imbalance if poorly mapped.

3. Knowledge of Task Sizes

 Task sizes may be:
o Known in advance
o Unknown in advance
Known Task Sizes
 Enables informed mapping decisions.
 Helps distribute workload evenly.
 Example:
o Matrix multiplication tasks
 Computation time predictable before execution.
Unknown Task Sizes
 Task execution time cannot be predicted.
 Mapping decisions become difficult.
 Example:
o 15-puzzle problem
 Number of moves to reach solution is unknown.

4. Size of Data Associated with Tasks

 Each task has associated input and output data.
  Data must be accessible to the process executing the task.
 Size and location of data affect:
o Mapping decisions
o Communication overhead
Input vs Output Data Sizes
 Input data may be small, output large, or vice versa.
Examples:
 15-puzzle:
o Input is one puzzle state (small).
o Computation may be very large.
 Minimum finding:
o Input size proportional to computation.
o Output is a single value.
 Parallel quicksort:
o Input and output sizes proportional to computation time.
3.3.2 Characteristics of Inter-Task Interactions
 In parallel algorithms, tasks must interact to:
o Share data
o Share work
o Perform synchronization
 Different algorithms require different interaction patterns.
 Nature of interactions affects:
o Choice of programming paradigm
o Mapping scheme
o Performance
 Inter-task interactions can be classified along multiple dimensions.

1. Static vs Dynamic Interactions

Static Interactions
 Interaction pattern is known before execution.
 Tasks interact at predetermined times.
 Set of interacting tasks is fixed.
 Task-interaction graph is known a priori.
  Stage of computation where interaction occurs is known.
 Easier to program in message-passing systems.
 Example:
o Parallel matrix multiplication
 Well suited for predictable communication patterns.
Dynamic Interactions
 Interaction timing is not known before execution.
 Interacting tasks may change during runtime.
 Task-interaction graph is not fully known in advance.
 Harder to implement in message-passing systems.
 Requires additional synchronization or polling.
 Easier to implement in shared-address-space systems.
Example: 15-puzzle problem
 Some tasks may exhaust their search space early.
 Idle tasks may steal unexplored states from busy tasks.
 Work transfer between tasks occurs dynamically.

2. Regular vs Irregular Interactions

Regular Interactions
 Interaction pattern has a predictable structure.
 Spatial or logical regularity can be exploited.
 Easier to optimize and implement efficiently.
 Common in grid-based or structured problems.
Example: Image Dithering
 Image divided into square regions.
 Each task processes one region.
 Tasks require boundary pixel values from neighboring regions.
 Interaction graph forms a 2D mesh.
 Communication pattern is fixed and structured.
Irregular Interactions
 No predictable interaction structure.
 Communication pattern depends on data values.
 Harder to manage and optimize.
 Particularly difficult in message-passing systems.
Example: Sparse Matrix–Vector Multiplication
 Each task knows its assigned matrix rows.
 Required vector elements depend on sparsity pattern.
 Access pattern for vector cannot be predicted beforehand.

3. Read-Only vs Read-Write Interactions

Read-Only Interactions
 Tasks only read shared data.
 No task modifies the shared data.
 No synchronization required for data consistency.
 Easier to implement.
Example: Parallel Matrix Multiplication
 Tasks read matrices A and B.
 No task modifies shared input matrices.
Read-Write Interactions
 Tasks both read and modify shared data.
  Requires synchronization to maintain correctness.
 More complex to implement.
Example: Heuristic Search in 15-Puzzle
 States stored in a shared priority queue.
 Tasks:
o Insert new states (write)
o Extract promising states (read)
 Queue is updated dynamically during execution.

4. One-Way vs Two-Way Interactions

Two-Way Interactions
 Both tasks actively participate.
 Typically producer–consumer relationship.
 Explicit communication between sender and receiver.
 Naturally supported in message-passing systems.
One-Way Interactions
 Only one task initiates the interaction.
 Receiving task is not explicitly involved.
 Common in read-only interactions.
 Easier in shared-address-space systems.

Programming Paradigm Considerations

Shared-Address-Space Paradigm
 Handles:
o Static interactions
o Dynamic interactions
o One-way interactions
o Two-way interactions
 Simpler interaction implementation.
Message-Passing Paradigm
 Requires both sender and receiver participation.
 Cannot directly support one-way interactions.
  One-way interactions must be converted to two-way interactions.

Converting One-Way to Two-Way Interactions

Static One-Way Interactions
 Easy to convert.
 Matching send/receive calls added.
 Location and timing are known beforehand.
Dynamic One-Way Interactions
 Difficult to convert.
 Require program restructuring.
 Common technique: polling
o Tasks periodically check for requests.
o Pending requests are serviced when detected.

3.4 Mapping Techniques for Load Balancing

 After decomposition, tasks must be mapped onto processes.
 Objective of mapping:
o Minimize total execution (elapsed) time.
 Efficient mapping reduces parallel overheads.

Sources of Overhead in Parallel Execution

 Inter-process interaction overhead
o Time spent in communication and synchronization.
 Process idling overhead
o Some processes remain idle while others are still executing.

Reasons for Process Idling

 Uneven distribution of tasks among processes.
 Some processes finish earlier than others.
 Task-dependency constraints cause tasks to wait.
 Poor synchronization between interacting tasks.
Objectives of a Good Mapping
 Reduce time spent in inter-process interactions.
 Reduce idle time of processes.
 Ensure balanced computation and interaction at each stage.

Conflict Between Mapping Objectives

 Assigning interacting tasks to the same process:
o Reduces communication overhead.
o Often causes severe load imbalance.
 Assigning tasks evenly across processes:
o Improves load balance.
o May increase communication overhead.
 Mapping all interacting tasks to one process:
o Eliminates communication.
o Eliminates parallelism.
 Therefore, finding an optimal mapping is nontrivial.

Balanced Load Is Necessary but Not Sufficient

 Equal total work per process does not guarantee minimal idle time.
 Tasks are not all executable at the same time.
 Task-dependency graph restricts parallel execution.
 At certain stages:
o Some processes are active.
o Others wait due to dependencies.
 Poor synchronization can also introduce idling.

Stage-wise Balance Requirement

 Mapping must ensure:
o Balanced computation at each execution stage.
o Balanced interactions at each execution stage.
 Different mappings with equal total workload can have different completion times.
  Dependency-induced synchronization affects performance.

Classification of Mapping Techniques

 Mapping techniques are broadly classified into:
o Static mapping
o Dynamic mapping
 Choice depends on:
o Task characteristics
o Interaction characteristics
o Programming paradigm

Static Mapping
 Tasks are assigned to processes before execution begins.
 Applicable to statically generated tasks.
 Can also be used for dynamically generated tasks in some cases.
 Mapping decision depends on:
o Knowledge of task sizes
o Size of data associated with tasks
o Inter-task interaction patterns
o Programming paradigm used
 Optimal static mapping for non-uniform tasks is NP-complete.
 Practical solutions use heuristics.
 Advantages:
o Easier to design
o Easier to program
o Predictable behavior

Dynamic Mapping
 Tasks are assigned to processes during execution.
 Mandatory when tasks are generated dynamically.
 Preferred when:
 o Task sizes are unknown
o Load imbalance is likely
 Can cause significant data movement overhead.
 If task data is large:
o Data transfer cost may outweigh benefits.
 Static mapping may be better in such cases.

Dynamic Mapping and Memory Models

 In shared-address-space systems:
o Dynamic mapping may work well for read-only data.
 Data movement overhead still exists:
o NUMA systems cause remote memory access.
o cc-UMA systems may require cache-to-cache transfers.
 Shared-address-space does not eliminate data movement cost.

Complexity Considerations
 Dynamic mapping:
o More complex to design
o Especially difficult in message-passing systems
 Static mapping:
o Simpler implementation
o Lower runtime overhead
3.4.1 Schemes for Static Mapping
 Static mapping is commonly used with:
o Data-partitioning based decomposition
o Problems having a static task-dependency graph
 Tasks are mapped to processes before execution begins
 Mapping schemes discussed are based on:
o Data partitioning
o Task partitioning
Mappings Based on Data Partitioning
 Data partitioning induces task decomposition
 Decomposition is selected with the final mapping in mind
 Common data representations considered:
o Arrays
o Graphs

Array Distribution Schemes

 Tasks are associated with data using the owner-computes rule
 Mapping data to processes is equivalent to mapping tasks
 Common techniques are used to distribute arrays or matrices

Block Distributions
 Simplest form of array distribution
 Each process gets a uniform, contiguous block of data
 Applicable to d-dimensional arrays
 Partitioning is done along one or more dimensions
 Particularly suitable when:
o There is locality of interaction
o Computation depends on nearby array elements

One-Dimensional Block Distribution

 Partitioning is done along one dimension
 For an n × n array:
o Row-wise partitioning:
 Each process gets n/p consecutive rows
o Column-wise partitioning:
 Each process gets n/p consecutive columns
 Illustrated using row-wise and column-wise distributions

Two-Dimensional Block Distribution

  Partitioning is done along two dimensions
 Matrix is divided into blocks of size:
o n/p₁ × n/p₂
 Number of processes:
o p = p₁ × p₂
 Processes are arranged in a 2D grid

Generalization to Higher Dimensions

 A d-dimensional array can be partitioned using:
o Up to d-dimensional block distributions
 Higher-dimensional distributions:
o Increase flexibility
o Allow higher concurrency

Load Balancing with Block Distributions

 Uniform blocks result in balanced computation
 Effective when:
o Each array element requires equal computation
 Widely used in dense numerical computations

Example: Matrix Multiplication (C = A × B)

 Decomposition is done by partitioning output matrix C
 Each element of C requires equal computation
 Uniform block distribution balances the load

One-Dimensional Distribution for Matrix Multiplication

 Each process computes:
o n/p rows or columns of C
 Maximum number of processes:
o n
 Higher communication overhead
Two-Dimensional Distribution for Matrix Multiplication
 Each process computes:
o A block of C
 Maximum number of processes:
o n²
 Better scalability
 Reduced communication overhead

Advantages of Higher-Dimensional Distributions

 Allow more processes to be used
 Increase degree of concurrency
 Reduce inter-process interactions

Communication Comparison
 One-dimensional distribution:
o Each process accesses:
 n²/p elements of A
 Entire matrix B (n²)
o Total shared data accessed: O(n²)
 Two-dimensional distribution:
o Each process accesses:
 n²/p elements of A
 n²/p elements of B
o Total shared data accessed: O(n²/p)
 Two-dimensional distribution significantly reduces communication

Cyclic and Block-Cyclic Distributions

 Block distribution assumes uniform workload
 If workload varies:
o Block distribution causes load imbalance
  Example:
o LU factorization
o Computation increases toward bottom-right of matrix

LU Factorization Characteristics
 Active matrix shrinks toward bottom-right during computation
 Processes assigned to early rows/columns:
o Perform less work
 Processes assigned to later rows/columns:
o Perform more work
 Results in:
o Load imbalance
o Process idling

Problems with Naive Block Mapping in LU

 Different blocks require different computation amounts
 Some processes finish early and remain idle
 Dependency constraints cause further idling
 Final blocks require multiple tasks, earlier blocks require few

Block-Cyclic Distribution
 Variation of block distribution
 Used to reduce:
o Load imbalance
o Process idling
 Array is partitioned into many more blocks than processes
 Blocks are assigned in a round-robin (wraparound) fashion

One-Dimensional Block-Cyclic Distribution

 Rows or columns divided into a·p blocks
 Each block contains n/(a·p) rows or columns
  Block bi is assigned to process Pi % p
 Each process receives:
o a non-adjacent blocks

Two-Dimensional Block-Cyclic Distribution

 Matrix divided into square blocks
 Blocks distributed in wraparound fashion on a 2D process grid
 Extensible to higher-dimensional arrays

Benefits of Block-Cyclic Distribution

 Each process gets work from different matrix regions
 Load balances even when work is uneven
 Higher probability that some assigned tasks are ready
 Reduces idle time significantly

Cyclic Distribution
 Extreme case of block-cyclic distribution
 Block size equals:
o One row (1D)
o One element (2D)
 Provides near-perfect load balance
 Disadvantages:
o Poor data locality
o High communication overhead
 Not practical for performance-critical applications

Choosing Block Size (a)

 Small a:
o Better locality
o Lower communication
 Large a:
 o Better load balance
o Higher communication
 Optimal a balances:
o Load balance
o Interaction overhead

Randomized Block Distributions

 Used when block-cyclic fails to balance load
 Suitable for:
o Irregular or patterned sparse data
 Blocks are assigned randomly to processes
 Improves load balance in skewed workloads

One-Dimensional Randomized Block Distribution

 Vector V of size a·p is created
 V is randomly permuted
 Each process gets a consecutive segment of V
 Blocks assigned according to permuted order

Two-Dimensional Randomized Block Distribution

 Row and column block indices are randomly permuted
 Blocks assigned using these permutations
 More effective than block-cyclic for irregular sparsity

Graph Partitioning
 Used for:
o Sparse data structures
o Irregular interaction patterns
 Common in:
o Physical simulations
o Mesh-based computations
Mesh-Based Computations
 Physical domain discretized into mesh points
 Each computation depends on:
o Local mesh point
o Adjacent mesh points
 Equal work per point → easy load balance
 Poor partitioning leads to high communication

Goal of Graph Partitioning

 Divide mesh into p parts such that:
o Each part has equal number of vertices
o Number of edges crossing partitions is minimized
 Optimal partitioning is NP-complete
 Heuristic algorithms provide good approximations

Advantages of Graph Partitioning

 Reduces inter-process communication
 Preserves spatial locality
 Assigns contiguous mesh regions to processes

Mappings Based on Task Partitioning

 Used when:
o Task-dependency graph is static
o Task sizes are known
 Objectives:
o Minimize idle time
o Minimize interaction cost
 Optimal mapping is NP-complete
 Heuristics often give acceptable solutions
Example: Binary Tree Task-Dependency Graph
 Arises in recursive decomposition
 Tasks along a branch mapped to same process
 Minimizes communication
 Inherent idling cannot be eliminated
 Mapping does not introduce additional idling

Task-Interaction Graph Partitioning

 Applicable when tasks interact irregularly
 Example:
o Mesh simulations
o Sparse matrix-vector multiplication
 Partitioning reduces communication overhead

Sparse Matrix-Vector Multiplication Example

 Naive mapping causes excessive communication
 Graph-partition-based mapping:
o Reduces data exchanges
o Minimizes accesses to remote vector elements

Hierarchical Mappings
 Used when:
o Task-dependency graph limits concurrency
 Tasks are further decomposed into subtasks
 Mapping is applied at multiple levels

Hierarchical Mapping Strategy

 Top-level tasks partitioned using task partitioning
 Lower-level tasks partitioned using data decomposition
 Different mapping techniques used at different layers
Applications of Hierarchical Mapping
 Parallel quicksort
 Sparse matrix factorization
 Elimination trees in sparse solvers
 Combines:
o Task partitioning
o Array/data partitioning
3.4.2 Schemes for Dynamic Mapping (in points)
Overview of Dynamic Mapping
 Dynamic mapping is used when static mapping causes severe load imbalance.
 Required when the task-dependency graph changes during execution.
 Primary goal is to balance workload among processes.
 Often referred to as dynamic load balancing.
 Dynamic mapping schemes are classified into centralized and distributed approaches.
Centralized Dynamic Mapping Schemes
 All executable tasks are maintained in a single central data structure.
 Task management may be handled by:
o A common shared structure, or
o A special process called the master, with other processes acting as slaves.
 Idle processes request work from the master or central pool.
 Newly generated tasks are added to the central pool or reported to the master.
 Easier to design and implement compared to distributed schemes.
 Scalability is limited due to contention for the central structure.
 Becomes a bottleneck as the number of processes increases.
Example: Self Scheduling
 Sorting each row of an 𝑛 × 𝑛matrix in parallel.
 Sorting time varies due to differences in initial row order.
 Static assignment of equal rows per process may cause imbalance.
 A central pool maintains indices of unsorted rows.
 Idle processes pick a row index, remove it from the pool, and sort that row.
 Known as self scheduling of loop iterations.
 Provides good load balance for independent tasks.
Chunk Scheduling
 Assigning one task at a time can overload the shared work queue.
 If task size is small, scheduling overhead becomes significant.
 In chunk scheduling, processes receive multiple tasks at once.
 Reduces overhead of frequent task assignments.
 Large chunk sizes may cause load imbalance.
 To reduce imbalance, chunk size is decreased as execution progresses.
 Chunk size may decrease linearly or non-linearly using predefined schemes.
Distributed Dynamic Mapping Schemes
 Executable tasks are initially distributed among processes.
 Processes exchange tasks at runtime to balance the workload.
 Any process can send or receive work from any other process.
 Avoids centralized bottlenecks.
 More complex to design and manage.
Key Design Parameters in Distributed Schemes
 Method for pairing sender and receiver processes.
 Whether load balancing is:
o Sender-initiated, or
o Receiver-initiated.
 Amount of work transferred per exchange.
 Timing of work transfer:
o After a process becomes idle, or
o When it anticipates running out of work.
 Poor parameter choices may lead to excessive communication or imbalance.
Suitability to Parallel Architectures
 Both centralized and distributed schemes can be implemented on:
o Message-passing systems, and
o Shared-address-space systems.
 Dynamic load balancing requires task movement between processes.
 On message-passing systems:
o Task computation cost must be much higher than communication cost.
 On shared-address-space systems:
o Tasks are not explicitly moved.
o Data movement occurs implicitly through caches or memory banks.
  Finer-grained tasks are more feasible on shared-address-space architectures.

Minimizing Interac on Overheads

1. Maximize data locality

 Reuse intermediate data wherever possible.

 Restructure computa ons so data is reused within smaller me windows.

 Reduce repeated access to nonlocal data.

2. Minimize volume of data exchange

 Each communicated word has an associated cost.

 Reduce the total amount of data communicated between processes.

 Prefer local computa on over shared or remote data access.

3. Minimize frequency of interac ons

 Each interac on has a startup overhead.

 Merge mul ple small interac ons into a single larger interac on where possible.

 Batch communica on opera ons to reduce overhead.

4. Minimize conten on and hot-spots

 Avoid centralized access to shared data structures.

 Use decentralized techniques for data access.

 Replicate data when necessary to reduce conten on.

5. Overlap computa on with interac on

 Use non-blocking communica on to allow computa on during communica on.

 Employ mul threading to hide communica on latency.

 Use data prefetching to fetch required data in advance.

6. Replicate data or computa ons

 Duplicate read-heavy data to avoid repeated communica on.

 Replicate computa ons when communica on cost outweighs computa on cost.

7. Use group communica ons

 Prefer collec ve communica on primi ves over point-to-point messaging.

 Reduce communica on overhead and simplify synchroniza on.

8. Overlap interac ons with other interac ons

 Schedule communica ons so that one interac on proceeds while another is wai ng.

 Improve overall u liza on of communica on resources.

Parallel Algorithm Models
1. Algorithm model

 A method of structuring a parallel algorithm.

 Involves selec ng an appropriate decomposi on technique.

 Involves choosing a suitable mapping strategy.

 Applies techniques to minimize interac on and communica on overheads.

2. Data Parallel Model

 Tasks are sta cally or semi-sta cally mapped to processes.

 Each task performs the same opera ons on different por ons of data.

 Emphasizes data decomposi on and uniform computa on.

3. Task Graph Model

 Based on a task-dependency graph.

 U lizes interrela onships among tasks.

 Promotes data locality and reduces interac on costs.

4. Master–Slave Model

 One or more master processes generate and distribute work.

 Worker (slave) processes execute assigned tasks.

 Work alloca on can be sta c or dynamic.

5. Pipeline / Producer–Consumer Model

 Data flows as a stream through mul ple stages.

 Each process performs a specific opera on on the data.

 Different stages can operate concurrently on different data items.

6. Hybrid Models

 Combine mul ple algorithm models.

 Models may be applied hierarchically (different levels).

 Models may be applied sequen ally to different phases of an algorithm

OpenMP - Introduc on
 OpenMP (Open Mul -Processing) is an Applica on Programming Interface (API).

 It is used for shared memory parallel programming.

 It supports portable parallel programs across different systems.

 It is designed for applica ons from many disciplines.

  OpenMP allows incremental paralleliza on.

 You can start with a sequen al program.

 Then, small parts are parallelized step by step.

 This makes debugging and learning easier.

 OpenMP supports single source code.

 The same code works as:

o Sequen al version

o Parallel version

 This simplifies program maintenance.

 OpenMP provides:

o Direc ves (compiler instruc ons)

o Library func ons

o Environment variables

 These are used to create, manage, and control parallel execu on.

 OpenMP is smaller and simpler than MPI.

 The full feature set is easy to learn.

Core OpenMP Constructs

 Parallel Construct

o Creates a team of threads.

o Code inside runs in parallel.

Work-Sharing Constructs

(Used to divide work among threads)

 Loop Construct

o Splits loop itera ons across threads.

 Sec ons Construct

o Different threads execute different code blocks.

 Single Construct

o Only one thread executes the code block.

 Workshare Construct (Fortran only)

 o Automa cally divides work among threads.

Clauses (Control behavior of constructs)

 Data-Sharing Clauses

o Control shared and private variables.

 Schedule Clause

o Controls distribu on of loop itera ons.

 No Wait Clause

o Removes implicit synchroniza on at the end.

Thread Synchroniza on and Control Features

 Barrier Construct

o All threads wait un l everyone reaches the barrier.

 Cri cal Construct

o Only one thread at a me executes the block.

 Atomic Construct

o Ensures safe update of a single memory loca on.

 Locks

o Used for explicit control of mutual exclusion.

 Master Construct

o Code executed by the master thread only.

Addi onal Features

 OpenMP includes library rou nes:

o To control number of threads.

o To query thread informa on.

 OpenMP includes environment variables:

o To control execu on behavior at run me.

Data scoping a ribute clauses

 Clauses are op onal addi ons to OpenMP direc ves.

 They control the behavior of parallel and work-sharing constructs.

  Clauses are essen al in prac ce for correctness and performance.

 They mainly control data-sharing, synchroniza on, and execu on behavior.

 Clauses are evaluated before entering the construct.

 Variables used in clauses must be defined outside the construct.

 Mul ple clauses can be used with one direc ve.

 Order of clauses does not ma er.

 Programmers must not assume any evalua on order.

Shared Clause

 Syntax: shared(list)

 Specifies variables that are shared among all threads.

 There is one single instance of the variable.

 All threads can read and write the variable.

 Example meaning:

o All threads update different elements of a shared array.

o A er the parallel region, updated values are available to the master thread.

 Important cau on:

o Mul ple threads may access the same memory loca on.

o This can cause data races.

o The programmer must ensure proper synchroniza on.

o OpenMP provides constructs like cri cal, atomic, and barrier to help.

Example:

#pragma omp parallel for shared(a)

for (i=0; i<n; i++)

a[i] += i;

Private Clause

 Syntax: private(list)

 Each thread gets its own local copy of the variable.

  Changes made by one thread are not visible to others.

 Common use:

o Loop itera on variables.

o Temporary variables inside parallel regions.

 By default:

o Loop itera on variables are private.

o However, it is recommended to specify explicitly.

 Key property:

o Values of private variables are undefined on entry and exit of the construct.

o Outer variables with the same name become undefined a er the construct.

 Purpose:

o Prevents data race condi ons.

o Ensures independent execu on by threads.

Example:

#pragma omp parallel for private(i,a)

for (i=0; i<n; i++)

a = i+1;

prin ("Thread %d has a value of a = %d for i = %d\n",

omp_get_thread_num(),a,i);

Lastprivate Clause

 Syntax: lastprivate(list)

 Used with:

o Work-sharing loop

o Sec ons construct

 Purpose:

o Makes the last value of a private variable available a er the construct.

 Meaning of “last”:

o For loops: value from the last itera on in sequen al order.

 o For sec ons: value from the lexically last sec on.

 Use case:

o When a value computed inside a parallel loop is needed later.

 Notes:

o Private variables normally disappear a er the construct.

o lastprivate preserves only the final logical value.

 Performance:

o May introduce overhead.

o More expensive with dynamic scheduling.

Example:

#pragma omp parallel for private(i) lastprivate(a)

for (i=0; i<n; i++)

a = i+1;

prin ("Thread %d has a value of a = %d for i = %d\n",

omp_get_thread_num(),a,i);

} /*-- End of parallel for --*/

prin ("Value of a a er parallel for: a = %d\n",a);

Firstprivate Clause

 Syntax: firstprivate(list)

 Variables are:

o Private to each thread

o Ini alized with pre-exis ng values before entering the construct

 Supported on:

o Parallel

o Loop

o Sec ons

o Single constructs

 Purpose:

o Used when private variables need ini al values.

  Key points:

o Ini aliza on is done by the ini al thread.

o A er ini aliza on, each thread modifies its own copy.

 Alterna ve:

o Read-only values can be passed as shared variables.

o This avoids ini aliza on overhead.

 Performance note:

o On cc-NUMA systems, firstprivate may be preferable.

Example:

for(i=0; i<vlen; i++) a[i] = -i-1;

indx = 4;

#pragma omp parallel default(none) firstprivate(indx) \

private(i,TID) shared(n,a)

TID = omp_get_thread_num();

indx += n*TID;

for(i=indx; i<indx+n; i++)

a[i] = TID + 1;

} /*-- End of parallel region --*/

prin ("A er the parallel region:\n");

for (i=0; i<vlen; i++)

prin ("a[%d] = %d\n",i,a[i]);

Default Clause

 Syntax (C/C++): default(none | shared)

 Syntax (Fortran): default(none | shared | private)

 Purpose:

o Sets the default data-sharing a ribute for variables.

o Reduces the need to list many variables explicitly.

 Common usage:

o default(shared) → variables are shared unless specified otherwise.

 o default(none) → all variables must be explicitly declared.

 Best prac ce:

o Use default(none) to avoid accidental data-sharing bugs.

Example: #pragma omp for default(shared) private(a,b,c)

Nowait Clause

 Purpose:

o Removes the implicit barrier at the end of a work-sharing construct.

 Risk:

o Threads may con nue execu on before shared data is ready.

 Use only when:

o The algorithm does not depend on synchroniza on.

Example:

#pragma omp for nowait

for (i=0; i<n; i++)

............

Schedule Clause

 Schedule clause controls how loop itera ons are assigned to threads.

 It is supported only on the loop construct.

 It has a major impact on performance.

 Syntax:
schedule(kind [, chunk_size])

Basic Concepts

 Itera on space: All itera ons of a loop.

 Chunk:

o A con guous, nonempty set of itera ons.

o Assigned as a unit to a thread.

 chunk_size:
 o Number of itera ons per chunk.

o Must be a posi ve integer.

o Can be any loop-invariant expression.

Schedule Kinds

Sta c Schedule

 Itera ons are divided once at the start.

 Each thread gets a fixed set of itera ons.

 Lowest overhead.

 O en the default, but should not be assumed.

 Best when:

o Work per itera on is uniform.

o Load is predictable.

 With chunk size:

o sta c,1 → round-robin distribu on.

o Larger chunk sizes → block distribu on.

Dynamic Schedule

 Threads request new chunks at run me.

 Load is balanced dynamically.

 Higher overhead than sta c.

 Best when:

o Workload is irregular or unpredictable.

 Itera ons are not con guous for a thread.

 Assignment is nondeterminis c.

Guided Schedule

 Similar to dynamic scheduling.

 Chunk size:

o Large at the beginning.

o Decreases over me.

  Reduces overhead ini ally.

 Improves load balancing near the end.

 Used for imbalanced workloads.

Run me Schedule

 Schedule and chunk size are chosen at run me.

 Uses environment variable:

o OMP_SCHEDULE

 Useful when:

o Best schedule is not known at compile me.

o Depends on problem size or number of threads.

Chunk Size Effects

 Meaning of chunk size depends on the schedule type.

 Larger chunks:

o Lower overhead.

o Poten al load imbalance.

 Smaller chunks:

o Be er load balance.

o Higher overhead.

Determinism and Correctness

 Sta c schedule:

o Determinis c.

o Same itera on always goes to the same thread.

 Dynamic and guided schedules:

o Nondeterminis c.

o Assignment depends on:

 Execu on speed.

 System load.

 Programs must not depend on:

 o Which thread executes a par cular itera on.

 Such programs are nonconforming.

Performance Considera ons

 Sta c schedule:

o Best performance in most cases.

o Lowest overhead.

 Dynamic and guided:

o Higher overhead.

o Overhead depends on the OpenMP implementa on.

Example:

#pragma omp parallel for default(none) schedule(run me) \

private(i,j) shared(n)

for (i=0; i<n; i++)

prin ("Itera on %d executed by thread %d\n",

i, omp_get_thread_num());

for (j=0; j<i; j++)

system("sleep 1");

Work sharing constructs

 Work-sharing constructs distribute computa on among threads.

 They are a core feature of OpenMP.

 Used inside a parallel region.

 They do not create threads themselves.

 If used:

o Inside an ac ve parallel region → work is shared.

o Outside or in an inac ve parallel region → direc ve is ignored.

 Work-sharing direc ves can appear in procedures:

o Used during parallel calls.

 o Ignored during sequen al calls.

Rules for Work-Sharing Constructs

 All threads must encounter the construct, or none must.

 All threads must encounter work-sharing and barrier regions in the same order.

 No barrier at entry.

 Implicit barrier at exit by default.

 Barrier can be removed using the nowait clause.

Types of Work-Sharing Constructs

 Loop (for / do)

 Sec ons

 Single

 Workshare (Fortran only)

Loop Construct

 Distributes loop itera ons across threads.

 Most commonly used work-sharing construct.

 Itera ons are assigned at run me.

Loop Restric ons (C/C++)

 Loop must be countable.

 Must use an integer loop variable.

 Increment or decrement must be fixed.

 Rela onal operator must be:

o <, <=, >, >=

 List-based or pointer-based loops are not allowed.

#pragma omp parallel shared(n) private(i)

{
#pragma omp for
for (i=0; i<n; i++)
prin ("Thread %d executes loop itera on %d\n",
omp_get_thread_num(),i);
}
Loop Variable Behavior

 Loop itera on variable is:

o Private by default.

o Each thread gets its own copy.

 Its value is undefined a er the loop unless lastprivate is used.

Loop Execu on Notes

 Output order is nondeterminis c.

 Threads may execute different numbers of itera ons.

 Extra itera ons are assigned in an implementa on-dependent manner.

 Programmer cannot assume:

o Which thread executes which itera on.

 Itera on mapping can be controlled using the schedule clause.

Sec ons Construct

 Used to execute different code blocks in parallel.

 Each sec on is executed once.

 Each thread executes:

o One sec on at a me.

 If:

o More sec ons than threads → threads execute mul ple sec ons.

o More threads than sec ons → extra threads are idle.

 Assignment of sec ons to threads is implementa on-dependent.

 Sec ons must be independent structured blocks.

#pragma omp parallel

{
#pragma omp sec ons
{
#pragma omp sec on
(void) funcA();
#pragma omp sec on
(void) funcB();
} /*-- End of sec ons block --*/
}
Common Use of Sec ons

 Parallel execu on of func ons or subrou nes.

 Parallelism limited by number of sec ons.

Load Imbalance Issue (Sec ons)

 Occurs when sec ons have unequal work.

 Some threads finish early and wait at barriers.

 Removing the barrier does not fix imbalance.

 May require alterna ve strategies.

Single Construct

 Ensures only one thread executes a code block.

 Does not specify which thread executes it.

 Other threads wait at an implicit barrier.

 Used when:

o Task must be executed exactly once.

o Thread iden ty does not ma er.

#pragma omp parallel shared(a,b) private(i)

{
#pragma omp single
{
a = 10;
prin ("Single construct executed by thread %d\n",
omp_get_thread_num());
}
/* A barrier is automa cally inserted here */
#pragma omp for
for (i=0; i<n; i++)
b[i] = a;
} /*-- End of parallel region --*/
prin ("A er the parallel region:\n");
for (i=0; i<n; i++)
prin ("b[%d] = %d\n",i,b[i]);

Single Construct – Important Notes

 Prevents:

o Mul ple writes to shared variables.

 o Non-atomic write issues.

 Ensures:

o Proper ini aliza on before use.

 Implicit barrier prevents race condi ons.

 Execu on thread is nondeterminis c.

Master Construct (Related)

 Executes code only on the master thread.

 No implicit barrier.

 Different from single.

Workshare Construct (Fortran Only)

 Used for Fortran array syntax parallelism.

 Divides statements into units of work.

 Each array element assignment is a unit of work.

 Supported statements:

o Array assignments

o Scalar assignments

o FORALL constructs

o WHERE constructs

o Atomic, cri cal, parallel constructs

!$OMP PARALLEL SHARED(n,a,b,c)

!$OMP WORKSHARE
b(1:n) = b(1:n) + 1
c(1:n) = c(1:n) + 2
a(1:n) = b(1:n) + c(1:n)
!$OMP END WORKSHARE
!$OMP END PARALLEL

Workshare Rules

 Assignment of work units is unspecified.

 Compiler ensures correct Fortran seman cs.

 Synchroniza on is automa cally handled.

  Only supported clause:

o nowait

Combined Parallel Work-Sharing Constructs

 Shortcut for:

o parallel + one work-sharing construct.

 Used when:

o Parallel region contains only one work-sharing construct.

 Examples:

o parallel for

o parallel sec ons

Advantages of Combined Constructs

 Improves readability

 Same seman cs as separate constructs.

 May improve performance:

o Compiler inserts fewer barriers.

o More op miza on opportuni es.

Important Restric on

 Only clauses valid for both constructs can be used.

 If program behavior depends on where a clause is placed:

o Program is illegal.
 o Behavior is undefined.

Synchroniza on constructs
Purpose of Synchroniza on in OpenMP

 Used to control access to shared data by mul ple threads.

 Prevents data races and ensures correct execu on order.

 Needed when implicit barriers are not enough or are inefficient.

 Works together with work-sharing constructs to parallelize programs.

4.6.1 Barrier Construct

 A barrier makes threads wait un l all threads reach the same point.

 No thread proceeds un l all threads arrive.

Key points

 Many OpenMP constructs have an implicit barrier at the end.

 Use an explicit barrier only when needed.

Syntax

 C/C++: #pragma omp barrier

 Fortran: !$omp barrier

Rules

 All threads must encounter the barrier, or none should.

 All threads must encounter barriers and work-sharing regions in the same order.

 In C/C++, the barrier must be placed where removing it keeps syntax valid.

Uses

 Ensures writes complete before reads.

 Avoids data race condi ons.

4.6.2 Ordered Construct

 Ensures a block inside a parallel loop runs in sequen al order.

Key points

 Only the ordered block runs sequen ally.

 The rest of the loop runs in parallel.

 Threads wait for previous loop itera ons to finish the ordered block.
Syntax

 C/C++:

o #pragma omp ordered

 Fortran:

o !$omp ordered

o !$omp end ordered

Rules

 Must be inside a parallel loop.

 Requires the ordered clause on the loop.

 No clauses allowed on the ordered construct itself.

Uses

 Ordered prin ng.

 Debugging and checking for data races.

4.6.3 Cri cal Construct

 Ensures only one thread at a me executes a block of code.

 Used to protect shared variables.

Key points

 The block is called a cri cal region.

 Op onal name can be given.

 Same name = same cri cal region.

 Names are global and must be unique.

Syntax

 C/C++: #pragma omp cri cal [(name)]

 Fortran:

o !$omp cri cal [(name)]

o !$omp end cri cal [(name)]

Uses

 Avoids data races during updates.

 Used for:

o Upda ng shared sums.

 o Prin ng output safely.

o Compu ng minimum or maximum values.

Note

 Can reduce performance due to serializa on.

 Prefer reduc on clause when applicable.

4.6.4 Atomic Construct

 Ensures atomic update of a single memory loca on.

 Faster than cri cal when applicable.

Key points

 Applies to one assignment statement only.

 Protects only the update, not surrounding code.+

 Requires hardware support for atomic opera ons.

Syntax

 C/C++: #pragma omp atomic

 Fortran: !$omp atomic

Supported opera ons

 C/C++: + - * / & | ^ << >>

 Fortran: + - * / .AND. .OR. .EQV. .NEQV.

 Fortran intrinsics: MAX, MIN, IAND, IOR, IEOR

Limita ons

 Expression must not reuse the le -hand variable.

 Does not prevent parallel execu on of func ons inside the statement.

Use cri cal instead when

 The en re block must be protected.

 Func on calls must not run in parallel.

4.6.5 Locks

 Low-level manual synchroniza on mechanism.

 Similar to semaphores.

 More flexible but more error-prone.

Types of locks

 Simple locks: Can be locked once.

 Nestable locks: Same thread can lock mul ple mes.

Lock rou nes

 init – ini alize lock

 set – acquire lock

 unset – release lock

 test – try to acquire lock without blocking

 destroy – remove lock

General steps

1. Declare lock variable.

2. Ini alize lock.

3. Set or test lock.

4. Perform work.

5. Unset lock.

6. Destroy lock.

Cau on

 Incorrect use can cause deadlock.

 Requires careful programming.

4.6.6 Master Construct

 Code block executed by master thread only (thread 0).

Key points

 Similar to single, but:

o No implicit barrier at entry or exit.

 Execu on is determinis c.

Syntax

 C/C++: #pragma omp master

 Fortran:

o !$omp master

o !$omp end master

Uses

 ]Master-only ini aliza on.

 Tasks that must be done by thread 0.

Important

 If other threads depend on the result:

o Use an explicit barrier.

o Or rely on a later implicit barrier.

Run me library rou nes

 OpenMP provides run me library rou nes in addi on to direc ves.

 These rou nes are called from code (C/C++ or Fortran).

 They allow dynamic control and synchroniza on of threads at run me.

 Run me libraries are useful when:

o Direc ves alone are not sufficient.

o Fine-grained control over execu on is needed.

Categories of Run me Library Rou nes

1. Thread Management Run me Rou nes

 Used to iden fy threads and control execu on behavior.

Key Rou ne

 omp_get_thread_num()

o Returns the thread ID (TID) of the calling thread.

o Thread IDs range from 0 to num_threads − 1.

o The thread with ID 0 is the master thread.

Usage

 Commonly used for:

o Debugging

o Prin ng thread-specific informa on

o Condi onal execu on based on thread ID

2. Run me Support for Synchroniza on

Purpose

 Used when implicit barriers are not sufficient or are inefficient.

 Helps coordinate access to shared data.

3. Lock Run me Library Rou nes

 Provide low-level synchroniza on, similar to semaphores.

 More flexible than cri cal or atomic.

 Must be used carefully to avoid deadlocks.

Types of Locks

 Simple locks

o Cannot be locked again if already locked.

 Nestable locks

o Can be locked mul ple mes by the same thread.

Lock Variable Types

 C/C++

o Simple lock: omp_lock_t

o Nestable lock: omp_nest_lock_t

 Fortran

o Simple lock: integer(kind=omp_lock_kind)

o Nestable lock: integer(kind=omp_nest_lock_kind)

Lock Run me Rou nes

(All operate on lock variables)

 omp_init_lock

o Ini alizes a lock.

 omp_destroy_lock

o Destroys a lock a er use.

 omp_set_lock

o Blocks un l the lock is available, then sets it.

  omp_unset_lock

o Releases the lock.

 omp_test_lock

o Tests lock availability.

o Returns immediately.

o Enables asynchronous execu on.

General Lock Usage Steps

1. Declare lock variable.

2. Ini alize lock using omp_init_lock.

3. Acquire lock using:

o omp_set_lock or

o omp_test_lock

4. Perform protected work.

5. Release lock using omp_unset_lock.

6. Destroy lock using omp_destroy_lock.

Important Notes on Locks

 Lock variables must be accessed only via lock rou nes.

 Improper usage can lead to:

o Deadlocks

o Program hangs

 Locks provide maximum flexibility, but also maximum risk.

4. Run me Support for Atomic Opera ons

 atomic uses hardware-supported atomic instruc ons.

 Run me system ensures:

o Only one thread updates a memory loca on at a me.

 Protects only the assignment, not surrounding code.

 More efficient than cri cal when applicable.

5. Run me Environment Interac on

 Run me behavior can depend on:

o System load

o Hardware support

o OpenMP implementa on

 Some run me decisions are nondeterminis c.

6. Run me Libraries vs Direc ves

 Direc ves

o Easier to use

o Safer

o Less flexible

 Run me libraries

o More control

o More complex

o Programmer responsible for correctness