1. Nov 26, 2012

### twoski

1. The problem statement, all variables and given/known data

Consider a cache memory system having the following characteristics :
- 512 Mbytes of main memory.
- Word size of 4 bytes.
- Cache size of 512 Kbytes.
- Line size of 8 bytes.

(a) Determine the address formats for (i) direct, (ii) associative, and (iii) two-way set associative mappings.

(b) For each of the following situations, explain whether programmed I/O, interrupt driven I/O, or DMA should be used.
(i) Transfer of a large block of data.
(ii) Transfer of a few bytes.
(iii) Transfer of a few bytes within a given time limit.

3. The attempt at a solution

The example our professor gave us doesn't explain anything so i'm not sure how to proceed.

Here's his example:

Cache size: 128 words
Line size: 8 words
Main memory: 16 kbytes
Number of memory blocks: 2k

Therefore, the Direct Address Format is 7 tag bits, 4 line bits and 3 word bits.

I have no clue how that conclusion was reached. How is it decided that there are 14 bits in an address? And how are the number of tag bits, etc. decided?

2. Nov 26, 2012

### Staff: Mentor

The cache is 128 (= 27) words.
A line is 8 (= 23) words, so how many lines are there?

To identify a particular word in memory, you indicate which line it's on, and which word within a line you're interested in.

3. Nov 26, 2012

### twoski

So then for direct addressing, i'd have 9 tag bits (since 512 = 2^9), 3 word bits and 6 line bits, right?

And for associative, there's 15 tag bits and 3 word bits.

How do i determine the set size/number of sets for the third question about set associative mapping?

Last edited: Nov 26, 2012
4. Nov 27, 2012

### Staff: Mentor

I'm not sure what the term "tag bits" means.

I think that the meaning of the first sentence above is that the tag bits are made up of 4 line bits and 3 word bits. I don't think this means there are 7 tag bits + 4 line bits and 3 word bits.

The tag bits term should be defined in your book, together with definitions of the addressing types. How are these terms defined? Let's start from these definitions.

5. Nov 27, 2012

### twoski

This is just taken from an example written on the board, for Associative Mapping my professor wrote that there are 11 tag bits and 3 word bits (assuming we're using the specs from his example). There are 11 tag bits because there are 2^11 = 2048 memory blocks.

I don't think tag bits are made up of the word/line bits because in his example, for Set Associative Mapping there are 8 tag bits, 3 line bits and 3 word bits.

6. Nov 27, 2012

### Staff: Mentor

How big are the memory blocks? Having 3 word bits suggests that each memory block is 8 words.
So what is the definition of "tag bits"?

7. Nov 27, 2012

### rcgldr

2^14 = 16384, so 14 address bits are needed to access 16 kbytes of memory. How the cache is implemented doesn't matter in this case, since there's no virtual memory or swap file to emulate a larger memory size.

Looking at the later example, line size is 8 bytes, not 8 words. For a line size of 8 bytes, the lower 3 bits of an address are used to index into a block in the cache or physical memory.

The number of tag bits is the total number of address bits minus the number of line bits and minus the number of index bits. The cache contains one tag for every line (block) in the cache, and the tag is compared against the upper bits of an address to see if that line in the cache contains the cached data corresponding to that address. Normally, there is also one "valid" bit per line to indicate the line is holding cached data, and one "dirty" bit to indicate that a write was done to a line but not yet written to main memory.

I changed the example to show "bytes" instead of "words. The 3 "byte" bits are the lower 3 bits of an address and normally called "index" bits. The number of line bits depends on how the cache is implemented, which in this case is a "direct mapped cache", where line bits are directly used as a block index for the cache. Since the cache has 16 blocks, then 4 line bits are required. Since line bits in a logical address are not translated, each block in the cache can only hold 1 of 128 potential memory blocks (8 bytes each) where the 4 bits in the logical address are the same as the 4 bits of the physical address. For example, block 0 of the cache can only hold data from any of the 128 physical memory blocks addressed as XXXXXXX0000XXX and block 5 of the cache can only hold data from any of the 128 physical memory blocks addressed as XXXXXXX0101XXX . For each memory access, the line bits are used to select (index) which block (line) of cache memory could potentially hold cached data, and then a single 7 bit compare with the upper address bits (the tag bits) plus a "valid" bit check would be done to determine if that cache block holds the cached data.

- - -

For a fully associative cache, there are zero line bits, and the number of tag bits is 14 - 3 = 11 bits. Each block of the cache will require an 11 bit memory used to store the upper 11 bits of an address of a cached block of memory plus a "valid" bit. A 12 bit (the 12th bit is the "valid" bit) by 16 entry content addressable memory could be used to search for a valid address match in one cycle. For each memory access, the content addressable memory does 16 compares in parallel, and if there is a match, it returns the index of the match, which would correspond to which 8 byte block in the cache that holds the cached data. With a fully associative cache, any line in the cache could hold any of the 2k memory blocks, and this would provide better performance than the example cache.

wiki article:

http://en.wikipedia.org/wiki/CPU_cache

Last edited: Nov 28, 2012