1 of 90

WES237B: Software for Embedded Systems

Pat Pannuto

Department of Computer Science and Engineering

University of California, San Diego

Summer Session 2023

2 of 90

Today

Morning

Performance & Optimization
Optimization in different levels (in the context of a single core)

Algorithmic (Cache Optimization), Compiler and Hardware
Memory Hierarchy

Afternoon

Lab session

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

3 of 90

Logistics

Assignment 1 due tomorrow

“Last pull” at midnight, i.e., results emailed early-am Monday

Assignment 2 released

Generally: First bit of assignment is lab portion, the rest is take-home
Finish the lab first if needed

Late policy?

1 week: 10% off
2 weeks: Last chance, 30% off
Email with any exceptional circumstances, we’ll work it out

Sign up for presentation slots (link sent out this afternoon)

6 groups of 2, two presentations per week for next three sessions

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

4 of 90

Recap

Embedded Systems (SoC) Design
ARM processor technology

ISA: ARMv4, ARMv5, ARMv6, ARMv7, ARMv8
Cortex-A5,6,7,…15

Processor Types

Microcontrollers, DSP, FPGA, GPU,…

Huffman Encoding

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

5 of 90

The guts of most interesting stuff is often ~this

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

void multiDimMath(float* const A, float* const B, float* const C, const int M, const int N, const int K)

{

for (int m = 0; m < M; m++) {

for (int n = 0; n < N; n++) {

for (int k = 0; k < K; k++) {

C[m * M + n] += A[m * M + k] * B[k * K + n];

}

6 of 90

Measuring Performance

7 of 90

The bottom line: Performance

Time to do the task

execution time, response time, latency

Tasks per day, hour, week, sec, ns. ..

throughput, bandwidth

Ferrari

Bus

Speed

160 mph

65 mph

Time to Bay Area

3.1 hours

7.7 hours

Passengers

2

60

Throughput (pmph)

320

3900

8 of 90

Measures of “Performance”

Execution Time
Throughput (operations/time)

Transactions/sec, queries/day, etc.

Frame Rate
Responsiveness
Performance / Cost
Performance / Power
Performance / Energy

9 of 90

Why Study Computer Performance?

In order to say X is n times faster than Y
Identify the benefits of running a program on a computer X, or bottlenecks of a program on a computer X
Embedded systems are too complex (CPU + FPGA + GPU) 🡺 How to measure performance of system consisting of sequential and parallel parts ?
To understand common techniques to measure performance
To know what to measure & how to measure

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

9

10 of 90

Performance is Affected by,…

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

10

11 of 90

Performance is Affected by,…

Technology

Clock speed
Processor technology

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

11

12 of 90

Performance is Affected by,…

Technology

Clock speed
Processor technology

Organization

Single core. vs. multi core
Types of processors implementation (SIMD, out of order,..)
Heterogeneous (SoC)
Memory hierarchy & memory type
Type of I/O devices
,…

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

12

13 of 90

Performance is Affected by,…

Technology

Clock speed
Processor technology

Organization

Single core. Vs. multi core
Heterogeneous (SoC)
Types of processors (SIMD, out of order,..)
Memory hierarchy & memory type
Type of I/O devices
,…

Software

Quality of compilers & libraries & parallel processing frameworks
Operating system

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

13

14 of 90

Principles of Measuring Performance

Well defined metrics

Execution time = Time spent running a program on X computer

Reproducibility

Should get the same result when you are using the same program on same machine under same conditions (OS, compiler levels,…)

Standard Benchmarks

SPEC (https://www.spec.org/benchmarks.html)

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

14

15 of 90

Performance Metrics

Raw speed = peak performance

In practice, never attainable
Clock rate * #of floating point operations/cycle (E.g., 10 Gflops)

Execution time = time to execute a program from beginning to end

The sooner the better
Wall clock time/elapsed time: Time to complete task as seen by the user. Might include operating system overhead or interference with other applications
CPU Time: does not include time spent for IO, external sources

User CPU time: CPU time spent in the program
System CPU time: CPU time spent in the OS performing taks requested by program

Throughput = total amount of work completed in a given time

Frames per second (fps)., 30 fps
Transactions or packets per second
Indication of how well hardware resources are being used

Memory: Bandwidth & Latency

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

15

16 of 90

There are many ways to measure program execution time

Program-reported time?
Wall-clock time?
user CPU time?
user + kernel CPU time?

$ time make # cargo build

Compiling hail v0.1.0 (/tock/boards/hail)

Finished release [optimized + debuginfo] target(s) in 19.96s

real 0m21.146s

user 0m30.388s

sys 0m2.032s

Well, it’s user+kernel cpu, for this class, because that’s what we can do something about.

But for the rest of the class, I’ll just say ET and you don’t have to think hard about what it means (ie, assume no other jobs, no stalls for disk, etc.)

Maybe: Note the ”time travel”. I.e. user > real in this example because of parallelism!

In case I forget: https://stackoverflow.com/questions/556405/what-do-real-user-and-sys-mean-in-the-output-of-time1

Real is wall clock time - time from start to finish of the call. This is all elapsed time including time slices used by other processes and time the process spends blocked (for example if it is waiting for I/O to complete).

User is the amount of CPU time spent in user-mode code (outside the kernel) within the process. This is only actual CPU time used in executing the process. Other processes and time the process spends blocked do not count towards this figure.

Sys is the amount of CPU time spent in the kernel within the process. This means executing CPU time spent in system calls within the kernel, as opposed to library code, which is still running in user-space. Like 'user', this is only CPU time used by the process. See below for a brief description of kernel mode (also known as 'supervisor' mode) and the system call mechanism.

17 of 90

Execution Time

Processor A is faster than the processor B

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

17

Relative performance: Performance of A is n times greater than B

18 of 90

How architects define Performance

Only has meaning in the context of a program or workload
Not very intuitive as an absolute measure, but most of the time we’re more interested in relative performance

Performance_X=

1

Execution Time_X

, for program X

19 of 90

Relative Performance

Can be confusing…

A runs in 12 seconds

B runs in 20 seconds

A/B = .6 , so A is 40% faster, or 1.4X faster, or B is 40% slower
B/A = 1.67, so A is 67% faster, or 1.67X faster, or B is 67% slower

Needs a precise definition

20 of 90

Relative Performance (Speedup), the Definition

Performance_X

Execution Time_X

Performance_Y

Speedup

Execution Time_Y

=

n

(X/Y)

21 of 90

Example

Machine A runs program C in 9 seconds.
Machine B runs the same program in 6 seconds.
What is the speedup we see if we move to Machine B from Machine A?

22 of 90

What is Time?

CPU Execution Time = CPU clock cycles * Clock cycle time

Every conventional processor has a clock with an associated clock cycle time or clock rate

Every program runs in an integral number (whole number) of clock cycles

Cycle Time

MHz = millions of cycles/second, GHz = billions of cycles/second

X MHz = 1000/X nanoseconds cycle time

Y GHz = 1/Y nanoseconds cycle time

23 of 90

CPU time

CPU time is the time CPU is computing

Not including followings

Memory access time
IO access time

CPU time = Clock cycles * Clock Period
Clock period = 1/Clock frequency

100 MHz of clock frequency = 10 ns of clock period
1GHz of clock frequency = 1 ns of clock period

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

23

24 of 90

How many clock cycles?

Number of CPU clock cycles =

[Instruction count] * [Average Clock Cycles per Instruction (CPI)]

Exercise:

Computer A runs program C in 3.6 billion cycles.

Program C requires 2 billion dynamic instructions.

What is the CPI?

25 of 90

Clock Cycles Per Instruction (CPI)

CPI is the average number of clock cycles per instruction

Throughput metric
Component metric (not a measure of performance )

Different classes of instructions can have different CPIs

CPI for floating point operations
CPI for adders, branch instructions

CPU Clock Cycles = Number of Instructions (NI)* CPI

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

25

The CPI of i^th class

The number of instructions of i^th class

26 of 90

Putting it all together

CPU Execution Time = [CPU clock cycles] * [Clock cycle time]

CPU clock cycles = [Instruction count] * [Average Clock Cycles per Instruction (CPI)]

CPU Execution Time

Instruction Count

CPI

Clock Cycle Time

=

X

instructions

cycles/instruction

seconds/cycle

seconds

27 of 90

CPU Execution Time

CPU Execution Time = CPU Clock Cycles * Clock Period

= NI*CPI*Clock Period

Execution time depends on

Number of instructions : Determined by the ISA

Programmable hardware counters can be used to find NI
Profiling tools such as gprof, valgrind

CPI: determined by the ISA & Compiler & Organization (Parallel execution)

Can be determined in software using simulator

Clock period: Determined by the process technology and implementation

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

27

28 of 90

Cycle Time/Clock Rate is no longer fixed

Increasingly, modern processors can execute at multiple clock rates (cycle times).
Why?
However, the granularity at which we can change the cycle time tends to be fairly coarse, so all of these principles and formulas still apply.

29 of 90

Who Affects Performance? How?

programmer
compiler
instruction-set architect
machine architect
hardware designer
materials scientist/physicist/silicon engineer

CPU Execution Time

Instruction Count

CPI

Clock Cycle Time

=

X

30 of 90

Which programs are best, are “most fair”, to run when measuring performance?

peak throughput measures (simple programs)?
synthetic benchmarks (whetstone, dhrystone,...)?
Real applications
SPEC (best of both worlds, but with problems of their own)

System Performance Evaluation Cooperative
Provides a common set of real applications

Along with strict guidelines for how to run them

Provides a relatively unbiased means to compare machines.

31 of 90

Amdahl’s Law

The impact of a performance improvement is limited by the percent of execution time affected by the improvement

Make the common case fast!!

Execution time

after improvement

=

Execution Time Affected

Amount of Improvement

Execution Time Unaffected

+

32 of 90

Amdahl’s Law and Massive Parallelism

.9

.1

33 of 90

Amdahl’s Law and Massive Parallelism

.9

.1

.45

Speedup

1.0

1/.55 = 1.82

34 of 90

Amdahl’s Law and Massive Parallelism

.9

.1

.45

.225

Speedup

1.0

1/.55 = 1.82

1/.325 = 3.07

35 of 90

Amdahl’s Law and Massive Parallelism

.9

.1

.45

.225

Speedup

1.0

1/.55 = 1.82

1/.325 = 3.07

< 10

36 of 90

Optimizations

37 of 90

What to optimize on a CPU?

Program type

Compute-bound
I/O bound

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

	Number of Instructions (NI)	CPI	Clock Frequency
Program	🗹
Compiler	🗹	🗹
ISA	🗹	🗹
Organization		🗹	🗹
Technology			🗹

CPU Execution Time = CPU Clock Cycles * Clock Period

= NI*CPI*Clock Period

Reduce Clock Period 🡺 Increase clock frequency
Decrease NI
Decrease CPI

38 of 90

Optimization is

An application X 🡺 optimize it on Y?

Where should I start?

When I know if I hit the target performance (or do I have a target performance)?

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

hard

Both system level and low-level knowledge/experience is needed
system level 🡺 Algorithmic, Compiler, Multi-core,…
Low-level🡪 Cache organization, compiler optimization,…

39 of 90

Optimization is hard (and getting harder…)

Must understand system as a whole to optimize

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Software Application

Compiler

Hardware (A GPU)

Algorithmic Optimization
Big O(n2) 🡪 Big O(nlogn)
Arithmetic optimizations
Algorithmic changes that uses HW efficiently
..

Loop vectorization
Constant subexpression elimination
,…

Micro architectural design
Frequency/Clock cycles
Instruction level parallelism…
Cache optimization..

Possible #of total optimization space = #algorithms * compiler optimization* # hardware optimizations 🡺 Optimization search space

40 of 90

Optimization is hard (and getting harder…)

Must understand system as a whole to optimize

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Software Application

Compiler

Algorithmic Optimization
Big O(n2) 🡪 Big O(nlogn)
Arithmetic optimizations
Algorithmic changes that uses HW efficiently
..

Loop vectorization
Constant subexpression elimination
,…

Micro architectural design,
Frequency/Clock cycles
Instruction level parallelism…
Cache optimization..

Hardware (A GPU)

[ or TPU or …]

Heterogenous (or system with multiple hardware units) 🡪 optimization parameter search space is large

41 of 90

Optimizations in Different Levels

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Software

Hardware

ISA

Pipelining, out-of-order execution,

Branch prediction, superscalar,

Cache organization, multi-core,…

Multithreading, Inline Assembly,

Blocking, Loop interchange,..etc.

Compiler level optimizations such

as dead code elimination, ..

Optimization: Must optimize at multiple levels:

Algorithm level, data representations, procedures, compiler, and hardware,...

42 of 90

Optimizations

Must understand system as a whole to optimize for performance
How programs are compiled and executed
How modern processors + memory systems operate
How to measure program performance and identify bottlenecks
How to improve performance without destroying code modularity and generality

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

43 of 90

Micro Architecture

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

43

44 of 90

Instruction Level Parallelism

Need general understanding of modern processor design
Hardware can execute multiple instructions in parallel
Performance limited by data dependencies
Simple transformations can yield dramatic performance improvement
Compilers often (sometimes) cannot make these transformations

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective; Third Edition

45 of 90

Superscalar processor

A superscalar processor can issue and execute multiple instructions in one cycle. The instructions are retrieved from a sequential instruction stream and are usually scheduled dynamically.
Benefit: without programming effort, superscalar processor can take advantage of the instruction level parallelism that most programs have
Most modern CPUs are superscalar
Intel: since Pentium (1993)

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective; Third Edition

46 of 90

Pipelined Functional Units

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Stage 1

Stage 2

Stage 3

long mult_eg(long a, long b, long c) {

long p1 = a*b;� long p2 = a*c;� long p3 = p1 * p2;

return p3;�}

Divide computation into stages
Pass partial computations from stage to stage
Stage i can start on new computation once values passed to i+1
E.g., complete 3 multiplications in 7 cycles, even though each requires 3 cycles

	Time
	1	2	3	4	5	6	7
Stage 1	a*b	a*c			p1*p2
Stage 2		a*b	a*c			p1*p2
Stage 3			a*b	a*c			p1*p2

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective; Third Edition

47 of 90

Haswell CPU

Multiple instructions can execute in parallel

2 load, with address computation
1 store, with address computation
4 integer
2 FP multiply
1 FP add
1 FP divide

Some instructions take > 1 cycle, but can be pipelined

Instruction Latency Cycles/Issue
Load / Store 4 1
Integer Multiply 3 1
Integer/Long Divide 3-30 3-30
Single/Double FP Multiply 5 1
Single/Double FP Add 3 1
Single/Double FP Divide 3-15 3-15

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective; Third Edition

48 of 90

SIMD (Single Instruction Multiple Data)

SIMD Operations: Single Precision

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

%zmm0

%zmm1

vaddsd %zmm0, %zmm1, %zmm1

+

%zmm0

%zmm1

vaddds %zmm0, %zmm1, %zmm1

SIMD Operations: Double Precision

Example AVX-512F (a subset of AVX-512) instructions (ARM case Neon)

zmm0 ...zmm31 are 512 bit registers; each can hold

16 single-precision (float of C; 32 bits) or
8 double-precision (double of C; 64 bits) ﬂoating point numbers

Operation	Syntax
*	vmulps %zmm0,%zmm1,%zmm2
+	vaddps %zmm0,%zmm1,%zmm2
	….
Float +	vfmadd132ps %zmm0,%zmm1,%zmm2
load	vmovups 256(%rax),%zmm0
Store	vmovups %zmm0,256(%rax)

49 of 90

ARM Matrix Multiplication with SIMD

https://developer.arm.com/documentation/102467/0200/Example---matrix-multiplication

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

void matrix_multiply_4x4_neon(float32_t *A, float32_t *B, float32_t *C) {

…

// Multiply accumulate in 4x1 blocks,

// i.e. each column in C

B0 = vld1q_f32(B);

C0 = vfmaq_laneq_f32(C0, A0, B0, 0);

C0 = vfmaq_laneq_f32(C0, A1, B0, 1);

C0 = vfmaq_laneq_f32(C0, A2, B0, 2);

C0 = vfmaq_laneq_f32(C0, A3, B0, 3);

vst1q_f32(C, C0);

…

}

50 of 90

The Memory Hierarchy

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

50

51 of 90

Random-Access Memory (RAM)

RAM is traditionally packaged as a chip
Basic storage unit is a cell(one bit)
Multiple RAM chips form a memory
Types: Static RAM, Dynamic RAM
DRAM/SRAM are volatile memories

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

	Trans per bit	Access Time	Needs Refresh	Cost	Application
SRAM	4/6	1X	No	100X	Cache memories/Scratch pad
DRAM	1	10X	Yes	1X	Main memories, frame buffers

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective; Third Edition

52 of 90

Processor and Memory Gap

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

HP, Computer Architecture A Quantitate Approach, 2011

53 of 90

Processor and Memory Gap

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective; Third Edition

54 of 90

Processor and Memory Power Consumption

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

The energy consumption for various arithmetic operations and memory accesses in a 45 nm

process.

Sze, Vivienne, et al. "Efficient Processing of Deep Neural Networks." Synthesis Lectures on Computer Architecture 15.2 (2020): 1-341.

55 of 90

Slow memory, faster processor: What can we do?

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

55

56 of 90

Locality

Principle of Locality: Programs tend to use data and instructions with addresses near or equal to those they have used recently

Temporal locality:

Recently referenced items are likely �to be referenced again in the near future

Spatial locality:

Items with nearby addresses tend �to be referenced close together in time

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective; Third Edition

57 of 90

Locality Example

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

sum = 0;

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

sum += a[i];

return sum;

58 of 90

C Memory

C is row major order
Meaning that if you have 2D array

Laid out as: Row 0, Row 1, Row 2,…. Row N.

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

59 of 90

Locality Example

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

int sum_array_rows(int a[M][N])

{

int i, j, sum = 0;

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

for (j = 0; j < N; j++)

sum += a[i][j];

return sum;

}

int sum_array_cols(int a[M][N])

{

int i, j, sum = 0;

for (j = 0; j < N; j++)

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

sum += a[i][j];

return sum;

}

Does these functions have good locality with respect to array a[]?

60 of 90

Memory Hierarchies

Some fundamental and enduring properties of hardware and software:

Fast storage technologies cost more per byte, have less capacity, and require more power (heat!).
The gap between CPU and main memory speed is widening.
Well-written programs tend to exhibit good locality.

They suggest an approach (trade-off) for organizing memory and storage systems known as a memory hierarchy.

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Trade-off

61 of 90

Memory Hierarchies

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Regs

L1 cache

(SRAM)

Main memory

(DRAM)

Local secondary storage

(local disks)

Larger,

slower,

and

cheaper

(per byte)

storage

devices

Remote secondary storage

(e.g., Web servers)

Local disks hold files retrieved from disks

on remote servers

L2 cache

(SRAM)

L1 cache holds cache lines retrieved from the L2 cache.

CPU registers hold words retrieved from the L1 cache.

L2 cache holds cache lines

retrieved from L3 cache

L0:

L1:

L2:

L3:

L4:

L5:

Smaller,

faster,

and

costlier

(per byte)

storage

devices

L3 cache

(SRAM)

L3 cache holds cache lines

retrieved from main memory.

L6:

Main memory holds disk blocks retrieved from local disks.

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective; Third Edition

62 of 90

A Modern Memory Hierarchy

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

Register File, 32 words, sub-nsec

L1 Cache, ~32 KB, ~nsecs

L2 cache, 512KB – 1 MB, ~nsecs

L3 Cache, ~ 10 nsecs

Main memory (DRAM), GB, ~100 ns

Disk, 100 GB, ~10 msec

63 of 90

The guts of most interesting stuff is often ~this

CC BY-NC-ND Pat Pannuto – Many slides adapted from Janarbek Matai

void Foo(float* const A, float* const B, float* const C, const int M, const int N, const int K)

{

for (int m = 0; m < M; m++) {

for (int n = 0; n < N; n++) {

for (int k = 0; k < K; k++) {

C[m * M + n] += A[m * M + k] * B[k * K + n];

}

And these are huge

Lab2: image.tif

480x640 pixels * 4 bytes/float ~= 1.3 MB (greyscale!)

64 of 90

Cache Fundamentals

(if time)

65 of 90

Cache

Cache: A smaller, faster storage device that acts as a staging area for a subset of the data in a larger, slower device.
Fundamental idea of a memory hierarchy:

For each k, the faster, smaller device at level k serves as a cache for the larger, slower device at level k+1.

Why do memory hierarchies work?

Because of locality, programs tend to access the data at level k more often than they access the data at level k+1.
Thus, the storage at level k+1 can be slower, and thus larger and cheaper per bit.

Big Idea: The memory hierarchy creates a large pool of storage that costs as much as the cheap storage near the bottom, but that serves data to programs at the rate of the fast storage near the top.

65

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective; Third Edition

66 of 90

Cache hierarchy vocabulary

Cache hit: When data needed by CPU is in the cache
Cache miss: When data needed by CPU is not in the cache

Cache controller must fetch data into cache and return it to CPU
Compulsory miss, conflict miss, capacity miss
THRASHING

Cache tag
Cache valid
Evict
Cache block or Cache Line

66

67 of 90

Locality and cacheing

Memory hierarchies exploit locality by cacheing (keeping close to the processor) data likely to be used again.
This is done because we can build large, slow memories and small, fast memories, but we can’t build large, fast memories.
If it works, we get the illusion of SRAM access time with disk capacity

SRAM access times are ~1ns at cost of $2000 to $5000 per Gbyte.
DRAM access times are ~70ns at cost of $20 to $75 per Gbyte.
Disk access times are 5 to 20 million ns at cost of $.20 to $2 per Gbyte.

68 of 90

A typical memory hierarchy

CPU

memory

on-chip caches

off-chip cache

main memory

disk

small

expensive $/bit

cheap $/bit

big

so then where is my program and data??

fast

slow

memory

69 of 90

Cache Fundamentals

cpu

lowest-level

cache

next-level

memory/cache

70 of 90

Cache Fundamentals

cache hit -- an access where the data is found in the cache.

cpu

lowest-level

cache

next-level

memory/cache

71 of 90

Cache Fundamentals

cache hit -- an access where the data is found in the cache.
cache miss -- an access which isn’t

cpu

lowest-level

cache

next-level

memory/cache

72 of 90

Cache Fundamentals

cache hit -- an access where the data is found in the cache.
cache miss -- an access which isn’t
hit time -- time to access the cache

cpu

lowest-level

cache

next-level

memory/cache

73 of 90

Cache Fundamentals

cache hit -- an access where the data is found in the cache.
cache miss -- an access which isn’t
hit time -- time to access the cache
miss penalty -- time to move data from further level to closer

cpu

lowest-level

cache

next-level

memory/cache

74 of 90

Cache Fundamentals

cache hit -- an access where the data is found in the cache.
cache miss -- an access which isn’t
hit time -- time to access the cache
miss penalty -- time to move data from further level to closer
hit ratio -- percentage of time the data is found in the cache

cpu

lowest-level

cache

next-level

memory/cache

75 of 90

Cache Fundamentals

cache hit -- an access where the data is found in the cache.
cache miss -- an access which isn’t
hit time -- time to access the cache
miss penalty -- time to move data from further level to closer
hit ratio -- percentage of time the data is found in the cache
miss ratio -- (1 - hit ratio)

cpu

lowest-level

cache

next-level

memory/cache

76 of 90

Cache Fundamentals, cont.

cache block size or cache line size– the amount of data that gets transferred on a cache miss.

cpu

lowest-level

cache

next-level

memory/cache

77 of 90

Cache Fundamentals, cont.

cache block size or cache line size – the amount of data that gets transferred on a cache miss.
instruction cache – cache that only holds instructions.

cpu

lowest-level

cache

next-level

memory/cache

78 of 90

Cache Fundamentals, cont.

cache block size or cache line size – the amount of data that gets transferred on a cache miss.
instruction cache – cache that only holds instructions.
data cache – cache that only caches data.

cpu

lowest-level

cache

next-level

memory/cache

79 of 90

Cache Fundamentals, cont.

cache block size or cache line size – the amount of data that gets transferred on a cache miss.
instruction cache – cache that only holds instructions.
data cache – cache that only caches data.
unified cache – cache that holds both.

cpu

lowest-level

cache

next-level

memory/cache

80 of 90

Cacheing Issues

On a memory access -

How do I know if this is a hit or miss?

On a cache miss -

where to put the new data?
what data to throw out?
how to remember what data this is?

cpu

lowest-level

cache

next-level

memory/cache

access

miss

81 of 90

Hardware implications on cache design

Caches are basically the thing that make real workloads fast
The size of a cache is inversely proportional to its speed

Smaller caches are faster

And every bit counts

This is why caches use as few bits as possible to do their work

This makes caches tricky to walk through as a human

82 of 90

Examples of simple caches

82

83 of 90

A simple cache

A cache that can put a line of data anywhere is called __________________________
The most popular replacement strategy is LRU ( ).

tag

data

the tag identifies

the address of

the cached data

4 entries, each block holds one word, any block

can hold any word.

address string:

4 00000100

8 00001000

12 00001100

4 00000100

8 00001000

20 00010100

4 00000100

8 00001000

20 00010100

24 00011000

12 00001100

8 00001000

4 00000100

84 of 90

A simple cache

A cache that can put a line of data anywhere is called Fully Associative
The most popular replacement strategy is LRU ( Least Recently Used ).

tag

data

the tag identifies

the address of

the cached data

4 entries, each block holds one word, any block

can hold any word.

address string:

4 00000100

8 00001000

12 00001100

4 00000100

8 00001000

20 00010100

4 00000100

8 00001000

20 00010100

24 00011000

12 00001100

8 00001000

4 00000100

85 of 90

A simpler cache

A cache that can put a line of data in exactly one place is called __________________.
Advantages/disadvantages vs. fully-associative?

an index is used

to determine

which line an address

might be found in

4 entries, each block holds one word, each word

in memory maps to exactly one cache location.

00000100

tag

data

address string:

4 00000100

8 00001000

12 00001100

4 00000100

8 00001000

20 00010100

4 00000100

8 00001000

20 00010100

24 00011000

12 00001100

8 00001000

4 00000100

86 of 90

A simpler cache

A cache that can put a line of data in exactly one place is called direct mapped
Advantages/disadvantages vs. fully-associative?

an index is used

to determine

which line an address

might be found in

4 entries, each block holds one word, each word

in memory maps to exactly one cache location.

00000100

tag

data

address string:

4 00000100

8 00001000

12 00001100

4 00000100

8 00001000

20 00010100

4 00000100

8 00001000

20 00010100

24 00011000

12 00001100

8 00001000

4 00000100

87 of 90

A set-associative cache

A cache that can put a line of data in exactly n places is called n-way ______________________.
The cache lines/blocks that share the same index are a cache ____________.

tag

data

4 entries, each block holds one word, each word

in memory maps to one of a set of n cache lines

00000100

tag

data

address string:

4 00000100

8 00001000

12 00001100

4 00000100

8 00001000

20 00010100

4 00000100

8 00001000

20 00010100

24 00011000

12 00001100

8 00001000

4 00000100

88 of 90

A set-associative cache

A cache that can put a line of data in exactly n places is called n-way set-associative.
The cache lines/blocks that share the same index are a cache set.

tag

data

4 entries, each block holds one word, each word

in memory maps to one of a set of n cache lines

00000100

tag

data

address string:

4 00000100

8 00001000

12 00001100

4 00000100

8 00001000

20 00010100

4 00000100

8 00001000

20 00010100

24 00011000

12 00001100

8 00001000

4 00000100

89 of 90

Longer Cache Blocks

Large cache blocks take advantage of spatial locality.
Too large of a block size can waste cache space.
Longer cache blocks require less tag space

tag

data

4 entries, each block holds two words, each word

in memory maps to exactly one cache location

(this cache is twice the total size of the prior caches).

address string:

4 00000100

8 00001000

12 00001100

4 00000100

8 00001000

20 00010100

4 00000100

8 00001000

20 00010100

24 00011000

12 00001100

8 00001000

4 00000100

00000100

90 of 90

Longer Cache Blocks

Large cache blocks take advantage of spatial locality.
Too large of a block size can waste cache space.
Longer cache blocks require less tag space

tag

data (now 64 bits)

4 entries, each block holds two words, each word

in memory maps to exactly one cache location

(this cache is twice the total size of the prior caches).

address string:

4 00000100

8 00001000

12 00001100

4 00000100

8 00001000

20 00010100

4 00000100

8 00001000

20 00010100

24 00011000

12 00001100

8 00001000

4 00000100

00000100