Catalogue

Course Notes

CSC3060

• CSC3060 Notes — Core lecture notes
• CSC3060 CSAPP Reference — Supplementary notes based on Computer Systems: A Programmer's Perspective

CSC4303

• CSC4303 Notes — Core lecture notes

DDA3020

• DDA3020 Notes — Core lecture notes

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

Chapter3

CISC [optimized for compact code size]

Size of Data Type in IA32

Register

Operands

• Immediate

• Register

• Memory Reference Immediate & Base Register & Index Register & Scale Factor (1,2,4,8)

Operation code

• Movement

  • $\text{mov}\text{S,D}$ [movb, movw, movl, movq, movabsq]

    Source operand (Immedita, Register, Memory); Destination operand (Register, Memory)

    Two operands of a move instruction cannot both be memory references. (It is necessary to first move the source memory reference into a register, and then move it to the destination memory reference.)

    movl writes 32 bits of data to the lower half and then automatically zero-extends the value into the upper 32 bits. (In x86-64, any instruction that generates a 32-bit result for a register will set the upper 32 bits of that register to zero.)

    movq can only be 32 bits (sign-extended to 64 bits), whereas movabsq can be 64-bit but the destination must be a register.

  • $\text{movz}\text{S, R}$ [movzbw, movzbl, movzwl, movzbq, movzwq]

    movzlq does not exist because of movl instruction.

  • $\text{movs}\text{S, R}$ [movsbw, movsbl, movswl, movsbq, movswq, movslq, cltq]

    cltq same as movslq %eax, %rax

• Stack

  let a quad number be the example

  • $\text{pushq}S$

    subq $8 %rsp
    movq %rbq,(%rsp)
    

  • $\text{popq}S$

    movq (%rsq),%rax
    addq $8, %rsp
    

Load Effective Address

$\text{leaq}S,D$

Computes effective address and stores it in destination register

Unary Operations

Binary Operations

Shift Operations

Shift instructions can shift by an immediate value, or by a value placed in the single-byte register %cl.

Condition Code

• $\text{CF}$ Carry Flag [check for overflow in unsigned operations]

• $\text{ZF}$ Zero Flag

• $\text{SF}$ Sign Flag

• $\text{OF}$ Overflow Flag

• $\text{cmpS D}$

  Similar to sub, but it only sets the condition codes without changing the value of the destination register.

  When S == D, $\text{ZF}=1$.

  It will set the condition codes based on the result of $D-S$.

• $\text{testS D}$

  Similar to and, but it only sets the condition codes without changing the value of the destination register.

  When S & D == 0, $\text{ZF}=1$.

Set Instructions

Jump Instructions

Conditional Move Instructions

Loop

do-while, while, and for loops can be implemented by combining conditional tests and jumps.

Switch

switch is compiled into a jump table. The execution time of the switch statement is irrelevant to the number of cases.

Transfer Control

Data Transfer

The registers' names depend on the size of the data type being passed.

If a function has more than 6 integer parameters, the additional arguments must be passed on the stack. Note that the argument 7 is located at the top of the stack. All stack-passed arguments are aligned to multiples of 8 bytes.

Pointer

Notes:

1. &E[i] - E yields type long (specifically ptrdiff_t) because pointer subtraction returns the number of elements between them as a signed integer.

2. int* uses movq (not movl) because pointers are 64-bit addresses in x86-64.

Nested Arrays

T D[R][C] $\&D[R][C]=x_D+L(C\cdot i+j)$, $L$ is the size of data type T in bytes.

Struture & Union

Structure

Notes:

1. The address of any K-byte basic object must be a multiple of $K$.

2. The offset of the first member is always 0 in a structure.

3. The compilers probably add some bytes at the end of a structure to ensure that each element in an array of structures could satisfy its alignment requirements.

Union

The total size of a union equals the size of its largest field.

Application

Buffer Overflow

Three protection mechanisms to thwart buffer overflow attacks:

• Stack Randomization Address-Space Layout Randomization (ASLR)

• Stack Corruption Detection Place a random canary value between local buffers and critical stack data to detect buffer overflows.

• Limiting Executable Code Regions

Dynamic Stack Frame

%rbp is base pointer/frame pointer dynamic stack frame

Floating-point Code

Chapter 4 Processor Architecture

Logic Design and Hardware Control Language (HCL)

Logic Gate

CMOS

Process

$\text{Fetch}\to \text{Decode}\to \text{Execute}\to \text{Memory}\to \text{Write Back}\to \text{Update}$

For Y86-84 :

1. Fetch

   • Read instruction bytes from memory using PC:
     • icode:ifun (instruction specifier)
     • rA, rB (register specifiers)
     • valC (8-byte constant)
   • Compute next instruction address → valP

2. Decode

   • Read up to two operands from registers
   • rA, rB → valA, valB
   • For popq, pushq, call, ret: also read from %rsp

3. Execute

   • Compute (ALU/address/stack) → valE
   • Set condition codes
   • Conditional moves: check CC, update dest register
   • Jumps: decide branch

4. Memory

   • Write to memory
   • Read from memory → valM

5. Write Back

   • Write up to two results to registers

6. Update

   • Set PC to next instruction address

Pipelining

• Throughput the number of instructions in one second.

  GIPS: Giga-Instructions Per Second

• Circuit Retiming

  Repositions registers within a design to optimize performance or area, without altering the system’s input/output behavior. It changes the state encoding by moving delays (registers) across combinational logic elements.

Hazards

The dependency between instructions may lead to incorrect computation results.

Data Hazards

• Stalling

  Stalling prevents data hazards by pausing the pipeline until required operands are ready. This approach is simple but reduces performance.

• Data Forwarding (Bypassing)

  Data forwarding allows a result computed in a later pipeline stage to be passed directly to an earlier stage as a source operand.

• Load/Use Hazards

  A load/use hazards occurs when an instruction requires a value that is still being loaded from memory by the previous instruction. Since the memory read completes late in the pipeline, forwarding cannot resolve the dependency in time, causing a stall.

Control Hazards

Control hazards occur when the processor cannot determine the next instruction's address during the fetch stage. In a pipelined processor, this typically happens for ret instructions and mispredicted conditional jumps.

• ret Inserting bubbles to wait for the return address to be determined.

• Conditional Jump Branch mispredictions are handled by cancelling the erroneously fetched instructions through the insertion of pipeline bubbles (or via instruction squashing) in the decode and execute stages.

Pipelined Y86-64 Implementations

Fetch Stage

1. Sequential Execution

halt, nop, rrmovq, irmovq , mrmovq, Opq, pushq, popq, covXX, addq

2. Jump Execution

call, jxx (The Select PC mechanism is employed to correct branch mispredictions.)

3. ret

Decode Stage

The selection logic chooses between the merged valA/valP signals and one of five forwarding sources (e_valE, m_valM, M_valE, W_valM, or W_valE) based on the instruction type and hazard detection. If no forwarding is triggered, d_rvalA (the register file read) is used as the default value.

Pipeline Control Logic

• Stall

  Keep the state of the pipeline registers unchanged. When the stall signal is set to 1, the register will retain its previous state.

• Insert Bubbles

  Setting the state of the pipeline registers to a value equivalent to a nop instruction. When the bubble signal is set to 1, the state of the register will be set to a fixed reset configuration.

Load/Use Data

A one-cycle pipeline stall is required between an instruction that reads a memory value in the execute stage and a subsequent instruction that uses that value in the decode stage.

Mispredicted Branches

When a branch is mispredicted as taken, the pipeline must squash the incorrectly fetched instructions from the target path and redirect fetching to the correct fall-through address.

Processing ret

The pipeline must stall until the ret instruction reaches the write-back stage.

Exception Handling

When an instruction triggers an exception, all subsequent instructions must be prevented from updating programmer-visible state, and execution must halt once the exception-causing instruction reaches the write-back stage.

Chapter 5 Optimizing Program Performance

Capabilities and Limitations of Optimizing Compilers

Memory Aliasing

The two pointers probably reference the same memory address.

Function Calls

Performance

CPE: Cycles Per Element.

Understanding Modern Processors

Instruction Control Unit (ICU) & Execution Unit (EU)

The ICU reads instructions from the instruction cache and uses branch prediction to speculatively fetch and decode future instructions in advance. This speculative execution mechanism allows the processor to start executing operations along the predicted program path before the actual branch outcome is known. If the prediction is incorrect, all speculative results are discarded and execution restarts from the correct branch target.

Decoded instructions are broken down into micro-operations, which are then sent to the EU for execution. The EU includes arithmetic units and dedicated load/store units, each with address calculation logic, to perform memory operations via the data cache.

All along, the retirement unit tracks instruction progress to ensure sequential program semantics are preserved. Instructions remain in a queue until their results are ready and all relevant branch predictions are verified. Only then are results committed to the architectural registers. If a branch was mispredicted, the affected instructions are flushed and their results discarded, preventing any erroneous state change in the program.

Register renaming allows out-of-order execution by assigning unique tags to instruction results. When a later instruction needs a register value, it uses the tag to get the result directly once ready, avoiding waits for register writes and enabling speculative execution.

Each operation is characterized by the following metrics:

• latency It represents the total time required to complete the operation.

• Issue time It indicates the minimum number of clock cycles needed between two consecutive operations of the same type.

• Capacity It refers to the number of functional units capable of executing that operation.

CSC4303 Network Programming

Reference

• Reference

Network Model

Transport Layer

User Datagram Protocol (UDP)

• Connectionless

  Each packet is independent.

  Sender    Time       Receiver
    |                     |
    |----- Packet1 -----> |
    |                     |
    |----- Packet2 -----> |
    |                     |
  

• Buffering

  UDP buffering is a "temporary storage area" maintained by the operating system for each UDP port, where arriving packets queue up when applications can't process them immediately.

  Application A  Application B   Application C
      ↓               ↓               ↓
  [Port X]        [Port Y]        [Port Z]      ← Port mapping
      ↓               ↓               ↓
  [Queue 1]       [Queue 2]       [Queue 3]     ← Independent UDP message queues
      │               │               │
      └───────┬───────┴───────┬───────┘
              ↓               ↓
      [Port Multiplexer/Demultiplexer]          ← Routes by port number
              ↓
      [Incoming UDP packets]
  

• Header

  Note that the Datagram length up to 64K.

       32-bit width (4 bytes per row)
  0                  16                31
  ┌──────────────────┬──────────────────┐
  │ Source Port      │ Destination Port │ ← Port addressing
  │   (16 bits)      │   (16 bits)      │
  ├──────────────────┴──────────────────┤
  │    Length        │    Checksum      │ ← Size & integrity
  │    (16 bits)     │    (16 bits)     │
  ├─────────────────────────────────────┤
  │                                     │
  │           Application Data          │
  │                                     │
  └─────────────────────────────────────┘
  

Transmission Control Protocol (TCP)

• Header

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |          Source Port          |       Destination Port        | ← Identifies sockets
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                        Sequence Number (32)                   | ← Byte-based sequencing
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                    Acknowledgment Number (32)                 | ← Next expected byte
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  Data Offset  |  0  |  Flags  |       Window Size (16)        | ← Control & flow control
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |     Checksum (16)             |       Urgent Pointer (16)     | ← Integrity & urgent data
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                         Options (variable)                    |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                           Data                                |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  

  • Connection Establishment (Setup)

    • Three-Way Handshake

      Both parties send Initial Sequence Numbers (ISNs) via SYNchronize segments. Each party acknowledges the other's sequence number using ACKnowledge segments.

      

      Step	Initiator (Client)	Receiver (Server)	Description
      First Handshake	Sends $\text{SYN}=1,\text{seq}=x$	Waits for connection request	Client requests to establish a connection and sends its ISN $x$.
      Second Handshake	Waits for acknowledgment	Sends $\text{SYN}=1,\text{ACK}=1,\text{seq}=y,\text{ack}=x+1$ It acknowledges receipt through sequence number $x$.	Server agrees to connect, sends its own ISN $y$, and acknowledges the receipt of $x$.
      Third Handshake	Sends $\text{ACK}=1,\text{seq}=x+1,\text{ack}=y+1$	Connection established	Client acknowledges the receipt of $y$, and the connection is formally established.

      Three-way handshake prevents a server from wasting resources on stale or duplicate connection requests by requiring the client's final acknowledgment.

    • State Machine

      

      • Client Path CLOSED → connect() → SYN_SENT → Receive SYN+ACK → ESTABLISHED

      • Server Path CLOSED → listen() → LISTEN → Receive SYN → SYN_RCVD → Receive ACK → ESTABLISHED

      • Both parties run instances of this state machine, and TCP allows for simultaneous open.

  • Connection Release (Teardown)

    • Four-Way Handshake (symmetric)

      

      Step	Initiator (Active Closer)	Receiver (Passive Closer)	Description
      First Wave	Sends $\text{FIN}=1,\text{seq}=u$	Waits for close request	Initiator has finished sending data and requests to close its sending channel.
      Second Wave	Waits for remaining data	Sends $\text{ACK}=1,\text{ack}=u+1$	Receiver acknowledges the close request but may still have data to send.
      Third Wave	Waits for confirmation	Sends $\text{FIN}=1,\text{seq}=v$	Receiver has finished sending data and requests to close its sending channel.
      Fourth Wave	Sends $\text{ACK}=1,\text{ack}=v+1$	Connection closed	Initiator acknowledges the close request.

    • State Machine

      

      • Active Closer Path ESTABLISHED → close() → FIN_WAIT_1 → Receive ACK → FIN_WAIT_2 → Receive FIN → TIME_WAIT → Timeout → CLOSED

      • Passive Closer Path ESTABLISHED → Receive FIN → CLOSE_WAIT → close() → LAST_ACK → Receive ACK → CLOSED

      • TIME_WAIT State

        • $2\times \text{MSL}$ (Maximum Segment Lifetime).

        • Lost ACKs can be recovered.

        • Old segments won't confuse new connections.

  • Flow Control (Receiver processing limitation)

    • Automatic Repeat Query

      ARQ with one message at a time is Stop-and-Wait. It allows only a single message to be outstanding from sender.

    • Sliding Window

      It allows $W$ outstanding packets, enabling pipelining to send multiple packets per RTT for improved performance.

      Sender buffers up to $W$ segments until they are acknowledged. The last frame sent minus last ack rec'd should no more than $W$.

      

      • Go-Back-N

        Only buffers next expected packet (LAS). Accepts only sequential packets, discards others, sends cumulative ACK.

      • Selective Repeat

        Buffers entire window. Stores out-of-order packets, sends individual ACKs, retransmits only lost packets.

      • Sequence Number

        $n$ bit counter wraps around at $2^n-1$. Let $\text{LAR}$ be Last Acknowledgement Received, $\text{LAS}$ be Last Acknowledgement Sent.

        Method	Sender's Range	Receiver's Range	Min Number Needed to Avoid Overlap
        Go-Back-N	$[\text{LAR}+1,\text{LAR}+W]$	$\text{LAS}+1$	$W+1$
        Selective Repeat	$[\text{LAR}+1,\text{LAR}+W]$	$[\text{LAS}+1,\text{LAS}+W]$	$2W$

    • Pacing

      • ACK Clocking (sender)

        ACK clocking is a feedback mechanism where the network itself determines the sending pace, preventing queue buildup and ensuring efficient, low-latency data flow.

      • Flow Control (Receiver)

        Flow control uses the WIN field, calculated as WIN = ReceiveBuffer - (LastByteRcvd - LastByteRead), to dynamically limit the sender's window, preventing receiver buffer overflow.

      $\text{SEQ}+\text{length}<\text{ACK}+\text{WIN}$

      • Adaptive Timeout

        Name	Formula
        $\text{SRTT}$ (average round‑trip time)	${\text{SRTT}}_{n+1}=(1-\alpha )\cdot {\text{SRTT}}_n+\alpha \cdot {\text{RTT}}_{n+1}$
        $\text{Svar}$ (variability of RTT)	${\text{Svar}}_{n+1}=(1-\beta )\cdot {\text{Svar}}_n+\beta \cdot \mid {\text{RTT}}_{n+1}-{\text{SRTT}}_{n+1}\mid$
        $\text{Timeout}$	${\text{Timeout}}_n={\text{SRTT}}_n+4\cdot {\text{Svar}}_n$

  • Congestion Control (Network capacity limitation) TCP congestion control uses a sliding window (cwnd), interprets packet loss as a congestion signal, and adjusts the window via AIMD to achieve an efficient and roughly fair bandwidth allocation.

    • Max-Min fairness

      Increse the rate of one flow will decrease the rate of a smaller flow.

      Step 1 Initialize all flows at zero
      Step 2 Increase all flows equally
      Step 3 Freeze bottlenecked flows
      Step 4 Repeat for remaining flows

    • Bandwidth allocation

      Network layer provides direct feedback & Transport layer reduces load [Network is distributed, no single party has an overall picture of its state.]

      • Models

        • Open loop [reserve] & Closed loop [use feedback to adjust rates]

        • Host support & Network support

        • Window based & Rate based

        TCP is a closed loop,host-driven, and window-based

      • AIMD(Additive Increase Multiplicative Decrease)

        • Hosts additively increase rate while network not congested

        • Hosts multiplicatively decrease rate when congested

    • TCP Tahoe/Reno

      

      • Slow Start

        For each ACK received: $\text{cwnd}=\text{cwnd}+1$, $\text{cwnd}$ doubles every RTT.

      • Later Additive Increase (AI)

        For each ACK received: $\text{cwnd}\leftarrow \text{cwnd}+\frac{1}{\text{cwnd}}$, roughly adds 1 packet per RTT.

      • Switching Threshold (Initially Infinity)

        Switch to AI when When $\text{cwnd}>\text{ssthresh}$, and $\text{ssthresh}=\frac{\text{cwnd}}{2}$ after loss. Begin with slow start after timeout ($\text{cwnd}=1$).

      • Fast Retransmit

        TCP's cumulative ACKs allow duplicate ACKs to signal lost packets for fast retransmission.(Treat three duplicate ACKs as a loss.)

      • Fast Recovery (TCP Reno)

        Fast recovery keeps data flowing during retransmission by maintaining the ACK clock. It avoids resetting to Slow Start after packet loss. Set $\text{ssthresh}=\frac{\text{cwnd}}{2}$ and then continue AI directly.

UDP & TCP

Socket

An endpoint for network communication that allows an application to attach to a specific port on the local network interface, enabling data exchange with other applications across the network.

• Process

  Cilent socket () ------------------------> connect () -> I/O -> close ()

  Server socket () -> bind () -> listen () -> accept () -> I/O -> close ()

  1. The server blocks in accept() on listenfd for incoming connections.

  2. The client calls connect() to initiate the TCP handshake, which also blocks.

  3. Upon completion, the server's accept() returns a connfd and the client's connect() returns, establishing a bidirectional channel between clientfd and connfd.

• Create int socket (int domain, int type, int protocol);

  • domain AF_INET IPv4 / AF_INET6 IPv6.

  • type SOCK_STREAM TCP / SOCK_DGRAM UDP.

  • protocol 0 (automatically select the default protocol).

• Bind int bind (int sockfd, sockaddr *addr, socklen_t addrlen);

  When a server binds a socket to a specific address, it establishes that data arriving at that address is read from this socket, and data written to this socket is sent from that address.

  • socket address

    struct sockaddr
    {
        uint_16 ss_family; // protocol family
        char ss_data[14]; // address data
    }
    

  • sockaddr_in

    struct sockaddr_in
    {
        uint16_t sin_family; // always AF_INET
        uint16_t sin_port; // in network byte order
        struct in_addr sin_addr; // in network byte order
        unsigned char sin_zero[8]; // pad to sizeof (struct sockaddr), placeholder
    }
    

    Network data is transmitted in big-endian byte order. Use htons() and htonl() to convert host-ordered values into network-ordered short and long integers, respectively.

• Listen int listen (int sockfd, int backlog);

  listen () transforms a socket descriptor into a listening socket capable of accepting client connections. The backlog parameter suggests how many pending connections the kernel may queue before refusing new requests (typically around 128).

• Accept int accpet (int listenfd, sockaddr *addr, int *addrlen);

  accept() blocks until a client connects via listenfd, stores the client's address in addr, and returns a connfd for communication using standard Unix I/O functions.

• Connect int connect (int clientfd, sockaddr *addr, socklen_t addrlen);

  Attempts to establish a connection with server at socket address addr.

  To convert a string-formatted IP address (e.g., SERVER_IP), use inet_pton (int af, const char *src, void *dst) to transform it into binary network format.

  Feature	listenfd	connfd
  Purpose	Accepts connection requests	Handles data exchange with a client
  Creation	Once at server start	Per accepted connection
  Lifetime	Entire server runtime	Duration of client service
  Quantity	One per port	One per active client
  Concurrent Use	Listens for all clients	Dedicated to single client

• Send and Receive

  ssize_t read (int fd, void *buf, size_t len); returns the number of bytes actually read (0 indicates the connection is closed, -1 indicates an error).

  ssize_t write (int fa, const void *buf, size_t len); returns the number of bytes actually written (-1 indicates an error).

• Close int close (int sockfd)

• Concurrency

  • Threading/Process Race conditions increase complexity!

  • I/O Multiplexing

    • select()

    • poll()

      poll() is a system call used to monitor multiple file descriptors concurrently for I/O readiness. Unlike select(), it imposes no fixed limit on the number of file descriptors that can be monitored.

      struct pollfd
      {
          int fd; // file descriptor
          short events; // requested events
          short revents; // returned events
      }   
      

Network Layer

Internet Protocol (IP)

• IPV4 Header

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| IHL   |Type of Service|        Total Length (16)      | ← Basic identification (IHL : Header)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|        Identification (16)    |Flags|   Fragment Offset (13)  | ← Fragmentation control
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Time to Live |    Protocol   |        Header Checksum (16)   | ← Routing & integrity (Time to Live : TTL)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Source Address (32)                     | ← Sender IP
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Destination Address (32)                   | ← Receiver IP
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Options (if any, variable)                 | ← Optional features
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                           Payload (Data)                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• IP Addresses An IP address is assigned to each network interface. Consequently, routers possess multiple interfaces, while most hosts have just one or two (wired and wireless).

• IP Prefixes In a prefix of length L, the top L bits are identical across all addresses. In CIDR notation, such a prefix is denoted as IP address/prefix length (e.g. 128.13.0.0/16 is 128.13.0.0 to 128.13.255.255.)

• IP Forwarding It uses longest prefix matching to select the most specific route.

• IP fragmentation

  • MTU Max Transfer Size
  • MSS Maximum Segment Size
  

  Each fragment is encapsulated with its own IP header.

  Field	Size (bits)	Purpose
  Identification	16	Unique identifier for the original datagram; all fragments of the same datagram share this value.
  Flags	3	Control bits for fragmentation DF (Don't Fragment) If set 1, routers must not fragment the packet. MF (More Fragments) If set 1, more fragments follow, otherwise indicates that it is the last fragment.
  Fragment Offset	13	Indicates the position of this fragment's data in 8‑byte units relative to the start of the original datagram.

Dynamic Host Configuration Protocol (DHCP) [Application Layer]

Uses UDP ports 67 (server) and 68 (client).

Address Resolution Protocol (ARP)

Every network device possesses a unique MAC (Media Access Control) address, which operates at the link layer.

ARP resolves IP to MAC addresses locally. A node broadcasts an ARP request, receives a private reply, and caches the mapping in its ARP table.

Internet Control Message Protocol (ICMP)

When an error occurs, an ICMP error report is sent back to the source IP address and the problematic packet is discarded. The source host must then rectify the issue.

• Message Format

  • IP Header Src = router, Dst = A, Protocol = 1

  • ICMP Header Type = X, Code = Y

  • ICMP Data Src = A, Dst = B, ...

• Type

• Traceroute

Traceroute sends probe packets with incrementing TTL. Each router that decrements TTL to zero replies with an ICMP Time Exceeded error, revealing its address.

Network Address Translation (NAT)

NAT maps multiple private IP:port pairs to a single public IP with unique external ports via a stateful translation table, enabling many internal devices to share one external address.

Routing and Forwarding

• Fully Distributed Routing

  • No central controller All routers are equal and make independent decisions.
  • Local knowledge only Routers learn about the network by exchanging messages with directly connected neighbors.
  • Concurrent operation
  • Failure tolerance There may be node/link/message failures.

• Hierarchical Routing

  Introduce a larger routing unit. Route first to the region, then to the IP prefix within the region.

  • Routing Table

    • Static Routing
    • Dynamic Routing RIP (Routing Information Protocol), OSPF (Open Shortest Path First), BGP (Border Gateway Protocol).

  • IP Prefix Aggregation and Subnets (Longest prefix matching)

    Routers can change prefix lengths without affecting hosts.

    • Subnetting Split large prefix into smaller ones internally.
    • Aggregation Join small prefixes into one large prefix externally.

Routing

• Sink Tree

  Sink tree for a destination is the union of all shortest paths towards the destination. Each node only stores next hop (parent) towards root.

• Distance Vector Routing

  Each node shares distance vectors with neighbors, updates paths using shortest heard distance, and forwards via best next hop.

  Slow convergence, count-to-infinity, and routing loops occur because nodes only know neighbor info, not full topology, causing outdated routes to propagate and persist.

  • RIP (Routing Information Protocol)

• Link-State Routing

  • Flooding
    • Send an incoming message on to all other neigbors.
    • Remember the message so that it is only flooded once.
  • Dijkstra

Application Layer

Peer to Peer

Leverage peer resources: computation, storage, bandwidth. Also emerging: mobility, coins (tokens), sensors. Decentralized, scalable architecture.

Storage networks replicate files anywhere, making search difficult, especially with node churn.

• Framework

  • Join How to start participating
  • Publish How to advertise files
  • Search How to find files
  • Fetch How to retrieve files

• Napster

  Server does all porcessing & Server maintains $O(N)$ state & Single point of failure

  • Join Client contacts central server on startup
  • Publish Reports list of files to central server
  • Search Query server → returns peer storing requested file
  • Fetch Get file directly from peer

• Gnutella

  Complete decentralization & Query flooding

  Search scope is $O(N)$ & Unpredictable search time & No guarantee of finding files (TTL-limited search only works well for haystacks)

  • Join Client contacts a few existing nodes on startup → these become its "neighbors"
  • Publish No need (no central index)
  • Search Ask neighbors → neighbors ask their neighbors → when/if found, reply back along the path; TTL limits propagation
  • Fetch Get file directly from peer

• Gnutella/KaZaA [Two-level hierarchy]

  Kept a centralized registration

  Supernodes have better connection to Internet and act as temporary indexing servers for other nodes to help improve the stability fo the network.

  Standard nodes connect to supernodes and report list od files.

• BitTorrent

  Central tracker server needed to bootstrap swarm.

  • File swarming Files split into chunks; download from multiple peers, upload to others simultaneously.
  • Tracker Central server coordinates peers (joins, maintains lists), but doesn't store files.
  • Tit-for-tat Upload to the fastest $N$ peers you download from. Encourages fairness, discourages freeloading.
  • Optimistic unchoke Randomly let new peers download to prevents starvation, discovers better partners.
  • Rarest first Prioritize distributing scarce chunks to improve file availability and resilience.
  • Out-of-band search Find files via Google/torrent sites. Scalable, no single point of failure.

• DHT (Distributed Hash Table)

  Decentralized system using consistent hashing: keys and nodes hashed onto a ring (Chord). Each key stored on its successor node. Finger tables enable $O(\log N)$ lookup (Entry $i$ which starts from $1$ points to the first node on the ring that is $\ge x+2^{i-1}$), improving from naive $O(N)$.

Amazon Dynamo

• Architecture

  

• Partition

  • Hash partitioning partition = hash(key) % partition_count

  • Consistent hashing (better)

  • Virtual nodes (vnodes) Virtual nodes assign multiple ring positions to each physical node, distributing data migration and improving load balancing across all nodes.

  • Heterogeneity More powerful nodes can have more capacity, thus more vnodes.

  • Replication Dynamo skips nodes to ensure replicas reside on different nodes (set Replication Factor, i.e. $RF$).

  • Dynamo Reads/Writes $R/W$ is configurable. When $R+W>RF$, the read and written will overlap, with last write wins (LWW) resolving conflicts.

  • Dynamo API

    • get (k) returns value(s) and context. It returns multiple versions if conflicts exist. The context contains Timestamps to track version history.
    • put (k,context,value) uses the provided context to indicate which previous version(s) this new version supersedes or merges.

HyperText Transfer Protocol (HTTP)

• Request

• Response