Prosesor modern adalah superscalar, yaitu, mereka dapat menjalankan beberapa instruksi secara bersamaan. Misalnya, beberapa prosesor dapat memproses dari empat hingga enam instruksi per siklus. Selain itu, banyak prosesor seperti itu mampu memulai instruksi rusak: mereka dapat mulai bekerja dengan perintah yang terletak di kode jauh kemudian.
Pada saat yang sama, kode sering berisi cabang (
if–then ). Cabang-cabang tersebut sering diimplementasikan sebagai "transisi", di mana prosesor dapat melanjutkan untuk menjalankan instruksi di bawah kode atau melanjutkan jalur saat ini.
Dengan eksekusi perintah superscalar yang rusak, percabangan menjadi sulit. Untuk ini, prosesor memiliki blok prediksi cabang yang canggih. Artinya, prosesor sedang mencoba untuk memprediksi masa depan. Ketika dia melihat cabang, dan karena itu transisi, dia mencoba menebak ke arah mana program akan berjalan.
Sangat sering ini bekerja dengan baik. Sebagai contoh, sebagian besar loop diimplementasikan sebagai cabang. Pada akhir setiap iterasi loop, prosesor harus memprediksi apakah iterasi berikutnya akan dilakukan. Seringkali lebih aman bagi prosesor untuk memprediksi bahwa siklus akan berlanjut (selamanya). Dalam hal ini, prosesor secara keliru memprediksi hanya satu cabang per siklus.
Ada contoh umum lainnya. Jika Anda mengakses konten array, maka banyak bahasa pemrograman menambahkan "memeriksa terikat" - pemeriksaan tersembunyi dari kebenaran indeks sebelum mengakses nilai array. Jika indeks tidak benar, kesalahan dihasilkan, jika tidak kode terus dieksekusi dengan cara biasa. Pemeriksaan perbatasan dapat diprediksi, karena dalam situasi normal semua operasi akses harus benar. Akibatnya, sebagian besar prosesor seharusnya memprediksi hasil dengan sempurna.
Apa yang terjadi jika percabangan sulit diprediksi?
Di dalam prosesor, semua instruksi yang telah dieksekusi tetapi berada pada cabang yang diprediksi salah harus dibatalkan, dan perhitungan harus dimulai lagi. Diharapkan bahwa untuk setiap kesalahan prediksi cabang kami membayar lebih dari 10 siklus. Karena itu, waktu pelaksanaan program dapat meningkat secara signifikan.
Mari kita lihat kode sederhana di mana kita menulis bilangan bulat acak ke dalam array keluaran:
while (howmany != 0) { out[index] = random(); index += 1; howmany--; }
Kami dapat menghasilkan angka acak yang cocok rata-rata selama 3 siklus. Artinya, total keterlambatan generator angka acak dapat sama dengan 10 siklus. Tetapi prosesor kami adalah superscalar, yaitu, kami dapat melakukan beberapa perhitungan angka acak secara bersamaan. Oleh karena itu, kami akan dapat menghasilkan angka acak baru kira-kira setiap 3 siklus.
Mari kita ubah fungsi sedikit sehingga hanya angka ganjil ditulis ke array:
while (howmany != 0) { val = random(); if( val is an odd integer ) { out[index] = val; index += 1; } howmany--; }
Anda mungkin secara naif berpikir bahwa fitur baru ini mungkin lebih cepat. Dan faktanya, karena kita perlu mencatat rata-rata hanya satu dari dua bilangan bulat. Ada cabang dalam kode, tetapi untuk memeriksa paritas bilangan bulat, cukup periksa satu bit.
Saya membandingkan kedua fungsi ini dalam C ++ pada prosesor Skylake:
Fungsi kedua bekerja sekitar lima kali lebih lama!
Adakah yang bisa diperbaiki di sini? Ya, kita bisa menghilangkan percabangan saja. Integer ganjil dapat dikarakterisasi sedemikian rupa sehingga merupakan bitwise logis DAN dengan nilai 1 sama dengan satu. Caranya adalah dengan menambah indeks array dengan satu hanya jika nilai acaknya ganjil.
while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; }
Dalam versi baru ini, kami selalu menulis nilai acak ke array output, bahkan jika itu tidak diperlukan. Sepintas, ini adalah pemborosan sumber daya. Namun, itu menyelamatkan kita dari cabang-cabang yang diprediksi secara keliru. Dalam praktiknya, kinerjanya hampir sama dengan kode asli, dan jauh lebih baik daripada versi dengan cabang:
Bisakah kompiler menyelesaikan masalah ini sendiri? Secara umum, jawabannya adalah tidak. Terkadang kompiler memiliki opsi untuk sepenuhnya menghilangkan percabangan, bahkan jika ada pernyataan
if-then dalam kode sumber. Misalnya, percabangan kadang-kadang dapat diganti dengan "conditional move" atau trik aritmatika lainnya. Namun, trik semacam itu tidak aman untuk digunakan dalam kompiler.
Kesimpulan penting: percabangan yang diprediksi secara keliru bukanlah masalah yang tidak signifikan, ia memiliki pengaruh yang besar.
Kode sumber saya ada di Github .
Membuat tolok ukur adalah tugas yang sulit: prosesor belajar untuk memprediksi percabangan
[Catatan terjemahan: bagian ini adalah
artikel terpisah dari penulis, tetapi saya menggabungkannya dengan yang sebelumnya, karena mereka memiliki tema yang sama.]
Pada bagian sebelumnya, saya menunjukkan bahwa sebagian besar waktu eksekusi suatu program dapat disebabkan oleh prediksi cabang yang salah. Tolok ukur saya adalah menulis 64 juta nilai integer acak ke sebuah array. Ketika saya mencoba untuk merekam hanya angka acak ganjil, kinerja karena prediksi yang salah sangat menurun.
Mengapa saya menggunakan 64 juta bilangan bulat, bukan, katakanlah, 2000? Jika Anda menjalankan hanya satu tes, maka itu tidak masalah. Namun, apa yang akan terjadi jika kita melakukan banyak upaya? Jumlah cabang yang keliru diprediksi akan dengan cepat turun ke nol. Kinerja prosesor Intel Skylake berbicara untuk dirinya sendiri:
Seperti dapat dilihat dari grafik di bawah ini, "pelatihan" berlanjut lebih jauh. Secara bertahap, proporsi cabang yang diprediksi salah turun menjadi sekitar 2%.
Artinya, jika kita terus mengukur waktu yang diambil oleh tugas yang sama, maka itu menjadi semakin berkurang, karena prosesor belajar untuk memprediksi hasil dengan lebih baik. Kualitas "pelatihan" tergantung pada model prosesor tertentu, tetapi diharapkan prosesor yang lebih baru harus belajar lebih baik.
Prosesor server AMD terbaru belajar untuk memprediksikan percabangan hampir sempurna (dalam 0,1%) dalam waktu kurang dari 10 upaya.
Prediksi ideal pada AMD Roma ini menghilang ketika jumlah nilai dalam masalah meningkat dari 2000 menjadi 10.000: prediksi terbaik berubah dari sebagian kecil kesalahan dari 0,1% menjadi 33%.
Anda mungkin harus menghindari kode pembandingan dengan percabangan untuk tugas-tugas kecil.
Kode github saya .
Pengakuan : Nilai-nilai AMD Rome diberikan oleh Vel Erwan.
Bacaan tambahan :
Kasus untuk (sebagian) prediksi cabang panjang sejarah GEometrik TAgged (Seznec et al.)