SanzSkuy: Created page with "'''Work-Span Model''' adalah cara menganalisis algoritma paralel ''tanpa peduli jumlah prosesor''. Daripada tanya "berapa cepat di 64 core?", model ini tanya dua hal yang lebih fundamental: berapa total kerjanya, dan seberapa panjang rantai ketergantungannya. '''Brent's Theorem''' kemudian menjembatani keduanya ke dunia nyata: dari dua angka itu, kita bisa menjamin batas waktu eksekusi di ''p'' prosesor berapa pun. Ini fondasi teori di balik semua yang praktis: kenapa r..."

2026-07-11T06:01:49Z

Created page with "'''Work-Span Model''' adalah cara menganalisis algoritma paralel ''tanpa peduli jumlah prosesor''. Daripada tanya "berapa cepat di 64 core?", model ini tanya dua hal yang lebih fundamental: berapa total kerjanya, dan seberapa panjang rantai ketergantungannya. '''Brent's Theorem''' kemudian menjembatani keduanya ke dunia nyata: dari dua angka itu, kita bisa menjamin batas waktu eksekusi di ''p'' prosesor berapa pun. Ini fondasi teori di balik semua yang praktis: kenapa r..."

New page

'''Work-Span Model''' adalah cara menganalisis algoritma paralel ''tanpa peduli jumlah prosesor''. Daripada tanya "berapa cepat di 64 core?", model ini tanya dua hal yang lebih fundamental: berapa total kerjanya, dan seberapa panjang rantai ketergantungannya. '''Brent's Theorem''' kemudian menjembatani keduanya ke dunia nyata: dari dua angka itu, kita bisa menjamin batas waktu eksekusi di ''p'' prosesor berapa pun.

Ini fondasi teori di balik semua yang praktis: kenapa reduction di [[CUDA: Reduction & Scan|CUDA]] dibuat berbentuk pohon, kenapa scan versi naive dianggap boros, dan kapan nambah GPU itu buang-buang duit.

= Komputasi sebagai DAG =

Bayangkan eksekusi program sebagai '''directed acyclic graph (DAG)''':
* Setiap simpul (node) = satu operasi (misalnya satu penjumlahan).
* Setiap sisi (edge) = ketergantungan data. Operasi B baru boleh jalan setelah A selesai kalau ada sisi A → B.

Contoh: menghitung <code>(a+b) * (c+d)</code>

<pre>
a b c d
\ / \ /
(+) (+)
\ /
\ /
(*)
</pre>

Dua penjumlahan tidak saling bergantung, jadi bisa jalan bersamaan. Perkalian harus menunggu keduanya. DAG ini punya 3 operasi total, tapi jalur terpanjangnya hanya 2 operasi.

Model ini mengabaikan biaya komunikasi, latensi memori, dan overhead scheduling — sengaja. Tujuannya mengisolasi sifat ''algoritmanya'', bukan mesinnya.

= Work dan Span =

Dua metrik utama:

; Work — T1
: Total jumlah operasi dalam DAG. Sama dengan waktu eksekusi kalau hanya ada '''1 prosesor''' (makanya notasinya T1).

; Span — T∞
: Panjang '''jalur terpanjang''' (critical path) dalam DAG. Sama dengan waktu eksekusi kalau prosesornya '''tak terhingga''' (makanya T∞). Disebut juga ''depth''. Sebanyak apa pun prosesor yang dilempar ke masalah ini, kita tidak bisa lebih cepat dari span — dependensi tidak bisa disogok.

Contoh klasik: menjumlahkan n = 8 angka dengan pohon reduksi:

<pre>
x0 x1 x2 x3 x4 x5 x6 x7
\ / \ / \ / \ /
(+) (+) (+) (+) level 1
\ / \ /
\ / \ /
(+) (+) level 2
\ /
\ /
(+) level 3
</pre>

* Work: T1 = n − 1 = 7 penjumlahan (sama seperti loop sekuensial — tidak ada kerja ekstra).
* Span: T∞ = log2 n = 3 level.

Untuk n besar: work Θ(n), span Θ(log n). Bandingkan dengan loop sekuensial <code>sum += x[i]</code>: work-nya sama Θ(n), tapi span-nya juga Θ(n) karena setiap iterasi bergantung pada hasil sebelumnya — DAG-nya rantai lurus. Algoritmanya harus ''disusun ulang'' supaya span turun; kompilator tidak melakukan ini gratis.

= Dua Hukum Dasar =

Misal Tp = waktu eksekusi di p prosesor. Dua batas bawah yang tidak bisa ditawar:

; Work Law
: Tp ≥ T1 / p
: p prosesor paling banter menyelesaikan p operasi per satuan waktu. Konsekuensinya: speedup Sp = T1/Tp ≤ p. Tidak ada speedup superlinear di model ini (kalau di dunia nyata ketemu superlinear, biasanya efek cache, bukan keajaiban algoritma).

; Span Law
: Tp ≥ T∞
: Prosesor tambahan tidak bisa memotong critical path.

Gabungan keduanya: Tp ≥ max(T1/p, T∞).

= Parallelism =

'''Parallelism''' sebuah algoritma didefinisikan sebagai:

: P̄ = T1 / T∞

Ini rata-rata banyaknya operasi yang tersedia untuk dikerjakan paralel di sepanjang critical path — sekaligus '''speedup maksimum yang mungkin dicapai''', berapa pun jumlah prosesornya.

Contoh pohon reduksi n = 1024: P̄ = 1023 / 10 ≈ 102. Artinya pakai lebih dari ±102 prosesor untuk masalah ini percuma; speedup mentok di situ.

Aturan praktis ('''parallel slackness'''): kalau p ≪ P̄ (misal 10× lebih kecil), maka speedup mendekati linear, Tp ≈ T1/p. Kalau p mendekati atau melebihi P̄, span mulai mendominasi dan speedup jenuh. Ini alasan GPU butuh masalah besar: dengan puluhan ribu thread, P̄ masalahnya harus jauh lebih besar lagi supaya semua thread kebagian kerja.

= Brent's Theorem =

Work law dan span law memberi batas '''bawah'''. Brent's Theorem (R. P. Brent, 1974) memberi batas '''atas''' — jaminan bahwa waktu segini pasti tercapai:

: '''Tp ≤ T1/p + T∞'''

(Bentuk yang lebih ketat: Tp ≤ (T1 − T∞)/p + T∞.)

== Sketsa Bukti ==

Susun DAG per level: level i berisi semua operasi yang jarak terjauhnya dari input adalah i. Ada T∞ level, dan misal level i berisi mi operasi (jumlah semua mi = T1).

Semua operasi dalam satu level saling bebas, jadi p prosesor bisa mengerjakan level i dalam:

: ⌈mi / p⌉ ≤ mi/p + 1

Jumlahkan untuk semua level:

: Tp ≤ Σ (mi/p + 1) = T1/p + T∞. ∎

Intuisinya: waktu eksekusi terpecah jadi dua komponen — bagian yang bisa dibagi rata ke prosesor (T1/p) dan "pajak" struktur dependensi yang harus dibayar penuh (T∞).

== Contoh Angka ==

Pohon reduksi n = 1024 (T1 = 1023, T∞ = 10) di p = 32 prosesor:

* Batas bawah: T32 ≥ max(1023/32, 10) = max(32, 10) = 32
* Batas atas (Brent): T32 ≤ 1023/32 + 10 ≈ 42

Jadi tanpa menjalankan apa pun, kita tahu waktunya di antara 32 dan 42 langkah. Speedup dijamin minimal 1023/42 ≈ 24× dari maksimum teoretis 32×.

== Korolari: Greedy Scheduler 2-Optimal ==

'''Greedy scheduler''' = scheduler yang tidak pernah membiarkan prosesor nganggur selama masih ada operasi yang siap jalan. Setiap greedy scheduler memenuhi batas Brent. Karena batas bawahnya max(T1/p, T∞) dan:

: T1/p + T∞ ≤ 2 · max(T1/p, T∞)

maka greedy scheduler mana pun paling buruk '''2× dari optimal'''. Ini alasan teoretis kenapa runtime seperti Cilk, TBB, dan [[OpenMP: Tasking|OpenMP tasking]] pakai greedy '''work-stealing''' dan hasilnya bagus: work-stealing mencapai ekspektasi Tp ≤ T1/p + O(T∞) tanpa perlu scheduler pintar-pintar amat.

Pesan praktisnya buat kita: '''jangan pusing mikirin scheduling manual; pusinglah menurunkan span dan menjaga work tetap kecil.''' Scheduler sudah hampir optimal; algoritmanya yang menentukan.

= Work-Efficiency =

Algoritma paralel disebut '''work-efficient''' kalau work-nya (asimtotik) sama dengan algoritma sekuensial terbaik. Ini kriteria penting yang sering dilupakan karena orang silau sama span kecil.

Contoh terkenal — [[Parallel Prefix Sum (Scan)|prefix sum]]:

{| class="wikitable"
! Algoritma !! Work !! Span !! Work-efficient?
|-
| Sekuensial || Θ(n) || Θ(n) || (baseline)
|-
| Naive/Hillis-Steele || Θ(n log n) || Θ(log n) || Tidak
|-
| Blelloch (up-sweep/down-sweep) || Θ(n) || Θ(log n) || Ya
|}

Hillis-Steele span-nya bagus tapi membayar log n kali lipat kerja ekstra. Di p prosesor, suku T1/p pada batas Brent membengkak log n kali — algoritma yang "lebih paralel" justru kalah begitu p terbatas (dan p ''selalu'' terbatas). Blelloch dapat span yang sama dengan work optimal. Inilah kenapa scan produksi (CUB, Thrust) berbasis Blelloch.

Aturan main mendesain algoritma paralel, urut prioritas:
# Work seminimal mungkin (idealnya work-efficient) — karena T1/p mendominasi saat p kecil.
# Span serendah mungkin (idealnya polylog, misal Θ(log n)) — supaya scalable saat p besar.

= Contoh Analisis Cepat =

{| class="wikitable"
! Algoritma !! Work T1 !! Span T∞ !! Parallelism
|-
| Penjumlahan/reduksi (pohon) || Θ(n) || Θ(log n) || Θ(n / log n)
|-
| Parallel for (badan independen) || Θ(n) || Θ(1)* || Θ(n)
|-
| Matmul klasik (loop ijk diparalelkan) || Θ(n³) || Θ(log n) || Θ(n³ / log n)
|-
| Quicksort paralel (partisi sekuensial) || Θ(n log n) || Θ(n) || Θ(log n) — jelek!
|-
| Merge sort paralel (merge paralel) || Θ(n log n) || Θ(log³ n) || bagus
|}

*Θ(1) kalau spawn-nya dianggap gratis; dengan spawn pohon biner jadi Θ(log n).

Baris quicksort menarik: rekursinya paralel, tapi partisi Θ(n) yang sekuensial masuk ke critical path di setiap level rekursi. Hasilnya span Θ(n) dan parallelism cuma Θ(log n) — hampir tidak scalable. Pola gagal seperti ini baru kelihatan kalau dianalisis pakai work-span; benchmark di 4 core tidak akan menunjukkannya. Lebih detail di [[Parallel Sorting]].

Contoh kode gaya OpenMP task untuk reduksi pohon (bandingkan span-nya dengan loop biasa):

<syntaxhighlight lang="c">
// Work: T1 = Θ(n), Span: T∞ = Θ(log n)
long sum(long *x, int lo, int hi) {
if (hi - lo < CUTOFF) { // basis: sekuensial
long s = 0;
for (int i = lo; i < hi; i++) s += x[i];
return s;
}
int mid = (lo + hi) / 2;
long a, b;
#pragma omp task shared(a)
a = sum(x, lo, mid); // dua cabang independen:
b = sum(x, mid, hi); // inilah yang memotong span
#pragma omp taskwait
return a + b;
}
</syntaxhighlight>

Rekurensi span-nya: T∞(n) = T∞(n/2) + Θ(1) = Θ(log n), karena dua cabang jalan ''bersamaan'' — hanya satu yang dihitung. Work-nya tetap: T1(n) = 2·T1(n/2) + Θ(1) = Θ(n).

= Hubungan dengan Amdahl's Law =

[[Amdahl's law]] adalah kasus khusus dari span law. Kalau fraksi f dari program sekuensial murni, maka bagian itu masuk penuh ke critical path: T∞ ≥ f·T1, sehingga parallelism P̄ ≤ 1/f — persis batas speedup Amdahl. Bedanya:

* Amdahl membagi program kasar jadi dua kotak: "sekuensial" dan "paralel sempurna".
* Work-span melihat struktur dependensi sebenarnya, jadi bisa menganalisis algoritma yang bagian paralelnya pun punya dependensi internal (seperti pohon reduksi).

Work-span lebih tajam; Amdahl lebih gampang dipakai buat estimasi kasar sistem utuh. Untuk sisi "problem size ikut membesar", lihat [[Gustafson's Law]] — dalam bahasa work-span: n naik → T1 naik jauh lebih cepat dari T∞ → parallelism naik → prosesor banyak jadi berguna lagi.

= Batas Model =

Yang sengaja diabaikan model ini (dan bisa menggigit di dunia nyata):
* '''Komunikasi & memori''' — di cluster, memindahkan data sering lebih mahal dari menghitungnya. Pelengkapnya: [[Roofline model]] (batas bandwidth) dan [[Isoefficiency & Scalability]] (overhead komunikasi vs ukuran masalah).
* '''Overhead spawn/sync''' — makanya kode nyata selalu pakai CUTOFF/grain size; task terlalu kecil membuat konstanta di T1 membengkak.
* '''Heterogenitas''' — semua "prosesor" dianggap identik dan satu operasi = satu satuan waktu.

Model ini menjawab "algoritmanya scalable atau tidak", bukan "programnya cepat atau tidak". Dua-duanya perlu.

= Ringkasan =

* '''Work T1''' = total operasi; '''Span T∞''' = critical path.
* Batas bawah: Tp ≥ max(T1/p, T∞). Batas atas (Brent): Tp ≤ T1/p + T∞.
* Parallelism P̄ = T1/T∞ = speedup maksimum. Pakai p ≪ P̄ supaya speedup ≈ linear.
* Greedy/work-stealing scheduler ≤ 2× optimal → fokus ke algoritma, bukan scheduler.
* Turunkan span, tapi '''jangan korbankan work-efficiency''' (pelajaran Blelloch vs Hillis-Steele).

= Lihat Juga =

* [[Amdahl's law]] — kasus khusus span law
* [[Gustafson's Law]] — scaling dengan problem size
* [[Parallel Prefix Sum (Scan)]] — studi kasus work-efficiency
* [[Parallel Sorting]] — studi kasus span di algoritma rekursif
* [[CUDA: Reduction & Scan]] — implementasi nyata pohon reduksi
* [[OpenMP: Tasking]] — work-stealing di praktik
* [[Roofline model]] — batas dari sisi memori/bandwidth

[[Kategori:HPC]]
[[Kategori:Teori Algoritma Paralel]]

Work-Span Model & Brent's Theorem - Revision history