Final Practice Problems | CSCI 343

Topics covered on the exam

• Arrays of RAM
• Cache size computation
• Cache Performance
• Potentially cache mapping questions if you didn’t have a quiz 3 on it
• Short-answer questions
• Questions based on presentations

Note

$b$ = bits
$B$ = bytes

RAM Expansion Problems

Problem 1

Given a RAM configuration $1\text{K} \times 16$, we want to:

• Increase the RAM capacity 10 times
• Access word 3079 (draw the circuit and indicate the settings to accommodate this task)

Solution

Put 10 chips together ($C_0$—$C_9$), 1024 words each

$$3079 = 3 \times 1024 + 7 \implies \text{access chip 3, with offset 7}$$ $$3079 = 2^{11} + 2^{10} + 7 = \texttt{110000000111}_2$$

Chip config $1\text{K} \times 16 = 2^{10} \times 16$ indicates:

$$\text{Bit width for the offset: } 10 \text{ bits}$$ $$\text{Word size: } 16 \text{ bits } \implies 16\text{-bit address}$$ $$16 - 10 = 6 \implies 6 \text{ bits for chip \#}$$

Address Structure:

$$\underset{{6 \text{ bits}}}{\boxed{\phantom{0}0\ 0\ 0\ 0\ 1\ 1\phantom{/}}} \underset{{10 \text{ bits}}}{\boxed{\phantom{0}0\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 1\ 1\phantom{/}}}$$

Circuit and its settings:

Implement a decoder to act as chip select. To accomodate 10 chips, we need a decoder with input size: $\lceil log_2{10} \rceil = 4$ bits

So, our $4 \times 2^4$ decoder takes chip # $3$ (= $0011_2$) as input and enables output line 3, activating $C_3$‘s CS line. Outputs 10—15 are unused.

Problem 2

Given a RAM configuration $2\text{K} \times 8$ and a 16-bit address size, we want to:

• Increase the RAM capacity 8 times
• Access word 5140 (draw the circuit and indicate the settings to accommodate this task)

Solution

Put 8 chips together ($C_0$—$C_7$), 2048 words each

$$5140 = 2 \times 2048 + 1044 \implies \text{access chip 2, with offset 1044}$$ $$5140 = 2^{12} + 2^{10} + 2^4 + 2^2 = \texttt{1010000010100}_2$$

Chip config $2\text{K} \times 8 = 2^{11} \times 8$ indicates:

$$\text{Bit width for the offset: } 11 \text{ bits}$$ $$\text{Address size: } 16 \text{ bits (indicated in the problem statement)}$$ $$16 - 11 = 5 \implies 5 \text{ bits for chip \#}$$

Address Structure:

$$\underset{{5 \text{ bits}}}{\boxed{\phantom{0}0\ 0\ 0\ 1\ 0\phantom{/}}} \underset{{11 \text{ bits}}}{\boxed{\phantom{0}1\ 0\ 0\ 0\ 0\ 0\ 1\ 0\ 1\ 0\ 0\phantom{/}}}$$

Circuit and its settings:

Implement a decoder to act as chip select. To accomodate 8 chips, we need a decoder with input size: $\lceil log_2{8} \rceil = 3$ bits

So, our $3 \times 2^3$ decoder takes chip # $2$ (= $010_2$) as input and enables output line 2, activating $C_2$‘s CS line.

Total Cache Size Computation Problems

Problem 1

Find the total # of bytes for a direct mapping cache to store 64 KB in 1-word blocks, assuming a word size of 32 bits and MIPS addressing.

Solution

1-word blocks $\implies$ no word select bits.

Word size 32 bits $\implies$ 32-bit address.

MIPS Addressing $\implies$ Byte Addressing $\implies$ Allocate bits for byte #

Address structure:

$$\overbrace{ \boxed{\phantom{000}\text{Tag}\phantom{00/}} \boxed{\phantom{0}\text{line \#}\phantom{/}} \boxed{\phantom{0}\text{byte \#}\phantom{/}} }^{\small 32 \text{ bits}}$$

$$\begin{aligned} \text{Word size} &= 32 \text{ bits} \\ &= 4\text{ B} \\ &= 2^2 \text{ B} \implies 2 \text{ bits for byte \#} \\[2em] \text{Data} &= 64 \text{ KB} \\ &= 2^6 \times 1 \text{ KB} \\ &= 2^6 \times 2^{10} \text{ B}\\ &= 2^{16} \text{ B} \\[2em] \text{\# of lines} &= \frac{\text{Data Size}}{\text{Block Size}} \\[1em] &= \frac{2^{16} \text{ B}}{2^2 \text{ B}} \\[1em] &= 2^{14} \text{ lines} \implies 14 \text{ bits for line \#} \end{aligned}$$ $$\text{Tag} = 32 - (14 + 2) = 16 \text{ bits}$$

Address Structure:

$$\underset{16\ b}{\boxed{\phantom{000}\text{Tag}\phantom{000}}} \underset{14\ b}{\boxed{\phantom{0}\text{line \#}\phantom{0}}} \underset{2\ b}{\boxed{\phantom{0}\text{byte \#}\phantom{0}}}$$

Each line is $1 + 16 + 32 = 49$ bits.

Total cache size:

$$\begin{aligned} 2^{14} \text{ lines} \ \times \ 49 \text{ bits/line} \ &= 49 \cdot 2^{14} \text{ b} \\ & = 49 \cdot 2^{11} \text{ B} \\ & = 49 \cdot 2 \text{ KB} \\ & = 98 \text{ KB} \end{aligned}$$

Problem 2

Find the total # of bytes for a direct mapping cache to store 128 KB in 2-word blocks, assuming a word size of 64 bits and byte addressing.

Solution

2-word blocks $\implies$ 1 word select bit.

Word size 64 bits $\implies$ 64-bit address.

Byte Addressing $\implies$ Allocate bits for byte #

Address structure:

$$\overbrace{ \boxed{\phantom{000}\text{Tag}\phantom{00/}} \boxed{\phantom{0}\text{line \#}\phantom{/}} \boxed{\phantom{0}\text{word \#}\phantom{/}} \boxed{\phantom{0}\text{byte \#}\phantom{/}} }^{\small 64 \text{ bits}}$$

$$\begin{aligned} \text{Word size} &= 64 \text{ bits} \\ &= 8\text{ B} \\ &= 2^3 \text{ B} \implies 3 \text{ bits for byte \#} \\[2em] \text{Block size} &= 2 \text{ words} \\ &= 2^1 \text{ words} \implies 1 \text{ bit for word \#} \\[2em] \text{Data} &= 128 \text{ KB} \\ &= 2^7 \times 1 \text{ KB} \\ &= 2^7 \times 2^{10} \text{ B}\\ &= 2^{17} \text{ B} \\[2em] \text{Block size} &= 2 \text{ words} \\ &= 2 \times 64 \text{ b} \\ &= 2 \times 8 \text{ B} \\ &= 16 \text{ B} \\ &= 2^4 \text{ B} \\[2em] \text{\# of lines} &= \frac{\text{Data Size}}{\text{Block Size}} \\[1em] &= \frac{2^{17} \text{ B}}{2^4 \text{ B}} \\[1em] &= 2^{13} \text{ lines} \implies 13 \text{ bits for line \#} \end{aligned}$$ $$\text{Tag} = 64 - (13 + 1 + 3) = 47 \text{ bits}$$

Address Structure:

$$\underset{47\ b}{\boxed{\phantom{000}\text{Tag}\phantom{000}}} \underset{13\ b}{\boxed{\phantom{0}\text{line \#}\phantom{0}}} \underset{1\ b}{\boxed{\phantom{0}\text{word \#}\phantom{0}}} \underset{3\ b}{\boxed{\phantom{0}\text{byte \#}\phantom{0}}}$$

Each line is $1 + 47 + 128 = 176$ bits.

Total cache size:

$$\begin{aligned} 2^{13} \text{ lines} \ \times \ 176 \text{ bits/line} \ &= 176 \cdot 2^{13} \text{ b} \\ & = 176 \cdot 2^{10} \text{ B} \\ & = 176 \cdot 1 \text{ KB} \\ & = 176 \text{ KB} \end{aligned}$$

Cache Mapping Problems

Problem 1

Given the following block access sequence:

$$1, 2, 4, 6, 1, 2, 4, 2, 4, 3, 5$$

Find the number of misses with (assume LRU is used as the replacement policy):

• fully associative mapping, consisting of 4 one-word blocks, given the following sequence of block addresses
• Direct Mapping, consisting of 4 one-word blocks
• 2-way set associative mapping, consisting of 4 one-word blocks

Solution: Fully Associative Mapping

$$\begin{array}{ccccccccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} \\ 1 & 2 & 4 & 6 & 1 & 2 & 4 & 2 & 4 & 3 & 5 \end{array} \;\longrightarrow\; \textbf{6 misses}$$

Solution: Direct Mapping

Each block maps to line: $\quad (\text{block\#}) \bmod 4$.

$$\begin{array}{ccccccccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} \\ 1 & 2 & 4 & 6 & 1 & 2 & 4 & 2 & 4 & 3 & 5 \end{array} \;\longrightarrow\; \textbf{7 misses}$$

Solution: 2-way set associative mapping

2-way set associative mapping $\implies$ 2 lines per set

Given: 4 lines and 2-way $\implies$ $4/2$ $\implies$ 2 sets: $\ S_0$ and $S_1$

block $\#$ maps to set: $\ (\text{block\#}) \bmod 2$;  LRU within each set.

$$\begin{array}{ccccccccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} \\ 1 & 2 & 4 & 6 & 1 & 2 & 4 & 2 & 4 & 3 & 5 \end{array} \;\longrightarrow\; \textbf{8 misses}$$

Problem 2

Given the following block access sequence:

$$2, 3, 5, 7, 1, 4, 6, 9, 2, 3, 5, 3, 5, 4, 6, 8, 0, 2, 9, 7$$

Find the number of misses with (assume LRU is used as the replacement policy):

• fully associative mapping, consisting of 8 one-word blocks, given the following sequence of block addresses
• Direct Mapping, consisting of 8 one-word blocks
• 2-way set associative mapping, consisting of 8 one-word blocks

Solution: Fully Associative Mapping

$$\begin{array}{cccccccccccccccccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} \\ 2 & 3 & 5 & 7 & 1 & 4 & 6 & 9 & 2 & 3 & 5 & 3 & 5 & 4 & 6 & 8 & 0 & 2 & 9 & 7 \end{array} \;\longrightarrow\; \textbf{11 misses}$$

Solution: Direct Mapping

Each block maps to line: $\quad (\text{block\#}) \bmod 8$.

$$\begin{array}{cccccccccccccccccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} \\ 2 & 3 & 5 & 7 & 1 & 4 & 6 & 9 & 2 & 3 & 5 & 3 & 5 & 4 & 6 & 8 & 0 & 2 & 9 & 7 \end{array} \;\longrightarrow\; \textbf{10 misses}$$

Solution: 2-way set associative mapping

2-way set associative mapping $\implies$ 2 lines per set

Given: 8 lines and 2-way $\implies$ $8/2$ $\implies$ 4 sets: $\ S_0, S_1, S_2, S_3$

block $\#$ maps to set: $\ (\text{block\#}) \bmod 4$;  LRU within each set.

$$\begin{array}{cccccccccccccccccccc} \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{red}{\times} & \color{red}{\times} & \color{blue}{\checkmark} & \color{blue}{\checkmark} & \color{blue}{\checkmark} \\ 2 & 3 & 5 & 7 & 1 & 4 & 6 & 9 & 2 & 3 & 5 & 3 & 5 & 4 & 6 & 8 & 0 & 2 & 9 & 7 \end{array} \;\longrightarrow\; \textbf{11 misses}$$

Cache Performance Problems

Problem 1

Assume that main memory accesses take 70 ns and that memory accesses are 36% of all instructions. The following table shows data for the L1 cache attached to processor P1.

Processor	L1 Miss Rate	L1 Hit Time
P1	8.0%	0.66 ns

• Assume that the L1 hit time determines the cycle time for the processor. What is the clock rate?

  Solution

  $$\text{Clock rate} = \frac{1}{0.66\text{ ns}} \approx 1.52\text{ GHz}$$

• What is the Average Memory Access Time for the processor (in ns)?

  Solution

  $$\text{AMAT} = 0.66\text{ ns} + 0.08 \times 70\text{ ns} = 6.26\text{ ns}$$

• Use the AMAT from above to find the average number of cycles for a memory access.

  Solution

  $$\frac{6.26\text{ ns}}{0.66\text{ ns}} \approx 9.48\text{ cycles}$$

• Assuming a base CPI of 1.0 without any memory stalls (for the rest of the instruction types in the program), what is the total average CPI?

  Solution

  $$\text{Average CPI} = 0.64 \times 1 + 0.36 \times 9.48 = 4.05$$

• We will consider the addition of an L2 cache; on a miss, P1 will now first check L2 cache, and only if that is a miss, will then need a main memory access. The L2 miss rate is 50%, and L2 hit time is 5.62ns. What is the AMAT and average CPI with the addition of this L2 cache?

  Solution

  $$\begin{aligned} \text{AMAT} &= \text{L1 Hit Time} + \text{L1 Miss Rate} \times (\text{L2 Hit Time} + \text{L2 Miss Rate} \times \text{Main Memory Access Time}) \\ &= 0.66\text{ ns} + 0.08 \times (5.62\text{ ns} + 0.50 \times 70\text{ ns}) \\ &= 0.66\text{ ns} + 0.08 \times 40.62\text{ ns} \\ &= 3.91\text{ ns} \end{aligned}$$ $$\frac{3.91\text{ ns}}{0.66\text{ ns}} \approx 5.92\text{ cycles}$$ $$\text{Average CPI} = 0.64 \times 1 + 0.36 \times 5.92 = 2.77$$

  CPI improved from 4.05 to 2.77 with the L2 cache added.