CSC3060 Introduction to Computer Systems

• Textbook Computer Systems A Programmer’s Perspective, 3e, INTERNATIONAL EDITION written by Randal Bryant and David R. O'Hallaron.

• Reference book Computer Organization and Design: The Hardware/Software Interface (RISC-V Edition) written by David A. Patterson and John L. Hennessy.

Chapter 1 A Tour of Computer System

Compilation System

Take C language as an example linux > gcc hello.c -o hello.

• Pre-processor (cpp) $\text{.c}\to \text{.i}$ Handles include/define, strips off comments and conditional compilation #ifdef
• Compiler (cc1) $\text{.i}\to \text{.s}$ Scan/parse/semantic check/code gen/opt
• Assembler (as) $\text{.s}\to \text{.o}$ From assembly to machine code
• Linker (ld) $\text{.o}\to \text{Executable}$ Relocation & reference resolution

Hardware Organization of a System

DMA (Direct Memory Access) is usually used for high-spped and bulk data transfers, controlled by system programmers.

• System Bus

  Transfer data in fixed-size blocks called words (4/8 bytes on a 32/64 bit system)

Memory Hierarchy

The localities of cache: Temporal Locality & Spatial Locality.

Abstractions in Computer Systems (Virtualization)

Virtualization is often related to multiplicity, fake versions, and sharing.

• Process & Thread

  Multiple processes can run concurrently on the same system, and each process appears to have exclusive use of the hardware.

  Context switching with OS Kernel.

  A process can actually consist of multiple execution units, called threads. Threads shares the same code and global data.

• Virtual Memory

  Program Code & Data, Shared Libraries, Heap, Stack, Kernel Virtual Memory from bottom to top.

  • Virtual address space canve greater than the physical memory.

  • Memory serves as a cache for virtaul memory.

  • Support multiprogramming.

  • Allow multiple processes to share data.

• File

Import Themes

Amdahl's Law (Quantifying the performance improvement ceiling)

$T_{new}=(1-\alpha )T_{old}+\frac{\alpha T_{old}}{k}=T_{old}(1-\alpha +\frac{\alpha }{k})$

$S=\frac{T_{old}}{T_{new}}=\frac{1}{1-\alpha +\frac{\alpha }{k}}$

Concurrency and Parallelism

• Concurrency It refers to the general concept of a system having multiple, simultaneous activities, which do not necessarily execute at the same time, but may interleave in time to create the logical impression of simultaneity.

• Parallelism It refers to the use of concureency to make a system run faster.

ILP and DLP

• Instruction-Level e.g. Parallelism pipelining, superscalar, out-of-order execution.

• Data-Level Parallelism e.g. Single Insruction Multiple Data (SIMD), Vector instructions.

Computer Architecture

Computer Architecture (e.g. Intel x86, IBM 360, ARM, RISC-V) is the interface between hardware and software, it includes ISA and Microarchitectures (e.g. Different implementations of the same ISA: Single cycle, Multi-cycle, Pipelined, Superscalar, Out-Of-Order, Speculative Execution, Cache Hierarchies, and Various Predictions).

Chapter 2 Representing and Manipulating Information

Information Storage

• Words

  $w$ word size $⟺$ $[0,2^w)$ virtual address space

• Addressing and Byte Ordering

  Big endian (e.g. IBM Mainframes) & Little endian (e.g. Intel x86, ARM, RISC-V).

  Big-endian means most significant byte first, and Little-endian means least significant byte first.

Integer Representaions

Sizes of Data Type in C/C++

Unsigned Encodings

Suppose a vector $\mathrm{x}=[x_{w-1},x_{w-2},\cdots ,x_0]$, then $B2{\mathrm{U}}_{\mathrm{w}}(x)=\sum _{i=0}^{w-1}{x}_i\cdot 2^i$

Two's Complement Encodings

Inverse form (1's Complement) For a negative number, keep the signed the same and invert the rest.
two zero exits & end-round carry out issues (hte end carry-out bit needs to add back to the LSB)

2's Complement For a negative number, keep the sign the same, invert the rest and add 1.

Suppose a vector $\mathrm{x}=[x_{w-1},x_{w-2},\cdots ,x_0]$, then $B2{\mathrm{T}}_{\mathrm{w}}(x)=-x_{w-1}\cdot 2^{w-1}+\sum _{i=0}^{w-2}{x}_i\cdot 2^i$

Conversions between Signed and Unsigned

$$T2{\mathrm{U}}_{\mathrm{w}}(x)=\{\begin{array}{l}x+2^w,x<0\\ x,x\ge 0\end{array}U2{\mathrm{T}}_{\mathrm{w}}(u)=\{\begin{array}{l}u,x\le Tma{x}_w\\ u-w^w,x>Tma{x}_w\end{array}$$

For a $n$-bit 2's complemetn signed binary numeral system:

• Minimum $-2^{n-1}$, corresponding to binary $\text{100}\cdots \text{0}$ (A special case that does not satisfy the invert bits and add 1 rule used for other negative numbers).
• Maximum $2^{n-1}-1$, corresponding to binary $\text{011}\cdots \text{1}$.

Sign Extension

Small to Big

• Zero extension of unsigned numbers

• Sign extension of two's complement numbers

  $B2{\mathrm{T}}_{\mathrm{w}}([x_{w-1},x_{w-2},\cdots ,w_0])=B2{\mathrm{T}}_{\mathrm{w}+\mathrm{k}}([x_{w-1},x_{w-1},\cdots ,x_{w-1},x_{w-1},x_{w-2},\cdots ,x_0])$

  Since $B2{\mathrm{T}}_{\mathrm{w}+1}-B2{\mathrm{T}}_{\mathrm{w}}=(-x_{w-1}\cdot 2^w+x_{w-1}\cdot 2^{w-1})-x_{w-1}\cdot 2^{w-1}=0$, by induction, we can proof it.

Big to Small

• $B2{\mathrm{U}}_{\mathrm{k}}(x)=B2{\mathrm{U}}_{\mathrm{w}}(x)\mathrm{mod}{2}^k$

• $B2{\mathrm{T}}_{\mathrm{k}}(x)=U2{\mathrm{T}}_{\mathrm{w}}(B2{\mathrm{U}}_{\mathrm{w}}(x)\mathrm{mod}{2}^k)$

Integer Arithmetic

Addition

$$x+y_w^u=\{\begin{array}{l}x+y,x+y<2^w\\ x+y-2^w,2^w\le x+y<2^{w+1}\end{array}$$

$$x+y_w^t=\{\begin{array}{l}x+y-2^w,2^{w-1}\le x+y\\ x+y,-2^{w-1}\le x+y<2^{w-1}\\ x+y+2^w,x+y<-2^{w-1}\end{array}$$

Additive Inverse

$x+x^{\prime }=0\text{or}{2}^w$

$$-x_w^u=\{\begin{array}{l}x,x=0\\ 2^w-x,x>0\end{array}-x_w^t=\{\begin{array}{l}x,x>Tmi{n}_w\\ Tmi{n}_w,x=Tmi{n}_w\end{array}$$

• For two numbers A, B, the overflow occurs when (NOT (sign_A XOR sign_B)) AND (sign_A XOR new_sign) == 1. (Two operands have the same sign but the result has a different sign.)

• One Bit Full Adder

  $S_i=A_i+B_i+\text{carry\_in}\text{carry\_out}=(A_i\&B_i)|(\text{carry\_in}\&(A_i\oplus B_i))$

• Carry Lookahead Adder

  $$\{\begin{array}{l}{g}_i=(A_i\cdot B_i)\\ p_i=(A_i\oplus B_i)\\ C_1=g_0+(p_0\cdot C_0)\\ C_2=g_1+(p_1\cdot g_0)+(p_1\cdot p_0\cdot C_0)\\ C_3=g_2+(p_2\cdot g_1)+(p_2\cdot p_1\cdot g_0)+(p_2\cdot p_1\cdot p_0\cdot C_0)\\ ⋮\end{array}$$

  

Multipilication

$$\begin{gathered} x\times y_w^u=(x\cdot y)\mathrm{mod}{2}^k \\ x\times y_w^t=U2{\mathrm{T}}_{\mathrm{w}}((x\cdot y)\mathrm{mod}{2}^k) \end{gathered}$$

Division (by a power of 2)

Unsigned numbers use logical shift, while two's complement numbers use arithmetic shift to achieve sign-preserving extension.

Right shift performs integer division by powers of two :

• $x\le 0x>>k=\lfloor \frac{x}{2^k}\rfloor$

• $x<0(x+(1<<k)-1)>>k=\lceil \frac{x}{2^k}\rceil$

Floating Point

Floating-Point Representation

$V=(-1{)}^s\times M\times 2^E$

s (sign) : The number is positive ($s=0$) or negative ($s=1$).

M (fraction) : A binary fraction.

E (exponent) : $2^E$ weight.

$\text{bias (float)}=127\text{bias(double)}=1023$ ($\text{bias}=2^{k-1}-1$)

When interpreted as signed integers, the bit representation of IEEE 754 floating-point numbers (excluding NaN) preserves the same sorting order.

Comparison (postive number)

Rounding

Floating Point Operations

• Lack of Associativity & Lack of Distributivity

  Example Questions

  Let $x,f,d$ are of type int, float, double (Their values are arbitrary, except that neither $f$ nor $d$ equals $+\infty$, $-\infty$, or $\text{NaN}$.). Then:

  • x == (int)(double) x True
  • x == (int)(float) x False $2^{24}-1\to (1+0.\underset{23\text{ones}}{\underbrace{11\dots 1}})\times 2^{23}$ (e.g. $16777217$)
  • d == (double)(float) d False (e.g. $1.234$)
  • f == (float)(double) f True
  • d*d >= 0.0 True

• Float Point Addition

  • Align decimal points (small to big)
  • Add significands
  • Normalize
  • Round and renormalize if needed
  Example

  $$\begin{array}{rl}& 9.999\times 10^1+1.610\times 10^{–1}\\ & =9.999\times 10^1+0.01610\times 10^1\\ & =10.015\times 10^1=1.0015\times 10^2\\ & =1.002\times 10^2\end{array}$$

Precision (IEEE 754-2008 Standard Formats)

FMA/FMAC

Fused Multiply and Add (FMA) or Fused Multiply and Accumulate (FMAC) combines multiply and add in one instruction ($A\times B+C$).

• Multiplication and addition are parallel.
• Normalization and rounding are combined at the end.

Use -mfma -ffp-contract=fast to enable FMA.

Chapter 3 Machine-Level Representation of Programs

Machine-Level Representation of Programs

RISC [optimized for processor speed]

Principles

1. Simplicity favors regularity
2. Smaller is faster
3. Make common cases fast
4. Good design demands good compromises

[RSA should be scalable, flexible, and extensible.]

Variants of RV

• RV32, RV64, RV128 Different data widths (addressing capability)

Instruction Types in RV32I

• Three operand instruction format.

• X0 is always zero.

• 32 means Address cability/Integer register length.

• Immediate

  • $\text{R}$ type No immediate.
  • $\text{B,I}$ type 12 bits immediate. Shift instructions are I-type but repurpose the immediate field as a 5-bit shift amount for RV32I (6-bit for RV64I). inst[30] distinguishes arithmetic from logical right shift, while inst[31:26] are fixed to zero except inst[30] (Range: $\pm 4\text{KB}$). The immediate in the branch instruction is an offset relative to PC.
  • $\text{S}$ type The 12‑bit immediate is split into high 7 bits (immediate) and low 5 bits (immed) (maintain regularity). The immediate in the store instruction is an offset relative to rs1.
  • $\text{J}$ type 20 bits immediate.

• Jump

  • jal

    • $rd\leftarrow PC+4$, $PC\leftarrow PC+\text{sign-extend}(\{\text{inst}[31],\text{inst}[19:12],\text{inst}[20],\text{inst}[30:21]\})\times 2$ (Jumps are 2-byte aligned, so last bit is implicit zero).
    • Range: $\pm 1\text{MB}$.
    • Beyond 1MB: Use AUIPC + JALR.

  • jalr

    • $rd\leftarrow PC+4$, $PC\leftarrow (rs1+\text{sign-extend}(\text{inst}[31:20]))\&\sim 1$ ($\sim 1$ clears LSB to ensure 2‑byte alignment).

• Load and Store

  lw rd, offset (rs1) means load data from memory and write into rd.

  sw rs2, offset (rs1) means store data from register rs2 into memory.

• LUI loads a 20‑bit immediate into the upper bits of a register; AUIPC adds a 20‑bit immediate to the current PC for position‑independent addressing.

  How to load a 32b const into a register?

  1. Use a LW instruction (cost more)
  2. lui and addi (When the lower 12 bits of a 32‑bit constant are $\ge \text{0x800}$, addi sign‑extends them, causing an incorrect result. The assembler automatically adjusts the upper 20 bits when using the li pseudo‑instruction.) (Range: $4\text{GB}$)

Instruction Encoding List

Application Binary Interface (ABI)

It is based on three key components : the computer ISA, the OS, and the calling convention. ABI incompatibility will occur due to differences between operating systems.

Data Alignment

• No cache line crossing; no double TLB (Translation Lookaside Buffer) misses; no double page faults come from a single memory instruction execution.

• Better cache line utilization.

RISC-I to RISC-V do not explicitly enforce data alignments. But their compilers often enforce data alignments.

Crossing a boundary makes the memory reference difficult to handle. The hardware needs to go through two exceptions instead of one.

Padding Rule

• Internal Padding Every member must start at an address that is a multiple of its own alignment requirement.
• Trailing Padding The total size of the struct must be a multiple of the largest alignment requirement among its members.

struct S1 {
    int white;
    long long count;
    char c;
    int red;
    int blue;
} A[];

Stack / Frame Alignments

• Defined by ABI (e.g., RISC‑V psABI: 16‑byte)
• CRT aligns sp before main ()

Compiler Reordering

• Independent Variables (Rearrangement Allowed)

• Struct Fields (Rearrangement Forbidden)

  • Binary compatibility
  • Pointer arithmetic
  • Interoperability

PC-relative Addressing

Branch instructions use PC‑relative addressing with a 12‑bit signed offset (in 2‑byte units). Since branch targets are always multiples of 2, encoding in 2‑byte units doubles the reachable range without losing information.

$$\text{Target Address}=\text{PC}+\text{sign\_extend}(12\text{-bit immediate})\times 2$$

CSR

Exception Handling

1. Save context Save current PC value to mepc register
2. Update status Update mstatus, disable further interrupts (clear MIE bit) to prevent nesting
3. Set cause Write exception/interrupt reason to mcause
4. Jump to handler Jump to exception handler entry point based on mtvec configuration

Frame Pointer (fp)/Stack Pointer (sp)

• sp points to the top of stack.
• fp points to a fixed location within the current stack frame, typically the address where the old fp is stored.
• When the function returns, the saved old fp is restored to the fp register, making fp point back to the caller's stack frame.

Calling Convention

• Caller-Saved Caller decides whether to save based on whether the value will be used after the call.
• Callee-Saved Callee must always save these registers before using them and restore them before returning (absolutely safe).
• Array variables are typically allocated in memory (stack or static data section), not in registers.

CISC [optimized for compact code size]

Chapter 4 Processor Architecture & Logic Design

Logic Designs

Major components

• Combinational element
• State (Sequential) elements $\text{Write}=0$, cannot write to register (B-type and S-type).
• Clock signals

The propagation delay of a combinational circuit is determined by the delay of the critical path, which is the longest path of logic gates from any input to any output.

Processor

Core

Data Path (Data Flow)

e.g. ALU, Register, Memory interface, Buses.

Control (Instruction Flow)

e.g. PC, Instruction fetch, and Control signal generation.

RV32I Data Path and Control

• Memory reference instrutions lw, sw
• Arithmetic/logical instrutions add, sub, and, or
• Control flow instruction beq, jal

Instruction Execution Cycle

Cycle

• Three Stages

  • Fetch Use the PC to supply the instruction address and fetch the instruction from memory.
  • Decode Decode the instruction (and read registers).
  • Execute
    • Use ALU to calculate (Arithmetic result & Memory address for load/store & branch target address)
    • Access data memory for load/store
    • Update PC (target address or PC + 4 (next word) or PC + 2 (if using compressed instructions RV32IC))

• Multi-cycle Instructions are broken down into multiple steps, each taking one clock cycle.

Time

CPU time is determined by the following:

$$\text{CPU Time}=\text{Instructions count}\times \text{Cycles per instruction (CPI)}\times \text{Clock cycle time}$$

Program execution time is determined by the following:

$$\frac{\text{time}}{\text{program}}=\frac{\text{instructions}}{\text{program}}\times \frac{\text{cycles}}{\text{instructions}}\times \frac{\text{time}}{\text{cycle}}$$

• CISC machines Lower instruction count, higher CPI, longer cycle time
• RISC machines Higher instruction count, lower CPI, shorter cycle time

Abstract View of RV32I Subset

Processor Designs

1. Analyze the requirements

2. Data Path Requirements selections

   • Combinational Components Adder & MUX & ALU (An adder only does addition (e.g., PC+4). An ALU includes an adder but also performs many other arithmetic/logic operations.)

   • Sequential Components

     Register $N$-bit storage with Write Enable control. Updates only at clock tick if $\text{Write}=1$.

     Register File consists of 32 registers with two read ports (rs1/rs2) and one write port (rd).

     Memory. Read ($\text{WE}=0$): Address → Data Out. Write ($\text{WE}=1$): Next clock tick, Data In → Address.

   • Assemble

     • Instruction Fetch Unit Fetch the instruction and Update the program counter.

     • Branch Operations Using ALU subtraction for branches risks overflow corrupting the sign, so RISC-V processors internally use flags (overflow and carry) or dedicated comparators for correct branch decisions without hardware traps.

     • Add and Subtract R[rd] <- R[rs1] op R[rs2]

     • Load/Store Operations A single ALU and register file need two multiplexers: one for ALU's second input (e.g. add rd, rs1, rs2 and addi rd, rs1, imm), another for register file's write data source (e.g. add x3, x1, x2 from ALU and lw x3, 8(x1) from memory).

   • Control Points and Signals

     Control Signal	Description	Expression
     PCsrc	Select the next PC value PC + 4 [$0$] Branch / jump target address [$1$]	(Branch or jal/jalr) ? 1 : 0
     RegWr	Write enable for register file	(Branch or Store) ? 0 : 1
     MemRd	Enable signal for reading data memory	Load ? 1 : 0
     MemWr	Enable signal for writing data memory	Store ? 1 : 0
     ALUsrc	Select the second ALU input register [$0$] immediate value [$1$]	R-type ? 0 : 1
     ALUctr	Determines the ALU operation	/
     WBsel	Selects the data written to the register file memory data [$0$] ALU result [$1$] PC + 4 [$2$]	Load: 0; R-type : 1; jal/jalr : 2

On each clock cycle, the single‑cycle processor executes one instruction. State elements update at the rising edge using combinational logic outputs computed during the cycle.

Control

• Asel rs1 or pc (When use jal, the target is PC + offset.)
• Bsel rs2 or immed.

Pipelining

Five Stages

1. $\text{IF}$ Instrcution fetch from (instruction) memory
2. $\text{ID}$ Instrcution decode & register read
3. $\text{EX}$ Execute operation or calculate address
4. $\text{MEM}$ Access (data) memory operand
5. $\text{WB}$ Write the result back to register

• Throughput increases as more instructions complete per unit time, but single instruction latency (The time it takes for each instruction to be executed.) does not decrease and may even increase.
• Pipeline rate is limited by the slowest stage.
• Potential/ideal speedup = Number of pipeline stages (number of pipeline steps).
• Need to reduce possible fill and drain (e.g., I-cache misses and branch misprediction)

Pipeline-oriented ISA Design

• All instructions are fixed length.
• Few and regular instruction formats.
• Only load/store instructions accessing memory.
• Instructions are simple.

Some principles of designing a pipelined datapath:

• Multi-stage partitioning
• Overlapped execution
• Increased throughput
• Improved resource utilization

Single Cycle & Multi Cycle & Pipeline

• Latency The total time required to complete one single instruction from start to finish. (Single-cycle data path actually has shorter instruction latency because of the setup time and propagation delay in pipeline.)
• Throughput The total number of instructions completed per unit of time.
• For superscalar implementation, CPI $<1$.
• Single cycle as lower throughput but shorter instruction latency.
• No arithmetic exceptions allow out‑of‑order retirement, avoiding stalls for long‑latency instructions.

Pipline Registers

Without pipeline registers, stages would overwrite each other’s data, causing instruction mix‑ups and loss of control information.

• Control signals are derived from instruction bits, that is, after the ID stage.

• Control information for later stages are also stored in the pipeline registers.

• Architecture States (visible to the programmer and compiler)

  • Registers (general purpose, fp, vector, flags)
  • PC
  • Memory

  It was saved during a context switch:

  • user-level switch (e.g. procedure call) saved on the runtime program stack (caller and callee convention).
  • system-level switch (e.g. process switch) saved on the Process Control Block (PCB) or the kernel stack.

• Micro-architecture states (invisible to the programmer)

  • $\text{Piplined registers}$ Pipelined registers hold transient data between stages for a few cycles.
  • Branch predictors
  • Caches
  • Buffers and Quenes
  • Counters

Hazards

Structure Hazards

A conflict arising due to hardware resourece limitations within the pipeline.

• Pipeline stalls

• Multiple resources

• Instruction Reordering

  Static scheduling (by compiler) reorders instructions at compile time to avoid hazards, while dynamic scheduling (by hardware) reorders them at runtime based on actual data and resource availability.

• ISA design

Split Instruction/Data caches can avoid structural hazards in the pipeline and increase the cache access bandwidth.

Data Hazards

A conflict arising because the current instruction depends on the result of a previous instruction that has not yet been computed or written back.

Solutions

Flow dependence (RAW) is a true data dependence, while anti-dependence (WAR) and output dependence (WAW) are name dependences that can be eliminated by register renaming.

• Stall pipeline (Interlocking)

• Data Forwarding (Bypassing)

  Add forwarding control logic to make extra connections in the datapath.

  Hazard detection compares $\text{EX/MEM}$ and $\text{MEM/WB}$ destination registers with current instruction’s source registers. (EXE-EXE EX/MEM.RegRd = ID/EX.RegRs1/2 and MEM-EXE MEM/WB.RegRd = ID/EX.RegRs1/2)

  Forwarding is skipped when RegWr == 0 or when the destination register is x0.

• Compiler Code Transformations

  Scheduling (reordering) scope is often limited by branches, indirect branches, and call/ret. Memory aliasing (e.g., $p$ and $q$ may point to same address) and unknown latencies (e.g. cache hit/miss unpredictable) further restrict reordering. Compiler must conservatively preserve dependencies.

Control Hazards

Control hazards are due to branch instructions (conditional jumps) and JAL/JALR instructions (unconditional jumps).

Condition and Target Address are Ready at the $\text{EXE}$ Stage.

Static Branch Prediction (Compile Time)

• Predict a backward branch as taken (loop back branches) and predict a forward branch as fall-through (the compiler always puts the then part in the fall-through path).
• Conditional branch's (e.g. blt) behavior is entirely program‑dependent and cannot be accurately predicted using simple static rules. Static branch prediction does not read registers at runtime. It only considers whether the branch target is forward or backward.
• Unconditional branches (e.g. jal) always jump, static prediction should always predict taken.
• The ISA may reserve a bit in branch instructions as a prediction bit.
• When branch prediction is wrong, pipeline flushing is performed.

Dynamic Branch Prediction (Run Time)

• Branch History Table (BHT) (Branch prediction should occur at the instruction fetch (IF) stage.)

  A branch history table stores past outcomes of branches, indexed by address, to predict future behavior and flush on misprediction.

  Tag identifies which address occupies a cache slot. BHT omits tags because prediction bits (1–2) are tiny, tags huge (30–46 bits).

  • 1-bit Predictor Flips on every misprediction, fails on nested loops.
  • 2-bit Predictor Four-state FSM, changes only after two consecutive mispredictions, handles loops better.

• Correlated Predictor

  Global history register selects a 2-bit counter entry in the pattern table. Current PC selects which table to use, separating histories for different branches.

• The Location Prediction

  Branch Type	Prediction Mechanism	Example
  Direct branch	Branch Target Buffer (BTB), fixed target	beq, jal
  Indirect branch	Hard to predict	jalr x0, 4(x1) (Return branch, Switch statements and Function pointers)
  Function return	Return Address Stack (RAS)	ret

Chapter 5 Optimizing Program Performance

Compiler Optimization

Compiler Optimization Levels

General Goals

Minimize the Number of Instructions

• Common Subexpression Elimination (CSE) Calculate the same expression once and reuse the result.
• Dead Code Elimination (DCE) Don't calculate values that are never used.
• Strength Reduction (SR) Avoid slow instructions (multiplication/division).

Minimize the Execution Cycles

• Register Allocation (RA) Keep frequently used variables in registers.
• Code Scheduling Reorder instructions to avoid stalls.
• Locality Improvement
• Preload & Redundant Load Elimination Load a value once and reuse it, instead of reloading from memory.

Avoid Branching

• Avoid Branching Conditional move in x86 (cmov, e.g. a = (b > c) ? b : c), conditional execution in ARM (e.g. addgt r0, r1, r2).
• Loop Unrolling Reduce the number of branch instructions. Loop unrolling improves performance by reducing the number of branch evaluations and branch mispredictions, also creates opportunities for CSE, code motion, and scheduling.
• Procedure Inlining Reduce the overhead of the call. However, inlining can cause register or I‑cache spilling when code grows too large. For recursive functions, inlining may lead to infinite expansion unless the compiler enforces a depth limit.
• Unswitching Move a condition outside the loop to avoid branching inside the loop. (e.g. if (cond) { for (...) { ... } } else { for (...) { ... } })

Limitations

1. Compilers cannot change the algorithm.

2. Compilers must obey the rules and semantics of the programming language.

   • Memory Aliasing Two pointers may point to the same memory location. Use a local variable for the intermediate value to avoid redundant loads or use the restrict qualifier to promise no aliasing.
   • FP Associativity Floating-point addition is not associative.
   • Function Side Effects A function may modify global state or have observable effects beyond its return value.
   • Volatile Variables A variable declared as volatile can be changed by external factors.
   • Memory Consistency In multi-threaded programs, compilers must respect memory ordering constraints.

3. Lack of runtime and domain knowledge.

4. Many specific optimization problems are NP-hard.

5. Boundary crossing issues (separate compilation).

Several Optimization Options

Chapter 6 The Memory Hierarchy

Storage Technologies

Access time is the same for all locations.

All unconventional DRAM chips offer much higher bandwidth, but the latency remains the same (The first data still takes the same time to arrive).

Static Random Access Memory (SRAM)

Dynamic Random Access Memory (DRAM)

• Reading DRAM Supercell Select row $i$ via RAS, load into buffer. Select column $j$ via CAS, output data, then rewrite row to refresh.
• Memory Modules A 64-bit word is stored across eight $8M\times 8$ DRAM chips in parallel, with each chip providing one byte (8 bits) at the same row and column address.

Memory Wall

The gap between the speed of processors and the main memory. The bottleneck has shifted from how fast memory can respond (latency) to how much data it can deliver per second (bandwidth).

Latency

• Reduction local memory, NUMA, PIM (Reduce the waiting time for each visit.)
• Hiding multi-threading/Hyper-threading, WARP interleaving, chip-multithreading (Keep computation units busy.)

Bandwidth

• Memory bandwidth multi-banks and interleaved memory, SDRAM, HBM
• Communication bandwith wider bus, interconnection network

Locality

Principle

Many Programs tend to use data and instructions with addresses near or equal to those they have used recently.

emporal locality

Recently referenced items are likely to be referenced again in the near future.

Spatial locality

Items with nearby addresses tend to be referenced close together in time.

while (A != NULL) A = A->next;

Memory Hierarchy

This gives you Large, Cheap memory, but Fast access.

Caches provide automatic (transparent) data movement, while local memory requires explicit programmer-controlled data management.

Cache Management

General Cache Memory Organization

Direct Mapped Caches

• Valid Bit

  A cache line is invalid (valid bit equals to $0$) when:

  • When a cache line of data has not come back from memory yet
  • Cache line is currently being replaced
  • Cache is flushed

• Three Steps

  • Set Selection Use the set index as an unsigned binary number to locate the cache set.
  • Line Matching Compare the tag to determine if the desired block is present in the set.
  • Word Extraction Use the block offset as a binary number to select the appropriate word within the cache line.

Set Associative Caches

$N$-way set-associative has $N$ lines per set while direct-mapped is one way and fully associative is one set.

Given a cache with total size $C$ measured in kilobytes, associativity $E$, and block size $B$ measured in bytes. The number of sets $S$ is calculated as $S=\frac{1024C}{BE}$.

Performance Impact of Cache Parameters

• When the block size is too small, the cache cannot fetch enough contiguous data in a single miss (lower spatial locality -- most accesses to nearby addresses still result in cache misses).
• When the block size is too large, the fixed-size cache holds fewer blocks, leading to more conflicts, frequent replacements and higher miss penalty (lower temporal locality -- the recently used data is quickly evicted before it can be reused).
• Number of cache lines is determined by the cache size and the line size.

Cache Hit and Miss

Cache Read

• Read Hit

• Read Miss When a read miss occurs, the CPU stalls the pipeline, fetches the missing block from the next memory level, and then resumes execution.

Cache Write

• Write Hit

  • Write Through

    It simultaneously updated to cache and memory. It ensures data isn't lost if the cache is disrupted, but increases memory traffic and write latency.

    Solution: write buffer. A write buffer hides write latency, but if store frequency exceeds the DRAM write cycle, the buffer saturates and stalls the CPU (Write buffer allows write-coalescing/combining to reduce traffic to memory.).

  • Write Back

    The CPU writes data only to the cache initially, and main memory is not updated until the cache line is eventually replaced (need Dirty Bit). This reduces memory traffic and write latency, but creates cache-memory inconsistency, requiring cache coherence protocols (e.g., MESI) in multi-core systems. Data loss risk on cache failure is mitigated by Error Correcting Code (ECC) protection.

• Write Miss

  • Write Allocate First read the data from main memory and loaded into the cache, and then the write operation is performed on the cached copy.
  • No Write Allocate It writes the data directly to main memory without loading the missing block into the cache (Better for streaming writes, e.g. writing database logs).

Instruction Cache Miss Handling

On an instruction cache miss, the CPU sends the PC to memory, waits for the read to complete, writes the fetched data into cache with its tag and valid bit set, then restarts the instruction fetch. (Instruction cache prefetching is a commonly used hardware optimization to reduce instruction cache misses.)

Types of Cache Misses

• Compulsory (or Cold) Miss The first access to a block that has never been loaded into the cache before. (Hardware prefetching & larger cache line size to reduce compulsory misses.)
• Conflict (or Collision) Miss Multiple references are mapping to the same set, and the set is not large enough to hold them.
• Capacity Miss Cache is not large enough to hold needed blocks.
• Coherence Miss Caused by invalidation from other processors in a multiprocessor system to maintain cache coherence.

Ways to Reduce Cache Miss Penalty

Non-Blocking Cache and Blocking Cache

Blocking Cache

A cache miss stalls the CPU pipeline immediately (stall on miss).

Non-Blocking Cache (Lockup-Free Cache)

The CPU continues executing other instructions on a miss and stalls only when the data is needed, using Miss Status Holding Register (MSHRs) to track outstanding misses (stall on use). Non-blocking caches support MLP (Memory Level Parallelism).

• Hit under Miss During one miss, the cache can still handle subsequent hits.
• Miss under Miss (better) During one miss, the cache can also handle another miss, allowing multiple outstanding misses.

Cache Block Replacement

Direct Mapped

Each set has only one line, so the new block always replaces the existing block in that set.

Set ssociative or Fully Associative

• Random

• Least Recently Used (LRU) [stack algorithm]

  Hardware keeps track of the access history and replaces the block that has not been used for the longest time.

  Each block has a counter. On a hit, reset its counter to 0 and increment all other counters in the set. On a miss, replace the block with the highest counter value.

• First In First Out (FIFO) The block that has been in the cache the longest is replaced, regardless of access history.

• Belady’s Algorithm [upper bound]

  Replace the block that will not be used for the longest time in the future. It is optimal but requires perfect knowledge of future accesses, making it impractical for real hardware.

Victim Cache

A small fully associative cache placed between the main cache and memory to hold recently evicted blocks, reducing conflict misses by providing a second chance for recently replaced data. Since such conflicts occur in only a few sets, just 4–8 entries suffice for fast access, combining the speed of direct-mapped L1 with the benefit of full associativity.

Snoopy Cache Coherence Schemes

Snoopy cache maintains coherence in bus-connected multi-processors by broadcasting all coherence operations over a shared bus. Every cache controller snoops the bus and reacts based on its local cache state. Each controller is a bidirectional state machine that processes CPU requests and bus snoop events, updating states according to a transition diagram.

Multiple controllers form a distributed algorithm operating at cache block granularity. The MESI protocol, with its four states (Modified, Exclusive, Shared, Invalid), tracks each block to enable coherence while minimizing bus traffic and memory accesses.

Exclusive/Inclusive Caches

Inclusive L2 caches simplify coherence invalidation in multiprocessor systems by checking at the L2 level, despite wasting capacity, which modern processors tolerate for easier consistency management, making inclusive more common than exclusive today.

Inclusive caches

Every line in L1 must be presented in L2 ($\text{L1}\subseteq \text{L2}$). When L2 evicts a line, it must invalidate the corresponding line in L1, and L2 can have a larger line size than L1.

Exclusive caches

If a line, A, is in L1, it must NOT be presented in L2. AMD had adopted this for L2/L3. When L1 evicts a line, it moves to L2. On an L1 miss that hits in L2, the line migrates from L2 to L1. And L1 and L2 must have the same line size.

NINE (Non-Inclusive and Non-Exclusive)

More suitable for L2/L3.

Average Memory Access Time (AMAT)

Usually, %instr is higher than %data, but I-cache hits better because instruction accesses are highly sequential with strong spatial locality, have no write misses (read-only), and exhibit simpler access patterns than data references, which often involve random pointers or strided array accesses.

AMAT was accurate for blocking caches and in-order CPUs, but lost relevance as out-of-order execution, non-blocking caches, prefetching hid miss latency and spliting I/D caches.

Low Hit Latency

• Small and Simple
• Direct-map or low associativity Number of comparators needed equals total cache entries for fully associative, but only $n$ for $n$-way set associative.
• Prediction Predict which way to compare first.
• Virtual address cache or virtual index and physical tagged cache Avoid or overlap with address translation delay.
• Cache layout closer to CPU to minimize signal delay

Chapter 7 Linking

Why Linking Matters

Modularity

Separate compilation allows developers to work on different modules independently, improving productivity and enabling code reuse.

Efficiency

• Time Separate compilation & Parallel compilation.
• Space Static linking (Executable files and running memory images contain only the library code they actually use.) & Dynamic linking (Executable files contain no library code. During execution, a single copy of the library code is shared among all executing processes.)

Static Linking

Symbol Resolution

Symbol tables in object files record symbol definitions (name, size, location), and the linker matches each symbol reference to exactly one definition during symbol resolution.

Link Symbols

Strong symbols are procedures and initialized globals, while weak symbols are uninitialized globals. Linker's Symbol Rules: Multiple strong symbols are forbidden; one strong wins over weak; multiple weak are arbitrary, unless -fno-common forces an error.

Avoid global symbols if possible, otherwise use static to limit scope, initialize globals to make them strong, and reference external globals with extern to avoid linker errors.

Static Libraries

Concatenate related relocatable object files into a single file with an index (called an archive). For example, ar rs libfoo.a a.o b.o c.o creates a static library libfoo.a containing a.o, b.o, and c.o.

Linkers scan files left to right, maintain an unresolved reference list, and only extract archive members that resolve current entries, so libraries must come at the end of the command line.

The solution to deal with the order sensitivity and duplicate symbol definitions is to introduce Shared libraries are object files whose code and data are loaded and linked into an application dynamically, either at load time or at run time.

Relocation

It first merges all separate code and data sections into single sections. Then, it relocates symbols from their relative offsets in .o files to final absolute addresses in the executable. Finally, it updates every reference to these symbols to reflect their new positions.

Object Files

Classification

ELF Object File Format

Component	Description
ELF Header	Word size, byte ordering, file type (.o / executable / .so), machine type, etc.
Segment Header Table (for OS)	Page size, virtual address memory segments (sections), segment sizes.
.text	Code
.rodata	Read-only data: jump tables, string constants, etc.
.data	Initialized global variables and initialized local static variables.
.bss	Uninitialized global variables and uninitialized local static variables. Has section header but occupies no space.
.symtab	Symbol table: procedure names, global variable names, static variable names, external symbols, section names, and their locations.
.rel.text	Relocation info for .text section: addresses of instructions that will need to be modified in the executable, plus instructions for modifying.
.rel.data	Relocation info for .data section: addresses of pointer data that will need to be modified in the merged executable.
.debug	Info for symbolic debugging (generated with gcc -g).
Section Header Table (for execution and debugging)	Offsets and sizes of each section.

• Using the command readelf -s <file> to view the symbol table of an Executable and Linkable Format (ELF) file.

• Note that Local non-static variables are stored on the stack.

• It will create local symbols in the symbol table with unique names.

Executable Object Files

Load Executable Object Files

Dynamic Linking with Shared Libraries

Load-Time Linking

It occurs when the executable is first loaded and run. The standard C library (libc.so) is typically dynamically linked this way.

LD_PRELOAD forces the dynamic linker to load a user-specified shared library first, allowing interception of standard functions, but cannot intercept statically linked _start.

Run-Time Linking

It occurs after the program has begun, using calls to the dlopen() interface on Linux.

Position-Independent Code (PIC)

To exploit the fact that the distance between any instruction in the code segment and any variable in the data segment is a runtime constant, the compiler creates a table called the Global Offset Table (GOT) that holds the absolute addresses of global variables.

Global Offset Table (GOT)

Resides in the data segment and stores the actual absolute addresses of external functions and global variables. These addresses are filled in by the dynamic linker at load time or on the first call.

Procedure Linkage Table (PLT)

A memory section containing small executable stubs for each external function the program calls. It lives in a read-only code section (.text or .plt), providing a trampoline that jumps through the GOT to the actual function.

.got stores addresses of global variables for direct access, while .got.plt stores addresses of external functions specifically for PLT stubs

Whole Process