Analyzing Cache Memory System Characteristics

[twoski]

Homework Statement

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.

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?

 

[Mark44]

Homework Statement

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.

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

The cache is 128 (= 2⁷) words.
A line is 8 (= 2³) 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.

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?

 

[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?

 

[Mark44]

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

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?

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.

 

[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.

 

[Mark44]

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.

How big are the memory blocks? Having 3 word bits suggests that each memory block is 8 words.

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.

So what is the definition of "tag bits"?

 

[rcgldr]

Main memory: 16 kbytes .. How is it decided that there are 14 bits in an address?

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.

... Line size of 8 bytes ... example ... Line size: 8 words

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.

tag bits

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.

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

therefore, the Direct Address Format is 7 tag bits, 4 line bits and 3 byte bits.

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