Cross Cutting Aspects

Performance

• performance: amount of useful work accomplished by a system, estimated in terms of accuracy, efficiency and speed; assessed with different metrics based on which aspect is profiled
• measuring execution time (time): wall clock time vs. CPU time
  • wall clock / elapsed time: total time spent (including I/O, time spent blocked or sleeping, OS scheduling...)
  • CPU time: time spent where the CPU is active (excluding I/O, time spent blocked or sleeping, OS scheduling...), split into user time (program code) and system time (kernel work / OS services)
    

Terminology

• Performance = \frac{1}{Execution Time}$Performance = \frac{1}{Execution Time}$
• clock cycle: single cycle of a hardware clock
• clock period / clock cycle time: length of a clock cycle (in ms, ns, µs...)
  • ClockPeriod=\frac1{ClockRate}$ClockPeriod=\frac1{ClockRate}$
• clock rate / clock frequency: number of cycles per second (in Hz / MHz (10⁶) / GHz (10⁹))
  • ClockRate=\frac1{ClockPeriod}$ClockRate=\frac1{ClockPeriod}$
  • 1 GHz \equiv$\equiv$ 1 ns
• cycles per instruction (CPI): average number of cycles per instruction of a program
  • CPI = \frac{\#Cycles}{\#Instructions}$CPI = \frac{\#Cycles}{\#Instructions}$ (total)
    
• ExecutionTime=\#Cycles \;\cdot\; ClockPeriod=\frac{\#Cycles}{ClockRate}$ExecutionTime=\#Cycles \;\cdot\; ClockPeriod=\frac{\#Cycles}{ClockRate}$
  • alternatively: ExecutionTime=\#Instructions\;\cdot\;CPI\;\cdot\;ClockPeriod=\frac{\#Instructions \;\cdot\; CPI}{ClockRate}$ExecutionTime=\#Instructions\;\cdot\;CPI\;\cdot\;ClockPeriod=\frac{\#Instructions \;\cdot\; CPI}{ClockRate}$

Dynamic and Static Energy

• dynamic (switching) energy: energy consumed when transistors switch states (no switching \to$\to$ 0)
  • energy: E_{dynamic} = \alpha \cdot C \cdot V²$E_{dynamic} = \alpha \cdot C \cdot V²$
    • \alpha$\alpha$: activity factor (not important for this discussion)
    • C$C$: load capaticance (how much current can flow?)
    • V$V$: supply voltage
  • power: P_{dynamic} = \alpha \cdot C \cdot V² \cdot f$P_{dynamic} = \alpha \cdot C \cdot V² \cdot f$
    • f$f$: clock frequency
• static (leakage) energy: energy consumed when circuit is idle (no transistor switching)
  • energy: E_{static} = P_{leakage} \cdot t$E_{static} = P_{leakage} \cdot t$
    • P_{leakage}$P_{leakage}$: leakage power
    • t$t$: time the circuit is powered

Parallelism

• task: some operation with inputs and outputs
  • task system: set of tasks with a dependence relation solving a given problem
  • concurrent tasks: two tasks are called concurrent if they are not dependent on each other (thus, could be executed at the same time)
  • simultaneous / parallel tasks: two tasks are executed in parallel if, at some point, both tasks have been started and have not terminated yet
• parallel computer: computer executing concurrent tasks in parallel

Parallel Metrics (p processors)

• speedup: Speedup(p) = \frac{Performance(p)}{Performance(1)}$Speedup(p) = \frac{Performance(p)}{Performance(1)}$ (ideal: p$p$ times)
  • scientific computing: Performance=\frac{Work}{Time}$Performance=\frac{Work}{Time}$
  • Speedup(p)=\frac{Time(1)}{Time(p)}$Speedup(p)=\frac{Time(1)}{Time(p)}$
• evaluation: strong vs. weak scaling
  • strong scaling: increase number of processors, keep total problem size fixed
  • weak scaling: increase number of processors, increase total problem size proportionally
• efficiency: Efficiency(p) = \frac{Speedup(p)}p$Efficiency(p) = \frac{Speedup(p)}p$ (ideal: 100\%$100\%$)

Memory Hierarchy

• temporal locality: addresses accessed recently will be accessed again in the near future with high probability
• spatial locality: addresses near to recently accessed addresses will be accessed in the near future with high probability

Fault Tolerance, Reliability, Availability

• fault: defect of a system that may cause an error (may be dormant)
  • internal fault: component fault (e.g. manufacturing defect)
  • external fault: propagated failure of another component or from outside the system (e.g. cosmic particles)
  • physical fault: hardware-related
  • design fault: either hardware- or software-related (e.g. illegal while loop condition)
  • interaction fault: caused by the environment (e.g. illegal input of system operator, radiation hitting system...)
• error: illegal system state; manifestation of a fault; can be propagated through a system, generating other errors (e.g. faulty memory bit flips)
• failure: error becomes observable at system's output \to$\to$ system behavior that is inconsistent with its specification (e.g. wrong calculation value, crash...)
  

• state sequence: correct states, tolerated error states (invisible), failure states

  • Correct State \xrightarrow{\text{Fault Action}}$\xrightarrow{\text{Fault Action}}$ Tolerated Error State
  • Correct State \xrightarrow{\text{Fault Action}}$\xrightarrow{\text{Fault Action}}$ Failure State
  • Tolerated Error State \xrightarrow{\text{Recovery Action}}$\xrightarrow{\text{Recovery Action}}$ Correct State
  • Tolerated Error State \xrightarrow{\text{Fault / Correct Action}}$\xrightarrow{\text{Fault / Correct Action}}$ Failure State
  • Failure State \xrightarrow{\text{Correction of Controlled Failure}}$\xrightarrow{\text{Correction of Controlled Failure}}$ Correct State
    

• fault tolerant system: a system that never enters a failure state (through error detection, error analysis and recovery)

• fail-controlled system: a system that can recover from a failure through special protocols

• fault prevention: methods preventing faults from being incorporated into a system (e.g. coding standards, firewalls, radiation shields...)

• fault removal: techniques to eliminate faults during design and development process

  • validation: are we building the right product? (check specification)
  • verification: are we building the product right? (prove that system complies with specification)
  • debugging: triggered by errors or failures \to$\to$ identify and remove faults

• reliability: probability that a system is free up failures up to a certain time (e.g. 1 hour, 1 day...)

• safety: probability that the system is operating correctly or will fail in a safe manner at a certain time (e.g. traffic lights)

• availability: percentage of planned operation time in which the system is available

Virtualization

• virtualization: the creation of a virtual version of something (e.g. hardware platform, operating system, peripheral...)
• virtual machine: virtualization of a computer through a virtual machine monitor (hypervisor), which can run multiple VMs at the same time and is responsible for distributing the real resources to those VMs
  • bare-metal: on top of hardware
  • hosted: inside a host OS
  • OS-level: containers, sharing kernel of host OS
• techniques: issue with handling privileged instructions...
  • full virtualization: OS unchanged
  • paravirtualization: OS changed
  • hardware-assisted: orthogonal mode of CPU operation (VM vs. hypervisor modes)

Processor Classes

• general purpose processors: can execute any program, not restricted / specialized to certain application classes
• network processors: designed for packet processing, optimized for processing a large number of incoming and outgoing packets through multiple packet processing engines (PPEs) (e.g. Intel Tofino 2)
  • P4: programming language for network processors; protocol-independent (i.e. no native support for IP, etc.)
• embedded processors (microcontrollers): application-specific, cheap, optimized for low power consumption, used in SoC (e.g. Intel 8051)

Parallel Architectures

• SIMD: single instruction multiple data; synchronized execution of same instruction on a set of data
• MIMD: multiple instruction multiple data; async. execution of different instructions
  • distributed memory: nodes with separate / private physical address spaces; message-based communication
  • shared memory: shared address space; communication through R/W to global addresses
    • UMA: uniform memory access; all processors share a single, centralized memory, and every processor has the same access latency
    • NUMA: non-uniform memory access; memory is physically distributed across processors / CPU sockets, so access time differs (local faster than remote)
      

Instruction Set Architecture

• ISA: defines the capabilities of the processor for the programmer
  • binary compatibility: two processors are binary compatible if they support the same ISA
• datatypes and formats: integers (of different lengths), fixed and floating point numbers, characters (and strings), bits
• operands: defines number of operands for an instruction (0-3), types of operands (immediate, register, memory), data alignment (n$n$-byte boundary = address multiple of n$n$)
• addressing modes
  • immediate: operand is part of instruction (e.g. mov rax, 3)
  • register: operand is in a register; register address given (e.g. mov rax, rbx)
  • direct: memory address is part of the instruction (e.g. mov rax, [0x123456789ABCDEF0])
  • register indirect: memory address is in a register (e.g. mov rax, [rbx])
  • indexed, displacement: register indirect plus fixed offset (e.g. mov rax, [rbx + 16])
• instructions: data transfer (e.g. mov), arithmetic and logic (e.g. add), control flow (e.g. jmp), I/O (e.g. in), system level instructions (e.g. int)
  • format: structured in opcode and operand; may be single format or multiple formats
• register: fast memory on the processor with short addresses (register number)
  • register types: general registers (e.g. r9), floating point registers (e.g. st0), special registers (e.g. rcx for loop control), system registers (e.g. rip)
  • register file: set of registers
  • sliding window register file: CPU register organization technique that supports fast function calls by giving each function its own logical set of registers, while physically sharing a single large register file
    • on function call, slide the window to a new set of registers (internally)
• execution modes: system mode vs. user mode
  • system mode: access to all components, reserved for OS
  • user mode: limited access, no direct memory access, no direct I/O access, no access to control registers
• exception: software interrupt (e.g. arithmetic error, privileged instructione executed in user mode...), handled by OS (saves processor state, jumps to handler, executes in supervisor mode, returns to original instruction in user mode)
  • precise exception: all previous instructions have been terminated, all subsequent instructions have not been executed
  • imprecise exception: exception can occur out-of-order
• interrupt handling: handled in the same way as exceptions; interrupts allow the processor to handle external async. signals

CISC vs. RISC

• complex instruction set computer (e.g. IA32, x86-64...)
  • variable instruction format (e.g. between 1 and 16 bytes for x86)
  • memory and register operands
  • specialized instructions
  • shorter program binaries, more flexible
• reduced instruction set computer (e.g. ARM, RISC-V)
  • single instruction format (fixed width, e.g. 32 bit)
  • load/store architecture (special instructions for moving data between memory and registers)
  • limited addressing modes
  • faster, requires emulating complex instructions (internally: CISC \to$\to$ RISC)

Instruction Pipelining

• instruction cycle: fetch \to$\to$ decode \to$\to$ execute \to$\to$ memory access \to$\to$ write back
  • instruction fetch (IF): fetch instruction from memory into instruction register and increment PC
  • instruction decode (ID): decode instruction and fetch register operands from register file
  • execute (EX): perform ALU operation; compute address for load / store operations
  • memory access (MA): read or write to / from memory in case of load / store; potentially replace PC (in case of branching / jumps)
  • write back (WB): write result back to register file
• pipelining: dividing incoming instructions into a series of sequential steps performed by different processor units with different parts of instructions processed in parallel
  • pipeline stage: a step in the instruction cycle (i.e. fetch, decode, execute...), each implemented by own hardware
  • pipeline register: special register placed inbetween each pipeline stage to hold intermediate data and control information, to be passed as input to the next stage; for synchronisation purposes (see connection to clock)
  • speedup: K$K$ pipeline stages, N$N$ instructions \implies$\implies$ \frac{K\cdot N}{N+K-1} \to K$\frac{K\cdot N}{N+K-1} \to K$
  • +: higher throughput
  • -: slowest stage defines throughput, higher latency (all instructions have to go through all stages, even MA for non-memory instructions, and all stages take the same time), more complex control logic
    
    
• superscalar processor: a type of CPU that can execute more than one instruction per clock cycle by having multiple execution units

Pipeline Hazards

• pipeline hazard: the pipeline cannot execute the next instruction in the following clock cycle as planned and might lead to wrong results
  • structural (resource) hazard: insufficient hardware resources to support all concurrent stages (e.g. same memory used for IF and MA)
    • solution: duplicate resources (e.g. separate memories for instructions and data), pipeline stall
  • data hazard: instruction depends on result of a previous instruction that has not yet completed (e.g. RAW add r1,r2,r3; sub r4,r1,r5 // depends on r1)
    • solution: forwarding (bypassing), pipeline stall, instruction reordering
  • control hazard: due to branch / jump instructions, where the next instruction to fetch depends on a currently unknown decision (e.g. conditional branch)
    • solution: branch prediction, pipeline stall

Data Dependencies

// read-after-write (RAW): true dependency
// instruction needs a value that a previous instruction will write
add r1, r2, r3 // writes r1
sub r4, r1, r5 // reads  r1

// write-after-read (WAR): anti-dependency
// instruction writes to a location that a previous instruction still needs to read
sub r2, r3, r4 // reads  r3
add r3, r5, r6 // writes r3

// write-after-write (WAW): output dependency
// two instructions write to the same location, and the order of the writes matters
add r1, r2, r3
sub r1, r4, r5

// read-after-write (RAW): true dependency
// instruction needs a value that a previous instruction will write
add r1, r2, r3 // writes r1
sub r4, r1, r5 // reads  r1

// write-after-read (WAR): anti-dependency
// instruction writes to a location that a previous instruction still needs to read
sub r2, r3, r4 // reads  r3
add r3, r5, r6 // writes r3

// write-after-write (WAW): output dependency
// two instructions write to the same location, and the order of the writes matters
add r1, r2, r3
sub r1, r4, r5

• true dependencies (RAW): cannot be removed with register renaming
• name dependencies (WAR, WAW): can be removed with register renaming
• independent instructions: can be reordered and executed in parallel

Data Dependency Solutions

• static solutions (software): implemented by the compiler
  • NOP insertion: insertion of NOPs after instructions that may lead to hazards
  • instruction reordering: execution of independent instructions between dependent instructions
• dynamic solutions (hardware): stalling / interlocking, fowarding, forwarding with interlocking
  • interlocking (stalling): automatically stalls the pipeline when a data hazard is detected
    
  • forwarding (bypassing): allows the processor to send a result directly from one pipeline stage to a later stage without waiting for write-back (data taken from pipeline registers)
    
  • forwarding with interlocking (bypassing with stalling): forwarding used wherever possible, otherwise interlocking (e.g. load-use hazards where data is not yet available, load r1,0(r2); add r3,r1,r4)
    

Control Hazards

• computing in decode phase: use an additional ALU in the decode phase to compute condition and target (longer critical path, may cause RAW)
• delay slot: one or more instructions immediately following a branch are always executed, regardless of whether the branch is taken or not
  • idea: compiler fills stall cycle with an independent instruction that is always executed, no matter the branch outcome

add r1,r2,r3       ...
...            ->  ...
br addr            br addr
nop                add r1,r2,r3   // delay slot, always executed!

add r1,r2,r3       ...
...            ->  ...
br addr            br addr
nop                add r1,r2,r3   // delay slot, always executed!

• branch prediction: speculative execution of instructions dependent on the predicted outcome
  1. predict whether a branch is taken or not
  2. fetch subsequent instructions based on prediction
  3. if prediction is correct, continue execution with no penalty
  4. if prediction is wrong, flush pipeline and restart execution on correct path
• static branch prediction: fixed beforehand, does not change at runtime
  • hardware: assume backwards branches are always taken (imagine loops)
  • software (compiler): specify via bit in jump opcode, guided by profiling / program analysis
• dynamic branch prediction: during runtime, takes jump history into account
  • branch prediction buffer: cache for information about conditional jumps, storing address tag (hash, quick to compute) and prediction bit (0: not taken, 1: taken)
  • single-bit predictor: bit set? \to$\to$ branch predicted to be taken; if prediction is wrong, invert bit
    • suboptimal for nested loops, there will always be a misprediction in the first iteration of the inner loop
      
  • two-bit predictor: requires two mispredictions to switch
    • 00: strongly not taken
    • 01: weakly not taken
    • 10: weakly taken
    • 11: strongly taken
      
  • two-bit predictor with saturation: instead of directly going from weakly taken / weakly not taken to strongly not taken / strongly taken, do it progressively
    
    • correlation predictor: base prediction on history of other preceding jumps
      • (m,n)-predictor: use history of last m$m$ jumps to select one of 2^m$2^m$ n$n$-bit predictors (depending on the outcome of the last jumps; all combos, hence 2^m$2^m$)
      • branch history register (BHR): store global history of last m$m$ jumps (bits determine if jump was taken), shift outcome into BHR after each jump; BHR gives index into pattern history table (PHT)

// correlation predictor example
if (aa == 2)  { aa = 0; }
if (bb == 2)  { bb = 0; }
if (aa != bb) { ... } // we know the outcome of this based on the previous 2 ifs

// correlation predictor example
if (aa == 2)  { aa = 0; }
if (bb == 2)  { bb = 0; }
if (aa != bb) { ... } // we know the outcome of this based on the previous 2 ifs

• branch target buffer (BTB): specialized cache in the CPU used to speed up the fetching of instructions after a branch
  • purpose: we can decide whether to take a branch or not (if we don't, the next instruction is sequentually after the branch instruction); but if we need to branch, calculating the target address can take extra cycles and stall the pipeline; we want to avoid stalling
  • contains: branch instruction address (PC), target address, prediction bits (optional)
  1. when fetching an instruction, check BTB
     1. PC matches BTB entry \to$\to$ fetch predicted target instruction
     2. PC doesn't match BTB entry \to$\to$ fetch next sequential instruction (assume not taken)
  2. when resolving the branch, update the BTB with correct target and prediction
     

Pipelining in Modern Processors

Fetch

• fetch unit: 4 step pipeline, one fetch every cycle
  • next fetch address instruction: gather possible branch target addresses (from multiple branch predictors), return addresses (from return address stack) and next address in sequential order
  • fetch address calculation: decide upon instruction address
  • instruction cache access: access I-Cache and I-TLB for getting the instruction itself
  • instructions drive to decode stage: align instruction and send to decode stage
• branch target buffer: decide for each instruction in the block if it is a branch, and if so, possibly what type (conditional, call, return) and the target address
  
• branch aliasing: because branch predictors need to be fast and efficient, the instruction address is typically hashed / truncated, which may lead to multiple addresses for different branches pointing to the same entry in the BTB \to$\to$ performance impact
  
• correlation predictor: 10 to 20 bit history (BHR) combined with PC to form a hash which is then used as an index into PHT
  • hash: typically bitwise OR between least significant bits of PC and BHR
    
• hybrid branch predictor (tournament predictor): no single predictor works best for all branches, so use another predictor (selector) to select which predictor to use (learns throughout execution)
  

// hybrid branch predictor example
if (x > 0)  ... // A: predictable per-branch   -> local wins
if (y == x) ... // B: correlated with branch A -> global wins 

// hybrid branch predictor example
if (x > 0)  ... // A: predictable per-branch   -> local wins
if (y == x) ... // B: correlated with branch A -> global wins 

• return address stack (RAS): small, specialized hardware stack used by modern CPUs to predict the return target of function calls accurately (stack-like, i.e. LIFO)
  • motivation: using a BTB alone would not work if we call some function B() from inside multiple different functions A(), C(), D()..., because the BTB could by design only store one target return (jump) address (i.e. only one of A(), C(), D()...)
  • call site: push address of next instruction onto stack
  • return: pop topmost address (take as prediction)
  • bad for recursive functions

Decode

• decoding: input is a raw stream of bytes, output is a series of control signals
• RISC: fixed instruction length \to$\to$ easy to identify and separate instructions and operands, enables programmable logic arrays (PLAs) with small lookup tables
  
• CISC: way more complicated \to$\to$ translation of CISC to a RISC-like instruction format (e.g. add [eax], ebx becomes something like load r0,ds:[eax]; add r1,r0,ebx; store ds:[eax],r1)
  
  • instruction length decoder (ILD): marks instruction boundaries after identifying prefixes, MODRM, immediates etc.
  • dynamic translation unit (DTU): translates instructions into smaller micro-operations
  • loop stream detector: detects a loop with some small number of micro-ops, buffers the micro-ops and replays them directly every iteration, skipping the fetch and decode stages (until the back-branch is no longer taken)

Rename / Allocation

• allocation: reorder buffer, issue queue, load / store queue
• register renaming: name dependencies resolved by using a larger set of physical registers (PRs) compared to architectural registers (ARs, what's visible in the ISA)
  • merged register file: use a single register file for storing speculative and commited values; each physical register is either free or allocated; free registers stored in free list
    • register map table (RMT): stores for each AR the latest PR assigned to it
    • instruction renamed? input registers looked up in RMT and IDs are replaced; output register replaced with ID of new PR
    • no PR available? stall instruction
  • write to AR: select new PR and update AR \to$\to$ PR mapping
  • read from AR: replace AR by current PR to which it is mapped
  • freeing PR: either if it was written and no further instruction reads it (hard to decide, since the CPU doesn't know instructions further into the future) or when the next instruction commits that writes to the same architectural register (i.e. value overwritten, so we don't need the old one anymore)
    
    
• reorder buffer (ROB): buffer for preserving program order
  1. when an instruction is decoded / renamed, a ROB entry is created representing the future destination of the instruction
  2. source operands are either read from the ARs (if unmodified) or values in previous ROB entries (if younger instructions wrote to the same register)
  3. instruction writes result to ROB entry
  4. ROB commits in program order, ROB entry is freed
     

Issue / Dispatch

• issue: instructions are issued to the functional units
  • functional unit: a piece of hardware (e.g. ALU, FPU, L/SU...) that receives an input, performs a defined operation on it and produces a result that may be written back to a register or forwarded to another unit
• in-order (static) instruction scheduling: instructions are issued to the functional units in program order; check oldest non-executed instruction and issue it when all operands and the functional unit are available

div  f0,  f2, f4 // A
add  f10, f0, f8 // B: blocked by A
load f12, f8, 10 // C: independent, but still cannot be executed because we need to respect program order

div  f0,  f2, f4 // A
add  f10, f0, f8 // B: blocked by A
load f12, f8, 10 // C: independent, but still cannot be executed because we need to respect program order

• out-of-order (dynamic) instruction scheduling: instructions may be executed out of program order
  • Tomasulo's algorithm: algorithm based on the concept of reservation stations for OoO scheduling (implicit renaming)
  • reservation station: buffer that holds an issued instruction along with its operands; results are directly forwarded via the result bus to other functional units that require the data
  • unified issue queue: centralized space holding instructions, regardless of functional unit
  • distributed issue queue: somewhere between Tomasulo and UIQ
    

• issue queue allocation: allocation, data ready, write data stages
  • allocation: renaming / allocation of issue queue entry, get data availability info
  • data ready: read available data from register file and write ready flag and source operand IDs to issue entry
  • write data: write available data into issue entry
• instruction wakeup: broadcasts from completing instructions that indicate operand availability, enabling dependent instructions in the issue queue to become ready for execution
  1. wakeup: match IDs
  2. select: select next instruction fom ready instructions for execution
  3. drive: forward information to execution unit
  4. execution: execute instruction
  • early wakeup signal: wakeup signal is sent earlier; only possible for fixed execution latencies (i.e. no memory operations) (can be made speculative or kept conservative)
    
    
• arbiter / scheduler: selects instruction(s) to be sent to execution stage
• issue width: number of instructions that can be issued in one cycle
• entry reclamation: once the instruction is selected and its data forwarded, its issue queue entry can be reclaimed
• operand read: read before issue vs. read after issue
  • read before issue: read operands before instructions are put into the issue queue (preferred due to less register ports and ease of handling commits), requires temporary registers in the issue queue to store operands; operands that are not yet available are later inserted via bypass network
    • +: less read ports required for register file since data may come from bypass network or ROB
    • -: additional registers required in issue queue
  • read after issue: read operands when the instruction is issued to a functional unit (issue queue only stores identifiers of source registers)
    • +: no additional registers in issue queue
    • -: more read ports required for register file; commit handling requires more effort (issue queue has to be searched for ROB entry reference(s), which must then be replaced by the architectural register)
    • handling limited number of register ports: active / reactive scheme
      • active: arbiters synchronize; if not enough read ports are available, cancel issuing of instructions
      • reactive: arbiters assume there are enough read ports; issued instructions are cancelled later and need to be reissued
    • separating register files: replicated / distributed register files
      • replicated register files: copies
      • distributed register files: clustering of entire execution path; instructions can only access data within their own register files; requires explicit communication mechanism between
• memory disambiguation: mechanism in charge of handling memory dependences
  • total ordering: every single memory operation happens in the exact order it appears in the code
  • load ordering with store ordering: loads can jump ahead of stores, but loads must stay in order relative to other loads
  • partial ordering: loads can execute whenever they want, provided they do not violate any data dependency
  • store ordering: speculate that a load won't conflict with any previous store and run it immediately

// memory ambiguity
store [r3], r4       //           problem:
load  r1  , [r2]     // RAW?      we don't know yet where [r3], [r2] and [r6] point to...
store [r6], r1       // WAR? WAW? ... it could be that [r3] == [r2] == [r6]
add   r3  , r1  , r7

// memory ambiguity
store [r3], r4       //           problem:
load  r1  , [r2]     // RAW?      we don't know yet where [r3], [r2] and [r6] point to...
store [r6], r1       // WAR? WAW? ... it could be that [r3] == [r2] == [r6]
add   r3  , r1  , r7

Execute

• execution of instructions: the architectural state is only updated in the commit stage; in the write-back stage, results are forwarded from functional units to intermediate storage (merged register file, ROB)
  
• bypass network: new data path dominated by wires and multiplexers used to forward data directly to a consuming instruction, bypassing the write-back stage
  • +: increased IPC
  • -: increased cycle time and power consumption
  • clustering: because bypassing increases complexity, it is only available within clusters (e.g. FPUs are clustered and data from a FPU cannot go to an integer ALU)
    

Commit

• commit stage: stage where instructions are officially completed and their results are made permanent in the architectural state
• retire register file (RRF): used alongside ROB; contains the architectural register values corresponding to committed instructions only
  • read after issue: instructions already in the "issue queue" must be checked; their pointers to a temporary ROB ID must be converted into pointers to the permanent architectural register ID in the RRF
  • read before issue
    • new instructions: simply fetch the data directly from the RRF
    • existing instructions: either already have the data from a previous ROB entry or received it via a "wakeup signal" when the result was first generated
      
• merged register file: no ROB, nothing to be done (value stays in the same physical register it was originally assigned to)
  • reclamation: physical register is only freed if another instruction commits that writes the same architectural register

Recovery from Branch Misprediction

• front-end recovery: flushing intermediate buffers, restoring branch predictor history, updating program counter
  • goal: stop fetching the wrong path
• back-end recovery: removing instructions residing in any buffer (e.g. memory disambiguation buffers, issue queue, ROB etc.); restoring the renaming table; physical registers and issue queue entries etc. should be reclaimed
  • goal: undo execution and free resources
  • ROB/RRF: recovery only starts once all instructions up to the (mispredicted) branch instructions are commited (\to$\to$ RRF represents state after branch instruction)
    • renaming table entries now point to registers in RRF
  • merged register file: doesn't wait until mispredicted branch commits; instead, uses "log" of changes to renaming table (for each write, log architectural register \leftrightarrow$\leftrightarrow$ assigned physical register) to recover correct state
• exceptions: handled at commit time because the instruction should not be a speculative instruction and because we need the exact architectural state before the execution of the instruction
  1. flush all in-flight instructions: clear out all instructions (younger than offending instruction) currently in pipeline
  2. recover architectural state: restore registers and memory
  3. redirect front-end to first address of exception hander: update PC to point to address of exception handling routine

Compiler Support

• improved instruction scheduling: self-explanatory
  • requires dependence analysis and symbolic optimization
• loop unrolling (factor k$k$): replicate loop body k$k$ times (with adapted accesses to loop variables and loop control)
  • always possible
• register allocation with graph coloring: the compiler starts with an unlimited number of virtual registers; in order to map these to (limited) architectural registers, it uses graph coloring
  • method: nodes are virtual registers, edges are inserted between nodes (virtual registers) if their lifetimes overlap
  • goal: minimal graph coloring \to$\to$ number of colors needed is number of architectural registers
    
• software pipelining: loops are restructured, such that in each iteration of the new loop different instructions of different iterations of the original loop are executed

Software Pipelining

LOAD  0
ADD   0  LOAD  1
STORE 0  ADD   1 LOAD  2
         STORE 1 ADD   2
                 STORE 2
LOAD 0
---
ADD   0
LOAD  1
---
STORE 0
ADD   1
LOAD  2
---
STORE 1
ADD   2
---
STORE 2

Software Pipelining

LOAD  0
ADD   0  LOAD  1
STORE 0  ADD   1 LOAD  2
         STORE 1 ADD   2
                 STORE 2
LOAD 0
---
ADD   0
LOAD  1
---
STORE 0
ADD   1
LOAD  2
---
STORE 1
ADD   2
---
STORE 2

• loop fusion: combines subsequent loops with the same loop control (not always possible!)

do i = 1, n
  a(i) = b(i) + 2                do i = 1, n
enddo                      ->      a(i) = b(i) + 2
                           ->      c(i) = d(i+1) * a(i)
do i = 1, n                      enddo
  c(i) = d(i+1) * a(i)
enddo

do i = 1, n
  a(i) = b(i) + 2                do i = 1, n
enddo                      ->      a(i) = b(i) + 2
                           ->      c(i) = d(i+1) * a(i)
do i = 1, n                      enddo
  c(i) = d(i+1) * a(i)
enddo

Caches

• goal: keep frequently accessed data in a small, fast memory nearby
  • required: program locality (temporal, spatial
• cache: invisible to the application, organized in cache lines (32 B - 128 B, loaded entirely at once)
  • hierarchy: lower level \to$\to$ smaller, but faster; higher level \to$\to$ larger, but slower
    
    • inclusive caches: all addresses in lower levels are included in higher levels
      • otherwise, they are considered exclusive caches
        • +: increased effective cache size
        • -: increased coherence / cache management complexity
  • tag array: stores tag and valid bits
  • data array: stores cache line data

Cache Mapping

• fully associative mapping: memory block can be placed anywhere in cache; entire cache is searched at once in parallel to potentially find corresponding address
  • idea: decompose address into block ID (upper bits, used as tag in cache) and word ID (lower bits, column index), use block ID as tag (index) in cache to find corresponding cache line, then use word ID as "offset" to find which data to return
    • entry found? return from cache, no need to access memory
    • no entry found? fetch data (line) from memory and insert cache (line) entry
      • no space? use a replacement algorithm
  • +: lowest number of conflict misses
  • -: expensive to implement

Address:
+------------+----+
| bbbbbbbbbb | ww |
+------------+----+

Example:
0x43F -> 0100 0011 11|11 -> idx. 0 (just inserted?), column 11 (4th) -> 0x12
0x5D2 -> 0101 1101 00|10 -> idx. 1 (just inserted?), column 10 (3rd) -> 0xFA

Cache:
+--------------+----+----+----+----+
|      Tag     | 00 | 01 | 10 | 11 |
+--------------+----+----+----+----+
| 0100 0011 11 | AB | CD | EF | 12 |
| 0101 1100 00 | 53 | 91 | FA | B2 |
|      ...     | .. | .. | .. | .. |
+--------------+----+----+----+----+

Address:
+------------+----+
| bbbbbbbbbb | ww |
+------------+----+

Example:
0x43F -> 0100 0011 11|11 -> idx. 0 (just inserted?), column 11 (4th) -> 0x12
0x5D2 -> 0101 1101 00|10 -> idx. 1 (just inserted?), column 10 (3rd) -> 0xFA

Cache:
+--------------+----+----+----+----+
|      Tag     | 00 | 01 | 10 | 11 |
+--------------+----+----+----+----+
| 0100 0011 11 | AB | CD | EF | 12 |
| 0101 1100 00 | 53 | 91 | FA | B2 |
|      ...     | .. | .. | .. | .. |
+--------------+----+----+----+----+

• direct mapping: every block of main memory maps to exactly one speciific cache line; no need to search the entire cache, just look at the corresponding line (by ID); no replacement algorithm needed (conflict? throw it out)
  • idea: decompose address into tag, line ID (determined by how many cache lines there are) and word ID (same as fully associative); for any address, it goes in the line determined by the line ID
    • line empty? insert cache line
    • line filled with correct tag? use that
    • line filled with other tag? evict it
  • +: fast, cheap (no replacement algorithm needed, no need to check entire cache)
  • -: very high probability of thrashing occuring

Address:
+---------+-----+----+
| bbbbbbb | lll | ww |
+---------+-----+----+

Example:
0x35C -> 0011 010|1 11|00 -> line 111, column 00 -> 0x3C

Cache:
    +----------+----+----+----+----+
    |    Tag   | 00 | 01 | 10 | 11 |
    +----------+----+----+----+----+
000 |    ...   | .. | .. | .. | .. |
001 |    ...   | .. | .. | .. | .. |
... |    ...   | .. | .. | .. | .. |
111 | 0011 010 | 3C | 5D | 29 | 15 |
    +----------+----+----+----+----+

Address:
+---------+-----+----+
| bbbbbbb | lll | ww |
+---------+-----+----+

Example:
0x35C -> 0011 010|1 11|00 -> line 111, column 00 -> 0x3C

Cache:
    +----------+----+----+----+----+
    |    Tag   | 00 | 01 | 10 | 11 |
    +----------+----+----+----+----+
000 |    ...   | .. | .. | .. | .. |
001 |    ...   | .. | .. | .. | .. |
... |    ...   | .. | .. | .. | .. |
111 | 0011 010 | 3C | 5D | 29 | 15 |
    +----------+----+----+----+----+

• set associative: best (compromise?) of both worlds
  • idea: decompose address into tag, set ID and word ID; now the set ID defines which set of the divided cache the address belongs to, and inside of this set, we may need to use some replacement algorithm
    • k$k$-way associative: each set has k$k$ cache lines
      • note: for each bit removed from the set ID bits, the number of cache lines in each set doubles \to$\to$ fully associative = 1-way associative (0 set bits)

Address:
+----------+----+----+
| bbbbbbbb | ss | ww |
+----------+----+----+

Example:
0x3CB -> 0011 1100 |10|11 -> set 10, column 11 -> 0x2C
0xFB8 -> 1111 1011 |10|00 -> set 10, column 00 -> 0xC2

Cache:
   +-----------+----+----+----+----+
   |    Tag    | 00 | 01 | 10 | 11 |
   +-----------+----+----+----+----+
00 |    ...    | .. | .. | .. | .. |
00 |    ...    | .. | .. | .. | .. |
01 |    ...    | .. | .. | .. | .. |
01 |    ...    | .. | .. | .. | .. |
10 | 0011 1100 | B5 | 8A | F9 | 2C |
10 | 1111 1011 | C2 | 5B | 9F | 32 |
11 |    ...    | .. | .. | .. | .. |
11 |    ...    | .. | .. | .. | .. |
    +----------+----+----+----+----+

Address:
+----------+----+----+
| bbbbbbbb | ss | ww |
+----------+----+----+

Example:
0x3CB -> 0011 1100 |10|11 -> set 10, column 11 -> 0x2C
0xFB8 -> 1111 1011 |10|00 -> set 10, column 00 -> 0xC2

Cache:
   +-----------+----+----+----+----+
   |    Tag    | 00 | 01 | 10 | 11 |
   +-----------+----+----+----+----+
00 |    ...    | .. | .. | .. | .. |
00 |    ...    | .. | .. | .. | .. |
01 |    ...    | .. | .. | .. | .. |
01 |    ...    | .. | .. | .. | .. |
10 | 0011 1100 | B5 | 8A | F9 | 2C |
10 | 1111 1011 | C2 | 5B | 9F | 32 |
11 |    ...    | .. | .. | .. | .. |
11 |    ...    | .. | .. | .. | .. |
    +----------+----+----+----+----+

Replacement Algorithms

• FIFO: first in first out
  • +: easy
  • -: may not always be desired (e.g. OS code / data loaded first, but we wouldn't want to evict / keep evicting it)
• LRU: replace least recently used cache line
  • +: better real-use representation
  • -: expensive to implement
• random: just choose a cache line at random to evict
  • +: surprisingly competitive performance, virtually no bookkeeping needed (only some RNG needed)
  • -: no context info

Write Policies (Update Strategies)

• write through: every write to the cache also writes through to main memory
  • drawback: high bus traffic
• write back: update main memory only when a dirty line is to be replaced
  • drawback: requires keeping everyone updated on what some latest value may be

Cache Misses

• cold miss: initial miss; memory block first touched
• capacity miss: memory block evicted due to limited cache size
• conflict miss: memory block evicted due to a conflict (same cache line as another, previously inserted memory block)

Instruction Cache, Trace Cache

• instruction cache: low latency (important for branch mispredictions), low number of conflict misses (expected linear behavior), only on L1
• trace cache: instruction cache optimized for how code actually runs (branch-aware), not how it’s laid out in memory
  • fetch continues along predicted path (new trace on misprediction)
  • may also contain decoded µops directly (x86)
    
    

Cache Optimization

• goal: optimize Average Access Time = Hit Time + Miss Rate \cdot Miss Penalty$Average Access Time = Hit Time + Miss Rate \cdot Miss Penalty$
  • average access time: latency for load / store to return
  • hit time: latency if address found in cache
  • miss rate: number of misses per number of memory operations
  • miss penalty: latency for fetching data from higher levels

Reducing Hit Time

• small caches, small associativity: reduce hit time and power consumption
• serial tag and data array access: shorter critical path \to$\to$ higher frequency (faster processing), but 1 more cycle (higher access latency) \to$\to$ better for out-of-order processors (can hide memory latency)
• parallel tag and data array access: better for in-order machines where memory latency is important
• avoiding address translation
  • virtually indexed and tagged caches: use virtual address for indexing and tagging, skipping MMU
    • homonym problem: same virtual address may refer to different physical addresses (e.g. context switching) (V \to P_1, V \to P_2, ...$V \to P_1, V \to P_2, ...$)
    • aliasing: multiple virtual addresses mapped to the same physical address (V_1 \to P, V_2 \to P, ...$V_1 \to P, V_2 \to P, ...$)
  • hybrid virtual-physical address caches (VIPT): virtual address for indexing, physical address for tagging
    • aliasing? use only page offset to index cache to avoid index overlaps \to$\to$ L1 size limit = PageSize \cdot Associativity$PageSize \cdot Associativity$
• way prediction: predict cache line in a set of a set associative cache
  • +: same performance as direct mapped cache with the added benefit of reducing the number of conflict misses due to associativity
  • -: way higher hit time if the prediction is wrong

Increasing Cache Bandwidth

• pipelining cache accesses: same as serial / parallel tag / data array access in hit time reduction (higher throughput \to$\to$ higher bandwidth
• multibanking: divide cache into multiple, smaller parts; thus, the CPU can access different parts of the cache at the same time (e.g. two memory addresses)
  • bank conflict: two requests access the same bank \to$\to$ bank stall
    
• non-blocking caches: allows the CPU to continue executing other instructions even if a cache miss occurs
  • blocking caches: on cache miss, stall the CPU until the data is fetched from memory
  • miss status holding register (MSHR): store information about pending misses
    • implicitly addressed: each MSHR stores block address (missed memory block) and destination register (for different words!) + format information (size? sign-extended?)
      
    • explicitly addressed: each MSHR field stores offset in the cache line, allowing for multiple cache misses for the same word (M$M$ determines how many misses per block are allowed; may be different from the number of words)
      
  • fill buffer: holds fetched data before it is written to the cache (data)
  • primary miss: first miss to a cache block
  • secondary miss: subsequent miss while the cache line is being fetched
  • structural-stall miss: secondary miss that the available hardware resources cannot handle (e.g. secondary miss to same word for implicitly addressed MSHR)

Reducing Miss Penalty

• multilevel caches: checking L2 or L3 is still faster than going to memory
• critical word first: memory system fetches the word the CPU actually needs first, before fetching the rest of the block
  • example: CPU needs W5, memory block contains W0-W7; send W5 first, the rest may arrive afterward
• early restart: CPU starts using requested word as soon as it arrives
  • example: CPU needs W5; gets sent W0-W4, and as soon as W5 arrives, it begins using it without waiting for W6 and W7
• write buffer: sits inbetween cache and main memory and handles the transfer of data on write-through / write-back between cache and memory; processor basically delegates this functionality to the buffer while it does something else instead of stalling on each store
  • merging write buffers: using write buffers more efficiently
  • read in combination with write buffers: reads also check entries in write buffer
• victim cache: additional small, fully associative cache that sits between two cache layers; if a line gets evicted, instead of going to memory (getting erased completely), it is moved to this victim cache; if some subsequent access to an evicted line happens soon after (e.g. frequent thrashing in direct mapped caches), the line can still be found in the victim cache

Reducing Miss Rate

• larger caches, larger cache lines, higher associativity: straightforward, but increases hit time / costs
• pseudo-associative cache: like a direct mapped cache, but on miss / conflict, check another line by e.g. flipping an index bit
• compiler optimizations: reduce reuse distance (lower reuse distance \to$\to$ more likely the data is still in the cache when it is needed again)
  • reference: load / store in the source code (e.g. literal A[i] in source code)
  • memory access: actual execution of the reference (e.g. execution of A[0])
  • reuse pair (r_1, r_2)$(r_1, r_2)$: a pair of memory accesses in a memory access stream, which touch the same memory location, without intermediate accesses to that location
  • reuse distance of a reuse pair (r_1,r_2)$(r_1,r_2)$: number of unique memory locations accessed between memory accesses r_1$r_1$ and r_2$r_2$

Reuse Distance Examples

A,B,C,D,E,F,G,A
Reuse Pair      : (A,A)
Unique Locations: 6 (B,C,D,E,F,G)
Reuse Distance  : 6

A,B,B,B,C,A
Reuse Pair      : (A,A)
Unique Locations: 2 (B,C)
Reuse Distance  : 2

Reuse Distance Examples

A,B,C,D,E,F,G,A
Reuse Pair      : (A,A)
Unique Locations: 6 (B,C,D,E,F,G)
Reuse Distance  : 6

A,B,B,B,C,A
Reuse Pair      : (A,A)
Unique Locations: 2 (B,C)
Reuse Distance  : 2

Compiler Optimizations

• strip mining: breaks the loop into smaller chunks (“strips”) that fit better in the cache; same accesses in same order; can always be done

// no strip mining
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        A[i][j] += B[j]; // if B is large, it may not stay in cache across iterations of i
    }
}


// strip mined loop
// S: strip size chosen such that B[jj ... jj + S - 1] fits in cache
for (int jj = 0; jj < M; jj += S) {
    for (int i = 0; i < N; i++) {
        for (int j = jj; j < min(jj + S, M); j++) {
            A[i][j] += B[j];
        }
    }
}

// no strip mining
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        A[i][j] += B[j]; // if B is large, it may not stay in cache across iterations of i
    }
}


// strip mined loop
// S: strip size chosen such that B[jj ... jj + S - 1] fits in cache
for (int jj = 0; jj < M; jj += S) {
    for (int i = 0; i < N; i++) {
        for (int j = jj; j < min(jj + S, M); j++) {
            A[i][j] += B[j];
        }
    }
}

• loop interchange: self-explanatory
  • C: row-major (outer i$i$ inner j$j$; for(int i = 0; i < M; ++i) for(int j = 0; j < N; ++j) A[i][j] = ...;)
  • Fortran: column-major (outer j$j$ inner i$i$; do j = 1, N do i = 1, M A(i,j) = ...)
    
    • may not work if there are dependencies

// loop interchange in C (row-major)

// bad (continuous thrashing)
for (int j = 0; j < N; ++j) {
    for (int i = 0; i < M; ++i) {
        A[i][j] += B[i][j];
    }
}

// good (optimized for cache locality)
for (int i = 0; i < M; ++i) {
    for (int j = 0; j < N; ++j) {
        A[i][j] += B[i][j];
    }
}

// loop interchange in C (row-major)

// bad (continuous thrashing)
for (int j = 0; j < N; ++j) {
    for (int i = 0; i < M; ++i) {
        A[i][j] += B[i][j];
    }
}

// good (optimized for cache locality)
for (int i = 0; i < M; ++i) {
    for (int j = 0; j < N; ++j) {
        A[i][j] += B[i][j];
    }
}

• tiling / blocking: strip mining + loop interchange
  
  
  

Data Transformations

• alignment: align a data structure so that it begins at a cache line boundary
• array padding: reduces cache miss rate by preventing frequently accessed data from mapping to the same cache lines or sets (i.e. direct mapped or set associative) through insertion of padding between the arrays, eliminating conflict misses and false sharing

// assume A and B are accessed together in a loop
// and A and B (by default) happen to map to the same cache line / set

// example: no array padding
int A[1024], B[1024];
A[i] -> miss
B[i] -> miss (evicts A[i])
A[i] -> miss (evicts B[i])
...

// example: with array padding
int A[1024], pad[16], B[1024]; // A and B now live in separate lines / sets
A[i] -> miss (cold)
B[i] -> miss (cold)
A[i] -> hit
B[i] -> hit
...

// assume A and B are accessed together in a loop
// and A and B (by default) happen to map to the same cache line / set

// example: no array padding
int A[1024], B[1024];
A[i] -> miss
B[i] -> miss (evicts A[i])
A[i] -> miss (evicts B[i])
...

// example: with array padding
int A[1024], pad[16], B[1024]; // A and B now live in separate lines / sets
A[i] -> miss (cold)
B[i] -> miss (cold)
A[i] -> hit
B[i] -> hit
...

• array element reordering: basically transpose array in memory (or just change their ordering to better match how they are accessed in memory, e.g. value at A[i][j] is now at A[j][i])

  • could be done instead of loop interchange because it globally changes the positions of the elements in the array and loop interchange may not be possible due to dependencies between iterations

• array merging: self-explanatory; avoids thrashing

// array merging

// no merging
int B[200], A[200]
for (int i = 0; i < N; ++i)
    B[i] = ... A[i] ... // could be that B and A constantly evict eachother

// merging
int C[400]
for(int i = 0; i < N; ++i)
    C[2 * i - 1] = ... C[2 * i] ... // now the elements are close to eachother, in the same line

// array merging

// no merging
int B[200], A[200]
for (int i = 0; i < N; ++i)
    B[i] = ... A[i] ... // could be that B and A constantly evict eachother

// merging
int C[400]
for(int i = 0; i < N; ++i)
    C[2 * i - 1] = ... C[2 * i] ... // now the elements are close to eachother, in the same line

Hardware / Software Prefetching

• hardware prefetching: hardware support to predict next data access and perform an advanced fetch from the next higher level
  • prefetch-on-miss: prefetch block n+1$n+1$ whenever a miss occurs for block n$n$ (no block 1? fetch 1 and 2; block 2 there; no block 3? fetch 3 and 4...; so only every second miss can be removed)
    
  • tagged prefetch: each cache line has an additional bit representing whether the line was prefetched and not yet referenced
    • miss? load desired memory block (tag 0) and next k$k$ blocks (tag 1)
    • hit, tag 0? line was demand-fetched or already referenced; no prefetch
    • hit, tag 1? line was prefetched and not referenced until now; prefetch next k$k$ blocks (tag 1) and set tag of this line to 0
      
  • stream buffer: use a FIFO buffer to store prefetched lines (e.g. if the HW detects we access 0x1000, it will fetch and store 0x1040, 0x1080, 0x10C0... into the stream buffer); on miss, check this buffer; on hit, transfer to main cache
    • arrays on different pages? create multiple streams
  • +: reduces miss rate and miss penalty
  • -: prefetching unused data wastes memory bandwidth and prefetched memory blocks may evict other blocks too early
• software prefetching: requires non-blocking, exception-ignoring prefetch instructions and non-blocking caches

Volatile Memory

• volatile: memory requires power to keep contents
• static random access memory (SRAM): uses flip-flops; small but fast, expensive, used for caches; each bit remains stored as long as power is supplied but doesn't need constant refreshing (hence "static")
  • 6T cell: six-transistor cell, stores a bit
    • coupled-inverter pair: 4 transistors forming a flip-flop to store a 0 or 1
    • access transistors: 2 transistors, controlling whether the cell connects to the external read / write liines
    • connected to wordline and bitlines
  • wordline: controls access transistors; “row switch” that decides which memory cells are active
  • bitlines: carry data to / from cell; “data highways” that carry the 0 or 1 to / from the memory cells
    
    • read: measure difference in bitline amplitudes
    • write: the stronger bitline voltages overwrite the cell's flip-flop
• dynamic random access memory (DRAM): each bit is stored as a charge in a tiny capacitor; larger but slower, cheap*; power needs periodic refreshing due to leakage (hence "dynamic")
  • 1T1C cell: 1 transistor, 1 capacitor (charged: 1, uncharged: 0)
  • 1 wordline, 1 bitline
  • destructive read: when you read from a charged capacitor, it loses its charge and has to be rewritten
  • write: charge capacitor according to bitline voltage
    
• synchronous DRAM (SDRAM): DRAM signals tied to processor clock; faster
  • double data rate (DDR): sends double the amount of data in one clock cycle (transmission with rising and falling edge instead of just rising edge)
    • 2 \to 5$2 \to 5$: clock rate increases

• memory is a matrix of cells
• dual in-line memory module (DIMM): RAM packaging
  • 8 byte wide bus \to$\to$ 64 bit transferred per cycle
  • registered DIMM (RDIMM): uses a register on the DIMM for command / address signals to reduce electrical load (instead of distributing the load along the entire stick), at the cost of slightly higher latency
  • load-reduced DIMM (LR-DIMM): reduces load even further by also buffering data signals
    

Virtual Memory

• goal: enable multiprocess, multiuser operating systems, where the OS selects memory for code and data of a program, loads it into said memory, manages and optimizes the usage of the physical memory and offers protection over the owned contents of a process in memory
• mapping of pages to frames (virtual to physical addresses): done via OS using page tables
  • pages: organization of virtual address space (typically 4K)
  • frames: organization of physical address space (typically same size as page; same offset)
  • page table: table storing for each page the frame to which it is mapped
  • inverted page table: maps physical memory frames to virtual pages, with one entry per physical frame, indexed by the frame number itself; slow search, destroys cache locality
• memory management unit (MMU): translates virtual addresses into physical addresses and checks access rights
• translation lookaside buffer (TLB): cache for translated addresses (page / frame pairs)
• memory controller (MC): accesses memory chip based on some physical address; integrated in the CPU
  

Non-Volatile Memory

• non-volatile: permanent; content is not lost on power off
• read only memory (ROM): non-volatile memory that stores data permanently; contents inserted during production
• programmable ROM (PROM): ROM that can be programmed once after production
• erasable PROM (EPROM): PROM that can be erased via UV light (entirely) and reprogrammed multiple times
• electrically erasable PROM (EEPROM): PROM that can be erased and reprogrammed electrically, without removing it from the circuit

• FLASH: block-level EEPROM for large-scale storage (e.g. SSD, USB drive)
  • NAND: used for mass storage; fast read-write speeds, reading data done in blocks
  • NOR: used e.g. for firmware, BIOS...; very fast read speeds, slower at writing / erasing (each cell accessed individually)
    
  • SLC, MLC, TLC, QLC: single / multi / triple / quad level cells, representing the number of bits per memory cell (higher: denser and cheaper, but slower with a lower life expectancy)
  • NVMe: protocol used to access SSDs over PCIe (CPU communicates directly with device) replacing SATA / AHCI; supports 64000 command queues, with 64000 commands each
• error correction code (ECC): used to correct data corruption; for 2^n$2^n$ bits, n+1$n+1$ parity bits are required (e.g. 64 bits = 2^6 \to 6+1=7$= 2^6 \to 6+1=7$ parity bits required \to$\to$ 71 bits total)

Very Long Instruction Word Processing

• very long instruction word: a type of instruction set architecture designed to exploit instruction-level parallelism by explicitly specifying, in advance, which instructions execute in parallel
  • problems: number of functional units manifests in ISA \to$\to$ low / no binary compatibility between different VLIW processors; latencies of FUs visible; static in-order scheduling (all operations should take the same number of cycles); NOPs lead to memory overhead and "wasted" cycles
  • Explicit Parallel Instruction Computing (EPIC): VLIW with architectural abstraction (FUs not explicitly specified)
    • instruction grouping: compiler combines independent instructions into groups
    • instruction format: three instructions are combined into one instruction word, called a bundle

VLIW Example (no dependencies)

High-level code:
a = b + c;
d = e * f;
g = A[i];

Normal (non-VLIW, assuming one per cycle):
ADD  a, b, c
MUL  d, e, f
LOAD g, A[i]

VLIW (single-cycle, one instruction):
|    ALU    |    MUL    |     MEM     | BR  |
| ADD a,b,c | MUL d,e,f | LOAD g,A[i] | NOP |

VLIW Example (no dependencies)

High-level code:
a = b + c;
d = e * f;
g = A[i];

Normal (non-VLIW, assuming one per cycle):
ADD  a, b, c
MUL  d, e, f
LOAD g, A[i]

VLIW (single-cycle, one instruction):
|    ALU    |    MUL    |     MEM     | BR  |
| ADD a,b,c | MUL d,e,f | LOAD g,A[i] | NOP |

VLIW Example (dependencies)

High-level code:
a = b + c;
d = a * e; // depends on a

VLIW (cycles 1,2):
| ADD a,b,c | NOP | NOP | NOP |
| NOP | MUL d,a,e | NOP | NOP |

VLIW Example (dependencies)

High-level code:
a = b + c;
d = a * e; // depends on a

VLIW (cycles 1,2):
| ADD a,b,c | NOP | NOP | NOP |
| NOP | MUL d,a,e | NOP | NOP |

{ .mii // memory integer integer; memory unit can also execute integer operations
     add r1 = r2, r3
     sub r4 = r4, r5;;   // end of group
     shr r7 = r4, r12;;  // end of group
} // end of bundle
{ .mmi
     ld8 r2 = [r1];;     // end of group
     st8 [r1] = r23
     tbit p1, p2 = r4, 5 // test 5th bit in r4; result of comparison and complement stored in p1 and p2
} // end of bundle
{ .mbb
     ld8 r45 = [r55]
(p3) br.call b1 = func1  // conditional call of func1 depending on predicate register p3; b1 stores target address (instruction commits only if predicate register is 1)
(p4) br.cond Label1
} // end of bundle
{ .mfi
     st4 [r45] = r6
     fmac f1 = f2, f3
     add r3 = r3, 8;;    // end of group spanning multiple bundles
} // end of bundle

{ .mii // memory integer integer; memory unit can also execute integer operations
     add r1 = r2, r3
     sub r4 = r4, r5;;   // end of group
     shr r7 = r4, r12;;  // end of group
} // end of bundle
{ .mmi
     ld8 r2 = [r1];;     // end of group
     st8 [r1] = r23
     tbit p1, p2 = r4, 5 // test 5th bit in r4; result of comparison and complement stored in p1 and p2
} // end of bundle
{ .mbb
     ld8 r45 = [r55]
(p3) br.call b1 = func1  // conditional call of func1 depending on predicate register p3; b1 stores target address (instruction commits only if predicate register is 1)
(p4) br.cond Label1
} // end of bundle
{ .mfi
     st4 [r45] = r6
     fmac f1 = f2, f3
     add r3 = r3, 8;;    // end of group spanning multiple bundles
} // end of bundle

Data Parallel Architectures

Single Instruction Multiple Data (SIMD)

• single instruction multiple data (SIMD): execute the same operation on a set of data with a single instruction
  • vector processor: uses large vector registers; load data into vector registers, performs single instruction on entire vectors, write results back to memory (e.g. Cray-1)
    • vector register: register designed to hold multiple values at once
    • vector functional units: pipelined, can start a new operation every cycle
    • vector load / store unit: deeply pipelined loads and stores, hiding memory latency (except for 1st element for obvious reasons)
    • scalar registers: holding scalar values for "normal" operations and as operands for vector operations
      
    • mask register: provide conditional execution of each element operation in a vector instruction
    • gather-scatter: operations to switch between compressed and normal matrix representation (for operations like A[K[i]] = A[K[i]] + C[M[i]])
      • gather: fetch elements based on index vector into vector register
      • scatter: distribute elements based on index vector into memory
  • multimedia SIMD extensions (CPU SIMD): SIMD extensions added to general-purpose CPUs; shorter vector registers (e.g. MMX, SSE, AVX)
    
  • graphics processing unit (GPU): massively parallel processors where thousands of lightweight threads execute the same instruction on different data (many cores, each running SIMD-like units)
    • single instruction multiple threads (SIMT): GPU programming model; one instruction executed by many threads (e.g. programmer sees int i = thread_id; C[i] = A[i] + B[i];, HW sees exec ADD for 32 threads), each thread has its own registers, ID, data
    • warps / wavefronts: fixed-size thread bundles; all threads execute the same instruction on different data (basically, a warp akin to a SIMD vector where each lane is a thread)
    • tensor memory accelerator (TMA): HW for async data transfer between global and shared memory

• roofline model: intuitive visual performance model used to provide performance estimates of a given compute kernel or application running on multi-core, many-core, or accelerator processor architectures, by showing inherent hardware limitations, and potential benefit and priority of optimizations
  • hardware abstraction: compute core (with some peak performance p_{peak}$p_{peak}$, measured in FLOPS), data source (e.g. memory, cache, network...); bandwidth b_s$b_s$ inbetween (byte/s)
  • software abstraction: some loop(s) doing N$N$ FLOPs causing V$V$ bytes of data transfer
    • computational intensity: I = \frac NV$I = \frac NV$ FLOP/byte
  • bottlenecks: p_{peak}$p_{peak}$ (execution of work) or I \cdot b_s$I \cdot b_s$ (data path)
  • upper limit (final performance): P = min(p_{peak}, I \cdot b_s)$P = min(p_{peak}, I \cdot b_s)$
    
  • at inflection point (best resource use): p_{peak} = I \cdot b_s$p_{peak} = I \cdot b_s$
  • left of inflection point (low intensity): P$P$ limited by data path (memory bound)
  • right of inflection point (high intensity): P$P$ limited by peak performance (compute bound)

Compute Unified Device Model (CUDA)

• Compute Unified Device Model (CUDA): NVIDIA's model for general-purpose programming on GPUs

  • thread block: group of threads that execute together on the GPU (can cooperate and share memory)
  • streaming multiprocessor (SM): hardware unit inside GPU that executes thread blocks
    • contains CUDA cores, registers, shared memory, warp schedulers...
    • each thread block is assigned to one SM; one SM can run multiple thread blocks at a time
    • each SM executes blocks using warps of 32 threads
      
  • CUDA threads have their own registers
    • shared memory - L1 cache: each thread block has its own memory that is shared within the threads inside the block; organized in 32 banks for the 32 threads of a warp
    • global L2 cache: communication among all threads of a kernel
      

• divergence: if threads in a warp take different paths, the warp serializes execution
  

Multithreading

• thread: basic execution unit for a piece of code; threads share system resources and have their own stack
• process: consists of one or more threads; different processes have different resources

• hardware multithreading: hardware support for multiple threads, requiring additional bookkeeping hardware and separate register files
  • cycle-by-cycle interleaving: on each cycle, the processor switches to another thread
  • block interleaving (scalar): instructions of a thread are executed until a long latency instruction is executed, which is when the processor provisionally switches to another thread
  • simultaneous multithreading (SMT) (superscalar): issue unit starts instructions from multiple threads in the same cycle

Shared Memory Systems

• shared memory: system provides shared address space; communication done via read / write to global addresses of this address space
• uniform memory access (UMA): shared memory with a symmetric global address space (every nodes accesses this space with the same latency)
• non-uniform memory access (NUMA / distributed shared memory): memory is distributed among nodes; local access much faster than remote access
  • cache-coherent NUMA (ccNUMA): NUMA, where each processor has its own caches, automatically kept coherent by the hardware on changes (more transparent but less scalable)
  • non-cache-coherent NUMA (nccNUMA): NUMA, where each processor has its own caches, but these are not automatically maintained by the hardware (more scalable but risk of stale data)
  • cache-only memory (COMA): no "main memory", all memory acts as a large cache, memory is dynamically allocated and migrated to where it is needed
    

Cache Coherence

• cache coherence: involves write propagation and write serialization
  • write propagation: a write by one core becomes visible to other cores
  • write serialization: all cores see writes to the same location in the same order
• snooping protocol: every cache eavesdrops on everyone else’s memory traffic and reacts when it sees something relevant
  • formally: distributed algorithm represented by a collection of cooperating finite state machines
    

Invalidation Protocol

• processor states: what the processor does
  • PrWr / PrRd: processor read / write request on a cache block
• bus states: messages on the bus (i.e. what others tell the processor)
  • BusRd: on read miss in processor's cache, send BusRd and expect to receive cache block
  • BusRdX: on write miss in processor's cache, send BusRdX, expect to receive cache block and invalidate block in all other caches
  • BusUpgr: on write hit in processor's cache, send BusUpgr to invalidate block in all other caches
  • Flush: cache block is being written back to memory
• write through cache: every change needs to update memory
  
• write back cache: update main memory only when a dirty line is to be replace
  • MSI: modified / shared / invalid
    • M: block has been modified in the cache; data is inconsistent with main memory, must write block to memory when evicted
    • S: block is unmodified and exists in read-only state in at least one cache
    • I: block is either not present in current cache or has been invalidated by a bus request; must be fetched from memory or from another cache
      
      
      
  • MESI: modified / exclusive / shared / invalid; reduces bus traffic when data is only in one cache
    • E: cache line is present only in current cache, matches main memory (may be changed to S on read request or M on own write)
      
      
      
  • MESIF: modified / exclusive / shared / invalid / forward
    • F: specialized form of the S state, indicates that a cache should act as a designated responder for any requests for the given line
      

Directory Protocols

• directory protocol: mechanism used to keep cached copies of shared data consistent across multiple processors, without relying on broadcast-based snooping
  • directory data structure: which cache(s) hold(s) a copy of the memory block, is the block shared / modified, which cache (if any) has exclusive ownership?
    • read miss: core A misses on read, queries directory; directory supplies data (from memory or owner cache) and records that A has a shared copy
    • write miss: core A misses on write, queries directory for access; directory identifies which cores currently cache the block and sends invalidate message to those cores only and gives A access

• directory storage schemes: define directory implementations
  • centralized: entire directory stored at one node (not scalable, single point of failure)
  • flat, memory-based: directory is distributed across nodes; each node stores information for its memory (huge memory overhead, proportional to P\cdot M$P\cdot M$ where P$P$ is the number of processors and M$M$ is the size of the memory)
    • memory overhead reduction: bigger cache lines, more processor per directory (e.g. 2 per directory instead of 1), use processor address instead of presence bit (e.g. for 1024 processors, 10 bits instead of 1024)
      
  • hierarchical: each directory summarizes the information of the lower level directories
    • +: transactions do not need to go to home, multiple requests from different nodes can be combined
    • -: higher latency due to potential lookup in higher levels, number of transactions may be bigger than in flat scheme

Memory Consistency

• coherence vs. consistency
  • coherence: writes to a single location are visible to all in the same order
  • consistency: writes to multiple locations are visible to all in the same order
• memory consistency model: defines the legal ways memory operations from different threads can appear to interleave and become visible to each other
• strict consistency: read returns value of most recent write (easy for programmers, but hinders optimizations such as write buffers)
  
• sequential consistency: "the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program"
  
• processor consistency: writes by a CPU are seen by all CPUs in the order they were issued; for every memory word, all CPUs see all writes to it in the same order
  • in other words: instead of everyone requiring to see the same order, it just matters that everyone sees the writes in their corresponding order (e.g. if P1 writes A before B, this is what is enforced) but everything else (e.g. interleaving) is undefined
    
    
• weak consistency: do whatever you want
  • synchronization operations finish all pending memory operations
    
    

Coherence Misses

• coherence miss: data exists in another cache, but our cache cannot use it yet because coherence rules say it might be stale or modified elsewhere (e.g. MESI, core 1 and 2 have X, core 1 writes X = 10 (M), core 2 wants to read X (I), miss)

Synchronization

• synchronization: coordination of events to operate a system in unison (general definition)
  • mutual exclusion: access to shared data structures is restricted
  • point-to-point events: processes signal other processes that they reached a specific point in their execution
  • global events: event constituting that a set of processes reached a specific point in their execution
• components: acquire, wait, release
  • acquire: process attempts to acquire right to synchronization
  • wait: process waits for synchronization
    • busy-waiting: spin for a variable to change
    • blocking: suspend and release via OS
    • hybrid: busy-waiting + blocking
  • release: process enables other processes to proceed past a sync event
• locks: used to implement mutex (only one thread can access a data structure at a time)
  • operations: lock (or wait until it is unlocked, then lock), unlock

Atomic Operations

// test and set lock
//
// if the old value was 0, it means the lock was free -> set it
// if the old value was 1, it means the lock is taken -> wait
function test_and_set(lock):
    old_value = lock
    lock = 1
    return old_value

// compare and swap
//
// compare contents of a memory location and swap it with a new value if it matches
function compare_and_swap(address, expected, new_value):
    old_value = *address
    if old_value == expected:
        *address = new_value
    return old_value

// fetch and OP (here: add)
//
// performs an operation on a memory location atomically and returns the original value
function fetch_and_add(address, value):
    old_value = *address
    *address = old_value + value
    return old_value

// test and set lock
//
// if the old value was 0, it means the lock was free -> set it
// if the old value was 1, it means the lock is taken -> wait
function test_and_set(lock):
    old_value = lock
    lock = 1
    return old_value

// compare and swap
//
// compare contents of a memory location and swap it with a new value if it matches
function compare_and_swap(address, expected, new_value):
    old_value = *address
    if old_value == expected:
        *address = new_value
    return old_value

// fetch and OP (here: add)
//
// performs an operation on a memory location atomically and returns the original value
function fetch_and_add(address, value):
    old_value = *address
    *address = old_value + value
    return old_value

Locks

• test-and-set lock (TAS): use an atomic test-and-set operation for locking (problem: a lot of bus traffic by continuously writing to the lock)
• test-and-test-and-set lock (TTAS): optimizes TAS by first checking the lock without writing, and only if it appears free, it tries to acquire it atomically
• load-link / store-conditional lock (LL/SC): uses load-link and store-conditional operations to lock
  • load-link: reads current value from memory address and tells processor to watch address
  • store-conditional: writes value to address only if no other processor has modified that location since the ll instruction was executed
• ticket lock: fair lock (every process will eventually obtain the lock), very little bus traffic
• array based lock: spread the wait traffic to different cache lines, so that each thread spin-waits on a different cache line to reduce the coherency traffic

// test-and-set lock (TAS)
lock(location):
    tas register, location // copy location to register and assign 1 to location
    bnz register, lock     // compare old value to 0; if lock was taken, then keep waiting (jump back)
    ret

unlock(location):
    st location, 0
    ret

// test-and-set lock (TAS)
lock(location):
    tas register, location // copy location to register and assign 1 to location
    bnz register, lock     // compare old value to 0; if lock was taken, then keep waiting (jump back)
    ret

unlock(location):
    st location, 0
    ret

// test-and-test-and-set lock (TTAS)
lock(location):
    mov register, location      // load lock value into register
    bz  register, lock_attempt  // if the lock is not set, try to acquire
wait:
    mov register, location      // if the lock is set...
    bnz register, wait          // ...keep reading lock
lock_attempt:
    tas register, location      // classic TAS
    bnz register, lock          // fail, start over
lock_acquired:
    ret

unlock(location):
    st location, 0
    ret

// test-and-test-and-set lock (TTAS)
lock(location):
    mov register, location      // load lock value into register
    bz  register, lock_attempt  // if the lock is not set, try to acquire
wait:
    mov register, location      // if the lock is set...
    bnz register, wait          // ...keep reading lock
lock_attempt:
    tas register, location      // classic TAS
    bnz register, lock          // fail, start over
lock_acquired:
    ret

unlock(location):
    st location, 0
    ret

// load-link, store-conditional (LL/SC)
lock(location):
    ll  reg1, location  // read lock value into reg1 and monitor lock location
    bnz reg1, lock      // if lock taken; try again; otherwise, attempt to acquire
    sc  location, reg2  // conditionally store lock value into lock location ONLY IF no-one wrote to location inbetween this operation and the previous ll operation
    beqz lock           // if someone else modified location in the mean time, fail and try again
    ret

unlock(location):
    st location, 0
    ret

// load-link, store-conditional (LL/SC)
lock(location):
    ll  reg1, location  // read lock value into reg1 and monitor lock location
    bnz reg1, lock      // if lock taken; try again; otherwise, attempt to acquire
    sc  location, reg2  // conditionally store lock value into lock location ONLY IF no-one wrote to location inbetween this operation and the previous ll operation
    beqz lock           // if someone else modified location in the mean time, fail and try again
    ret

unlock(location):
    st location, 0
    ret

// ticket lock
typedef struct {
    atomic_int ticket;
    atomic_int service;
} ticket_lock_t;

void lock_init(ticket_lock_t *l) {
    atomic_init(&l->ticket, 0);
    atomic_init(&l->service, 0);
}

void lock(ticket_lock_t *l) {
    // 1. Take a ticket (increment the global ticket counter)
    int my_ticket = atomic_fetch_add(&l->ticket, 1);

    // 2. Spin until the service counter matches my ticket
    while (atomic_load(&l->service) != my_ticket);
}

void unlock(ticket_lock_t *l) {
    // 3. Increment the service counter to let the next person in
    atomic_fetch_add(&l->service, 1);
}

// ticket lock
typedef struct {
    atomic_int ticket;
    atomic_int service;
} ticket_lock_t;

void lock_init(ticket_lock_t *l) {
    atomic_init(&l->ticket, 0);
    atomic_init(&l->service, 0);
}

void lock(ticket_lock_t *l) {
    // 1. Take a ticket (increment the global ticket counter)
    int my_ticket = atomic_fetch_add(&l->ticket, 1);

    // 2. Spin until the service counter matches my ticket
    while (atomic_load(&l->service) != my_ticket);
}

void unlock(ticket_lock_t *l) {
    // 3. Increment the service counter to let the next person in
    atomic_fetch_add(&l->service, 1);
}

// array based lock
typedef struct {
  int next_ticket;
  int can_serve[NTHREADS * 16];
  int my_ticket[NTHREADS * 16];
} lock_t;

void lock(lock_t* lck, int tid) {
    // 1. Assign ticket number to arriving thread
    lck->my_ticket[tid * 16] = atomic_fetch_add(lck->next_ticket, 1) % NTHREADS;

    // 2. Wait until ticket number is ready to go
    while (lck->can_serve[lck->my_ticket[tid * 16] * 16] != 1);
}

void unlock(lock_t* lck, int tid) {
    // 3. Release current thread's ticket and go to next ticket number
    lck->can_serve[lck->my_ticket[tid * 16] * 16] = 0;
    lck->can_serve[(lck->my_ticket[tid * 16] + 1) % NTHREADS * 16] = 1;
}

// array based lock
typedef struct {
  int next_ticket;
  int can_serve[NTHREADS * 16];
  int my_ticket[NTHREADS * 16];
} lock_t;

void lock(lock_t* lck, int tid) {
    // 1. Assign ticket number to arriving thread
    lck->my_ticket[tid * 16] = atomic_fetch_add(lck->next_ticket, 1) % NTHREADS;

    // 2. Wait until ticket number is ready to go
    while (lck->can_serve[lck->my_ticket[tid * 16] * 16] != 1);
}

void unlock(lock_t* lck, int tid) {
    // 3. Release current thread's ticket and go to next ticket number
    lck->can_serve[lck->my_ticket[tid * 16] * 16] = 0;
    lck->can_serve[(lck->my_ticket[tid * 16] + 1) % NTHREADS * 16] = 1;
}

Transactions

• transaction: request + all the steps needed to complete it + response
  • in other words: extended atomic operation
  • characteristics
    • atomicity: at commit, all memory writes take effect at once; at abort, none of the writes appear to take effect
    • isolation: no other code can observe writes before commit
    • serializability: transactions seem to commit in a single serial order
  • conflict? abort transaction (i.e. another core reads an address in the write set or writes an address in the read or write set)
    • detection: cache coherency protocol

Chip Multiprocessors

• chip multiprocessors: multicore processors
  • why? power and heat limits when it comes to making one core faster; difficulty parallelizing existing serial applications

Shared LLC

• +: no replication of shared blocks, dynamic cache space sharing (if one processor needs less space, the other can use more), lower communication latency (lower coherence protocol overhead)
• -: higher bandwidth, competition between cores may induce higher latency, complex design, one CPU can evict data of other CPU

Private LLC

• non-broadcast: directory protocol
• broadcast: snooping

OpenMP

• OpenMP: portable programming library for shared memory systems with Fortran and C/C++ API
• parallel region: #pragma omp parallel
• for-loop: #pragma omp for [parameters], loop variable private by default
• tasking: parallel \to$\to$ single \to$\to$ for(...) \to$\to$ task
• sections: each section can run simultaneously, independently

// sections
#pragma omp parallel sections
{
    #pragma omp section
    {
        compute_A();
    }

    #pragma omp section
    {
        compute_B();
    }

    #pragma omp section
    {
        compute_C();
    }
} // implicit barrier

// sections
#pragma omp parallel sections
{
    #pragma omp section
    {
        compute_A();
    }

    #pragma omp section
    {
        compute_B();
    }

    #pragma omp section
    {
        compute_C();
    }
} // implicit barrier

Distributed Memory Systems

• distributed memory (multicomputer, DM) systems: nodes with private physical address space; communication based on messages
  • massively parallel systems: dedicated systems with single OS instance
  • clusters: collection of servers dedicated to parallel computing with a dedicated high-performance network, individual OS instances on each machine
  • network of workstations (NoW): no dedicated high-performance network
• network: nodes connected via routers and links
  
  • packets: sent via network interface from source to target node
  • scalability: number of concurrent messages and the bandwidth in the network grows with the number of nodes, latency for message transfers grows less then linear with the number of nodes, cost grows at most linear with the number of nodes
  • Bandwidth = \frac{Bytes}{Second}$Bandwidth = \frac{Bytes}{Second}$
  • StartupTime$StartupTime$: time for an empty message
  • Latency$Latency$: time for message transfer
  • topology: specifies the logical structure of the communication network
  • routing algorithm: determines path of messages through network
    • hop: transmission to next router
    • path: consists of multiple hops
    • oblivious routing algorithm: decides only on source and destination; no reaction to events (e.g. link failure) or loads in network
    • adaptive routing algorithm: respects events and / or load in network
  • router: has input and output ports; every input port connected to an output port
    • arbitration: decision, if multiple incoming messages go to the same output port, which one goes first
    • might have buffers on input ports

• packet: messages are split sender-side into multiple smaller packets (on-chip: typically no split since messages are already of cache line size)
  • flow control digit (flit): packets are streamed as flits
  • physical control digit (phit): if the physical link width is less than a flit, the transmission of a flit is done in multiple cycles

Packet (128 bytes)
 ├─ Flit 0 (header)
 ├─ Flit 1 (payload)
 ├─ Flit 2 (payload)
 └─ Flit 3 (tail)

Packet (128 bytes)
 ├─ Flit 0 (header)
 ├─ Flit 1 (payload)
 ├─ Flit 2 (payload)
 └─ Flit 3 (tail)

Flit = 128 bits
Link width = 32 bits

→ 1 flit = 4 phits

Flit = 128 bits
Link width = 32 bits

→ 1 flit = 4 phits

Network Flow Control

• bufferless: no buffers at input ports
  • hot-potato: incoming flit is sent to another free output port if the desired port is busy
  • circuit-switched network: path pre-reservation using probe message (requires minimal buffering for probe message to wait until output port is free)
• buffered: buffers at input ports
  • packet-buffer: links and buffers are allocated per packet; input port must have large enough buffer for entire packet
    
  • wormhole flow control: links and buffers are allocated per flit
• end-to-end transmission time: Time(n)=Overhead+RoutingDelay+ChannelOccupancy+ContentionDelay$Time(n)=Overhead+RoutingDelay+ChannelOccupancy+ContentionDelay$
  • overhead: time for getting messages in and out of the network
  • routing delay: in each switch, a message suffers some routing delay
  • channel occupancy: time for transferring n$n$ bytes over the channel
    • ChannelOccupancy=\frac{n+ne}{b}$ChannelOccupancy=\frac{n+ne}{b}$
      • ne$ne$: number of bytes for protocol overhead
      • b$b$: channel bandwidth
  • contention delay: time while a message is blocked because the next channel is occupied
  • typical formula: Time(n)=StartupTime+\frac{n}{Bandwidth}$Time(n)=StartupTime+\frac{n}{Bandwidth}$

Network Topologies

• distance: number of links on route
• degree: number of links in a router
• diameter: maximum routing distance
• physical properties: technology, length, link width
• local bandwidth: bandwidth available to each node individually
  • EffectiveLocalBandwidth=b\cdot\frac{n}{n+n_E}$EffectiveLocalBandwidth=b\cdot\frac{n}{n+n_E}$
    • b$b$: raw bandwidth
    • n$n$: packet length
    • n_E$n_E$: header information
• aggregate bandwidth: total bandwidth
  • entry bandwidth: sum of the bandwidth of all links of the nodes into the network
  • bisection bandwidth: sum of the bandwidth of the minimum set of links that, if removed, partition the network into two equal unconnected sets of nodes

Topologies

• fully connected: diameter 1, degree N$N$
• linear arrays: diameter N-1$N-1$, average distance \frac N3$\frac N3$, bisection bandwidth 1, route given by relative address R=B-A$R=B-A$ where A,B$A,B$ are node numbers from 0 to N-1$N-1$
  
• multidimensional topologies: d$d$-dimensional array, route by traversing r_i=b_i-a_i$r_i=b_i-a_i$ hops in each dimension
  • meshes: diameter d \cdot (k-1)$d \cdot (k-1)$, average distance \frac{dk}3$\frac{dk}3$, degree from d$d$ to 2d$2d$, bisection bandwidth k^{d-1}$k^{d-1}$?
  • tori: diameter d\cdot\frac k2$d\cdot\frac k2$, average distance \frac{dk}4$\frac{dk}4$, degree 2d$2d$, bisection bandwidth 2?
    
• hypercubes: binary n$n$-cubes, n=\log N$n=\log N$ is the number of dimensions, N=2^n$N=2^n$ is the number of nodes, nodes connected to n$n$ nodes that differ in exactly one bit (Gray code), routing by length number of ones in A xor B, dimension order routing via hops in non-zero dimensions
  • diameter n$n$, bisection bandwidth 2^{n-1}$2^{n-1}$
    
• k-ary tree: height d = \log_k N$d = \log_k N$, fixed degree, logarithmic diameter and average distance, routing up to common ancestor, then down
  • going from A to B: R = B \oplus A$R = B \oplus A$
  • common ancestor: let i$i$ be position of most signifcant 1 in R$R$, route up i+1$i+1$ levels
  • descent: down in direction given by low i+1$i+1$ bits of B$B$
    
    
• fat tree: as you move higher up the hierarchy toward the core, the links become "fatter" (more bandwidth) to ensure that data doesn't get backed up
  
• dragonfly network: "group of groups", groups of nodes and routers, multiple routers in a group have an all-to-all connection, all groups have an all-to-all connection, diameter 3 (typically)
  • +: small number of long cables, reduced cost, high performance
    

Network Interface

• virtual interface architecture (VIA): a kernel-bypass networking architecture that lets applications communicate directly with network hardware via protected virtual interfaces, achieving very low latency and high throughput