Orkom Cache Memory

Cache Memory Maria Susan Anggreainy, M.Kom

09/03/2008

Maria Susan Anggreainy, M.Kom

1

Characteristics „ „ „ „ „ „ „ „ 09/03/2008

Location Capacity Unit of transfer Access method Performance Physical type Physical characteristics Organisation Maria Susan Anggreainy, M.Kom

2

Location „ „

„

09/03/2008

CPU Æ register Internal Æ Main Memory (memori utama) External Æ Compact disk, tape

Maria Susan Anggreainy, M.Kom

3

Capacity „

Word size z

„

Number of words z

„

09/03/2008

or Bytes

Bagi internal memory umumnya dalam satuan Byte atau Word. z

„

The natural unit of organisation

Panjang Word yang umum adalah 8,16 dan 32 bit.

Bagi eksternal mememory umumnya adalam satuan Byte Maria Susan Anggreainy, M.Kom

4

Unit of Transfer „

Internal z

„

External z

„

Usually governed by data bus width, biasanya sama dengan panjang Word (panjang Instruksi). Usually a block which is much larger than a word

Addressable unit Smallest location which can be uniquely addressed z Word internally z

09/03/2008

Maria Susan Anggreainy, M.Kom

5

Access Methods (1) „

Sequential z

z z

z

„

Direct z z

z

z 09/03/2008

Memory diorganisasikan menjadi unitunit data yang disebut Record. Start at the beginning and read through in order Access time depends on location of data and previous location e.g. tape Individual blocks have unique address Access is by jumping to general vicinity (kisaran umum) plus sequential search Access time depends on location and previous location e.g. disk Maria Susan Anggreainy, M.Kom

6

Access Methods (2) „

Random z

z

z

„

Individual addresses identify locations exactly Access time is independent of location or previous access e.g. RAM

Associative z z

z 09/03/2008

z

Mirip Random Access Data is located by a comparison with contents of a portion of the store Access time is independent of location or previous access Maria Susan Anggreainy, M.Kom e.g. cache

7

Performance „

Access time z

„

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 z Cycle time is access + recovery z

„

Transfer Rate z

09/03/2008

Rate at which data can be moved Maria Susan Anggreainy, M.Kom

8

„

dimana TN = waktu rata-rata untuk membaca atau menulis N bit z TA = waktu akses rata-rata z N = jumlah bit z R =kecepatan transfer, dalam bit per detik(bps) z

09/03/2008

Maria Susan Anggreainy, M.Kom

9

Physical Types „

Semiconductor (dengan teknologi LSI atau VLSI) z

„

Magnetic z

„

Disk & Tape

Optical z

„

RAM

CD & DVD

Others Bubble z Hologram z

09/03/2008

Maria Susan Anggreainy, M.Kom

10

Physical Characteristics „

„

„ „

09/03/2008

Decay (apakah perlu direfresh terus menerus ?) Volatility (apakah isinya hilang ketika power tidak ada?) Erasable Power consumption

Maria Susan Anggreainy, M.Kom

11

Organisation „

09/03/2008

Physical arrangement of bits into words

Maria Susan Anggreainy, M.Kom

12

Memory Hierarchy „

Registers z

„

In CPU

Internal or Main memory May include one or more levels of cache z “RAM” z

„

External memory z

09/03/2008

Backing store Maria Susan Anggreainy, M.Kom

13

Memory Hierarchy - Diagram

09/03/2008

Maria Susan Anggreainy, M.Kom

14

Semakin menurun, semakin…: „ „ „

09/03/2008

Murah rasio harga/bit-nya Besar kapasitasnya lambat

Maria Susan Anggreainy, M.Kom

15

The Bottom Line „

How much? z

„

How fast? z

„

09/03/2008

Capacity Time is money

How expensive?

Maria Susan Anggreainy, M.Kom

16

Hierarchy List „ „ „ „ „ „ „ „ 09/03/2008

Registers L1 Cache L2 Cache Main memory Disk cache Disk Optical Tape Maria Susan Anggreainy, M.Kom

17

Cache „ „

„

09/03/2008

Small amount of fast memory Sits between normal main memory and CPU May be located on CPU chip or module

Maria Susan Anggreainy, M.Kom

18

Cache operation - overview „

„ „ „

„ „

09/03/2008

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 Maria Susan Anggreainy, M.Kom

19

09/03/2008

Maria Susan Anggreainy, M.Kom

20

Cache Design „ „ „ „ „ „

09/03/2008

Size Mapping Function Replacement Algorithm Write Policy Block Size Number of Caches

Maria Susan Anggreainy, M.Kom

21

Size does matter „

Cost z

„

More cache is expensive

Speed More cache is faster (up to a point) z Checking cache for data takes time z

09/03/2008

Maria Susan Anggreainy, M.Kom

22

Typical Cache Organization

09/03/2008

Maria Susan Anggreainy, M.Kom

23

Mapping Function „ „ „

09/03/2008

Direct Mapping Associative Mapping Set Associative Mapping

Maria Susan Anggreainy, M.Kom

24

Direct Mapping „

Each block of main memory maps to only one cache line z

09/03/2008

i.e. if a block is in cache, it must be in one specific place

Maria Susan Anggreainy, M.Kom

25

Direct Mapping pros & cons „ „ „

Simple Inexpensive Fixed location for given block z

09/03/2008

If a program accesses 2 blocks that map to the same line repeatedly, cache misses are very high

Maria Susan Anggreainy, M.Kom

26

Associative Mapping „

09/03/2008

A main memory block can load into any line of cache

Maria Susan Anggreainy, M.Kom

27

Set Associative Mapping „

„ „

Cache is divided into a number of sets Each set contains a number of lines A given block maps to any line in a given set z

„

e.g. 2 lines per set z z

09/03/2008

e.g. Block B can be in any line of set i 2 way associative mapping A given block can be in one of 2 lines in only one set Maria Susan Anggreainy, M.Kom

28

Replacement Algorithms (1) Direct mapping „ „

„

09/03/2008

No choice Each block only maps to one line Replace that line

Maria Susan Anggreainy, M.Kom

29

Replacement Algorithms (2) Associative & Set Associative „ „ „

Hardware implemented algorithm (speed) Least Recently used (LRU) e.g. in 2 way set associative z

„

First in first out (FIFO) z

„ „

replace block that has been in cache longest

Least frequently used z

09/03/2008

Which of the 2 block is lru?

replace block which has had fewest hits

Random

Maria Susan Anggreainy, M.Kom

30

Write Policy „

„

„

09/03/2008

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

Maria Susan Anggreainy, M.Kom

31

Write through „

„

„ „

„ 09/03/2008

All writes go to main memory as well as cache Multiple CPUs can monitor main memory traffic to keep local (to CPU) cache up to date Lots of traffic Slows down writes Remember bogus write through caches! Maria Susan Anggreainy, M.Kom

32

Write back „ „

„

„ „

„ 09/03/2008

Updates initially made in cache only 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 I/O must access main memory through cache N.B. 15% of memory references are writes Maria Susan Anggreainy, M.Kom

33

Pentium 4 Cache „ „

„

80386 – no on chip cache 80486 – 8k using 16 byte lines and four way set associative organization Pentium (all versions) – two on chip L1 caches z

„

Pentium 4 – L1 caches z z z

„

8k bytes 64 byte lines four way set associative

L2 cache z z z

09/03/2008

Data & instructions

z

Feeding both L1 caches 256k 128 byte lines 8 way set associative Maria Susan Anggreainy, M.Kom

34

Power PC Cache Organization „

„

„ „ „

601 – single 32kb 8 way set associative 603 – 16kb (2 x 8kb) two way set associative 604 – 32kb 610 – 64kb G3 & G4 z

64kb L1 cache „

z 09/03/2008

8 way set associative

256k, 512k or 1M L2 cache „

Maria Susan Anggreainy, M.Kom

two way set associative

35

Comparison of Cache Sizes

09/03/2008

Maria Susan Anggreainy, M.Kom

36