Teknik Yang dikembangkan untuk meningkatkan kinerja komputer

Branch Prediction : teknik dimana prosesor memungkinkan mengamati terlebih dahulu di dalam software dan melakukan prediksi percabangan atau kelompok instruksi yang akan di eksekusi berikutnya. Program yang terdiri dari kelompok perintah bercabang sering digunakan dalam pemrograman.
• Pada CPU yang mendukung perintah pencabangan, CPU membutuhkan cukup banyak clock cycle, mengingat CPU menempatkan semuanya pada pipeline dan menemukan perintah berikutnya yang akan dieksekusinya.
• Sirkuit untuk branch prediction melakukan pekerjaan ini bekerja sama dengan pipeline, yang dilakukan sebelum proses di ALU dilaksanakan, dan memperkirakan hasil dari pencabangan tersebut.
• Jika CPU berfikir bahwa branch akan menuju suatu cabang, biasanya berdasarkan pekerjaan sebelumnya, maka perintah berikutnya sudah dipersiapkan untuk dieksekusi berikut data-datanya, bahkan dengan adanya pipeline ini, bila tidak diperlukan suatu referensi dari instruksi terakhir, maka bisa dilaksanakan dengan segera, karena data dan instruksi yang dibutuhkan telah dipersiapkan sebelumnya.


Perkembangan branch predictor ditentukan diantaranya oleh 3 (tiga) kategori dasar 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)

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


* Data Flow Analysis : proses pengumpulan informasi temtang cara bagaimana variabel- variabel dipakai dalam program.
* Speculative execution : dengan modal prediksi cabang dan analisis data, maka prosesor dapat melakukan eksekusi spekulatif terlebih dahulu sebelum waktunya.

• CPU akan menggunakan melakukan perhitungan pada pipeline yang berbeda berdasarkan kemungkinan yang diperkirakan oleh komputer.
• Jika kemungkinan yang dilakukan oleh komputer tepat, maka hasilnya sudah bisa diambil langsung dan tinggal melanjutkan perintah berikutnya
• Jika kemungkinan yang diperkirakan oleh komputer tidak tepat, maka akan dilaksanakan kemungkinan lain sesuai dengan logika instruksi tersebut.