Matematika Speedup

Hukum Amdahl sebagai penghitung kecepatan maksimal dan pembatasnya terhadap intuisi.

Daftar isi

Setiap klaim kecepatan pada akhirnya diukur dengan satu perbandingan sederhana, yaitu waktu sebelum dan waktu sesudah perubahan. Topik ini membahas speedup, yaitu ukuran berapa kali lipat sebuah perubahan mempercepat pekerjaan, lalu memperkenalkan hukum Amdahl sebagai rumus yang menghitung speedup maksimal ketika hanya sebagian pekerjaan yang dipercepat oleh $n$ unit paralel. Pembahasan ditutup dengan berkas Python yang menghitung tabel speedup untuk dua porsi kerja yang berbeda, sehingga pembatasan yang dikenakan rumusnya terlihat dalam angka, bukan dalam kesan.

Speedup sebagai perbandingan waktu#

Speedup didefinisikan sebagai perbandingan waktu kerja lama terhadap waktu kerja baru, dengan rumus $S = \frac{T_{\text{lama}}}{T_{\text{baru}}}$ . Nilai $S = 1$ berarti tidak ada perubahan kecepatan, sedangkan $S = 4$ berarti pekerjaan selesai empat kali lebih cepat. Sebagai contoh netral, program kompresi arsip cadangan yang semula bekerja 40 detik dan setelah optimasi bekerja 10 detik memiliki speedup 4. Ukuran ini tidak bersatuan karena kedua waktunya saling menghapus satu sama lain, sehingga aman dibandingkan antarversi sepanjang beban kerjanya sama.

Angka persen penghematan waktu berbeda dari speedup dan sering tertukar. Menghemat 75 persen waktu sama dengan speedup 4, tetapi menghemat 40 persen waktu hanya sama dengan speedup 1,67 karena tersisa 60 persen pekerjaan yang tidak memendek. Kebiasaan yang aman adalah menghitung kedua ukuran dari dua waktu yang diukur pada beban kerja yang persis sama, lalu menyebut beban kerjanya bersama angkanya. Tanpa kebiasaan itu, dua laporan speedup yang dihitung dari beban kerja berbeda tidak dapat dibandingkan.

Hukum Amdahl dan bentuk rumusnya#

Hukum Amdahl merumuskan speedup maksimal apabila hanya sebagian pekerjaan yang dapat dipercepat. Pekerjaan dinormalisasi menjadi satu satuan, lalu dipecah menjadi dua bagian, yaitu $f$ porsi yang dipercepat oleh $n$ unit paralel dan $1-f$ porsi serial yang tetap berjalan pada satu unit. Unit di sini dapat berupa inti prosesor maupun unit eksekusi di dalam satu inti, dan rumusnya tidak menuntut bentuk fisik tertentu. Porsi serial dikerjakan dengan waktu $1-f$ , sedangkan porsi paralel terbagi rata sehingga waktunya menjadi $f/n$ , dan jumlah keduanya membentuk pembagi rumus berikut.

S_{\text{maks}} = \frac{1}{(1-f) + \frac{f}{n}}

Dua kasus uji menegaskan rumus itu masuk akal. Apabila $n = 1$ , pembaginya menjadi $(1-f) + f = 1$ , sehingga speedupnya tepat 1 karena tidak ada paralelisme sama sekali. Apabila $f = 1$ , seluruh pekerjaan terbagi rata dan speedupnya tepat $n$ , yaitu keadaan ideal memakai seluruh unit. Kasus yang menarik justru berada di antara keduanya, yaitu ketika $f$ besar tetapi tidak pernah mencapai satu, sehingga porsi serialnya tetap terbawa sampai pembagian berakhir.

Batas ketika unit bertambah#

Apabila jumlah unit $n$ ditambah tanpa batas, suku $f/n$ dalam pembagi menyusut menuju nol, sehingga rumus Amdahl menyusut menjadi pembalikan porsi serialnya.

S_{\text{maks}} = \frac{1}{1-f}

Batas inilah yang membendung intuisi. Porsi yang dipercepat mencapai 90 persen menyisakan porsi serial 10 persen, sehingga speedup tidak pernah melewati 10 seberapa banyak unit pun ditambahkan. Porsi yang dipercepat separuh pekerjaan berhenti di angka 2, jauh di bawah taksiran kasar yang mengalikan banyaknya unit. Angka batasnya dapat dihitung langsung dari sisa porsi serialnya tanpa mengetahui bentuk pekerjaannya, sehingga rumus yang sama berlaku untuk program kompresi, pengolah teks, maupun pengolahan data ilmiah. Menambah unit tetap berguna, tetapi keuntungannya makin kecil karena pembagi semakin dekat ke $1-f$ , sedangkan selisih yang tersisa semakin tipis.

Jalan keluar dari batas ini adalah memperkecil porsi serialnya, misalnya mempercepat bagian yang masih berjalan satu demi satu, bukan menambah unit. Selama porsi serialnya tidak berubah, penambahan unit hanya menggeser speedup sedikit demi sedikit menuju angka batas yang sama. Perlu dicatat pula bahwa rumus Amdahl mengukur beban kerja tetap, sedangkan hukum Gustafson mengukur beban kerja yang tumbuh bersama jumlah unit, sehingga angka yang dilaporkannya lebih ramah bagi paralelisme skala besar.

Tabel speedup dengan Python#

Berkas amdahl.py berisi fungsi speedup_amdahl yang menghitung rumus Amdahl untuk porsi $f$ dan $n$ unit apa pun, lalu mencetak tabel untuk f = 0.9 dan f = 0.5 pada beberapa pilihan $n$ , ditambah satu baris batas ketika $n$ menuju tak hingga. Jalankan berkasnya, lalu bandingkan laju kenaikan kedua kolomnya.

python amdahl.py

"""Tabel speedup hukum Amdahl untuk dua porsi kerja dan beberapa jumlah unit.

Rumus yang dihitung: S = 1 / ((1 - f) + f / n), dengan f porsi kerja yang
dipercepat dan n banyaknya unit paralel. Baris "batas" menghitung keadaan
n menuju tak hingga, yaitu suku f / n yang menghilang dari pembagi.
"""

F_PORSI = (0.9, 0.5)             # dua porsi kerja yang dipercepat
N_UNIT = (1, 2, 4, 8, 16, 1000)  # beberapa pilihan jumlah unit paralel


def speedup_amdahl(f, n):
    """Speedup maksimal hukum Amdahl untuk porsi f dan n unit paralel."""
    return 1.0 / ((1.0 - f) + f / n)


header = f"{'n':>5} | {'S (f = 0.9)':>11} | {'S (f = 0.5)':>11}"
print(header)
print("-" * len(header))
for n in N_UNIT:
    s = [speedup_amdahl(f, n) for f in F_PORSI]
    print(f"{n:>5} | {s[0]:>11.2f} | {s[1]:>11.2f}")
batas = [speedup_amdahl(f, float("inf")) for f in F_PORSI]
print(f"{'batas':>5} | {batas[0]:>11.2f} | {batas[1]:>11.2f}")

text Keluaran

    n | S (f = 0.9) | S (f = 0.5)
---------------------------------
    1 |        1.00 |        1.00
    2 |        1.82 |        1.33
    4 |        3.08 |        1.60
    8 |        4.71 |        1.78
   16 |        6.40 |        1.88
 1000 |        9.91 |        2.00
batas |       10.00 |        2.00

Kolom f = 0.9 bergerak cepat pada awalnya, dari 1.00 menuju 4.71 pada delapan unit, tetapi menambah unit dari 8 menjadi 16 hanya menaikkan speedup dari 4.71 ke 6.40, dan seribu unit masih berhenti di 9.91 dari batas atas 10.00. Kolom f = 0.5 menunjukkan batas atas yang jauh lebih rendah, yaitu 2.00, dan empat unit saja sudah menyentuh 1.60 dari angka itu. Efisiensi tiap unit juga turun seiring bertambahnya unit, karena speedup 6.40 yang dicapai 16 unit berarti tiap unit hanya menyumbang 40 persen kemampuan idealnya. Pola pada kedua kolom itulah alasan keputusan tentang paralelisme selalu diawali pertanyaan tentang besarnya porsi yang benar-benar dapat dipercepat.

Kesalahan umum#

Kesalahan pertama adalah mengukur kedua waktu pada kondisi yang tidak setara. Speedup hanya bermakna apabila $T_{\text{lama}}$ dan $T_{\text{baru}}$ diukur pada beban kerja yang sama dan data masukan yang sama, dengan selisih satu-satunya berupa perubahan yang sedang diuji. Membandingkan program lama pada data kecil dengan program baru pada data besar menghasilkan angka yang terlihat mengesankan tetapi tidak menjelaskan apa pun. Simpan dua pengukuran sebagai sepasang catatan yang menyebut beban kerjanya, lalu hitung speedup dari pasangan itu.

Kesalahan kedua adalah memperlakukan $S_{\text{maks}}$ sebagai target yang pasti dicapai. Rumus Amdahl mengasumsikan tiap unit bekerja tanpa biaya tambahan, pembagian kerjanya rata sempurna, dan jalur data tidak menjadi sengketa, sedangkan unit paralel nyata membayar biaya koordinasi dan membagi lebar pita memori yang sama. Speedup nyata selalu berada di bawah rumusnya, dan jarak keduanya justru informasi berharga tentang biaya paralelisme pada sistem yang diukur. Perlakukan hasil rumus sebagai batas atas, bukan sebagai prediksi.

Kesalahan ketiga adalah memaksakan paralelisasi pada porsi serial. Speedup yang kecil bukan tanda rumusnya gagal atau pengukurannya keliru, melainkan sering kali merupakan kesimpulan utamanya, yaitu porsi yang dapat dipercepat ternyata kecil. Angka itu menunjuk keputusan yang lebih berdampak, seperti mengurangi pekerjaan yang berjalan satu demi satu atau mempercepat bagian yang tidak dapat dibagi, sebelum menambah unit paralel apa pun.

Ringkasan#

Speedup adalah perbandingan $T_{\text{lama}}$ terhadap $T_{\text{baru}}$ yang menyatakan berapa kali lipat pekerjaan menjadi lebih cepat.
Hukum Amdahl menghitung $S_{\text{maks}} = \frac{1}{(1-f) + \frac{f}{n}}$ dengan $f$ porsi yang dipercepat dan $n$ unit paralel, karena porsi serial $1-f$ tidak ikut memendek.
Ketika $n$ menuju tak hingga, speedup berhenti di $\frac{1}{1-f}$ , yaitu 10 untuk porsi 90 persen dan 2 untuk porsi separuh.
Tabel dari amdahl.py memperlihatkan keuntungan unit tambahan yang makin mengecil, sehingga memperkecil porsi serial lebih menentukan daripada menambah unit.

Referensi#

Computer Systems: A Programmer’s Perspective — Carnegie Mellon University — Buku yang membahas hukum Amdahl sebagai penghitung speedup maksimal pada bab ukuran performa.
6.004 Computation Structures — MIT OpenCourseWare — Materi kuliah yang memakai hukum Amdahl saat menakar batas perbaikan performa perangkat keras.