PENGANTAR
Keberhasilan usaha produsen alat pemroses untuk meningkatkan kecepatan prosessor sangat signifikan. Evolusi perkembangan ini semakin membuktikan Hukum Moore yang menyatakan bahwa produsen keping prosessor setiap tiga tahun akan dapat menciptakan generasi baru dengan jumlah transistor empat kali lipat pada setiap keping (Stallings, 2003). Stallings (2003) juga memberikan fakta sejak intel meluncurkan keluarga prosessor X86 pada tahun 1978, penambahan rangkaian baru dan pengurangan jarak antar rangkaian dapat meningkatkan kecepatan dan kinerja mikroprosessor sebesar empat kali atau lima kali setiap tiga tahun.
Fog (2008) menggambarkan pada sebuah mikroprosessor sederhana, semua instruksi ditangani dalam dua langkah, yaitu decoding dan eksekusi. Mikroprosessor dapat menghemat waktu eksekusi instruksi dengan men-decode sebuah instruksi selama proses eksekusi instruksi lain sedang dikerjakan. Prinsip ini disebut dengan pipelining. Pipelining, merupakan fitur standar prosesor tipe RISC (Reduced Instruction Set Computing), yang dapat digambarkan persis seperti barisan antrian. Menurut Gajski dkk. (1992) teknik pipelining membagi instruksi kedalam stage-stege dan menempatkan (latched) stage satu setelah stage lainnya. Dalam kondisi ini prosesor dapat mengerjakan langkah-langkah instruksi lainnya pada waktu yang sama, sehingga beberapa instruksi dapat dieksekusi dalam periode waktu yang singkat (http://cse.stanford.edu), sehingga Pipelining dapat meningkatkan kinerja prosessor (Gajski dkk., 1992).
Lebih lanjut Fog (2008) mengungkapkan permasalahan muncul ketika prosessor harus mengkesekusi percabangan instruksi. Percabangan instruksi merupakan implementasi dari what of analysis if-then-else. Yaitu ketika if pada kondisi true, maka proses akan menuju ke lokasi lain, dan jika if kondisi false maka prosessor akan mengeksekusi instruksi selanjutnya. Hal tersebut mengakibatkan delay pada aliran intstruksi yang melalui pipeline, karena prosessor tidak mengetahui instruksi mana yang harus dieksekusi sampai selesai melaksanakan instruksi percabangan. Kondisi ini akan mengganggu aliran kerja konstan mikroprosessor yang berakibat menurunnya kecepatan eksekusi instruksi (Stallings, 2003).
Semakin panjang pipelines mengakibatkan waktu tunggu juga semakin lama dan berakhir sampai diketahui instruksi yang akan dimasukkan ke dalam pipelines diketahui (Fog, 2008). Mikroprosessor modern cenderung mempunyai pipelines yang panjang, sehingga percabangan yang terjadi akan menjadikan permasalahan performance prosessor. Stallings (2003) memberikan beberapa teknik untuk mempertahankan kecepatan atau kinerja optimal pada desain prosessor, yaitu Branch Prediction, Data Flow Analysis, dan Speculative Execution.
Pada paper ini akan dibahas tentang Branch Prediction sebagai teknik penting untuk menjaga performance prosessor modern (Heil dkk., 1999) dan sebagai solusi untuk penanganan permasalahan percabangan (dependensi) instruksi pada pipelines (Stallings, 2003; Fog, 2008).CARA KERJA BRANCH PREDICTORS
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 informasi2. 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
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
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)
(b)Gambar 5. Model prediksi percabangan menggunakan bimodial prediction. (a) Diagram state; (b) Penggunaan diagram state pada tabel pipelines. Sumber : Co (2001).
DAFTAR PUSTAKA
Acιiçmez, O., Ç.K. Koç, dan J.P. Seifert. On the Power of Simple Branch Prediction Analysis. http://eprint.iacr.org/2006/351.pdf. Tanggal akses 12 November 2008, Jam 07.02.
Co, M. 2001. Intro to Branch Prediction. Department of Computer Science University of Virginia. http://www.cs.virginia.edu/~skadron/cs654/slides/bpred.ppt. Tanggal Akses 12 November 2008, Jam 07.30.
Fog, A. 2008. Branch prediction in the Pentium family: How the branch prediction mechanism in the Pentium has been uncovered with all its quirks, and the incredibly more effective branch prediction in the later versions. http://www.x86.org/ articles/branch/ branchprediction.htm. Tanggal Akses 11 November 2008, Jam 17.00 WIB.
Gajski, D.D., N.D. Dutt, A.C-II Wu, dan S.Y-L. Lin. 1992. High-Level Synthesis Introduction to Chip and System Design. Kluwer Academic Publisher. Boston/Dordrecht/London. 358p.
Heil, T.H., Z. Smith, dan J.E. Smith. 1999. Improving Branch Predictors by Correlating on Data Values. http://www.ece.wisc.edu/~jes/papers/micro99.heil.pdf. tanggal akses 11 November 2008, Jam 17.10 WIB.
Jiménez, D.Á. Recent Advances in Branch Prediction. Department of Computer Science Rutgers, The State University of New Jersey. http://ce.et.tudelft.nl/ cecoll/slides/06/0516jimenez.ppt. Tanggal akses 11 November 2008. 20.30.
Stallings, W. 2003. Computer Organization and Architecture: Designing for Performance. Sixth Edition. Prentice-Hall (Person Education, Inc.). New Jersey. 815p.
http://cse.stanford.edu/class/sophomore-college/projects-00/ risc/pipelining/index.html. Tanggal akses 12 November 2008, Jam 07.17.
Tidak ada komentar:
Posting Komentar