intro-to-cache-placement

docx

School

University of British Columbia *

*We aren’t endorsed by this school

Course

2216

Subject

Electrical Engineering

Date

Jan 9, 2024

Type

docx

Pages

Uploaded by SuperHumanGerbilMaster998

Lesson 9 Show the microcode to execute ADD R5, R5, R5, R5, R5 4. R5out, Yin, ADD, Zin // Z now has R5+R5 5. Zout, Yin, ADD, Zin // Z now has R5+R5 + R5+R5 6. Zout, R5in, END. Show the microcode to execute ADD R1, R2, ((R3)) Today: 1

Main focus for today: Addressing: cpu, main memory, and cache These next two lessons deal with addresses, cache, memory, words, sets, lines, blocks, bits, bytes Every memory cell has an address Each cell is the same size e.g. one Byte in each cell A word is (today) usually 8 Bytes = 64 bits b means “bits” B means “Bytes” For us, I will assume that each cell contains one word Consider this example: A 32-bit main memory address, whose cells store 1 Byte each. QUESTION: How much total memory is there? ANSWER: 2^32 cells => 2^32 Bytes => 4GB question: there are 500,000 people there are 5 people per house how many digits are needed to address the houses? answer: 500,000 people divided by 5 people/house = 100,000 houses log10(100,000) = 5 digits from 00000 to 99999 QUESTION: We have 1GB total memory 4 Bytes in each cell How many bits are in the address? ANSWER: 2^30 B/mm divided by 2^2 B/cell = 2^28 cells/mm => 2^28 addresses/mm We need 28 bits in the address: from 0 to (2^28)-1 Log2(2^28) = 28 Definition: logarithm: exponent log 2 (32) = 5 2^5 = 32 2

mandatory steps for full marks: - use powers of 2 - always show your work - always include units including in your work QUESTION: How many bytes are in each cell if there is 256MB total memory and the address is 24 bits? ANSWER: 2^28 B/mm divided by 2^24 cells/mm = 2^4 B/cell QUESTION: How many cells are there if there is 2MB total memory, and 16 bits per cell? ANSWER: 2^21 B/mm divided by 2^1 B/cell = 2^20 cells/mm QUESTION: How many bits are in a mm address if there are 2^16 cells and 8 Bytes per cell? ANSWER: 16 bits allows us to address 2^16 cells Analogy: how many digits are in a house address if there are 10^4 houses? 4: 0000 to 9999. Log10(10^4) = 4 QUESTION: How many bits are in a mm address if there are 2^3 cells and 8 Bytes per cell? ANSWER: 3 3

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

1 byte cell 0: 00000 1 byte cell 1: 00001 1 byte cell 2: 00010 1 byte cell 3: 00011 1 byte cell 4: 00100 1 byte cell 5: 00101 1 byte cell 6: 00110 1 byte cell 7: 00111 1 byte cell 8: 01000 1 byte cell 9: 01001 1 byte cell 10: 01010 1 byte cell 11: 01011 1 byte cell 12: 01100 1 byte cell 13: 01101 1 byte cell 14: 01110 1 byte cell 15: 01111 1 byte cell 16: 10000 1 byte cell 17: 10001 1 byte cell 18: 10010 1 byte cell 19: 10011 1 byte cell 20: 10100 1 byte cell 21: 10101 1 byte cell 22: 10110 1 byte cell 23: 10111 1 byte cell 24: 11000 1 byte cell 25: 11001 1 byte cell 26: 11010 1 byte cell 27: 11011 1 byte cell 28: 11100 1 byte cell 29: 11101 1 byte cell 30: 11110 1 byte cell 31: 11111 5

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

QUESTION: Which cells are in MM block 2000? ANSWER: 2000*8 = 16000 plus the next 7: 16000-16007 QUESTION: Which line of cache does MM block 521 go into? ANSWER: 521 % 4 = 1; line 1 QUESTION: Which line of cache does MM cell 4206 go into? ANSWER: a) figure out its block; b) figure out that block's line a) floor(4206 / 8) = block 525 remainder 6; BLOCK 525 b) block 525 goes into line 525%4 = 1; LINE ONE is the answer NEW QUESTION: if we have a direct-mapped cache with 8 words per line, and 32 lines total: - A) Which line does MM block 1674 go into? - B) which line does MM cell 1674 go into? ANSWER: - A) block 1674 gets mapped directly into line 1674%32 = 10; line 10 (the eleventh line) - B) figure out cell 1674’s block, then its line: 1674 / 8 = 209 remainder 2; the third word in block 209 Block 209 gets mapped directly into line 209%32 = 17; line 17 convert 587 in base ten, to base two: 587 = 512 + 64 + 8 + 2 + 1 = 10010 01 011 tag line word -------------------------- convert 4206 in base ten, to base two: 4206 = 1000001101110 the final bits indicate the word; here it's 3 bits the next middle bits indicate the line; here it's 2 bits 10000011 01 110 tag line word ----------------------- convert 33 in base ten, to base two: 1 00 001 T L W ...main-memory cell 33 should be word 1 in line 0 in the cache ------------------------------ if the tag were 0: 0 00 001 T L W cell 00001 in base two, which is cell #1 in base ten ------------ if the tag were 2: 10 00 001 T L W 8

cell 10 00 001 in base two, which is cell #65 in base ten ------------ if the tag were 3: 11 00 001 T L W cell 11 00 001 in base two, which is cell #97 in base ten 9

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Cache Cache contains lines of many words (some power-of-two number of words) (to make use of the principle of spatial locality) When word n gets transferred from mm to cache, its neighbors come too e.g. A line holds 64 words (this is an example only) Assume the CPU requests word 99 The cache will load as follows: Memory block 0 holds words 0 – 63 Memory block 1 holds words 64 – 127 therefore along with 99, we get 64-98 and 100-127 also QUESTION: which words go along if the CPU requested word 300, and which memory block is word 300 in? ANSWER: Memory block 2 holds words 128 – 191 Memory block 3 holds words 192 – 255 Memory block 4 holds words 256 – 319 New example: QUESTION: A line holds 256 words. Assume the CPU requests word 4000. Which block is it in? And which other words are also in that block? ANSWER: 4000 / 256 = 15 remainder 160 Therefore word 4000 is in block 15 The first in block 15 is word (15 * 256 = ) 3840, plus the next 255 words: 3840 – 4095 Memory block 0 holds words 0 – 255 Memory block 1 holds words 256 – 511 … 10

QUESTIONS about this cache example (above): Cell 19: 10011 The virtual address is made of fields for the TAG, the LINE, and the WORD (in that order). The right-most one bit indicates the word position in cache. The middle two bits indicate the line in cache. The tag indicates which of the four competing words is in the cache right now: the first one, the second one, the third one, or the fourth one. All four are directly mapped to the same location in the cache. Only 1 goes there at a time, and the tag tells which one is in there currently. 12

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

In that last example, we had: 32 cells of memory. 1 word per cell. We had 4 lines of cache, 2 words per line. It was a direct-mapped cache. How many bits are in the main memory address? Log2(32) = 5 bits (see the diagram above) The CPU says address 10011 is “cell 19”. But the cache sees this as a virtual address, as follows: The first two bits are the tag, indicating which of the four words that COULD be in that cache word location, IS there now. The next two bits indicate which LINE cell 19 goes into. The final bit indicates which word position it’s in: the first or second (0 or 1). NEW QUESTION: Consider the same memory with 32 words (cells). Consider a cache with 2 lines and 8 words per line. What is the makeup of the virtual address; i.e. how many bits indicate the TAG, the LINE, and the WORD? ANSWER: 1 bit 1 bit 3 bits TAG LINE WORD Consider cell 19: 1 0 011 Tag is 1, line is 0, word is 011 13

New question: Memory: 1024 cells, 1 word per cell Cache: direct mapped, 32 lines, 8 words per line How long is a main-memory address, and how many bits make up the tag, line, and word? ANSWER: 10-bit mm address log2(1024) = 10 10 – 5 – 3 = 2 5 3 TAG LINE WORD Entire address: TAG + LINE + WORD must = 10 bits How much competition is there for a cache space? Memory has 1024 words, cache has 2^32 lines * 2^3 words/line = 2^8 words Memory therefore has 4 times as many words. It will take 2 bits to identify which of the four words mapped to a cache spot, IS in that spot now. 14