Chapter 12 Memory Organization

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Chapter 12::

Chapter 12: Memory Organization 4343 - Computer Organization & Design

Memory Hierarchy:

1 / 19 Memory Hierarchy Main Memory RAM Volatile, unless backed up with battery Stores active programs and data Communicates directly with the CPU Auxiliary Memory Magnetic (disks & tapes) Non volatile Saves files (programs & data) Communicates with the CPU through a controller

Memory Hierarchy:

2 / 19 Memory Hierarchy CPU Cache Main Memory I/O Processor Magnetic Disks Magnetic Tapes

Cache Memory:

3 / 19 Cache Memory High speed (towards CPU speed) Small size (power & cost) CPU Cache (Fast)  Cache Main Memory (Slow)  Mem Hit Miss 95% hit ratio  Access = 0.95  Cache + 0.05  Mem

Cache Memory:

4 / 19 Cache Memory CPU Cache 1 Mword Main Memory 1 Gword 30-bit Address Only 20 bits !!!

Cache Memory:

5 / 19 Cache Memory Cache Main Memory 00000000 00000001 • • • • • • • • • • 3FFFFFFF 00000 00001 • • • • FFFFF Address Mapping !!!

Associative Memory:

6 / 19 Associative Memory Cache 00000 00001 • • • • FFFFF Main Memory 00000000 00000001 • • 00012000 • • 08000000 • • 15000000 • 3FFFFFFF 00012000 15000000 08000000 Address (Key) Data Cache Location

Associative Mapping:

7 / 19 Associative Mapping Cache 0 1 A 6 4 7 C C 0 0 0 5 00012000 15000000 08000000 00012000 30 Bits (Key) 16 Bits (Data) 0 1 A 6 Data Address Can have any number of locations How many comparators?

Direct Mapping:

8 / 19 Direct Mapping Cache 0 1 A 6 4 7 C C 0 0 0 5 000 150 080 00500 01400 00900 000 00500 Address 000 Tag 0 1 A 6 Data Compare Match No match 10 Bits (Tag) 16 Bits (Data) 00000 FFFFF 20 Bits (Addr) What happens when Address = 100 00500

Direct Mapping with Blocks:

9 / 19 Direct Mapping with Blocks Cache 0 1 A 6 0 2 5 4 4 7 C C A 0 B 4 0 0 0 5 5 C 0 4 000 150 080 00500 00501 • 01400 01401 • 00900 00901 • 000 0050 0 Address 000 Tag 0 1 A 6 Data Compare Match No match 10 Bits (Tag) 16 Bits (Data) FFFFF 20 Bits (Addr) 00000 Block Size = 16

Set-Associative Mapping:

10 / 19 Set-Associative Mapping Cache 0 1 A 6 4 7 C C 0 0 0 5 000 150 080 00500 01400 00900 000 00500 Address 000 Tag1 0 1 A 6 Data1 Compare Match 10 Bits (Tag) 16 Bits (Data) 00000 FFFFF 20 Bits (Addr) 0 7 2 1 0 8 2 2 0 9 0 9 010 000 000 010 Tag2 0 7 2 1 Data2 Compare 10 Bits (Tag) 16 Bits (Data) 2-Way Set Associative No match

Replacement Algorithms:

11 / 19 Replacement Algorithms For Associative & Set-Associative Cache Which location should be emptied when the cache is full and a miss occurs? F irst I n F irst O ut ( FIFO ) L east R ecently U sed ( LRU ) Distinguish an Empty location from a Full one Valid Bit

Replacement Algorithms:

12 / 19 Replacement Algorithms CPU Reference A B C A D E A D C F Miss Miss Miss Hit Miss Miss Miss Hit Hit Miss Cache FIFO  A A B A B C A B C A B C D E B C D E A C D E A C D E A C D E A F D Hit Ratio = 3 / 10 = 0.3

Replacement Algorithms:

13 / 19 Replacement Algorithms CPU Reference A B C A D E A D C F Miss Miss Miss Hit Miss Miss Hit Hit Hit Miss Cache LRU  A B A C B A A C B D A C B E D A C A E D C D A E C C D A E F C D A Hit Ratio = 4 / 10 = 0.4

Writing Policy:

14 / 19 Writing Policy Read Operations Main memory and cache have duplicate data values Write Operations If the CPU writes to the cache only ( fast ), then the main memory will have a different copy . At some time (before emptying the cache) “ Write Back ” the new value to the main memory. Mark the altered data location in cache with Dirty Bit “ Write Through ” to both the cache and the main memory ( slow ) then data is always consistent .

Homework:

15 / 19 Homework Chapter 12 12-15 12-16 12-17 12-18

Homework:

16 / 19 Homework Mano 12-15 A two-way set associative cache memory uses blocks of four words. The cache can accommodate a total of 2048 words from main memory. The main memory size is 128K x 32. a. Formulate all pertinent information required to construct the cache memory? b. What is the size of the cache memory?

Homework:

17 / 19 Homework 12-16 The access time of a cache memory is 100 ns and that of main memory 1000 ns. It is estimated that 80 percent of the memory requests are for read and the remaining 20 percent for write. The hit ratio for read accesses only is 0.9. A write-through procedure is used. a. What is the average access time for the system considering only memory read cycles? b. What is the average access time of the system for both read and write requests? c. What is the hit ratio taking into consideration the write cycles?

Homework:

18 / 19 Homework 12-17 A four-way set-associative cache memory has four words in each set. A replacement procedure based on the least recently used (LRU) algorithm is implemented by means of 2-bit counters associated with each word in the set. A value in the range 0 to 3 is thus recorded for each word. When a hit occurs, the counter associated with the referenced word is set to 0, those counters with values originally lower than the referenced one are incremented by 1, and all others remain unchanged. If a miss occurs, the word with counter value 3 is removed, the new word is put in its place, and its counter is set to 0. The other three counters are incremented by 1. Show that this procedure works for the following sequence of word reference: A, B, C, D, B, E, D, A, C, E, C, E. (Start with A, B, C, D as the initial four words with word A being the least recently used.)

Homework:

19 / 19 Homework 12-18 A digital computer has a memory unit of 64K x 16 and a cache memory of 1K words. The cache uses direct mapping with a block size of four words. a. How many bits are there in the tag, index, block, and word fields of the address format? b. How many bits are there in each word of cache, and how are they divided into functions? Include a valid bit. c. How many blocks can the cache accommodate?