1 of 64

ECE 5755: Modern Computer Systems and Architecture

Lecture 7: Out of Order Execution

Lynn Ann Conway, an American computer scientist, electrical engineer, and transgender activist, invested generalized dynamic instruction handling, a key advanced in out-of-order execution. Her work was also instrumental in VLSI chip design and electronic design automation.

2 of 64

Today’s agenda

  • Out-of-order Execution
  • Memory Hierarchy

Photos, illustrations, graphics here.

3 of 64

Intel TopDown & VTune

https://ieeexplore.ieee.org/document/6844459

Photos, illustrations, graphics here.

4 of 64

Intel TopDown & VTune

  • Key idea is to identify performance bottleneck by categorizing cycles as either
    • Frontend bound

Photos, illustrations, graphics here.

5 of 64

Intel TopDown & VTune

  • Key idea is to identify performance bottleneck by categorizing cycles as either
    • Frontend bound
    • Bad speculation

Photos, illustrations, graphics here.

6 of 64

Intel TopDown & VTune

  • Key idea is to identify performance bottleneck by categorizing cycles as either
    • Frontend bound
    • Bad speculation
    • Retiring

Photos, illustrations, graphics here.

7 of 64

Intel TopDown & VTune

  • Key idea is to identify performance bottleneck by categorizing cycles as either
    • Frontend bound
    • Bad speculation
    • Retiring
    • Backend Bound

Photos, illustrations, graphics here.

8 of 64

Lab Compute server specifications

  • Intel Xeon Silver 4514Y 2G, 16C/32T2.2 GHz (Emerald Rapids architecture)
  • Cores: 16x2 total
  • Dual socket
  • Cache sizes:
    • L1 Cache: 80KB (per core)
    • L2 Cache: 2MB (per core)
    • L3 Cache: 30MB (shared)
  • 128 GB of Main Memory

Photos, illustrations, graphics here.

9 of 64

Lab Compute server specifications

  • Intel Xeon Silver 4514Y 2G, 16C/32T2.2 GHz (Emerald Rapids architecture)
  • Cores: 16x2 total
  • Dual socket
  • Cache sizes:
    • L1 Cache: 80KB (per core)
    • L2 Cache: 2MB (per core)
    • L3 Cache: 30MB (shared)
  • 128 GB of Main Memory

Photos, illustrations, graphics here.

10 of 64

Queues to use

  • You have access to two queues
    • Shared (3 nodes)
    • ECE 5755 (1 node with priority)

srun -p shared -n 1 --mem=1g --pty /bin/bash

​

​

srun -p ece5755 -n 1 --mem=1g --pty /bin/bash

Photos, illustrations, graphics here.

11 of 64

Things to keep in mind

  • Gathering performance counters can require iterating many times to get “steady behavior”
    • Don’t run your code once in a single loop
    • Loop many times, re-run experiments to ensure typical behavior
    • Show “average” and “variance” if you want to be certain!
  • Ensure nothing else is running on server so you are profiling your OWN application
    • We took care of this for you: when you submit jobs on slurm, you get exclusive access.
    • Please be mindful of this resource… Each experiment is limited to 5 minutes

Photos, illustrations, graphics here.

12 of 64

Instruction Level Parallelism (ILP)

  • ILP is a major part of CPU performance
    • Dynamic Branch Prediction & Hardware Speculation
    • Dynamic instruction scheduling
      • Scoreboarding
      • Tomasulo’s Algorithm
    • Superscalar/Multiple instruction Issue

​

  • All of these things fit well together

​

Photos, illustrations, graphics here.

13 of 64

Overview of score-boarding stages

  • Fetch: Same as before
  • IS: Check structural hazards (issue in order)
  • Rd: Check data hazards (dynamically issue instructions hazards)
  • Execute: Same as before
  • M: Same as before
  • WB: Check for WAR hazards before committing

​

IF

IS

EX

M

WB

Rd

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

14 of 64

Scoreboarding stages: Issue (or dispatch)

  • Fetch – Same as before
  • Issue (Check Structural Hazards)
    • If FU is free and no other active instruction has same destination register (WAW), then issue instruction
    • Do not issue until structural hazards cleared
    • Stalled instruction stay in I-Buffer
    • Size of buffer is also a structural Hazard
      • May have to stall Fetch if buffer fills
    • Note: Issue is In-Order, stalls stops younger instructions

IF

IS

EX

M

WB

Rd

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

15 of 64

Scoreboarding stages: Read operands (or issue)

  • Read Operands (Check Data Hazards)
    • Check scoreboard for whether source operands are available
    • Available?
      • No earlier issued active instructions will write register
      • No currently active FU is going to write it
    • Dynamically avoids RAW hazards

IF

IS

EX

M

WB

Rd

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

16 of 64

Scoreboarding stages: Execution/Write Result

  • Execution
    • Execute/Update scoreboard
  • Write Result
    • Scoreboard checks for WAR stalls and stalls completing instruction, if necessary
    • Before, stalls only occur at the beginning of instructions, now it can be at the end as well
    • Can happen if:
      • Completing instruction destination register matches an older instruction that has not yet read its source operands

IF

IS

EX

M

WB

Rd

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

17 of 64

Scoreboard example

In-order issue; out-of-order execute & commit

Photos, illustrations, graphics here.

18 of 64

Scoreboarding limitations

  • Number and type of functional units

​

  • Number of instruction buffer entries (scoreboard size)

​

  • Amount of application ILP (RAW hazards)

​

  • Presence of antidependencies (WAR) and output dependencies (WAW)
    • Inorder issue for WAW/Structural Hazards limits scheduler
    • WAR stalls are critical for loops (hardware loop unrolling)

Photos, illustrations, graphics here.

19 of 64

Another approach: Tomasulo’s algorithm

  • Used in IBM 360/91 Machines (Late 60s)
  • Similar to scoreboarding, but added renaming
  • Key concept: Reservation Stations

​

  • Very Important Topic
    • Scheduling ideas led to Alpha 21264, HP PA-8000, MIPS R10K, Pentium III, Pentium 4, PowerPC 604, etc…

​

Photos, illustrations, graphics here.

20 of 64

What are Reservation Stations?

  • Distributed (rather than centralized) control scheme
    • Bypassing is allowed via Common Data Bus (CDB) to RS
    • Register Renaming eliminates WAR/WAW hazards
  • Scoreboard/Instruction Buffer becomes Reservation Stations
    • Fetch and Buffer operands as soon as available
      • Eliminates need to always get values from registers at execute
      • Don’t need both registers to be available at the same time
    • Pending instructions designate reservation stations that will provide their inputs

Photos, illustrations, graphics here.

21 of 64

Register renaming

  • Dynamically change register names to eliminate “false dependencies” (WAR/WAW hazards)
  • Architectural registers: Names not Locations
    • Many more locations (“reservation stations” or “physical registers”) than names (“logical or architectural registers”);
    • Dynamically map names to locations

​

Photos, illustrations, graphics here.

22 of 64

Register Renaming with Tomasulo

  • At instruction issue:
    • Register specifiers for source operands are renamed to the names of the reservation stations
    • Values can exist in reservation station or register file
      • To eliminate WARs, register file values are copied to reservation stations at issue
  • Technique used in Pentium III, Pentium M, PowerPC604

​

Photos, illustrations, graphics here.

23 of 64

The three main stages of Tomasulo Algorithm

1. Issue—get instruction from FP Op Queue

If reservation station free (no structural hazard), �control issues instr & sends operands (renames registers).

2. Execution—operate on operands (EX)

When both operands ready then execute;� if not ready, watch Common Data Bus for result

3. Write result—finish execution (WB)

Write on Common Data Bus to all awaiting units; �mark reservation station available

​

Photos, illustrations, graphics here.

24 of 64

Tomasulo Organization

  • Normal data bus: data + destination (“go to” bus)
  • Common data bus: data + source (“come from” bus)
    • 64 bits of data + 4 bits of Functional Unit source address
    • Write if matches expected Functional Unit (produces result)
    • Does the broadcast

Photos, illustrations, graphics here.

25 of 64

Reservation Station Components

  • Op: Operation to perform in the unit
  • Qj, Qk: Reservation stations producing source registers (value to be written)
    • Note: No ready flags needed as in Scoreboard
    • Qj,Qk=0 => ready

​

  • Vj, Vk: Value of Source operands
    • Store buffers has V field, result to be stored
  • Busy: Indicates reservation station or FU are occupied
  • Register Result Status: Indicates which functional unit will write each register, if one exists. Blank when no pending instructions that will write that register.

​

Photos, illustrations, graphics here.

26 of 64

Tomasulo Example

Photos, illustrations, graphics here.

27 of 64

Tomasulo Example

Photos, illustrations, graphics here.

28 of 64

Tomasulo Example

Note: Unlike scoreboarding hardware, this processor can have multiple loads

Photos, illustrations, graphics here.

29 of 64

Tomasulo Example

Note: registers names are removed (“renamed”) in Reservation Stations; MULT issued vs. scoreboard

Load1 completing; what is waiting for Load1?

Photos, illustrations, graphics here.

30 of 64

Tomasulo Example

Load2 completing; what is waiting for Load2?

Photos, illustrations, graphics here.

31 of 64

Tomasulo Example

Photos, illustrations, graphics here.

32 of 64

Tomasulo Example

Issue ADDD here vs. scoreboard?

Photos, illustrations, graphics here.

33 of 64

Tomasulo Example

Add1 completing; what is waiting for it?

Photos, illustrations, graphics here.

34 of 64

Tomasulo Example

Photos, illustrations, graphics here.

35 of 64

Tomasulo Example

Photos, illustrations, graphics here.

36 of 64

Tomasulo Example

Add2 completing; what is waiting for it?

Photos, illustrations, graphics here.

37 of 64

Tomasulo Example

Write result of ADDD here vs. scoreboard?

All quick instructions complete in this cycle!

Photos, illustrations, graphics here.

38 of 64

Tomasulo Example

Photos, illustrations, graphics here.

39 of 64

Tomasulo Example

Photos, illustrations, graphics here.

40 of 64

Tomasulo Example

Photos, illustrations, graphics here.

41 of 64

Tomasulo Example

Photos, illustrations, graphics here.

42 of 64

Tomasulo Example

Photos, illustrations, graphics here.

43 of 64

Tomasulo Example

Photos, illustrations, graphics here.

44 of 64

Tomasulo Example

Photos, illustrations, graphics here.

45 of 64

Tomasulo Example

Once again: In-order issue, out-of-order execution and completion.

Photos, illustrations, graphics here.

46 of 64

Comparing Tomasulo and Scoreboard

  • Why take longer on scoreboard/6600?

Structural Hazards

Lack of forwarding

Photos, illustrations, graphics here.

47 of 64

Tomasulo summary

  • Reservation Stations
    • Distribute RAW hazard detection
    • Renaming eliminates WAW hazards
    • Buffering values in Reservation Stations removes WARs
    • Tag match in CDB requires many associative compares
  • Common Data Bus
    • Achilles heal of Tomasulo
    • Multiple writebacks (multiple CDBs) expensive
  • Load/Store reordering
    • Load address compared with store address in store buffer

​

Photos, illustrations, graphics here.

48 of 64

Tomasulo vs. scoreboarding

  1. No explicit checking for WAW or WAR hazards
  2. CDB broadcasts results rather than waiting on registers
  3. Loads/Store are treated like basic FUs
  4. Distributed vs. Centralized control

Photos, illustrations, graphics here.

49 of 64

Our processor so far…

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

PC

A

B

IR

IR

IR

IR

B

O

O

D

Photos, illustrations, graphics here.

50 of 64

Memory Hierarchy Design

  • Until now we have assumed an ideal memory
    • All accesses are 1 cycle
  • Unlimited size, very fast memory
    • Fast memory is very expensive (power, cost)!
    • Large amounts of fast memory would actually be very slow…
  • There are always tradeoffs in memory design:
    • Cost vs. speed & size vs. speed

​

​

​

Photos, illustrations, graphics here.

51 of 64

Memory Hierarchy Design

  • Until now we have assumed an ideal memory
    • All accesses are 1 cycle
  • Unlimited size, very fast memory
    • Fast memory is very expensive (power, cost)!
    • Large amounts of fast memory would actually be very slow…
  • There are always tradeoffs in memory design:
    • Cost vs. speed & size vs. speed

​

​

​

Smaller, fast expensive memory close to the core (Cache, $)

Larger, slower, cheaper memory farther away

Photos, illustrations, graphics here.

52 of 64

Modern Memory Hierarchy (DIMM)

Photos, illustrations, graphics here.

53 of 64

Memory Wall in Modern GPUs

AI and Memory Wall. Gholami et. al. https://arxiv.org/pdf/2403.14123

Photos, illustrations, graphics here.

54 of 64

Processor-Memory Performance Gap, “Memory Wall”

Photos, illustrations, graphics here.

55 of 64

Processor-Memory Performance Gap, “Memory Wall”

  • Suppose a processor executes:
    • Ideal CPI of 1.1
    • 50% arithmetic/logic, 30% load&store, 20% control
    • 10% of data operations have a 50 cycle miss penalty

​

​

​

Photos, illustrations, graphics here.

56 of 64

Processor-Memory Performance Gap, “Memory Wall”

  • Suppose a processor executes:
    • Ideal CPI of 1.1
    • 50% arithmetic/logic, 30% load&store, 20% control
    • 10% of data operations have a 50 cycle miss penalty

​

​

​

  • Majority of the time the processor waits on memory

​

 

Photos, illustrations, graphics here.

57 of 64

Memory Hierarchy: An overview

Fact: Large memories are slow and fast memories are small

  • How do we create a memory to give the illusion of being large, cheap, and fast (most if not all the time)?
    • Hierarchy
    • Parallelism

Speed (cycles):

Size (bytes):

Cost (per size):

½

100’s

Highest

1’s

O(10s) K

10’s

O(M)

100’s

O(10s-100s) G

1000’s

T’s

Lowest

Photos, illustrations, graphics here.

58 of 64

What do we put in smaller, faster memories?

  • Locality of memory references
    • Property of real programs, few exceptions

​

​

  • Temporal locality
    • Recently referenced data is likely to be referenced again soon
    • Reactive: cache recently used data in small, fast memory

​

  • Spatial locality
    • More likely to reference data near recently referenced data
    • Proactive: fetch data in large chunks to include nearby data, how?

​

  • Holds for data and instructions.
  • Why? Where does it come from?

Photos, illustrations, graphics here.

59 of 64

Example: Locality?

  • Data:
    • Temporal: sum referenced in each iteration
    • Spatial: array a[] accessed in stride-1 pattern
  • Instructions:
    • Temporal: cycle through loop repeatedly
    • Spatial: reference instructions in sequence

​

  • Being able to assess the locality of code is a crucial skill for a programmer

​

sum = 0;

for (i = 0; i < n; i++)

sum += a[i];

return sum;

Photos, illustrations, graphics here.

60 of 64

Basic memory structure

  • Number of entries
    • 2n, where n is number of address bits
    • Example: 1024 entries, 10 bit address
    • Decoder changes n-bit address to �2n bit “one-hot” signal
    • One-bit address travels on “wordlines”

​

  • Size of entries
    • Width of data accessed
    • Data travels on “bitlines”
    • 256 bits (32 bytes) in example

​

  • How do we use a cache entry?
    • Divide up memory in blocks too.

​

0

1

1021

1022

1023

2

3

1024*256bit

SRAM

bitlines

wordlines

10 bits

Photos, illustrations, graphics here.

61 of 64

Basic memory structure

  • Number of entries
    • 2n, where n is number of address bits
    • Example: 1024 entries, 10 bit address
    • Decoder changes n-bit address to �2n bit “one-hot” signal
    • One-bit address travels on “wordlines”

​

  • Size of entries
    • Width of data accessed
    • Data travels on “bitlines”
    • 256 bits (32 bytes) in example

​

  • How do we use a cache entry?
    • Divide up memory in blocks too.

​

0

1

1021

1022

1023

2

3

1024*256bit

SRAM

bitlines

wordlines

10 bits

Photos, illustrations, graphics here.

62 of 64

Caches: Indexing to find data

  • Basic cache: array of lines
    • Example: 32KB cache (1024 frames, 32B blocks)
    • “Hash table in hardware”
  • To find frame: decode part of address
    • Which part?
    • 32-bit address
    • 32B blocks → 5 lowest bits locate byte in block
      • These are called offset bits
    • 1024 frames → next 10 bits find frame
      • These are the index bits
    • Note: nothing says index must be these bits
    • But these work best (think about why)

​

  • How do you know you are getting the right data?

0

1

1021

1022

1023

2

3

[4:0]

[31:15]

index [14:5]

<<

1024*

256bit

SRAM

bitlines

wordlines

data

address

Photos, illustrations, graphics here.

63 of 64

Knowing that You Found It: Tags

  • Each frame can hold one of 217 blocks
    • All blocks with same index bit pattern
  • How to know which if any is currently there?
    • To each frame attach tag and valid bit (why do we need valid bits?)
    • Compare frame tag to address tag bits
      • No need to match index bits (why?)
  • Lookup algorithm
    • Read frame indicated by index bits
    • “Hit” if tag matches and valid bit is set
    • Otherwise, a “miss”. Get data from next level

0

1

1021

1022

1023

2

3

[4:0]

tag [31:15]

data

index [14:5]

<<

address

=

hit?

wordlines

Photos, illustrations, graphics here.

64 of 64

Memory Performance Metrics

  • Latency: Time to access one word
  • Bandwidth: How much data from the memory can be supplied to the processor per unit time?
    • Width of the data channel * rate of which it can be used
  • Hit Rate: Percentage of time data accessed is found in designated cache
    • Miss rate = 1 – Hit Rate

​

  • Average memory access time:
    • AMAT = (L1$ access time) * HitRate + (L2$ access time) * L1MissRate + DRAM access time * L2MissRate

Photos, illustrations, graphics here.