CMSC 411 - A. Sussman (from D. O'Leary) 1Computer Systems ArchitectureCMSC 411Unit 5 – Memory HierarchyAlan SussmanOctober 7, 2004CMSC 411 - Alan Sussman 2Administrivia• HW #3 due today– questions• Quiz 2 Tuesday, Oct. 12– on Unit 3, basic pipelining– practice quiz posted, answers posted later today– questions?• Read Chapter 5 – except 5.11-5.15CMSC 411 - Alan Sussman 3Last time• Long instructions– can cause structural hazards, and WAW hazards – why?– detect hazards early, to allow precise exceptions• in ID pipeline stage, and delay EX cycle if problem detected• can delay WB, use history or future file, let OS deal with it, to enable precise exceptions• MIPS R4000 pipeline design– 8 stage pipeline – superpipelining– extra stages come from multi-cycle cache accesses– 2 cycle load delay and 3 cycle branch delay (1 delay slot, 2 cycle stall for taken branches)– complex FP pipeline – 8 stages used in different combinations for different operationsCache MemoryCMSC 411 - Alan Sussman 5Issues to consider• How big should the fastest memory (cache memory) be?• How do we decide what to put in cache memory?• If the cache is full, how do we decide what to remove?• How do we find something in cache?• How do we handle writes?CMSC 411 - Alan Sussman 6First, there is main memory• Jargon:– frame address – which page?– block number – which cache block?– contents – the dataCMSC 411 - A. Sussman (from D. O'Leary) 2CMSC 411 - Alan Sussman 7Then add a cache• Jargon: Each address of a memory location is partitioned into– block address•tag• index– block offsetFig. 5.5CMSC 411 - Alan Sussman 8How does cache memory work?• The following slides discuss:– what cache memory is– three organizations for cache memory• direct mapped.• set associative• fully associative– how the bookkeeping is done• Important note: All addresses shown are in octal. Addresses in the book are usually decimal.CMSC 411 - Alan Sussman 9What is cache memory?Main memory firstMain memory is divided into (cache) blocks.Each block contains many words (16-64 common now).CMSC 411 - Alan Sussman 10Main memoryBlocks are grouped into frames (pages), 3 frames in this picture.CMSC 411 - Alan Sussman 11Main memory (cont.)00010203040506071011121314151617202122Blocks are addressed by their frame number, and their block numberwithin the frame.CMSC 411 - Alan Sussman 12Cache memoryCache has many, MANY fewer blocks than main memory, each witha block number,a memory address,data,a valid bit,a dirty bit.0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 2 3 4 5 6 710 21 42 53 74 25 16 77CMSC 411 - A. Sussman (from D. O'Leary) 3CMSC 411 - Alan Sussman 13Cache memory (cont.)Initially, all the valid bitsset to zero.0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 2 3 4 5 6 710 21 42 53 74 25 16 77CMSC 411 - Alan Sussman 14Cache memory (cont.)0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 2 3 4 5 6 710 21 42 53 74 25 16 77Suppose want to load block 14 (octal) from memory into cache.Three ways to organize cache• direct mapped• set associative• fully associativeCMSC 411 - Alan Sussman 15Direct mapped cache0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 2 3 4 5 6 710 21 42 53 74 25 16 77In direct mapped cache, block 14 can only be put in the cache block with address 4.So the cache will no longer hold the block with memory address 74.CMSC 411 - Alan Sussman 16Direct mapped cache (cont.)0 0 0 0 1 0 0 00 0 0 0 0 0 0 00 1 2 3 4 5 6 710 21 42 53 14 25 16 77After the load, the contents look like this.CMSC 411 - Alan Sussman 17Set associative cache0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 2 3 4 5 6 710 24 41 55 72 26 13 77In set associative cache, each memory block can be put in any of a set of possible blocks in cache.For example, if divide cache into 4 sets, block 14 can be put in any block in Set 0 (since last two bits of 14 octal are zero).Set 0 Set 1 Set 2 Set 3CMSC 411 - Alan Sussman 18Set associative cache (cont.)1 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 2 3 4 5 6 714 24 41 55 72 26 13 77So after loading the block, cache memory might looklike this.Set 0 Set 1 Set 2 Set 3CMSC 411 - A. Sussman (from D. O'Leary) 4CMSC 411 - Alan Sussman 191 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 2 3 4 5 6 714 24 41 55 72 26 13 77Note that the last two bits of the memory block’s address always match the set number, so do not need to be stored. This part of the address iscalled the index. The higher order bits are stored, and are called the tag.In these pictures, both index and tag shown.Set 0 Set 1 Set 2 Set 3Set associative cache (cont.)CMSC 411 - Alan Sussman 20Set associative cache replacement• Which entry in the set to replace?• Three common choices:– Replace an eligible random block– Replace the least recently used (LRU) block• can be hard to keep track of, so often only approximated– Replace the oldest eligible block (First In, First Out, or FIFO)CMSC 411 - Alan Sussman 21Data cache replacement – Fig. 5.692.592.192.192.592.192.192.592.192.2256KB100.3100.599.7103.1102.3102.4103.9104.3103.464KB110.4111.8109.0113.3115.1111.7115.5117.3114.116KBFIFORandomLRUFIFORandomLRUFIFORandomLRUSizeEight-WayFour-wayTwo-waySPEC2000, in misses per 1000 instructionsSet associativityComputer Systems ArchitectureCMSC 411Unit 5 – Memory HierarchyAlan SussmanOctober 12, 2004CMSC 411 - Alan Sussman 23Administrivia• Quiz 2 today– questions?• HW for Unit 5 out soonCMSC 411 - Alan Sussman 24Last time• Main memory– frame address – page number– block number – cache block within page– contents – the data• Cache memory– block address• tag – high order bits for matching• index – which set, for set associative caches– block offset – which byte within the block– contains way fewer blocks than main memory– for each cache block – block number, memory address of block it contains, data, valid bit, dirty bitCMSC 411 - A. Sussman (from D. O'Leary) 5CMSC 411 - Alan Sussman 25Last time (cont.)• Direct mapped cache– each memory block can only go into 1 cache block –use low order bits of block address• Set associative cache– multiple places for a memory block to go – the degreeof set associativity is how many– don’t need to store the index (the set number), since its known from the cache block number – rest of block address is the tag– replacement policy determines which block to replace when new one is loaded (e.g., random, LRU, FIFO)CMSC 411 - Alan Sussman 26Fully associative cache0 0 0 0