Chapter 9
Memory Organization
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Chapter Outline
• Hierarchical Memory Systems
• Cache Memory
• Virtual Memory
• Pentium/Windows Memory System
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Memory Hierarchy
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Associative Memory
• Data Register
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Associative Memory
• Data Register
• Mask Register
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Associative Memory
• Data Register
• Mask Register
• Match Register
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Associative Memory
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Associative Cache
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Data Lines/Blocks
• Multiple consecutive words form a line
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Data Lines/Blocks
• Multiple consecutive words form a line
• All data in a line is moved together
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Data Lines/Blocks
• Multiple consecutive words form a line
• All data in a line is moved together
• Takes advantage of locality of reference
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Associative Cache with a Line
Size of 4 Bytes
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Direct Mapped Cache
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Direct Mapped Cache with a
Line Size of 4 Bytes
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Drawbacks of Direct Mapped
Cache
0000 0000 0000 0000: JUMP 1000H
0001 0000 0000 0000: JUMP 0000H
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Set-Associative Cache
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Set-Associative Cache with a
Line Size of 4 Bytes
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Data Replacement Policies
• FIFO
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Data Replacement Policies
• FIFO
• LRU
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Data Replacement Policies
• FIFO
• LRU
• Random
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Example
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Example
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Example
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Example
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Writing Data to Cache
• Write back
• Write through
• Write allocate
• Write no-allocate
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Cache Performance
• Hits and misses
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Cache Performance
• Hits and misses
• Hit ratio
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Cache Performance
• Hits and misses
• Hit ratio
• Average memory access time
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Cache Activity - Associative
Cache
A 0 B0 C2 A 0 D1B0 E 4 F5 A 0 C2 D1B0 G 3C2 H 7 I6 A 0 B0
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Cache Activity - Associative
Cache
A 0 B0 C2 A 0 D1B0 E 4 F5 A 0 C2 D1B0 G 3C2 H 7 I6 A 0 B0
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Cache Activity - Direct
Mapped Cache
A 0 B0 C2 A 0 D1B0 E 4 F5 A 0 C2 D1B0 G 3C2 H 7 I6 A 0 B0
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Cache Activity - Direct
Mapped Cache
A 0 B0 C2 A 0 D1B0 E 4 F5 A 0 C2 D1B0 G 3C2 H 7 I6 A 0 B0
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Cache Activity - 2-Way Set-
Associative Cache
A 0 B0 C2 A 0 D1B0 E 4 F5 A 0 C2 D1B0 G 3C2 H 7 I6 A 0 B0
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Cache Activity - 2-Way Set-
Associative Cache
A 0 B0 C2 A 0 D1B0 E 4 F5 A 0 C2 D1B0 G 3C2 H 7 I6 A 0 B0
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
2-Way Set-Associative Cache
with a Line Size of 2
A 0 B0 C2 A 0 D1B0 E 4 F5 A 0 C2 D1B0 G 3C2 H 7 I6 A 0 B0
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
2-Way Set-Associative Cache
with a Line Size of 2
A 0 B0 C2 A 0 D1B0 E 4 F5 A 0 C2 D1B0 G 3C2 H 7 I6 A 0 B0
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Virtual Memory
• Memory Management Unit (MMU)
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Virtual Memory
• Memory Management Unit (MMU)
• Swap disk/file
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Virtual Memory
• Memory Management Unit (MMU)
• Swap disk/file
• Logical address
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Virtual Memory
• Memory Management Unit (MMU)
• Swap disk/file
• Logical address
• Physical address
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Paging - Pages and Frames
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
MMU Configuration
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Page Table
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Address Conversion
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Translation Lookaside Buffer
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Example
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Example
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Segmentation
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Fragmentation
• Internal fragmentation
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Fragmentation
• Internal fragmentation
• External fragmentation
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Fragmentation
• Internal fragmentation
• External fragmentation
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Beyond the Basics
• Split cache
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Beyond the Basics
• Split cache
• Multilevel page table
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Multilevel Page Table
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Pentium/Windows NT Memory
Management
8 KB
8 KB
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Pentium/Windows NT Cache
Memory Management
• 16KB L1 split cache
– 2-way set-associative
– Line size of 32 bytes
• TLB used for cache and virtual memory
• Pseudo-LRU replacement policy
• 256K L2 unified cache
– 4-way set-associative
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Pentium/Windows NT Virtual
Memory Management
• 4 GB address space
– Low-order 2 GB for individual processes
– High-order 2 GB for Windows NT
components
• Uses paging, not segmentation
• 10-bit page directory pointer + 10-bit
offset
• Uses the same TLBs as cache memory
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001
Summary
• Hierarchical Memory Systems
• Cache Memory
• Virtual Memory
• Pentium/Windows Memory System
Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001