Cache Memory

Cache Memory Internal Memory Processor Memory – Registers Cache Memory – L1, L2, L3 Main Memory – Dynamic Random Access Memory (DRAM) Cost/Bit Decreases Access Time Increases Capacity Increases Decreasing Frequency of Access External Memory (Peripheral) Principle of Locality of Reference Fixed Hard Disk There is a high probability that future memory accesses are in the near vicinity Removable Hard Disk of recent memory accesses Optical Disks – CD, DVD Solid State Memory -- Flash Drives, Memory Cards Magnetic Tape Unit of Transfer: number of electrical lines
 memory module Word: • • • (alternative definitions) Unit of memory organization, i.e., the “natural” amount of memory that is retrievable in a single cycle Number of bits used to represent an integer or some multiple thereof Equal to the instruction length o Intel x86 word size 32 bits – instruction lengths vary o Cray C90 64 bit word, instruction length 46 bits Addressable Units • Word • Byte o If (address length == A bits) the number, N, of addressable units, i.e., bytes, is 2A Unit of Transfer • Main Memory -- number of memory bits read/written during a single event, i.e., number of lines into and out of the memory module, • External Memory – blocks Access Methods • Sequential Access – magnetic tapes o sequential searching, counting, waiting o access time is highly variable • Direct Access – disk drives o (track, sector)  general vicinity o sequential searching, counting, waiting o access time is variable within strict limits • Random Access – main memory o memory address  data item o access time is  independent of previous searches  close to being constant • Associative Access – cache memory o comparison of selected bit locations within a word, for a selected match, simultaneously o word is retrieved based on a portion of its contents rather than its address o access time is constant 1 Performance • Access Time (Latency) o Random Access Memory  time differential: ((time that data is stored or made available) – (time address is presented)) o Non-Random Access Memory  time differential: ((time that read-write mechanism is positioned at desired location) – (time that the (track, sector) is presented)) • Memory Cycle Time – System Bus o Access Time + time required for transient signals to die + time required to regenerate data after destructive reads  Transfer Time -- rate at which data is transferred
 a memory unit o Random Access Memory  transfer time = 1/(cycle time) o Non-Random Access Memory  transfer time ࢔ ࢀࡺ = ࢀ࡭ + ࡾ TN : average time to read/write N bits TA : average access time n : number of bits R : transfer rate measured in bits/second (bps) • Two Level Memory Access Level 1 hold 1000 words with Level 2 holds 100,000 words with an access time 0.01 µs an access time 0.1 µs ࢎ࢏࢚ ࢘ࢇ࢚࢏࢕ = ‫ ܔ܍ܞ܍ۺ‬૚ ‫ܛܜܑܐ ܡܚܗܕ܍ܕ‬ ‫ܛܜܑܐ ܡܚܗܕ܍ܕ ܔ܉ܜܗܜ‬ if 95% of the memory accesses are from Level 1 5% of the memory accesses are from Level 2 then the hit ratio is (0.95)(0.01 µs) + (0.05)( 0.01 µs + 0.1 µs)  0.0095 µs + 0.0055 µs  0.015 µs • • Locality of Reference o Instructions  Loops, Subroutines o Data  Tables, Arrays, Clustered Data Sets CPU IBM Mainframes --Expanded Storage (slow semiconductor-based storage) Memory Register Set (Cache) Cost/Bit Decreases Access Time Increases Capacity Increases Decreasing Frequency of Access L1 Cache External Storage L2 Cache Main Memory Buffer Memory, i.e., Disk Cache Disks normally Read/Write in Block Clusters 2 Performance Characteristics of Two-Level Memories Spatial Locality – clustered memory locations • Sequential Instructions • Sequential Data Locations • Using larger cache blocks • Incorporating prefetching mechanisms into the cache memory logic Temporal Locality – repeatedly access a set of memory locations • Loops • Maintaining recently used data and instructions in cache memory 3 Locality of Reference – clustered sets of data/instructions Cache Memory Word Transfers CPU L1 Cache L2 Cache L3 Cache Main Memory Block Transfers Slower Faster Line Numbers Tag Memory Address Cache Memory (example) Main Memory Ctr 0 0 1 1 2 Block 0 K words 2 ⋮ Lines ⋮ c-1 Line Size == Block Length, i.e. K Words each line contains one block of main memory Block M-1 K words Cache Memory n 2 -1 c lines where each Line consists of K words, i.e., a block of main memory Tag bits – identifies block currently stored in line Control bits, e.g., modified bit, read bit, etc. (Ctr) Word Length Byte addressable machines can have Lines as small as 32 bits, with 4 bytes/block c << M 4 • • • • Main Memory n 2 addressable words each word has a unique n-bit address M blocks each consisting of K words ࢔ M = ૛ ൗࡷ i.e., M*K = ૛࢔ Alternative Organizations address lines CPU Data Buffer data lines System Bus control lines Cache Main Memory System Bus Address Buffer Main Memory CPU attempts to retrieve data from Cache If data is not in Cache then the Address Buffer & Data Buffer are used to access main memory via the system bus the requested data item is returned to the CPU while the system simultaneously returns the memory block to the Cache Cache Address Buffer CPU Data Buffer CPU attempts to retrieve data from Cache If data is not in Cache then the Address Buffer & Data Buffer are activated to access main memory via the system bus; 1st 2nd the memory block is returned to the Cache and then the requested data item is returned to the CPU 5 Logical (Virtual) Cache cache stores data using virtual addresses logical address physical address MMU Main Memory Cache Processor data address fields of machine instructions contain virtual addresses Physical Cache cache stores data using physical addresses logical address physical address MMU Main Memory Cache Processor data Virtual Cache • delivers memory items to CPU faster, i.e., does not need to wait for Memory Management Unit • most virtual memory systems start the pages at address zero; the same virtual address for two different processes refer to two different physical addresses; hence either the cache must be flushed with each process context switch or each line of the cache must contain additional bits to identify the correct virtual address space logical address P0 2 56 logical address P1 page table P0 2 physical address P0 0 1 2 56 5 page table P1 0 1 56 1 P1 A 2 P C P0 3 P0 D 4 P1 C 5 P0 A 6 P1 B 7 P1 D 8 P0 B 1 56 5 2 3 1 3 ………. 6 • Logical Cache, i.e., Virtual Cache Faster response time within each process Context switch  flush cache memory OR add additional bits to each line which identifies the process that is using that line • Physical Cache Slower response time since each cache access has to also invoke the MMU Context switch does not require that the cache memory be flushed • Cache Size Parameters Small  cost per bit of cache ≅ cost per bit of main memory Large  overall average access time of (main + cache) memory ≅ access time of cache memory ∆↑ cache size  ∆↑ logic gates  ∆↓ cache access time chip & board size limits cache memory size • Mapping Function Main Memory Blocks  Cache Lines (number of cache lines << number of main memory blocks) Determining which memory block occupies a specific cache line Assumptions for Direct, Associative & Set-Associative Mapping Functions cache holds 64 KB data transfer block size == 4 bytes cache line size == 4 bytes 14 number of cache lines == 16K, i.e., 2 lines of 4 bytes each Page 125 Example 4.2 main memory == 16 MB; byte addressable; 24-bit address (2 main memory == 4 MB blocks (4 bytes/block) • 24 = 16 MB) Direct Mapping ࢏ = ࢐ ࢓࢕ࢊ ࢓ where i : cache line number, j : main memory block number, m : number of cache lines Cache Line 0 1 2 … Main Memory Blocks Assigned s 0, m, 2m, …, 2 -m s 1, m + 1, 2m + 1, … , 2 – m + 1 s 2, m + 2, 2m + 2, … , 2 – m + 2 … … Cache Access m = 16K = 2 ࢏ = ࢐ ࢓࢕ࢊ Cache Line 0 1 … … … m-1 m – 1, 2m – 1, 3m – 1, … , 2 - 1 s 2 14 Page 128 Example 4.2a 14 ૛૚૝ Block Address 000000, 010000, … , FF0000 000004, 010004, … , FF0004 … 00FFFC, 01FFFC, … , FFFFFC –1 Page 129 Figure 4.10 tag 0 0 0 0 0 line 0 0 0 0 0 0 0 0 0 0 word 0 0 binary 0 0 0 0 0 0 0 data 1 3 5 7 9 2 4 hexadecimal If two different blocks have the same tag number they map onto different lines, e.g., Block 000101100011001110011100 containing FEDCBA98 maps to line 0CE7 with tag 16 Block 000101101111111111111100 containing 12345678 maps to line 3FFF with tag 16 Memory Address (24bits)  Tag (8bits) + “Cache” Line (14) + “Byte” Cache Line Offset (2 bits) 7 6 s+w Line Li Tag Cache Tag Data Word 3 Main Memory B0 L0 s-r r w Tag s-r match s Li w Bj w equal? Lm-1 no match w bits identifies unique byte/word within block s bits specify a particular block in main memory; it is also used as the tag r bits identifies a specified line of the cache 1. 2. 3. 4. Line number indexes into cache Desired tag is compared with the tag value returned from the cache line If equal, use the word value to index into the line to locate the desired word/byte If not equal, use the tag value conjoined with the word value to locate the desired block in main memory Memory Address Length = s+w bits Number of addressable units of memory (words or bytes) = 2s+w Block size == Line size == 2w words or bytes Number of blocks in Main Memory = Number of lines in cache = m = 2r Size of cache = 2r+w words or bytes Size of tag = (s-r) bits ૛࢙శ࢝ ૛࢝ = ૛࢙ Implementation is inexpensive If two different blocks map to the same line, repeated references to these two blocks will result in continual swapping of the blocks, i.e., thrashing! Save swapped out line in a victim cache Victim Cache – fully associative cache (4-16 cache lines) residing between direct mapped L1 cache & next level of memory 8 Associative Mapping • • each main memory block may be loaded into any line of the cache memory address
 Tag + Word o Tag is used to identify a specific memory block o Word == offset within the line ; used to identify a specific word memory address does not identify the line number of lines is not determined by the address format control logic simultaneously examines every line’s Tag for a match to the memory address’s Tag • • • Memory Address Length = s+w bits s+w Number of addressable units of memory (words or bytes) = 2 w Block size == Line size == 2 words or bytes Number of blocks in Main Memory = ૛࢙శ࢝ = ૛࢝ ૛࢙ Number of lines in cache = undetermined Size of tag = s bits s+w Tag Cache Tag Data Word Main Memory B0 L0 s w Tag s no match Li w compare Bj w Lm-1 fully associative search, i.e., simultaneous search, of the content of all Tags page 129, figure 4.11 Tag field uniquely identifies a block of main memory To determine whether the block is in the cache, the cache control logic must simultaneously examine every line’s tag for a match • • • page 130 Example 4.2b Figure 4.12 Handouts slides 38, 40, 41, 42, 43 Disadvantage – complex circuitry required to implement associative memory retrieval Advantage – flexibility as to where a new block may be stored in the cache 9 Set Associative Mapping • • Set == Group of Lines Cache == Group of Sets • k-way set-associative mapping function ࢓=࢜ ∗࢑ (v == m & k == 1)  direct mapping i = ࢐ ࢓࢕ࢊ ࢜ (v == 1 & k == m)  associative mapping where i : cache set number j : main memory block number m : number of lines in the cache v : number of sets k : number of lines in each set (v == m/2 & k == 2)  2-way set-associative cache memory Significantly improves hit ratio over direct mapping (v == m/4 & k == 4)  4-way set-associative cache memory Modest improvement over 2-way for small additional cost Block Bi can be mapped into any of the lines of the set i  address length = s+w bits s+w  number of addressable units = 2 words or bytes w  block size = line size = 2 words or bytes s+w w s  number of blocks in main memory = (2 )/2 = 2  number of lines in set = k d  number of sets = 2 = v d  number of lines in cache = m = kv = k*2 d+w  size of cache = k*2 words or bytes  size of tag = s-d bits o Physical implementation of a set-associative cache  v number of individual associative caches (sets)  k number of individual direct associative caches (lines in a set)  each direct associative cache
 way which consists of v lines  first v blocks of main memory are directly mapped to the v lines of each way s+w Tag Set Cache Tag Data Word Main Memory F0 F1 s-d w B0 Set 0 d Fk-1 s-d s+w Fk Bj compare match Fk+1 F2k-1 no match Set 1 page 133, figure 4.14 slides 44 & slide 51 10 Replacement Algorithms • Direct Mapping --∀ block ∃! line, i.e., for every block there exists only one unique line, i.e., there is no choice • Associative & Set Associative o LRU, i.e., Least Recently Used – select block with longest time in cache with no memory references  2-way set-associative : each line has a USE bit – when a line is referenced its USE bit is set to 1 and the USE bit of the other line is set to 0 Line 1 1 65AB 665A Set Line 2 0 DE53 4534 replacement choice for the set will be the line with the USE bit == 0 • USE bit n-way associative & associative : maintain a separate list of line numbers when a line is referenced, its line number is placed at the front of the list replacement candidates are taken from the back of the list o FIFO, i.e., first-in, first-out – select block with longest time in cache round-robin -- circular buffer o LRU, i.e., least recently used – select block with fewest references each line has a counter to record the number of references 371 65AB 665A Counters 15 DE53 4534 o Random choice – select block using a random number generator Write Policy • old block in cache has not been altered  overwrite old block with new block • old block in cache has been altered  write old block to main memory before overwriting with the new block • Write-Through – all write operations change both the cache and the main memory any other processor-cache module must monitor main memory traffic to maintain consistency traffic bottleneck • Write-Back – updates are written only to the cache o when line is modified it’s dirty bit is set o when the line is selected for replacement, the line needs to be written to main memory only if it’s dirty bit is set portions of main memory are invalid access of I/O modules must be through the cache complex circuitry & potential bottleneck Percentage of Memory Reference Writes, i.e., • • • Normal computation 15% vector-vector multiplication 33% matrix transposition 50% 11 ‫ܛ܍܋ܖ܍ܚ܍܎܍ܚ ܡܚܗܕ܍ܕ ܍ܜܑܚܟ‬ ‫ܛ܍܋ܖ܍ܚ܍܎܍ܚ ܡܚܗܕ܍ܕ ܔ܉ܜܗܜ‬ Bus Organization multiple devices may each have a cache memory module even with write-through, multiple caches may hold invalid data • Bus Watching with Write-Through o each cache controller monitors write operations to main memory by other bus masters o if a write is to a location in main memory that also resides in the local cache, the local cache data items are invalidated • Hardware Transparency o All cache updates are written to main memory; any matching words in other caches are also updated • Non-cacheable Memory o Shared memory  Is that portion of memory shared by more than one processor  declared to be non-cacheable, i.e., it is never copied into cache memory  all references to shared memory are cache misses Principle of Locality useable information Block Size too small Up to a certain point: Block Size Δ ↑  Hit Ratio ↑ useable information After that point: Block Size Δ ↑  Hit Ratio ↓ Optimal Line Size • Normal Computation • High Performance Multilevel Caches • L1 : on-chip cache o bus access is eliminated o shorter data paths 8 Bytes ≤ Line Size ≤ 64 Bytes 64 Bytes ≤ Line Size ≤ 128 bytes useable information un-useable information faster data retrieval • L2 : external cache, i.e., off-chip cache o processor does not need to engage in bus access to DRAM nor ROM o If L2 is implemented as a SRAM, i.e., static RAM chip, which matches the bus speed then data can be accessed using a zero-wait state transaction o separate data path may be used to reduce traffic on the data bus • L2 may be placed on-chip yielding faster response times o L3 off-chip • L3 on-chip Page 139 figure 4.17 Simulation Study Two-level Cache Performance vs. Cache Size L2 must be 2x twice L1 L1 Size size forfor Performance Performance Increase Increase 12 Split Caches – parallel instruction execution, prefetching predicted future instructions • Data Caches • Instruction Caches Unified Cache – higher hit ratio – Execution pattern More instruction fetches than data fetches  cache fills with instructions More data fetches than instruction fetches  cache fills with data Pentium 4 Cache Organization • 80386 cache exists but not on chip • 80486 single on-chip cache 8 KB, line size 16 bytes, 4-way set associative • Pentium data on-chip L1 cache instruction on-chip L1 cache • Pentium II L1 data cache 16 KB, line size 64 bytes, 4-way set associative, on-chip L1 instruction cache, on-chip … see below L2 cache 512 KB, line size 128 bytes, 8-way associative, on-chip feeds both L1 cache memories • Pentium III L1 data cache 16 KB, line size 64 bytes, 4-way set associative, on-chip L1 instruction cache, on-chip … see below L2 cache 512 KB, line size 128 bytes, 8-way associative, on-chip feeds both L1 cache memories L3 cache • Pentium 4 L1 data cache 16 KB, line size 64 bytes, 4-way set associative, on-chip L1 instruction cache, on-chip, line size 128 bytes, 8-way associative, on-chip L2 cache 512 KB, line size 128 bytes, 8-way associative, on-chip feeds both L1 cache memories L3 cache, on-chip Fetch/Decode Unit  Fetch instructions in order  Decode into micro-instructions  Store in L1 instruction cache Out-Of-Order Execution Unit  Schedules micro-instruction executions subject to  Data dependencies  Resource availability  Schedules speculative execution of micro-instructions Execution Units  Fetch required data from L1 data cache  Execute micro-instructions  Store results in registers Memory  L2 cache, L3 cache, System Bus, Main Memory Data Cache  Write-Back Policy – data written to main memory only when  removed from cache  data is modified 13