Uploaded byIIUM
PDF, PPTX4,993 views

Csc1401 lecture05 - cache memory

The document discusses cache memory principles and design. It begins with an overview of the memory hierarchy and how cache memory fits between the CPU and main memory. It then covers key elements of cache design, including cache addressing, size, mapping functions, and replacement algorithms. Mapping functions discussed include direct mapping, associative mapping, and set associative mapping. The document provides examples and diagrams to illustrate these cache mapping techniques.

Education◦
In this document
Powered by AI

Introduction of Madam Raini Hassan, Du’a for study, and a brief overview of Semester II 2014/2015.

Lecture introducing Cache Memory, its principles, and elements of cache design including cache addresses, size, and organization.

Discusses characteristics of computer memory systems, including location, capacity, unit of transfer, access methods, and the principle of locality.

Explains the memory hierarchy, trade-offs among capacity, access time, cost, and diagrams illustrating various memory levels.

Defines cache memory, its operation, and relationship with main memory, describing how CPUs utilize cache for faster data access.

Details on cache size, mapping functions (Direct, Associative, Set-Associative) and their implementation in process memory.

Cache management strategies covering replacement algorithms including LRU, FIFO, and their implementation for efficient data storage.

Describes write policies for cache management including Write Through and Write Back strategies to maintain memory integrity.

Discusses line size and number of caches in modern systems, including multilevel cache structure and advantages of unified vs split caches.

Highlights the evolution of cache organization specifically related to Intel microprocessors, illustrating changes in cache tech.

Download as PDF, PPTX
Madam Raini Hassan Office: C5 - 23, Level 5, KICT Building Department: Computer Science Emails: hrai@iium.edu.my, hraini.iii@gmail.com 1Semester II 2014/2015
Du’a for Study Semester II 2014/2015 2
LECTURE 05 Cache Memory (Chapter 4)
Outline • Computer Memory System Overview Characteristics of Memory Systems The Memory Hierarchy • Cache Memory Principles • Elements of Cache Design Cache Addresses Cache Size Mapping Function Replacement Algorithms Write Policy Line Size Number of Caches • Pentium 4 Cache Organization Semester II 2014/2015 4
Introduction • The complex subject of computer memory is made more manageable if we classify memory systems according to their characteristics. Semester II 2014/2015 5
Key Characteristics of Computer Memory Systems Table 4.1 Key Characteristics of Computer Memory Systems Semester II 2014/2015 6
7 1. Location • Refers to whether memory is internal and external to the computer • Internal memory is often equated with main memory • Processor requires its own local memory, in the form of registers • Cache is another form of internal memory • External memory consists of peripheral storage devices that are accessible to the processor via I/O controllers Semester II 2014/2015
8 2. Capacity • Memory is typically expressed in terms of bytes. • In other words, the capacity of a memory is the total number of bits that can be stored. • Word – A group of bits in memory that represents instructions or data. – The natural unit of organization (1 byte = 8 bits) – Common word lengths – 8, 16, 32 bits • Byte – The smallest unit of binary data is the bit and a collection of 8 bit is known as byte (1 byte = 8 bits) Semester II 2014/2015
9 3. Unit of Transfer • For internal memory (main memory), this is the number of bits read out of or written into memory at a time. • The unit of transfer need not equal a word on an addressable unit. • For external memory, data are often transferred in units larger than words; referred to as block. Semester II 2014/2015
Sequential access Memory is organized into units of data called records Access must be made in a specific linear sequence Access time is variable Direct access Involves a shared read-write mechanism Individual blocks or records have a unique address based on physical location Access time is variable 4. Access Methods (1) Semester II 2014/2015 10
Random access Each addressable location in memory has a unique, physically wired-in addressing mechanism The time to access a given location is independent of the sequence of prior accesses and is constant Any location can be selected at random and directly addressed and accessed Main memory and some cache systems are random access Associative A word is retrieved based on a portion of its contents rather than its address Each location has its own addressing mechanism and retrieval time is constant independent of location or prior access patterns Cache memories may employ associative access 4. Access Methods (2) Semester II 2014/2015 11
The two most important characteristics of memory Three performance parameters are used: Access time (latency) • For random-access memory it is the time it takes to perform a read or write operation • For non-random-access memory it is the time it takes to position the read-write mechanism at the desired location Memory cycle time • Access time plus any additional time required before second access can commence. • Additional time may be required for transients to die out on signal lines or to regenerate data if they are read destructively. • Concerned with the system bus, not the processor. Transfer rate • The rate at which data can be transferred into or out of a memory unit • For random-access memory it is equal to 1/(cycle time) 5. Capacity and Performance Semester II 2014/2015 12
13 6. Physical Types • Semiconductor – RAM • Magnetic surface memory – Disk & Tape • Optical – CD & DVD • Magneto-optical – Note book computer Semester II 2014/2015
14 7. Physical Characteristics • Decay • Volatility – Information decays naturally or is lost when electrical power is switched off – Example; semiconductor memory • Non-volatile – Once recorded, information remains without deterioration until deliberately changed – No electrical power is needed to retain information – Example: Magnetic-surface memories and semiconductor memory • Erasable • Non-erasable – Cannot be altered, except by destroying the storage unit – Semiconductor memory of this type is known as read-only memory (ROM) • Power consumption Semester II 2014/2015
15 8. Organization • Physical arrangement of bits into words. Semester II 2014/2015
Principle of Locality • Principle of locality (or locality of reference): • Program accesses a relatively small portion of the address space at any instant of time. • Temporal locality and spatial locality. Address Space 0 2 n - 1 Probability of reference Semester II 2014/2015 16
Principle of Locality (2)  Temporal locality (locality in time):   Keep most recently accessed data items closer to the processor.  Spatial locality (locality in space):   Move blocks consisting of contiguous words to ‘upper’ levels.  Block is a unit of transfer. Semester II 2014/2015 17
Principle of Locality (3) What programming constructs lead to principle of locality? Spatial Temporal Data arrays loop counters Code no branch/jump loop Semester II 2014/2015 18
The Memory Hierarchy • Design constraints on a computer’s memory can be summed up by three questions: – How much, how fast, how expensive • There is a trade-off among capacity, access time, and cost – Faster access time, greater cost per bit – Greater capacity, smaller cost per bit – Greater capacity, slower access time • The way out of the memory dilemma is not to rely on a single memory component or technology, but to employ a memory hierarchy Semester II 2014/2015 19
Memory Hierarchy – Basic Theoretical Diagram • Registers • L1 Cache • L2 Cache • Main memory • Disk cache • Disk • Optical • Tape Semester II 2014/2015 20
Memory Hierarchy – Simplified “Real Life” Diagram Semester II 2014/2015 21
Memory Hierarchy – Practical Diagram Semester II 2014/2015 22
Memory Hierarchy – Current Control Data path ProcessorRegs Second- ary MemoryL2 Cache L1$ Main Memory Speed(ns): 0.5ns 2ns 6ns 100ns 10,000,000ns Size (MB): 0.0005 0.05 1-4 100-1000 100,000 Cost ($/MB): -- $100 $30 $1 $0.05 Technology: Regs SRAM SRAM DRAM Disk Semester II 2014/2015 23
24 The 3 Parameters • Capacity, speed and cost increase moving from top to down. • First, access time get bigger; e.g.: CPU can be accessed in a few nanoseconds. • Second, the storage capacity increases as we go downwards. • CPU registers – around 128 bytes, caches – a few megabytes, main memory – thousands of megabytes, and magnetic disks – a few gigabytes. • Third, the number of bits per RM spent increases down the hierarchy. Semester II 2014/2015
The Bottom Line • How much? – Capacity • How fast? – Time is money • How expensive? Semester II 2014/2015 25
So you want fast? • It is possible to build a computer which uses only static RAM (see later) • This would be very fast • This would need no cache – How can you cache? • This would cost a very large amount Semester II 2014/2015 26
27 Cache Memory Principles • Small amount of fast memory • Sits between normal main memory and CPU • May be located on CPU chip or module Semester II 2014/2015
Cache and Main Memory Semester II 2014/2015 28
29 Other definitions of Cache 1. Cache memory is random access memory (RAM) that a computer microprocessor can access more quickly than it can access regular RAM. As the microprocessor processes data, it looks first in the cache memory and if it finds the data there (from a previous reading of data), it does not have to do the more time-consuming reading of data from larger memory. 2. A cache is a small capacity fast memory, too expensive to be used for the whole of RAM. It acts as an intermediate store between the CPU and main memory and is used to improve the overall speed of the computer since it is used primarily to keep the most active portions of the program being used. 3. A special, high-speed memory unit. 4. It is a temporary, very fast, digital storage for a central processor. Semester II 2014/2015
30 Cache operation - overview • CPU requests contents of memory location • Check cache for this data • If present, get from cache (fast) • If not present, read required block from main memory to cache • Then deliver from cache to CPU • Cache includes tags to identify which block of main memory is in each cache slot Semester II 2014/2015
Cache/Main Memory Structure Semester II 2014/2015 31
Cache Read Operation Semester II 2014/2015 32
Typical Cache Organization Semester II 2014/2015 33
Elements of Cache Design Table 4.2 Elements of Cache Design Semester II 2014/2015 34
+ 1. Cache Addresses • Virtual memory – Facility that allows programs to address memory from a logical point of view, without regard to the amount of main memory physically available – When used, the address fields of machine instructions contain virtual addresses – For reads to and writes from main memory, a hardware memory management unit (MMU) translates each virtual address into a physical address in main memory Semester II 2014/2015 35
Logical and Physical Caches Semester II 2014/2015 36
37 2. Cache Size • Cost – More cache is expensive • Speed – More cache is faster – Checking cache for data takes time Semester II 2014/2015
Table 4.3 Cache Sizes of Some Processors a Two values separated by a slash refer to instruction and data caches. b Both caches are instruction only; no data caches.Semester II 2014/2015 38
3. Mapping Function • Because there are fewer cache lines than main memory blocks, an algorithm is needed for mapping main memory blocks into cache lines • Three techniques can be used: 1. Direct 2. Associative 3. Set Associative Semester II 2014/2015 39
40 3. Mapping Function (Example) • Cache of 64kByte • Cache block of 4 bytes – i.e. cache is 16k (214) lines of 4 bytes • 16MBytes main memory • 24 bit address – (224=16M) Semester II 2014/2015
41 3. Mapping Function: Direct Mapping Direct Mapping • The simplest technique. • Each block of main memory maps to only one possible cache line – i.e. if a block is in cache, it must be in one specific place • Address is in two parts Semester II 2014/2015
42 3. Mapping Function: Direct Mapping Direct Mapping • Least Significant w bits identify unique word • Most Significant s bits specify one memory block • The MSBs (Most Significant Bits) are split into a cache line field r and a tag of s-r (most significant) Semester II 2014/2015
3. Mapping Function: Direct Mapping Semester II 2014/2015 43
3. Mapping Function: Direct Mapping Cache Organization Semester II 2014/2015 44
3. Mapping Function: Direct Mapping Example Semester II 2014/2015 45
3. Mapping Function: Direct Mapping Summary • Address length = (s + w) bits • Number of addressable units = 2s+w words or bytes • Block size = line size = 2w words or bytes • Number of blocks in main memory = 2s+ w/2w = 2s • Number of lines in cache = m = 2r • Size of tag = (s – r) bits Semester II 2014/2015 46
47 3. Mapping Function: Direct Mapping Pros & Cons • Simple • Inexpensive • Cons: Fixed location for given block – If a program accesses 2 blocks that map to the same line repeatedly, then the blocks will be continually swapped in the cache, caused the cache misses to be very high Semester II 2014/2015
48 3. Mapping Function: Fully Associative Cache • To reduce the conflict misses of direct mapped caches without affecting its fast access time is to remember what was discarded in case it is needed again. • Since the discarded data has already been fetched, it can be used again at a small cost. • Such recycling is possible by using a victim cache, also known as fully associative cache. • Typical size is 4 to 16 cache lines • Residing between direct mapped L1 cache and the next level of memory Semester II 2014/2015
3. Mapping Function: Fully Associative Cache Organization Semester II 2014/2015 49
50 3. Mapping Function: Associative Associative Mapping • Permits each main memory block to be loaded into any line of the cache. • The cache control logic interprets a memory address simply as a Tag and a Word field. • Tag uniquely identifies block of memory. • To determine whether a block is in the cache, the cache control logic must simultaneously examine every line’s Tag for a match . • Cache searching gets expensive. Semester II 2014/2015
3. Mapping Function: Associative Mapping Semester II 2014/2015 51
3. Mapping Function: Associative Mapping Example Semester II 2014/2015 52
3. Mapping Function: Associative Mapping Summary • Address length = (s + w) bits • Number of addressable units = 2s+w words or bytes • Block size = line size = 2w words or bytes • Number of blocks in main memory = 2s+ w/2w = 2s • Number of lines in cache = undetermined • Size of tag = s bits Semester II 2014/2015 53
54 3. Mapping Function: Set-Associative Set-Associative Mapping • Compromise that exhibits the strengths of both the direct and associative approaches while reducing their disadvantages • Cache consists of a number of sets • Each set contains a number of lines • A given block maps to any line in a given set – Block B can be in any line of set i • e.g. 2 lines per set – 2 way associative mapping – A given block can be in one of 2 lines in only one set Semester II 2014/2015
Mapping From Main Memory to Cache: k-Way Set Associative Semester II 2014/2015 55
k-Way Set Associative Cache Organization Semester II 2014/2015 56
3. Mapping Function: Set Associative Mapping Summary • Address length = (s + w) bits • Number of addressable units = 2s+w words or bytes • Block size = line size = 2w words or bytes • Number of blocks in main memory = 2s+w/2w=2s • Number of lines in set = k • Number of sets = v = 2d • Number of lines in cache = m = kv = k * 2d • Size of cache = k * 2d+w words or bytes • Size of tag = (s – d) bits Semester II 2014/2015 57
Semester II 2014/2015 58
3. Mapping Function: Varying Associativity Over Cache Size Semester II 2014/2015 59
4. 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. Semester II 2014/2015 60
61 4. Replacement Algorithms: Direct mapping • No choice • Each block only maps to one line • Replace that line Semester II 2014/2015
62 4. Replacement Algorithms: Associative & Set Associative • Hardware implemented algorithm (speed) 1. Least Recently used (LRU) 2. First in first out (FIFO) 3. Least frequently used 4. Random Semester II 2014/2015
4. Replacement Algorithms: LRU 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 Semester II 2014/2015 63
4. Replacement Algorithms: FIFO 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. Semester II 2014/2015 64
4. Replacement Algorithms: LFU 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 Semester II 2014/2015 65
When a block that is resident in the cache is to be replaced there are two cases to consider: 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 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 There are two problems to contend with: More than one device may have access to main memory 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 5. Write Policy Semester II 2014/2015 66
5. Write Policy In other words… • Must not overwrite a cache block unless main memory is up to date • Multiple CPUs may have individual caches • I/O may address main memory directly 2 methods of write policy are… Semester II 2014/2015 67
5. Write Policy: Write Through 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 Semester II 2014/2015 68
5. Write Policy: Write Back Write Back – Minimizes memory writes – Updates initially are made only in the cache – Update bit for cache slot is set when update occurs – If block is to be replaced, write to main memory only if update bit is set – Other caches get out of sync – Resulting 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 Semester II 2014/2015 69
6. 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. • As the block size increases the hit ratio will at first increase because of the principle of locality. • As the block size increases more useful data are brought into the cache. • 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. Semester II 2014/2015 70
6. Line Size • Two specific effects come into play: – 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 Semester II 2014/2015 71
7. Number of Caches • When caches were originally introduced, the typical system had a single cache. • More recently, the use of multiple caches has become the norm. Semester II 2014/2015 72
7. Number of Caches: 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 Semester II 2014/2015 73
7. Number of Caches: Multilevel Caches • 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 Semester II 2014/2015 74
7. Number of Caches: 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 Semester II 2014/2015 75
7. Number of Caches: Unified Versus Split Caches • 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 Semester II 2014/2015 76
Pentium 4 Cache Organization • The evolution of cache organization is seen clearly in the evolution of Intel microprocessors (Table 4.4) Semester II 2014/2015 77
Table 4.4 Intel Cache Evolution 78

More Related Content

PPTX
Cache memory
byAhsan Ashfaq
 
PPTX
Cache memory
byShailesh Tanwar
 
PPTX
Multiprocessor
byNeel Patel
 
PPT
Cache memory
byFaiq Ali Sayed
 
PPTX
Memory organization
byAL- AMIN
 
PPTX
FILE ALLOCATION METHODS.pptx ...........
byHiteshiArya
 
PPTX
Memory Hierarchy
byTrinity Dwarka
 
PPTX
Cache memory
byJay Prajapati
 
Cache memory
byAhsan Ashfaq
 
Cache memory
byShailesh Tanwar
 
Multiprocessor
byNeel Patel
 
Cache memory
byFaiq Ali Sayed
 
Memory organization
byAL- AMIN
 
FILE ALLOCATION METHODS.pptx ...........
byHiteshiArya
 
Memory Hierarchy
byTrinity Dwarka
 
Cache memory
byJay Prajapati
 

What's hot

PPT
Introduction to Computer Architecture
byAnkush Srivastava
 
PDF
Memory Management
byDEDE IRYAWAN
 
PPTX
Virtual Memory
byArchith777
 
PPTX
RISC and CISC Processors
byAdeel Rasheed
 
PPTX
Cache memory
byPrasenjit Dey
 
PPTX
Distributed shared memory ch 5
byAlagappa Government Arts College, Karaikudi
 
PPTX
Paging and Segmentation in Operating System
byRaj Mohan
 
PPTX
Computer architecture
byInternational Islamic University
 
PPT
Memory hierarchy
byMahesh Kumar Attri
 
PPTX
Cache memoy designed by Mohd Tariq
byMohd Tariq
 
PPT
Chapter 12 - Mass Storage Systems
byWayne Jones Jnr
 
PPTX
Memory organization (Computer architecture)
bySandesh Jonchhe
 
PPTX
CS304PC:Computer Organization and Architecture Session 23 Decimal Arithmetic ...
byGuru Nanak Technical Institutions
 
PPTX
Cache memory and virtual memory
byPrakharBansal29
 
PPT
multiprocessors and multicomputers
byPankaj Kumar Jain
 
PPT
cache memory
byNAHID HASAN
 
PPT
Unit 5 I/O organization
bychidabdu
 
PPT
distributed shared memory
byAshish Kumar
 
PPT
Memory management
byVishal Singh
 
PPTX
Modes of transfer
byAndhra University
 
Introduction to Computer Architecture
byAnkush Srivastava
 
Memory Management
byDEDE IRYAWAN
 
Virtual Memory
byArchith777
 
RISC and CISC Processors
byAdeel Rasheed
 
Cache memory
byPrasenjit Dey
 
Distributed shared memory ch 5
byAlagappa Government Arts College, Karaikudi
 
Paging and Segmentation in Operating System
byRaj Mohan
 
Computer architecture
byInternational Islamic University
 
Memory hierarchy
byMahesh Kumar Attri
 
Cache memoy designed by Mohd Tariq
byMohd Tariq
 
Chapter 12 - Mass Storage Systems
byWayne Jones Jnr
 
Memory organization (Computer architecture)
bySandesh Jonchhe
 
CS304PC:Computer Organization and Architecture Session 23 Decimal Arithmetic ...
byGuru Nanak Technical Institutions
 
Cache memory and virtual memory
byPrakharBansal29
 
multiprocessors and multicomputers
byPankaj Kumar Jain
 
cache memory
byNAHID HASAN
 
Unit 5 I/O organization
bychidabdu
 
distributed shared memory
byAshish Kumar
 
Memory management
byVishal Singh
 
Modes of transfer
byAndhra University
 

Viewers also liked

PPT
04 Cache Memory
byJeanie Delos Arcos
 
PPT
Cache memory presentation
bybravehearted1010
 
PPT
cache memory
byArmy Public School and College -Faisal
 
PPS
Cache memory
byAnuj Modi
 
PPTX
Semiconductor memories and auxiliary memories
byAsif Iqbal
 
PPTX
Cache performance considerations
bySlideshare
 
PPT
Cache memory
byMuhammad Ishaq
 
PDF
Locality of (p)reference
byFromDual GmbH
 
PPT
Cache memory.12
bymyrajendra
 
PPT
Vam: A Locality-Improving Dynamic Memory Allocator
byEmery Berger
 
PPTX
Cache memory
byGeorge Thomas
 
PPTX
Wireless sensor networks
bystudying telecommuciation engineering
 
PPT
Motorola microprocessor
byIffat Anjum
 
PDF
Csc1401 lecture07 -external memory
byIIUM
 
PDF
Routing Protocols for Wireless Sensor Networks
byDarpan Dekivadiya
 
PDF
Kernel Module Programming
bySaurabh Bangad
 
PPTX
Cache memory
byAnand Goyal
 
PPT
Interrupts
byNOTES EDU
 
PPT
Cache memory
byUniversitas Teknologi Indonesia Bali
 
PPTX
Routing Protocols in WSN
byDarpan Dekivadiya
 
04 Cache Memory
byJeanie Delos Arcos
 
Cache memory presentation
bybravehearted1010
 
cache memory
byArmy Public School and College -Faisal
 
Cache memory
byAnuj Modi
 
Semiconductor memories and auxiliary memories
byAsif Iqbal
 
Cache performance considerations
bySlideshare
 
Cache memory
byMuhammad Ishaq
 
Locality of (p)reference
byFromDual GmbH
 
Cache memory.12
bymyrajendra
 
Vam: A Locality-Improving Dynamic Memory Allocator
byEmery Berger
 
Cache memory
byGeorge Thomas
 
Wireless sensor networks
bystudying telecommuciation engineering
 
Motorola microprocessor
byIffat Anjum
 
Csc1401 lecture07 -external memory
byIIUM
 
Routing Protocols for Wireless Sensor Networks
byDarpan Dekivadiya
 
Kernel Module Programming
bySaurabh Bangad
 
Cache memory
byAnand Goyal
 
Interrupts
byNOTES EDU
 
Cache memory
byUniversitas Teknologi Indonesia Bali
 
Routing Protocols in WSN
byDarpan Dekivadiya
 

Similar to Csc1401 lecture05 - cache memory

PPT
Chapter 8 computer memory system overview
byAhlamAli20
 
PPTX
CH04-COA10e.pptx
byRahmadaniPutri
 
PPTX
cache cache memory memory cache memory.pptx
bysaimawarsi
 
PPT
chapter 4 memory and memory hierarchiy .ppt
bymule41
 
PPTX
ĐÁP ÁN 11 @ FDSF SDF SFSF SDFSDFSDFSDFDFDDDDDDDDDDDDDDD
byLuthMnh54
 
PPTX
MANHJC1BBBBBBBBBBBBBBBBBBBBB1111111111111111111B2E
byLuthMnh54
 
PPTX
UNIT II samiya patel random use pls.pptx
by5SamiyaPatel
 
PPTX
MEMORY & I/O SYSTEMS
byAmirthavalli Senthil
 
PPTX
computer architecture memory system organization
byssuser7fd7cb1
 
PPTX
FALLSEM2024-25_BCSE205L_TH_VL2024250108124_2024-09-30_Reference-Material-IV.pptx
byssuser7fd7cb1
 
PPT
Internal Memory FIT NED UNIVERSITY OF EN
bymoizbhai999
 
PPT
Ch 4 95
byJecka Cortez
 
PPTX
Computer organizatin.Chapter Seven.pptxs
byafendimohammed288
 
PPTX
ch-5 COA\szdghfjgkvjbmyughbhjtngfbvc.pptx
byFiraolGadissa
 
PPTX
COA notes
byShrutiKushwaha29
 
PPTX
onur-comparch-fall2018-lecture3b-memoryhierarchyandcaches-afterlecture.pptx
bysivasubramanianManic2
 
PPTX
Memory Organization of computer systemss
byRajasekharK28
 
PDF
Memory (Computer Organization)
byJyotiprakashMishra18
 
PPTX
Computer architecture memory system
byMazin Alwaaly
 
PPTX
Computer Architecture Input Output Memory.pptx
byGunasundari Selvaraj
 
Chapter 8 computer memory system overview
byAhlamAli20
 
CH04-COA10e.pptx
byRahmadaniPutri
 
cache cache memory memory cache memory.pptx
bysaimawarsi
 
chapter 4 memory and memory hierarchiy .ppt
bymule41
 
ĐÁP ÁN 11 @ FDSF SDF SFSF SDFSDFSDFSDFDFDDDDDDDDDDDDDDD
byLuthMnh54
 
MANHJC1BBBBBBBBBBBBBBBBBBBBB1111111111111111111B2E
byLuthMnh54
 
UNIT II samiya patel random use pls.pptx
by5SamiyaPatel
 
MEMORY & I/O SYSTEMS
byAmirthavalli Senthil
 
computer architecture memory system organization
byssuser7fd7cb1
 
FALLSEM2024-25_BCSE205L_TH_VL2024250108124_2024-09-30_Reference-Material-IV.pptx
byssuser7fd7cb1
 
Internal Memory FIT NED UNIVERSITY OF EN
bymoizbhai999
 
Ch 4 95
byJecka Cortez
 
Computer organizatin.Chapter Seven.pptxs
byafendimohammed288
 
ch-5 COA\szdghfjgkvjbmyughbhjtngfbvc.pptx
byFiraolGadissa
 
COA notes
byShrutiKushwaha29
 
onur-comparch-fall2018-lecture3b-memoryhierarchyandcaches-afterlecture.pptx
bysivasubramanianManic2
 
Memory Organization of computer systemss
byRajasekharK28
 
Memory (Computer Organization)
byJyotiprakashMishra18
 
Computer architecture memory system
byMazin Alwaaly
 
Computer Architecture Input Output Memory.pptx
byGunasundari Selvaraj
 

More from IIUM

PDF
How to use_000webhost
byIIUM
 
PDF
Chapter 2
byIIUM
 
PDF
Chapter 1
byIIUM
 
PDF
Kreydle internship-multimedia
byIIUM
 
PDF
03phpbldgblock
byIIUM
 
PDF
Chap2 practice key
byIIUM
 
PDF
Group p1
byIIUM
 
PDF
Tutorial import n auto pilot blogspot friendly seo
byIIUM
 
PDF
Visual sceneperception encycloperception-sage-oliva2009
byIIUM
 
PDF
03 the htm_lforms
byIIUM
 
PDF
Exercise on algo analysis answer
byIIUM
 
PDF
Redo midterm
byIIUM
 
PDF
Heaps
byIIUM
 
PDF
Report format
byIIUM
 
PDF
Edpuzzle guidelines
byIIUM
 
PDF
Final Exam Paper
byIIUM
 
PDF
Final Exam Paper
byIIUM
 
PDF
Group assignment 1 s21516
byIIUM
 
PDF
Avl tree-rotations
byIIUM
 
PDF
Week12 graph
byIIUM
 
How to use_000webhost
byIIUM
 
Chapter 2
byIIUM
 
Chapter 1
byIIUM
 
Kreydle internship-multimedia
byIIUM
 
03phpbldgblock
byIIUM
 
Chap2 practice key
byIIUM
 
Group p1
byIIUM
 
Tutorial import n auto pilot blogspot friendly seo
byIIUM
 
Visual sceneperception encycloperception-sage-oliva2009
byIIUM
 
03 the htm_lforms
byIIUM
 
Exercise on algo analysis answer
byIIUM
 
Redo midterm
byIIUM
 
Heaps
byIIUM
 
Report format
byIIUM
 
Edpuzzle guidelines
byIIUM
 
Final Exam Paper
byIIUM
 
Final Exam Paper
byIIUM
 
Group assignment 1 s21516
byIIUM
 
Avl tree-rotations
byIIUM
 
Week12 graph
byIIUM
 

Recently uploaded

PPTX
COMMUNICATION. pptx
byAneetaSharma15
 
PPTX
THERAPEUTIC COMMUNICATION for 2nd year GNM, 2ND YEAR P.B.B.SC NSG, 5TH SEM B....
byparmarjuli1412
 
PDF
PTE Answer Short Questions_ 50+ Most Repeated Questions & Smart Tips to Score...
byGurully
 
PDF
Creating Motion Graphics and Videos with Generative AI
byShalin Hai-Jew
 
PPTX
How to Set Up Default Header_Footer in Odoo 18.2
byCeline George
 
PPTX
Presentation1jdhdhhhjjjdbbdnjenmmen.pptx
bypgiopration
 
PDF
Plant Domestication | Complete Concept Explained BREEDING PLANT DOMESTICATION
bySatyam Sharma
 
PDF
Genetic Erosion in Crop Plants: Causes, Consequences, and Conservation Strate...
bySatyam Sharma
 
PDF
MS. LAPORE (QUIZ BOWL FILE 2025) . pdf
byjadepcuadra
 
PDF
BP303T PHARMACEUTICALMICROBIOLOGY UNIT 3
byRushiMandali
 
PDF
JRF Plant Science Syllabus | Complete Unit-Wise Discussion & Preparation Stra...
bySatyam Sharma
 
PPTX
GROWTH AND DEVELOPMENT..............pptx
byAneetaSharma15
 
PPTX
How to Manage Reconciliation of Draft Entries in Odoo 19
byCeline George
 
PDF
Energy Topics For All Student by LDM MIA
byLDMMIA, Reiki Yoga
 
PDF
BP605 T PHARMACEUTICAL BIOTECHNOLOGY UNIT 3 PART 1
byRushiMandali
 
PDF
how to write your research instrument.pdf
byThelma Villaflores
 
PPT
Layers of the Earth crust and Lithosphere.ppt
bybonpat1954
 
PDF
Hunwick's Roman Roads and Ridge Roads, a Discussion Document
byJohn Pallister
 
PDF
JRF Plant Science Preparation Strategy by Experts | Complete Syllabus Discuss...
bySatyam Sharma
 
PDF
Major Evolutionary Patterns in Crop Plants: Implications for Breeding and Div...
bySatyam Sharma
 
COMMUNICATION. pptx
byAneetaSharma15
 
THERAPEUTIC COMMUNICATION for 2nd year GNM, 2ND YEAR P.B.B.SC NSG, 5TH SEM B....
byparmarjuli1412
 
PTE Answer Short Questions_ 50+ Most Repeated Questions & Smart Tips to Score...
byGurully
 
Creating Motion Graphics and Videos with Generative AI
byShalin Hai-Jew
 
How to Set Up Default Header_Footer in Odoo 18.2
byCeline George
 
Presentation1jdhdhhhjjjdbbdnjenmmen.pptx
bypgiopration
 
Plant Domestication | Complete Concept Explained BREEDING PLANT DOMESTICATION
bySatyam Sharma
 
Genetic Erosion in Crop Plants: Causes, Consequences, and Conservation Strate...
bySatyam Sharma
 
MS. LAPORE (QUIZ BOWL FILE 2025) . pdf
byjadepcuadra
 
BP303T PHARMACEUTICALMICROBIOLOGY UNIT 3
byRushiMandali
 
JRF Plant Science Syllabus | Complete Unit-Wise Discussion & Preparation Stra...
bySatyam Sharma
 
GROWTH AND DEVELOPMENT..............pptx
byAneetaSharma15
 
How to Manage Reconciliation of Draft Entries in Odoo 19
byCeline George
 
Energy Topics For All Student by LDM MIA
byLDMMIA, Reiki Yoga
 
BP605 T PHARMACEUTICAL BIOTECHNOLOGY UNIT 3 PART 1
byRushiMandali
 
how to write your research instrument.pdf
byThelma Villaflores
 
Layers of the Earth crust and Lithosphere.ppt
bybonpat1954
 
Hunwick's Roman Roads and Ridge Roads, a Discussion Document
byJohn Pallister
 
JRF Plant Science Preparation Strategy by Experts | Complete Syllabus Discuss...
bySatyam Sharma
 
Major Evolutionary Patterns in Crop Plants: Implications for Breeding and Div...
bySatyam Sharma
 

Csc1401 lecture05 - cache memory

  • 1.
    Madam Raini Hassan Office:C5 - 23, Level 5, KICT Building Department: Computer Science Emails: hrai@iium.edu.my, hraini.iii@gmail.com 1Semester II 2014/2015
  • 2.
  • 3.
  • 4.
    Outline • Computer MemorySystem Overview Characteristics of Memory Systems The Memory Hierarchy • Cache Memory Principles • Elements of Cache Design Cache Addresses Cache Size Mapping Function Replacement Algorithms Write Policy Line Size Number of Caches • Pentium 4 Cache Organization Semester II 2014/2015 4
  • 5.
    Introduction • The complexsubject of computer memory is made more manageable if we classify memory systems according to their characteristics. Semester II 2014/2015 5
  • 6.
    Key Characteristics ofComputer Memory Systems Table 4.1 Key Characteristics of Computer Memory Systems Semester II 2014/2015 6
  • 7.
    7 1. Location • Refersto whether memory is internal and external to the computer • Internal memory is often equated with main memory • Processor requires its own local memory, in the form of registers • Cache is another form of internal memory • External memory consists of peripheral storage devices that are accessible to the processor via I/O controllers Semester II 2014/2015
  • 8.
    8 2. Capacity • Memoryis typically expressed in terms of bytes. • In other words, the capacity of a memory is the total number of bits that can be stored. • Word – A group of bits in memory that represents instructions or data. – The natural unit of organization (1 byte = 8 bits) – Common word lengths – 8, 16, 32 bits • Byte – The smallest unit of binary data is the bit and a collection of 8 bit is known as byte (1 byte = 8 bits) Semester II 2014/2015
  • 9.
    9 3. Unit ofTransfer • For internal memory (main memory), this is the number of bits read out of or written into memory at a time. • The unit of transfer need not equal a word on an addressable unit. • For external memory, data are often transferred in units larger than words; referred to as block. Semester II 2014/2015
  • 10.
    Sequential access Memory is organizedinto units of data called records Access must be made in a specific linear sequence Access time is variable Direct access Involves a shared read-write mechanism Individual blocks or records have a unique address based on physical location Access time is variable 4. Access Methods (1) Semester II 2014/2015 10
  • 11.
    Random access Each addressable locationin memory has a unique, physically wired-in addressing mechanism The time to access a given location is independent of the sequence of prior accesses and is constant Any location can be selected at random and directly addressed and accessed Main memory and some cache systems are random access Associative A word is retrieved based on a portion of its contents rather than its address Each location has its own addressing mechanism and retrieval time is constant independent of location or prior access patterns Cache memories may employ associative access 4. Access Methods (2) Semester II 2014/2015 11
  • 12.
    The two mostimportant characteristics of memory Three performance parameters are used: Access time (latency) • For random-access memory it is the time it takes to perform a read or write operation • For non-random-access memory it is the time it takes to position the read-write mechanism at the desired location Memory cycle time • Access time plus any additional time required before second access can commence. • Additional time may be required for transients to die out on signal lines or to regenerate data if they are read destructively. • Concerned with the system bus, not the processor. Transfer rate • The rate at which data can be transferred into or out of a memory unit • For random-access memory it is equal to 1/(cycle time) 5. Capacity and Performance Semester II 2014/2015 12
  • 13.
    13 6. Physical Types •Semiconductor – RAM • Magnetic surface memory – Disk & Tape • Optical – CD & DVD • Magneto-optical – Note book computer Semester II 2014/2015
  • 14.
    14 7. Physical Characteristics •Decay • Volatility – Information decays naturally or is lost when electrical power is switched off – Example; semiconductor memory • Non-volatile – Once recorded, information remains without deterioration until deliberately changed – No electrical power is needed to retain information – Example: Magnetic-surface memories and semiconductor memory • Erasable • Non-erasable – Cannot be altered, except by destroying the storage unit – Semiconductor memory of this type is known as read-only memory (ROM) • Power consumption Semester II 2014/2015
  • 15.
    15 8. Organization • Physicalarrangement of bits into words. Semester II 2014/2015
  • 16.
    Principle of Locality •Principle of locality (or locality of reference): • Program accesses a relatively small portion of the address space at any instant of time. • Temporal locality and spatial locality. Address Space 0 2 n - 1 Probability of reference Semester II 2014/2015 16
  • 17.
    Principle of Locality(2)  Temporal locality (locality in time):   Keep most recently accessed data items closer to the processor.  Spatial locality (locality in space):   Move blocks consisting of contiguous words to ‘upper’ levels.  Block is a unit of transfer. Semester II 2014/2015 17
  • 18.
    Principle of Locality(3) What programming constructs lead to principle of locality? Spatial Temporal Data arrays loop counters Code no branch/jump loop Semester II 2014/2015 18
  • 19.
    The Memory Hierarchy •Design constraints on a computer’s memory can be summed up by three questions: – How much, how fast, how expensive • There is a trade-off among capacity, access time, and cost – Faster access time, greater cost per bit – Greater capacity, smaller cost per bit – Greater capacity, slower access time • The way out of the memory dilemma is not to rely on a single memory component or technology, but to employ a memory hierarchy Semester II 2014/2015 19
  • 20.
    Memory Hierarchy –Basic Theoretical Diagram • Registers • L1 Cache • L2 Cache • Main memory • Disk cache • Disk • Optical • Tape Semester II 2014/2015 20
  • 21.
    Memory Hierarchy –Simplified “Real Life” Diagram Semester II 2014/2015 21
  • 22.
    Memory Hierarchy –Practical Diagram Semester II 2014/2015 22
  • 23.
    Memory Hierarchy –Current Control Data path ProcessorRegs Second- ary MemoryL2 Cache L1$ Main Memory Speed(ns): 0.5ns 2ns 6ns 100ns 10,000,000ns Size (MB): 0.0005 0.05 1-4 100-1000 100,000 Cost ($/MB): -- $100 $30 $1 $0.05 Technology: Regs SRAM SRAM DRAM Disk Semester II 2014/2015 23
  • 24.
    24 The 3 Parameters •Capacity, speed and cost increase moving from top to down. • First, access time get bigger; e.g.: CPU can be accessed in a few nanoseconds. • Second, the storage capacity increases as we go downwards. • CPU registers – around 128 bytes, caches – a few megabytes, main memory – thousands of megabytes, and magnetic disks – a few gigabytes. • Third, the number of bits per RM spent increases down the hierarchy. Semester II 2014/2015
  • 25.
    The Bottom Line •How much? – Capacity • How fast? – Time is money • How expensive? Semester II 2014/2015 25
  • 26.
    So you wantfast? • It is possible to build a computer which uses only static RAM (see later) • This would be very fast • This would need no cache – How can you cache? • This would cost a very large amount Semester II 2014/2015 26
  • 27.
    27 Cache Memory Principles •Small amount of fast memory • Sits between normal main memory and CPU • May be located on CPU chip or module Semester II 2014/2015
  • 28.
    Cache and MainMemory Semester II 2014/2015 28
  • 29.
    29 Other definitions ofCache 1. Cache memory is random access memory (RAM) that a computer microprocessor can access more quickly than it can access regular RAM. As the microprocessor processes data, it looks first in the cache memory and if it finds the data there (from a previous reading of data), it does not have to do the more time-consuming reading of data from larger memory. 2. A cache is a small capacity fast memory, too expensive to be used for the whole of RAM. It acts as an intermediate store between the CPU and main memory and is used to improve the overall speed of the computer since it is used primarily to keep the most active portions of the program being used. 3. A special, high-speed memory unit. 4. It is a temporary, very fast, digital storage for a central processor. Semester II 2014/2015
  • 30.
    30 Cache operation -overview • CPU requests contents of memory location • Check cache for this data • If present, get from cache (fast) • If not present, read required block from main memory to cache • Then deliver from cache to CPU • Cache includes tags to identify which block of main memory is in each cache slot Semester II 2014/2015
  • 31.
  • 32.
  • 33.
  • 34.
    Elements of CacheDesign Table 4.2 Elements of Cache Design Semester II 2014/2015 34
  • 35.
    + 1. Cache Addresses •Virtual memory – Facility that allows programs to address memory from a logical point of view, without regard to the amount of main memory physically available – When used, the address fields of machine instructions contain virtual addresses – For reads to and writes from main memory, a hardware memory management unit (MMU) translates each virtual address into a physical address in main memory Semester II 2014/2015 35
  • 36.
  • 37.
    37 2. Cache Size •Cost – More cache is expensive • Speed – More cache is faster – Checking cache for data takes time Semester II 2014/2015
  • 38.
    Table 4.3 Cache Sizes ofSome Processors a Two values separated by a slash refer to instruction and data caches. b Both caches are instruction only; no data caches.Semester II 2014/2015 38
  • 39.
    3. Mapping Function •Because there are fewer cache lines than main memory blocks, an algorithm is needed for mapping main memory blocks into cache lines • Three techniques can be used: 1. Direct 2. Associative 3. Set Associative Semester II 2014/2015 39
  • 40.
    40 3. Mapping Function(Example) • Cache of 64kByte • Cache block of 4 bytes – i.e. cache is 16k (214) lines of 4 bytes • 16MBytes main memory • 24 bit address – (224=16M) Semester II 2014/2015
  • 41.
    41 3. Mapping Function:Direct Mapping Direct Mapping • The simplest technique. • Each block of main memory maps to only one possible cache line – i.e. if a block is in cache, it must be in one specific place • Address is in two parts Semester II 2014/2015
  • 42.
    42 3. Mapping Function:Direct Mapping Direct Mapping • Least Significant w bits identify unique word • Most Significant s bits specify one memory block • The MSBs (Most Significant Bits) are split into a cache line field r and a tag of s-r (most significant) Semester II 2014/2015
  • 43.
  • 44.
    3. Mapping Function:Direct Mapping Cache Organization Semester II 2014/2015 44
  • 45.
  • 46.
    3. Mapping Function:Direct Mapping Summary • Address length = (s + w) bits • Number of addressable units = 2s+w words or bytes • Block size = line size = 2w words or bytes • Number of blocks in main memory = 2s+ w/2w = 2s • Number of lines in cache = m = 2r • Size of tag = (s – r) bits Semester II 2014/2015 46
  • 47.
    47 3. Mapping Function:Direct Mapping Pros & Cons • Simple • Inexpensive • Cons: Fixed location for given block – If a program accesses 2 blocks that map to the same line repeatedly, then the blocks will be continually swapped in the cache, caused the cache misses to be very high Semester II 2014/2015
  • 48.
    48 3. Mapping Function:Fully Associative Cache • To reduce the conflict misses of direct mapped caches without affecting its fast access time is to remember what was discarded in case it is needed again. • Since the discarded data has already been fetched, it can be used again at a small cost. • Such recycling is possible by using a victim cache, also known as fully associative cache. • Typical size is 4 to 16 cache lines • Residing between direct mapped L1 cache and the next level of memory Semester II 2014/2015
  • 49.
    3. Mapping Function:Fully Associative Cache Organization Semester II 2014/2015 49
  • 50.
    50 3. Mapping Function:Associative Associative Mapping • Permits each main memory block to be loaded into any line of the cache. • The cache control logic interprets a memory address simply as a Tag and a Word field. • Tag uniquely identifies block of memory. • To determine whether a block is in the cache, the cache control logic must simultaneously examine every line’s Tag for a match . • Cache searching gets expensive. Semester II 2014/2015
  • 51.
  • 52.
  • 53.
    3. Mapping Function:Associative Mapping Summary • Address length = (s + w) bits • Number of addressable units = 2s+w words or bytes • Block size = line size = 2w words or bytes • Number of blocks in main memory = 2s+ w/2w = 2s • Number of lines in cache = undetermined • Size of tag = s bits Semester II 2014/2015 53
  • 54.
    54 3. Mapping Function:Set-Associative Set-Associative Mapping • Compromise that exhibits the strengths of both the direct and associative approaches while reducing their disadvantages • Cache consists of a number of sets • Each set contains a number of lines • A given block maps to any line in a given set – Block B can be in any line of set i • e.g. 2 lines per set – 2 way associative mapping – A given block can be in one of 2 lines in only one set Semester II 2014/2015
  • 55.
    Mapping From Main Memory toCache: k-Way Set Associative Semester II 2014/2015 55
  • 56.
  • 57.
    3. Mapping Function:Set Associative Mapping Summary • Address length = (s + w) bits • Number of addressable units = 2s+w words or bytes • Block size = line size = 2w words or bytes • Number of blocks in main memory = 2s+w/2w=2s • Number of lines in set = k • Number of sets = v = 2d • Number of lines in cache = m = kv = k * 2d • Size of cache = k * 2d+w words or bytes • Size of tag = (s – d) bits Semester II 2014/2015 57
  • 58.
  • 59.
    3. Mapping Function:Varying Associativity Over Cache Size Semester II 2014/2015 59
  • 60.
    4. 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. Semester II 2014/2015 60
  • 61.
    61 4. Replacement Algorithms: Directmapping • No choice • Each block only maps to one line • Replace that line Semester II 2014/2015
  • 62.
    62 4. Replacement Algorithms: Associative& Set Associative • Hardware implemented algorithm (speed) 1. Least Recently used (LRU) 2. First in first out (FIFO) 3. Least frequently used 4. Random Semester II 2014/2015
  • 63.
    4. Replacement Algorithms: LRU Leastrecently 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 Semester II 2014/2015 63
  • 64.
    4. Replacement Algorithms: FIFO 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. Semester II 2014/2015 64
  • 65.
    4. Replacement Algorithms: LFU LeastFrequently Used (LFU) – Replace that block in the set that has experienced the fewest references – Could be implemented by associating a counter with each line Semester II 2014/2015 65
  • 66.
    When a blockthat is resident in the cache is to be replaced there are two cases to consider: 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 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 There are two problems to contend with: More than one device may have access to main memory 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 5. Write Policy Semester II 2014/2015 66
  • 67.
    5. Write Policy Inother words… • Must not overwrite a cache block unless main memory is up to date • Multiple CPUs may have individual caches • I/O may address main memory directly 2 methods of write policy are… Semester II 2014/2015 67
  • 68.
    5. Write Policy:Write Through 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 Semester II 2014/2015 68
  • 69.
    5. Write Policy:Write Back Write Back – Minimizes memory writes – Updates initially are made only in the cache – Update bit for cache slot is set when update occurs – If block is to be replaced, write to main memory only if update bit is set – Other caches get out of sync – Resulting 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 Semester II 2014/2015 69
  • 70.
    6. 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. • As the block size increases the hit ratio will at first increase because of the principle of locality. • As the block size increases more useful data are brought into the cache. • 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. Semester II 2014/2015 70
  • 71.
    6. Line Size •Two specific effects come into play: – 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 Semester II 2014/2015 71
  • 72.
    7. Number ofCaches • When caches were originally introduced, the typical system had a single cache. • More recently, the use of multiple caches has become the norm. Semester II 2014/2015 72
  • 73.
    7. Number ofCaches: 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 Semester II 2014/2015 73
  • 74.
    7. Number ofCaches: Multilevel Caches • 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 Semester II 2014/2015 74
  • 75.
    7. Number ofCaches: 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 Semester II 2014/2015 75
  • 76.
    7. Number ofCaches: Unified Versus Split Caches • 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 Semester II 2014/2015 76
  • 77.
    Pentium 4 CacheOrganization • The evolution of cache organization is seen clearly in the evolution of Intel microprocessors (Table 4.4) Semester II 2014/2015 77
  • 78.