Branch Prediction
Dalam arsitektur komputer, sebuah prediktor cabang adalah sirkuit digital yang mencoba untuk menebak mana cara cabang (misalnya struktur if-then-else ) akan pergi sebelum ini diketahui pasti. Tujuan dari cabang prediktor adalah untuk meningkatkan aliran dalam pipa instruksi. Prediktor cabang penting dalam pipelined hari ini mikroprosesor untuk mencapai tinggi kinerja.
Dua arah percabangan biasanya diimplementasikan dengan lompat bersyarat instruksi. Sebuah lompat bersyarat dapat menjadi "tidak diambil" dan melanjutkan eksekusi dengan cabang pertama dari kode yang mengikuti segera setelah lompat bersyarat - atau dapat "diambil" dan melompat ke tempat yang berbeda di memori program dimana cabang kedua kode adalah disimpan.
Hal ini tidak diketahui secara pasti apakah lompat bersyarat akan diambil atau tidak diambil sampai kondisi telah dihitung dan lompat bersyarat telah lulus tahap eksekusi instruksi dalam pipa.
Tanpa prediksi cabang, prosesor harus menunggu sampai instruksi jump bersyarat telah lulus tahap mengeksekusi sebelum instruksi berikutnya dapat memasuki tahap fetch dalam pipa. Prediktor cabang mencoba untuk menghindari pemborosan waktu dengan mencoba untuk menebak apakah lompat bersyarat yang paling mungkin diambil atau tidak diambil. Cabang yang diduga sebagai yang paling mungkin adalah kemudian diambil dan dieksekusi spekulatif . Jika kemudian mendeteksi bahwa menebak salah maka instruksi spekulatif dieksekusi atau dijalankan sebagian dibuang dan pipa dimulai atas dengan cabang yang benar, menimbulkan penundaan.
Waktu yang terbuang dalam kasus misprediction cabang adalah sama dengan jumlah tahap dalam pipa dari tahap fetch ke tahap mengeksekusi. Mikroprosesor modern cenderung memiliki jaringan pipa yang cukup panjang sehingga penundaan misprediction adalah antara 10 dan 20 siklus clock . Semakin lama semakin tinggi pipa kebutuhan untuk prediksi cabang yang baik.
Pertama kalinya sebuah instruksi jump bersyarat yang dihadapi, tidak ada banyak informasi untuk dasar prediksi di. Tetapi prediksi cabang menyimpan catatan dari apakah cabang diambil atau tidak diambil. Ketika bertemu dengan lompat bersyarat yang telah dilihat beberapa kali sebelum maka dapat dasar prediksi pada sejarah masa lalu. Prediktor cabang mungkin, misalnya, mengakui bahwa lompat bersyarat diambil lebih sering daripada tidak, atau bahwa itu adalah diambil setiap kali kedua.
Prediksi cabang tidak sama dengan prediksi cabang sasaran . Prediksi cabang mencoba untuk menebak apakah lompatan bersyarat akan diambil atau tidak. Cabang prediksi target yang mencoba untuk menebak target lompatan bersyarat atau tanpa syarat diambil sebelum dihitung oleh decoding dan melaksanakan instruksi itu sendiri. Cabang cabang prediksi dan prediksi target sering dikombinasikan ke dalam sirkuit yang sama.
Data flow analysis
Data flow analysis adalah teknik untuk mengumpulkan informasi tentang kemungkinan himpunan nilai-nilai dihitung pada berbagai titik dalam sebuah program komputer . Sebuah program grafik kontrol aliran (CFG) digunakan untuk menentukan bagian-bagian dari program yang nilai tertentu yang ditugaskan untuk variabel 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 analisis aliran data dari program adalah untuk mengatur aliran data persamaan untuk setiap simpul dari graf aliran kontrol dan memecahkan mereka dengan berulang kali menghitung output dari input lokal di setiap node sampai seluruh sistem stabil, yaitu, itu mencapai fixpoint . Pendekatan umum dikembangkan oleh Gary Kildall saat mengajar di Naval Postgraduate School.
Specualtive Execution
Pendekatan eksekusi spekulatif memanfaatkan kelimpahan meningkatnya siklus pengolahan cadang untuk mengotomatisasi prefetching untuk aplikasi warung pada disk I / O. Biasanya, ketika aplikasi membutuhkan beberapa data yang tidak di memori, ia akan mengeluarkan permintaan disk dan kemudian kios menunggu bahwa permintaan untuk menyelesaikan. Daripada hanya membuang-buang siklus pengolahan yang tidak terpakai saat aplikasi yang terhenti pada I / O, pendekatan eksekusi spekulatif menggunakan siklus ini untuk mencoba untuk menemukan dan memulai prefetching untuk kebutuhan masa depan aplikasi data yang macet dengan menjalankan menjelang eksekusi mereka terhenti. Secara khusus, pendekatan ini mengasumsikan bahwa ini spekulatif pra-eksekusi kode aplikasi akan cukup mirip dengan masa normal eksekusi aplikasi (non-spekulatif) bahwa ia akan menghadapi akses yang sama untuk non-penduduk data. Berdasarkan asumsi ini, eksekusi spekulatif upaya untuk meningkatkan kinerja aplikasi berikutnya dengan mengubah setiap akses tersebut kepada prefetches.
Gambar dibawah menggambarkan bagaimana pendekatan ini bisa memberikan perbaikan kinerja substansial untuk aplikasi hipotetis yang mengakses empat non-residen halaman data tersebar di tiga disk. Untuk mempermudah, asumsikan bahwa aplikasi mengeksekusi untuk satu juta siklus antara masing-masing akses tersebut, dan bahwa disk dapat melayani permintaan dalam tiga juta siklus. Saat aplikasi ini dijalankan, biasanya pelaksanaannya akan bergantian antara pengolahan dan mengulur-ulur pada I / O. Jika pendekatan eksekusi spekulatif yang diterapkan kemudian, ketika warung eksekusi normal pada pertama permintaan I / O, eksekusi akan terus spekulasi. Setiap kali eksekusi spekulatif pertemuan akses ke data yang non-residen, itu malah akan mengeluarkan panggilan prefetch non-blocking. Dengan cara ini, mungkin dapat melakukan prefetching untuk semua akses berikutnya aplikasi data. Ketika permintaan disk yang asli selesai, eksekusi normal akan melanjutkan. Sekarang, bagaimanapun, selanjutnya data yang mengakses akan keluar dilayani dari memori utama, mengurangi separuh waktu eksekusi aplikasi.
Perlu dicatat bahwa eksekusi spekulatif tidak akan efektif dalam semua kasus. Misalnya, akan menawarkan tidak memberikan manfaat pada sistem di mana CPU, memori atau disk sudah dimanfaatkan sepenuhnya. Juga, suatu proses spekulatif salah akan memprediksi masa depan jika mereka mengakses bergantung pada data yang bukan penduduk. Namun, keberhasilan kami dalam menerapkan eksekusi spekulatif untuk berbagai aplikasi benchmark menunjukkan bahwa independen I / O akses yang umum.
Tidak ada komentar:
Posting Komentar