2021/22 Semester A
CS 2115 Computer Organization
City University of Hong Kong
HOMEWORK 4
Instruction:
• The submission deadline is 2021 Nov. 30 23:59. Late submissions will not be accepted.
• The solutions should be submitted to Canvas. Email submissions (or other form of
submissions) will not be submitted.
• Your submission should contain 1 “*.circ” file which includes all the required circuits, and
two memory image files (for the address memory and data memory respectively). The files
should be named as “HW4-SID.circ”, “HW4-SID-address-mem” (address memory image)
and “HW4-SID-data-mem” (data memory image), where SID is replaced by your own SID.
Question 1 (5 points):
Build a set-associative cache in Logisim. The memory is word addressable, i.e., each memory block
stores one word (32 bits). The cache has 2 sets, and each set has 4 ways. Each cache line stores one
word (32 bits). The LRU replacement policy is used within each set. We assume the address width is
16 bits.
We ignore the cache penalty, i.e., in case of a cache miss, the data can be fetched from the memory
and installed into the cache within the same cycle.
We assume the data memory cannot be asynchronously modified by others, so valid bits are not
needed in the cache.
The circuit should contain the following components:
• A cache, which has the following input and outputs pints
o Input address: the memory block address sent into the cache
o Input data: in case of a cache miss, the data to be loaded from the data memory to
cache
o Output address: in case of a cache miss, the address to be sent to the data memory
o Output data: the data read from the cache
o Miss indicator: if the access is a cache miss, this indicator outputs 1, otherwise this
indicator outputs 0.
• An address memory, which stores the addresses of the memory blocks to be accessed one
by one. In a real processor, the address of the memory blocks to be accessed is generated by
the processor, but in this exercise, you are not required to build the processors. Instead, you
can store the addresses of the memory blocks to be accessed in this address memory. You
should also design auxiliary circuits so that the addresses stored in the address memory can
be sent to the cache one after one (hint: using a register to build something similar to a
program counter in processors).
• A data memory, which stores the data to be accessed. The data memory is enabled (i.e., set
1 to the “sel” pin) only if a cache miss occurs.
The addresses of the memory content to be accessed are stored in the address memory starting
from address 0x00.
2021/22 Semester A
CS 2115 Computer Organization
City University of Hong Kong
You should store the following data in the data memory:
address data
0x10 0x10
0x11 0x11
0x12 0x12
0x13 0x13
0x14 0x14
0x15 0x15
0x16 0x16
0x17 0x17
0x18 0x18
0x19 0x19
0x1a 0x1a
0x1b 0x1b
0x1c 0x1c
0x1d 0x1d
0x1e 0x1e
0x1f 0x1f
… …
You should store the following data in the address memory:
address data
0x00 0x10
0x01 0x11
0x02 0x12
0x03 0x18
0x04 0x1c
0x05 0x1b
0x06 0x1a
0x07 0x11
0x08 0x15
0x09 0x1b
0x0a 0x13
0x0b 0x1d
0x0c 0x1c
0x0d 0x11
0x0e 0x12
0x0f 0x10
… …
You can refer to Tutorial 11 to see the example of a direct-mapped cache. The requirement of that
example is similar to this question, but this question asks you to build a 4-way associative cache
instead of a direct-mapped cache. The following gives an example of the structure of circuits.
2021/22 Semester A
CS 2115 Computer Organization
City University of Hong Kong