Part III: Set Associative Mapped Cache

Execute the above program by setting the following Parameters:

Number of sets $($Set Blocks$)$: $2$ way

Cache Type: Set Associative

Replacement: LRU$/$FIFO$/$Random

a$)$ Fill up the following table for three different replacement algorithms and state which replacement algorithm is better and why?

$\backslash$table$[[$Replacement Algorithm: Random$],[$Block Size,Cache size,Miss,Hit,Hit ratio$],[2,,,,],[2,8,,,],[2,16,,,],[2,32,,,],[2,64,,,],[$Replacement Algorithm: FIFO$],[$Block Size,Cache size,Miss,Hit,Hit ratio$],[2,,,,],[2,8,,,],[2,16,,,],[2,32,,,],[2,64,,,],[$Replacement Algorithm: LRU$],[$Block Size,Cache size,Miss,Hit,Hit ratio$],[2,4,,,],[2,8,,,],[2,16,,,],[2,32,,,],[2,64,,,]]$

b$)$ Plot the graph of Cache Hit Ratio Vs Cache size with respect to different replacement algorithms. Comment on the graph that is obtained.

c$)$ Fill in the following table and analyse the behaviour of Set Associative Cache. Which one is better and why?

$\backslash$table$[[$Replacement Algorithm: LRU$],[$Block Size,,Set Blocks,Miss,Hit,Hit ratio$],[$Cache size,,,,$],[2,64,2-$ Way,,,$],[2,64,4-$ Way,,,$],[2,64,8-$ Way,,,$]]$r

Code to be used:

The following code written in STL Language:

program Thirteen

var a array$(5)$ byte

var b array$(5)$ byte

$a(0)=4$

$a(1)=1$

$a(2)=3$

$a(3)=5$

$a(4)=2$

var len byte

var temp byte

var $11$ byte

var $12$ byte

var $x1$ byte

var $x2$ byte

var j byte

var $j1$ byte

vark byte

var i byte

len $=4$

$11=$ len $-1$

for $k=0$ to len

write$($a$($k$),"")$

next

writeln$("\text{'}")$

writeln$("$Bubble Sort Starts"$)$

for $i=0$ to $11$

$12=$ len $-i-1$

for $j=0$ to $12$

$j1=j+1$

$x1=a(j)$

$x2=a(j1)$

if $x1>x2$ then

temp $=a(j1)$

$a(j1)=a(j)$

$a(j)=$ temp

end if

next

for $k=0$ to len

write$($a$($k$),"")$

next

writeln$("")$

next

writeln$("$Bubble Sort Ends"$)$

end

General procedure to convert the given STL program into ALP:

Open CPU OS Simulator. Go to advanced tab and press compiler button

Copy the above program in Program Source window

Open Compile tab and press compile button

In Assembly Code, enter start address and press Load in Memory button

Now the assembly language program is available in the CPU simulator.

Set speed of execution to FAST.

Open I$/$O console

To run the program, press the RUN button.

General Procedure to use Cache set up in CPU$-$OS simulator

After compiling and loading the assembly language code in the CPU simulator, press the "CachePipeline" tab and select cache type as "Data". Press the "SHOW CACHE" button.

In the newly opened cache window, choose appropriate cache Type, cache size, set blocks, replacement algorithm and write policy.