Question

Below is a list of 32-bit memory address references, given as word addresses.

3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253 5.2.1

a) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with 16 one-word blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

b) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with two-word blocks and a total size of 8 blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

Answer 1

This problem requires converting decimal memory addresses to binary, identifying the tag and index for a direct-mapped cache, and determining hits and misses for each reference.

Step-by-step explanation:

Cache memory operations and management are central to the performance of computer architecture. This problem involves understanding how the direct-mapped cache works, converting decimal addresses into binary, and determining cache hits and misses.

Part a)

In a direct-mapped cache with 16 one-word blocks, the memory address is split into tag and index. The index needs 4 bits (since there are 16 blocks, and 2^4 = 16) and the remaining higher order bits are the tag. A cache hit occurs if the current address's tag matches an address's tag already stored in the cache with the same index. Initially, the cache is empty, so the first reference will always be a miss.

For example, the word address 3 in binary is 00000000000000000000000000000011. With the least significant 4 bits as the index (0011), the tag would be the remaining bits (all zeros here). As the cache starts empty, this would be a miss. As references are processed, some will be hits if their tags and indices match any previously stored addresses.

Part b)

For a direct-mapped cache with two-word blocks and a total of 8 blocks, we have to take into consideration that each block now stores two words. The index field will now have 3 bits (since 2^3 = 8). Since the block size is two words, the lowest order bit of the address is used to determine the word within a block, and this bit is not part of the index.

As a result, the memory addresses will have their last bit ignored for the index and tag calculation (e.g., word address 3 becomes binary 11, and after dropping the least significant bit for the block offset, we are left with an index of 1 (binary 01) and the rest as the tag). Starting with an empty cache, each address will result in a miss initially and then we'll determine hits or misses based on whether the cache already has the block with the same tag and index.

Answer 2

For a direct mapped cache the general rule is: first figure out the bits of the offset (the right-most bits of the address), then figure out the bits of the index (the next-to right-most address bits), and then the tag is everything left over (on the left side).

One way to think of a direct mapped cache is as a table with rows and columns. The index tells you what row to look at, then you compare the tag for that row, and if it matches, the offsettells you which column to use. (Note that the order you use the parts: index/tag/offset, is different than the order in which you figure out which bits are which: offset/index/tag.)

So in part (a) The block size is 1 word, so you need 0 offset bits (because 20=120=1). You have 16 blocks, so you need 4 index bits to give 16 different indices (because 24=1624=16). That leaves you with the remaining 28 bits for the tag. You seem to have gotten this mostly right (except for the rows for "180" and "43" where you seem to have missed a few bits, and the row for "181" where you interchanged some bits when converting to binary, I think). You are correct that everything is a miss.

For part (b) The block size is 2 words, so you need 1 offset bit (because 21=221=2). You have 8 blocks, so you need 3 index bits to give 8 different row indices (because 23=823=8). That leaves you with the remaining 28 bits for the tag. Again you got it mostly right except for the rows for "180" and "43" and "181". (Which then will change some of the hits and misses.)