Eksekusi Luar Urutan

Eksekusi luar urutan memungkinkan prosesor mengeksekusi instruksi segera setelah operandnya siap, daripada secara ketat sesuai urutan program, menggunakan penggantian nama register dan penyangga untuk menampilkan paralelisme sambil tetap menghasilkan hasil dalam urutan.

Definition

Eksekusi luar urutan adalah teknik mikroarsitektural di mana prosesor secara dinamis menyusun ulang eksekusi instruksi untuk menjalankan instruksi independen kapan pun operandnya tersedia, sambil menggunakan penyangga dan penggantian nama untuk mempertahankan tampilan penyelesaian sekuensial, dalam urutan.

Scope

Topik ini mencakup penjadwalan dinamis: stasiun reservasi, penggantian nama register untuk menghilangkan dependensi palsu, penyangga penyusunan ulang yang memberlakukan komit dalam urutan, dan pemulihan eksekusi spekulatif. Ini dibangun langsung di atas algoritma Tomasulo. Ini tidak termasuk prediksi arah cabang (prediksi cabang) dan gagasan yang lebih luas tentang seberapa banyak paralelisme yang ada (paralelisme tingkat instruksi), berfokus pada mekanisme penyusunan ulang itu sendiri.

Core questions

• Bagaimana prosesor dapat mengeksekusi instruksi di luar urutan program namun menghasilkan hasil yang benar dan dalam urutan?
• Bagaimana penggantian nama register menghilangkan dependensi tulis-setelah-baca dan tulis-setelah-tulis?
• Apa kontribusi stasiun reservasi dan penyangga penyusunan ulang?
• Bagaimana pengecualian dan kesalahan prediksi dipulihkan secara tepat dalam inti luar urutan?

Key concepts

• penjadwalan dinamis
• stasiun reservasi
• penggantian nama register
• bus data umum
• penyangga penyusunan ulang
• komit dalam urutan
• pengecualian yang tepat
• pemulihan eksekusi spekulatif

Key theories

Algoritma Tomasulo

Skema Tomasulo menggunakan stasiun reservasi dan bus data umum untuk mengganti nama register dan mengirim instruksi ke unit fungsional saat operandnya tersedia, memungkinkan eksekusi luar urutan yang hanya menghormati dependensi data yang sebenarnya.

Pengecualian yang tepat melalui komit dalam urutan

Penyangga penyusunan ulang menampung hasil instruksi luar urutan dan melakukan komitnya dalam urutan program, sehingga pengecualian dan kesalahan prediksi dapat ditangani secara tepat seolah-olah eksekusi telah dilakukan secara ketat berurutan.

Mechanisms

Instruksi yang telah didekode diganti namanya ke register fisik dan ditempatkan di stasiun reservasi atau antrean masalah, di mana mereka menunggu operand yang disiarkan pada bus hasil. Ketika siap, mereka dieksekusi pada unit fungsional yang tersedia dalam urutan apa pun. Penyangga penyusunan ulang melacak urutan program asli dan melakukan komit hasil secara berurutan, membuang hasil spekulatif pada kesalahan prediksi atau pengecualian sehingga status arsitektur selalu tepat.

Clinical relevance

Eksekusi luar urutan adalah mesin inti CPU berkinerja tinggi, menyembunyikan latensi memori dan eksekusi dengan menemukan pekerjaan independen yang harus dilakukan. Ini juga memiliki implikasi keamanan: karena pekerjaan spekulatif, luar urutan dapat secara transien mengakses data sebelum dibatalkan, ini memungkinkan kelas serangan saluran samping mikroarsitektural Spectre dan Meltdown.

History

Tomasulo memperkenalkan penjadwalan dinamis di IBM System/360 Model 91 pada tahun 1967. Kombinasi dengan penyangga penyusunan ulang untuk pengecualian yang tepat, yang dikembangkan pada tahun 1980-an, membuat eksekusi luar urutan praktis untuk prosesor tujuan umum, dan menjadi standar dalam desain berkinerja tinggi dari pertengahan 1990-an dan seterusnya.

Debates

Kinerja versus kompleksitas, daya, dan keamanan

Eksekusi luar urutan memberikan kinerja utas tunggal yang kuat tetapi dengan biaya yang signifikan dalam kompleksitas perangkat keras dan daya, dan spekulasinya telah terbukti dapat dieksploitasi; ini memicu perdebatan tentang seberapa agresif berspekulasi versus mendukung desain yang lebih sederhana, lebih efisien, atau lebih aman.

Key figures

• Robert Tomasulo
• Yale Patt
• James E. Smith
• John L. Hennessy

Seminal works

• tomasulo1967
• hennessy2019

Frequently asked questions

Jika instruksi dieksekusi di luar urutan, bagaimana program masih benar?

Prosesor hanya menyusun ulang eksekusi, bukan hasilnya. Penggantian nama register memastikan ia menghormati dependensi data yang sebenarnya, dan penyangga penyusunan ulang melakukan komit hasil dalam urutan program asli, sehingga status arsitektur yang terlihat persis seperti yang akan dihasilkan oleh eksekusi sekuensial.

Apa itu penggantian nama register?

Penggantian nama register memetakan register arsitektur yang disebutkan dalam instruksi ke kumpulan register fisik yang lebih besar. Ini menghilangkan dependensi palsu (nama) yang muncul dari penggunaan kembali nama register, memungkinkan lebih banyak instruksi independen dieksekusi secara paralel tanpa konflik atas penyimpanan register.