A cache memory has a line size of eight 64-bit words and a capacity of 4K words

Question

A cache memory has a line size of eight 64-bit words and a capacity of 4K words. The main memory size that is cacheable is 1024 Mbits. Assuming that the addressing is done at the byte level, show the format of main memory addresses using 8-way set-associative mapping.

So here's what I have understood from this question so far: Line size = 8 words = 2^3, which means that w = 3; Cache size = 4K = (2^3 + 2^6)/(2^3) = 2^6 lines; 8-way set associative means that each cache contains (2^6)/(2^3) = 2^3 Main memory size = 1024 Mbits = 128 M

I am stuck as to how to proceed next. Any help would be greatly appreciated.

Answer 1

First, I'm going to do everything in bytes.

A 64-bit word means 8 bytes.

Line size: 8 words in a line, means 8 x 8 bytes = 64 bytes in a line = 2⁶ bytes.

Cache size: 4k words, meaning 4096 x 8 bytes = 32k total bytes.

Cache indexes: 32k total bytes / 8 way set associative = 2¹⁵ / 2³ = 2¹² index positions in the cache line-set array.

Main memory: 1024 MBits = 1024 * 2²⁰ = 2³⁰ and, 2³⁰ / 8 bits-per-byte = 2²⁷ bytes (or 128 Mbytes).

So, that means there are 27 addressing bits in total for the cacheable memory.  Those 27 bits break down into 3 parts:

+--------------------+
| tag | index | rest |
+--------------------+

The "index", which is 12-bits in width, is used to lookup into the cache array to identify one cache line set.

The tag bits are used to isolate one of the lines in the set of 8 (or determine a miss).

The "rest" bits determine which bytes in the 64-byte line are the particular bytes of interest for a given memory reference instruction.  More precisely, the rest bits indicate the first byte of interest, and the memory reference instruction encodes the number of bytes of interest (e.g. 1, 2, 4, 8).

Since the line size is 64-bytes, then the "rest" is 6 bits; these 6 bits are used after the cache lookup identifies the line (on hit).

That means that the tag, which makes up the remainder, must be 27-12-6 = 9 bits wide.  A tag of this size is stored in the each cache line in the set for comparison with the tag in the address bits.

So, the 27 bits of address break down into 9 tag bits, 12 index bits, and 6 "rest" bits.  The cache line lookup operation consumes the 9 tag bits and 12 index bits, and, after the line is identified, the rest bits (and instruction-specified length) are used to extract the bytes of interest.