Lab Assignment 3 CSci 4203 Fall 2021
CSci 4203 Fall 2021 Lab Assignment 3 :
You are provided with a set associative cache implemented in SystemVerilog from the
companion website for the textbook
(http://booksite.elsevier.com/9780124077263/appendices.php) and need to solve the problems
described below. SystemVerilog introduces C-like data-types and data-structures which are
useful for high-level modelling of the hardware. Several useful tutorials for SystemVerilog can be
found at http://www.asic-world.com/systemverilog which can help you get into it fairly quickly.
Reading :
5.12.1 – 5.12.10 from the online companion website. More specifically, figure 5.12.3 is very
useful for understanding a direct mapped cache organization that the given code was based on.
Background :
The given code implements a cache and memory system.
There are four key components in the given cache and memory system shown in the above
figure. The first two parts are the Tag and Data Arrays which contain the tags and their
corresponding cache lines. The second part is the main memory, which contains an array of
data values. The third part is the Cache FSM, which is used to communicate between these
components and the CPU. Signals used include tag_req, tag_write and tag_read. tag_req sends
metadata such as line number, set index, write_enable, for lookup into the tag array. tag_write
contains the address to write into the tag array or to read from it, as controlled by tag_req.
tag_read is the response by the tag array to the cache FSM, which includes all tags in the
accessed set. The data_req, data_write and data_read have similar functionality, but in the data
array instead. cpu_req and cpu_res are used to communicate with the CPU. cpu_req contains
an address which the CPU is checking memory for. cpu_res contains the result. Lastly,
http://www.asic-world.com/systemverilog
mem_req and mem_data are used to communicate with the main memory. mem_req contains
address, data and other information, such as whether it is a read or write. mem_data is the
memory response, which is a 16 byte value, the same size as a cache block.
For an N-way associative cache, the data and tag arrays hold 1024xN elements, since there are
now 1024 sets and each set has N cache lines. In the above example there are N=2 cache
ways only. Whenever there is a tag hit, then the corresponding tagarray elements are returned
to the FSM. The size of each element in the tag array is the size of a tag, which is 18 bits. The
data array is organized in a similar manner as the tag arrays. However, the data array access
returns a much larger value of 16*N bytes size to the FSM.
The cache FSM state transitions are shown in the above figure. The FSM has four states,
namely, idle, compare_tag, allocate, and write_back.
idle :
The idle state is the default cache state, when there are no in-flight accesses.
compare_tag :
The compare_tag state is reached when a tag comparison needs to check whether the cache
line is present in the cache. If there is a tag hit, then the state returns to idle, and the data is
returned to the CPU. Any replacement information associated with the cache lines in the
relevant set are also updated. If there is a cache miss, then a replacement victim is chosen, and
the state moves to either the allocate state or the writeback state (in case the replacement
victim was dirty).
writeback:
In the writeback state, the FSM waits until the memory acknowledges that it has updated its
contents. Then the FSM issues a request for the missing cache line to memory, and returns to
the allocate state.
allocate:
In the allocate state, the FSM waits until the memory has returned the contents of the missing
cache line, and writes it into the data/tag arrays. Then it transitions to the compare_tag state,
which will now record a cache hit, and return the data to the CPU.
Handout :
For Problem 1, the following sv files are used :
dm_cache_data_1.sv defines the cache data and tag arrays.
dm_cache_fsm_1.sv defines the cache controller, which is modelled as an fsm (finite state
machine). This file also instantiates the cache data and tag arrays.
package_definitions_1.sv contains definitions of parameters, such as set associativity, data
structures corresponding to the signals used by the cache and memory system, replacement
policy counters and other metadata.
testbench_1.sv file instantiates the fsm and main memory, executes test cases and computes
your score.
Similarly, there are also modified copies of these files for Problem 2, which are similar to the
files above, except for changes related to the replacement policy.
Running The TestBenches :
Create a new project, and import only the sv files for the problem you are working on into the
project. Then, run the behavioral simulation. Your score should be printed out in the TCL
console. Below, you may find a screenshot of the result.
The test cases create a wide variety of situations, in order to test how the replacement policy
works.
Problem 1 (50 points) :
Change the replacement policy for the set-associative cache to random replacement policy. This
means that the replacement victim is always chosen in a random manner.
Hint : Use the ‘$random()’ library function which is implemented by Vivado. The $random()
library function will generate a random number. This should be limited to the range [0,
Associativity-1] using the modulo operator (%).
Please fill in the TODO sections mentioned in the code. The main changes required are in the
allocate state of the cache FSM.
Problem 2 (50 points):
Implement an LFU (first in first out) replacement policy by maintaining a counter for each cache
line which is incremented when there is a hit and set to 0 when the line is evicted. When there is
an eviction request, then the cache line with the smallest counter value will be selected for
eviction. If many cache lines have the smallest counter value, then the one with the smallest
index should be selected for eviction.
Please fill in the TODO sections mentioned in the code. The main changes required are in the
allocate and compare_tag states of the cache FSM.
Avoid Combinational Loops :
Sometimes, you may find that your code gets stuck in an infinite loop. This might be due to a
‘Combinational loop’ in your fsm. If two variables in the control logic depend on each other, then
they will keep updating their values forever and the simulation will not proceed.
For example :
always_comb begin
a=b;
b=a;
end
Will be stuck forever in a ‘combinational loop’.
These can be avoided by ensuring the ‘output’ and ‘input’ variables of your combinational block
do not have any common variables.
Handin :
Implement your solution by modifying the given *.sv files.
Do not turn in testbench.sv for any of the problems.
These files should be placed into a folder, Lab3_X500. For example, it will be Lab3_ramkr004
for me. Then compress this folder using the command :
tar -cvzf Lab3_X500.tar.gz Lab3_X500
Grading Scheme :
The solutions will be graded using the testbenches provided to you. In case you lose points due
to incorrect test cases, then partial credit will be assigned on a per-case basis. Please comment
your code and keep it neat and clean. This will be helpful for partial credit.