Prediksi Cabang dan Spekulasi

Mengapa pipeline membutuhkan prediksi cabang, cara predictor bekerja, dan biaya salah prediksi.

Daftar isi

Pada pipeline lima tahap, hasil perbandingan instruksi cabang seperti beq baru diketahui pada tahap EX, yaitu tahap eksekusi di ALU, sementara pipeline sudah mengambil dua instruksi berikutnya di jalur yang belum tentu benar. Topik ini membahas cara pipeline tetap berjalan penuh di hadapan ketidakpastian itu, yaitu dengan menebak jalur lalu mengeksekusi lebih dulu berdasarkan tebakannya. Pembahasan mencakup tiga predictor, yaitu komponen yang menebak hasil cabang, mulai dari yang paling sederhana sampai penghitung saturasi dua bit, kemudian mengukur akurasinya pada pola perulangan yang diketahui serta menghitung biaya setiap tebakan yang meleset.

Mengapa cabang menghentikan pipeline#

Semua instruksi selain cabang melanjutkan ke alamat berikutnya, sehingga tahap IF tidak pernah salah memilih alamat. Instruksi cabang berbeda karena beq membandingkan dua register dan keputusan perpindahan PC baru jatuh setelah ALU menyelesaikan pengurangannya pada tahap EX. Pada saat itu, tahap IF dan ID sudah memproses dua instruksi di jalur berurutan, dan keduanya harus dibuang apabila cabang ternyata diambil (taken).

Cara yang paling aman adalah membekukan pengambilan instruksi sampai keputusan jatuh, sehingga setiap cabang menimbulkan dua siklus tanpa kemajuan. Harga itu terasa besar karena instruksi cabang muncul sangat sering pada program nyata, biasanya sekitar seperlima dari seluruh instruksi yang dieksekusi pada beban kerja umum. Perulangan memperparah keadaannya karena cabang penutup perulangan dieksekusi berulang kali dan diambil pada hampir setiap putaran. Perulangan lima iterasi misalnya mengeksekusi cabang penutupnya lima kali, yaitu empat kali diambil dan satu kali tidak, sehingga pipeline tanpa prediksi membayar sepuluh siklus kosong hanya untuk cabang tersebut. Membayar dua siklus untuk setiap eksekusi cabang membuat keuntungan throughput pipeline menyusut secara nyata.

Prediksi jalur dan spekulasi#

Spekulasi adalah mengeksekusi instruksi yang arahnya belum pasti berdasarkan sebuah tebakan, dan prediksi cabang adalah tebakan itu sendiri. Apabila tebakannya benar, pipeline berjalan penuh tanpa stall, yaitu tanpa siklus yang terbuang. Apabila tebakannya meleset, seluruh instruksi spekulatif yang sudah berada di dalam pipeline dibuang melalui proses yang disebut flush, lalu pengambilan instruksi dimulai ulang dari jalur yang benar. Tebakan dan pembuangan harus dipahami sebagai satu kesatuan, karena tanpa pembuangan yang bersih, instruksi spekulatif akan menulis register dan memori dengan hasil yang tidak seharusnya.

Predictor paling sederhana adalah selalu tidak-taken (always-not-taken), yaitu selalu menebak bahwa cabang tidak diambil sehingga pipeline terus mengambil instruksi secara berurutan. Tebakan ini tidak membutuhkan tabel maupun keadaan tersimpan, dan benar setiap kali cabang memang tidak diambil, misalnya pada percabangan yang menangani kasus langka. Untuk pola perulangan, tebakan ini buruk karena cabang penutup perulangan diambil pada setiap putaran kecuali putaran terakhir. Biaya meleset pada pipeline lima tahap yang menyelesaikan cabang di tahap EX adalah dua siklus per kejadian, yaitu dua instruksi spekulatif yang sudah berada di tahap IF dan ID.

Predictor satu bit dan dua bit#

Predictor satu bit menyimpan hasil terakhir setiap cabang dan menebak bahwa hasil berikutnya sama dengan hasil terakhir. Predictor ini menyesuaikan diri dengan pola yang mapan, tetapi meleset dua kali pada setiap putaran perulangan, yaitu saat keputusan terakhir putaran melawan tebakannya dan saat keputusan pertama putaran berikutnya masih terpengaruh hasil itu. Satu bit keadaan ternyata terlalu rapuh untuk pola yang paling sering muncul pada program nyata.

Penghitung saturasi dua bit (two-bit saturating counter) menaikkan ketahanan itu satu tingkat. Keadaannya adalah bilangan dua bit yang naik setiap hasil diambil dan turun setiap hasil tidak diambil, dengan batas atas 3 dan batas bawah 0. Tebakan diambil hanya bila nilainya minimal 2, sehingga satu hasil yang melawan pola hanya menurunkan keadaan satu tingkat dan tidak langsung membalik tebakannya. Sifat ini disebut saturasi, yaitu keadaan menempel di batasnya alih-alih meluber. Tabel berikut memuat keempat keadaannya.

Nilai	Keadaan	Tebakan	Setelah diambil	Setelah tidak diambil
0	N kuat	tidak diambil	1	0
1	N lemah	tidak diambil	2	0
2	T lemah	diambil	3	1
3	T kuat	diambil	3	2

Predictor yang lebih besar mengikuti gagasan yang sama, yaitu menyimpan riwayat yang lebih panjang, misalnya dua tingkat sejarah hasil atau gabungan beberapa predictor yang dipilih otomatis. Semua bentuk itu tetap menghasilkan tebakan biner, diambil atau tidak, yang digunakan tahap IF pada siklus berikutnya. Prinsip satu bit dan dua bit tetap menjadi dasar seluruh bentuk lanjutannya.

Simulasi pola perulangan#

Berkas prediksi.py mensimulasikan predictor satu bit dan dua bit pada pola yang sama, yaitu empat kali diambil lalu satu kali tidak, pola yang persis dihasilkan cabang penutup perulangan dengan lima iterasi. Pola itu diulang empat putaran sehingga totalnya dua puluh keputusan cabang, dan keadaan awal kedua predictor adalah tidak diambil. Simulator mencetak tabel per keputusan yang memuat hasil sebenarnya, tebakan, benar atau salahnya, dan keadaan predictor sesudahnya, kemudian menutup dengan predictor pembanding yang selalu menebak tidak-taken. Keluarannya menandai hasil diambil dengan T dan tidak diambil dengan N. Jalankan berkasnya dan perhatikan keputusan pertama, kelima, dan keenam pada setiap putaran.

python prediksi.py

"""Prediktor cabang 1-bit dan 2-bit pada pola loop yang diketahui.

Pola: empat kali diambil (T) lalu satu kali tidak (N), diulang empat
putaran sehingga total ada dua puluh keputusan cabang.
"""

POLA = ["T", "T", "T", "T", "N"] * 4


def sim_1bit(pola):
    """Prediksi mengikuti hasil terakhir; keadaan awal N."""
    keadaan = "N"
    hasil = []
    for nyata in pola:
        prediksi = keadaan
        keadaan = nyata
        hasil.append((nyata, prediksi, prediksi == nyata, keadaan))
    return hasil


NAMA_2BIT = ("N kuat", "N lemah", "T lemah", "T kuat")


def sim_2bit(pola):
    """Penghitung saturasi dua bit; keadaan awal 0 (N kuat)."""
    keadaan = 0
    hasil = []
    for nyata in pola:
        prediksi = "T" if keadaan >= 2 else "N"
        if nyata == "T":
            keadaan = min(keadaan + 1, 3)
        else:
            keadaan = max(keadaan - 1, 0)
        hasil.append((nyata, prediksi, prediksi == nyata, NAMA_2BIT[keadaan]))
    return hasil


def cetak(judul, hasil):
    benar = sum(1 for h in hasil if h[2])
    print(judul)
    print(f"{'no':>3}  {'nyata':<5}  {'prediksi':<8}  {'hasil':<6}  keadaan")
    for i, (nyata, prediksi, ok, keadaan) in enumerate(hasil, start=1):
        print(f"{i:>3}  {nyata:<5}  {prediksi:<8}  {'benar' if ok else 'salah':<6}  {keadaan}")
    print(f"akurasi: {benar}/{len(hasil)} = {100 * benar / len(hasil):.1f}%")
    print()


cetak("Prediktor 1-bit, keadaan awal N", sim_1bit(POLA))
cetak("Prediktor 2-bit, keadaan awal N kuat", sim_2bit(POLA))

benar_n = sum(1 for nyata in POLA if nyata == "N")
print(f"Pembanding, selalu tidak-taken: akurasi {benar_n}/{len(POLA)} = {100 * benar_n / len(POLA):.1f}%")

text Keluaran

Prediktor 1-bit, keadaan awal N
 no  nyata  prediksi  hasil   keadaan
  1  T      N         salah   T
  2  T      T         benar   T
  3  T      T         benar   T
  4  T      T         benar   T
  5  N      T         salah   N
  6  T      N         salah   T
  7  T      T         benar   T
  8  T      T         benar   T
  9  T      T         benar   T
 10  N      T         salah   N
 11  T      N         salah   T
 12  T      T         benar   T
 13  T      T         benar   T
 14  T      T         benar   T
 15  N      T         salah   N
 16  T      N         salah   T
 17  T      T         benar   T
 18  T      T         benar   T
 19  T      T         benar   T
 20  N      T         salah   N
akurasi: 12/20 = 60.0%

Prediktor 2-bit, keadaan awal N kuat
 no  nyata  prediksi  hasil   keadaan
  1  T      N         salah   N lemah
  2  T      N         salah   T lemah
  3  T      T         benar   T kuat
  4  T      T         benar   T kuat
  5  N      T         salah   T lemah
  6  T      T         benar   T kuat
  7  T      T         benar   T kuat
  8  T      T         benar   T kuat
  9  T      T         benar   T kuat
 10  N      T         salah   T lemah
 11  T      T         benar   T kuat
 12  T      T         benar   T kuat
 13  T      T         benar   T kuat
 14  T      T         benar   T kuat
 15  N      T         salah   T lemah
 16  T      T         benar   T kuat
 17  T      T         benar   T kuat
 18  T      T         benar   T kuat
 19  T      T         benar   T kuat
 20  N      T         salah   T lemah
akurasi: 14/20 = 70.0%

Pembanding, selalu tidak-taken: akurasi 4/20 = 20.0%

Baris akurasi pada ketiga bagian keluaran membandingkan tiga strategi pada pola yang sama. Strategi selalu tidak-taken mencatat 20 persen karena pola ini memang didominasi cabang yang diambil. Predictor satu bit mencapai 60 persen dengan delapan keputusan yang salah, dan seluruhnya berada pada dua posisi yang berulang, yaitu keputusan pertama yang masih menyimpan keadaan awal, keputusan terakhir setiap putaran yang melawan tebakan diambil, serta keputusan pertama putaran berikutnya yang terpengaruh hasil itu.

Predictor dua bit mencapai 70 persen dengan enam keputusan yang salah. Dua kesalahan pertama terjadi saat penghitung masih naik dari keadaan awalnya, sedangkan empat sisanya masing-masing satu per putaran, tepat pada keputusan kelima yang menutup putaran. Satu hasil tidak diambil hanya menurunkan penghitung dari T kuat ke T lemah, sehingga tebakan untuk empat keputusan berikutnya tetap diambil dan benar seluruhnya. Selisih sepuluh poin terhadap predictor satu bit sepenuhnya berasal dari satu keputusan yang selamat per putaran.

Untuk melihat ringkasannya saja, jalankan perintah berikut dari direktori topik.

bash

# tampilkan hanya baris akurasi dari keluaran simulator
python3 prediksi.py | grep akurasi

text Keluaran

akurasi: 12/20 = 60.0%
akurasi: 14/20 = 70.0%
Pembanding, selalu tidak-taken: akurasi 4/20 = 20.0%

Biaya salah prediksi per instruksi#

Akurasi predictor baru menjadi bermakna setelah dikaitkan dengan harganya dalam siklus. Model yang paling sederhana menghitung tambahan siklus rata-rata per instruksi dari tiga besaran, yaitu frekuensi cabang $f$ terhadap seluruh instruksi, tingkat salah prediksi $p$ , dan biaya flush dua siklus untuk pipeline yang menyelesaikan cabang di tahap EX. Nilai CPI, singkatan cycles per instruction atau rata-rata jumlah siklus per instruksi, idealnya tepat satu untuk pipeline.

\text{CPI} = 1 + f \times p \times 2

Dengan $f$ sebesar dua puluh persen dan $p$ sebesar sepuluh persen, tambahannya adalah $0{,}2 \times 0{,}1 \times 2 = 0{,}04$ , sehingga CPI menjadi 1,04 dan pipeline hanya kehilangan empat persen dari performa idealnya. Naikkan $p$ menjadi tiga puluh persen dan biayanya menjadi $0{,}12$ siklus per instruksi, tiga kali lebih mahal, tanpa mengubah satu instruksi pun pada programnya. Perhitungan inilah yang menjadikan predictor bagian tetap dari prosesor modern, karena selisih beberapa persen akurasi langsung terbaca pada setiap instruksi yang dieksekusi. Sisi keamanan dari spekulasi, yaitu jejak yang bisa diukur dari eksekusi yang belum pasti, dibahas pada modul Kenyataan Perangkat Keras Modern.

Kesalahan umum#

Kesalahan pertama adalah menilai predictor dari satu pola saja. Simulator pada topik ini menunjukkan selisih akurasi yang besar antara pola dan jenis predictor, sehingga satu angka pada satu pola tidak dapat digeneralisasi ke beban kerja lain. Perbaikannya adalah mengukur predictor pada pola yang sama ketika membandingkannya, sebagaimana keluaran simulator membandingkan ketiga strategi pada satu pola.

Kesalahan kedua adalah mengira flush mengulang instruksi yang sudah selesai. Flush hanya membuang instruksi spekulatif yang belum mencapai tahap WB, sehingga tidak ada register maupun memori yang tertulis dua kali. Apabila sebuah implementasi menulis register dari instruksi spekulatif, bug-nya berada pada posisi pembuangannya, bukan pada predictor.

Kesalahan ketiga adalah menyamakan persentase cabang yang diambil dengan akurasi predictor. Persentase yang diambil adalah properti program, sedangkan akurasi adalah properti predictor pada program tersebut, dan keduanya baru berguna setelah dihitung pada pola yang sama.

Kesalahan keempat adalah mengira predictor ikut menebak alamat tujuan cabang. Semua predictor pada topik ini hanya menebak arahnya, sedangkan alamat tujuan dihitung dari PC dan offset yang tersimpan di dalam instruksinya. Predictor nyata memang menyimpan alamat tujuan dalam tabel tersendiri, tetapi mekanisme itu berdiri di samping tebakan arah, bukan menggantikannya.

Ringkasan#

Cabang menyimpan ketidakpastian arah PC sampai tahap EX, sehingga pipeline yang tidak menebak harus membekukan pengambilan instruksi dua siklus untuk setiap cabang.
Spekulasi menjalankan instruksi dari jalur tebakan, predictor selalu tidak-taken berjalan tanpa tabel, tetapi buruk untuk perulangan, predictor satu bit menyesuaikan diri tetapi meleset dua kali per putaran, dan penghitung saturasi dua bit mentolerir satu hasil yang melawan pola.
Salah prediksi dibayar dengan flush, yaitu membuang instruksi spekulatif dan memulai ulang pengambilan dari jalur yang benar, dengan biaya dua siklus pada pipeline yang menyelesaikan cabang di tahap EX.
Tambahan siklus rata-rata per instruksinya adalah $f \times p \times 2$ , sehingga selisih kecil pada akurasi predictor langsung terlihat pada performa keseluruhan.

Referensi#

Computer Systems: A Programmer’s Perspective — Carnegie Mellon University — Buku yang membahas prediksi cabang, biaya salah prediksi, dan flush pada pembahasan pipelining prosesor modern.
6.004 Computation Structures — MIT OpenCourseWare — Materi kuliah yang menyajikan predictor satu bit dan dua bit dalam konteks pipeline lima tahap.