Prob A Cache Addressing The following problem explores the a

Prob. A: Cache Addressing. The following problem explores the addressing patterns of a cache system, and to do so uses a small cache, by today\'s standards. Another difference here from what we have described in class is that this is a word addressed system, not a byte addressed system. Nevertheless, the activity described is repeated in larger caches. A cache memory machine uses a cache which can store 512 lines of 32 words each. Assume a main memory size of 8,388,608 words.

A.1: Which bits of the word address should specify the line number?

A.2: If a set associative scheme is used, which bits should specify the set number?

A.3: Describe the worst case reference pattern (for maximum cache miss) assuming (i) direct addressing, (ii) set associative with 2 lines per set, (iii) set associative with 4 lines per set, (iv) fully associative cache allocation. How likely are these worst cases?

Solution

1024*8 means that you have:

Address Lines:

Assuming that number of address lines (address bits) is n, how can we find n? If n=1, you can only address 2 locations (0 and 1). If n=2, you can address 2 locations (0, 1, 2, and 3). As you can see, number of addressable locations = n^2.
Given that number of addressable locations = 1024, then 1024=2^n
This means that n=log(1024) to the base 2.
Thus, n=10.

Data Lines:

You have 8 bits for every location, therefore your memory needs a data bus with 8 lines. Every time you read a location (by loading its address on the address bus), the 8 bits that are stored at that location are loaded (by the memory chip) on the 8-line data bus.

Memory size:

As obvious, your memory has 1024*8 bits (8192 bits). Or simply, 1024 bytes :)