Dependencies

Page 1: Introduction

  • Course: CMPEN 431 Computer Architecture

  • Semester: Spring 2025

  • Instructors: Jack Sampson & Alexandar Devic

  • Main Focus: Understanding Program Dependencies and Generalizing Program Scheduling

Page 2: Definition of Dependence

  • Dependence Definition: B depends on A in computation when:

    • B requires results computed by A as operands (producer-consumer).

    • B must be computed after A for soundness (side-effects, exception handling).

  • Conservative vs. Definite Dependence:

    • Conservative: Maybe (not always required).

    • Definite: Always required.

  • Dependencies Across Scales:

    • Programs: e.g., cat FOO | less introduces a dependence between cat and less.

    • Functions: g(f(x)) has f depend on x and g depend on f(x).

    • Procedures: Calls to increment(int * i) depend on memory state.

    • Operations: Example of register-carried dependence in assembly instructions.

  • General Graphs of Dependencies:

    • Transitive dependencies can form graphs.

    • Static graph: General directed graph (contains loops).

    • Dynamic graph (correct program): DAG (Directed Acyclic Graph).

Page 3: Importance of Dependencies

  • Semantics & Use:

    • Causality is critical for reasoning about operation sequences.

    • Difficult to define operating on unproduced data without clarity on dependencies.

  • Performance Limitations:

    • Dependencies restrict execution speed.

    • Issue of 'Loose Loops Sink Chips' in pipelining.

    • Producer-consumer stalls and control-dependence may limit efficiency.

  • Independence Understanding:

    • Knowledge of independence can lead to significant speedups.

Page 4: Relevant Granularities (1/2)

  • Instruction:

    • Node in program dependence graph with one or more operators.

    • Considerations:

      • Resource dependencies (liveness).

      • Data dependencies (producer-consumer).

      • Control dependencies (conditional execution).

  • Basic Block:

    • A category for control dependence.

    • Single entry and exit, with contiguous instructions sharing identical control dependencies.

  • Hyper Block:

    • A subgraph with single entry and multiple exits (feed-forward).

    • Rooted DAG of basic blocks.

Page 5: Relevant Granularities (2/2)

  • Loops & Loop-Nests:

    • Common cyclic program subgraphs with high dynamic coverage.

    • Structure: head-body-tail; optimizations benefit from regularity.

  • Functions/Procedures/Methods:

    • Characterized by single entry, narrow interface, but diverse structure.

    • Useful for resource scoping in compilers.

  • Objects:

    • Units of compilation/code generation, co-compiled.

    • Optimization across objects is challenging (source availability issues).

Page 6: Static vs. Dynamic Dependence

  • Static Dependence:

    • Based on the code's structure, regardless of its execution.

  • Dynamic Dependence:

    • Actual run-time behavior of the program, affected by inputs and execution context.

  • Depict how functions and their calls can vary execution paths and dependencies dynamically.

Page 7: Static vs. Dynamic Graphs

  • Static Graph:

    • Represents potential code paths and dependencies without execution context.

  • Dynamic Graph:

    • Reflects actual execution, often with unrolled or varied control paths based on execution outcome.

Page 8: Program Dependences at the ISA Level

  • Dependence Types:

    • RAW (Read After Write): Later operator consumes produced operand.

    • WAR (Write After Read): Later operator reclaims resource.

    • WAW (Write After Write): Later operator redefines the value.

  • Instruction Examples Illustrating Dependences.

Page 9: Code to Structure

  • Example code demonstrates translating a looping construct into its dependence graph.

  • Shows how instructions can be structured into basic blocks in a control flow graph.

Page 10: Control Flow Graph Continuing from Page 9

  • Depicts the same loop with control flow expansion.

Page 11: From Code to Structure (LLVM IR)

  • Describes the LLVM Intermediate Representation (IR) for the same loop with detailed program dependence.

Page 12: Program Dependence with RAW

RAW (Read After Write) Example:

In a program, consider the following sequence of instructions:

In this example:

  • On line 1, the variable x is written with the value 5.

  • On line 2, the variable y reads the value of x to perform the addition.

  • Therefore, instruction 2 has a RAW dependency on instruction 1 because it reads from x, which has been written by the previous instruction.

  • Similarly, on line 3, y is read to calculate z, which introduces another RAW dependency.

Page 13: Program Dependence with WAW

1. x = 5;
2. y = x + 2;
3. z = y * 2;

Example demonstrating WAW (Write After Write) dependency: In a program, consider the following sequence of instructions:

  1. x = 10;

  2. x = 20;

  3. x = 30;

In this example:

  • On line 1, the variable x is written with the value 10.

  • On line 2, the variable x is written again with the value 20.

  • On line 3, x is written once more with the value 30.

Therefore, there are WAW dependencies here because each subsequent instruction overwrites the value of x written by the previous instruction.

Page 14: Program Dependence with WAR

WAR (Write After Read) Example: In a program, consider the following sequence of instructions:

  1. y = x + 2;

  2. x = 5;

  3. z = y * 2; In this example: On line 1, the variable y reads the value of x to perform the addition. On line 2, the variable x is then written with the value 5. Therefore, instruction 2 has a WAR dependency on instruction 1 because instruction 1 uses the value of x before instruction 2 updates it.

Page 15: From Code to Structure (SSA)

  • Static Single Assignment (SSA) form further elucidates program dependence with specific control flow.

Page 16: Control and Dependence Example Continues with SSA

  • Highlights SSA benefits in reducing redundancy in variable assignments and improving optimization potential.

Page 17: Further Example with SSA

  • In-depth execution flow of instructions demonstrating SSA and control flow improvements.

Page 18: Program Dependence Graph

  • Presents a comprehensive program dependence graph illustrating various relationships.

Page 19: Relevance to Compilers and Optimizers

  • Emphasizes understanding dependencies helps optimize code efficiencies and handling during code generation (e.g., unrolling, branch prediction).

Page 20: Types of Code Parallelism

  • Instruction-Level Parallelism (ILP):

    • Average number of instructions potentially executed simultaneously.

  • Data-Level Parallelism (DLP):

    • Example emphasizes differences between data and instruction parallelism influences.

Page 21: Code Scheduling Example

  • Discusses naive scheduling of loop code highlighting potential pitfalls in producer/consumer dependencies.

Page 22: Rescheduling Example

  • Analyzed updated scheduling to minimize stalls and improve performance design.

Page 23: Advanced Scheduling Example

  • Shows a more sophisticated loop reorganization, reducing stalls effectively.

Page 24: Loop Unrolling Definition

  • Loop Unrolling Explained Simply: Loop unrolling is a way to make loops run faster by reducing the number of times you have to repeat a loop.

    Instead of writing a loop that does the same thing over and over, you can write out what the loop does directly several times in one go. This way, the computer doesn’t have to check if it should loop again so many times, which saves time.

Page 25: Detailed Unrolled Code Example

  • Offers insights into how loop unrolling translates into practical code improvements with effective performance metrics.

Page 26: Continued Unrolling Example

  • Additional optimizations further illustrated with calculations on cycle performance and instruction efficiency.

Page 27: Extended Unrolled Code Example

  • Presents a series of load and store operations to illustrate parallelism and throughput gains.

Page 28: Resulting Dependency and Scheduling

  • Continues with optimally scheduled dependencies demonstrating performance enhancement.

Page 29: Exam Question Framework

  • Introduces an exam question focusing on dependencies with labeling instructions with data dependency types.

Page 30: Dependency Labeling Continued

  • Directs attention on how to categorize instructions based on dependencies for clearer analysis.

Page 31: Further Dependency Question Framework

  • Elaborates on instruction categorization, reinforcing the analysis of dependencies in programming contexts.

Page 32: Static Control and Data Dependencies Exam Question

  • Challenges students with a question regarding control flow graph and basic blocks, testing comprehension of the material.

= x + 2; 3. z = y * 2;