Cache line

Cache line adalah unit transfer data terkecil antara cache CPU dan memori utama (RAM). Setiap kali CPU butuh data — walaupun cuma 1 byte — yang diangkut dari RAM bukan 1 byte itu saja, melainkan satu blok penuh berukuran tetap, umumnya 64 byte pada CPU x86 modern (Apple M-series memakai 128 byte).

Konsep ini kelihatan sepele, tapi hampir semua trik optimasi performa di HPC — mulai dari layout data SoA, loop ordering, cache blocking, sampai menghindari false sharing — ujung-ujungnya adalah soal memperlakukan cache line dengan benar.

Analogi Sederhana

Bayangkan kamu masak di dapur (CPU) dan bahan-bahannya disimpan di gudang belakang rumah (RAM). Bolak-balik ke gudang itu lama. Jadi aturannya: setiap ke gudang, kamu wajib bawa pulang satu boks penuh, bukan satu bahan saja. Boks itu ditaruh di meja dapur (cache).

Kalau isi satu boks memang bahan-bahan yang akan kamu pakai berurutan → sekali jalan, kerjaan lancar lama. Ini yang disebut spatial locality.
Kalau kamu cuma butuh 1 bahan dari boks itu dan sisanya tidak terpakai → kamu tetap capek mengangkut satu boks penuh. Bandwidth terbuang.

Meja dapur juga terbatas — kalau penuh, boks lama harus dikeluarkan (eviction) untuk memberi tempat boks baru.

Hierarki Memori

Cache bukan cuma satu lapis. Makin dekat ke core, makin cepat tapi makin kecil:

        +-----------+
        |  Register |   ~0-1 siklus      (byte-an)
        +-----------+
        |    L1     |   ~4 siklus        (32-64 KiB per core)
        +-----------+
        |    L2     |   ~12-14 siklus    (256 KiB - 2 MiB per core)
        +-----------+
        |    L3     |   ~30-50 siklus    (8-128 MiB, dibagi antar core)
        +-----------+
        |    RAM    |   ~200-400 siklus  (puluhan GB)
        +-----------+
        |  SSD/Disk |   jutaan siklus
        +-----------+

  makin ke bawah: makin BESAR, makin LAMBAT

Perhatikan jomplangnya: akses L1 vs RAM bedanya bisa 50–100x. Artinya, satu cache miss ke RAM setara ratusan instruksi aritmetika yang "hilang". Inilah kenapa banyak kode HPC yang bottleneck-nya bukan di kecepatan hitung (FLOPS), tapi di memori (memory-bound).

Level	Ukuran tipikal	Latency (kira-kira)	Catatan
Register	ratusan byte	0–1 siklus	bagian dari core
L1	32–64 KiB per core	~4 siklus (~1 ns)	terpisah untuk instruksi (L1i) dan data (L1d)
L2	256 KiB – 2 MiB per core	~12–14 siklus	biasanya privat per core
L3 (LLC)	8–128 MiB	~30–50 siklus	dibagi antar core
RAM (DRAM)	puluhan–ratusan GB	~200–400 siklus (~60–100 ns)	lewat memory controller

Angka pastinya beda-beda tiap CPU; yang penting dipahami adalah ordo perbandingannya.

Cara Kerja: Alamat Dipecah Tiga

RAM secara logis dibagi menjadi blok-blok 64 byte. Blok mana masuk ke slot cache mana ditentukan langsung dari bit-bit alamatnya:

Alamat memori (contoh, cache line 64 byte):

+--------------------------------+-----------+-----------+
|              TAG               |   INDEX   |  OFFSET   |
+--------------------------------+-----------+-----------+
                                       |           |
                                       |           +--> byte ke berapa
                                       |                DI DALAM line (0-63,
                                       |                6 bit karena 2^6=64)
                                       +--> line ini masuk ke SET
                                            nomor berapa di cache

TAG disimpan bersama line-nya, dipakai untuk mengecek:
"line yang nyangkut di slot ini beneran punya alamat X atau bukan?"

Contoh konkret: L1d sebesar 32 KiB, 8-way set associative, line 64 byte:

32.768 / 64 = 512 line
512 / 8 way = 64 set → butuh 6 bit index
Sisa bit alamat di atasnya jadi tag

Kalau CPU mencari data: hitung set dari index → bandingkan tag dengan 8 line di set itu → cocok = cache hit (cepat), tidak cocok = cache miss (harus turun ke level bawah).

Spatial Locality: Kenapa Akses Berurutan Cepat

Karena satu line = 64 byte = 16 buah float, membaca array secara berurutan cuma kena miss sekali tiap 16 elemen:

Akses BERURUTAN (stride 1):

  a[0] a[1] a[2] ... a[15] | a[16] a[17] ... a[31] | a[32] ...
  MISS  hit  hit ...  hit    MISS   hit  ...  hit    MISS
  \________ 1 line ______/   \________ 1 line _____/

  --> 1 miss per 16 float. Hardware prefetcher bahkan bisa
      menebak polanya dan mengambil line berikutnya DULUAN,
      sehingga miss-nya nyaris tak terasa.


Akses LONCAT-LONCAT (stride 16 float = 64 byte):

  a[0]      a[16]     a[32]     a[48]
  MISS      MISS      MISS      MISS
  --> TIAP akses = 1 miss. Dari 64 byte yang diangkut,
      cuma 4 byte yang dipakai. Bandwidth efektif tinggal 1/16.

Dua kode bisa punya jumlah operasi persis sama tapi kecepatannya beda berkali-kali lipat hanya karena pola aksesnya beda. Ini juga alasan utama layout SoA menang untuk akses per-field.

Contoh Klasik: Urutan Loop Matriks

Array 2D di C/C++ disimpan row-major: satu baris utuh dulu, baru baris berikutnya.

A[3][4] di memori:

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| A00 | A01 | A02 | A03 | A10 | A11 | A12 | A13 | A20 | A21 | A22 | A23 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
 \_______ baris 0 ______/ \_______ baris 1 ______/ \______ baris 2 _____/

Loop i-lalu-j : jalan terus ke kanan     --> ramah cache
Loop j-lalu-i : loncat antar baris (N*4 byte) --> miss terus-terusan

// CEPAT: mengikuti layout memori (row-major)
for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
        sum += A[i][j];

// LAMBAT: melawan layout — tiap iterasi loncat satu baris penuh
for (int j = 0; j < N; ++j)
    for (int i = 0; i < N; ++i)
        sum += A[i][j];

Untuk N besar (matriks tidak muat di cache), versi kedua bisa lebih lambat berkali-kali lipat, padahal hasil dan jumlah operasinya identik.

Cache Blocking (Tiling)

Kalau datanya terlalu besar untuk cache, strategi standarnya: pecah kerjaan jadi blok-blok kecil yang muat di L1/L2, lalu pakai blok itu berulang kali selagi masih "hangat" di cache.

Matmul naif C = A x B:
  - baris A dibaca berurutan (aman)
  - kolom B dibaca loncat-loncat sepanjang N --> badai cache miss

Dengan blocking (mis. blok 64x64):

        B                          Kerjakan per-blok:
  +----+----+----+                 blok A dan blok B dimuat sekali,
  | B00| B01| .. |                 dipakai puluhan kali untuk
  +----+----+----+                 menghitung blok C, BARU pindah
  | B10| B11| .. |                 ke blok berikutnya.
  +----+----+----+
                                   Reuse naik --> traffic ke RAM turun.

Teknik ini (plus SIMD) adalah fondasi kenapa library BLAS seperti OpenBLAS/MKL bisa mendekati peak FLOPS, sementara triple-loop naif cuma dapat beberapa persen.

False Sharing: Jebakan di Kode Multithread

Ini masalah cache line yang paling sering menggigit di kode paralel. Dua thread menulis ke variabel yang berbeda, tapi variabelnya kebetulan tinggal di cache line yang sama.

   Core 0                              Core 1
   Thread A: counter[0]++              Thread B: counter[1]++

              satu cache line (64 byte)
            +-------------+-------------+------------------+
            | counter[0]  | counter[1]  |   (sisa line)    |
            +-------------+-------------+------------------+
                  ^               ^
                  A               B

Protokol koherensi (MESI) bekerja per-LINE, bukan per-variabel:
  1. A menulis  -> salinan line di Core 1 di-INVALIDATE
  2. B menulis  -> line harus dipindah/di-invalidate balik
  3. dst... line "ping-pong" bolak-balik antar core

Hasil: dua thread yang secara logika TIDAK berbagi data apa pun
saling memperlambat, kadang sampai lebih lambat dari versi serial.

Solusinya: beri jarak (padding) supaya tiap thread punya line sendiri.

// Bermasalah: 8 counter (8 byte) muat dalam 1 line
long counter[NUM_THREADS];

// Solusi: paksa tiap counter menempati line sendiri
struct alignas(64) PaddedCounter {
    long value;
    // compiler otomatis menambah padding sampai 64 byte
};
PaddedCounter counter[NUM_THREADS];

C++17 menyediakan konstanta std::hardware_destructive_interference_size sebagai pengganti angka 64 yang di-hardcode.

Catatan singkat soal MESI: tiap line di tiap core punya status Modified / Exclusive / Shared / Invalid. Menulis ke line yang statusnya Shared memaksa core lain meng-invalidate salinannya — inilah mekanisme yang membuat false sharing mahal.

Cara Mengecek Ukuran Cache Line

Di Linux:

getconf LEVEL1_DCACHE_LINESIZE
# atau
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
# atau lihat kolom COHERENCY-SIZE:
lscpu -C

Untuk melihat efek cache miss secara nyata, pakai perf:

perf stat -e cache-references,cache-misses,LLC-load-misses ./program

Tips Praktis

Akses memori berurutan sebisa mungkin — susun loop mengikuti layout data (row-major di C/C++), bukan sebaliknya.
Pilih layout data sesuai pola akses — lihat SoA vs AoS.
Kecilkan working set: struct yang ramping = lebih banyak elemen per line. Urutkan field dari yang terbesar untuk mengurangi padding kompiler.
Blocking/tiling untuk kerjaan yang datanya lebih besar dari cache (matmul, stencil, transpose).
Align data panas ke 64 byte (alignas(64), std::aligned_alloc) — penting juga untuk load SIMD.
Waspadai false sharing di kode multithread: data yang ditulis thread berbeda jangan sampai satu line. Pisahkan dengan padding.
Ukur, jangan menebak: perf stat, perf c2c (khusus mendeteksi false sharing), cachegrind (valgrind --tool=cachegrind).

Lihat Juga

Referensi

Ulrich Drepper, What Every Programmer Should Know About Memory, Red Hat, Inc., 2007 — https://people.freebsd.org/~lstewart/articles/cpumemory.pdf
John L. Hennessy & David A. Patterson, Computer Architecture: A Quantitative Approach, 6th Edition, Morgan Kaufmann, 2017 — Bab 2, Memory Hierarchy Design.
Intel Corporation, Intel 64 and IA-32 Architectures Optimization Reference Manual — bagian cache dan memory subsystem.
Agner Fog, The Microarchitecture of Intel, AMD and VIA CPUs — https://www.agner.org/optimize/
Igor Ostrovsky, "Gallery of Processor Cache Effects" — https://igoro.com/archive/gallery-of-processor-cache-effects/
Scott Meyers, "CPU Caches and Why You Care", code::dive 2014 (rekaman talk tersedia di YouTube).
cppreference.com — std::hardware_destructive_interference_size — https://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size

Kategori:HPC Kategori:Arsitektur Komputer Kategori:Optimasi Performa