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 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 (a+b) * (c+d)

 a   b       c   d
  \ /         \ /
  (+)         (+)
    \         /
     \       /
       (*)

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

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:

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

Work: T₁ = n − 1 = 7 penjumlahan (sama seperti loop sekuensial — tidak ada kerja ekstra).
Span: T_∞ = log₂ n = 3 level.

Untuk n besar: work Θ(n), span Θ(log n). Bandingkan dengan loop sekuensial sum += x[i]: 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_p = waktu eksekusi di p prosesor. Dua batas bawah yang tidak bisa ditawar:

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

Span Law: T_p ≥ T_∞; Prosesor tambahan tidak bisa memotong critical path.

Gabungan keduanya: T_p ≥ max(T₁/p, T_∞).

Parallelism

Parallelism sebuah algoritma didefinisikan sebagai:

P̄ = T₁ / 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, T_p ≈ T₁/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_p ≤ T₁/p + T_∞

(Bentuk yang lebih ketat: T_p ≤ (T₁ − 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 m_i operasi (jumlah semua m_i = T₁).

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

⌈m_i / p⌉ ≤ m_i/p + 1

Jumlahkan untuk semua level:

T_p ≤ Σ (m_i/p + 1) = T₁/p + T_∞. ∎

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

Contoh Angka

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

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

T₁/p + T_∞ ≤ 2 · max(T₁/p, T_∞)

maka greedy scheduler mana pun paling buruk 2× dari optimal. Ini alasan teoretis kenapa runtime seperti Cilk, TBB, dan OpenMP tasking pakai greedy work-stealing dan hasilnya bagus: work-stealing mencapai ekspektasi T_p ≤ T₁/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 — prefix sum:

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₁/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₁/p mendominasi saat p kecil.
Span serendah mungkin (idealnya polylog, misal Θ(log n)) — supaya scalable saat p besar.

Contoh Analisis Cepat

Algoritma	Work T₁	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):

// 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;
}

Rekurensi span-nya: T_∞(n) = T_∞(n/2) + Θ(1) = Θ(log n), karena dua cabang jalan bersamaan — hanya satu yang dihitung. Work-nya tetap: T₁(n) = 2·T₁(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·T₁, 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₁ 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 T₁ 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₁ = total operasi; Span T_∞ = critical path.
Batas bawah: T_p ≥ max(T₁/p, T_∞). Batas atas (Brent): T_p ≤ T₁/p + T_∞.
Parallelism P̄ = T₁/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