SanzSkuy at 07:39, 3 July 2026

2026-07-03T07:39:04Z

← Older revision		Revision as of 07:39, 3 July 2026
Line 232:		Line 232:
	* [[SoA vs AoS]]		* [[SoA vs AoS]]
	* [[SIMD]]		* [[SIMD]]
	* [[Memory ~~coalescing~~]]		* [[Memory Coalescing]]
	* [[Roofline model]]		* [[Roofline model]]
	* [[NUMA]]		* [[NUMA]]

SanzSkuy: Created page with "'''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..."

2026-07-03T07:37:26Z

Created page with "'''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..."

New page

'''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 [[SoA vs AoS|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:

<pre>
+-----------+
| 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
</pre>

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'').

{| class="wikitable"
! 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:

<pre>
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?"
</pre>

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 <code>float</code>, membaca array secara berurutan cuma kena miss sekali tiap 16 elemen:

<pre>
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.
</pre>

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 vs AoS|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.

<pre>
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
</pre>

<syntaxhighlight lang="cpp">
// 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];
</syntaxhighlight>

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.

<pre>
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.
</pre>

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.'''

<pre>
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.
</pre>

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

<syntaxhighlight lang="cpp">
// 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];
</syntaxhighlight>

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

Catatan singkat soal '''MESI''': tiap line di tiap core punya status '''M'''odified / '''E'''xclusive / '''S'''hared / '''I'''nvalid. 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:

<syntaxhighlight lang="bash">
getconf LEVEL1_DCACHE_LINESIZE
# atau
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
# atau lihat kolom COHERENCY-SIZE:
lscpu -C
</syntaxhighlight>

Untuk melihat efek cache miss secara nyata, pakai <code>perf</code>:

<syntaxhighlight lang="bash">
perf stat -e cache-references,cache-misses,LLC-load-misses ./program
</syntaxhighlight>

== 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 (<code>alignas(64)</code>, <code>std::aligned_alloc</code>) — 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''': <code>perf stat</code>, <code>perf c2c</code> (khusus mendeteksi false sharing), cachegrind (<code>valgrind --tool=cachegrind</code>).

== Lihat Juga ==

* [[SoA vs AoS]]
* [[SIMD]]
* [[Memory coalescing]]
* [[Roofline model]]
* [[NUMA]]

== 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]]

Cache line - Revision history

SanzSkuy at 07:39, 3 July 2026