The following problems contain basic information about the overall size of a system's main memory and the layout of its cache, which has a direct cache architecture. The cache consists of a set of cache lines, each line has a valid flag, a dirty flag, a number of bits for storing the tag, and a number of data bytes needed to hold the line of memory.
Each problem states the total memory being addressed, the number of lines in the cache, and the size of the lines in bytes in the cache.
Using this information, you will determine how each of two memory addresses map into the cache. One of these numbers is specified in the problem and the other number is the numeric portion of your Z-ID.
|
For each problem: a. Give the number of bits needed to address all main memory of specified size. b. Give the number of bits needed to select the correct line in the cache. c. Give the number of bits needed to select the correct byte in a cache line. d. Give the size in bytes of a segment ( number of lines in cache * number of bytes/line ). e. Give the number of bits needed to identify the segment location (tag id) of the address being accessed in memory. This is the difference between the total number bits to address all of memory and the number of bits to address all of the bytes in a segment. f. Give the amount of additional memory needed in the cache to handle the tags, valid bits, and dirty bits. Fractional results are OK. Remember, we use 8 bit units because they are relatively easy to work with. A computer doesn't care and can use odd register sizes if it is more efficient. The general formula will be :
number of cache lines * ( number of tag bits/line + number of valid bits/line + number of dirty bits/line ) / 8 bits/byte.
For address specified in the problem, express in both both binary and hex : You may use any method to convert your Z-ID to binary. g. Give the byte id with-in the cache line of the memory element specified. h. Give the line id of the memory element specified. i. Give the tag of the memory element specified.
|
a. The main memory size is 16 X 1 MiB or 2^4 * 2^20 = 2^24 bit address range. 24 bits needed to address all of memory
b. The number of lines in cache = 256 or 2^8. 8 bits to address any line in cache.
c. The number of bytes/line in cache = 256 or 2^8. 8 bits to any byte on the cache line of interest.
d. Since the lowest 8 bits of the memory address are used for the byte index, the next 8 bits are used for the line index, we need 16 bits to address all of the cache. The cache size is 65536 bytes.
e. If the total memory address is 2^24 or 24 bits wide and the byte index is 256 or 2^8 and the line index is 256 or 2^8, then the tag width can be found by subtracting the number of bits needed for the line and byte indexs. 24 - 16 = 8 bits needed for the segment id or tag.
f. The additional cache memory for tag and flag bits :
256 lines * ( 1 bit(valid) + 1 bit(dirty) + 8 bits(tag) ) /8 bits/byte
256 * 10 = 2560 bits or 320 bytes.
Our value in binary was 0000 1101 1110 1101 0110 0011b.
g. Byte index of 0110 0011b or 63h.
h. Line id was 1110 1101b or EDh.
i. Tag of 0000 1101b or 0Dh
Note that in some cases, the split between bytes, lines, and segments will
not always line up on the hexadecimal digits representing the main memory
address.
Example: memory 312739 = 100 1100 0101 1010 0011 or 04C5A3h
32 MiB memory, 4 byte by 32 line cache.
a. The main memory size is 2^25 or 25 bit address range.
b. 32 line cache or 2^5. 5 bits to address lines in cache.
c. 4 bytes/line or 2^2. 2 bits to address any byte in the line.
d. 4 bytes/line * 32 lines = 2^2 * 2^5 = 2^7 or 128 bytes in a cache segment.
e. 32MB bytes / 128 bytes/segment = 2^25 / 2^7 = 2^18 segments. We need 18 bits for the segment or tag id.
f. 32 lines * ( 1 bit(valid) + 1 bit(dirty) + 18 bits(tag))/ 8 bits/byte.
32 * 20 / 8 = 80 bytes for tags and flags.
The binary of the address is 0 0000 0100 1100 0101 1010 00 11. Note the zero padding on the left to give a 25 bit value (full address range).
g. The byte id is the 2 bit id 11h or 3h
h. The line id is the 5 bit id 0 1000 or 08h
i. And the tag is the 18 bit id 00 0000 1001 1000 1011b or 0098Bh
Convert you Z-ID to binary. You need to do this only once. You may use
any method you desire to convert from decimal to binary.
For each of the following problems, answer the 9 questions listed above. Do both the provided address and the address represented by your Z-ID.
All specified memory addresses are in Hexadecimal.
1. 16 MiB memory, 32 byte by 256 line cache. Accessing memory cells F6766F (g,h,i)
2. 256 MiB memory, 8 byte by 64 line cache. Accessing memory cells 67373A (g,h,i)
3. 512 MiB memory, 4 byte by 2048 line cache. Accessing memory cells A1A163E (g,h,i)
4. 32 MiB memory, 16 byte by 128 line cache. Accessing memory cells 6D2D39 (g,h,i)
5. 1 GiB memory, 32 byte by 1024 line cache. Accessing memory cells 757575 (g,h,i)
****************************
Key