Pertemuan II Branch Prediction Data Flow Analysis Speculative Execution Pipelining

Dalam arsitektur komputer, sebuah Branch Prediction adalah sirkuit digital yang mencoba untuk menebak arah mana cabang (misalnya struktur if-then-else) akan pergi sebelum keadaannya diketahui pasti. Tujuan dari Branch Predictor untuk meningkatkan aliran dalam pipa instruksi. Branch Prediction penting dalam mikroprosesor pipelined untuk mencapai kinerja tinggi. Dua arah percabangan biasanya diimplementasikan dengan instruksi lompat bersyarat. Melonjaknya 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 itu disimpan. Tanpa prediksi cabang, prosesor harus menunggu sampai instruksi lompat bersyarat telah melewati tahap mengeksekusi sebelum instruksi berikutnya dapat memasuki tahap fetch dalam pipa. Prediktor cabang upaya 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 yang diambil dan spekulasi kemudian dieksekusi. Jika kemudian mendeteksi bahwa ada kesalahan menebak maka instruksi dieksekusi spekulatif atau sebagian dieksekusi dibuang dan pipa dimulai dari atas dengan cabang yang benar. Waktu yang terbuang dalam kasus misprediction cabang sama dengan jumlah tahap dalam pipa dari tahap ke tahap fetch mengeksekusi. Mikroprosesor modern cenderung memiliki pipa yang cukup panjang sehingga penundaan misprediction adalah antara 10 dan 20 siklus clock. Semakin lama pipa tinggi kebutuhan untuk prediksi cabang makin baik. Pertama kali instruksi lompat bersyarat ditemui, tidak ada banyak informasi untuk dasar prediksi ini. Tapi prediksi cabang menyimpan catatan dari apakah cabang diambil atau tidak diambil. Ketika bertemu dengan lompat bersyarat yang telah melihat beberapa kali sebelum kemudian dapat dasar prediksi pada kejadian yang lalu. Branch prediction mungkin, misalnya, mengakui bahwa lompat bersyarat diambil lebih sering daripada tidak, atau bahwa itu diambil setiap dua kali. branch prediction tidak sama dengan prediksi cabang target. Prediksi cabang upaya 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 mengeksekusi instruksi itu sendiri. Cabang cabang prediksi dan prediksi target sering dikombinasikan ke dalam sirkuit yang sama. 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. 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 Kontrol konkurensi Optimis dalam sistem database 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 Execution adalah 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. Pipelining Pengertian : Pipeline adalah kerja paralel, dimana komputer mengerjakan 2 atau lebih bagian dari instruksi secara bersamaan Pipelining adalah teknik yang digunakan untuk merealisasi Parallel Processing, yaitu dengan membagi operasi ke dalam k-stage (beberapa tingkatan) atau sub-operasi, sehingga pada satu saat ada k operasi berjalan yang sekaligus. Pipelining adalah salah satu cara yang paling sering digunakan dalam pararel prosesing. Sebuah operasi dibagi menjadi sejumlah sub operasi elementer, kita namakan k. kemudian kita membentuk sebuah sistem dengan banyak stage sebesar k, dan mengeksekusi sub operasi tersebut pada setiap stage satu demi satu. Pipelining adalah suatu teknik instruksi yang digunakan dalam desain komputer dan perangkat elektronik digital lainnya untuk meningkatkan instruksi throughput (jumlah instruksi yang dapat dijalankan pada waktu yang sama). Contoh : gambar dibawah adalah generik pipa dengan 4 tahapan: 1. Fetch 2. Membaca sandi 3. Menjalankan 4. Write-back Abu-abu atas kotak daftar tunggu instruksi yang akan dilaksanakan; bagian bawah kotak abu-abu adalah daftar instruksi yang telah selesai, dan tengah kotak putih adalah pipa. Pelaksanaan adalah sebagai berikut: Waktu Eksekusi Empat menunggu instruksi yang akan dilaksanakan 1 hijau instruksi yang diambil dari memori 2 hijau adalah instruksi decoded ungu adalah instruksi yang diambil dari memori 3 hijau instruksi dijalankan (sebenarnya dilakukan operasi) ungu adalah instruksi yang decoded biru instruksi yang diambil 4 hijau instruksi dari hasil ditulis kembali ke daftar file atau memori ungu instruksi yang dijalankan biru adalah instruksi decoded merah instruksi yang diambil 5 hijau instruksi selesai ungu instruksi yang ditulis kembali biru instruksi dijalankan merah adalah instruksi decoded 6 The purple instruksi selesai biru instruksi yang ditulis kembali merah instruksi dijalankan 7 biru instruksi selesai merah instruksi yang ditulis kembali 8 merah instruksi selesai 9 Semua instruksi dijalankan Kekurangan pada Pipeline adalah dalam prakteknya, bagaimanapun, prosesor RISC beroperasi lebih dari satu siklus per instruksi. Prosesor mungkin mengumpulkan hasil dari data dependensi dan instruksi cabang. Data dependensi terjadi bila instruksi tergantung pada hasil dari instruksi sebelumnya. Instruksi tertentu mungkin perlu data dalam register yang belum disimpan, sejak itulah pekerjaan yang sebelumnya instruksi yang belum mencapai tahap yang akan di pipeline. sebagai contoh: add $r3, $r2, $r1 add $r5, $r4, $r3 Dalam contoh ini, instruksi pertama memberitahu prosesor untuk menambahkan isi register r1 dan r2 dan menyimpan hasilnya dalam register r3. Instruksi kedua untuk menambahkan r3 dan r4 dan simpan ke r5. Tempat ini kita set instruksi dalam pipeline. Ketika terjadi instruksi yang kedua itu adalah tahap kedua, prosesor akan mencoba untuk membaca r3 dan r4 dari register. Ingat, meskipun, yang pertama adalah instruksi hanya satu langkah di depan kedua, jadi isi r1 dan r2 sedang ditambahkan, tetapi hasilnya belum ditulis ke dalam daftar r3. Instruksi yang kedua itu tidak dapat dibaca dari register R3 karena belum ditulis dan belum harus menunggu hingga data yang diperlukan disimpan. Akibatnya, pipa yang stalled dan sejumlah kosong instruksi dikenal sebagai gelembung pergi ke dalam pipa. Data dependensi mempengaruhi Pipelines lebih panjang daripada yang singkat karena memerlukan waktu yang lebih lama untuk instruksi untuk mencapai akhir pendaftaran tahap-menulis pipa yang panjang. MIPS solusi untuk masalah ini adalah kode reordering. Jika, seperti dalam contoh di atas, berikut ini ada petunjuk tidak ada hubungannya dengan dua pertama, kode dapat diatur ulang sehingga instruksi yang dijalankan di antara dua tergantung petunjuk dan pipa dapat mengalir efisien. Tugas kode reordering umumnya mengkompile ke kiri, yang mengakui data dependensi dan upaya untuk meminimalkan kinerja.