View source for Work-Span Model & Brent's Theorem

'''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 — T<sub>1</sub>
: Total jumlah operasi dalam DAG. Sama dengan waktu eksekusi kalau hanya ada '''1 prosesor''' (makanya notasinya T<sub>1</sub>).

; Span — T<sub>∞</sub>
: Panjang '''jalur terpanjang''' (critical path) dalam DAG. Sama dengan waktu eksekusi kalau prosesornya '''tak terhingga''' (makanya T<sub>∞</sub>). 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: T<sub>1</sub> = n − 1 = 7 penjumlahan (sama seperti loop sekuensial — tidak ada kerja ekstra).
* Span: T<sub>∞</sub> = log<sub>2</sub> 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 T<sub>p</sub> = waktu eksekusi di p prosesor. Dua batas bawah yang tidak bisa ditawar:

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

; Span Law
: T<sub>p</sub> ≥ T<sub>∞</sub>
: Prosesor tambahan tidak bisa memotong critical path.

Gabungan keduanya: T<sub>p</sub> ≥ max(T<sub>1</sub>/p, T<sub>∞</sub>).

= Parallelism =

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

: P̄ = T<sub>1</sub> / T<sub>∞</sub>

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, T<sub>p</sub> ≈ T<sub>1</sub>/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:

: '''T<sub>p</sub> ≤ T<sub>1</sub>/p + T<sub>∞</sub>'''

(Bentuk yang lebih ketat: T<sub>p</sub> ≤ (T<sub>1</sub> − T<sub>∞</sub>)/p + T<sub>∞</sub>.)

== Sketsa Bukti ==

Susun DAG per level: level i berisi semua operasi yang jarak terjauhnya dari input adalah i. Ada T<sub>∞</sub> level, dan misal level i berisi m<sub>i</sub> operasi (jumlah semua m<sub>i</sub> = T<sub>1</sub>).

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

: ⌈m<sub>i</sub> / p⌉ ≤ m<sub>i</sub>/p + 1

Jumlahkan untuk semua level:

: T<sub>p</sub> ≤ Σ (m<sub>i</sub>/p + 1) = T<sub>1</sub>/p + T<sub>∞</sub>. ∎

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

== Contoh Angka ==

Pohon reduksi n = 1024 (T<sub>1</sub> = 1023, T<sub>∞</sub> = 10) di p = 32 prosesor:

* Batas bawah: T<sub>32</sub> ≥ max(1023/32, 10) = max(32, 10) = 32
* Batas atas (Brent): T<sub>32</sub> ≤ 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(T<sub>1</sub>/p, T<sub>∞</sub>) dan:

: T<sub>1</sub>/p + T<sub>∞</sub> ≤ 2 · max(T<sub>1</sub>/p, T<sub>∞</sub>)

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 T<sub>p</sub> ≤ T<sub>1</sub>/p + O(T<sub>∞</sub>) 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 T<sub>1</sub>/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 T<sub>1</sub>/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 T<sub>1</sub> !! Span T<sub>∞</sub> !! 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
|}

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

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<sub>∞</sub>(n) = T<sub>∞</sub>(n/2) + Θ(1) = Θ(log n), karena dua cabang jalan ''bersamaan'' — hanya satu yang dihitung. Work-nya tetap: T<sub>1</sub>(n) = 2·T<sub>1</sub>(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<sub>∞</sub> ≥ f·T<sub>1</sub>, 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 → T<sub>1</sub> naik jauh lebih cepat dari T<sub>∞</sub> → 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 T<sub>1</sub> 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 T<sub>1</sub>''' = total operasi; '''Span T<sub>∞</sub>''' = critical path.
* Batas bawah: T<sub>p</sub> ≥ max(T<sub>1</sub>/p, T<sub>∞</sub>). Batas atas (Brent): T<sub>p</sub> ≤ T<sub>1</sub>/p + T<sub>∞</sub>.
* Parallelism P̄ = T<sub>1</sub>/T<sub>∞</sub> = 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]]