KAL
Menu

Kode yang Ramah Cache

Penelusuran row-major, tata letak struktur, dan keputusan pemrograman yang menurunkan jumlah miss.

Daftar isi

Urutan akses memori sebagian besar ditentukan oleh kode yang ditulis pemrogram, dan urutan itulah yang mengubah jumlah miss. Simulator pada topik simulasi-cache sudah menunjukkan perbedaan tingkat hit antarpola, dan topik ini menerapkan prinsip yang sama pada program sungguhan. Bahasan mencakup tata letak matriks dalam memori, penelusuran baris demi baris dan kolom demi kolom, bukti jumlah miss melalui simulasi, serta pilihan tata letak data antara array of structs dan struct of arrays.

Tata letak matriks dan urutan perulangan#

C menyimpan matriks dua dimensi secara row-major, yaitu baris demi baris yang diletakkan berdampingan dalam memori. Dengan int berukuran 4 byte dan line 64 byte, satu line memuat 16 elemen bertetangga dari baris yang sama. Penelusuran baris demi baris memanfaatkan seluruh isi line sebelum pindah ke baris berikutnya, sedangkan penelusuran kolom demi kolom menyentuh satu elemen per line dan membiarkan sisanya terbuang.

Bukti jumlah missnya dapat disimulasikan pada matriks kecil dengan cache direct-mapped yang sengaja dibuat kecil, yaitu line 16 byte dengan empat set. Skrip berikut menghitung miss untuk kedua urutan perulangan pada matriks 8x8.

python hitung-miss.py 
# Jumlah miss untuk penelusuran baris dan kolom pada matriks 8x8 ber-int.
# Model cache sengaja dibuat kecil agar pola konfliknya terlihat:
# line 16 byte sehingga satu line memuat 4 int, dengan 4 set direct-mapped.

BARIS = 8
KOLOM = 8
UKURAN_INT = 4    # byte
UKURAN_LINE = 16  # byte, memuat 4 int
JUMLAH_SET = 4    # set direct-mapped, kapasitas total 4 line

def simulasikan(urutan):
    """Hitung miss atas urutan indeks int dengan cache direct-mapped."""
    set_cache = [None] * JUMLAH_SET
    miss = 0
    for i in urutan:
        blok = (i * UKURAN_INT) // UKURAN_LINE  # line tempat int ke-i berada
        set_ke = blok % JUMLAH_SET
        if set_cache[set_ke] != blok:
            miss += 1
            set_cache[set_ke] = blok
    return miss

baris = [b * KOLOM + k for b in range(BARIS) for k in range(KOLOM)]
kolom = [b * KOLOM + k for k in range(KOLOM) for b in range(BARIS)]

for nama, urutan in (("baris", baris), ("kolom", kolom)):
    m = simulasikan(urutan)
    print(f"penelusuran {nama}: miss {m} dari {len(urutan)} akses")
text Keluaran 
penelusuran baris: miss 16 dari 64 akses
penelusuran kolom: miss 64 dari 64 akses

Selisihnya empat kali lipat pada data yang persis sama. Penelusuran baris mengalami satu miss per empat akses karena setiap line melayani empat elemen, sedangkan penelusuran kolom miss pada setiap akses karena langkah antar akses selalu melampaui satu line. Cache kecil dengan empat set membuat kondisi ini muncul bahkan tanpa data besar, sehingga seluruh angkanya dapat diperiksa dengan tangan.

Penelusuran dua arah dalam C#

Program berikut menelusuri matriks 1024x1024 dua kali, pertama baris demi baris dan kemudian kolom demi kolom, lalu mencetak jumlah hasil keduanya. Kedua jumlah harus identik, sehingga kebenaran kedua penelusuran dapat diperiksa dari keluaran yang deterministik. Pengukuran waktu sengaja tidak dicetak oleh program karena nilainya berubah-ubah antareksekusi dan antarmesin.

c penelusuran.c 
/* Penelusuran matriks baris demi baris dan kolom demi kolom.
 * Kedua penelusuran menghitung jumlah yang sama, sehingga keluarannya
 * dapat dibandingkan secara langsung dan selalu sama di mesin mana pun. */
#include <stdio.h>
#include <stdlib.h>

#define BARIS 1024
#define KOLOM 1024

int main(void) {
    int (*matriks)[KOLOM] = malloc(BARIS * sizeof *matriks);
    if (matriks == NULL) {
        fprintf(stderr, "alokasi memori gagal\n");
        return 1;
    }

    /* isi matriks dengan pola yang pasti, tanpa bilangan acak */
    for (int b = 0; b < BARIS; b++) {
        for (int k = 0; k < KOLOM; k++) {
            matriks[b][k] = (b + 2 * k) % 7;
        }
    }

    long long jumlah_baris = 0;
    for (int b = 0; b < BARIS; b++) {
        for (int k = 0; k < KOLOM; k++) {
            jumlah_baris += matriks[b][k];
        }
    }

    long long jumlah_kolom = 0;
    for (int k = 0; k < KOLOM; k++) {
        for (int b = 0; b < BARIS; b++) {
            jumlah_kolom += matriks[b][k];
        }
    }

    printf("jumlah penelusuran baris : %lld\n", jumlah_baris);
    printf("jumlah penelusuran kolom : %lld\n", jumlah_kolom);
    printf("kedua jumlah %s\n",
           jumlah_baris == jumlah_kolom ? "SAMA" : "BEDA");

    free(matriks);
    return 0;
}
text Keluaran 
jumlah penelusuran baris : 3145722
jumlah penelusuran kolom : 3145722
kedua jumlah SAMA

Kedua jumlah bernilai sama karena penjumlahan tidak bergantung pada urutan aksesnya. Perbedaannya terletak pada jumlah miss. Setiap baris berisi 1024 int atau 4 KiB, sehingga langkah dari satu elemen ke elemen baris berikutnya pada penelusuran kolom melompati jarak 4 KiB dan selalu membutuhkan line baru. Versi baris memakai kembali line yang sama untuk 16 akses berturut-turut. Perintah berikut dipakai untuk mengompilasi programnya.

bash 
# kompilasi program tanpa opsi optimasi
cc penelusuran.c -lm -o penelusuran

Selisih waktunya nyata dan terukur, tetapi tidak deterministik, sehingga tidak ditempel sebagai keluaran program. Pada pengukuran terpisah yang dijalankan saat topik ini ditulis, dengan perintah kompilasi yang sama tanpa opsi optimasi, versi kolom membutuhkan waktu sekitar empat sampai lima kali lipat versi baris. Angka itu pasti berubah antarmesin, antarcompiler, dan antaropsi optimasi seperti -O2, tetapi arah selisihnya jarang berbalik.

Alat paling langsung untuk memverifikasi prediksi ini adalah penghitung performa (performance counter) pada prosesor nyata, yaitu perangkat keras yang mencatat kejadian seperti cache miss selama program berjalan. Tanpa alat semacam itu, simulasi kecil dan penalaran tata letak tetap memberi perkiraan yang andal arahnya. Yang tidak boleh dilakukan adalah menyimpulkan kecepatan hanya dari membaca kode, karena urutan akses yang tampak sepele ternyata mengubah jumlah miss berkali-kali lipat.

Array of structs dan struct of arrays#

Pilihan tata letak juga menentukan isi setiap line. Array of structs menampung seluruh medan setiap objek secara berdampingan, sedangkan struct of arrays menampung satu medan dari seluruh objek dalam satu array tersendiri. Perbedaannya paling terlihat ketika proses hanya menyentuh sebagian medan.

c 
// tidak-dijalankan
/* Array of structs: seluruh medan pelajar berdampingan, sehingga
 * penelusuran satu medan tetap menarik medan lain ke dalam line. */
struct pelajar { int nomor; double nilai; char aktif; };
struct pelajar kelas[1000];

/* Struct of arrays: medan yang diakses bersama dikelompokkan,
 * sehingga setiap line yang tertarik terpakai penuh. */
int nomor[1000];
double nilai[1000];
char aktif[1000];

Pada array of structs, membaca seluruh medan nilai tetap menarik medan nomor dan aktif ke dalam line yang sama, sehingga efektifnya line terpakai tidak penuh. Pada struct of arrays, array nilai menempati line untuk dirinya sendiri dan seluruh isinya terpakai. Kondisi inilah yang membuat kode numerik yang memproses satu medan secara massal sering memilih struct of arrays, sedangkan kode yang hampir selalu memakai seluruh medan satu objek sekaligus tetap nyaman dengan array of structs. Ukuran medan juga ikut berperan, karena struct campuran menambahkan celah perataan (alignment padding) yang memperlebar jarak antar nilai yang sama.

Kesalahan umum#

Tiga kekeliruan berikut paling sering muncul ketika kode ditata agar ramah cache.

  1. Menukar urutan perulangan pada bahasa yang berbeda tata letaknya. C menyimpan matriks secara row-major, sedangkan Fortran menyimpannya secara column-major, sehingga urutan yang ramah pada satu bahasa menjadi mahal pada bahasa lain. Perbaikannya adalah memeriksa tata letak bahasanya terlebih dahulu sebelum menata perulangan.
  2. Menilai perubahan tanpa mengunci mode kompilasi. Hasil tanpa opsi optimasi dan dengan -O2 dapat berbeda jauh, karena compiler juga menyusun ulang dan mengelompokkan akses. Perbaikannya adalah melaporkan opsi kompilasi bersama hasil ukurnya.
  3. Menganggap penelusuran kolom selalu salah. Beberapa algoritme memang bekerja per kolom, dan transposisi satu kali yang diikuti penelusuran cepat berulang kali bisa lebih murah daripada penelusuran mahal yang diulang terus. Perbaikannya adalah menghitung biaya keduanya untuk pola akses yang sesungguhnya.

Ringkasan#

  • C menyimpan matriks secara row-major, sehingga penelusuran baris memanfaatkan line penuh dan penelusuran kolom tidak.
  • Simulasi matriks 8x8 pada cache kecil menunjukkan 16 miss dibandingkan dengan 64 miss, sedangkan program C membuktikan kedua urutan menghasilkan jumlah yang sama.
  • Selisih waktu kedua versi nyata tetapi tidak deterministik, sehingga dilaporkan di prosa dengan kualifikasi, bukan sebagai keluaran.
  • Array of structs mengumpulkan medan satu objek, sedangkan struct of arrays mengumpulkan medan yang diakses bersama, dan pilihannya mengikuti pola akses.

Referensi#