9/9 Notes: Combinational Devices and Boolean Algebra

Voltage Transfer Characteristics

1. The center white region is taller than it is wide. Net result: device must have GAIN > 1 and thus be ACTIVE
2. VTC can do anything when $V_{IL}$ < $V_{IN}$ < $V_{IH}$

Combinational Circuits

• Do not have memory
• Each output is a function of current input values

Sequential Circuits

• Have memory, ie, state
• Each output depends on current state + current inputs

Combinational Devices

A circuit element that has

• One or more digit inputs
• One or more digital outputs
• Functional specification that details the value of each output for every possible combination of valid input values
• A timing specification consisting (at a minimum) of a propagation delay
  • An upper bound on the required time to produce valid stable output values form an arbitrary set of valid stable input values

• Each circuit element is combinational
• Every input is connected to exactly one output or to a constant (0 or 1)
• The circuit contains no directed cycles

These conditions are sufficient, not necessary. A device may be combinational even if it doesn't satisfy these conditions

Functional Specifications

There are many ways to specify the function of a combinational device

We will use two systematic approaches:

• Truth tables enumerate the output values for all possible combinations of input values
• Boolean expressions are equations containing binary (0/1) variables and three operations: AND (.), OR (+), and NOT (overbar)

Propagation delay ($t_{PD}$): An upper bound on the delay from valid inputs to valid outputs

• Used later (for sequential logic)

The Combinatorial Contract

Boolean Algebra

Boolean Algebra comprises

• Two elements, 0 and 1
• Two binary operators, AND and OR
• One unary operator, NOT

Axioms

• Holds for axioms -> holds for all expressions

• a + b * c doesn't hold for integers

Equivalence and Normal Form

• It is unique, but there may be simpler expressions

Corollary: Boolean expressions can represent any combinational function

Logic Synthesis

A logic diagram represents a Boolean expression as a circuit schematic with logic gates and wires

SOP (Sum of Products) Boolean Expression with three levels of gates:

1. Inverters
2. ANDs
3. ORs

• It isn't unique

Simple algebraic manipulations, K-maps

Multilevel Boolean Simplification

Inverting logic (NAND, NOR)

NANDs and NORs are universal

1. Current technology, inverting gates are faster and smaller
2. Delay and area grow with number of inputs

Infeasible, so hardware designers write circuits in a hardware description language and use a synthesis tool to derive optimized implementations

9/11 Notes: Minispec

Learn how to design a combinational circuit as a function, which can be simulated or synthesized into gates

Building a Combinational Adder

Goal: Build a circuit that takes two n-bit inputs a and b and produces $(n+1)$-bit output $s = a + b$

i-th step of addition:

• Take three 1-bit inputs, a,b,c (carry-in)
• Produce two 1-bit outputs: s, c (carry-out)

Full Adder (FA)

• Adds 3 one-bit numbers: a,b, and carry-in
• Produces a sum bit and a carry-out bit

Cascade FAs for binary addition: called a ripple-carry adder

A hardware description language (HDL) is a programming language specialized to describe hardware

• Specify the structure and behavior of digital circuits
• Designs can be automatically simulated or synthesized to hardware
• Enables building hardware with same principles used to build software (write and compose simple, reusable building blocks)
• Uses a familiar syntax (functions, variables, control-flow statements, etc.)

Minispec

Combinational Logic as Functions

• Combinational circuits are described using functions

• Types start with an uppercase letter, all variable and function names are lowercase

Bool: True or False

Bit\#(n): n-bit value

Full Adder in Minispec

4-bit Ripple-Carry Adder

Multiplexer

2-way multiplexer or mux selects between two inputs a and b based on a single-bit input s

Equivalent to:

Usually used using 2-way multiplexers

$K$-way $n$-bit mux uses $(k-1) \cdot n$ one-bit muxes

In hardware, the statement instantiates and evaluates both foo(x) and bar(y) in parallel

Constant selector: x{[}2{]}

Shift Operators

Fixed-size shift operation is cheap in hardware

• Just wire the circuit appropriately

Logical shifts insert zeros

Naive is to have 32 different fixed-size shifters and select using a mux

Barrel Shifter

Efficient circuit to perform variable-size shifts

Barrel shift performs shift by s using a series of fixed-size power-of-2 shifts

Instead of $N^2$, it would be NlogN = 160 for N=32

For $N=4$

9/16 Notes: Complex Combinational Logic

Complex Combinational Logic

Parametric Types

• Bit\#(n), an n-bit value, is a parametric type
  • n is the parameter (an integer)
  • Using Bit\#(n) requires specifying a fixed n
• Minispec provides other parametric types, lets you define your own
  • Parametric types are generic
  • Take on one or more parameters
    • Must be known at compile time
  • Specifying the parameters yields a concrete type
• Parameters can be Integers or types
  • Ex: Vector\#(n,T) is n element vector of T's

Parametric Functions

• Functions have fixed argument and return types
  • Problem 1: Have to write a function for every bit width
  • Problem 2: If you build large functions from smaller ones, you have to write many functions!
• Parametric functions: write one generic function that covers every case
  • rca\#(n), a n-bit ripple-carry adder
• Parametric function must be invoked with fixed parameters, which instantiates a concrete function
  • rca\#(32) instantiates a 32-bit adder

Integer is A special Type

• Integer values are (positive or negative) numbers with an unbounded number of bits
  • Unbounded bits -> can't be synthesized to hardware
• Integers are guaranteed to be evaluated at compile time, ie, turned into fixed numbers
  • If compiler can't evaluate an Integer expression, it throws an error
• Integer supports same operations as Bit\#(n), (arithmetic, logical, comparisons, etc)
  • But evaluated by compiler -> operations on Integers never produce any hardware

User-Defined Types

Type synonyms: giving a different name to a type

Structs: group of member values with different types

Enums: set of symbolic constants

Much clearer than using raw bits!

For Loops

• Allow compactly expressing a sequence of similar statements
• Not like loops in software programming languages
  • Fixed number of iterations
  • Unrolled at compile time

Conditional Statements

• Similar syntax, but implemented very differently than software
  • Translated to muxes, like conditional expressions
  • Each variable assigned within an if statement uses a mux to select the right value (one assigned in the if branch, else branch, or previous value)
• Minispec also has case statements

Minispec Takeaways

• Lets you build circuits with constructs similar to those of software programming languages
• Implementation of these features often very different from software
  • Parametric functions and types are instantiated
  • Functions are inlined
  • Conditionals are translated to multiplexers
  • Loops are unrolled

Algorithmic Tradeoffs in Hardware Design

• Choosing the right algorithm is key to optimizing your design

Ripple-Carry Adder: Simple but Slow

when adding 11\ldots111 to 00\ldots001,

Carry-Lookahead Adders (CLAs)

• CLAs compute all carry bits in $O(\log n)$ delay
• Key idea: Transform chain of carry computations into a tree

Fixed-Size Shifts

• Fixed-size shift operation is cheap in hardware
  • Wire the circuit appropriately
• Logical shifts insert zeros

• Arithmetic Shifts are similar

• $\log_2(N)$ muxes that choose between shifting by $2^i$ and not

Building a Carry-Lookahead Adder

• Step 1: Generate the output carry in $O(\log n)$ delay
• Step 2: Extend step 1 to generate all carries in $O(\log n)$ delay

2 main ideas that are broadly useful beyond CLAs:

• Step 1: function composition is associative
• Step 2: parallel scan algorithm

Turning Function Chains into Tree

Since function composition is associative, can turn a chain of functions into a tree by first composing the functions

1-bit input, 1-bit output

Composing 1-bit functions

Generating Output Carry

Generating all carries

• Also need all intermediate ones as well
• Parallel scan algorithm

Option 1: Brent-Kung CLA

Low area but extra delay

Option 2: Kogge-Stone CLA

High area, but lower delay

• 2 bits per function, but 3 values, so how they are encoded can affect logic cost

F = \{g,p\}

• g = ab (generate bit)
• p = a + b (propagate bit)

g = 0, p = 0 -> kill

g = 0, p = 1 -> propagate

g = 1, p = 1 -> generate

9/18 Notes: CMOS Technology

CMOS Technology

Differences in technology

Single-Thread Performance slowing down compared to transistors

• Logical Cores starting popping up on each device

Deep Dive in a Chip

Field-Effect Transistors (FETs)

Transistor (FET) are voltage controlled switches

pFET (p-channel): In a pFET, the charge carriers are holes, which are effectively positive charges (the absence of an electron). For a conducting path to form, holes flow from the source to the drain.

Source and drains are called diffusion terminals

By convention, we label diffusion terminals as source or drains depending on their voltages:

• On nFETs, source = diffusion terminal at lower voltage
• On pFETs, source = diffusion terminal at higher voltage

FETs have a threshold voltage $V_{TH}$

• nFET is ON if voltage between gate and source $V_{GS}$ exceeds $V_{TH}$, OFF otherwise
• pFET is ON if voltage between source and gate $V_{SG}$ exceeds $V_{TH}$, OFF otherwise

Two drains are connected to $V_{out}$

• nFET and pFET are sometimes abbreviated as nMOS and pMOS
• CMOS stands for complementary MOS

A = 0, B = 1 -> 1

A = 1, B = 0 -> 1

A = 1, B = 1 -> 0

CMOS NAND gate

CMOS Logic

CMOS gates have complementary pullup and pulldown networks

Bad Gates

General CMOS Gate Recipe

• Step 1: Derive pullupnetwork that does what you want
• Step 2: Derive complementary pulldown network: replace pFETs with nFETs, series subnets with parallel subnets, and parallel subnets with series subnets
• Step 3: Combine pFET pullup network from Step 1 with nFET pulldown network from Step 2 to form the CMOS gate

A single CMOS gate can't implement any arbitrary function

CMOS Gates are Inverting

• In a CMOS gate, rising inputs (0 -> 1) lead to falling output (1 -> 0) and vice versa

On a rising input:

• nFETs go OFF -> ON, so pulldown may connect output to ground
• pFETs go ON -> OFF, so pullup may disconnect output from $V_{DD}$
• Output either stays the same or falls

Corollary: cannot build non-inverting logic using a single CMOS gate

• AND is a NAND + INVERT

MOSFET Physical Structure

FET First-Order Electrical Model

• Wider FETs drive more current (less R), but gates are harder to drive (higher C), and take more area

CMOS Power Dissipation

9/23 Notes: Sequential Circuits

Sequential Circuits

Something that is unable to build yet:

• Memory stores current state
• Combinational logic computes:
  • Next state (from input + current state)
  • Output bits (from input + current state)
• State changes on LOAD control input

Memory: Using Feedback

Use feedback to maintain storage indefinitely

• Logic gates are built to restore marginal signal levels, so noise shouldn't be a problem

• Two end-points are stable
• Middle point is metastable

D Latch

A simple circuit that can hold state

• If C = 1, the value of Q holds
  • Latch is closed, ignores D input and preserves what last value Q had
• If C = 0, the value of D passes to Q (Transparent Mode)
  • Latch is open, Q = D

Sequential circuits using D latches is a terrible idea

• D goes to Q first

• Combinational logic stops being combinational

Memory should sample an instant, not an interval

Use two gates!

D Flip-Flop

Falling edge: 1 -> 0: it will stay the same

D Flip-Flop Timing

Setup Time: $t_{setup}$

• Minimum amount of time data input D must be stable and unchanging before the clock edge arrives

Hold Time: $t_{hold}$

• Minimum amount of time the data input D must be kept stable and unchanging after the clock edge has passed

Propagation Delay: $t_{pd}$

• Time it takes for output Q to show the new data value after clock edge has occurred

This is edge-trigged no longer level-sensitive

Next state is calculated, but only let through when the rising clock edge occurs

D Flip-Flop with Write Enable

How are Flip-Flops Initialized?

• When Reset = 1, flip flop is set to initial value regardless of value of EN
• When Reset = 0, then it behaves like a D flip-flop with enable

Synchronous Sequential Circuits

• All the D Flip-Flops use the same periodic clock signal
• Register: Group of DFFs
  • Stores multi-bit values
• Registers update their contents simultaneously, at the rising edge of the clock

• Synchronous sequential circuits: All state kept in registers driven by the same clock
• Allows discretizing time into cycles and abstracting sequential circuits as finite state machines (FSMs)
• FSMs can be described with state-transition diagrams or truth tables

Combination Lock

• A 1-bit input (“0” or “1”)
• A 1-bit output (“Unlock” signal)
• UNLOCK is 1 iff: last 4 inputs were the “combination”: 0110

• Mutually exclusive
  • Can't have two choices
• Collectively exhaustive
  • Every state must specify what happens for each possible input combination

Two Bit Counter

Single-clock Synchronous Circuits

• Between registers are combinational logic

Each logic gate takes a small amount of time to operate

• Signal must arrive at register `b' and be stable for a brief period (setup time) before the next clock tick arrives

Slowest path: critical path

• Hold time ($t_{hold}$) constraint of FF2 may be violated if $D_2$ changes too quickly
• Prop delay, the upper bound on time from valid inputs to valid outputs, does not help us analyze hold time!
• Contamination delay ($t_{CD}$) is the lower bound on time from which input-to-output transition

To fix setup constraint:

• Change the logic to be faster (lower $t_{PD}$)
• Change the clock to be slower (higher $t_{CLK}$)

Hold constraint (changing clk won't help)

• Changing the clock period will not fix violations.
• The sum of contamination delays must be greater than the register hold time, otherwise the circuit won't work.

Min clock period: maximum sum of the propagation delays plus setup time

9/25 Notes: FSMs

State Elements

• D Flip-Flop (DFF): State element that samples its input at the rising edge of the clock
  • DFF enhancements: write-enable circuit to optionally capture new input value
  • Reset circuit to set initial value
• Register: Group of DFFs
  • Stores multi-bit values

FSMs

• Synchronous sequential circuits: all state kept in registers driven by the same clock
• Allows discretizing time into cycles and abstracting sequential circuits as FSMs
• FSMs can be described with state-transition diagrams or truth tables

• Build large circuits from smaller ones
• Problem: Wiring up FSMs can introduce combinational cycles

Modules

• Minispec modules add some structure to FSMs to make them composable
• Modules separate the combinational logic to compute the outputs and the next state
  • Methods compute outputs
  • Rules compute next state
  • Methods and rules use separate input wires (method arguments vs rule inputs)

Two-Bit Counter in Minispec

Reg\#(T) Module

• Reg\#(T) is a register of values of type T
  • Eg Reg\#(Bool) or Reg\#(Bit\#(16)), not Reg\#(16)
• Register writes use a special register assignment operator: <=
  • Eg, count <= count + 1
• <= has two key differences from =
  • = assigns to variable immediately, <= updates register at the end of the cycle
  • Registers can be written at most once per cycle

Composing Modules

Module Components

1. Submodules, which can be registers or other user-defined modules to allow composition of modules
2. Methods produce outputs given some input arguments and the current state
3. Rules produce the next state and submodule inputs given some external inputs and the current state
4. Inputs represent external inputs controlled by the enclosing module

Strict hierarchical composition

1. Each module interacts only with its own submodules
2. Methods do not read inputs

Conditions enable:

• Impossible to get combinational cycles
• Very simple semantics: system behaves as if rules fire sequential, outside-in

Simulating and Testing Modules

• Modules can be simulated/tested with testbenches
  • Another module that uses the tested module as a submodule
  • Drives its inputs through a sequence of test cases
  • Checks that outputs are as expected
• System functions let testbench modules output results and control simulation
  • \$display to print output
  • \$finish to terminate simulation
  • System functions have no hardware meaning, are ignored when synthesized

Multi-Cycle Computations

Time is More Flexible Than Space

• Sequential circuits can implement more computations than combinational circuits
  • Variable amount of input and/or output
  • Variable number of steps
• Example: Build a circuit that adds two numbers of arbitrary length
  • Combinational: Can't, inputs/outputs must have fixed width
  • Sequential: Trivial, eg. add one bit per cycle:

GCD

• Euclid's algorithm efficiently computes the GCD of two numbers

• Takes a variable number of steps
• Approach: Build a sequential circuit that performs one iteration of the while loop per cycle

Circuit

General Recipe for Multi-Cycle Circuits

1. Specify circuit interface: Data inputs and outputs; also, control signals

• In GCD: a,b,result; start, isDone

1. Implement state elements: every value that spans multiple cycles needs to be in a register

• (x,y)

1. Implement combinational logic that performs all needed operations on register values

• (x==0, x>=y, x-y)

1. Implement a mux at the input of each register, and determine the possible values of each register case by case

• In GCD, four possible next values -> 4-input muxes

1. Derive the mux select signals; may require some combinational logic

• sel

1. Derive outputs

• Result, isDone

Designing Good Module Interfaces

GROUP RELATED INPUTS AND OUTPUTS

Maybe Type

• Maybe\#(T) represents an optional value of type T
  • Either Invalid and no value, or Valid and a value
• Possible implementation: A value + a valid bit

• Optional values are so common that Maybe\#(T) has a few built-in operations

Improved GCD

Summary

• Modules implement FSMs in a composable way
  • Extra structure to FSMs: Combinational logic split into rules (produce next state) and methods (produce outputs)
  • Clean hierarchical composition: No combinational cycles, system behaves as if rules execute outside-in
• Sequential circuits can implement more computations than combinational circuits
  • Variable amount of input and/or output
  • Variable number of steps
• To build simple, easy-to-use module interfaces, group related inputs and outputs

10/2 Notes: Introduction to Pipelining

Introduction to Pipelining

Performance Measures

Two timing metrics of interest when designing a system:

1. Latency: the delay from when an input enters the system until its associated output is produced
2. Throughput: The rate at which inputs or outputs are processed

The metric to prioritize depends on the application

• Airbag deployment system? Latency
• General-purpose processor? Throughput (maximize instructions/second)

Performance of Combinational Logic

Pipelined Circuits

Use registers to hold H's inputs stable!

2 stage pipeline:

• If we have valid input X during clock cycle j, H(X) is valid during clock j+2

Suppose F, G, H have propagation delays of 15, 20, 25 ns and we are using ideal registers ($t_{PD} = 0$, $t_{SETUP} = 0$):

Pipeline Conventions

Definition:

• A well-formed K-Stage Pipeline is an acyclic circuit having exactly K registers on every path from an input to an output
• Combinational circuit is thus a 0-stage pipeline

Composition convention:

• Every pipeline stage, hence every K-Stage pipeline, has a register on its output

Clock period: the clock must have a period $t_{CLK}$ sufficient to cover the longest register to register propagation delay plus setup time

Ill-Formed Pipelines

A Pipelining Methodology

• Step 1: draw a line that crosses every output in the circuit, and mark the endpoints as terminal points
• Step 2: Continue to draw new lines between the terminal points across various circuit connections, ensuring that every connection crosses each line in the same direction

• Replacing a slow combinational component with a k-pipe version may let us decrease the clock period
• Must account for new pipeline stages in our plan

Design Tradeoffs Introduction: Multiplier Case Study

Multiplication by repeated addition

Implementation of mi

Folded (Multi-Cycle) Multiplier

• Combinational circuit often have repetitive logic
  • N bit multiplier has N-1 adders
• Folded circuits use less combinational logic, reuse it over multiple cycles
  • Implement multiplication with one adder, taking   N cycles to perform the additions

10/7 Notes: Design Tradeoffs in Sequential Circuits

Design Tradeoffs in Sequential Circuits

Optimizing Hardware Design

• Throughput
• Latency
• Area of the design
• Power consumption
• Energy of executing a task

Design Alternatives

Benefits of Sequential Logic

• Sequential circuits can implement more computations than combinational circuits
  • Variable amount of input and/or output
  • Variable number of steps
• Sequential circuits allow more design tradeoffs
  • Pipelined circuits improve throughput by decreasing clock period and overlapping multiple computations
  • Multi-cycle/folded circuits reduce area by reusing a small amount of combinational logic over multiple cycles

Clock Frequency Constraints

• To analyze latency and throughput, we've assumed $t_{CLK}$ depends only on our circuit
  • Lower $t_{PD}$ -> lower $t_{CLK}$ -> lower latency & higher throughput
• In practice, other constraints may set $t_{CLK}$
  • Propagation delay of other circuits
  • Limits on power consumption
• When our own circuit is not limiting $t_{CLK}$, throughput and latency tradeoffs change
  • $t_{CLK,4stage}$ = $t_{CLK,2stage}$/2
    • Throughput: 2x, Latency: 1x
  • $t_{CLK,4stage}$ = $t_{CLK,2stage}$
    • Throughput: 1x, Latency: 2x

Increasing Throughput with Replication

• Increase throughput by replicating a circuit and using the copies in parallel

Pipeline or Replicate

• Consider these two multipliers

Factorial FSM

Control FSM for Factorial

Programming the Datapath

Use factorial datapath and change the control FSM to solve other problems:

• Multiplication
• Squaring

Limited Problems:

• Limited storage
• Limited set of operations, and inputs to those operations
• Limited inputs to the control FSM

Control FSM for Factorial

• ENIAC (1943): first general-purpose digital computer, programmed by setting huge array of dials and switches, reprogramming took about 3 weeks

Modern computers instead store programs in memory, coded as a sequence of instructions

10/9 Notes: Compilers and RISC-V Assembly

Compilers and RISC-V Assembly

Components of MicroProcessor

• 32 General Purpose Registers
• Each register is 32 bits wide
• x0 = 0

Memory:

• Each memory location is 32 bits wide (1 word)
  • Instructions and data
• Memory is byte (8 bits) addressable
• Address of adjacent words are 4 apart
• Address is 32 bits
• Can address $2^{32}$ bytes or $2^{30}$ words

RISC-V Instruction Types

• Computational Instructions executed by ALU
  • Register-Register: oper rd, rs1, rs2
  • Register-Immediate: oper rd, rs1, const
• Control flow instructions
  • Conditional br\_comp rs1, rs2, label
  • Unconditional jal rd, label and jalr rd, offset(rs1)
• Loads and Stores
  • lw rd, offset(rs1)
  • Sw rs2, offset(rs1)
• Pseudoinstructions
  • Shorthand for other instructions

RISC-V Stack

• Stack is in memory
• Stack grows down from higher to lower addresses
• sp points to top of stack (last pushed element)
• Push sequence:
  • addi sp, sp, -4 //allocate
  • sw a1, 0(sp)
• Pop sequence:
  • lw a1, 0(sp)
  • addi sp, sp, 4 //allocate
• Leave as you found it!

Compiling Procedures

• A calling convention specifies rules for register usage across procedures
• RISC-V calling convention gives symbolic names to registers x0-x31 to denote their role:

Callee: Saves callee-saved registers (sN) on stack before using them in a procedure. Must restore sN registers and stack before exiting procedure.

Compile Factorial to RISC-V

Anatomy of a Modern Compiler

• Read source program
• Break it up into basic elements
• Check correctness, produce errors
• Translate to generic intermediate representation (IR)

Synthesis (backend)

• Optimize IR
• Translate IR to ASM
• Optimize ASM

Frontend Stages

• Lexical analysis (scanning): Source -> List of tokens

• Syntactic analysis (parsing): Tokens -> Syntax tree

• Semantic analysis (type checking)

Intermediate Representation (IR)

• Internal compiler language that is
  • Language-independent
  • Machine-independent
  • Easy to optimize

• Why yet another language?
  • Assembly does not have enough info to optimize it well
  • Enables modularity and reuse

• Perform a set of passes over the CFG
  • Each pass does a specific, simple task over the CFG
  • By repeating multiple simple passes on the CFG over and over, compilers achieve very complex optimizations
• Example optimizations:
  • Dead code elimination: Eliminate assignments to variables that are never used, or basic blocks that are never reached
  • Constant propagation: Identify variables that are constant, substitute the constant elsewhere
  • Constant folding: Compute and substitute constant expressions

Control Flow Graph

• Assignments
  • x = a op b
• Basic block: sequence of assignments with an optional branch at the end
  • x = 3
  • y = x+7
  • if (x!=y)
• Control flow graph:
  • Nodes: basic blocks
  • Edges: jumps or branches between basic blocks

Code Generation

• Translate generated IR to assembly
• Register allocation: map variables to registers
  • If variables > registers, map some to memory, and load/store them when needed
• Translate each assignment to instructions
  • Some assignments may require > 1 instr if our ISA doesn't have op
• Emit each basic block: label, assignments, and branch or jump
• Lay out basic blocks, removing superfluous jumps
• ISA and CPU-specific optimizations
  • If possible, reorder instructions to improve performance

GCD

Modern Compilers

10/14 Notes: Single-Cycle Processor

Building a Single-Cycle RISC-V Processor

Von Neumann Model

• Main memory holds programs and their data
• Central processing unit accesses and processes memory values
• Input/output devices to communicate with the outside world

Stored-Program Computer

• Express program as a sequence of coded instructions
• Memory holds both data and instructions
• CPU fetches, interprets, and executes successive instructions of the program

• Instructions coded as binary data
• Program Counter or PC: Address of the instruction to be executed
• Logic to translate instructions into control signals for datapath

Instructions

• Instructions are the fundamental unit of work
• Each instruction specifies:
  • An operation or opcode to be performed
  • Source operands and destination for the result
• In a von Neumann machine, instructions are executed sequentially
  • CPU logically implements this loop: By default, the next PC is current PC + size of current instruction unless the instruction says otherwise

Instruction Set Architecture (ISA)

• ISA: The contract between software and hardware
  • Functional definition of operations and storage locations
  • Precise description of how software can invoke and access them
• ISA is a key layer of abstraction
  • ISA specifies what the hardware provides, not how it's implemented
  • Hides the complexity of CPU implementation
  • Enables fast innovation in hardware (no need to change software!)
    • 8086 (1978): 29 thousand transistors, 5 MHz, 0.33 MIPS
    • Pentium 4 (2003): 44 million transistors, 4 GHz, \textasciitilde5000 MIPS
    • 128-core Zen 5 (2024): \textasciitilde150 billion transistors, 4 GHz, \textasciitilde3M MIPS
  • Commercially successful ISAs last for decades
    • Today's x86 CPUs carry baggage of design decisions from the 70's

“Iron Law”

• Less Executed instructions (work/instruction)
• Less Cycles per instruction (CPI)
• Lower Cycle time

Nowadays, Simple single-cycle processor, executes one instruction from start to end each clock cycle

• CPI = 1, but low frequency
• Later: Pipelining to increase frequency

RISC-V ISA

Data Types

• 8-bit byte, 16-bit half-word, 32-bit word
• Integers are signed in 2's complement (default), or unsigned

Storage

• Processor
  • 32 general-purpose registers (x0 hardwired to 0)
  • Program counter (PC) holds address of current instruction
• Main memory: 32-bit byte addresses; accessed in words, half-words, or bytes; little-endian

Instruction types

• ALU: Two input registers, or register and immediate
• Loads and stores: Move data between registers and memory
• Control flow: Branches and jumps

All 32 bit

Incremental Featurism

We'll implement datapaths for each instruction class individually, and merge them (using MUXes)

Register File Timing

• RD1 reads “old” value of Reg{[}RA1{]} until next cycle
• The new value (WD) only becomes visible after the write completes

Reads are combinational, write are synchronous

Instruction Fetch/Decode

Use Program Counter (PC) to fetch the current instruction:

• Use PC as memory address
• Add 4 to PC, load new value at end of cycle
• Fetch instruction from memory

ALU Instructions

ALU with Immediate

Load and Store Instructions

Branch Instructions

Remaining Functions

Single-Cycle Processor

(a) PC (Program Counter)

• Holds the current instruction address.
• Updates to the next instruction address (nextPc) at the clock edge.
• Provides the address to Instruction Memory.

$\rightarrow$ The only piece of control state for instruction sequencing.

(b) Instruction Memory

• Takes pc and outputs the 32-bit instruction bits.
• Read-only during execution.
• Must be combinationally readable (i.e., returns instruction quickly, no clock needed), since you can't afford another cycle.

$\rightarrow$ Provides the opcode, register fields, and immediate to decode.

(c) Decode

• Extracts the instruction fields (rs1, rs2, rd, immediate, control bits).
• Generates control signals for multiplexers, ALU, memory enable, etc.
• No state — purely combinational.

$\rightarrow$ Translates instruction bits into control and data-flow signals.

(d) Register File

• Has 2 read ports (to get both operands in one cycle) and 1 write port (for the result at the end of the cycle).
• Read ports are combinational; write port updates at clock edge.

$\rightarrow$ Provides operands instantly; accepts result at end of cycle.

(e) Execute (ALU / branch logic)

• Performs all computation: arithmetic, comparisons, address calculation, branch targets.
• Takes in operands and immediate; outputs a result and branch decision.

$\rightarrow$ Handles the “compute” part of every instruction type.

(f) Data Memory

• Provides/accepts data for LOAD and STORE instructions.
• Has one read/write port; read is combinational, write on clock edge.

$\rightarrow$ Used only for memory access instructions, but must be physically present all the time (since all instructions share the same datapath).

(g) Write-back MUX

• Chooses what data goes back into the register file:
  • ALU result
  • Memory read data
  • PC + 4 (for jumps/links)
• Controlled by decode logic.

$\rightarrow$ Provides unified path to the single register file write port.

(h) Control paths

• Decode block generates all control signals (mux selects, enables, ALU function).
• Every datapath block acts combinationally within the same clock cycle.

10/16 Notes: Memory Hierarchy

Memory Hierarchy

Memory Technology

Static RAM (SRAM)

• Each wordline corresponds to one row of memory cells.
• Each bitline pair runs vertically through all rows in one column.
  • carry data in and data out for that bit position across all rows
• Address decoder
  • Activates exactly one wordline corresponding to that address.
• Drivers
  • Handle the write path.
• Sense Amplifiers
  • During a read, the selected row's cells slightly disturb the voltage on their bitlines

(6T) Cell:

• Two CMOS inverters (4 FETs) forming a bistable element
• Two access transistors

1. Drivers precharge all bitlines to Vdd (1), and leave them floating
2. Address decoder activates one wordline
3. Each cell in the activated word slowly pulls down one of the bitlines to GND (0)
4. Sense amplifiers sense change in bitline voltages, produce output data

SRAM Write

1. Drivers set and hold bitlines to desired values (Vdd and GND for 1, GND and Vdd for 0)
2. Address decoder activates one wordline
3. Each cell in word is overpowered by the drivers, stores value

Multiported SRAMs

• We can do multiple reads and writes with multiple ports by adding one set of wordlines and bitlines per port
• Cost/bit for N ports?
  • Wordlines: N
  • Bitlines: 2*N
  • Access FETs: 2*N

Wires dominate area

1T Dynamic RAM (DRAM) Cell

Problem: Capacitor leaks charge, must be refreshed periodically (  milliseconds)

DRAM Read and Write

• Writes: Drive bitline to Vdd or GND, activate wordline, charge or discharge capacitor
• Reads
  • Precharge bitline to Vdd/2
  • Activate wordline
  • Capacitor and bitline share charge
    • If capacitor was discharged, bitline voltage decreases slightly
    • If capacitor was charged, bitline voltage increases slightly
  • Sense bitline to determine if 0 or 1
• Issue: Reads are destructive!
  • Data must be rewritten to cells at end of read

Non-Volatile Storage: Flash

• Very dense: Multiple bits/transistor, read and written in blocks
• Slow (especially on writes), 10-100 us
• Limited number of writes: charging/discharging the floating gate (writes) requires large voltages that damage transistor

Non-Volatile Storage: Hard Disk

• Hard Disk: Rotating magnetic platters + read/write head
  • Extremely slow (\textasciitilde10ms): Mechanically move head to position, wait for data to pass underneath head
  • \textasciitilde100MB/s for sequential read/writes
  • \textasciitilde100KB/s for random read/writes
  • Cheap

Memory Overview

• Different technologies have vastly different tradeoffs
• Size is a fundamental limit, even setting cost aside:
  • Small + low latency, high bandwidth, low energy, or
  • Large + high-latency, low bandwidth, high energy
• Can we get best of both worlds? (large, fast, cheap)

Want large, fast, and cheap memory, but\ldots{}

• Large memories are slow (even if built with fast components)
• Fast memories are expensive

Approaches

Approach 1: Expose Hierarchy

• Registers, SRAM, DRAM, Flash, Hard Disk each available as storage alternatives
• Tell programmers: “Use them cleverly”

• Programming model: Single memory, single address space
• Machine transparently stores data in fast or slow memory, depending on usage patterns

Memory usages

• Memory accesses have two common properties:
  • temporal locality: If a location has been accessed recently, it is likely to be accessed (reused) soon
  • Spatial locality: If a location has been accessed recently, it is likely that nearby locations will be accessed soon

Cache

• Cache: A small, interim storage component that transparently retains (caches) data from recently accessed locations
• Processor sends accesses to the cache. Two options:
  • Cache hit: Data for this address in cache, returned quickly
  • Cache miss: Data not in cache
    • Fetch data from memory, send it back to processor
    • Retain this data in the cache (replacing some other data)
• Processor must deal with variable memory access time

Levels of Caches

Cache Metrics

Basic Cache Algorithms

Direct-Mapped Caches

• Each word in memory maps into a single cache line
• Access (for cache with 2W lines):
  • Index into cache with W address bits (the index bits)
  • Read out valid bit, tag, and data
• If valid bit == 1 and tag matches upper address bits, HIT

10/21 Notes: Cache

Cache

Memory Hierarchy Interface: Single memory, single address space

• Implementation: Machine transparently stores and moves data across fast or slow memories, depending on usage patterns

Basic Cache Algorithm

• Takes advantage of spatial locality
• Allows consecutive memory locations to live in the cache simultaneously
• Reduces likelihood of replacing data that may be accessed again in the near future

Block Size

• Take advantage of spatial locality: Store multiple
• words per data line
  • Words in a block come from consecutive memory locations
  • Fetch entire block from memory and replace entire cache line
  • Another advantage: Reduces size of tag memory!
  • Potential disadvantage: Fewer indices in the cache

4-block, 16-word direct-mapped cache

• Larger block sizes\ldots{}
  • Take advantage of spatial locality
  • Incur larger miss penalty since it takes longer to transfer the block from memory
  • Can increase the average hit time and miss ratio
• AMAT = HitTime + MissPenalty*MissRatio

Conflict Misses with Direct Map

Fully Associative Cache

Opposite extreme: Any address can be in any location

• No cache index!
• Flexible (no conflict misses)
• Expensive: Must compare tags of all entries in parallel to find matching one

N-way Set-Associative Cache

• Use multiple direct-mapped caches in parallel to reduce conflict misses
  • Nomenclature:
    • \# Rows = \# Sets
    • \# Columns = \# Ways
    • Set size = \#ways = “set associativity” (e.g., 4-way $\rightarrow$ 4 lines/set)
• Each address maps to only one set, but can be in any line within the set
• Tags from all ways are checked in parallel

Fully associative cache: Extreme case with a single set and as many ways as cache lines

Replacement Policies

• Optimal policy: Replace the line that is accessed furthest in the future
• Idea: Predict the future from looking at the past
  • If a line has not been used recently, it's often less likely to be accessed in the near future (a locality argument)
• Least Recently Used (LRU): Replace the line that was accessed furthest in the past
  • Need to keep ordered list of N items $\rightarrow$ N! Orderings
    • $\rightarrow$ $O(\log_2 N!)$ = $O(N \log_2 N)$ “LRU bits” + complex logic
  • Caches often implement cheaper approximations of LRU
• Others aren't as good
  • First-In, First-Out (least recently replaced)
  • Random: Choose a candidate at random

Write Policies

• Write-through: CPU writes are cached, but also written to main memory immediately. Memory always holds current contents
  • Simple, wastes bandwidth
• Write-back: CPU writes are cached, but not written to main memory until we replace the line. Memory contents can be “stale”
  • Faster, low bandwidth, more complex
  • Commonly implemented in current systems

Example: SW Cache Write-Hit

SB Cache Write-Hit

1. Tags don't match -> Miss
   1. D=1: Write cache line 1 (tag = 0x280: addresses 0x28010-0x2801C) back to memory
   2. If D=0: Don't need to write the line back to memory.
2. Load line (tag = 0x48: addresses 0x4810-0x481C) from memory
3. Write 0x09 to 0x4818 (block offset 2), set D=1.

Comparing Hit Rates

10/23 Notes: Pipelined Processors

Pipelined Processors

“Iron Law” of performance:

• Lower executed instructions
• Lower cycles per instruction
• Lower cycle time

Single-Cycle Processor Performance

• CPI = 1
• $t_{CLK}$ = longest path for any instruction

$t_{CLK} \approx t_{IMEM} + t_{DEC} + t_{RF} + t_{EXE} + t_{DMEM} + t_{WB}$

Pipelined Implementation

• Divide datapath into multiple pipeline stages to reduce $t_{CLK}$
  • Each instruction executes over multiple cycles
  • Consecutive instructions are overlapped to keep CPI around 1.0
• 5-stage pipeline:
  • Instruction Fetch Stage: maintains PC, fetches instruction and passes it to
  • Decode & Read Registers Stage: decodes instruction and reads source operands from register file, passes them to
  • Execute Stage: performs indicated operation in ALU, passes result to
  • Memory Stage: if it's a load, use input as the address, pass read data (or ALU result if not a load) to
  • Write-Back Stage: write result back into register file

$t_{CLK}$ = max\{$t_{IF}$ , $t_{DEC}$, $t_{EXE}$, $t_{MEM}$, $t_{WB}$\}

Processor has state: PC, Register file, Memories

• There are loops we cannot break!
  • To compute the next PC
  • To write result into the register file
• Can't produce a well-formed pipeline with what we know so far\ldots{}

Simplified Single-Cycle Datapath

• For now, nextPC = PC + 4
  • No branches or jumps
• Same register file appears twice in the diagram
  • Top: reads are combinational
  • Bottom: writes are clocked
• Magic memories
  • Loads are combinational
  • Return data in same clock cycle

$t_{CLK} \approx t_{IMEM} + t_{DEC} + t_{RF} + t_{EXE} + t_{DMEM} + t_{WB}$

Classic 5-Stage Pipeline Datapath

• Pipeline registers separate different stages
• Each stage services one instruction per cycle

Throughput = 1/ $t_{CLK}$ = 1 instr/cycle

CPI = 1

Better Performance

Classic 5-Stage RISC Pipeline with Clocked Memory Reads

• Pipeline registers separate different stages
• Each stage services one instruction per cycle
• For now, nextPC = PC+4 (no branches or jumps)
• Instruction and data memories have clocked reads

• Combinational (async) read: address$\rightarrow$data is a pure combinational path.
• Clocked (sync) read: address is sampled on a clock edge; data appears a cycle later.

• In Lab 4, instruction and data “magic” memories have combinational reads: reads complete in the same cycle

• From Lab 5 on, we will use memories with clocked reads: read data is available at the beginning of the next cycle

Data Hazard

• xor reads x11 on cycle 3, but addi does not update it until end of cycle 5 $\rightarrow$ x11 is stale!
• Pipeline must maintain correct behavior\ldots{}

A data value $\rightarrow$ Data hazard

The program counter $\rightarrow$ Control hazard

Plan of attack:

1. Design a 5-stage pipeline that works with sequences of independent instructions
2. Handle data hazards
3. Handle control hazards

Strategy 1: Stall. Wait for the result to be available by freezing earlier pipeline stages

Strategy 2: Bypass (aka Forward). Route data to the earlier pipeline stage as soon as it is calculated

Strategy 3: Speculate

• Guess a value and continue executing anyway
• When actual value is available, two cases
  • Guessed correctly $\rightarrow$ do nothing
  • Guessed incorrectly $\rightarrow$ kill & restart with correct value

Stalling

• In general, load & store hazards may be solved in the pipeline or in the memory system

Resolving Data Hazards by Bypassing

Bypass Logic

• Add bypass muxes to DEC outputs
• Route EXE, MEM, WB outputs to mux inputs
• Bypass value if destination register of instruction in EXE, MEM, or WB matches source register of instruction in DEC
  • No bypass for x0
• If multiple matches, use value from most recent instruction (EXE $>$ MEM $>$ WB)

Full vs Partial

• Bypasses are expensive
  • Lots of wires & large muxes
• May affect clock cycle time\ldots{}
  • But full bypassing is not needed! We can always stall
    • e.g., just bypass from EXE and WB
• With a fully bypassed pipeline, do we still need the stall signal?

Compilers Can Help

Compilers can rearrange code to put dependent instructions farther away

Example:

• Simple, wastes cycles, higher CPI

Strategy 2: Bypass. Route data to the earlier pipeline stage as soon as it is calculated

• More expensive, lower CPI
• Still needs stalls when result is produced after EXE stage
• Can use fewer bypasses & stall more often

More pipeline stages $\rightarrow$ More frequent data hazards

• Lower $t_{CLK}$, but higher CPI

10/28 Notes: Pipelined Processors: Data and Control Hazards

Pipelined Processors: Data and Control Hazards

Caches Cause Variable Memory Response Time

• Timing of clocked read assuming cache hit (returns data by next clock cycle)

• Timing of clocked read on cache miss. The cache will produce a stall signal, telling the pipeline to wait until the memory responds.

• Stall. Wait for the result to be available by freezing earlier pipeline stages
• Assume a 4-cycle miss penalty

Control Hazards

support for branch and jump instructions

Resolving Control Hazards with Speculation

• When EXE finds a jump or taken branch, it supplies nextPC and sets ANNUL=1
  • Writes NOPs in IF/DEC and DEC/EXE pipeline registers, annulling instructions currently in IF and DEC stages (called branch annulment)
  • Loads the branch or jump target into PC register

Interactions

• Stalling can address all pipeline hazards
  • Simple, but hurts CPI
• Bypassing improves CPI on data hazards
• Speculation improves CPI on control hazards
  • Speculation works only when it's easy to make good guesses

10/30 Notes: Operating Systems

Operating Systems

6.191 So Far: Single-User Machines

• Hardware executes a single program
• This program has direct and complete access to all hardware resources in the machine
• The ISA is the interface between software and hardware
• Most computer systems don't work like this!

Operating Systems

• Multiple executing programs share the machine
• Each executing program does not have direct access to hardware resources
• Instead, an operating system (OS) controls these programs and how they share hardware resources
  • Only OS has unrestricted access to hardware
• The application binary interface (ABI) is the interface between programs and the OS

Process vs Program

• Program is a collection of instructions (just the code)
• A process is an instance of a program that is being executed
  • Includes program code + state (registers, memory, and other resources)
• The OS Kernel is a process with special privileges

Goal of OS

• Abstraction: OS hides details of underlying hardware
  • Processes open and access files instead of issuing raw commands to the disk
• Resource management: OS controls how processes share hardware (CPU, memory, disk, etc)
• Protection and privacy: processes can not access each other's data

OS kernel provides a private address space to each process

• Each process is allocated space in physical memory by OS
• A process is not allowed to access memory of other processes

• Each process is given a fraction of CPU time
• A process cannot use more CPU time than allowed

Virtual Machines

The OS gives a Virtual Machine (VM) to each process

• Each process believes it runs on its own machine
• But this machine does not exist in physical hardware

• Very general concept, used beyond operating systems

VM are Everywhere

• Virtual machines can be implemented entirely in software, but at a performance cost
  • Python programs are 10-100x slower than native Linux programs due to Python interpreter overheads
• We want to support operating systems with minimal overheads -> need hardware support for virtual machines

ISA extensions to support OS

• Two modes of execution: user and supervisor
  • OS kernel runs in supervisor mode
  • All other processes run in user mode
• Privileged instructions and registers that are only available in supervisor mode
• Exceptions and interrupts to safely transition from user to supervisor mode
• Virtual memory to provide private address spaces and abstract the storage resources of the machine

Exceptions

• Exceptions usually refer to synchronous events, generated by the process itself (illegal instruction, divide-by-0, illegal memory address, system call)
• Interrupts usually refer to asynchronous events, generated by I/O devices (timer expired, keystroke, packet received, disk transfer complete)
• Use exceptions to encompass both types of events, and use synchronous exception for synchronous events

When an exception happens, the processor:

• Stops the current process at instruction $I_i$, completing all instructions up to $I_{i-1}$
• Saves the PC of instruction $I_i$ and the reason for the exception in special (privileged) registers
• Enables supervisor mode, disables interrupts, and transfer control to a pre-specified exception handler PC

After OS kernel handles the exception, it returns control to the process at instruction $I_i$

• Exceptions are transparent to the process!

If the exception is due to an illegal operation by the program that cannot be fixed (e.g. an illegal access), the OS aborts the process

Exception Use \#1: CPU Scheduling

• The OS kernel schedules processes into the CPU
  • Each process is given a fraction of CPU time
  • A process cannot use more CPU time than allowed
• Key enabling technology: Timer interrupts
  • Kernel sets timer, which raises an interrupt after a specified time‹

• No state is lost.
• No code dies.
• It is a pause forced by the OS to maintain fair CPU sharing.
• It is not an error, not a fault, not a time exception.

Exception Use \#2: Emulating Instructions

• mul x1, x2, x3 is an instruction in the RISC-V `M' extension (x1 <- x2*x3)
  • If `M' is not implemented, this is an illegal instruction
• Run code on RV32IM machine on a RV32I machine is an illegal instruction exception

• Result: Program believes it is executing in a RV32IM processor, when it's actually running in a RV32I
  • Any drawbacks? Much slower than a hardware multiply

Exception Use \#3: System Calls

• The OS kernel lets processes invoke system services (eg. access files) via system calls

• Processes invoke system calls by executing a special instruction that causes an exception
  • ecall in RISC-V

Types of System Calls

• Accessing files (sys\_open/close/read/write/\ldots)
• Using network connections (sys\_bind/listen/accept/\ldots)
• Managing memory (sys\_mmap/munmap/mprotect/\ldots)
• Getting information about the system or process (sys\_gettime/getpid/getuid/\ldots)
• Waiting for a certain event (sys\_wait/sleep/yield\ldots)
• Creating and interrupting other processes (sys\_fork/exec/kill/\ldots)
• \ldots{} and many more!

Programs rarely invoke system calls directly. Instead, they are used by library/language routines

• Some of these system calls may block the process!

Process Life Cycle: The Full Picture

• OS maintains a list of all processes and their status \{ready, executing, waiting\}
  • A process is scheduled to run for a specified amount of CPU time or until completion
  • If a process invokes a system call that cannot be satisfied immediately (e.g. a file read that needs to access disk), it is blocked and put in the waiting state
  • When the waiting condition has been satisfied, the waiting process is woken up and put in the ready list

Exceptions in RISC-V

• RISC-V provides several privileged registers, called control and status registers (CSRs)
  • mepc: exception PC
  • mcause: cause of the exception (interrupt, illegal instr, etc)
  • mtvec: address of the exception handler
  • mstatus: status bits (privilege mode, interrupts enabled, etc)
• RISC-V also provides privileged instructions, e.g.
  • csrr and csrw to read/write CSRs
  • mret to return from the exception handler to the process
  • Trying to execute these instructions from user mode causes an exception -> normal processes can't take over the system

• ecall instruction causes an exception, sets mcause CSR to a particular value
• ABI defines how process and kernel pass arguments and results
• Typically, similar conventions as a function call:
  • System call number in a7
  • Other arguments in a0-a6
  • Results in a0-a1 (or in memory)
  • All registers are preserved (treated as callee-saved)
    • except the ABI-designated return registers (at least a0).

11/4 Notes: Virtual Memory

Virtual Memory

Goals of OS:

• Protection and privacy: Processes cannot access each other's data
• Abstraction: Hide away details of underlying hardware
  • e.g., processes open and access files instead of issuing raw commands to hard drive
• Resource management: Controls how processes share hardware resources (CPU, memory, disk, etc.)

Key enabling technologies:

• User mode + supervisor mode
• Exceptions to safely transition into supervisor mode
• Virtual memory to abstract the storage resources of the machine

Virtual Memory Systems

Illusion of a large, private, uniform store

• Protection & Privacy
  • Each process has a private address space
• Demand Paging
  • Use main memory as a cache of disk
  • Enables running programs larger than main memory
  • Hides differences in machine configuration

Names for Memory Locations

• Virtual Address
  • Address generated by the process
  • Specific to the process's private address space
• Physical Address
  • Address used to access physical (hardware) memory
  • Operating system specifies mapping of virtual addresses into physical addresses

Segmentation (Base-and-Bound) Address Translation

• Each program's data is allocated in a contiguous segment of physical memory
• Physical address = Virtual Address + segment Base
• Bound register provides safety and isolation
• Base and Bound registers should not be accessed by user programs (only accessible in supervisor mode)

Separate Segments for Code and Data

• Prevents a buggy program from overwriting code
• Enables multiple processes to share code segment

Memory Fragmentation

Paged Memory Systems

• Divide physical memory in fixed-size blocks called pages
  • Typical page size: 4KB
• Interpret each virtual address as a pair < virtual page number, offset>
• Use a page table to translate from virtual to physical page numbers
  • Page table contains the physical page number (starting physical address) for each virtual page number

Private Address Space per Process

• Each process has a page table
• Page table has an entry for each process page

Paging vs. Segmentation

Paging:

• Fixed-size pages.
• No external fragmentation.
• Possible internal fragmentation.
• Fast, index-based translation.
• Ubiquitous in modern OSes.

Segmentation:

• Variable-size segments.
• External fragmentation.
• No internal fragmentation.
• Base+offset translation.
• Logical protection and sharing.

Suppose Page Tables reside in Memory

1. Use PT Base Reg + VPN to index the page table. That lookup is a DRAM read to fetch the physical page number.
2. Use the physical page number + offset to read the target word. That is a second DRAM access.

Demand Paging (using main memory as cache of disk)

• All the pages of the processes may not fit in main memory
  • Therefore, DRAM is backed up by swap space on disk
• Page Table Entry (PTE) contains:
  • A resident bit to indicate if the page exists in main memory
  • PPN (physical page number) for a memory-resident page
  • DPN (disk page number) for a page on the disk
  • Protection and usage bits
• Even if all pages fit in memory, demand paging allows bringing only what is needed from disk
  • When a process starts, all code and data are on disk; bring pages in as they are accessed

If resident=0: the PTE's number is a DPN. No physical frame is assigned. Any access triggers a page

Virtual -> Physical Translation

Caching vs Demand Paging

Page Faults

• An access to a page that does not have a valid translation causes a page fault exception
• OS page fault handler is invoked, handles miss:
  • Choose a page to replace, write it back if dirty. Mark page as no longer resident
  • Read page from disk into available physical page
  • Update page table to show new page is resident
  • Return control to program, which re-executes memory access

Translation Lookaside Buffer (TLB)

Problem: address translation is very expensive! Each reference requires accessing page table

Solution: Cache translations in TLB

• TLB hit -> single-cycle translation
• TLB miss -> access page table to refill TLB

TLB and Page Table

TLB Designs

• Typically 32-128 entries, 4 to 8 way set-associative
  • Modern processors use a hierarchy of TLBs
    • Eg: 128-entry L1 TLB + 2K-entry L2 TLB
• Switching processes is expensive because TLB has to be flushed
  • Modern processors include process ID in TLB entries to avoid flushing
• Handing a TLB miss: look up the page table (aka “walk” the page table). If the page is in memory, load the VPN-> PPN translation in the TLB. o/w cause a page fault
  • Page faults are always handled in software
  • But page walks are usually handled in hardware using a memory management unit (MMU)
    • RISC-V, x86 access page table in hardware

Address Translation

Summary

• Virtual memory benefits:
  • Protection and privacy: Private address space per process
  • Demand paging: Can use main memory as a cache of disk
• Segmentation: Each process address space is a contiguous block (a segment) in physical memory
  • Simple: Base and bound registers
  • Suffers from fragmentation, no demand paging
• Paging: Each process address space is stored on multiple fixed-size pages. A page table maps virtual to physical pages
  • Avoids fragmentation
  • Enables demand paging: pages can be in main memory or disk
  • Requires a page table access on each memory reference
• TLBs make paging efficient by caching the page table

11/6 Notes: Virtual Memory 2

Virtual Memory 2

Goals of Virtual Memory

• Protection: processes cannot access each other's data
• Abstract storage resources of the machine

Lecture

• Translation Lookaside Buffers (TLB)
• CPU caches and virtual memory
• Hierarchical page tables
• Page caches and page sharing

• Page faults are always handled in software
• But page walks are usually handled in hardware using a memory management unit (MMU)
  • RISC-V, x86 access page table in hardware

Using Cache with Virtual Memory

• Two processes can have the same virtual address (for example, both map a stack at 0x7fff\ldots).
  • each process has its own page table
• If the cache stores data by virtual address alone, the hardware cannot tell which process the entry belongs to.

Virtually Indexed, Physically Tagged Cache (VIPT)

1. A virtual address splits into {[}VPN \textbar{} page-offset{]}.
2. The TLB needs the VPN to produce the PPN.
3. The cache index is chosen from the page-offset bits. These bits reach the cache immediately.
4. The cache reads the indexed set and extracts the tag in parallel with the TLB lookup.
5. When the TLB finishes, you have the physical page number. Concatenate {[}PPN \textbar{} page-offset{]} to form the physical address's tag.
6. Compare this physical tag with the tag read from the cache set to decide hit or miss.

Problem: Linear Page Table Size

• With 32-bit addresses, 4 KB pages & 4-byte PTEs:
  • $2^{20}$ PTEs, i.e., 4 MB page table per process
  • We often have hundreds to thousands of processes per machine\ldots{} use GBs of memory just for page tables?
• Use larger pages?
  • Internal fragmentation (not all memory in page is used)
  • Larger page fault penalty (more time to read from disk)
• What about a 64-bit virtual address space?
  • Even 1MB pages would require $2^{44}$ 8-byte PTEs (35 TB!)
• Solution: Use a sparse data structure to store page table
  • Page table size proportion to memory used, not address space
  • Most common solution: Trees -> Hierarchical page tables

Hierarchical Page Table

• Page table memory is proportional to amount of memory used by process
  • Assume process uses 8MB of virtual memory (contiguous)
  • 8MB/4KB = $2^{11}$ pages
  • Memory usage:
    • Best case: 2 entries in L1, each pointing to an L2 page table that stores 1024 ($2^{10}$) physical page numbers -> 2 * 4KB = 8KB
    • Total of 12KB
    • Compared to 4MB

A two-level page table represents all $2^{20}$ possible PTEs, but it only stores one always-allocated L1 table and then allocates L2 tables only for regions the process actually uses. So the full space exists logically, but only a small fraction is materialized in memory.

Cons

• Each page table walk needs multiple memory accesses
  • But TLBs make page table walks rare

Page Cache

• So far, we have seen using disk only as swap space
  • But disks mainly store data in files, which users can read and write\ldots{} how does the OS manage these files?

• OS caches files in main memory, in pages
  • Provides faster access to recently accessed files
  • Speeds up writes: writes to files are kept in dirty pages in main memory, written back to disk in bulk
  • Page cache reuses virtual memory mechanisms

Mapping Files to Process Memory

• Processes can use syscalls to read and write data from files into their own private memory
  • open/read/write/close syscalls
• Processes can also map files to virtual memory directly, using the mmap() syscall
  • No copies
  • Maps file pages directly from page cache

Page Sharing and Memory Mapping

• Multiple processes can map same file to their virtual memory
  • Commonly used to share code, files
  • Processes can also map shared read-write memory pages, enabling them to communicate through main memory

Shared Memory

• When processes want to communicate using a shared memory, doing this through a file is inefficient
  • Writes are also propagated to disk!
• OS allows processes to create shared memory regions
  • Managed as files (so they can have a name & reuse same interfaces, like mmap)
  • But these files are not stored on disk, only in main memory

Summary

• TLBs make paging efficient by caching the page table
• Hierarchical page tables make page table memory proportional to the amount of memory used by process
• Page caches enable using main memory to accelerate operations on files
• Page sharing avoids needless memory copies, enables fast inter-process communication

11/13 Notes: Exceptions and I/O

Exceptions and I/O

Implementing Exceptions

Review: exceptions

Exceptions: Events that need to be processed by the OS kernel. The event is usually unexpected or rare

RISC-V Exception Handling

• RISC-V provides several privileged registers, called control and status registers (CSRs), e.g.,
  • mepc: exception PC
  • mcause: cause of the exception (interrupt, illegal instr, etc.)
  • mtvec: address of the exception handler
  • mstatus: status bits (privileged mode, interrupts enabled, etc.)
• RISC-V also provides privileged instructions, e.g.,
  • csrr and csrw to read/write CSRs
  • mret to return from the exception handler to the process
  • Trying to execute these instructions from user mode causes an exception -> normal processes cannot take over the machine

Exceptions in the Pipeline

• On an exception, need to:
  • Save current PC in mepc
  • Save the cause of the exception in mcause
  • Set PC with the exception handler
• Exceptions cause control flow hazards!
  • They are implicit branches
• Want precise exceptions:
  • All preceding instructions must have completed
  • Instruction causing exception and future instructions must not have executed (no updates to register or memory)
  • Simple in single-cycle machines, more complex with pipelining

When Can Exceptions Happen?

• Memory fault (e.g., illegal memory address)
• Illegal instruction (e.g., emulating divide)
• Arithmetic exception (e.g., divide by zero)
• Memory fault (e.g., illegal memory address)

Instructions following the one that causes the exception may already be in the pipeline\ldots{}

• BUT none has written registers or memory yet

Handling Control Hazards due to Exceptions

• Instructions may suffer exceptions in different pipeline stages
• Must prioritize exceptions from earlier instructions, i.e., deeper in the pipeline

• When any stage flags an exception, that stage becomes the faulting instruction.

• All younger stages must be flushed. Each “Kill X Stage” signal does this.

• All older stages are allowed to complete normally so that the machine state reflects execution up to but not including the faulting instruction.

• The PC is replaced with the handler address.

• The faulting instruction's PC goes to EPC, and the exception type goes to Cause.

Resolving Exceptions

If an instruction has an exception at stage i

• Kill instructions in stages i-1, \ldots, 1 (flush the pipeline)
• Set PC to be the exception handler

Commit happens only in WB.

Typical Exception Handler Structure

• A small common handler (CH) written in assembly + many exception handler (EHs), one for each cause (typically written in normal C code)
• Common handler is invoked on every exception:
  • Saves registers x1-x31, mepc into known memory locations
  • Passes mcause, process state to the right EH to handle the specific exception/interrupt
  • EH returns which process should run next (could be the same or a different one)
  • CH loads x1-x31, mepc from memory for the right process
  • CH executes mret, which sets pc to mepc, disables supervisor mode, enables interrupts

Implementing I/O

• The system has shared I/O registers that both the processor and the I/O devices can read and write
• Key questions?
  • How to access I/O registers?
  • How do processors and device coordinate on each transfer?

• Option 1: Use special instructions
  • Eg. in and out instructions in x86
  • Inflexible, adds instructions -> used rarely
• Option 2: Memory-mapped I/O (MMIO)
  • I/O registers are mapped to physical memory locations
  • Processor accesses them with loads and stores
  • These loads and stores should not be cached!

Coordinating I/O Transfers

• Option 1: Polling (synchronous)
  • Processor periodically reads the register associated with a specific I/O device
• Option 2: Interrupts (asynchronous)
  • Processor initiates a request, then moves to other work
  • When the request is serviced, the I/O device interrupts the processor
• Pros of each approach?
  • Polling is simple
  • Interrupts let processor do useful computation while request is serviced but each transfer is less resource efficient

Polling-based I/O

• Consider a simple character-based display
• Uses one I/O register with the following format:

• The ready bit (bit 31) is set to 1 only when the display is ready to print a character
• When the processor wants to display an 8-bit character, it writes it to char (bits 0-7) and sets the ready bit to 0
• After display has processed the character, it sets ready bit to 1

Interrupt-based I/O

• Consider a simple keyboard that uses a single I/O register with a similar format:

• On a keystroke, the keyboard writes the typed character in char, sets full bit to 1, and raises a keyboard interrupt
• Interrupt handler reads char and sets full bit to 0, so keyboard can deliver future keystrokes
• This works fine because the keyboard is very slow compared to the CPU. Faster devices use more sophisticated mechanisms (e.g., network cards write packets to main memory and use I/O registers only to indicate status of transfer)

11/18 Notes: Synchronization

Synchronization

Thread-Level Parallelism

• Divide computation among multiple threads of execution
  • Multiple independent sequential threads which compete for shared resources such as memory and I/O devices
  • Multiple cooperating sequential threads, which communicate with each other
• Communication models:
  • Shared memory:
    • Single address space
    • Implicit communication by memory loads & stores
  • Message passing:
    • Separate address spaces
    • Explicit communication by sending and receiving messages

Synchronization

• Need for synchronization arises whenever there are parallel processes in a system
  • Forks and Joins: a parallel process may want to wait until several events have occurred
  • Producer-Consumer: a consumer process must wait until the producer process has produced data
  • Mutual Exclusion: Operating system has to ensure that a resource is used by only one process at a given time

Thread-safe programming

• Multithreaded programs can be executed on a uniprocessor by timesharing
  • Each thread is executed for a while (timer interrupt) and then the OS switches to another thread, repeatedly
• Thread-safe multithreaded programs behave the same way regardless of whether they are executed on multiprocessors or a single processor

Synchronous Communication

FIFO (First-In First-Out) Buffers

rcv() can be invoked before any send()

Semaphores (Dijkstra, 1962)

Programming construct for synchronization:

• New data type: semaphore, an integer >= 0

semaphore s = K;

• New operations
  • wait(semaphore s) -> wait until s > 0, then s = s-1
  • signal(semaphore s) -> s = s+1
    • One waiting thread may now be able to proceed
• Semantic guarantee: a semaphore s initialized to K enforces the precedence constraint:

Semaphore for Precedence

Semaphore for Resource Allocation

Abstract problem:

• Pool of K resources
• Many threads, each needs resource for occasional uninterrupted period
• Must guarantee that at most K resources are in use at any time

Solution:

FIFO Buffer w Semaphores: still not correct

Simultaneous Transactions

For certain code segments, called critical sections, we would like to ensure that no two executions overlap

• This constraint is called mutual exclusion

Solution: embed critical sections in wrappers that guarantee their \ul{atomicity} (make them appear to be single, instantaneous operations)

Issue: lock granularity

• One lock for all accounts?
• One lock per account?
• One lock for all accounts ending in 004?

Producer/Consumer Atomicity Problems

Consider multiple producer threads:

FIFO Buffer w Semaphores

Synchronization: The dark side

Naive use of synchronization constraints can introduce its own set of problems, particularly when a thread requires access to more than one protected resources

Conditions for Deadlock

1. Mutual Exclusion: only one thread can hold a resource at a given time
2. Hold-and-wait: a thread holds allocated resources while waiting for others
3. No preemption: a resource can not be removed from a thread holding it
4. Circular wait

Solution: Avoidance -or- Detection and Recovery

Person that then grabs the highest stick will be able to eat

SOLUTION

Summary

Communication among parallel threads or asynchronous processes requires synchronization

• Precedence constraints: a partial ordering among operations
• Semaphores as a mechanism for enforcing precedence constraints
• Mutual exclusion (critical sections, atomic transactions) as a common compound precedence constraint
• Solving Mutual Exclusion via binary semaphores
• Synchronization serializes operations, limits parallel execution

Many alternative synchronization mechanisms exist!

Deadlock:

• Consequence of undisciplined use of synchronization mechanism
• Can be avoided in special cases, detected and corrected in others

But how do we guarantee mutual exclusion in these particular critical sections without using semaphores?

• Use a special instruction (e.g., “test and set”) that performs an atomic read-modify-write. Depends on atomicity of single instruction execution. This is the most common approach.

11/20 Notes: Cache Coherence

Cache Coherence

Multicores

• Modern microprocessors usually have 2 to 8 cores where each core has a private cache for performance
• Cores can be used cooperatively to speed up an application
• Cores communicate with each other via memory

Cache Coherence Avoids Stale Data

• Need to provide the illusion of a single shared memory
• Problem:

• Solution: A cache coherence protocol controls cache contents to avoid stale lines
  • Eg, invalidate core 0's copy of A before letting core 2 write to it

Maintaining Coherence

• In a coherent memory all loads and stores can be placed in a global order
  • Multiple copies of an address in various caches can cause this property to be violated
• This property can be ensured if:
  • Only one cache at a time has the write permission for an address
  • No cache can have a stale copy of the data after a write to the address has been performed

Snooping-Based Coherence {[}Goodman 1983{]}

Processor

• Executes instructions. Issues load and store requests with an address and optional data. It does not know about coherence.

Cache

• Sits between processor and bus. Handles load/store. Holds some blocks of memory. Maintains a per-line state (Valid or Invalid in your simple protocol). Issues bus transactions when required.

Shared Memory

• Holds the full data. Updated by bus writes. Read by bus reads.

Bus

• A shared communication medium. Only one transaction at a time. All caches see every transaction in the same order. That is what “broadcast and totally ordered” means.

• Bus provides serialization point (this order is the coherence order)
  • Broadcast, totally ordered
  • Each cache controller “snoops” all bus transactions
  • Controller updates state of cache in response to processor and snoop events and generates bus transactions
• Snoopy protocol (FSM)
  • One FSM per cache
    • Each cache contains many cache lines. Every line has a coherence state (M, E, S, I for MESI). Instead of treating the whole cache as one big state machine, each line has its own small finite-state machine (FSM). So a 32 KB cache with 512 lines has 512 independent MESI machines.
  • State-transition diagram
  • Actions

• Assumes write-through caches and no-write allocate

• Rule 1. Write-through
  • A write always updates memory on the bus. The cache never holds a dirty copy. So there is no Modified state. A line is either Valid (clean) or Invalid.
• Rule 2. No-write-allocate
  • A write that misses does not bring the block into the cache. The cache does not allocate a line for a write miss.

Observe the control flow:

1. Processor talks only to its cache.
2. The cache decides whether to hit or miss.
3. If needed, the cache sends a transaction on the bus.
4. All caches observe that transaction and update coherence state.
5. Memory is updated or accessed depending on transaction type.

LD is local for core 1 too

ST issues BusWr -> makes Core 1 invalid

Issues?

• Every write updates main memory
• Every write requires broadcast & snoop

create high traffic and high latency

Modified/Shared/Invalid (MSI) Protocol

• Each line in each cache maintains MSI state:
  • I - cache doesn't contain the address
  • S - cache has the address but so may other caches; hence it can only be read
  • M - only this cache has the address; hence it can be read and written
    • Any other cache that had this address got invalidated

S (Shared): this core has a clean copy; other caches may also have it; memory is up to date.

I (Invalid): this core has no usable copy.

BusWB

• write the dirty, most-up-to-date data back to memory (or directly to the requester)
• BusRdX is only a request for exclusive ownership, not actual write data

YOU issue a PrWr while in S or I $\rightarrow$ you send BusRdX.

Someone ELSE issues BusRdX $\rightarrow$ you must invalidate.

Improvement over V/I:

• In M, the cache has exclusive and dirty data.
  • V/I doesnt have dirty state
  • Writes are local, so don't need write-through on every store
• MSI has S, so multiple clean readers don't fight
• Memory bandwidth is no longer bottleneck as writeback only occurs when dirty data must leave M

Cache Interventions

• MSI lets cache serve writes without updating memory, so main memory can have stale data
  • Core 0's cache needs to supply data
  • But main memory may also respond!
• Cache must override response from main memory

MSI Optimizations: Exclusive State

• Observation: Doing read-modify-write sequences on private data is common
  • Problem with MSI?
    • 2 bus transactions for every read-modify-write of private data
• Solution: E state (exclusive, clean)
  • If no other sharers, a read acquires line in E instead of S
  • Writes silently cause E-> M (exclusive, dirty)

Directory-Based Coherence

• Route all coherence transactions through a directory
  • Tracks contents of private caches -> No broadcasts
• Can scale more effectively than broadcast-based protocols

Implementing Cache Coherence

• Coherence protocols must enforce two rules:
  • Write propagation: Writes eventually become visible to all processors
  • Write serialization: Writes to the same location are serialized (all processors see them in the same order)
• How to ensure write propagation?
  • Write-invalidate protocols: Invalidate all other cached copies before performing the write
  • Write-update protocols: Update all other cached copies after performing the write
• How to ensure write serialization?
  • Snooping-based protocols: All caches observe each other's actions through a shared bus
  • Directory-based protocols: A coherence directory tracks contents of private caches and serializes requests

11/25 Notes: Parallel Processing

Parallel Processing

• A computational approach that divides a problem into smaller tasks, which can then be processed in parallel across multiple processing units (ALUs, cores, servers)
• Very general concept, exploited at different granularities
  • Instruction-level parallelism (ILP)
  • Data-level parallelism (DLP)
  • Thread-level parallelism (TLP)
• All modern systems heavily rely on parallelism to achieve high performance

Application Requirements Increased

• Programs have evolved from simple computations to complex, large scale applications
  • Parallelism -> Application property

• Scientific simulations (climate modeling, molecular dynamics)
• ML and generative AI (training deep neural networks, ChatGPT)
• Distributed cloud applications (websearch, social networks, databases, etc.)
• Image and video processing (rendering, compression, etc.)

Parallel Processing Granularities

• Different granularities depending on the unit that is processed in parallel

Instruction-Level Parallelism

• Independent instructions within a program can be executed in parallel

B is accessed down columns, which destroys spatial locality

• No, need to handle values of N that are not multiples of unrolling factor with final cleanup loop
  • Will stop early and leave 1-3 elements unprocessed

Unrolling pros & cons?

• Pros: Fewer branches & bookkeeping instructions (e.g., indexing) ILP can be exploited more easily (less hardware)
• Cons: larger code

Matrix Multiplication

• Matrix multiplication time (N=4096): 17.0s (1.17x faster)
  • 59.9B cycles
  • 258B instructions (1.46x better)
  • 4.3 instructions/cycle (1.25x worse)

Data-Level Parallelism

• In conventional ISAs, each instruction manipulates a single piece of data (arithmetic, memory, etc.)
• Many application classes apply the same operations across different data elements
  • ML, images/video processing, graphics, gaming, etc.
• Exploit with Vector/SIMD instructions (single instruction multiple data)
  • Apply the same operation to multiple data elements
  • Common extension in modern processors:
    • Vector registers of a maximum width (e.g., 64 elements)
    • Instructions to operate on vectors in one step

Vector Code Example

ld.v v1, 0(a4) loads 16 elements of a into vector register v1.

ld.v v2, 0(a5) loads 16 elements of b into v2.

add.v v3, v1, v2 adds element-wise across all 16 lanes.

st.v v3, 0(a6) stores 16 results to x.

• One instruction fetch and control stream on the left.
• Multiple parallel execution lanes in the middle.
• Each lane has its own slice of the register file and its own ALU.
• All lanes receive the same opcode at the same time.
• Each lane operates on a different element of the vector.

Vector Processing Implementations

• Advantages of vector ISAs:
  • Compact: 1 instruction defines N operations
  • Parallel: N operations are (data) parallel and independent
  • Expressive: Memory operations describe regular patterns
• Modern CPUs: vector extensions & wider registers
  • SSE (1999): 128-bit operands (4x32-bit or 2x64-bit)
  • AVX (2011): 256-bit operands (8x32-bit or 4x64-bit)
  • AVX-512 (2017): 512-bit operands
  • Explicit parallelism, extracted at compile time (vectorization) or manually (SIMD/SIMT programming)

• Vector speedup does not come from a single “vector length” hardware load. It comes from increasing useful work per instruction and matching the compute width to memory behavior.
• Memory can remain the bottleneck. If you double vector width but do not increase memory bandwidth or improve locality, speedup can be marginal.

Shift to Multicore

• Main avenue to improve performance since 2005 is to increase cores per processor

Multithreading Frameworks

• Pthreads: a C library for creating and managing POSIX threads
• OpenMP: an API for C, C++, and Fortran to support parallel programming using a shared-memory model

Matrix Multiplication w pthreads

Amdahl's Law

• Speedup = $\text{time}_{\text{without enhancement}}$ / $\text{time}_{\text{with enhancement}}$
• Suppose an enhancement speeds up a fraction f of a task by a factor of S

A Modern CPU

• 64 cores/processor
• High emphasis on ILP: 3.5GHz, 6-wide cores
  • Many complex mechanisms to achieve high performance on a single thread
• 256-bit vectors (8 32-bit elements)
• Lightly multithreaded: 2 threads/core (SMT)

NVIDIA H100

• 144 cores at 1.8GHz
• Vector cores with \textasciitilde32 lanes (1024 bits)
• Highly multithreaded: 64 threads/core
• 60MB L2 cache, 3.3 TB/s high-bandwidth memory
• Peak throughput: 67 FP32 TFLOP/s (vs. 6 TFLOP/s for AMD 64-core CPU)

What are Locality?

Locality: reuse of same or neighboring addresses by a program

• Temporal locality: reuse of the same memory location (instructions or data)
• Spatial locality: use of neighboring memory locations (instructions or data)
• Loop reordering, loop tiling

Optimizing Locality: Loop Reordering

• Caches designed to take advantage of data locality
  • Cache lines > 1 word (amortize cost of main memory access)
• However, code is not always structured to take advantage of the program's inherent locality
  • Especially crucial with parallel code (little memory bandwidth per core)
• Loop Reordering: change the order of loop iterations to leverage cache's spatial locality $\rightarrow$ Reduce cache misses

Optimizing Locality: Loop Tiling

• What if the data is much larger than the cache size?
  • Data in cache will be evicted before reuse -> cache misses ↑
  • e.g., B is much larger than cache size
• Loop tiling: Partition the loop iteration space
  • Fit elements accessed in inner loops into cache
  • Data stays in the cache until it is reused

• Parallelism allows computation to execute simultaneously improving performance
• Different granularities of parallelism (ILP, DLP, TLP)
• Different hardware techniques to take advantage of each
  • High-performance cores (ILP)
  • Vector/SIMD (DLP)
  • Multicore and multithreaded processors (TLP)
  • Modern systems rely on these techniques differently, depending on their target domain (e.g., CPUs vs GPUs)
• Minimizing data movement is especially important on parallel processors (loop tiling, reordering)