Branch in Instruction Pipeline

MASALAH DENGAN BRANCH

Branch atau percabangan instruksi seringkali kita temukan dalam suatu program atau kode. Pada instruction pipelining, sebuah instruksi yang bercabang dapat menimbulkan masalah berupa delay dan kesulitan menentukan instruksi mana yang harus dilakukan setelahnya, seperti yang diilustrasikan berikut:

Misalnya kita memiliki sebuah kode:

Percabangan pada kode di atas terjadi pada baris keempat, yaitu jika r1 (hasil dari pengurangan r2 dengan r3) tidak sama dengan 0, maka langsung loncat ke baris ke-6 (L1). Jika digambarkan dengan ilustrasi sebagai berikut:

Ada dua masalah saat penanganan instruksi baris keempat atau “beqz”.

1. Ketika beqz berada di tahap decode, nilai r1 masih belum ditentukan, karena instruksi yang mengeluarkan r1, yaitu instruksi “sub” masih berada pada tahap execution, sehingga hasil pengurangan (r1) belum ditulis ke memori. Hal ini dapat berakibat pada kesalahan pembacaan r1.
2. Prosesor tidak bisa menentukan instruksi yang harus di-fetch setelah fetch instruksi beqz, karena prosesor belum mengetahui instruksi mana yang harus dipanggil setelah instruksi beqz, apakah “ldi” atau “not”.

Karena pembahasan difokuskan mengenai branch, maka masalah akan difokuskan ke masalah no. 2.

Cara paling mudah untuk menangani hal seperti ini adalah dengan men-stall instruksi setelah instruksi yang bercabang, sehingga kira-kira menjadi seperti ini:

Dengan menggunakan stall seperti ini, maka jika di dalam suatu program terdapat banyak operasi percabangan akan terjadi penguluran waktu yang sangat lama dan mengganggu kinerja program. Ada beberapa teknik untuk menangani percabangan seperti ini, yang akan dibahas di bagian selanjutnya.

TEKNIK PENANGANAN BRANCH

Ada beberapa teknik yang dapat digunakan untuk mengoptimalkan pipeline saat ada branch pada program, diantaranya adalah Delayed Branch, Branch Prediction, dan Multiple Streams.

1. Delayed Branch

Konsep delayed branch adalah mengisi kekosongan yang ditinggalkan karena menunggu pemrosesan instruksi yang mengandung branch dengan mengeksekusi instruksi yang tidak ada hubungannya dengan instruksi yang mengandung branch. Konsep delayed branch dapat dilihat pada ilustrasi berikut (tulisan biru adalah instruksi yang tidak ada hubungannya dengan beqz):

Kelemahan dari cara ini adalah prosesor terkadang tidak bisa menentukan instruksi mana yang harus disimpan setelah branch, sehingga terkadang malah menimbulkan kesalahan yang lebih besar karena salah menyimpan instruksi.

2. Brench Prediction

Branch Prediction adalah cara yang dilakukan untuk menangani branch dengan cara memprediksi instruksi yang akan datang setelah branch. Branch Prediction dilakukan dengan beberapa cara:

a.       Predict always taken, yaitu selalu beranggapan bahwa branch akan selalu menghasilkan jump ke instruksi target, sehingga langsung mengambil instruksi target setelah instruksi branch.

b.       Predict never taken, yaitu selalu beranggapan bahwa jump tidak akan terjadi, sehingga hanya mengambil instruksi selanjutnya dari instruksi branch.

c.       Prediksi berdasarkan heuristik dan statistik. Dengan cara ini, prosesor akan menentukan instruksi yang diproses selanjutnya adalah instruksi target atau bukan dengan mempertimbangkan jenis dari instruksi branch yang ditemui, bergantung pada seberapa sering operasi tersebut menghasilkan jump atau tidak.

d.      Prediksi dengan 2-bit branch prediction. Menggunakan pengalaman sebelumnya untuk menentukan apakah suatu branch akan diambil atau tidak. Jika prediksinya salah 2 kali berturut-turut, barulah pada prediksi selanjutnya akan mengubah keputusan, seperti tergambar pada diagram stata di bawah ini:

e.       Prediksi dengan Branch History Table (BHT). Setiap branch yang pernah ditemui akan dimasukkan dalam sebuah tabel yang berisi 2-bit yang merupakan low-order bit dari branch PC. Dari tabel yang ada, prosesor akan memutuskan apakah branch ini akan diambil atau tidak.

Dan masih banyak cara yang dikembangkan untuk memprediksi branch yang datang.

3. Multiple Streams

Cara lain untuk menangani branch adalah dengan meng-fetch kedua instruksi secara bersamaan menggunakan pipeline yang berbeda. Prosesor kemudian akan memutuskan menggunakan pipeline yang mana setelah branch dieksekusi. Cara ini tentunya termasuk cara yang “mahal”.