ELEKTRO INDONESIA               Edisi ke Delapan, Juli 1997

Desain Chace pada Sistem Komputer

Cache umumnya menggunakan memori statik yang mahal harganya, sedangkan memori utama menggunakan memori dinamik yang jauh lebih murah. Sistem komputer akan bekerja sangat cepat apabila seluruh sistem memori utamanya menggunakan memori statik, tetapi akibatnya harga sistem komputer akan menjadi sangat mahal. Selain itu, karena hamburan panas pada memori statik lebih besar, sistem komputer yang menggunakan memori statik ini akan menghasilkan panas yang berlebihan.

Hirarki Sistem Memori

Gambar 1

Program komputer pada umumnya tidak mengakses memori secara acak. Besar kecenderungannya bahwa bila program mengakses suatu word maka dalam waktu dekat word tersebut akan diakses lagi. Hal ini dikenal sebagai prinsip lokalitas temporal. Juga besar kecenderungannya bahwa dalam waktu dekat word yang berada di dekat word yang baru diakses akan diakses juga. Yang terakhir ini dikenal sebagai prinsip lokalitas spatial. Karena sifat lokalitas temporal, maka harus diperhatikan word yang telah ada dalam cache, dan karena sifat lokalitas spatial maka perlu diperhatikan kemungkinan memindahkan beberapa word yang berdekatan sekaligus.

Rasio (Kena) dan Waktu Akses

h = (jumlah perujukan yang berhasil) / ( jumlah perujukan)

Dalam studi tentang cache, pengukuran umumnya justru terhadap rasio luput (miss) yang besarnya adalah:

m = (1 - h)
Waktu akses rata-rata, dengan asumsi bahwa perujukan selalu dilakukan ke cache lebih dahulu sebelum ke memori utama, dapat dihitung sebagai berikut:

t _a = t _c + (1-h) t _m
dengan t_a adalah waktu akses rata-rata, t _c adalah waktu akses cache dan tm adalah waktu akses ke memori utama. Setiap kali prosesor terpaksa mengakses memori utama, diperlukan tambahan waktu akses sebesar t _m (1-h). Misalnya, bila rasio kena adalah 0,85, waktu akses ke memori utama adalah 200 ns dan waktu akses ke cache adalah 25 ns, maka waktu akses rata-rata adalah 55 ns.

Bila persamaan t_a disusun ulang, dapat ditulis menjadi:
t _a = t _c {1/k + (1-h)}
dengan k adalah rasio antara waktu akses memori utama dengan waktu akses cache (t_m/t_c).
Dari persamaan di atas dapat dilihat bahwa waktu akses rata-rata didominasi oleh rasio waktu akses memori utama dengan cache bila k kecil. Pada kasus di atas, dengan waktu akses memori utama 200 ns dan waktu akses cache 25 ns, maka k = 8. Rasio luput 1 prosen menyebabkan waktu akses rata-rata menjadi 27 ns, tidak jauh beda dengan waktu akses cache. Pada umumnya k berkisar antara 3-10 (Wilkinson, 1991:68).

Organisasi Cache

Organisasi cache yang dipetakan langsung hanya memerlukan satu kali pembandingan untuk setiap akses ke cache. Baris cache merupakan indeks yang diimplementasikan dengan perangkat keras, sehingga hanya tag dari alamat memori yang diakses yang perlu dibandingkan dengan baris cache. Pada sistem komputer yang memerlukan frekuensi detak tinggi, cara ini sangat menguntungkan. Masalah muncul apabila dua blok yang sering diakses dipetakan ke baris cache yang sama. Dua blok ini akan saling usir dari cache.

PadaGambar 2a terlihat bahwa bagian alamat yang membentuk tag tidak digunakan untuk memetakan alamat pada baris cache, sehingga bila alamat-alamat tersebut hanya berbeda bit tagnya, akan terjadi konflik.
Alamat dibagi menjadi dua bagian, yakni bagian tag dan offset. Tag dicocokkan dengan seluruh tag yang ada dalam baris cache.
Dalam rancangan cache asosiatif-penuh (fully associative), suatu blok dapat ditempatkan pada baris cache manapun. Secara sederhana alamat dibagi menjadi dua bagian yakni bit rendah dan bit tinggi. Bit rendah membentuk offset di dalam baris cache, sedangkan bit tinggi membentuk tag untuk dicocokkan dengan rujukan berikutnya.

Cache asosiatif-penuh harus memiliki mekanisme untuk menentukan ke dalam baris mana suatu blok harus ditempatkan. Blok dapat ditempatkan dalam baris manapun yang kosong, tetapi bila semua baris cache penuh harus ditentukan blok mana yang akan dikeluarkan dari cache. Idealnya, digunakan prinsip LRU (least recently used) yakni blok yang paling lama tidak dipakai dikeluarkan dari cache. Karena cukup mahal mengimplementasikannya, maka umumnya digunakan teknik-teknik yang mendekati prinsip LRU.

Cache asosiatif-penuh memecahkan masalah konflik alamat dengan resiko memperbanyak implementasi rangkaian perangkat keras untuk membandingkan tag terhadap semua baris cache. Untuk memperkecil resiko tersebut sekaligus mengurangi terjadinya konflik alamat, dirancang organisasi cache yang lain yakni asosiatif-kelompok (set-associative).

Dalam cache asosiatif-kelompok, satu kelompok terdiri atas beberapa baris. Bit alamat bagian tengah menentukan kelompok baris di mana suatu blok ditempatkan. Pada contoh Gambar 2c satu kelompok terdiri atas dua baris sehingga disebut sebagai organisasi asosiatif-kelompok dua-jalan (two-way set-associative). Mikroprosesor Amd486DX2, misalnya, memiliki 8 KB cache asosiatif-kelompok empat-jalan (four-way set-associative) dengan baris masing-masing selebar 26 byte. Cache sebesar 8 KB tersebut dibagi menjadi 128 kelompok yang masing-masing terdiri atas empat baris (AMD, 1993).

Dalam setiap kelompok, cache dipetakan secara asosiatif-penuh. Cache dengan dua baris per kelompok atau cache asosiatif-kelompok dua-jalan memerlukan dua pembandingan untuk satu kali akses. Selain membutuhkan lebih sedikit pembandingan dibanding cache asosiatif-penuh, cache asosiatif-kelompok juga memudahkan implementasi teknik LRU (least recently used). Bit tengah dari alamat digunakan untuk memilih sekelompok baris (bukan hanya satu baris seperti pada sistem pemetaan langsung). Tag alamat kemudian dicocokkan dengan tag seluruh baris cache yang dipilih.

Selain ketiga organisasi cache di atas, pada masa-masa awal pemanfaatan sistem cache beberapa jenis prosesor menggunakan cache, dengan pemetaan-sektor. Pada pemetaan sektor, baik memori utama maupun cache dibagi menjadi sektor-sektor. Setiap sektor terdiri atas sejumlah blok. Sembarang sektor pada memori utama dapat terpetakan ke sembarang sektor dalam cache, dengan suatu tag disimpan bersama tiap-tiap sektor dalam cache untuk mengidentifikasi alamat sektor memori utama. Dalam pengirimannya ke cache atau pengembaliannya ke memori utama, data/instruksi tidak dikirim sektor per sektor tetapi blok per blok. Pada saat terjadi luput sektor (sector miss) blok yang diperlukan dari satu sektor dipindahkan ke lokasi tertentu dalam satu sektor. Lokasi sektor dalam cache dipilih berdasarkan algoritma penggantian tertentu. Desain ini sudah tidak populer lagi karena prosentase kena (hit) lebih rendah dibanting dengan organisasi asosiatif-kelompok (Wilkinson, 1991:74-75; Hwang dan Briggs, 1985:106-107).

Cache Tunggal dan Cache Ganda

Unjuk kerja cache berkaitan langsung dengan organisasi yang diterapkan. Secara kasar dapat dinyatakan bahwa cache berukuran n yang dipetakan langsung (direct-mapped) memiliki prosentase luput yang sama dengan cache asosiatif-kelompok dua-arah berukuran n/2. Jelas bahwa besarnya kapasitas cache bukanlah ukuran akurat untuk menilai unjuk kerjanya.

Hal lain yang juga perlu diperhatikan dalam membandingkan cache adalah arsitekturnya. Beberapa prosesor menerapkan sistem cache tunggal, yakni dimiliki secara bersama oleh data maupun instruksi. Arsitektur cache jenis ini dikenal sebagai arsitektur Princeton. Prosesor Amd486DX2 merupakan contoh prosesor dengan arsitektur Princeton. Sistem prosesor lain, misalnya P6 (Pentium Pro), menggunakan dua cache, yakni satu cache data dan satu cache instruksi. Prosesor dengan cache ganda seperti ini dikenal sebagai prosesor dengan cache berarsitektur Harvard.
Pemisahan antara cache instruksi dengan cache data menyebabkan hilangnya interferensi antara perujukan data dan perujukan instruksi. Pemisahan cache instruksi dari cache data juga memungkinkan pengambilan data dan instruksi secara bersamaan. Arsitektur Harvard memiliki dua kelemahan pokok. Jika suatu program memperbarui dirinya sendiri dengan menuliskan instruksi baru, instruksi tersebut akan ditulis dalam cache data. Sebelum instruksi baru itu dapat dieksekusi, kedua cache harus dikosongkan, dan modifikasi yang dilakukan tadi disimpan dulu ke memori utama. Cache instruksi mengambil instruksi hasil modifikasi tersebut dari memori utama. Kelemahan kedua, bila suatu program memerlukan cache instruksi yang lebih besar dan cache data yang lebih kecil, cache berarsitektur Hardvard tidak bisa memenuhi karena alokasinya tidak bisa diubah seperti cache tunggal.

Memori Nyata dan Memori Maya

Sistem operasi mengalokasikan memori untuk program dalam unit-unit berukuran tetap yang disebut halaman (page). Satu halaman pada umumnya berukuran 4 KB. Sistem operasi juga menyimpan tabel yang berisi pemetaan halaman maya ke halaman nyata. Setiap kali program mengakses alamat maya, sistem harus melihat tabel translasi alamat maya ke alamat nyata sehingga lokasi memori yang benar dapat diakses.

Sistem pemeriksaan tabel (table look-up) memerlukan waktu operasi yang cukup lama. Oleh karena itu, prosesor menggunakan cache khusus yang disebut sebagai TLB (translation look-aside buffer) untuk menyimpan translasi alamat terbaru. Jadi, hanya bila translasi halaman yang diperlukan tidak tersedia dalam TLB, sistem operasi akan menginterupsi program, memeriksa translasi halaman dalam tabel yang menetap dalam memori (memory resident), mengisikan hasil translasi ke dalam TLB dan mengembalikan kontrol kepada program.

Luput yang terjadi pada TLB memerlukan siklus detak yang lebih banyak daripada luput yang terjadi pada cache. Bila terjadi luput pada TLB maka seluruh alur-pipa (pipeline) harus dikosongkan, register-register harus diselamatkan, rutin pemeriksaan harus dieksekusi, dan register-register harus dipulihkan. Proses ini memerlukan belasan bahkan ratusan siklus detak.

Untuk memeriksa dan menyimpan data dalam cache, baik alamat nyata maupun alamat maya dapat dipakai. Pemilihan organisasi cache mempengaruhi berbagai aspek dalam organisasi sistem komputer dan unjuk-kerja aplikasi.

Cache Alamat Maya

Pada cache yang dipetakan ke alamat nyata, sistem operasi bisa saja mengalokasikan halaman nyata yang berbeda untuk pelaksanaan program yang sama. Dengan demikian, tag dari cache untuk alamat-alamat instruksi bisa berbeda pada pelaksanaan program yang sama, bahkan meskipun dilakukan komputasi yang sama. Unjuk-kerja bisa berbeda jauh meskipun program yang dijalankan sama, terutama bila alamat nyata tersebut dipetakan langsung.

Cache Alamat Nyata

Operasi Asinkron

Gambar 3a

Pada rancangan prosesor yang paling sederhana, jika cache mengisyaratkan terjadinya luput, prosesor berada pada kondisi menunggu. Rangkaian demikian memang sederhana, tetapi memaksa instruksi berikutnya menunggu dieksekusi sampai cache terisi. Pada rancangan yang lebih canggih, prosesor dapat mengeksekusi instruksi-instruksi berikutnya yang tidak bergantung pada isi cache yang ditunggu. Jika terjadi luput lagi sementara luput sebelumnya belum selesai, prosesor akan berhenti sebagai tanda bahwa telah terjadi satu luput. Pada umumnya dapat ditolerir dua atau lebih keadaan luput sebelum prosesor berhenti.

Pada rancangan prosesor paling sederhana, jika terjadi luput, seluruh baris yang berisi nilai yang diperlukan akan diisikan dan diberikan kepada prosesor. Hal ini menjamin bahwa luput berikutnya pada baris yang sama tidak mungkin terjadi saat baris dalam proses dipindahkan.

Metode yang lebih canggih mengisikan baris cache mulai dari kata (word) data yang diminta dan seterusnya sampai ke awal baris. Kata data yang diminta dipasok ke prosesor segera setelah dikirim dari memori, dan sisanya dipindahkan saat prosesor melanjutkan pemrosesan.

Catatan Akhir

Gambar 3b

Daftar Pustaka

• Anonim. 1993. Am486DX/DX2 Hardware Reference Manual. Advanced Micro Devices
• Bacon, David F. 1994. Cache Advantage. Byte, August 1994.
• Halfhill, Tom R. 1995. Intel's P6. Byte, April 1995.
• Hwang, Kai dan Fay_ A. Briggs. 1985. Computer Architecture and Parallel Processing
• Silberschatz, Abraham dan Peter B. Galvin. 1995. Operating System Concept. Massachusetts: Addison-Wesley Publishing Company
• Wilkinson, Barry. 1991. Computer Architecture: Design and Performance. New York: Prentice Hall.

Hari Wibawanto adalah Staf Pengajar Pendidikan Teknik Elektro FPTK IKIP Semarang