instructor: Mark Jeffrey

lec: T 3PM-5PM MC254, W 9AM-10AM BA1170
lec2: M11AM-1PM BA1180, W10AM-11AM BA1160
tut: W 4PM-5PM GB120
pra: F 9AM-12PM BA3155

Zoom: https://utoronto.zoom.us/j/82657136791 (Passcode: 552552)

breakdown

quercus quiz * (9-1) (2%)
lab * 5 (25%)
mt (27%)
fe (45%)

Week 1. Sep 8
Week 2. Sep 15
Week 3. Sep 22
Week 4. Sep 29
Week 5. Oct 6
Week 6. Oct 13
Week 7. Oct 20

Week 1. Sep 8

the role of a computer architect:

technology: CMOS, logic gates, ISA, SRAM, DRAM, register, packaging, magnetic store, flash, ...
computer: supercomputer, embedded systems, laptop, desktop, game console, server, calculator
goals: function, performance, reliable, cost/manufacturing, energy efficient, time to market, security

important differences:

age of discipline
automated mass production
rates of change: all 3 factors (tech, computer, goal) are changing quickly
boot-strapping effect: better computers help next generations

design goals:

functional
- need to be correct
- what functions should it support?
reliable
- does it continue to perform correctly?
- hard vs soft faults
high performance
- 'fast' is meaningful only in the context of a set of important tasks
- not just GHZ
low cost
- per unit manufacturing cost (wafer)
- cost of making 1st chip (mask)
- design cost (huge teams)
low power
- energy in (battery life, cost electricity)
- energy out (cooling)
secure?
- can it leak protected info?

About security:

architecture: timing independent functional behavior of a computer
microarchitecture: implementation techniques to improve performance
meltdown: leaks kernel memory; hw & sw fixes exist
spectre: leaks memory outside of bound and sandboxing
ECE552 focuses on microarchitectual techniques for performance (important to understand ramifications of those techniques)

technology push

what do 1867-1999 (133 yrs) and 2000-2001 (2 yrs) have in common?
answer: equal progress in processor speed (1GHz vs. 2GHz)
this is driven by moore's law: devices (transistors per chip doubles every 18-24 months)
computer architects turn additional resources into
- speed
- power savings
- functionality

performance growth:

unmatched by any other industry [John Crawford]
doubling every 20 months (1986-2002): 800x
doubling every 24 months (1978-2003): 6000x

technology trends:

moore's law
- continued (at least so far) transistor miniaturization
- absolute improvements in density, speed, power, cost
- but slowing dramatically since 2012
changes quickly and with respect to each other
- e.g. memory density increases faster than its speed

the microprocessor revolution:

1980
- enough transistors (50k) to put full processor on a single chip
- huge perf advantage - fewer inter-chip crossings
even bigger manufacturing advancement: 1 component
microprocessors have created new market segments: desktop, laptops, cameras
and replaced incumbents in existing segments
- microprocessor-based clusters replaced supercomputers, mainframes
- microprocessor-based servers replaced minicomputers

how are growing transistor counts utilized?

implicit parallelism
- extracting implicit instruction-level parallelism (ILP)
  1. pipelining enables increasing clock frequency
  2. caches necessary because of increased clock frequency
- deeper pipelining, branch speculation
- multiple issue, super scalar
- dynamic scheduling (out-of-order execution)
explicit parallelism
1. support data and thread-level parallelism; hw provides parallel resources; sw uses code to use them
2. hw support for multithreaded programs
  - coherent caches, sync primitives

application pull

corollary to moore's law: cost halves every two years: in a decade you can buy a computer for less than its sales tax today. - Jim Gray
computers cost-effective for
- national security - weapon design
- enterprise computing - banking
- departmental computing - computer-aided design
- personal computer - spreadsheets, email, web
- pervasive computing - prescription drug labels

application specific designs

the course is mostly about general-purpose cpus
there is profitable segment of application-specific cpus
- with some critical domain-specific functionality in hardware: graphics engines, physics engines
- much more effective (performance, power) than software - but expensive (more likely to go obsolete than gpcpus)
- e.g. emotion engine (ps2), ipod, machine learning (google's tpu)

layers of abstraction

only way of dealing with complex systems
architects need to understand computers at many levels
- instruction set architecture
- microarchitecture
- systems architecture
- technology
- applications

+------+ +-------+ +--------+
|  app | |  app  | |compiler|
+------+ +-------+ +--------+
+---------------------------+
|     OS, device drivers    |   us
+---------------------------+ <-----+
+------+ +-------+ +--------+ <-----+
|  IO  | |memory | |processr|
+------+ +-------+ +--------+
+---------------------------+
|circuits, devices, material|
+---------------------------+

instruction set architecture (ISA) facilitates implementation of software layers.
this course: design of processor, memory, i/o to implement isa
touch on other layers: compilers, os, circuits

instruction set architecture (ch 3.2)

hardware/software interface
- software impact
  - support OS functions: restartable instructions, memory relocation and protection
  - a good compiler target: if simple
  - dense: improve mem performance
- hardware impact
  - efficient impl (across generations)
  - parallel impl: no 'serial' bottlencks
- abstraction without interpretation

microarhichitecture

register-transfer-level (RTL) design
implement instruction set
exploit capabilities of technology
- locality and concurrency
iterative process
- generative proposed architecture
- estimate cost
- measure perf
delivering more perf: sequential and parallel applications
- deep pipelining
- multiple issue
- dynamic scheduling
- branch prediction/speculation
- multi-core

performance

empirical evaluation

metrics
- performance <- focus
- cost, power, reliability
often more important in combination than individually
- performance/cost (MIPS/$),
- performance/power (MIPS/W): GOPS/W for tpu
basis for design and purchase decisions

performance

performance metrics
- latency (execution time): time required to finish a fixed task
- throughput (bandwidth): number of tasks completed in a fixed time
reporting: benchmarking and averaging
cpu performance equation and performance trends
very different: throughput can exploit parallelism; latency cannot

eg. d=10 miles, car has cap= 5, speed = 60 mi/hr. then latency = 10 mi / 60 mi/hr = 10 min. throughput = 15 people/hr (3 round trips / hr).

bus has cap=60, speed=20 mi/hr. then latency=30 mins, throughput=60 people/hr.

performance improvement

process A is X times faster than processor B if
- latency(P, A) = latency(P, B) / X
- throughput(P, A) = throughput(P, B) * X
processor A is X% faster than processor B if
- latency(P, A) = latency(P, B) / (1 + X/100)
- throughput(P, A) = throughput(P, B) * (1 + X/100)
(100% speedup is 2 times)

eg. for latency, car is 3 times (200%) faster than bus; for throughput, bus is 4 times (300%) faster than car.

what is 'P':

a program: which one?
an actual target workload?
- + accurate
- - not portable, not repeatable, overly specific
- - big program - hard to pinpoint problems
some representative benchmark programs (suites)?
- + portable/repeatable, pretty accurate
- - hard to pinpoint problems
- - may not be exactly what one runs
some small kernel benchmarks (micro-benchmarks)
- e.g. loop adding numbers
- + portable/repeatable, easy to run
- + small - easy to pinpoint problems
- - not representative of complex behaviours in real programs

adding/averaging perf numbers

can add latencies: latency(P1+P2, A) = latency(P1, A) + latency(P2, A)
cannot add throughputs like this
throughputs: throughput(P1+P2, A) = 2 / [(1/throughput(P1, A)) + (1/throughput(P2, A))]
same goes for means
- arithmetic: $\frac{1}{N}\sum_{P=1}^N\mathrm{latency}(P)$ $\frac{1}{N} \sum_{P = 1}^{N} latency (P)$
  - for units proportional to time, e.g. latency
- harmonic: $\frac{N}{\sum_{P=1}^N\frac{1}{\mathrm{throughput}(P)}}$ $\frac{N}{\sum _{P = 1}^{N} \frac{1}{throughput ( P )}}$
  - for units inversely proportional to time, e.g. throughput
- geometric: $\sqrt[N]{\prod_{P=1}^N\mathrm{speedup}(P)}$ $N \prod_{P = 1}^{N} speedup (P)$
  - for unitless quantities, e.g. speedups
- we use the right avg based on the metric

iron law of performance

multiple aspects to performance: helps to isolate them
$\mathrm{latency}(P,A)=\frac{\mathrm{seconds}}{\mathrm{program}}=\frac{\mathrm{instrs}}{\mathrm{program}} \cdot \frac{\mathrm{cycles}}{\mathrm{instr}} \cdot \frac{\mathrm{seconds}}{\mathrm{cycle}}$
instructions/program (dynamic instr count): function of program, compiler, ISA
cycles/instr (CPI): function of program (float instr vs. ints), compiler, ISA, microarchitecture
seconds/cycle (clock period): function of μarchitecture, technology
for low latency (better perf), we want to minimize all three
- hard: often pull against each other

cycles per instruction

cycle/instr is for average instruction
IPC = 1/CPI
different instrs have different cycle costs: e.g. int add takes 1 cycle, fp divide takes >10
assumes we know something about instruction frequencies

eg. a program executes equal int, FP, and mem operations. int is 1 cycle, FP is 3 cycles, mem is 2 cycles. then CPI = (1 + 3 + 2) / 3 = 2.

caveat: this sort of calculation ignores dependency.

measuring CPI

CPI & exec time are measured using
- exec time: time (unix): wall clock + cpu + system
- CPI = cpu time / (clock period * dynamic instr count)
- how is dynamic instr count measured? (eg. pin)
- want CPI breakdowns (e.g. CPI_CPU, CPI_MEM) to see what to fix

Week 2. Sep 15

improving CPI

historically, clock accounts for 70%+ of perf improvement
this has changed:
- deep pipelining is now power efficient
- physical speed limits are approaching

eg. given processor with instr frequencies and costs

int alu: 50%, 1 cycle
load: 20%, 5 cycles
store: 10%, 1 cycle
fp alu: 20%, 2 cycles

CPI is 50% * 1 + 20% * 5 + 10% * 1 + 20% * 2 = 0.5 + 1 + 0.1 + 0.4 = 2.

which change would improve perf more?

branch prediction to reduce branch cost to 1 cycle: CPI is 1.8.
a bigger data cache to reduce load cost to 3 cycles: CPI is 1.6. <-

speedup = old time / new time = $\frac{\mathrm{IC}\cdot\mathrm{old CPI}\cdot \mathrm{old t}}{\mathrm{IC}\cdot\mathrm{new CPI}\cdot \mathrm{new t}}$ =2/1.6=1.25 (25%).

eg. given processor

alu: 45%, 1 cycle
load: 20%, 1 cycles
store: 15%, 2 cycles
fp alu: 20%, 2 cycles

suppose we reduce store 1 cycle, but slow down clock by 20%.

old CPI = 0.45*1+0.2*1+0.15*2+0.2*2 = 0.45+0.2+0.3+0.4 = 1.35
new CPI = 0.45*1+0.2*1+0.15*1+0.2*2 = 0.45+0.2+0.15+0.4 = 1.2
speedup = old time / new time = $\frac{\mathrm{IC}\cdot1.35\cdot t}{\mathrm{IC}\cdot1.2\cdot\frac{1/0.8}{t}}$ =0.9 (slowdown)

this is example of Amdahl's law - do not want to speed up small fraction at cost of the rest.

  ^
  |
n |
  |
  |
  |
  |
1 +---------+--------+
  |  f      | 1-f    |
  +---------+--------+---------->
                           time

  ^
  |
n |----+
  |    |
  |    |
  |    |
  | f  |
1 +    +--------+
  |    |   1-f  |
  +----+----+---+----+---------->
                           time

let f be fraction that can run in parallel (be sped up)
1-f be fraction that must run sequentially
n is number of cores
then speedup = $\frac{1}{(1-f)+f/n}$ . as n -> $\infty$ , speedup -> $\frac{1}{1-f}$ .

good ideal scaling for modest number of cores
large number of cores require more parallelism
amdahl's is not just about parallelism
f -> fraction we can speed up
performance is always limited by the sequential fraction (1-f)

pipelining

the sequential model

implicit model of all modern commercial ISAs
- called von Neuman, but in ENIAC design before
basic feature: program counter (PC)
- defines total order on dynamic instruction: next PC is ++PC instr unless says otherwise
- order and named storage define computation: value flow from instr X to instr Y via storage A iff X names A as its output, and Y comes after X in the total order and Y names A as its input

processor logically executes loop

instr execution is assumed to be atomic
instr X finishes before X+1 starts

fetch PC <---+
decode       |
read inputs  |
execute      |
write output |
next PC   ---+

alternatives have been proposed: e.g. dataflow [dennis, 1974/75].

single cycle datapath

datapath:
- functional units (ALU), registers, memory interface D$ (data cache)
control: decode portion
- muxes (ovals), write enables (red lines, regulate flow of data in datapath)
- translate ops into control signals

breaking instruction into steps

instruction fetch (F)
- fetched from mem at address indicated by PC
- increment PC to point to next instruction in sequence
instruction decode (D)
- decode instructions and find type
- read registers
execution (X)
- ALU performs arithmetic/logic operation (arih instrs)
- compute memory addr (load/store)
- if branch, compute target PC and update
memory access (M)
- contents of mem[addr] are fetched
- contents of mem[addr] are modified
write back (W)
- write instruction result to register

multi-cycle

add latches to create the multicycle implementation so clock cycles are shorter.
load is longest (yellow)

single vs. multi-cycle

single-cycle is hardwired
- low CPI (=1), long clock period (accommodate slowest instr)
multi-cycle: micro-programed / state machine
- shorter clock period, higher CPI

eg. single cycle has clock speed = 50ns, CPI=1. then performance is 50ns/instr.

multiple-cycle has 20% branch (3 cycles), 20% load (5 cycles), 60% ALU (4 cycles). let us say clock period = 11ns. CPI = 0.2*3 + 0.2*5 + 0.6*4 = 4. perf = 44 ns / instr.

(why not 50/5=10ns? not every stage is executed, and not every stage has same required clock period.)

can we have both low CPI and short clock period? not if datapath executes only one instruction at a time.

latency vs throughput:

latency: no good way to make a single instr go faster
throughput: we do not care about single instr latency. the goal is to make program go faster (overall) - drive down average CPI.

use pipelining

MULTI-CYCLE:
instr0: [fetch] [decode] [exec]
instr1:                  [fetch] [decode] [exec]

PIPELINED:
instr0: [fetch] [decode] [exec]
instr1:         [fetch]  [decode] [exec]
instr2:                  [fetch]  [decode] [exec]

improve instr throughput by overlapping execution of multiple instructions
when instr advances from stage 1 to stage 2, allow next instr to enter stage 1
"instr-stage parallelism"
individual instructions take same # of stages
but instr enter and exit the pipeline at faster rate

5-stage pipelined datapath

temporary values (PC, IR, A, B, O, D) are re-latched every stage.
- reason: 5 instructions may be in pipeline at once, do they share single PC?
- notice, PC not latched after ALU stage
five stages: F, D, X, M, W
latches named by stages they separate: F/D, D/X, X/M, M/W

there is one single-cycle controller, but pipeline the control signals:

terminology and foreshadowing:

scalar pipeline: 1 instr per stage per cycle
- alternative: superscalar pipeline: multiple instrs per stage per cycle
in-order pipeline: instr enter execute stage in program order
- alternative: out-of-order pipeline: out of program order
pipeline depth: number of stages in the pipeline

eg. given three instrs

                1 2 3 4 5 6 7 8 9
ADD r1,r2->r3   F D X M W
LW #0(r5)->r4     F D X M W         (load)
SW r6->#4(r7)       F D X M W       (store)

ADD is noop at M stage, and SW is noop at W stage to help instrs are executed in order.

pipelining

balanced: all steps should take approximately same time. does not make sense to optimize any stage that is not the longest.
instrs must pass through all stages and in same order even if some are unneeded.
buffering: not all stages take same time
independent computation
- no relationship between work units
- minimize pipeline stalls

eg. given 20% branch, 20% load, 60% ALU. suppose clock period is 12ns (50/5 stages + overhead). CPI = 1 (each instr takes 5 cycles, but 1 instr completes every cycle). perf = 12 ns / instr.

actually CPI = 1 + some penalty for pipelining. say CPI = 1.5, then perf = 18ns/instr.

why is pipeline clock period longer?

pipeline registers add delay
pipeline stage have different delays; clock period is max delay
extra bypass logic

why is pipeline CPI > 1?

CPI for scalar in-order pipeline is 1 + stall penalties
stalls used to resolve hazards
- hazard: condition that jeopardizes sequential illusion
- stall: pipeline delay to restore the sequential illusion
CPI = 1 + stall-freq1*stall-cyc1 + stall-freq2*stall-cyc2 + ...
- penalities add: stalls generally do not overlap in in-order pipelines

make common case fast (MCCF)

long penalties are ok if they happen rarely
stalls also have implications for ideal number of pipeline stages (diminishing returns)

managing a pipeline

proper flow requires two pipeline operations
- mess with latch write-enable and clear signals to achieve
operation I: stall
- effect: stop instr in current stage
- use: make younger instrs wait for older instrs to complete
- impl: de-assert write enables for pipeline registers
operation II: flush
- effect: remove instr from current stage
- use: control (later)
- impl: assert clear signals
both must be propagated to younger instrs

data hazards

dependence and hazards

dependence: relationship that serialize two instructions
- data: 2 instrs use same value or storage
- control: 1 instr affects whether another instr executes
hazard: dependence cause potential incorrect execution
- possibility of using wrong data, corrupting data or execution flow
- can be fixed with stalls - instr stays in the same stage for multiple cycles

read-after-write (RAW)

ADD r2,r3->r1
SUB r1,r4->r2

problem: if we swapped add and sub, then sub will have wrong value
this is true dependence: value flows through this true dependence. using a diff output register for add will not help.

eg. internal forwarding

                   1  2  3  4  5  6  7  8
ADD r1, r2 -> r3   F  D  X  M |W
LW #0(r3) -> r4       F  D  X  M  W
ADDI r3, #1 -> r6        F  D  X  M  W
SW r3 -> #0(r7)             F |D  X  M  W

ADD is writing to r3 currently
LW reads r3 2 cycles ago
ADDI reads 1 cycles ago
SW reading r3 this cycle - correct (internal forwarding WD)
- reading from same register; no hazard detection needed

Week 3. Sep 22

RAW: detect and stall

stall logic: detect and stall reader in D:
- (F/D.rs1 && (F/D.rs1 == D/x.rd || F/D.rs1 == X/M.rd))
- || (F/D.rs2 && (F/D.rs2 == D/x.rd || F/D.rs2 == X/M.rd))
- de-assert write-enable at PC+=4 so no next instr is fetched
- add no-op between F/D and D/X so instr will not execute
reevaluate every cycle until no longer true, and pipeline will continue executing
no checking in W stage (internal forwarding)
+ low cost, simple; - IPC degraded (RAW common in code)

eg. D and W share regfile

each gets regfile for half a cycle
1st half W writes, 2nd half D reads
2nd cycle stall
d* = data stall, p* = propagated stall

                  1  2  3  4  5  6  7  8  9  10
ADD  r1,r2 -> r3  F  D  X  M  W
LW   #0(r3) -> r4    F  d# d* D  X  M  W
ADDI r3,1 -> r6         p# p* F  D  X  M  W
SW   r3, #0(r7)                  F  D  X  M  W

reducing RAW stalls with bypassing

bypass (forward) data directly to input of X or M stage
MX: from beginning of M to the input of X (blue)
WX: from beginning of W to the input of X (pink)
WM: from beginning of W to the input of M (green)

suppose LW #4(r3) -> r1 is in X stage, ADD r1, r2 -> r3 is in M stage, then LW can get r3 from the output of ADD.

logic:

stall logic controls latches; bypass logic controls mux inputs
complement one another: can't bypass -> must stall
ALU-A input mux bypass logic:
- (X/M.rd == D/X.rs1) -> 1
- (M/W.rd == D/X.rs1) -> 1
- else -> 2

eg. full bypassing using MX bypass

               1  2  3  4  5  6  7  8  9  10
ADD r2,r3->r1  F  D  X |M  W
SUB r1,r4->r2     F  D |X  M  W

eg. full bypassing using WX bypass

               1  2  3  4  5  6  7  8  9  10
ADD r2,r3->r1  F  D  X  M |W
LW #0(r7)->r5     F  D  X  M  W
SUB r1,r4->r2        F  D |X  M  W

eg. WM bypass

               1  2  3  4  5  6  7  8  9  10
LW #0(r2)->r1  F  D  X  M |W
SW r1->#0(r4)     F  D  X |M  W

stalling-on-load:

               1  2  3  4  5  6  7  8  9  10
LW #0(r2)->r1  F  D  X  M |W
SUB r1,r4->r2     F  d* D |X  M  W

must stall for one cycle
stall = (D/X.op == LW) && ((F/D.rs1 == D/X.rd) || (F/D.rs2 == D/X.rd && F/D.op != SW))
rs1 holds base addr for SW, rs2 holds data for SW

performance impact of load/use penalty

assume branch 20%, load 20%, store 10%, other 50%
50% of loads are followed by dependant instruction
CPI = 1 + 0.2*0.5*1 = 1.1

write-after-write (WAW)

ADD r2,r3->r1* -+
SUB r1,r4->r2   |
OR  r3,r6->r1* <+

compiler effects: scheduling problem (reordering of instrs)
- artificial: no value flows through dependence; eliminate by using different output reg name for r1
pipeline effects: does not affect in-order pipelines with single cycle execution operation
- can have WAW hazards with multicycle ops (multiple execute cycles)

write-after-read (WAR)

ADD r3,r2*->r1
SUB r4,r5->r2*
OR r1,r3->r6

compiler effects: scheduling problem (solve by using different output reg names)
pipeline effects: does not happen in simple inorder pipeline (even multicycle)
- can happen with out-of-order execution

remarks:

no read-read hazards (reads are independent)
only one hazard happens for an instr

some instructions take more execution cycles

                         +--+  +--+
                         |X |  |M |
                         +--+  +--+
+---+  +---+      +--+ +--+ +--+ +--+ +--+ +--+     +---+
| F +--> D +----> |M1| |M2| |M3| |M4| |M5| |M6+---->+ W |
+---+  +---+      +--+ +--+ +--+ +--+ +--+ +--+     +---+
                        +--+ +--+ +--+
                        |A1| |A2| |A3|
                        +--+ +--+ +--+
                  +---------------------------+
                  |||||||||||||||||||||||||||||
                  +---------------------------+
                            div

long ops: RAW stalls more frequent
WAW hazards are possible: instrs no longer reach W in order
WAR hazards are not possible: reg read always in D

eg.

                  1  2  3  4  5  6  7  8  9 10
DIV.S f0,f1->f2   F  D  X  X  X  X  X |W
S.S f2->#0(r1)       F  d* d* d* D  X |M  W     (!!)
ADD.S f0,f1->f2         F  D  X  X  W
...
ADD.S f2,f3->f4                        F  D  X
                    wanted f2 overwritten ^

option 1: stall younger instr (ADD.S) at W
- + simple and intuitive; - lower perf, cascading stalls
option 2: cancel older instr (DIV.S) writeback
- + no perf loss; - complex: what if exception

structural hazards: resource needed twice in 1 cycle

e.g. multiple WB in 1 cycle
e.g. shared I/O
can fix by stall (s*)

               1  2  3  4  5  6  7  8  9
LW #0(r1)->r2  F  D  X  M  W
ADD r4,r3->r1     F  D  X  M  W
SUB r5,r3->r1        F  D  X  M  W
AND r3,r4->r6           s* F  D  X  M  W

to fix: proper ISA/pipeline design

best to avoid by design: each instr uses every structure exactly once, for at most 1 cycle & always in same stage relative to F

control hazards

steps needed for branch: br (Rj op Rk) displ

comparison s/t Rj and Rk
- set flag for output if comparison
compute target (instr) addr = PC + displ
- modify PC if needed
we add ALU to D or X stage to compute target

option 1: always stall

at decode: know its a branch and stall
- insert nops for 2 cycles (c*)
- then after X we know the branch outcome and can fetch next instr

                1  2  3  4  5  6  7  8  9
ADDI r1,#1->r3  F  D  X  M  W
BNEZ r3,targ       F  D  X |M  W
SW r6,#4(r7)          c* c*|F  D  X  M  W

CPI_BASE = 1
CPI = 1 + 0.2*0.2 = 1.4

option 2: assume not-taken. branch 20%, other 80%, 75% of branches are taken.

only pay 2 cycle penalty for taken branches
CPI = 1 + 0.2*0.75*2 = 1.3

                      1  2  3  4  5  6  7  8  9
      ADDI r1,#1->r3  F  D  X  M  W
      BNEZ r3,targ       F  D  X  M  W
      SW r6->#4(r7)         f' d' X  M  W
      ADD r2,r1->r4            f' D  X  M  W
targ: ADD r4,r->r4                F  D  X  M  W

f', d' we need to speculative
mis-speculation recovery: what to do if branch prediction was wrong
- note branch resolves in X
- younger instrs in F, D haven't changed permanent state
- flush instr in F/D, D/X pipeline register

if branch is taken:

                      1  2  3  4  5  6  7  8  9
      ADDI r1,#1->r3  F  D  X  M  W
      BNEZ r3,targ       F  D  X  M  W
      SW r6->#4(r7)         F  D  -  -  -
      ADD r2,r1->r4            F  -  -  -  -
targ: ADD r4,r->r4                F  D  X  M  W

note 2 instrs cancelled - did not reach stage where they update reg or mem.

branch prediction:

simple strategy assumes not-taken, but taken branches are more common
want a predictive strategy
- yield taken or not taken prediction with a high probability of being right
important for
- deeper pipelines
- out-of-order execution (heavily dependant on prediction)

speculation

speculative execution: execute before all parameters are known with certainty
correct speculation: + avoids stalls, improve perf
mis-speculation:
- - must flush/abort incorrect instrs
- - must undo incorrect changes if any (recover pre-speculative state)
want: %correct * gain > [(1-%correct) * penalty]

control speculation

guess branch target, start fetching at guessed position
execute branch to verify guess
- correct: keep going
- mis-spec: flush
do not write regs or mem until prediction verified
gain = 2 cycles
penalty = 0 cycles (mis-spec is no worse than stalling)
%correct = branch prediction
- static (compiler) ~ 85%
- dynamic (hardware) ~ 95%

eg. assume not-taken. branch 20%, other 80%, 75% of branches are taken. branch predicted with 95% accuracy. then CPI = 1 + 2*0.2*(1-0.95) = 1.02.

dynamic branch prediction

part I: direction predictor
- applies to conditional branches only
- predicts taken or not taken
- hard
part II: target predictor
- applies to all control transfers (func calls)
- supplies target PC
- done in F stage, determine if instr is control prior to D stage
- easy

anatomy

                      all instrs or       PC and/or
                      only branches?      global/local
                                          history
+----------+        +------------+       +------------+
|program   |------->| event      |------>| prediction |
|execution |        | selection  |       | index      |
+----------+        +------------+       +------------+
     ^                                 ^       |
      .                             .          |
       .                         .             |
        .                     .                |
recovery?.                 .                   v
          . +------------+           +-----------+
           .|  feedback  |<----------|prediction |  saturating counters,
            |            |---------->|mechanism  |  markov,
            +------------+           +-----------+  perceptrons, etc.
            using branch outcome,
            update pred. mechanism,
            update history

branch direction prediction

predict in fetch stage
direction predictor (DIRP)
- map conditional-branch PC to taken/not-taken decision
- - difficult to do well
- individual branches often unbiased or weakly biased
branch prediction buffer (BPB)
- 1-bit predictor: simplest
  - PC indexes table of bits (0=N,1=T) (inf large), no tags
  - essentially: branch will go same way it went last time

eg. consider the inner loop only. assume path taken last time.

for (i = 0; i < 100; i++)
    for (j = 0; j < 3; j++)

predict N T T T N T T T N T T T
outcome T T T N T T T N T T T N
        ^     ^ ^     ^ ^     ^

there are 2 built-in mispredictions per loop.

Week 4. Sep 29

two-bit saturating counters (2bc):

replace each single-bit prediction with (0,1,2,3) = (strong not-taken, weak not-taken, weak taken, strong taken)
force DIRP to mis-predict twice before 'changing its mind'

T
    +-----------------+    T    +-----------------+
 +--|  predict taken  |<--------|  predict taken  |
T|  |       11        |         |       10        |
 +->|       TT        |-------->|       TN        |
    +-----------------+    N    +-----------------+
                                  |             ^
                                N |             | T
                                  v             |
    +-----------------+    N    +-----------------+
 +--|predict not taken|<--------|predict not taken|
N|  |       00        |         |       01        |
 +->|       NN        |-------->|       NT        |
    +-----------------+    T    +-----------------+

store and accessing predictions

suppose our table is limited. if we use k bits from PC, then its size is 2^k entries
aliasing: 2 branches with different PCs access the same counter
- this is ok, since we just do a prediction
we could have tags, but its size may overwhelm the actual data (cache)

eg. with k = 10 PC bits, then the table size is 2^10*2=2048 bits. tag = 32 - 10 (index) - 2 (lower bits) = 20 bits. size is 2^10*(2+20)=22 kbits.

+------+----+-+       +---+ 2^k rows
| tag  | idx| |       |---| PBT
+------+----+-+       |---|
         |            |---|
         +----------->|---|
                      +---+

eg. using 2bc

for (i = 0; i < 100; i++)
    for (j = 0; j < 3; j++)

predict N n t T t T T T t T T T
outcome T T T N T T T N T T T N
        ^ ^           ^       ^

this fixes pathology (changing minds too quickly)
requires some training

correlated branch prediction

have a history register (instead of PC to index branch prediction table)
record last k branch outcomes by shifting

eg. using corrs:

state/prediction BHR=NN N- T  T  T  T  T  T  T  T  T  T  T
                 BHR=NT N  N- T  T  T  T+ T  T  T  T+ T  T
                 BHR=TN N  N  N  N  N- T  T  T  T+ T  T  T
                 BHR=TT N  N  N- T- N  N  N- N- N  N  N- T-
outcome           N  N  T  T  T  N  T  T  T  N  T  T  T  N

it does not get better. BHR is not long enough to capture patterns.

eg. using 3 bits of history:

                                          v
state/prediction BHR=NNN N- T  T  T  T  T  T  T  T  T  T  T
                 BHR=NNT N  N- T  T  T  T  T  T  T  T  T  T
                 BHR=NTN N  N  N  N  N  N  N  N  N  N  N  N
                 BHR=NTT N  N  N- T  T  T  T+ T  T  T  T+ T   <<
                 BHR=TNN N  N  N  N  N  N  N  N  N  N  N  N
                 BHR=TNT N  N  N  N  N  N- T  T  T  T+ T  T   <<
                 BHR=TTN N  N  N  N  N- T  T  T  T+ T  T  T   <<
                 BHR=TTT N  N  N  N+ N  N  N  N+ N  N  N  N+  <<
outcome                  T  T  T  N  T  T  T  N  T  T  T  N

note prediction reaches a steady state of perfect accuracy. only 4 patterns are active.

correlated predictor design choices:

choice 1: one global BHR or one per PC (local)?
- each one captures different kinds of patterns
- global often better - captures local patterns for tight loops
choice 2: how many history bits (BHR size)?
- tricky
- long BHR good for some, short better for others
- BPB utilization decreases with longer BHR - many history patterns never seen
- using PC & BHR allow multiple PCs to dynamically share BPBs
- long BHR requires longer training period

two-level predictors

first level: history register or table
- global (G) or per-address PC (P)
second level: prediction table
- global (g) or per-address PC (p)

eg. global history register (G) and global prediction table (g):

      +---+          +-------+
8bits |   |          |       | 2^8 rows
      | G |----8---> |   g   |
      |   |          |       |
      +---+          +-------+
                    2-bit counters

size = 8 + 2^8*2 = 520 bits.

eg. global history register (G) and per-address prediction table (p):

                        choose k=2 bits
                     +----+--+--+
           branch PC |    |  |  |
                     +----+--+--+
                           | 2
                           v
      +---+          +---------------+
8bits |   |          |+-+ +-+ +-+ +-+| 2^8 rows
      | G |----8---> || | | | | | | ||
      |   |          |+-+ +-+ +-+ +-+|
      +---+          +---------------+
                      2^k=4 tables
                  private predictor tables

size = 8 + 2^8 * 2^2 * 2 = 2056 bits

eg. per-address history register (P) and global prediction table (g):

branch PC
+----+--+--+
|    |  |  | choose 6 bits
+----+--+--+
      |             +----------+         +---------+
      +--6--------> |          |         |         |
                    +----------+         |         |
                    +----------+---8---->|    g    |
              2^6   |          |         |         | 2^8 rows
              rows  +----------+         +---------+
                      8 bits               2 bits
                private history table

size = 2^6 * 8 + 2^8 * 2 = 1024 bits

eg. per-address history register (P) and per-address prediction table (p):

branch PC
+----+--+--++
|    |  |  ||
+----+--+--++
      |   |
      |   +--2-----------------------------v
      |             +----------+         +---------------+
      +------6----> |          |         |+-+ +-+ +-+ +-+| 2^8
                    +----------+         || | | | | | | || rows
                    +----------+---8---->|| | | | | | | || (2bits)
              2^6   |          |         |+-+ +-+ +-+ +-+|
              rows  +----------+         +---------------+
                      8 bits                  4 tables
                private history table  private prediction tables

size = 2^6 * 8 + 2^8 * 2 * 4 = 2560 bits

hybrid (tournament) predictor [McFarling'93]:

attacks correlated predictor BPB problem
idea: combine two predictors
- simple BPB predicts history independent branches
- correlated predictor predicts only branches that need history
- chooser assigns simple BPB, move misprediction threshold

+--+
|PC|-----+-------------+-------+
+--+     |             v       v
+---+    v    +---+  +---+  +-------+
|GHR|-> xor ->|BPB|  |BPB|  |chooser|
+---+         +---+  +---+  +-------+
                |      |        |
                v      v        |
              .----------.      |
              |   mux    |<-----+
              '----+-----'
                   v

many direction prediction stretegies

perceptron-based predictiors (recent AMD procs)
lab 2
also need to predict target PC

branch target buffer (BTB)

a small cache (blackbox mapping from PC to target PC)
if hit, then this is a control instr & going to the target PC (if taken)
if miss, then this is not a control instr or one we have not seen before, or evicted
why use partial tag - ok to be wrong, just making predictions; aliasing is ok

zen4 BTB: 1.5K(L1) to 7K(L2) entries

why does BTB work:

because control instr targets are stable
- + direct condition branch
- + direct calls
- + direct jump instrs
- - indirect conditional branch (less well)
- indirect calls
  - + dynamically linked
  - - dynamically dispatched / virtual funcs
- - indirect condition jumps (switch)
- - (indirect) returns (but common)
direct means constant target, indirect means register target

return address stack (RAS)

return addresses are easy to predict without a BTB
hardware return address stack tracks call sequence
- call pushes PC+4 into RAS, predict for return is RAS[TOS]
- how to tell if an instr is a return before decoding it - attach pre-decode bits to I$
  - written after 1st time instr executes
  - useful bits: return? conditional branch?
this happens in fetch stage

branch prediction summary

perf requirement for pipelined processors
importantance of accuracy increases with depth and width of pipeline
basic building block: 2-bit saturating counter
predict direction and target

handling interrupts/exceptions:

interrupt: external (e.g. timer, IO)
exception: internal (e.g. divide by zero, page fault, mem violation, illegal instr); don't need hardware
can occur at any stage except W
- page fault: F, M
- illegal op code: D
- divide by zero: X
upon detecting interrupt:
- OS saves processor state
- interrupt handling routine: abort or correct
- for instrs before i in program order currently in pipeline:
  - complete normally
  - results are part of saved processor state
- for instr i and after it already in the pipeline:
  - converted to nops
- saved PC corresponds to the PC of instr i
- called precise state / precise interrupts
upon detecting exception
- flag inserted into pipeline register
- instr converted to noop
- exception handled when flag reaches M/W pipeline reg
  - because exceptions are handled in program order, not handled in temporal order

eg. handling exceptions

               1  2  3  4  5  6
DIV r1,r0->r2  F  D  X* M  W <- handle here
ADD r3,r4->r5     F* D  X  M  W

X*: div/0
F* page fault

eg. out of order

                 1  2  3  4  5  6  7  8  9  10
DIV.S f0,f1->f2  F  D  E/ E/ E/ E/ E/ W
S.S f2->[r1]        F  D  d* d* d* X  M^ W
ADD.S f0,f1->f0        F  D  E+ E+ W

M^: page fault

make it appear as if DIV.S finished and S.S, ADD.S have not started
allow DIV.S to writeback
flush S.S and ADD.S
- but ADD.S has already wrote back!
- can keep "undo" reg file - complicated
- can force WB to be inorder
invoke exception handler
restart S.S

eg. two simultaneous in-flight exceptions

                 1  2  3  4  5  6  7  8  9  10
DIV.S f0,f1->f2  F  D  E/ E/ E/ E/ E/ W
S.S f2->[r1]        F  D  d* d* d* X  M^ W
DIV.S f0,f4->f2        F  D  E\ E/ E/ E/ E/ W

M^: page fault
E\: div/0

interrupts must be handled in program order (S.S first)
- handler for S.S must see program as if DIV.S has not started
must defer interrupts until writeback and force in-order writeback
bottom line: maintaining precise state is important but hard

dynamic scheduling

problem wih in-order pipelines:

                 1  2  3  4  5  6  7  8  9  10  11
ADD.S f0,f1->f2  F  D  X  X  X |M  X
MUL.S f2,f3->f2     F  d* d* D |X  X  X  M  W
SUB.S f0,f1->f4        p* p* F  D  X  X  X  M  W

in cycle 4: MUL.S stalls due to RAW. OK - this is a fundamental problem
SUB.S stalls due to a pipeline hazard. it cannot advance since MUL.S is in its way
- this is only reason and is fundamental
can move SUB.S to hide the stall

static instruction scheduling:

issue: time at which instr begins to execute
schedule: order in which instrs execute
scheduling: re-ordering instrs to enable rapid issue
static: done by compiler
- requires knowledge of pipeline and program dependences
- requires large scheduling scope full of independent instrs
- e.g. loop unrolling - increases scope for loops

dynamic scheduling:

execute instrs in non-sequential (non-vonneumann) order
- +reduce RAW stalls
- +increase pipeline and functional unit (FU) utilization
  - - original motivation was to increase FP unit utilization
- + expose more opportunities for parallel issue (ILP)
  - - not in-order -> can be parallel
why build complex hardware if it can be done by software:
- + performance portability
  - don't want to recompile for new machine
- + more info available
  - mem address, branch predictions, cache misses
- + more register available
  - compiler might not have enough to fix WAR/WAW hazards
- + easier to do speculation and recover from misspeculation
  - flush instead of recovery code
- but compiler has much larger scope
  - compiler does as much as it can and hardware does the rest

instruction buffer

conceptually a bunch of latches for instrs - gives us scheduling scope
splits D into two pieces
- D1: accumulates decoded instrs into buffer in order
- D2: buffer sends instrs down rest of pipeline out of order

tomasulu's algorithm:

register renaming: removes WAR/WAW hazards
reservation stations (RS): instruction buffer
common data bus (CDB): brodcasts results to RS
first impl: IBM 360/91 [1967] (for FP units only)

true/data dependence (RAW)

instr i+1 uses result produced by instr i
transitive
data dependent instrs cannot execute simultaneously or be completely overlapped

name dependencies

occurs when 2 instrs use same reg/mem location but there is no data flow between
anti-dependence (WAR)
- instr i+1 writes a register that instr i reads
- original ordering must be preserved to ensure i gets correct value
output dependence (WAW)
- instr i and instr i+1 write the same register/memory location
- ordering must be preserved to ensure that value finally written corresponds to instr i+1

in hardware: change register names to eliminate WAR/WAW hazards
key: think of registers as names, not storage locations
- can have more locations than names
- can have multiple active versions of same name
map-table: maps names to most recent locations
- SRAM indexed by name
- on write: allocate new location, note mapping in table
- on read: find location of most recent write via lookup in map-table
- detail: must de-allocate locations at some point (later)

eg.

names: r1, r2, r3, r4
locations: p1, p2, p3, p4, p5, p6, p7, p8
original mapping: r1->p1, r2->p2, r3->p3, r4->p4
- p5-p8 are free

map table         free list
r1  r2  r3  r4
--------------
p1  p2  p3  p4    p5,p6,p7,p8
p5  p2  p3  p4    p6,p7,p8
p5  p6  p3  p4    p7,p8
p5  p7  p3  p4    p8
p8  p7  p3  p4

div r2,r3->r1  div p2,p3->p5
add r2,r1->r3  add p2,p5->p6
subi r4,4->r2  subi p4,4->p7
add r4,r2->r1  add p4,p7->p8

removes WAW and WAR dependencies
leaves RAW intact

Week 5. Oct 6

tomasulo organization

reservation stations:
- FU, busy, op
- Qj, Qk: source reg tags (RS# of RS that will produce input value)
- Vj, Vk: source reg value
map table:
- T: tag (RS#) that will write this reg
common data bus
- broadcasts <RS#, value> of completed instrs
tags interpreted as ready-bits++
- T == 0: value ready
- T != 0: value not ready; watch for CDB broadcast of T

new pipeline (FDSXW):

F: same as before
D: dispatch
- stall for structural hazard (RS full)
- if input reg ready, write ready value into RS, else read tag into RS
- set reg stations (map table) - rename; output reg to allocated RS#
S: issue
- wait for RAW hazard and structural hazards (FU busy)
- else read reg values from RS and send to execute
X: execute/memory
- same as before
W: writeback
- wait for structural hazards (CDB)
- if output reg status still match, clear tag & write result reg
- CDB broadcast to RS
  - if tag match, clear tag, copy value
- free RS entry

remark. stalls propagate to later instrs but waits do not.

value/copy-based regiseter renaming (/tomasulo-style):

names: architectural registers
storage locations: register file & reservation station
- values can & do exist in both
- reg file holds most recent value
- RS versions eliminate WAR hazards
storage locations referred to internally by RS# tags
- register table translates names to tags
- tag == 0 => value in reg file
- tag != 0 => value not ready & is being computed by RS# (e.g. 4)
CDB broadcasts vakyes wutg tags attached

eg.

L.S [r1+0]->f1 (allotted RS#2)
  maptable[r1]==0 => RS[2].vk=regfile[r1]
  maptable[f1]=RS#2
MUL.S f0,f1->f2 (alloted RS#4)
  maptable[f0]==0 => RS[4].vj=regfile[f0]
  maptable[f1]==RS#2 => RS[4].vk=RS#2
ADD.S f7,f8->f0
  can write regfile[f0] before MUL.S execs
L.S[r1+4]->f1
  can write regfile[f1] before MUL.S execs
  can write regfile[f1] before 1st L.S execs

reservation stations
RS# | FU | Busy | Op | Vj | Vk | Qj | Qk
2   | LD | YES  |L.S.|    |    | 0  |[r1]
4   |FP1 | YES  |MULS|    |RS#2|[f0]|

eg.
cycle 1:

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |yes |34+[R2] |Reg|T    
LD.S 34(r2)->f6  |c1|  |  |           |load2 |no  |        |f0 |
LD.S 45(r3)->f2  |  |  |  |           |load3 |no  |        |f2 |
MUL.S f2,f4->f0  |  |  |  |           +------+----+--------+f4 |     
SUB.S f6,f2->f8  |  |  |  |           |CDB                 |f6 |load1
DIV.S f0,f6->f10 |  |  |  |           |T     |V            |f8 |
ADD.S f8,f2->f6  |  |  |  |           |      |             |f10|     
-----------------+--+--+--+-----------+------+-------------+...|     
reservation stations                                       |r2 |     
FU   |busy|op   |Qj   |Qk   |Vj|Vk                         |r3 |     
add1 |no  |     |     |     |  |                           +---+--------
add2 |no  |     |     |     |  |                           |ex latencies
add3 |no  |     |     |     |  |                           |op |cycles  
mult1|no  |     |     |     |  |                           |ADD|2       
mult2|no  |     |     |     |  |                           |L.S|2       
                                                           |MUL|10      
                                                           |DIV|40

cycle 2

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |yes |34+[R2] |Reg|T    
LD.S 34(r2)->f6  |c1|c2|  |           |load2 |yes |45+[R3] |f0 |
LD.S 45(r3)->f2  |c2|  |  |           |load3 |no  |        |f2 |load2
MUL.S f2,f4->f0  |  |  |  |           +------+----+--------+f4 |     
SUB.S f6,f2->f8  |  |  |  |           |CDB                 |f6 |load1
DIV.S f0,f6->f10 |  |  |  |           |T     |V            |f8 |
ADD.S f8,f2->f6  |  |  |  |           |      |             |f10|     
-----------------+--+--+--+-----------+------+-------------+...|     
reservation stations                                       |r2 |     
FU   |busy|op   |Qj   |Qk   |Vj|Vk                         |r3 |     
add1 |no  |     |     |     |  |                           +---+
add2 |no  |     |     |     |  |
add3 |no  |     |     |     |  |
mult1|no  |     |     |     |  |
mult2|no  |     |     |     |  |

can have multiple loads outstanding

cycle 3

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |yes |34+[R2] |Reg|T    
LD.S 34(r2)->f6  |c1|c2|  |           |load2 |yes |45+[R3] |f0 |mult1
LD.S 45(r3)->f2  |c2|c3|  |           |load3 |no  |        |f2 |load2
MUL.S f2,f4->f0  |c3|  |  |           +------+----+--------+f4 |     
SUB.S f6,f2->f8  |  |  |  |           |CDB                 |f6 |load1
DIV.S f0,f6->f10 |  |  |  |           |T     |V            |f8 |
ADD.S f8,f2->f6  |  |  |  |           |      |             |f10|     
-----------------+--+--+--+-----------+------+-------------+...|     
reservation stations                                       |r2 |     
FU   |busy|op   |Qj   |Qk   |Vj|Vk                         |r3 |     
add1 |no  |     |     |     |  |                           +---+
add2 |no  |     |     |     |  |
add3 |no  |     |     |     |  |
mult1|yes |MUL.S|load2|     |- |[f4]
mult2|no  |     |     |     |  |

1st load starts executing - 2 cycles in X (c3-c4), so X=c4, not c3
f2 renamed => MUL will get value from Load2, not the register file
f4 ready, so value copied into Vk in RS

cycle 4

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |yes |34+[R2] |Reg|T    
LD.S 34(r2)->f6  |c1|c2|c4|           |load2 |yes |45+[R3] |f0 |mult1
LD.S 45(r3)->f2  |c2|c3|  |           |load3 |no  |        |f2 |load2
MUL.S f2,f4->f0  |c3|  |  |           +------+----+--------+f4 |     
SUB.S f6,f2->f8  |c4|  |  |           |CDB                 |f6 |load1
DIV.S f0,f6->f10 |  |  |  |           |T     |V            |f8 |add1 
ADD.S f8,f2->f6  |  |  |  |           |      |             |f10|     
-----------------+--+--+--+-----------+------+-------------+...|     
reservation stations                                       |r2 |     
FU   |busy|op   |Qj   |Qk   |Vj|Vk                         |r3 |     
add1 |yes |SUB.S|load1|load2|- |-                          +---+
add2 |no  |     |     |     |  |
add3 |no  |     |     |     |  |
mult1|yes |MUL.S|load2|     |  |[f4]
mult2|no  |     |     |     |  |

1st load finishes executing
2nd load starts executing
both f2 & f6 are renamed -> tags, puts into Qj & Qk

cycle 5

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |no  |        |Reg|T    
LD.S 34(r2)->f6  |c1|c2|c4|c5         |load2 |yes |45+[R3] |f0 |mult1
LD.S 45(r3)->f2  |c2|c3|c5|           |load3 |no  |        |f2 |load2
MUL.S f2,f4->f0  |c3|  |  |           +------+----+--------+f4 |     
SUB.S f6,f2->f8  |c4|  |  |           |CDB                 |f6 |
DIV.S f0,f6->f10 |c5|  |  |           |T     |V            |f8 |add1 
ADD.S f8,f2->f6  |  |  |  |           |load1 |mem(1)       |f10|mult2
-----------------+--+--+--+-----------+------+-------------+...|     
reservation stations                                       |r2 |     
FU   |busy|op   |Qj   |Qk   |Vj    |Vk                     |r3 |     
add1 |yes |SUB.S|     |load2|mem(1)|-                      +---+--------
add2 |no  |     |     |     |      |
add3 |no  |     |     |     |      |
mult1|yes |MUL.S|load2|     |      |[f4]
mult2|yes |DIV.S|mult1|     |      |[f6]

writeback: CDB available
CDB broadcasts to MT: if output tag matches, update reg val, clear tag
CDB broadcasts to RS: input tag matches (anyone wait on load1?) -> copy value into V field
free load1 RS entry
dispatch: no pending instrs writing f6 (regfile written in 1st half of cycle - internal forwarding)

cycle 6

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |no  |        |Reg|T    
LD.S 34(r2)->f6  |c1|c2|c4|c5         |load2 |no  |        |f0 |mult1
LD.S 45(r3)->f2  |c2|c3|c5|c6         |load3 |no  |        |f2 |
MUL.S f2,f4->f0  |c3|c6|  |           +------+----+--------+f4 |     
SUB.S f6,f2->f8  |c4|c6|  |           |CDB                 |f6 |add2
DIV.S f0,f6->f10 |c5|  |  |           |T     |V            |f8 |add1 
ADD.S f8,f2->f6  |c6|  |  |           |load2 |mem(2)       |f10|mult2
-----------------+--+--+--+-----------+------+-------------+...|     
reservation stations                                       |r2 |     
FU   |busy|op   |Qj   |Qk   |Vj     |Vk                    |r3 |     
add1 |yes |SUB.S|     |     |mem(1) |mem(2)
add2 |yes |ADD.S|add1 |     |       |[f2]
add3 |no  |     |     |     |       |
mult1|yes |MUL.S|     |     |mem(2) |[f4]
mult2|yes |DIV.S|mult1|     |       |[f6]

load2 writing result - anyone waiting?
- mult1 & add1: value copied from CDB into Vj and Vk
- maptable[f2] cleared -> copy value into regfile
  - no pending instr writing to f2
mult1 and add1 can issue - starting next cycle

cycle 7: no change

DIV.S and ADD.S waiting on values (RAW) - can't issue
MUL.S and SUB.S executing

cycle 8

SUB.S finishes executing (X=c8); nothing else changes

cycle 9

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |no  |        |Reg|T    
LD.S 34(r2)->f6  |c1|c2|c4|c5         |load2 |no  |        |f0 |mult1
LD.S 45(r3)->f2  |c2|c3|c5|c6         |load3 |no  |        |f2 |
MUL.S f2,f4->f0  |c3|c6|  |           +------+----+--------+f4 |     
SUB.S f6,f2->f8  |c4|c6|c8|c9         |CDB                 |f6 |add2
DIV.S f0,f6->f10 |c5|  |  |           |T     |V            |f8 |
ADD.S f8,f2->f6  |c6|c9|  |           |add1  |m-m          |f10|mult2
-----------------+--+--+--+-----------+------+-------------+...|
reservation stations                                       |r2 |
FU   |busy|op   |Qj   |Qk   |Vj     |Vk                    |r3 |
add1 |no  |     |     |     |       |
add2 |yes |ADD.S|     |     |m-m    |[f2]
add3 |no  |     |     |     |       |
mult1|yes |MUL.S|     |     |mem(2) |[f4]
mult2|yes |DIV.S|mult1|     |       |[f6]

ADD.S: both operands available -> can issue (S=c9)

cycle 10: no change

ADD.S starts executing
DIV.S still waiting
MUL.S still executing

cycle 11

ADD.S finishes executing (X=c11)

cycle 12

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |no  |        |Reg|T    
LD.S 34(r2)->f6  |c1|c2|c4|c5         |load2 |no  |        |f0 |mult1
LD.S 45(r3)->f2  |c2|c3|c5|c6         |load3 |no  |        |f2 |
MUL.S f2,f4->f0  |c3|c6|  |           +------+----+--------+f4 |     
SUB.S f6,f2->f8  |c4|c6|c8|c9         |CDB                 |f6 |
DIV.S f0,f6->f10 |c5|  |  |           |T     |V            |f8 |
ADD.S f8,f2->f6  |c6|c9|11|12         |add2  |(m-m)+f2     |f10|mult2
-----------------+--+--+--+-----------+------+-------------+...|
reservation stations                                       |r2 |
FU   |busy|op   |Qj   |Qk   |Vj     |Vk                    |r3 |
add1 |no  |     |     |     |       |
add2 |no  |     |     |     |       |
add3 |no  |     |     |     |       |
mult1|yes |MUL.S|     |     |mem(2) |[f4]
mult2|yes |DIV.S|mult1|     |       |[f6]

cycle 13-15: no change

MUL.S still executing (10-cycle op)
DIV.S still waiting for value

cycle 16

MUL.S finishes executing (X=c16)
mult2 (DIV.S) still waiting on mult1

cycle 17

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |no  |        |Reg|T    
LD.S 34(r2)->f6  |c1|c2|c4|c5         |load2 |no  |        |f0 |
LD.S 45(r3)->f2  |c2|c3|c5|c6         |load3 |no  |        |f2 |
MUL.S f2,f4->f0  |c3|c6|16|17         +------+----+--------+f4 |     
SUB.S f6,f2->f8  |c4|c6|c8|c9         |CDB                 |f6 |
DIV.S f0,f6->f10 |c5|17|  |           |T     |V            |f8 |
ADD.S f8,f2->f6  |c6|c9|11|12         |mult1 |M*f4         |f10|mult2
-----------------+--+--+--+-----------+------+-------------+...|
reservation stations                                       |r2 |
FU   |busy|op   |Qj   |Qk   |Vj     |Vk                    |r3 |
add1 |no  |     |     |     |       |
add2 |no  |     |     |     |       |
add3 |no  |     |     |     |       |
mult1|no  |     |     |     |       |
mult2|yes |DIV.S|     |     |M*f4   |[f6]

cycle 57

DIV.S finishes executing (X=c57)

cycle 58

instr status                          |      |Busy|Address |Map Table
instr            |D |S |X |W          |load1 |no  |        |Reg|T
LD.S 34(r2)->f6  |c1|c2|c4|c5         |load2 |no  |        |f0 |
LD.S 45(r3)->f2  |c2|c3|c5|c6         |load3 |no  |        |f2 |
MUL.S f2,f4->f0  |c3|c6|16|17         +------+----+--------+f4 |
SUB.S f6,f2->f8  |c4|c6|c8|c9         |CDB                 |f6 |
DIV.S f0,f6->f10 |c5|17|57|58         |T     |V            |f8 |
ADD.S f8,f2->f6  |c6|c9|11|12         |mult2 |M*f4/f6      |f10|
-----------------+--+--+--+-----------+------+-------------+...|
reservation stations                                       |r2 |
FU   |busy|op   |Qj   |Qk   |Vj     |Vk                    |r3 |
add1 |no  |     |     |     |       |
add2 |no  |     |     |     |       |
add3 |no  |     |     |     |       |
mult1|no  |     |     |     |       |
mult2|no  |     |     |     |       |

mult2 (DIV.S) writes back; maptable[f10] cleared; free mult2
D column: in-order dispatch; X column: out-of-order execution; W column: out-of-order completion

summary

hazard type	tomasulo
instr buffer/RS	stall in D - structural
FU	wait in S - structural
RAW	wait in S
WAR	none - renaming
WAW	none - renaming

dyanamic scheduling as loop unrolling:

three steps:
1. combine interations: increases scheduling scope -> more flexibility
2. pipeline schedule: reduce impact of RAW hazards
3. rename registers: rename away WAR & WAW violations that come from scheduling

eg. single-precision AX (SAX):

for (i = N; i>0; i--)
  Z[i] = A * X[i];

0: L.S X(r1),f0   // Loop
1: MUL.S f0,f2,f4 // A in f2
2: S.S f4,Z(r1)
3: SUBI r1,4,r1   // i in r1
4: BNEZ r1,Loop

consider two iterations: L.S, MUL.S, S.S, SUBI, L.S, MUL.S, S.S

RAW chains within each iteration: L.S -> MUL.S -> S.S
scheduling wants to hoist the 2nd L.S above the 1st S.S

assume mul takes 4 cycles; 1st load takes 8 cycles (cache miss), 2nd load 1 cycle (hit, after 1st load executes); R1 has 80; &Z[0] == &X[0].

cycle 1:

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |   |   |     |ld2|no  |    |      |f0 |ld1
MUL.S f0,f2->f4 |   |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |   |   |   |     |st1|no  |    |      |f4 |
SUBI r1,4->r1   |   |   |   |     |st2|no  |    |      |f6 |
BNEZ r1,Loop    |   |   |   |     |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |   |   |   |     |---+----+----+------|f10|        WAW
MUL.S f0,f2->f4 |   |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |   |   |   |     |T     |V            |r1 |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|no  |
mult2|no  |

cycle 2

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |   |     |ld2|no  |    |      |f0 |ld1
MUL.S f0,f2->f4 |c2 |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |   |   |   |     |st1|no  |    |      |f4 |mult1
SUBI r1,4->r1   |   |   |   |     |st2|no  |    |      |f6 |
BNEZ r1,Loop    |   |   |   |     |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |   |   |   |     |---+----+----+------|f10|
MUL.S f0,f2->f4 |   |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |   |   |   |     |T     |V            |r1 |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld1 |    |      |[f2]
mult2|no  |

cycle 3

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |   |     |ld2|no  |    |      |f0 |ld1
MUL.S f0,f2->f4 |c2 |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult1
SUBI r1,4->r1   |   |   |   |     |st2|no  |    |      |f6 |
BNEZ r1,Loop    |   |   |   |     |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |   |   |   |     |---+----+----+------|f10|
MUL.S f0,f2->f4 |   |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |   |   |   |     |T     |V            |r1 |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld1 |    |      |[f2]
mult2|no  |

renaming sets up a dataflow graph [Dennis, 1974/1975]: Ld1 -> mult1 -> St1

cycle 4

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |   |     |ld2|no  |    |      |f0 |ld1
MUL.S f0,f2->f4 |c2 |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult1
SUBI r1,4->r1   |c4 |   |   |     |st2|no  |    |      |f6 |
BNEZ r1,Loop    |   |   |   |     |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |   |   |   |     |---+----+----+------|f10|
MUL.S f0,f2->f4 |   |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |   |   |   |     |T     |V            |r1 |add1
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |yes |SUBI |    |    |[r1]  |4
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld1 |    |      |[f2]
mult2|no  |

cycle 5

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |   |     |ld2|no  |    |      |f0 |ld1
MUL.S f0,f2->f4 |c2 |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult1
SUBI r1,4->r1   |c4 |c5 |   |     |st2|no  |    |      |f6 |
BNEZ r1,Loop    |c5 |   |   |     |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |   |   |   |     |---+----+----+------|f10|
MUL.S f0,f2->f4 |   |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |   |   |   |     |T     |V            |r1 |add1
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |yes |SUBI |    |    |[r1]  |4
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld1 |    |      |[f2]
mult2|no  |

next cycle: 2nd load dispatches

cycle 6

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |   |     |ld2|yes |    |add1  |f0 |ld2
MUL.S f0,f2->f4 |c2 |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult1
SUBI r1,4->r1   |c4 |c5 |c6 |     |st2|no  |    |      |f6 |
BNEZ r1,Loop    |c5 |   |   |     |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |   |   |     |---+----+----+------|f10|
MUL.S f0,f2->f4 |   |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |   |   |   |     |T     |V            |r1 |add1
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |yes |SUBI |    |    |[r1]  |4
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld1 |    |      |[f2]
mult2|no  |

f0 will never get result of ld1
- ok since dependent instr (MUL.S) will get value directly from Ld1 (CDB)
branches: 2 options
1. no speculation - branch must be resolved before younger instr can execute
2. must have a way to undo mis-speculation

cycle 7

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |   |     |ld2|yes |76  |      |f0 |ld2
MUL.S f0,f2->f4 |c2 |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult2
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|no  |    |      |f6 |
BNEZ r1,Loop    |c5 |c7 |   |     |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |   |   |     |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |   |   |   |     |T     |V            |r1 |
                                  |add1  |76           |   |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld1 |    |      |[f2]
mult2|yes |MUL.S|ld2 |    |      |[f2]

reg file decoupled from computation
1st & 2nd iterations overlap

cycle 8

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |   |     |ld2|yes |76  |      |f0 |ld2
MUL.S f0,f2->f4 |c2 |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult2
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |mult2 |f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |     |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |c8 |   |     |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |c8 |   |   |     |T     |V            |r1 |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld1 |    |      |[f2]
mult2|yes |MUL.S|ld2 |    |      |[f2]

L.S #2 issues now since branch is resolved in X
- no longer speculative (we will add speculation later!)

cycle 9

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |   |     |ld2|yes |76  |      |f0 |ld2
MUL.S f0,f2->f4 |c2 |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult2
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |mult2 |f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |c8 |   |     |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |c8 |   |   |     |T     |V            |r1 |add1
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |yes |SUBI |    |    |76    |4
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld1 |    |      |[f2]
mult2|yes |MUL.S|ld2 |    |      |[f2]

2nd SUBI dispatches (not shown)

cycle 10

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|yes |80  |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |c10|     |ld2|yes |76  |      |f0 |ld2
MUL.S f0,f2->f4 |c2 |   |   |     |ld3|no  |    |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult2
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |mult2 |f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |c8 |   |     |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |c8 |   |   |     |T     |V            |r1 |add1
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |yes |SUBI |    |    |76    |4
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld1 |    |      |[f2]
mult2|yes |MUL.S|ld2 |    |      |[f2]

ld1 completing execution - who is waiting?
BNEZ #2 dispatched (not shown)

cycle 11

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|no  |    |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |c10|c11  |ld2|yes |76  |      |f0 |ld3
MUL.S f0,f2->f4 |c2 |c11|   |     |ld3|yes |    |add1  |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult2
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |mult2 |f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |c8 |c11|     |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |   |   |     |CDB                 |...|
S.S f4->#0(r1)  |c8 |   |   |     |T     |V            |r1 |add1
                                  |ld1   |Mem[80]      |   |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |yes |SUBI |    |    |76    |4
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|    |    |M[80] |[f2]
mult2|yes |MUL.S|ld2 |    |      |[f2]

ld1 puts result on CDB
- value written in Vj for mult1
ld2 completing execution - who is waiting?
L.S #3 (not shown) would dispatch

cycle 12

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|no  |    |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |c10|c11  |ld2|no  |    |      |f0 |ld3
MUL.S f0,f2->f4 |c2 |c11|   |     |ld3|yes |    |add1  |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult2
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |mult2 |f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |c8 |c11|c12  |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |c12|   |     |CDB                 |...|
S.S f4->#0(r1)  |c8 |   |   |     |T     |V            |r1 |add1
                                  |ld2   |M[76]        |   |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |yes |SUBI |    |    |76    |4
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|    |    |M[80] |[f2]
mult2|yes |MUL.S|    |    |M[76] |[f2]

dispatch 3rd MUL.S?
- will be structural hazard
- no reservation station entries
- must stall -> propagates to younger instrs

cycle 13

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|no  |    |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |c10|c11  |ld2|no  |    |      |f0 |ld3
MUL.S f0,f2->f4 |c2 |c11|   |     |ld3|yes |72  |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult2
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |mult2 |f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |c8 |c11|c12  |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |c12|   |     |CDB                 |...|
S.S f4->#0(r1)  |c8 |   |   |     |T     |V            |r1 |
                                  |add1  |72           |   |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|    |    |M[80] |[f2]
mult2|yes |MUL.S|    |    |M[76] |[f2]

SUBI #2 write back
- why didn't it write back in cycle 12? structural hazard on CDB

cycle 14

BNEZ #2 completes X -> L.S #3 issues

cycle 15

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|no  |    |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |c10|c11  |ld2|no  |    |      |f0 |ld3
MUL.S f0,f2->f4 |c2 |c11|c15|     |ld3|yes |72  |      |f2 |
S.S f4->#0(r1)  |c3 |   |   |     |st1|yes |80  |mult1 |f4 |mult2
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |mult2 |f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |c8 |c11|c12  |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |c12|   |     |CDB                 |...|
S.S f4->#0(r1)  |c8 |   |   |     |T     |V            |r1 |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|    |    |M[80] |[f2]
mult2|yes |MUL.S|    |    |M[76] |[f2]

mult1 is completing execution - who is waiting?

cycle 16

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|no  |    |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |c10|c11  |ld2|no  |    |      |f0 |ld3
MUL.S f0,f2->f4 |c2 |c11|c15|c16  |ld3|yes |72  |      |f2 |
S.S f4->#0(r1)  |c3 |c16|   |     |st1|yes |80  |[80]*F|f4 |mult2
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |mult2 |f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |c8 |c11|c12  |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |c12|c16|     |CDB                 |...|
S.S f4->#0(r1)  |c8 |   |   |     |T     |V            |r1 |
                                  |mult1 |M[80]*f2     |   |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|no  |
mult2|yes |MUL.S|    |    |M[76] |[f2]

cycle 17

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|no  |    |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |c10|c11  |ld2|no  |    |      |f0 |ld3
MUL.S f0,f2->f4 |c2 |c11|c15|c16  |ld3|yes |72  |      |f2 |
S.S f4->#0(r1)  |c3 |c16|c17|     |st1|yes |80  |[80]*F|f4 |mult1
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |[76]*F|f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|no  |    |      |f8 |
L.S #0(r1)->f0  |c6 |c8 |c11|c12  |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |c12|c16|c17  |CDB                 |...|
S.S f4->#0(r1)  |c8 |c17|   |     |T     |V            |r1 |
                                  |mult2 |M[76]*f2     |   |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld3 |    |      |[f2]
mult2|no  |

MUL.S #3 structural hazard resolved

cycle 18

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|no  |    |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |c10|c11  |ld2|no  |    |      |f0 |ld3
MUL.S f0,f2->f4 |c2 |c11|c15|c16  |ld3|yes |72  |      |f2 |
S.S f4->#0(r1)  |c3 |c16|c17|c18  |st1|no  |    |      |f4 |mult1
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|yes |76  |[76]*F|f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|yes |72  |mult1 |f8 |
L.S #0(r1)->f0  |c6 |c8 |c11|c12  |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |c12|c16|c17  |CDB                 |...|
S.S f4->#0(r1)  |c8 |c17|c18|     |T     |V            |r1 |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld3 |    |      |[f2]
mult2|no  |

S.S does not use CDB
dispatch S.S #3, stalled previously due to structural hazard by MUL.S #3

cycle 19

instr status                      |   |Busy|Addr|T     |Map Table
instr           |D  |S  |X  |W    |ld1|no  |    |      |Reg|T
L.S #0(r1)->f0  |c1 |c2 |c10|c11  |ld2|no  |    |      |f0 |ld3
MUL.S f0,f2->f4 |c2 |c11|c15|c16  |ld3|yes |72  |      |f2 |
S.S f4->#0(r1)  |c3 |c16|c17|c18  |st1|no  |    |      |f4 |mult1
SUBI r1,4->r1   |c4 |c5 |c6 |c7   |st2|no  |    |      |f6 |
BNEZ r1,Loop    |c5 |c7 |c8 |c9   |st3|yes |72  |mult1 |f8 |
L.S #0(r1)->f0  |c6 |c8 |c11|c12  |---+----+----+------|f10|
MUL.S f0,f2->f4 |c7 |c12|c16|c17  |CDB                 |...|
S.S f4->#0(r1)  |c8 |c17|c18|c19  |T     |V            |r1 |
----------------------------------+--------------------+---+------
reservation stations
FU   |busy|op   |Qj  |Qk  |Vj    |Vk
add1 |no  |
add2 |no  |
add3 |no  |
mult1|yes |MUL.S|ld3 |    |      |[f2]
mult2|no  |

Tomasulo can overlap loop iterations

why can tomasulo overlap loop iterations:

register renaming: multiple iterations use different physical dests for regs => dynamic loop unrolling
reservation stations: buffer old values of regs => avoid WAR hazards; permits OoO issue of independent instrs
other perspctive: it builds dataflow depenency graph on the fly

two major advantages:

distributed reservation stations & CDB
- if multiple instrs are waiting on a single result & each has operand, then instrs can be issued simultaneously with broadcast on CDB
elimination of stalls for WAW and WAR hazards

drawback: if 1st store has page fault, younger instrs can have already updated values. we do not have info to restore the states.

dynamic scheduling summary:

out of order exec
- higher pipeline/FU utilization, improved perf
- easer and more effective in hardware than in software
  - more storage locations than architectural regs
  - dynamic handling of cache misses
instr buffer: multiple F/D latches
- implements large scheduling scopr + passing functionality
- split decode into in-order dispatch and out-of-order issue
  - stall vs. wait

precise state and speculation

true register renaming + reorder buffer (ROB) = MIPSR10K design

sequential (vN) semantics for interrupts:

all instrs bfore interupt should complete
all instrs after interrupt should look as if they never started
same thing for mispredicted branches

precise state:

speculative execution requires: ability to abort & restart at every instr
precise synchrounous interrupts require: ability to abort & restart at every load, store, div

Week 6. Oct 13

instr buffer becomes reorder buffer (ROB):

is a FIFO queue containing
- flag indicating if instr has completed
- new and old reg mapping
conceptually buffers completed results en route to reg file
we split write-back to two stages:
compute (C):
- completed instr write result into physical reg file
- OoO: wait does not back propagate to younger instrs
retire (R): aka commit, graduate
- ROB return old physical reg to free list
- in order: stall back propagate to younger instrs

load/store queue (LSQ):

completed store write to LSQ
when store retires, head of LSQ written to D$ (data cache) / memory
when load executes, accesses LSQ & D$ in parallel
- forward value from LSQ if there exists older store with matching address

architectural reg files are gone
physical reg file holds all values
- # of physical regs > # of architectural reg names
- map architectural regs to physical regs
- renmove WAR/WAW hazards
- replace value copies in tomasulo RS
fundamental change to map table
- mappings cannot be ∅ => there is no arch reg file
- (recall in tomasulo ∅ indicates value in arch reg file is up to date)
free list keeps track of unallocated physical regs
- ROB is responsible for returning regs to free list

one big physical reg file holding all data, no copies
+ reg file closer to FUs => small fast data path
- ROB and RS 'on the side' used only for control and tags

R10K data structures:

new tags: tomasulo's reservation station ID => R10K's PR#
ROB
- T: physical reg corresponding to this instr's logical output
- Told: physical reg previously mapped to this instr's logical output
reservation station
- T, S1, S2: output, source physical regs
- '+' indicates value ready
map table
- T+: PR# (never empty) + 'ready' bit

R10K pipeline (FDSXCR):

D (dispatch)
- structural hazards: check RS, ROB, physical regs, stall
- allocate RS & ROB entries, new physical reg (T)
- read PR tags for input regs, store in RS (S1, S2)
- read old PR tag for output reg, store in ROB(Told)
- store new output tag (T) in RS and ROB
X (execute)
- free RS entry
  - (used to be at W, can be earlier because RS# is not tag)
C (compute)
- write destination PR
- set instr output reg's ready bit in maptable
- set ready bits for matching input tags
R (retire)
- if ROB head is not complete, stall
- handle any exceptions
- if store, write value from LSQ into D$/memory
- free ROB (& LSQ) entry
- free previous physical reg (Told)

eg.

Loop: L.S #0(r1)->f0
      MUL.S f0,f2->f4
      S.S f4->#0(r1)
      SUBI r1,4->r1
      BNEZ r1,Loop

cycle 1:

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
ht|1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |   |      |   |f0 |PR#5  |
  |  |                |     |     |   |   |      |   |f2 |PR#2+ |
  |  |                |     |     |   |   |      |   |f4 |PR#3+ |
  |  |                |     |     |   |   |      |   |r1 |PR#4+ |
  |  |                |     |     |   |   |      |   |----------+------
  |  |                |     |     |   |   |      |   |
  |  |                |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#6,PR#7,PR#8
1|add1 |no  |
2|add2 |no  |
3|mult1|no  |
4|mult2|no  |
5|ld1  |yes |L.S  |PR#5 |PR#4+|
6|ld2  |no  |
7|st1  |no  |
8|st2  |no  |

allocate new PR (PR#5) for f0
remember old PR mapped to f0 (PR#1) in ROB

cycle 2

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |      |   |f0 |PR#5  |
t |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |   |      |   |f2 |PR#2+ |
  |  |                |     |     |   |   |      |   |f4 |PR#6  |
  |  |                |     |     |   |   |      |   |r1 |PR#4+ |
  |  |                |     |     |   |   |      |   |----------+------
  |  |                |     |     |   |   |      |   |
  |  |                |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#7,PR#8
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5 |PR#2+|
4|mult2|no  |
5|ld1  |yes |L.S  |PR#5 |PR#4+|
6|ld2  |no  |
7|st1  |no  |
8|st2  |no  |

ld1 is ready to issue (PR#4+)

cycle 3

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3+   |   |f0 |PR#5  |
  |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |   |      |   |f2 |PR#2+ |
t |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
  |  |                |     |     |   |   |      |   |r1 |PR#4+ |
  |  |                |     |     |   |   |      |   |----------+------
  |  |                |     |     |   |   |      |   |
  |  |                |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#7,PR#8
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5 |PR#2+|
4|mult2|no  |
5|ld1  |yes |L.S  |PR#5 |PR#4+|
6|ld2  |no  |
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

stores are not allocated a physical reg

cycle 4

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3+   |   |f0 |PR#5  |
  |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |   |      |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
t |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |   |      |   |r1 |PR#7  |
  |  |                |     |     |   |   |      |   |----------+------
  |  |                |     |     |   |   |      |   |
  |  |                |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#8
1|add1 |yes |SUBI |PR#7 |PR#4+|
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5 |PR#2+|
4|mult2|no  |
5|ld1  |yes |L.S  |PR#5 |PR#4+|
6|ld2  |no  |
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

cycle 5

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3+   |   |f0 |PR#5  |
  |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |   |      |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
  |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |c5 |      |   |r1 |PR#7  |
t |5 |BNEZ r1,Loop    |     |     |c5 |   |      |   |----------+------
  |  |                |     |     |   |   |      |   |
  |  |                |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#8
1|add1 |yes |SUBI |PR#7 |PR#4+|
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5 |PR#2+|
4|mult2|no  |
5|ld1  |yes |L.S  |PR#5 |PR#4+|
6|ld2  |no  |
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

input for SUBI is ready
RS for branch not shown; BNEZ will read r1's value from PR#7 when ready

cycle 6

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3+   |   |f0 |PR#8  |
  |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |   |      |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
  |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |c5 |c6    |   |r1 |PR#7  |
  |5 |BNEZ r1,Loop    |     |     |c5 |   |      |   |----------+------
t |6 |L.S #0(r1)->f0  |PR#8 |PR#5 |c6 |   |      |   |
  |  |                |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5 |PR#2+|
4|mult2|no  |
5|ld1  |yes |L.S  |PR#5 |PR#4+|
6|ld2  |yes |L.S  |PR#8 |PR#7 |
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

diff from tomasulo: RS freed at end of X (RS# is not used as tag)
branch predicted taken => dispatch L.S from 2nd loop iteration

cycle 7

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3+   |   |f0 |PR#8  |PR#7
  |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |   |      |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
  |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |BNEZ r1,Loop    |     |     |c5 |c7 |      |   |----------+------
t |6 |L.S #0(r1)->f0  |PR#8 |PR#5 |c6 |   |      |   |
  |7 |MUL.S f0,f2->f4 |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5 |PR#2+|
4|mult2|no  |
5|ld1  |yes |L.S  |PR#5 |PR#4+|
6|ld2  |yes |L.S  |PR#8 |PR#7+|
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

SUBI completes
- broadcasts tag (no value on CDB, just tag); value written to physical reg file
- sets ready bit in map table, RS
MUL.S #2 stalls b/c no free physical reg (not dispatched)
assume only 1 instr issues per cycle (reading reg file)

cycle 8

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3+   |   |f0 |PR#8  |
  |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |   |      |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
  |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |BNEZ r1,Loop    |     |     |c5 |c7 |c8    |   |----------+------
t |6 |L.S #0(r1)->f0  |PR#8 |PR#5 |c6 |c8 |      |   |
  |7 |MUL.S f0,f2->f4 |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5 |PR#2+|
4|mult2|no  |
5|ld1  |yes |L.S  |PR#5 |PR#4+|
6|ld2  |yes |L.S  |PR#8 |PR#7+|
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

cycle 9

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3+   |   |f0 |PR#8  |
  |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |   |      |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
  |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |BNEZ r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
t |6 |L.S #0(r1)->f0  |PR#8 |PR#5 |c6 |c8 |c9+   |   |
  |7 |MUL.S f0,f2->f4 |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5 |PR#2+|
4|mult2|no  |
5|ld1  |yes |L.S  |PR#5 |PR#4+|
6|ld2  |yes |L.S  |PR#8 |PR#7+|
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

branch completes => prediction correct

cycle 10

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3-10 |   |f0 |PR#8  |
  |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |   |      |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
  |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |BNEZ r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
t |6 |L.S #0(r1)->f0  |PR#8 |PR#5 |c6 |c8 |c9+   |   |
  |7 |MUL.S f0,f2->f4 |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5 |PR#2+|
4|mult2|no  |
5|ld1  |no  |
6|ld2  |yes |L.S  |PR#8 |PR#7+|
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

L.S #1 finishes executing (cache miss => 8 cycles)

cycle 11

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
h |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3-10 |c11|f0 |PR#8  |PR#5
  |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |c11|      |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
  |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |BNEZ r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
t |6 |L.S #0(r1)->f0  |PR#8 |PR#5 |c6 |c8 |c9-11 |   |
  |7 |MUL.S f0,f2->f4 |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5+|PR#2+|
4|mult2|no  |
5|ld1  |no  |
6|ld2  |no  |
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

L.S #2 cache hit, only takes 1 cycle after 1st load finishes executing

cycle 12

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
  |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3-10 |c11|f0 |PR#8+ |PR#8
h |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |c11|c12+  |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#6  |
  |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |BNEZ r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
t |6 |L.S #0(r1)->f0  |PR#8 |PR#5 |c6 |c8 |c11   |c12|
  |7 |MUL.S f0,f2->f4 |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#1
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5+|PR#2+|
4|mult2|no  |
5|ld1  |no  |
6|ld2  |no  |
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

L.S #1 is oldest instr (ROB head) & complete => retire
- return Told (PR#1) to free list & deallocate ROB entry

cycle 13

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
  |1 |L.S #0(r1)->f0  |PR#5 |PR#1 |c1 |c2 |c3-10 |c11|f0 |PR#8+ |
h |2 |MUL.S f0,f2->f4 |PR#6 |PR#3 |c2 |c11|c12+  |   |f2 |PR#2+ |
  |3 |S.S f4->#0(r1)  |     |     |c3 |   |      |   |f4 |PR#1  |
  |4 |SUBI r1,4->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |BNEZ r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
  |6 |L.S #0(r1)->f0  |PR#8 |PR#5 |c6 |c8 |c11   |c12|
t |7 |MUL.S f0,f2->f4 |PR#1 |PR#6 |c13|   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |
1|add1 |no  |
2|add2 |no  |
3|mult1|yes |MUL.S|PR#6 |PR#5+|PR#2+|
4|mult2|yes |MUL.S|PR#1 |PR#8+|PR#2+|
5|ld1  |no  |
6|ld2  |no  |
7|st1  |yes |S.S  |     |PR#4+|PR#6 |
8|st2  |no  |

MUL.S #1 is now oldest instr but not completed => cannot retire
MUL.S #2 gets newly freed PR#1

observations:

out of order execution, out of order completion, in-order retirement.
long delay between L.S and MUL.S completion (perf suffers due to not enough physical regs)

Week 7. Oct 20

precise state in r10k:

physical regs are written out of order
- since ther is no architectural regs
we can 'free' written regs and restore old ones
- do by manipulating map table and free list
- not the reg file

restoring precise state in R10K

option 1: serial rollback using T, Told
- + simple, - slow
option 2: single-cycle restoration from checkpoint
- + fast, - checkpoints are expensive
modern processor compromise
- make common case fast
- checkpoint only low confidence branches
- serial recovery for page faults, interrupts => rare rollbacks

eg. serial rollback

Loop: ldf [r1+0]->f0
      mulf f0,f2->f4
      stf f4->[r1+0]
      subi r1,8->r1
      bnez r1,Loop

page fault:

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
  |8 |stf f4->[r1+0]  |     |     |c14|   |      |   |f0 |PR#8+ |
t |9 |subi r1,8->r1   |PR#3 |PR#7 |c18|   |      |   |f2 |PR#2+ |
h |3 |stf f4->[r1+0]  |     |     |c3 |c16|c17   |c18|f4 |PR#1  |
  |4 |subi r1,8->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#3  |
  |5 |bnez r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
  |6 |ldf [r1+0]->f0  |PR#8 |PR#5 |c6 |c8 |c11   |c12|
  |7 |mulf f0,f2->f4  |PR#1 |PR#6 |c13|c14|c15-18|   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |
1|add1 |yes |subi |PR#3 |PR#7+|
2|add2 |no  |
3|mult1|no  |
4|mult2|no  |
5|ld1  |no  |
6|ld2  |no  |
7|st1  |no  |
8|st2  |yes |stf  |     |PR#7+|PR#1 |

stf (ROB#3) page faults; subi, bnez, ldf have completed but not retired
roll back reg mappings, start at tail

undo subi (ROB#9)

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
  |8 |stf f4->[r1+0]  |     |     |c14|   |      |   |f0 |PR#8+ |
t |9 |subi r1,8->r1   |PR#3 |PR#7 |c18|   |      |   |f2 |PR#2+ |
h |3 |stf f4->[r1+0]  |     |     |c3 |c16|c17   |c18|f4 |PR#1  |
  |4 |subi r1,8->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |bnez r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
  |6 |ldf [r1+0]->f0  |PR#8 |PR#5 |c6 |c8 |c11   |c12|
  |7 |mulf f0,f2->f4  |PR#1 |PR#6 |c13|c14|c15-18|   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#3
1|add1 |no  |
2|add2 |no  |
3|mult1|no  |
4|mult2|no  |
5|ld1  |no  |
6|ld2  |no  |
7|st1  |no  |
8|st2  |yes |stf  |     |PR#7+|PR#1 |

free RS
free T (PR#3), return to free list
restore MT[r1] to Told (PR#7)
free ROB#9

undo stf (ROB#8)

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
t |8 |stf f4->[r1+0]  |     |     |c14|   |      |   |f0 |PR#8+ |
  |  |                |     |     |   |   |      |   |f2 |PR#2+ |
h |3 |stf f4->[r1+0]  |     |     |c3 |c16|c17   |c18|f4 |PR#1  |
  |4 |subi r1,8->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |bnez r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
  |6 |ldf [r1+0]->f0  |PR#8 |PR#5 |c6 |c8 |c11   |c12|
  |7 |mulf f0,f2->f4  |PR#1 |PR#6 |c13|c14|c15-18|   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#3
1|add1 |no  |
2|add2 |no  |
3|mult1|no  |
4|mult2|no  |
5|ld1  |no  |
6|ld2  |no  |
7|st1  |no  |
8|st2  |no  |

free RS
free ROB#8

undo mulf (ROB#7)

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
  |  |                |     |     |   |   |      |   |f0 |PR#8+ |
  |  |                |     |     |   |   |      |   |f2 |PR#2+ |
h |3 |stf f4->[r1+0]  |     |     |c3 |c16|c17   |c18|f4 |PR#6+ |
  |4 |subi r1,8->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |bnez r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
  |6 |ldf [r1+0]->f0  |PR#8 |PR#5 |c6 |c8 |c11   |c12|
t |7 |mulf f0,f2->f4  |PR#1 |PR#6 |c13|c14|c15-18|   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#3,PR#1
1|add1 |no  |
2|add2 |no  |
3|mult1|no  |
4|mult2|no  |
5|ld1  |no  |
6|ld2  |no  |
7|st1  |no  |
8|st2  |no  |

free T (PR#1), return to free list
restore MT[f4] to Told (PR#6)
free ROB#7

undo ldf (ROB#6)

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
  |  |                |     |     |   |   |      |   |f0 |PR#5+ |
  |  |                |     |     |   |   |      |   |f2 |PR#2+ |
h |3 |stf f4->[r1+0]  |     |     |c3 |c16|c17   |c18|f4 |PR#6+ |
  |4 |subi r1,8->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#7+ |
  |5 |bnez r1,Loop    |     |     |c5 |c7 |c8    |c9 |----------+------
t |6 |ldf [r1+0]->f0  |PR#8 |PR#5 |c6 |c8 |c11   |c12|
  |  |                |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#3,PR#1,PR#8
1|add1 |no  |
2|add2 |no  |
3|mult1|no  |
4|mult2|no  |
5|ld1  |no  |
6|ld2  |no  |
7|st1  |no  |
8|st2  |no  |

free T (PR#8), return to free list
restore MT[f0] to Told (PR#5)
free ROB#6
bnez (ROB#5) has no output reg => just free ROB#5

undo subi (ROB#4)

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
  |  |                |     |     |   |   |      |   |f0 |PR#5+ |
  |  |                |     |     |   |   |      |   |f2 |PR#2+ |
h |3 |stf f4->[r1+0]  |     |     |c3 |c16|c17   |c18|f4 |PR#6+ |
t |4 |subi r1,8->r1   |PR#7 |PR#4 |c4 |c5 |c6    |c7 |r1 |PR#4+ |
  |  |                |     |     |   |   |      |   |----------+------
  |  |                |     |     |   |   |      |   |
  |  |                |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#3,PR#1,PR#8,PR#7
1|add1 |no  |
2|add2 |no  |
3|mult1|no  |
4|mult2|no  |
5|ld1  |no  |
6|ld2  |no  |
7|st1  |no  |
8|st2  |no  |

free T (PR#7), return to free list
restore MT[r1] to Told (PR#4)
free ROB#4

done

ROB                                                  |map table |CDB
ht|# |instr           |T    |Told |D  |S  |X     |C  |reg|T+    |T
  |  |                |     |     |   |   |      |   |f0 |PR#5+ |
  |  |                |     |     |   |   |      |   |f2 |PR#2+ |
ht|3 |stf f4->[r1+0]  |     |     |c3 |c16|c17   |c18|f4 |PR#6+ |
  |  |                |     |     |   |   |      |   |r1 |PR#4+ |
  |  |                |     |     |   |   |      |   |----------+------
  |  |                |     |     |   |   |      |   |
  |  |                |     |     |   |   |      |   |
--+--+----------------+-----+-----+---+---+------+---+
reservation stations                |free list
#|FU   |busy|op   |T    |S1   |S2   |PR#3,PR#1,PR#8,PR#7
1|add1 |no  |
2|add2 |no  |
3|mult1|no  |
4|mult2|no  |
5|ld1  |no  |
6|ld2  |no  |
7|st1  |no  |
8|st2  |no  |

effects of younger instrs undone; stf is ROB head & tail
(slides still show st2 busy in the last two steps; it was freed when undoing ROB#8)

MIPS R10K summary

true reg renaming via physical reg file
- at retirement, free old reg mapping
avoid extra data copying
- do not move data from reg to reservation station
roll-back
- undo speculative instrs
- support precise exception model

three great tastes

CPI < 1: go superscalar
superscalar increases RAW hazards: go out-of-order
RAW hazards still a problem: build larger window
branches a problem for filling large window: add control speculation

caches

motivation:

a 3GHz processor can execute add in 0.33ns
today's main mem latency is 50-100ms
unobtainable goal
- mem operating at processor speeds
- mem as large as needed to run all programs
- mem that is cost effective
cannot achieve all at once

locality

temporal locality: recently referenced data is likely to be referenced again soon
- reactive: cache recently used data in small, fast mem
spacial locality: more likely to reference data near referenced ata
- proactive: fetching in large chunks to include nearby data
holds for data and instrs (loops)

memory hierarchy:

upper components: fast, small, expensive
lower components: slow, large, cheap
connected by buses: also have latency and bandwidth issues
most frequently accessed data in M1
- M1 + next most frequently accessed data in M2, etc. (inclusive)
- move data up-down hierarchy

+---+            +----+    +------+    +--------+
|CPU|<-->|M1|<-->| M2 |<-->|  M3  |<-->|   M4   |
+---+            +----+    +------+    +--------+

optimize average access time
- latency = latencyM1 + %miss * latencyM2
- attack each

concrete memory hierarchy:

1st level: primary caches
- split instrs (I$) and data (D$)
- typically 8-64 KB each, access 1-2 cycles
2nd level: second-level cache (L2$)
- on-chip
- made of SRAM(same circuit type as CPU)
- typically 512-16 MB, 5-10 cycles
L3: on-chip
3rd level: main mem
- DRAM
- > 100 cycles
4th level: disk (swap and files)
- millions of cycles

  ┌────────────────┐  ─┐
  │      CPU Regs  │   │ compiler
  ├───────┬────────┤   │ managed
  │  I$   │   D$   │  ─┤
  └───┬───┴───┬────┘   │
  ┌───┴───────┴────┐   │ hardware
  │      L2$       │   │ managed
  └───────┬────────┘   │
  ┌───────┴────────┐   │
  │  main memory   │  ─┤
  └───────┬────────┘   │ software
  ┌───────┴────────┐   │ managed
  │      disk      │   │
  └────────────────┘  ─┘

basic mem array structure:

number of entries: 2^n where n is # addr bits
- decoder changes n-bit address into 2^n one-bit signals
- one-bit addr travels on word line
size of entries: which of data is accessed
- data travels on bitlines

eg. finding data via indexing:

                                data  tag v
                          ╱┐  ┌──────┬───┬─┐ 1024*256 bits
                         │ ├─►│  0   │   │ │ SRAM
                         │ ├─►│  1   │   │ │
                         │w├─►│  2   │   │ │
             ┌──────────►│o├─►│  3   │   │ │
             │           │r│  │  ┊   │ ┊ │┊│
             │           │d├─►│ 1021 │   │ │
             │           │s├─►│ 1022 │   │ │
             │           │ ├─►│ 1023 │   │ │
             │            ╲┘  └───┬──┴─┬─┴┬┘
             │                    │    │  │
     ┌───────┼────────────────────┼──►(=) │
     │       │                    │    │  │
     │       │                    ▼    ▼  ▼
┌────┴─────┬─┴─────────┬─────┐  ┌────┐┌────┐
│tag[31:15]│index[14:5]│[4:0]├─►│ << ││ &  │
└──────────┴───────────┴─────┘  └─┬──┘└─┬──┘
                 ▲                ▼     ▼
               address           data  hit?

decode part of address

32-bit address -> 32-bit blocks -> log32 = 5 lowest bits within block
- known as offset bits
1024 lines -> next log1024 = 10 bits
- known as index bits

tags:

each entry can hold one of 2^17 blocks
- all addresses with same index pattern
to each entry attach tag and valid bit, compare block tag bitsto addr tag bits
- no need to include index bits

lookup algorithm:

ready entry indicated by index bits
hit iff tag matches and valid bit is set

calculating tag overhead:

"32KB cache' means cache holds 32KB data
- called capacity
- tag store considered overhead
tag overhead of 32KB cache with 1024 32-bit blocks
- (32 - 10 - 5) = 17-bit tags
- (17 bit + 1 valid bit) * 1024 = 2.2 KB ~ 6% overhead
- 64-bit addr: tag increases to 49 bits ~ 20% overhead

handling cache miss:

cache controller: finite statemachine
- remembers miss addr
- access next level mem
- wait for response
- write data/tag into proper locations

cache performance equation

%miss: = #misses / #accesses
%hit = 1 - %miss
t_hit = time to access cache
t_miss = time to bring data to cache
performance metric = tavg = t_hit + %miss * t_miss

eg. calculating CPI:

base CPI=1
30% loads/stores
I$ %miss = 2%, t_miss = 10c, t_hit = 1c
D$ %miss = 10%, t_miss = 10c, t_hit = 1c

then

CPI_I$ = %miss * t_miss = 0.02 * 10c = 0.2c
CPI_D$ = %miss * t_miss * % loads/stores = 0.1 * 10c * 0.3 = 0.3c
CPI_new = 1 + 0.2 + 0.3 = 1.5

for hierarchy:

t_avg = T_L1 + %miss_L1 * T_L1miss
      = T_L1 + %miss_L1 * (T_L2 + %miss_L2 \* T_L2miss)
      = ...

eg. performance calculation:

all are load instrs
D$: t_cacheD$ = 1ns, %miss = 5%
L2: t_cacheL2 = 10ns, %miss = 20%
main mem: t_mem = 50ns

then without L2:

t_missD$ = t_mem = 50ns
t_avgD$ = t_D$ + %miss_D$ * t_mem = 3.5ns

with L2:

t_missD$ = t_avgL2
t_avgL2 = t_L2 + %miss_L2 * t_mem = 20ns
t_avgD$ = 1ns + 0.05 * 20ns = 2ns

eg. cache miss simulation:

4-bit addresses -> 16-bit mem
8-bit cache, 2-bit blocks
- number of sets, aka entries: 8/2 = 4
- how address splits into offset/index/tag bits:
  - offset bits: log2=1
  - index bits: log4=2
  - tag bits: 4 - 2 - 1 = 1

observation: there are conflicting pairs like 0000/1000

regardless of block size
Q: can we allow pairs like these to simultaneously reside?
A: reorganize as set-associative cache

set-associativity

block can reside in one of few lines
line groups called sets
each line in set called ways
+ reduces conflicts
- increases latency (extra tag matching and mux)
1-way: direct-mapped cache (DM)
1-set: fully-associative cache (FA)

2-way associative cache:

                                way 0    way 1
                          ╱┐  ┌──────┬─┬──────┬─┐
                         │ ├─►│   0  │ │  512 │ │
                         │s├─►│   1  │ │  513 │ │
             ┌──────────►│e├─►│   2  │ │  514 │ │
             │           │t│  │   ┊  │┊│   ┊  │┊│
             │           │s├─►│  510 │ │ 1022 │ │
             │           │ ├─►│  511 │ │ 1023 │ │
             │            ╲┘  └──┬───┴┬┴──┬───┴┬┘
     ┌───────┼───────────────────┼──┬─┼───┼──┐ │
     │       │                   │  └(=)  │  └(=)
     │       │                   │    └───┼────┼┐
     │       │                   ▼        ▼    ││
     │18     │9                 ┌──────────┐   ││
     │       │                  │   mux    │◄──┤│
     │       │                  └─┬────────┘   ││
     │       │                    ▼            ▼▼
┌────┴─────┬─┴─────────┬─────┐5 ┌────┐       ┌────┐
│tag[31:14]│index[13:5]│[4:0]├─►│ << │       │ OR │
└──────────┴───────────┴─────┘  └─┬──┘       └─┬──┘
                 ▲                ▼            ▼
              address            data         hit?

eg. 8-bit cache, 2-bit blocks, 2-way set-associative:

observation:

avoid conflicts (0000 and 1000)
new conflicts: addr rearrangement happens (0011)
conflict avoidance usually dominates

replacement policies

on cache miss, which block in set to replace
options:
- random
- FIFO
- LRU (fits temporal locality) - expensive in hardware
- NMRU (not most recently used) - easier to impl approx. of LRU
  - is LRU for 2-way associative cache
- belady's - replace block that would be used furthest in future
  - unachievable optimum

2-way NMRU: add MRU field in each set, updated on each access

                                 data from memory
                                         │
                                     ┌───┴────┐
     ┌───────────────────────────────┼────┬───┼────┐
     │                               ▼    ▼   ▼    ▼
     │                    ╱┐  ┌───┬──────┬─┬──────┬─┐
     │                   │s├─►│   │   0  │ │  512 │ │
     │       ┌──────────►│e├─►│   │   1  │ │  513 │ │
     │       │           │t│  │ ┊ │   ┊  │┊│   ┊  │┊│
     │       │           │s├─►│   │  511 │ │ 1023 │ │
     │       │            ╲┘  └┬─┬┴──┬───┴┬┴──┬───┴┬┘
     ├───────┼─────────────────┼─┼───┼──┬─┼───┼──┐ │
     │       │                 ▲ ▲   │  └(=)  │  └(=)
     │       │                 │ │   │    └───┼────┼┐
     │       │                 │ │   ▼        ▼    ││
     │       │              WE │ │  ┌──────────┐   ││
     │       │                 │ │  │   mux    │◄──┤│
     │       │                 │ │  └─┬────────┘ ┌─┼┤
     │       │                 │ └────┼─────────mux┤│
     │       │                 │      ▼            ▼▼
┌────┴─────┬─┴─────────┬─────┐ │   ┌────┐        ┌────┐
│tag[31:15]│index[14:5]│[4:0]├─┼──►│ << │        │ OR │
└──────────┴───────────┴─────┘ │   └──┬─┘        └─┬──┘
                 ▲             └──────┼────────────┤
              address                 ▼            ▼
                                    data         hit?

eg. 4-bit addr, 8-bit cache, 4-way LRU

2-bit counter for way: 00 is most recently used, 11 is least recently used
when block is accessed
- reset counter to 00
- update counters (+1) less than accessed block
replace block with counter 11 on cache miss

prefetching

put blocks into cache proactively/speculatively
reduce miss penalty via parallelism
key: anticipate upcoming miss addresses accurately
- can do in software or hardware
simple e.g.: next-block prefetcher
- miss on addr x => anticipate miss on x + block size
- + work for instrs: especially sequential execs
- + work for data: arrays