Di hampir semua program komputer, ada bagian kode yang bercabang menjadi jalur terpisah. Misalnya, pernyataan if-then-else memiliki dua kemungkinan hasil. Pernyataan ini tidak menimbulkan masalah apa pun pada prosesor berurutan, karena CPU memproses setiap perintah secara berurutan. Cabang menghadirkan masalah besar bagi prosesor pipelined, karena banyak instruksi dieksekusi sekaligus.
Skenario
Dalam kasus program dengan pernyataan bercabang dengan dua kemungkinan hasil, dua jalur kode yang mungkin tidak boleh berada di tempat yang sama. Pemrosesan yang diperlukan untuk menyelesaikan salah satu opsi akan berbeda. Jika tidak, program tidak akan bercabang. Kemungkinan akan ada cukup banyak pernyataan percabangan yang hanya pernah diambil sekali, seperti pernyataan if.
Ada juga pernyataan percabangan yang membentuk loop. Meskipun ini mungkin tidak umum secara numerik seperti pernyataan sekali pakai, mereka umumnya diulang secara statistik. Dapat diasumsikan bahwa kemungkinan besar sebuah cabang akan membawa Anda kembali berputar-putar daripada tidak.
Mengapa Ini Masalah?
Tidak masalah bagaimana masalah ini diungkapkan dalam prosesor yang sepenuhnya berurutan. Ini bukan masalah. Cabang mana yang akan diambil diketahui sebelum bagian pertama dari instruksi berikut diproses.
Namun, dalam prosesor pipelined, instruksi berikut diantrekan. Mereka sudah diproses ketika prosesor tahu cabang mana yang diambil. Jadi bagaimana seharusnya prosesor menangani skenario ini? Ada beberapa pilihan. Yang terburuk adalah hanya menunggu dan membiarkan pipa menganggur sementara menunggu jawaban di cabang mana yang akan diambil. Ini berarti bahwa setiap kali Anda memiliki pernyataan percabangan, Anda akan selalu kehilangan setidaknya siklus waktu prosesor sebanyak yang Anda miliki tahapan dalam pipa.
Atau, Anda dapat mencoba menjalankan kedua opsi di saluran dan membuang pilihan yang salah. Ini akan memiliki setengah hukuman untuk tidak melakukan apa-apa tetapi masih dikenakan hukuman kinerja pada setiap pernyataan bercabang. Mengingat bahwa CPU modern juga dapat menjalankan instruksi yang rusak, Anda berpotensi mencoba menjalankan setiap instruksi percabangan sesegera mungkin. Jadi hasilnya diketahui sebelum dibutuhkan. Opsi ini dapat membantu, kecuali tidak dapat diskalakan. Misalkan Anda memiliki kepadatan pernyataan percabangan yang relatif tinggi. Dalam hal ini, Anda tidak akan dapat menjalankan semuanya lebih awal tanpa memiliki waktu menganggur.
Bagaimana Masalah Ini Benar-Benar Ditangani?
Pada kenyataannya, prosesor menyertakan prediktor cabang. Peramal cabang mencoba menebak hasil pilihan percabangan mana yang akan diambil. Prosesor kemudian mengasumsikan bahwa prediksi itu benar dan menjadwalkan instruksi. Jika peramal cabang akurat, tidak ada penalti kinerja.
Jika peramal cabang membuat kesalahan, Anda harus menyiram pipa dan mulai memproses hasil yang sebenarnya. Ini menghasilkan penalti kinerja yang sedikit lebih buruk daripada tidak melakukan apa-apa dan hanya menunggu hasilnya. Untuk mendapatkan kinerja terbaik, penting untuk memastikan bahwa prediktor cabang seakurat mungkin. Ada berbagai pendekatan yang berbeda untuk ini.
Kode yang Cocok
Dalam kode mesin, cabang selalu merupakan pilihan antara membaca instruksi berikutnya atau melompat ke satu set instruksi di tempat lain. Beberapa implementasi awal dari prediktor cabang hanya berasumsi bahwa semua cabang akan selalu atau tidak akan pernah diambil. Implementasi ini dapat memiliki tingkat keberhasilan yang sangat baik jika kompiler mengetahui perilaku ini dan dirancang untuk menyesuaikan kode mesin sehingga hasil yang paling mungkin selaras dengan umum prosesor anggapan. Ini membutuhkan banyak penyetelan dan penyesuaian kebiasaan pengembangan perangkat lunak.
Alternatif lain adalah belajar dari statistik bahwa loop umumnya diambil dan selalu melompat jika cabang mundur dalam aliran instruksi dan jangan pernah melompat jika lompatannya ke depan karena itu biasanya keadaan yang secara statistik lebih kecil kemungkinannya untuk meninggalkan a lingkaran. Ini adalah kedua jenis prediksi cabang statis, di mana hasil cabang diprediksi pada waktu kompilasi.
Prediktor Cabang Dinamis
Prediktor cabang modern bersifat dinamis, menggunakan statistik dari program yang sedang berjalan untuk mencapai tingkat keberhasilan prediksi yang lebih baik. Penghitung jenuh adalah dasar untuk semua prediktor cabang saat ini. Tebakan pertama diputuskan secara statis atau acak. Setelah cabang diambil atau tidak diambil, hasilnya disimpan dalam sebagian memori. Saat berikutnya cabang yang sama muncul, prediktor cabang memprediksi hasil yang sama seperti sebelumnya.
Ini secara alami menghasilkan tingkat prediksi yang baik untuk loop. Ada dua versi tentang ini. Versi awal hanya menggunakan satu bit data untuk menunjukkan apakah cabang diambil atau tidak. Versi selanjutnya menggunakan dua bit untuk menunjukkan pilihan yang diambil dengan lemah atau kuat atau tidak. Setup ini masih dapat memprediksi hasil dari mengambil loop jika program kembali ke sana, umumnya meningkatkan tingkat keberhasilan.
Pola Pelacakan
Untuk melacak pola, beberapa prediktor cabang melacak riwayat pilihan apa yang diambil. Sebagai contoh, anggaplah sebuah loop dipanggil secara terus-menerus tetapi hanya loop sekitar empat kali sebelum keluar dari loop. Dalam hal ini, prediktor adaptif dua tingkat dapat mengidentifikasi pola ini dan memprediksinya terjadi lagi. Ini meningkatkan tingkat keberhasilan lebih jauh melalui penghitung jenuh sederhana. Prediktor cabang modern membangun ini lebih lanjut dengan menggunakan jaringan saraf untuk melihat dan memprediksi pola.
Beberapa prediktor cabang menggunakan beberapa algoritma dan kemudian membandingkan hasilnya untuk memutuskan prediksi mana yang akan digunakan. Beberapa sistem melacak setiap instruksi percabangan secara terpisah dalam apa yang disebut prediksi cabang lokal. Lainnya menggunakan sistem prediksi cabang global untuk melacak semua instruksi percabangan terbaru. Keduanya memiliki kegunaan dan kekurangannya masing-masing.
Kesimpulan
Sebuah prediktor cabang adalah bagian khusus dari CPU pipa. Ia mencoba untuk memprediksi hasil dari instruksi percabangan sebelum instruksi yang sebenarnya diproses. Ini adalah fungsi inti dari CPU pipelined karena memungkinkan CPU untuk menjaga pipeline tetap jenuh meskipun tidak yakin instruksi apa yang perlu dijalankan. Mereka tidak menawarkan pengurangan kinerja ketika mereka benar. Algoritma modern dapat akurat dalam beban kerja yang relatif dapat diprediksi sebanyak 97% dari waktu.
Tidak ada metode prediksi yang sempurna, sehingga implementasinya bervariasi. Dampak kinerja dari membuat prediksi yang salah tergantung pada panjang pipa. Secara khusus, panjang pipa sebelum dapat ditentukan jika prediksi itu salah. Itu juga tergantung pada berapa banyak instruksi di setiap tahap pipa. CPU desktop kelas atas modern memiliki sekitar 19 tahapan pipeline dan dapat menjalankan setidaknya empat instruksi secara bersamaan di setiap tahapan.