University:
California State University, Northridge
Course:
COMP 222 | Computer Organization
Academic year:

2016
Views:

104

Pages:

26
Author:

leatherfaceg5v

+ William Stallings Computer Organization and Architecture + Chapter 4 Cache Memory Part 3 Simple Set Associative Cache Memory Address Space Memory Address Tag Set Word 0 0 0 0 0 0 0 1 0 0 0 0 0 1 2 0 0 0 0 1 0 3 0 0 0 0 1 1 Block Block 0 Block 1 4 0 0 0 1 0 0 5 0 0 0 1 0 1 6 0 0 0 1 1 0 7 0 0 0 1 1 1 8 0 0 1 0 0 0 9 0 0 1 0 0 1 10 0 0 1 0 1 0 11 0 0 1 0 1 1 12 0 0 1 1 0 0 Block 2 Block 3 Block 4 Block 5 13 0 0 1 1 0 1 14 0 0 1 1 1 0 15 0 0 1 1 1 1 16 0 1 0 0 0 0 17 0 1 0 0 0 1 18 0 1 0 0 1 0 19 0 1 0 0 1 1 20 0 1 0 1 0 0 21 0 1 0 1 0 1 22 0 1 0 1 1 0 23 0 1 0 1 1 1 24 0 1 1 0 0 0 25 0 1 1 0 0 1 26 0 1 1 0 1 0 K=1 Word 0 Block 6 Block 7 Block 8 Block 9 Set Word 1 K=2 Word 0 Word 1 0 1 2 3 4 5 6 7 SIMPLE EXAMPLE DESIGN PARAMETERS Word: 1 bit Set: 3 bits Tag: 2 bits Keys: 2 with 2 words/line Block 10 Block 11 Block Size: 21 or 2 words Block 12 Number of Blocks: 16 Block 13 27 0 1 1 0 1 1 28 0 1 1 1 0 0 29 0 1 1 1 0 1 30 0 1 1 1 1 0 31 0 1 1 1 1 1 Block 14 Block 15 Number of Sets: 23 or 8 Simple Set Associative Cache Worksheet Memory Address Space Memory Address Tag Set Word 0 0 0 0 0 0 0 1 0 0 0 0 0 1 2 0 0 0 0 1 0 3 0 0 0 0 1 1 4 0 0 0 1 0 0 5 0 0 0 1 0 1 6 0 0 0 1 1 0 7 0 0 0 1 1 1 8 0 0 1 0 0 0 9 0 0 1 0 0 1 10 0 0 1 0 1 0 11 0 0 1 0 1 1 12 0 0 1 1 0 0 13 0 0 1 1 0 1 14 0 0 1 1 1 0 15 0 0 1 1 1 1 16 0 1 0 0 0 0 17 0 1 0 0 0 1 18 0 1 0 0 1 0 Key 1 Key 2 Set Block v d Tag Word 0 Word 1 v d Tag Word 0 Word 1 W0-A W1-A 0 Block 1 2 Block 3 4 Block 5 6 Block 7 Block Block Block DATA WORDS NOTATION W0-A W1-A Block WHERE "A" IS THE MEMORY ADDRESS Block 19 0 1 0 0 1 1 20 0 1 0 1 0 0 21 0 1 0 1 0 1 22 0 1 0 1 1 0 23 0 1 0 1 1 1 24 0 1 1 0 0 0 25 0 1 1 0 0 1 26 0 1 1 0 1 0 27 0 1 1 0 1 1 28 0 1 1 1 0 0 29 0 1 1 1 0 1 30 0 1 1 1 1 0 31 0 1 1 1 1 1 Block Block Block Block Block Block s+w Cache Tag Memory Address Word Set s–d d Tag Main Memory Data B0 F0 B1 w F1 Set 0 s–d Fk–1 Fk s+w Bj Compare Fk+i (hit in cache) 1 if match 0 if no match 0 if match 1 if no match Set 1 F2k–1 (miss in cache) Figure 4.14 k-Way Set Associative Cache Organization Tag (hex) Main memory address (binary) Tag Main Memory Address = Set + Word 000 000000000000000000000000 000 000000000000000000000100 Data 13579246 Tag Set 9 bits Word 13 bits 2 bits 000 000000001111111111111000 000 000000001111111111111100 02C 000101100000000000000000 02C 000101100000000000000100 77777777 11235813 Set Tag Data Data Number Tag 000 13579246 0000 02C 77777777 02C 11235813 0001 02C 000101100011001110011100 FEDCBA98 02C FEDCBA98 0CE7 02C 000101100111111111111100 12345678 1FF 11223344 02C 12345678 1FFE 1FFF 9 bits 1FF 111111111000000000000000 1FF 111111111000000000000100 1FF 111111111111111111111000 1FF 111111111111111111111100 32 bits 1FF 24682468 9 bits 32 bits 16 Kline Cache 11223344 24682468 32 bits 16 MByte Main Memory Note: Memory address values are in binary representation; other values are in hexadecimal Figure 4.15 Two-Way Set Associative Mapping Example Figure 4.15 shows our example using set-associative mapping with two lines in each set, referred to as twoway set-associative. • The 13-bit set number identifies a unique set of two lines within the cache. It also gives the number of the block in main memory, modulo 213. This determines the mapping of blocks into lines. • Thus, blocks 000000, 008000, …, FF8000 of main memory map into cache set 0. • Any of those blocks can be loaded into either of the two lines in the set. Note that no two blocks that map into the same cache set have the same tag number. • For a read operation, the 13-bit set number is used to determine which set of two lines is to be examined. • Both lines in the set are examined for a match with the tag number of the address to be accessed. In the extreme case of v = m , k = 1, the setassociative technique reduces to direct mapping, and for v = 1, k = m , it reduces to associative mapping. • The use of two lines per set (v = m /2, k = 2) is the most common set-associative organization. It significantly improves the hit ratio over direct mapping. • Four- way set associative (v = m /4, k = 4) makes a modest additional improvement for a relatively small additional cost [MAYB84, HILL89]. Further increases in the number of lines per set have little effect. 1.0 0.9 0.8 Hit ratio 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 1k 2k 4k 8k 16k 32k 64k 128k 256k 512k Cache size (bytes) direct 2-way 4-way 8-way 16-way Figure 4.16 Varying Associativity over Cache Size 1M + Replacement Algorithms Once the cache has been filled, when a new block is brought into the cache, one of the existing blocks must be replaced For direct mapping there is only one possible line for any particular block and no choice is possible For the associative and set-associative techniques a replacement algorithm is needed To achieve high speed, an algorithm must be implemented in hardware + The most common replacement algorithms are: Least recently used (LRU) Most effective Replace that block in the set that has been in the cache longest with no reference to it Because of its simplicity of implementation, LRU is the most popular replacement algorithm First-in-first-out (FIFO) Replace that block in the set that has been in the cache longest Easily implemented as a round-robin or circular buffer technique Least frequently used (LFU) Replace that block in the set that has experienced the fewest references Could be implemented by associating a counter with each line Write Policy When a block that is resident in the cache is to be replaced there are two cases to consider: There are two problems to contend with: If the old block in the cache has not been altered then it may be overwritten with a new block without first writing out the old block More than one device may have access to main memory If at least one write operation has been performed on a word in that line of the cache then main memory must be updated by writing the line of cache out to the block of memory before bringing in the new block A more complex problem occurs when multiple processors are attached to the same bus and each processor has its own local cache - if a word is altered in one cache it could conceivably invalidate a word in other caches + Write Through and Write Back Write through Simplest technique All write operations are made to main memory as well as to the cache The main disadvantage of this technique is that it generates substantial memory traffic and may create a bottleneck Write back Minimizes memory writes Updates are made only in the cache Portions of main memory are invalid and hence accesses by I/O modules can be allowed only through the cache This makes for complex circuitry and a potential bottleneck Line Size When a block of data is retrieved and placed in the cache not only the desired word but also some number of adjacent words are retrieved Two specific effects come into play: As the block size increases more useful data are brought into the cache As the block size increases the hit ratio will at first increase because of the principle of locality • Larger blocks reduce the number of blocks that fit into a cache • As a block becomes larger each additional word is farther from the requested word The hit ratio will begin to decrease as the block becomes bigger and the probability of using the newly fetched information becomes less than the probability of reusing the information that has to be replaced + Multilevel Caches As logic density has increased it has become possible to have a cache on the same chip as the processor The on-chip cache reduces the processor’s external bus activity and speeds up execution time and increases overall system performance When the requested instruction or data is found in the on-chip cache, the bus access is eliminated On-chip cache accesses will complete appreciably faster than would even zero-wait state bus cycles During this period the bus is free to support other transfers Two-level cache: Internal cache designated as level 1 (L1) External cache designated as level 2 (L2) Potential savings due to the use of an L2 cache depends on the hit rates in both the L1 and L2 caches The use of multilevel caches complicates all of the design issues related to caches, including size, replacement algorithm, and write policy 0.98 0.96 0.94 0.92 Hit ratio 0.90 L1 = 16k 0.88 L1 = 8k 0.86 0.84 0.82 0.80 0.78 1k 2k 4k 8k 16k 32k 64k 128k 256k 512k 1M 2M L2 Cache size (bytes) Figure 4.17 Total Hit Ratio (L1 and L2) for 8 Kbyte and 16 Kbyte L1 + Unified Versus Split Caches Has become common to split cache: One dedicated to instructions One dedicated to data Both exist at the same level, typically as two L1 caches Advantages of unified cache: Higher hit rate Balances load of instruction and data fetches automatically Only one cache needs to be designed and implemented Trend is toward split caches at the L1 and unified caches for higher levels Advantages of split cache: Eliminates cache contention between instruction fetch/decode unit and execution unit Important in pipelining Problem Solution Add external cache using External memory slower than the system faster memory bus. technology. Move external cache onIncreased processor speed results in chip, operating at the external bus becoming a bottleneck for same speed as the cache access. processor. Add external L2 cache Internal cache is rather small, due to using faster technology limited space on chip than main memory Contention occurs when both the Create separate data and Instruction Prefetcher and the Execution instruction caches. Unit simultaneously require access to the cache. In that case, the Prefetcher is stalled while the Execution Unit’s data access takes place. Create separate back-side bus that runs at higher speed than the main Increased processor speed results in (front-side) external bus. external bus becoming a bottleneck for L2 The BSB is dedicated to cache access. the L2 cache. Move L2 cache on to the processor chip. Some applications deal with massive Add external L3 cache. databases and must have rapid access to large amounts of data. The on-chip caches Move L3 cache on-chip. are too small. Processor on which Feature First Appears 386 486 486 Pentium Table 4.4 Intel Cache Evolution Pentium Pro Pentium II Pentium III Pentium 4 (Table is on page 150 in the textbook.) System Bus Out-of-order execution logic L1 instruction cache (12K µops) Instruction fetch/decode unit 64 bits L3 cache (1 MB) Integer register file Load address unit Store address unit Simple integer ALU FP register file Simple integer ALU Complex integer ALU FP/ MMX unit FP move unit L1 data cache (16 KB) Figure 4.18 Pentium 4 Block Diagram L2 cache (512 KB) 256 bits Table 4.5 Pentium 4 Cache Operating Modes Control Bits Operating Mode CD NW Cache Fills Write Throughs Invalidates 0 0 Enabled Enabled Enabled 1 0 Disabled Enabled Enabled 1 1 Disabled Disabled Disabled Note: CD = 0; NW = 1 is an invalid combination. + Summary Cache Memory Chapter 4 Computer memory system overview Characteristics of Memory Systems Memory Hierarchy Cache memory principles Pentium 4 cache organization Elements of cache design Cache addresses Cache size Mapping function Replacement algorithms Write policy Line size Number of caches

Cache Memory, Part 3

of 26

Description

Free up your schedule!

Take 5 seconds to unlock