Stallings (2003) mendeskripsikan cara kerja teknik Branch Predictors, yaitu prosessor melihat kode instruksi selanjutnya dari memori, kemudian memprediksi percabangan atau kelompok instruksi yang mirip untuk diproses berikutnya. Apabila perkiraan prosessor benar pada bebarapa waktu tertentu, prosessor akan mengambil instruksi-instruksi yang benar dan menyimpannya di dalam buffer, sehingga prosessor selalu dalam keadaan sibuk. Prediksi Branch predictors tidak hanya pada sebuah percabangan selanjutnya, tetapi juga beberapa cabang berikutnya.
Penelitian Branch prediction untuk mendukung performance prosessor modern dalam menangani percabanan instruksi telah banyak dilakukan. Branch Predictor dinamis yang pertama untuk mengambil prediksi percabangan didasarkan pada history informasi lokal. Sejak itu, Branch Predictors mengalami perkembangan yang signifikan. Perkembangan branch predictor ditentukan diantaranya oleh 3 (tiga) kategori dasar (Heil dkk., 1999), yaitu:
1. Penambahan path global dan history informasi
2. Teknik mengkombinasikan antara history global dan lokal
3. Mengurangi hambatan melalui skema peng-indeks-an tabel yang lebih baik
Gambar 1. Branch Predictor melalui speculative execution. Sumber: Heil dkk. (1992)
Sampai saat ini, hampir seluruh kondisi Branch Predictors masih diusulkan menggunakan kontrol aliran informasi sebagai input-input dasar, termasuk percabangan yang dihasilkan atau cabang PC (Program Counter). Disamping meningkatkan jalur yang telah ada, predictors mengkombinasikan tipe informasi yang sama untuk meningkatkan jalur yang baik. Mispredicted pada percabangan mengakibatkan teknik Branch Prediction mempunyai pengaruh yang negattif untuk meningkatkan performance prosessor.
Gambar 1 memberikan ilustrasi metode untuk menintegrasikan data values ke dalam branch prediction yang dikenal sebagai speculative branch execution (Heil dkk. 1992). Fog (2008) memberikan contoh ketika terjadi 4 (empat) kali percabangan pada kondisi yang sama, maka pada pemrosesan berikutnya juga diduga akan terjadi percabangan yang sama. Prediksi ini digunakan oleh mikroprosessor untuk menentukan instruksi yang akan dimasukkan ke dalam pipelines (buffer), sebelum mikroprosesor benar-benar yakin terjadi percabangan pada instruksi. Semua perhitungan yang berdasarkan prediksi akan diabaikan jika prediksinya salah, tetapi apabila prediksi benar maka waktu yang dibutuhkan untuk eksekusi instruksi menjadi lebih singkat (Fog, 2008).
Speculative branch execution membutuhkan satu atau dua akses terhadap tabel serial (tergantung pada data-value predictor yang digunakan) dan menggunakan history percabangan atau data-value, tetapi tidak dapat menggunakan keduanya. Gambar 2 menunjukkan skema speculative branch execution menggunakan prediksi data-value dengan ukuran yang tidak terbatas. Dibandingkan dengan percabangan statis skema tersebut tingkat akurasinya lebih baik (Heil dkk. 1992).
Gambar 2. penggunaan data-values secara langsung untuk memprediksi percabangan.
MISPREDICTED
Gambar 3. mispredicted pada 20 Stage pipelines. Sumber: (Acιiçmez dkk.)
Instruki yang bersifat spekulatif dibuang dari pipelines dan prosessor memulai eksekusi dari jalur setelah terjadinya mispredicted (Acιiçmez dkk.). Pada gambar 3 dapat diperhatikan gambaran “20 stage Misprediction Pipelines” Prosessor Intel Pentium 4, yang menunjukkan alamat ketika terjadi bottlenecks dan eksekusi instruksi spekulatif setelah percabangan. Pada kondisi tersebut, prosessor membutuhkan informasi :
- Hasil percabangan. Prosessor harus mengetahui hasil percabangan (Taken atau Not Taken) untuk mengeksekusi urutan instruksi yang benar. Informasi ini tidak langsung tersedia ketika terjadi percabangan, untuk itu prosessor harus mengeksekusi percabangan untuk memperoleh informasi stages selanjutnya di dalam pipelines untuk diekseskusi. Ketika menunggu hasil percabangan, prosessor mencoba untuk memprediksi urutan instruksi yang akan dieksekusi selanjutnya. Prediksi ini didasarkan pada history percabangan yang sama/mirip antara percabangan sebelumnya yang telah dieksekusi dengan percabangan yang akan diproses.
- Target alamat percabangan. Prosessor mencoba menentukan percabangan ke dalam dua kategori Taken dan Not Taken. Jika prediksi keluar dari Taken, maka instruksi pada alamat target diambil dan dikeluarkan. Pengambilan instruksi dari alamat target membutuhkan informasi alamat tersebut. Seperti halnya hasil percabangan, target alamat juga dimungkinkan tidak tersedia secara langsung. Untuk itu, Prosessor akan mencoba untuk mengambil record target alamat percabangan sebelumnya yang dieksekusi pada pipelines (buffer), yang dikenal dengan Branch Target Buffer (BTB).
Gambar 4. Arsitektur Branch Predictors. Sumber: Acιiçmez dkk.
Gambar 4 mendeskripsikan Branch Prediction Units (BPU) yang terdiri dari 2 bagian utama, yaitu BTB dan Predictor. BTB adalah buffer tempat prosessor menyimpan alamat target pada percabangan sebelumnya. Ketika ukuran buffer terbatas, prosessor cukup menyimpan nomor alamat target pada buffer atau menumpuk/mengganti alamat sebelumnya yang tersimpan di buffer. fungsi dan arsitetektur BTB sangat mirip dengan cache biasa, dan digunakan sebagai cache untuk melihat alamat target percabangan sebelumnya yang menunjuk ke alamat instruksi tertentu. Predictor adalah bagaian dari BPU yang melakukan prediksi hasil percabangan. Yang termasuk bagian-bagian predictor, yaitu Branch History Registers (BHR) seperti Global History Register atau Local History Registers, and Branch Prediction Tables, dan lain-lain (Acιiçmez dkk.).
ALGORITMA BRANCH PREDICTORS
Jiménez memberikan contoh algoritma Branch Predictor sebagai berikut:
Parameter atau variable yang digunakan dalam algoritma:
GHL – Global history length
GHR – Global History shift register
GA – Global Array alamat percabangan sebelumnya
W – n × m × (GHL + 1) array (larik) bertipe small integer
CONTOH PEMANFAATAN BRANCH PREDICTORS
Branch Predictors UltraSPARC-III memiliki (Co, 2001):
• Pipeline 14-stage, prediksi percabangan akan diakses saat mengambil instruksi pada stage 2-3
• 16K-entry 2-bit counter Gshare predictor
– Bimodal predictor, melakukan operasi XOR terhadap bit-bit PC dengan global history register (kecuali 3 bit dibawahnya) untuk mengurangi alias.
• Miss queue
– Membagi mispredict penalty dengan menyediakan instruksi yang siap untuk di proses
Pada UltraSPARC-III yang menggunakan Bimodal Branch Prediction memiliki sebuah tabel masukkan berukuran 2 bit yang berisi salah satu dari 4 state sebagai berikut :
00 : Strongly Not Taken
01 : Weakly Not Taken
10 : Weakly Taken
11 : Strongly Taken
Gambar 5 menunjukkan state dan tebel untuk menggambarkan branch prediction model Bimodal Prediction :
(a)
(b)
Gambar 5. Model prediksi percabangan menggunakan bimodial prediction. (a) Diagram state; (b) Penggunaan diagram state pada tabel pipelines. Sumber : Co (2001).
