Question

Media applications that play audio or video files are part of a class of workloads called “streaming” workloads; i.e., they bring in large amounts of data but do not reuse much of it. Consider a video streaming workload that accesses a 512 KiB working set sequentially with the following address stream:

0, 2, 4, 6, 8, 10, 12, 14, 16, …

5.5.1 Assume a 64 KiB direct-mapped cache with a 32-byte block. What is the miss rate for the address stream above? How is this miss rate sensitive to the size of the cache or the working set? How would you categorize the misses this workload is experiencing, based on the 3C model?

5.5.2 Re-compute the miss rate when the cache block size is 16 bytes, 64 bytes, and 128 bytes. What kind of locality is this workload exploiting?

5.5.3 “Prefetching” is a technique that leverages predictable address patterns to speculatively bring in additional cache blocks when a particular cache block is accessed. One example of prefetching is a stream buffer that prefetches sequentially adjacent cache blocks into a separate buffer when a particular cache block is brought in. If the data is found in the prefetch buffer, it is considered as a hit and moved into the cache and the next cache block is prefetched. Assume a two-entry stream buffer and assume that the cache latency is such that a cache block can be loaded before the computation on the previous cache block is completed. What is the miss rate for the address stream above?

Cache block size (B) can affect both miss rate and miss latency. Assuming a 1-CPI machine with an average of 1.35 references (both instruction and data) per instruction, help find the optimal block size given the following miss rates for various block sizes.

$\mathbf{8}\mathbf{:}\mathbf{4}\mathbf{\%}$

$\mathbf{16}\mathbf{:}\mathbf{3}\mathbf{\%}$

$\mathbf{32}\mathbf{:}\mathbf{2}\mathbf{\%}$

$\mathbf{64}\mathbf{:}\mathbf{1}\mathbf{.}\mathbf{5}\mathbf{\%}$

$\mathbf{128}\mathbf{:}\mathbf{1}\mathbf{\%}$

5.5.4 What is the optimal block size for a miss latency of 20×B cycles?

5.5.5 What is the optimal block size for a miss latency of 24+B cycles?

5.5.6 For constant miss latency, what is the optimal block size

Short answer

5.5.1

Miss rate$=\frac{1}{16}$

5.5.2

if the cache block size is 16 byte

the miss rate for the given address stream is $\frac{1}{miss}$$=\frac{1}{8}$

if the cache block size is 64 byte

The miss rate for the given address stream is$\frac{1}{miss}$$=\frac{1}{32}$

If the cache block size is 128 byte

The miss rate for the given address stream is$\frac{1}{miss}$$=\frac{1}{64}$

andthe workload is exploiting spatial locality

5.5.3

The miss rate is$0\cdot 00038\%=0\%$

5.5.4

Brole="math" localid="1655285883526" $=8$ is the optimal block size

5.5.5

B role="math" localid="1655285902426" $=32$is the optimal block size

5.5.6

B = 128 is optimal

Step-by-step solution

Determine the formulae

Write the formula for calculating the size of the block

$Sizeoftheblock$role="math" localid="1655286115236" $=\frac{videostreamingworkloadaccessesdata}{Cachelinesize}$ …….(1)

Write the formula for calculating the miss rate for the address stream

$missratefortheaddressstream=\frac{Sizeofthedirect-mappedcache}{Sizeoftheblock}$……..(2)

Write the formula for calculating miss rate

role="math" localid="1655286304946" $Missrate=\frac{numberofmisses}{totalaccesses}$ ……..(3)

Determine the miss rate for the given address stream

5.5.1

Video streaming workload that accesses data = 512 KiB

Given address stream =$0,2,4,6,8,10,12,14,\mathrm{16.....}$

Difference between the stream = 2

Size of direct-mapped cache = 64 KiB

Cache line size =32-byte

First, we calculate the size of the block

Now we calculate the miss rate for the address stream

$\begin{array}{c}\mathrm{Miss}\mathrm{rate}\mathrm{for}\mathrm{the}\mathrm{address}\mathrm{stream}=\frac{\mathrm{Size}\mathrm{of}\mathrm{the}\mathrm{direct}-\mathrm{mapped}\mathrm{cache}}{\mathrm{Size}\mathrm{of}\mathrm{the}\mathrm{block}}\\ =\frac{64\mathrm{KiB}}{16\mathrm{K}}\\ =4\mathrm{B}\\ =4\times 8\mathrm{bits}\\ =32\mathrm{bits}\end{array}$

Difference between the stream 2 so the miss occurs at the$\begin{array}{l}=\frac{32}{2}\\ ={16}^{th}access\end{array}$

Therefore, the miss will occur for every${16}^{\mathrm{th}}$ access of the address stream

So, the miss rate for the given address stream is$\frac{1}{miss}$$=\frac{1}{16}$

Miss rate is not sensitive because miss rate is not dependent on the size of the cache or working set.

categorize the misses

The miss will occur for every ${16}^{\mathrm{th}}$access of the address stream so in every 16 addresses of the stream there are 15 hits and 1 miss.

Therefore, the number of misses is predictable for a given workload.

Based on the 3C model the misses in this workload is experiencing cold-stat misses or compulsory misses

Re-compute the miss rate if the cache block size is 16 byte

Given data

Video streaming workload that accesses data = 512 KiB

Given address stream =$0,2,4,6,8,10,12,14,\mathrm{16.....}$

Difference between the stream = 2

Size of direct-mapped cache = 64 KiB

Case 1:

If cache line size = 16 byte

Difference between the stream 2 so the miss occurs at the$\begin{array}{l}=\frac{16}{2}\\ =8^{th}access\end{array}$

Therefore, the miss will occur for every$8^{th}$ access of the address stream

So, the miss rate for the given address stream is$\frac{1}{miss}$$=\frac{1}{8}$

Re-compute the miss rate if the cache block size is 64 byte

If cache line size = 64 byte

$\begin{array}{c}\mathrm{size}\mathrm{of}\mathrm{the}\mathrm{block}=\frac{\mathrm{video}\mathrm{streaming}\mathrm{workload}\mathrm{accesses}\mathrm{data}}{\mathrm{Cache}\mathrm{line}\mathrm{size}}\\ =\frac{512\mathrm{KiB}}{64\mathrm{bytes}}\\ =8\mathrm{K}\end{array}$

$\begin{array}{c}\mathrm{Miss}\mathrm{rate}\mathrm{for}\mathrm{the}\mathrm{address}\mathrm{stream}=\frac{\mathrm{Size}\mathrm{of}\mathrm{the}\mathrm{direct}-\mathrm{mapped}\mathrm{cache}}{\mathrm{Size}\mathrm{of}\mathrm{the}\mathrm{block}}\\ =\frac{64\mathrm{KiB}}{8\mathrm{K}}\\ =8\mathrm{B}\\ =8\times 8\mathrm{bits}\\ =64\mathrm{bits}\end{array}$

Difference between the stream 2 so the miss occurs at the$\begin{array}{l}=\frac{64}{2}\\ ={32}^{th}access\end{array}$

Therefore, the miss will occur for every${32}^{th}$ access of the address stream

So, the miss rate for the given address stream is$\frac{1}{miss}$$=\frac{1}{32}$

Re-compute the miss rate if the cache block size is 128 byte

If cache line size = 128 byte

$\begin{array}{c}\mathrm{Miss}\mathrm{rate}\mathrm{for}\mathrm{the}\mathrm{address}\mathrm{stream}=\frac{\mathrm{Size}\mathrm{of}\mathrm{the}\mathrm{direct}-\mathrm{mapped}\mathrm{cache}}{\mathrm{Size}\mathrm{of}\mathrm{the}\mathrm{block}}\\ =\frac{64\mathrm{KiB}}{4\mathrm{K}}\\ =16\mathrm{B}\\ =16\times 8\mathrm{bits}\\ =128\mathrm{bits}\end{array}$

Difference between the stream 2 so the miss occurs at the$\begin{array}{l}=\frac{128}{2}\\ ={64}^{th}access\end{array}$

Therefore, the miss will occur for every ${32}^{th}$access of the address stream

So, the miss rate for the given address stream is$\frac{1}{miss}$$=\frac{1}{64}$

kind of locality is this workload

Spatial memory locality is considered to occur if a location has been referenced recently and there is a chance of it being referenced again in the future and here Every access has a nearby location.

So, the workload is exploiting spatial locality

Using Prefetching to reduce the miss rate to zero

5.5.3

Given data

Video streaming workload that accesses data = 512 KiB

Given address stream =$0,2,4,6,8,10,12,14,\mathrm{16.....}$

Difference between the stream = 2

Size of direct-mapped cache = 64 KiB

Due to the two-entry stream buffer and the cache latency, a cache block can be loaded before the previous cache block is finished being computed.

Prefetching is used to predict future accesses to the cache memory as the current block is being executed, the new predicted block is preloaded into the cache memory, thereby reducing the miss rate to zero

Number of misses = 1

Total accesses

Now, calculate the miss rate $=\frac{512KB}{2}$

$\begin{array}{c}=\frac{512\times 1024}{2}\\ =26144\end{array}$

Now, calculate the miss rate

Therefore, the miss rate is$0\cdot 00038\%=0\%$

Determine the optimal block size for a miss latency of 20×B cycles

5.5.4

To determine the optimal block size for a miss latency we calculate AMAT (Average memory access time) for B

AMAT for B $=8:0.040\times (20\times 8)$

$=6\cdot 40$

AMAT for B $=16:0.030\times (20\times 16)$

$=9\cdot 60$

AMAT for B $=32:0.020\times (20\times 32)$

$=12\cdot 80$

AMAT for B $=64:0.015\times (20\times 64)$

$=19\cdot 20$

AMAT for B$=128:0.010\times (20\times 128)$

$=25\cdot 60$

B $=8$ is the optimal block size for a miss latency of 20×B cycles

Determine the optimal block size for a miss latency of 24+B cycles

5.5.5

Again, we calculate AMAT (Average memory access time) to determine the optimal block size for miss latency of 24+B cycles

AMAT for B $=8:0.040\times (24+8)$

$=1\cdot 28$

AMAT for B $=16:0.030\times (24+16)$

$=1\cdot 20$

AMAT for B $=32:0.020\times (24+32)$

$=1\cdot 12$

AMAT for B$=64:0.015\times (24+64)$

$=1\cdot 32$

AMAT for B$=128:0.010\times (24+128)$

$=1\cdot 52$

$\mathrm{B}=32$is the optimal block size for a miss latency of 24×B cycles .

Determine the optimal block size for constant miss latency

B = 128 is optimal

Because it Is minimizing the miss rate minimizes the total miss latency.