Branch Prediction DataFlow Analysis Speculative Execution

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 moderndalam 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 baikGambar 1. Branch Predictor melalui speculative execution. Sumber: Heil dkk. (1992)

Sampai saat ini, hampir seluruh kondisi Branch Predictorsmasih 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-valuedengan 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.

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.

– 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 adalah teknik untuk mengumpulkan informasi tentang kemungkinan himpunan nilai-nilai dihitung di berbagai titik di sebuah program komputer. Kontrol aliran Sebuah program grafik (CFG) digunakan untuk menentukan bagian-bagian dari program dimana nilai tertentu ditugaskan ke variabel yang mungkin merambat. Informasi yang dikumpulkan sering digunakan oleh compiler ketika mengoptimalkan program. Sebuah contoh kanonik dari analisis data-aliran mencapai definisi.

Sebuah cara sederhana untuk melakukan Data-Flow Analysis program adalah untuk mengatur aliran data persamaan untuk setiap node dari grafik kontrol aliran dan menyelesaikannya dengan berulang kali menghitung output dari input lokal di setiap node sampai seluruh sistem stabil,sampai mencapai sebuah fixpoint. Pendekatan umum ini dikembangkan oleh Gary Kildall saat mengajar di Naval Postgraduate School.
Eksekusi spekulatif dalam sistem komputer adalah melakukan pekerjaan, yang hasilnya mungkin tidak diperlukan. Teknik optimasi kinerja digunakan dalam prosesor pipelined dan systems.School lainnya.

MAIN IDEA ~
Eksekusi spekulatif adalah optimasi kinerja. Ide utama adalah untuk melakukan pekerjaan yang mungkin tidak diperlukan. Targetnya adalah untuk menyediakan konkurensi lebih jika sumber daya tambahan yang tersedia. Teknologi berikut menggunakan ide ini:

Prefetching dalam memori dan sistem file
Cabang prediksi
Kontrol konkurensi Optimis dalam sistem database

Prosesor
Pipelined mikroprosesor modern menggunakan eksekusi spekulatif untuk mengurangi biaya instruksi cabang bersyarat menggunakan skema yang memprediksi jalur eksekusi dari suatu program berdasarkan sejarah eksekusi cabang . Ternyata bahwa dalam rangka meningkatkan kinerja dan pemanfaatan sumber daya komputer, beberapa instruksi harus dijadwalkan terlebih dahulu di tempat yang tidak ditentukan bahwa instruksi tersebut harus dieksekusi sama sekali, di depan cabang.

Dalam optimasi compiler untuk sistem multiprocessing, eksekusi spekulatif melibatkan prosesor menganggur mengeksekusi kode di blok prosesor berikutnya, dalam hal tidak ada ketergantungan pada kode yang dapat berjalan pada prosesor lainnya. Keuntungan dari skema ini adalah mengurangi waktu respon untuk prosesor individu dan sistem secara keseluruhan. Namun, ada hukuman bersih untuk kasus rata-rata, karena dalam kasus taruhan yang buruk, pipa harus memerah. Compiler terbatas dalam mengeluarkan instruksi eksekusi spekulatif, karena memerlukan bantuan perangkat keras untuk buffer efek spekulasi-instruksi dieksekusi. Tanpa dukungan hardware, compiler hanya bisa mengeluarkan instruksi spekulatif yang memiliki efek samping dalam hal spekulasi yang salah.

Eager Executionadalah bentuk eksekusi spekulatif di mana kedua sisi cabang kondisional dijalankan, namun hasil berkomitmen hanya jika predikat benar. Dengan sumber daya terbatas, eksekusi bersemangat (juga dikenal sebagai eksekusi oracle) akan dalam teori memberikan kinerja yang sama seperti prediksi cabang yang sempurna. Dengan sumber daya yang terbatas ingin eksekusi harus digunakan hati-hati karena jumlah sumber daya yang dibutuhkan tumbuh secara eksponensial dengan masing-masing tingkat cabang dieksekusi bersemangat

Lazy Evaluation tidak berspekulasi. Penggabungan eksekusi spekulatif dalam implementasi dari bahasa pemrograman Haskell merupakan topik penelitian saat ini. Haskell bersemangat dirancang di sekitar gagasan eksekusi spekulatif. Versi terbaru dukungan GHC jenis eksekusi spekulatif dengan mekanisme aborsi untuk kembali dalam kasus pilihan yang buruk disebut eksekusi optimisasi.