1
e-journal Teknik Elektro dan Komputer (2013), ISSN 2301-8402
ORGANISASI CACHE MEMORY Arie S. M. Lumenta. Jurusan Teknik Elektro-FT UNSRAT, Manado-95115, Email:
[email protected]
utama. Selanjutnya akan dibahas mengenai organisasi cache memory untuk meningkatkan kinerja suatu sistem komputer secara keseluruhan, terutama memperpendek waktu akses prosessor ke memory utama. Termasuk didalamnya pembahasan tentang beberapa aspek penting dalam pengorganisasian suatu cache dan beberapa hal penting dalam disain rancangan cache memory serta hal-hal yang mempengaruhi performa suatu cache memory.
Abstrak Cache memory dirancang secara umum untuk meningkatkan kinerja suatu sistem komputer. Secara logika cache memory berada diantara prosessor dan memory utama yang bertujuan untuk menyediakan data atau instruksi yang akan diolah oleh prosessor. Hal ini menyebabkan waktu yang dibutuhkan menjadi lebih singkat karena prosessor tidak perlu mengambilnya dari memori utama. Terdapat beberapa metode pemetaan memory utama kepada cache memory yakni pemetaan langsung, cache assosiative, set assosiative dan sector caches. Dalam makalah ini akan dibahas tentang metode pemetaan tersebut. Juga akan dibahas tentang parameter-parameter disain suatu cache memory serta tentang performance suatu cache memory. Kata kunci : cache memory, block, direct mapping, assosiative cache, hit ratio, cycle counts
2. Definisi Cache Memori Dalam hirarki memori posisi cache memory adalah satu level dibawah register seperti tampak pada Gambar 1 berikut.
Register Cache Memori
1. Pendahuluan
Memori Utama
Idealnya sebuah prosessor tidak membuang waktu untuk mengakses instruksi dan data dari memori utama. Sistem memori utama dituntut untuk secepat mungkin menyediakan sebuah operand bagi prosessor disertai dengan kemampuan menyediakan sejumlah data sebanyak yang dapat disediakan per satuan waktu. Semakin cepat prosessor mengolah data, maka semakin sulit bagi sistem memori utama untuk mensuplai operand dalam satu atau dua siklus. Oleh sebab itu diperlukan suatu cara untuk mempercepat waktu akses prosessor ke memori utama Untuk meningkatkan kecepatan dalam hal menyediakan data dan intstruksi bagi prosessor, memori utama dibatasasi oleh batasan rancangan elektronik dan masalah packaging. Karena itu perlu dicari solusi lain untuk menangani masalah tersebut. Salah satu cara yang digunakan adalah dengan membuat suatu memori cache yang menyimpan data atau instruksi terbaru dari memori utama dalam bentuk word-word yang dapat mempercepat akses prosessor ke memori
Memori Sekunder
Gambar 1. Hirarki Memori PengGambaran tersebut menunjukkan bahwa semakin keatas ukuran semakin kecil dan kecepatan semakin cepat serta harga semakin mahal. Sebaliknya, dari atas kebawah ukuran semakin besar dan kecepatan makin lambat serta harga makin murah. Cache memory adalah memori berukuran kecil, buffer memori berkecepatan tinggi yang digunakan komputer untuk menampung sebagian isi memori utama yang sedang digunakan [Smith, 1982]. 3. Organisasi Cache Memory Secara logika cache memory berada diantara CPU dan memori utama. Ada dua sistem organisasi untuk cache memori seperti ditunjukkan pada Gambar 2.
1
2
e-journal Teknik Elektro dan Komputer (2013), ISSN 2301-8402
Secara prinsip komponen sebuah cache ditunjukkan seperti pada Gambar 3. Memory word disimpan didalam sebuah cache data memory dan dikelompokkan menjadi halamanhalaman kecil yang disebut blok-blok cache atau lines. Isi dari cache data memory adalah copy dari satu set blok memory utama.
Cache M1 CPU Cache access
Block replacement
PA First level D - Cache
VA
PA
PA
MMU
Second level D - Cache
D
D
Main memory
D
PA CPU
I - Cache
I
I
(b) Cache terpisah yang diakses dengan alamat fisik Gamabar 3. Model pengalamatan fisik sebuah cache memory (Hwang, 1993)
Main memory M2
sedangkan pengalamatan virtual adalah ketika sebuah cache di-index dengan sebuah alamat virtual seperti Gambar 4:
Main memory access Captions : MMU
VA
PA
VA = Virtual Address
Sytem bus
Main memory
CPU
(a) look-aside
PA = Phisical Address I = Instructions D = Data Stream
Cache
I or D
D or I
(a) Cache yang diakses dengan alamat virtual.
Cache M1
Cache access
Block placement 32 I - Cache (4K Bytes)
Main memory M2
Main memory controller
Cache controller
CPU
I
I
Main memory access
D
32
IU
MMU
PA
32
Main memory
I
32
FU VA D - Cache (8K Bytes)
128
(b) look-through cache
4. Direct Mapping dan Associative Caches Perpindahan informasi dari memori utama ke cache memory diatur dalam unit-unit blok cache atau jalur cache [Hwang, 1993]. Direct mapping atau pemetaan langsung adalah teknik pemetaan alamat cache memory yang relative sederhana. Blok dalam cache yang disebut block frames dihubungkan dengan block dalam memory
Captions :
MMU
PA Cache D or I
CPU
128
(b) Sebuah cache terpisah yang diakses oleeh alamat virtual Gambar 4. Model pengalamatan virtual sebuah cache.
Cache memory memiliki dua jenis pengalamatan yaitu secara fisik dan secara virtual. Pengalamatan secara fisik adalah ketika sebuah cache diakses dengan sebuah alamat fisik memory, seperti pada Gambar 3 dibawah: PA
D
D
Dua sistem organisasi memori (Hayes, 1998)
VA
32
32
Sytem bus
Gambar 2.
64
VA
Main memory
VA = Virtual Address PA = Phisical Address I = Instructions D = Data Stream
I or D
utama. Dimisalkan block frames adalah Bi untuk i=0,1,2,3,…,m dan block dalam memory utama adalah Bj dengan j=0,1,2,3,…n. Dengan direct mapping tiap block {Bj} dipetakan
(a) Cache yang diakses dengan alamat fisik.
2
3
e-journal Teknik Elektro dan Komputer (2013), ISSN 2301-8402
langsung
dengan
block
Alamat memory dibagi menjadi tiga bagian yaitu: lower (w) bits sebagai word offset dalam block, upper (s) bits yang merupakan blok alamat di memory utama dengan leftmost (s-r) bits sebagai tag untuk dicocokan dan block (r) bits yang biasanya digunakan untuk mengimplementasikan modulo-m untuk penempatan isi block memory utama ke dalam block cache, dimana m=2r. Hit cache terjadi ketika dua tag sesuai, sebaliknya jika tidak maka yang terjadi adalah miss cache. Ketika terjadi miss seluruh alamat memori (s+w bits) digunakan untuk mengakses memori utama. Organisasi assosiative cache menawarkan fleksibilitas yang tinggi dalam pemetaan block cache seperti tampak pada Gambar 7.
{ Bi }.
frame
Diasumsikan pula bahwa n>>m, n=2s dan m=2r. Tiap block atau block frame diasumsikan memiliki b words, dimana b=2w mengakibatkan cache berisi m.b=2r+w words dan main memory memiliki n.b=2s+w words yang dialamati oleh (s+w) bits. Ketika block frame dibagi menjadi v=2t himpunan, maka block untuk tiap himpunan adalah k=m/v=2r-t. Organisasi direct mapping cache seperti yang diGambarkan pada Gambar 5, didasarkan pada sebuah pemetaan langsung oleh n/m=2s-r block memory yang dipisahkan dengan jarak yang sama ke satu block frame dalam cache. Pemetaan block Bj ke block frame Bi mengikuti aturan: Bj → Bi jika i=j (modulo m) Organisasi direct mapping ini sangat kaku tetapi merupakan organisasi cache memory yang paling sederhana yang dapat diimplementasikan.
B0 B1 B2 Cache Tag 4 bits
(Block frames) B0
B3 B4
Main memory
B5
B0
B6
B1
B1
B2
B7
Cache
B8
B3
(Block frames)
Tag 2 bits
Main memory
B4
B0
B9
B5
B2
B11
B6 B1
B10
B7
B12
B8
B13 B3
B2
B9
B14
B10
B15
B11 B12
Gambar 7.
B13
Organisasi assosiative cache
B3
B14
Pada asssosiative cache tiap block dalam memory utama dapat ditempatkan di block frame mana saja yang tersedia. Pemetaan assosiative memberikan kebebasan penuh untuk memilih lokasi cache sebagai tempat pemetaan isi blok memori. Hal ini mengakibatkan ruang dalam cache dapat digunakan lebih efisien.
B15
Gambar 5.
Organisasi cache dengan deirct mapping.
Untuk direct mapping dengan kasus dimana tiap block mengandung 2 words (w=2 bits), pengalamatan memorynya tampak pada Gambar 6 dibawah :
5. Set-Assosiative dan Sector Caches. memory Tag
Block
Main memory
s+w
address
Tag
Word
Cache
W0 W1
Data Data Data
s-r
r
W2 B0
Set assosiative adalah kombinasi teknik direct mapping dan assosiative cache. Pada metode ini block cache dikelompokkan ke dalam set, dan aturan pemetaan memungkinkan blok memori utama untuk berada dalam block set tertentu. Pada k-way assosiative cache, m cache block frames dibagi menjadi v=m/k sets, dimana k adalah block per set. Tiap set diidentifikasi dengan d-bit set bilangan, dimana 2d=v. Tag block cache selanjutnya direduksi menjadi s-d bits. Dalam praktek, ukuran set k biasanya
B0
W3
Data
w
s-r
Data Compare
w
X (hit in cache)
Data Data Data
Bj
(block frames)
s
X w
W4j W(4j+1) W(4j+2) W(4j+3)
Bj
(miss in cache)
Gambar 6.
Pengalamatan cache/memory
3
4
e-journal Teknik Elektro dan Komputer (2013), ISSN 2301-8402
adalah bilangan-bilangan 2, 4, 8, 16, atau 64. Gambar 8 dibawah memperlihatkan metode pemetaan set assosiative. memory Set
Main memory
s+w
address
Tag
Tag
Word
Cache
B0 B1
B0 B1
d
(3bits)
B2 Set 0
s-d
berbagai algoritma perpindahan dan lebih ekonomis untuk jumlah sector tag dibandingkan assosiative. Contoh sector mapping untuk organisasi 4 way diperlihatkan dalam Gambar 9.
B3
word
B3
Tag
B0
w B1
0
B(ik)
B2
B(ik+1)
B3
Set i (hit in cache)
Tag
B(ik+1)
X
B(ik+k-1)
Compare
B1 B2
Sector Frames (3bits)
X
B0
block
(Tag)
B(k-1)
w
Memory address (2bits) (4bits)
sector
Valid bit
B4 B5 B6 B7
Main memory
B4 B5
1
(block frames)
B6 B7 Tag
Main memory
B8 B9
(miss in cache)
2
B10 B11 Tag
(a) Pencarian k-way assosiative
3
B12 B13 B14 B15
Tag 2 bits Set 0
B0
Cache
B1
B0
B29
B3 B4
Set 1
B28
B2 B1
B30
Main memory
B31
B5
B2
B6
Gambar 9.
B3
B7 B8
Organisasi cache 4 way sector mapping
B9
B4
Set 2 B10
B5
B11
6. Hit Rate dan Miss Penalty.
B12 B6
B13
Set 3
Indikator untuk melihat keefektifan implementasi hirarki memori adalah dengan melihat tingkat keberhasilan mengakses berbagi level memory. Hit adalah keberhasilan mengakses data dalam suatu cache. Jumlah hit yang dinyatakan sebagai fraksi semua akses yang dilakukan disebut hit rate. Sedangkan miss rate adalah jumlah kegagalan akses dilakukan. Miss penalty didefinisikan sebagai waktu tambahan yang diperlukan untuk membawa data yang diinginkan ke dalam cache. Penalty direfleksikan saat prosessor berhenti melakukan proses karena instruksi atau data yang diperlukan tidak tersedia untuk dieksekusi. Secara umum, miss penalty adalah waktu yang diperlukan untuk membawa sutu blok data dari unit yang lebih lambat dalam hirarki memori ke unit yang lebih cepat. Miss penalty dapat dikurangi bila diterapkan mekanisme transfer data yang efisien antara berbagi unit hirarki.
B14
B7
B15
(b) Pemetaan block assosiative.
cache
dalam
2-way
Gambar 8. Pemetaan Set-Assosiative Cache Menggunakan 64 set berarti field set memiliki 6 bit alamat untuk menentukan set cache mana yang mungkin berisi block yang diinginkan. Kemudian field tag alamat harus dibandingkan secara assosiative terhadap tag 2 block set untuk memeriksa apakah block yang dimaksud berada disana. Pada sector mapping cache, cache memory dan memori utama dibagi menjdi sektor-sektor dengan ukuran tetap. Hal ini mengakibatkan tiap sector dapat ditempatkan pada sector frames mana saja yang tersedia. Jika terjadi miss cache hanya block hilang yang diambil kembali dari memori utama dan dibawa ke block frame yang sama pada sector yang tersedia. Dibandingkan dengan assosiative atau set assosiative, sector mapping cache menawarkan keuntungan yakni lebih fleksibel untuk diimplementasikan, dapat menggunakan
7. Cache Performance Performa suatu cache dapat dilihat dari cycle counts dan hit ratio. Kecepatan cache dipengaruhi oleh teknologi memori utama, organisasi cache dan cache hit ratio. Cycle count
4
5
e-journal Teknik Elektro dan Komputer (2013), ISSN 2301-8402
secara langsung berelasi dengan hit ratio seperti tampak pada Gambar 10 dibawah. Write-through dan write-back juga mempengaruhi cycle counts. Disamping itu, ukuran cache, block size, dan jumlah set, turut mempengaruhi cycle count.
meningkat pula. Hal ini dapat dilihat pada Gambar 12. Hit ratio (with fixed cache size) Hit Ratio
1 Cycle count
Initial
Optimal Block size (Bytes)
Gambar 12. Hit Ratio versus block size Gambar 12 menunjukkan bahwa memperbesar ukuran block suatu cache tidak akan selalu meningkatkan performa suatu cache. Meningkatkan ukuran block cache pada satu titik memang akan meningkatkan performa suatu cache. Hal ini terlihat pada tercapainya titik optimal yang mendekati angka hit ratio ideal. Tetapi jika ukuran block cache terus ditingkatkan hit ratio justru akan semakin turun menuju ke titik 0.
Cache size, set number or block size
Gambar 10. Total cycle untuk akses cache Hit ratio cache dipengaruhi oleh ukuran cache dan ukuran block seperti tampak pada Gambar 11.
Hit Ratio
8. Penutup 1
Dari pembahasan diatas dapat ditarik kesimpulan bahwa cache dapat diorganisasikan dalam beberapa cara pemetaan. Masing-masing teknik memiliki teknik yang berbeda dalam pemindahan data dari memory utama ke dalam cache. Hit ratio adalah salah satu parameter untuk melihat performa suatu cache. Angka hit ratio yang ideal adalah 1. Meningkatkan ukuran cache dan ukuran block dalam cache tidak serta merta akan meningkatkan performa suatu cache. Dengan kata lain dapat dikatakan bahwa peningkatan ukuran cache dan ukuran block cache tidak linier dengan peningkatan performa suatu cache.
Cache size (Bytes) Hit Ratio Gambar 11. Hit ratio versus cache size Hit Ratio
Gambar 11 diatas menunjukkan bahwa semakin besar ukuran cache maka akan mendekati angka hit ratio yang ideal. Tetapi memperbesar ukuran cache saat performa suatu cache telah mendekati angka hit ratio yang ideal tidak serta merta akan mencapai hit ratio yang ideal. Dari grafik terlihat bahwa pada saat itu memperbesar ukuran cache tidak memberikan pengaruh apa-apa, dalam hal ini garis grafik lurus asimptot dengan angka hit ratio ideal. Kurva pada Gambar 11. dapat didekati dengan persamaan 1 – C - 0.5 , dimana C adalah total ukuran cache. Bila ukuran hit ratio tetap maka hubungan antara hit ratio dengan block size menunjukkan bahwa semakin besar ukuran block suatu cache tidak menjamin bahwa performa suatu cache akan
Pustaka [1] Kai Hwang, Advanced Computer Architecture: Parallelism, Scalability, Programmability. McGrawHill, 1993. [2] Alan J. Smith, Cache Memories. ACM Computing Survey, pp. 473-530, Sept. 1982 [3] John P. Hayes, Computer Architecture and Organization. 3rd ed. McGrawHill, 1998.
5
