DOC PREVIEW
WUSTL CSE 362M - Chapter 7 The Memory Hierarchy – Part II

This preview shows page 1-2-3-4-31-32-33-34-35-63-64-65-66 out of 66 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 66 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 7 The Memory Hierarchy Part II Note The slides being presented represent a mix Some are created by Mark Franklin Washington University in St Louis Dept of CSE Many are taken from the Patterson Hennessy book Computer Organization Design Copyright 1998 Morgan Kaufmann Publishers This material may not be copied or distributed for commercial purposes without express written permission of the copyright holder The original slides may be found at http books elsevier com us mk us subindex asp maintarget companions d efaultindividual asp isbn 1558604286 country United States srccode re f subcode head pdf basiccode txtSearch SearchField operator order community mk Additionally some of the slides are taken from V Heuring H Jordan Computer Systems Design and Architecture 1997 SP06 1 Outline PART 1 Memory components SRAM DRAM ROM Decoders cell arrays Memory boards Chip Arrays More addresses wider words 2 D 3 D chip arrays Memory modules Partitioning memory to improve performance interleaving PART 2 Memory Hierarchy Temporal Physical Locality Cache Memory Direct Mapped Associative Set Associative Designs Performance issues and improved designs Virtual Memory Physical vs Logical Addressing TLB etc Performance Analysis and Modeling SP06 2 Memory Technology Characteristics Level SP06 Memory Type Average Access Time Typical Size Unit of Transfer Block Size 3 10ns 8KB 256MB Word 16 32bits Cache line 8B 16B 1 Cache 2 Main Memory 30 200ns 2MB 32GB 3 Disk 5 10ms 100Gb Page 4KB 16KB 4 Magnetic Tape 1 5sec 200Gb Record 16KB 3 Levels of the Memory Hierarchy Capacity Access Time Cost Staging Xfer Unit CPU Registers 100s Bytes 10s ns Registers Cache K Bytes 10 50 ns 1 0 1 cents bit Cache Instr Operands Blocks Main Memory M Bytes 100ns 400ns 0001 00001 cents bit Disk G Bytes 10 ms 10 000 000 ns 5 6 10 10 cents bit Tape infinite sec min 10 8 SP06 Upper Level faster prog compiler 1 8 bytes cache cntl 8 128 bytes Memory Pages OS 512 8K bytes Files user operator Mbytes Disk Tape Larger Lower Level 4 The Principle of Locality The Principle of Locality Program access a relatively small portion of the address space at any instant of time Two Different Types of Locality Temporal Locality Locality in Time If an item is referenced it will tend to be referenced again soon e g loops reuse Spatial Locality Locality in Space If an item is referenced items whose addresses are close by tend to be referenced soon e g straightline code array access Last 20 years HW relied on locality for speed SP06 5 Memory Hierarchy Terminology Hit data appears in some block in the upper memory level Hit Rate the fraction of memory accesses found in the upper level probability of a hit Hit Time Time to access the upper level which consists of RAM access time Time to determine hit miss Miss data needs to be retrieve from a block in the lower memory level Miss Rate 1 Hit Rate Probability of a miss Miss Penalty access time i e time to access 1st word of block transfer time i e time to transfer block after access Hit Time Miss Penalty factor of 10 to 20 SP06 6 Simplified Cache Performance Gains Average Instruction Time General Expression pipelined processor with no hazards one instruction per cycle Tinst Hit time Hit rate Miss time Miss rate With cache 95 hit probability 20 cycle miss penalty Tinst cache 1 0 0 95 20 0 0 05 1 95cycles Without cache Tinst no cache 20 0 1 0 20 0cycles Performance improvement 10 25 SP06 7 The Cache Mapping Function Example CPU 256 KB 16 words 32 MB Main memory Cache Block Word Address Mapping function The cache mapping function is responsible for all cache operations Placement strategy where to place an incoming block in the cache Replacement strategy which block to replace upon a miss Read and write policy how to handle reads and writes upon cache misses Mapping function must be implemented in hardware Why Three different types of mapping functions Direct mapped Fully associative Set associative SP06 Heuring Jordan 8 CACHE Addressing how are addresses mapped Memory Address 0 1 2 3 4 5 6 7 8 9 A B C D E F SP06 Memory 4 Byte Direct Mapped Cache Cache Index 0 1 2 3 Location 0 can be occupied by data from Memory location 0 4 8 etc In general any memory location whose 2 LSBs of the address are 0s Address 1 0 cache index Which one should we place in the cache Determining which one is in the cache 9 CACHE Addressing how are addresses mapped Since size of main memory size of cache how do we map general addresses into cache addresses Case 1 Direct Mapping address is modulo the number of blocks in the cache 000 001 010 011 100 101 110 111 Cache Cache is 8 words Main memory is 32 words 00001 SP06 00101 01001 01101 10001 Memory 10101 11001 11101 10 Direct Mapped Cache Tag memory Valid bits 30 1 0 0 256 512 9 1 1 1 257 513 1 1 2 2 258 514 1 1 255 Tag field 5 bits Cache memory Main memory block numbers 7680 7936 0 2305 7681 7937 1 7682 7938 2 255 511 767 Tag 0 1 2 9 One cache line 8 bytes Key Idea all the MM Cache address blocks from a given group can go into only one location in the 5 Main memory address cache corresponding Tag to the group number Group 8 3 8 3 Group Byte 8191 255 30 31 One cache line 8 bytes Now the cache needs only examine the single group that its reference specifies SP06 Heuring Jordan 11 Direct Mapped Cache Address showing bit positions 31 30 13 12 11 210 Byte offset For MIPS Hit 10 20 Tag Data Index Index Valid Tag Data 0 1 2 1021 1022 1023 20 SP06 32 12 Direct Mapped Cache Operation 1 Decode the group number of the incoming MM address to select the group 2 If Match AND Valid Main memory address Tag Group Byte 3 1 Tag memory Valid bits 30 1 9 1 1 1 3 Then gate out the tag field 8 256 decoder 1 Cache memory Hit 256 0 5 5 3 1 2 2 4 Compare cache tag with incoming tag 5 If a hit then gate out the cache line 8 5 1 1 255 5 Tag field 5 bits 4 5 bit comparator Cache miss 64 5 3 6 Selector Cache hit 8 6 and use the word field to select the desired word SP06 Heuring Jordan 13 Direct Mapped Cache 64 KB cache with 4 word 16B blocks Taking advantage of spatial locality Address showing bit positions 31 16 15 16 Hit 4 32 1 0 12 2 Byte offset Tag Data Index V Block offset 16 bits 128 bits Tag Data 4K entries 16 32 32 32 32 Mux 32 SP06 14 Performance as a function of block size 40 Increasing the block size tends to decrease miss rate 35 30 Miss rate 25 20 15 10 5 Use …


View Full Document

WUSTL CSE 362M - Chapter 7 The Memory Hierarchy – Part II

Download Chapter 7 The Memory Hierarchy – Part II
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Chapter 7 The Memory Hierarchy – Part II and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chapter 7 The Memory Hierarchy – Part II 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?