Organisasi dan Kebijakan Cache

Organisasi cache berkaitan dengan bagaimana cache memetakan blok memori ke penyimpanan — penempatan dan asosiativitasnya — serta kebijakan yang mengatur penggantian dan penulisan, yang bersama-sama menentukan seberapa sering cache mengenai (hit) dan bagaimana ia berinteraksi dengan memori utama.

Definition

Organisasi dan kebijakan cache adalah pilihan struktural dan manajemen dari sebuah cache — di mana blok dapat ditempatkan, blok mana yang dikeluarkan saat terjadi miss, dan bagaimana penulisan disebarkan ke tingkat yang lebih rendah — yang mengatur tingkat hit dan perilakunya.

Scope

Topik ini mencakup desain internal cache tunggal: penempatan langsung-terpetakan (direct-mapped), set-asosiatif (set-associative), dan asosiatif penuh (fully associative); kebijakan penggantian seperti LRU (least-recently-used) dan perkiraannya; kebijakan penulisan (write-through versus write-back) dan alokasi penulisan (write-allocation); ukuran blok; dan klasifikasi miss menjadi wajib (compulsory), kapasitas (capacity), dan konflik (conflict). Ini tidak termasuk koherensi multi-cache (protokol koherensi cache) dan translasi alamat (memori virtual dan paging).

Core questions

• Bagaimana penempatan langsung-terpetakan (direct-mapped), set-asosiatif (set-associative), dan asosiatif penuh (fully associative) berbeda dalam biaya dan perilaku konflik?
• Kebijakan penggantian apa yang harus mengeluarkan blok saat terjadi miss, dan bagaimana perkiraannya dilakukan dengan murah?
• Bagaimana kebijakan write-through dan write-back berbeda dalam lalu lintas dan kompleksitas?
• Bagaimana miss diklasifikasikan, dan perubahan desain mana yang mengurangi setiap jenis?

Key concepts

• cache langsung-terpetakan (direct-mapped cache)
• cache set-asosiatif (set-associative cache)
• cache asosiatif penuh (fully associative cache)
• penggantian paling jarang digunakan (LRU replacement)
• write-through vs write-back
• alokasi penulisan (write-allocate)
• ukuran blok (line)
• miss wajib (compulsory), kapasitas (capacity), dan konflik (conflict)

Key theories

Model miss Tiga C

Miss cache dapat dikategorikan sebagai wajib (akses pertama), kapasitas (cache terlalu kecil untuk set kerja), dan konflik (asosiativitas terlalu sedikit), sebuah kerangka kerja yang menghubungkan setiap parameter desain — ukuran, ukuran blok, asosiativitas — dengan miss yang dikuranginya.

Mechanisms

Alamat memori dibagi menjadi bidang tag, indeks, dan offset. Indeks memilih satu set, tag mengidentifikasi blok di dalamnya, dan asosiativitas menetapkan berapa banyak blok yang berbagi satu set. Saat terjadi miss, cache mengambil blok dan mengeluarkan blok lain yang dipilih oleh kebijakan penggantian (seringkali perkiraan dari yang paling jarang digunakan). Penulisan baik memperbarui memori utama segera (write-through) atau menandai blok sebagai kotor (dirty) dan menunda pembaruan (write-back).

Clinical relevance

Organisasi cache mengatur kinerja yang efektif karena penalti miss sangat besar dibandingkan dengan hit. Pemrogram meningkatkan perilaku cache melalui tata letak data, pemblokiran, dan pola akses yang meningkatkan lokalitas, sementara arsitek menyetel asosiativitas, ukuran blok, dan kebijakan penulisan untuk menyeimbangkan tingkat hit dengan area, daya, dan bandwidth.

History

Wilkes mengusulkan memori slave (cache) pada tahun 1965, dan cache segera diadopsi secara komersial. Survei Alan Jay Smith tahun 1982 mensintesis pengukuran ekstensif tentang penempatan, penggantian, dan kebijakan penulisan, menetapkan kosakata desain yang masih digunakan hingga saat ini. Model tiga-C kemudian memberikan cara terstruktur untuk memahami penyebab dan solusi miss.

Key figures

• Maurice Wilkes
• Alan Jay Smith
• John L. Hennessy
• David A. Patterson

Seminal works

• smith1982cache
• hennessy2019

Frequently asked questions

Apa perbedaan antara cache write-through dan write-back?

Cache write-through memperbarui cache dan memori utama pada setiap penulisan, menjaga memori tetap terkini tetapi menghasilkan lebih banyak lalu lintas. Cache write-back hanya memperbarui cache, menandai blok sebagai kotor (dirty), dan menuliskannya ke memori hanya saat dikeluarkan, mengurangi lalu lintas dengan biaya pembukuan tambahan.

Mengapa menggunakan cache set-asosiatif daripada cache langsung-terpetakan (direct-mapped)?

Cache langsung-terpetakan (direct-mapped) memungkinkan setiap blok hanya satu lokasi, sehingga blok yang memetakan ke slot yang sama akan berkonflik. Asosiativitas set memberikan setiap blok beberapa lokasi yang mungkin dalam satu set, mengurangi miss konflik dengan biaya perangkat keras perbandingan yang lebih banyak dan hit yang sedikit lebih lambat.