Revision: 0

Created on: Sun, Feb 4, 2024

Department of Computer Science,
Last Update: Sun, Feb 4, 2024
Faculty of Mathematics and Natural Science

PART 2: The Computer System

Chapter 4 – Cache Memory (Part 1)
KOM120G – Organisasi dan Arsitektur Komputer
Pertemuan ke-3
HERU SUKOCO
Net Centric Computing (NCC) Laboratory
Email: hsrkom@{ipb.ac.id, apps.ipb.ac.id, gmail.com}
Website: http://www.herusukoco.web.id TEL./FAX.: +62-251-8625584
hsrkomote @hsrkom Mobile (+Whatsapp): +62 812 1979 7891
Inspiring Innovation with Integrity
in Agriculture, Ocean, and Biosciences for a Sustainable World
Readings
• William Stallings. (2016). “Computer Organization and
Architecture: Designing for Performance”. 10th Edition. Pearson-
Prentice Hall. ISBN: 9780134101613.
• Part 2 - Chapter 4

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 3

Additional Readings
Panduan Penggunaan Moodle sangat lengkap dan komprehensif
serta mudah dipahami dari UNSW Sydney karena disajikan dalam 2
bentuk, tulisan dan video. Semoga dapat melengkapi panduan
untuk pemanfaatan LMS IPB. Aamiin.

1. Lecture Recordings+ -> URL: https://teaching.unsw.edu.au/ETS

2. Moodle Support for Staff -> https://teaching.unsw.edu.au/moodle

Semoga bermanfaat.

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 4

Additional Materials
• All materials could find in this link:
• Introduction to Computer Organization and Architecture (COA)
• URL:
https://www.youtube.com/watch?v=Ol8D69VKX2k&list=PLBlnK6fEyqRgLLlzdgiTUKULKJPYc0
A4q&index=1
• Related additional materials on today’s lectures:
• Introduction to Cache Memory
• URL: https://www.youtube.com/watch?v=Ez_kyBS-y5w
• Direct Memory Mapping
• URL: https://www.youtube.com/watch?v=V_QS1HzJ8Bc
• Direct Memory Mapping – Solved Examples
• URL: https://www.youtube.com/watch?v=OxaYvJquPe0
• Associative Mapping
• URL: https://www.youtube.com/watch?v=uwnsMaH-iV0
• Set Associative Mapping
• URL: https://www.youtube.com/watch?v=KhAh6thw_TI

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 5

Objectives (Learning Outcomes)
After studying this chapter, you should be able to, students can
• Present an overview of the main characteristics of computer
memory systems and the use of a memory hierarchy.
• Describe the basic concepts and intent of cache memory.
• Discuss the key elements of cache design.
• Distinguish among direct mapping, associative mapping, and set-
associative mapping.
• Explain the reasons for using multiple levels of cache.
• Understand the performance implications of multiple levels of
memory.

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 6

Outline
PART 1:
• Chapter 4.1: Computer Memory System Overview
• Characteristics of Memory Systems
• The Memory Hierarchy
• Chapter 4.2: Cache Memory Principles

PART 2:
• Chapter 4.3: Elements of Cache Design
• Cache Addresses, Cache Size, Mapping Function Replacement Algorithms Write Policy, Line Size, and Number
of Caches
• Chapter 4.4: Pentium 4 Cache Organization
• Chapter 4.5: Key Terms, Review Questions, and Problems

Supplement: Appendix 4A Performance Characteristics of Two-Level Memories

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 7

 Department of Computer Science,
Faculty of Mathematics and Natural Science

Chapter 4.1
Computer Memory System Overview
Characteristics of memory systems and the memory
hierarchy

Inspiring Innovation with Integrity in Agriculture, Ocean, and Biosciences for a Sustainable World
Pendahuluan
• Konsep MEMORI tampaknya sederhana,

• Namun MEMORI menunjukkan jenis, teknologi, organisasi,

kinerja, dan biaya dibandingkan fitur apa pun dalam sistem
komputer.
• Tidak ada satupun teknologi yang optimal dalam memenuhi kebutuhan
memori untuk sistem komputer.
• Akibatnya, sistem komputer pada umumnya dilengkapi dengan hierarki sub-
sistem memori:
• internal (dapat diakses langsung oleh prosesor) dan
• eksternal (dapat diakses oleh prosesor melalui modul I/O).
Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 9
Karakteristik Sistem Memori
Subyek memori komputer yang kompleks menjadi lebih mudah
dikelola jika kita mengklasifikasikan sistem memori berdasarkan
karakteristik utamanya.
KARAKTERISIK:
• Location • Performance
• Capacity • Physical type
• Unit of transfer • Physical characteristics
• Access method • Organisation

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 10

 Inspiring Innovation with Integrity
in Agriculture, Ocean, and Biosciences for a Sustainable World

• CPU
• Internal
• External
Location
 Inspiring Innovation with Integrity
in Agriculture, Ocean, and Biosciences for a Sustainable World

• or Bytes
• Word size
Capacity

• Number of words
• The natural unit of organisation
 Unit of Transfer
• Internal
• Usually governed by data bus width
• External
• Usually, a block which is much larger than a word
in Agriculture, Ocean, and Biosciences for a Sustainable World

• Addressable unit
• Smallest location which can be uniquely addressed
Inspiring Innovation with Integrity

• Word internally
• Cluster on M$ disks
• Number of addresses = 2a, where a = # of address bits
 Access Methods (1)
— Sequential
— Start at the beginning and read through in order
— Access time depends on location of data and previous location
— e.g. tape
— Direct
in Agriculture, Ocean, and Biosciences for a Sustainable World

— Individual blocks have unique address

— Access is by jumping to vicinity plus sequential search
Inspiring Innovation with Integrity

— Access time depends on location and previous location

— e.g. disk
 Access Methods (2)
• Random
• Individual addresses identify locations exactly
• Access time is independent of location or previous access
• e.g. RAM
in Agriculture, Ocean, and Biosciences for a Sustainable World

• Associative
• Data is located by a comparison with contents of a portion of the store
Inspiring Innovation with Integrity

• Access time is independent of location or previous access

• e.g. cache
 Performance
• Access time
• Time between presenting the address and getting the valid data
• Memory Cycle time
• Time may be required for the memory to “recover” before next access
in Agriculture, Ocean, and Biosciences for a Sustainable World

• Cycle time is access + recovery

• Transfer Rate
Inspiring Innovation with Integrity

• Rate at which data can be moved

 Physical Types
• Semiconductor
• RAM
• Magnetic
• Disk & Tape
in Agriculture, Ocean, and Biosciences for a Sustainable World

• Optical
• CD & DVD
Inspiring Innovation with Integrity

• Others
• Bubble
• Hologram
 Inspiring Innovation with Integrity
in Agriculture, Ocean, and Biosciences for a Sustainable World

• Decay
• Volatility
• Erasable
• Power consumption
Physical Characteristics
 Inspiring Innovation with Integrity
in Agriculture, Ocean, and Biosciences for a Sustainable World

• e.g. interleaved
• Not always obvious
Organisation
• Physical arrangement of bits into words
 The Bottom Line - Constraints
• How much?
• Capacity
• How fast?
• Time is money
in Agriculture, Ocean, and Biosciences for a Sustainable World

• How expensive?
• Cost
Inspiring Innovation with Integrity

• Choose 2 out of 3
 Memory Hierarchy
• Registers
• In CPU
• Internal or Main memory
• May include one or more levels of cache
in Agriculture, Ocean, and Biosciences for a Sustainable World

• “RAM”
• External memory
Inspiring Innovation with Integrity

• Backing store
 Memory Hierarchy
• List: — Decreasing cost per bit
• Registers
— Increasing capacity
• L1 Cache
— Increasing access time
• L2 Cache
in Agriculture, Ocean, and Biosciences for a Sustainable World

— Decreasing frequency
• Main memory
• Disk cache of access
Inspiring Innovation with Integrity

• Disk
• Optical
• Tape
 Locality of Reference
• During the course of the execution of a program, memory
references tend to cluster
• e.g. loops
in Agriculture, Ocean, and Biosciences for a Sustainable World
Inspiring Innovation with Integrity
 Department of Computer Science,
Faculty of Mathematics and Natural Science

Chapter 4.2
Cache Memory Principles
Principles of cache memory

Inspiring Innovation with Integrity in Agriculture, Ocean, and Biosciences for a Sustainable World
 CACHE MEMORY Organization
Total instruksi = 100
Source: NESO Academy

80 instruksi

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 25

 CACHE MEMORY Organization
Source: NESO Academy
Total of instructions = 100

RAM: 80 instructions

Only 100 instructions!

Seems handleable!

Q: Mengapa kita tidak letakkan semua instruksi di RAM (MM)?

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 26

Typical CACHE Organization

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 27

Cache Read Operation

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 28

Cache Memory Principles:
Cache and Main Memory

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 29

 Imagine when you are playing GAMES!

Source: NESO Academy

Recommended
Senin, 5RAM: 4GB
Feb 2024 Recommended RAM: 8GB Recommended
KOM120G RAM: 8GB
- Organisasi dan Arsitektur Komputer Recommended RAM: 16GB
30
 Cache
• Small amount of fast memory
• Sits between normal main memory and CPU
• May be located on CPU chip or module
in Agriculture, Ocean, and Biosciences for a Sustainable World
Inspiring Innovation with Integrity
 How much improvement?
• A processor has two level memory access
• A word to be processed must be in level 1
• Suppose level 1 contains 1.000 words, has an access time of 0.01
μs; level 2 contains 100.000 words has an access time of 0.1 μs
in Agriculture, Ocean, and Biosciences for a Sustainable World

• Suppose 95% of the memory access found in level 1 then average

time to access a word is:
Inspiring Innovation with Integrity

(.95)(.01 μs) + (.05)(.01 μs +.1 μs)

= .095 μs + .0055 μs = .015 μs
Cache/Main Memory Structure
 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
in Agriculture, Ocean, and Biosciences for a Sustainable World

• Then deliver from cache to CPU

Inspiring Innovation with Integrity

• Cache includes tags to identify which block of main memory is in

each cache slot
 Inspiring Innovation with Integrity
in Agriculture, Ocean, and Biosciences for a Sustainable World

Cache Read Operation - Flowchart

References
William Stallings. (2016). “Computer Organization and Architecture: Designing
for Performance”. 10th Edition. Pearson-Prentice Hall. ISBN:
9780134101613.
NASO Academy. May 14, 2021. Computer Organization & Architecture (COA):
Introduction to Cache Memory. Online: YouTube. Access Time on YouTube
on Sun, Feb 5, 2024. URL: https://www.youtube.com/watch?v=Ez_kyBS-
y5w

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 36

 G1 ü G1 ü
1
3 7 2
2 4
2 3
4 2
1
1 5 2
5 3 3 G1 ü
2 4 8
1
S 1 1 4
3 G1 ü
5 4
2
2 4

Discussion 1 2
3
1
3
1
6 3
4 G2
3 G3
G3

Senin, 5 Feb 2024 KOM120G - Organisasi dan Arsitektur Komputer 37