1/1/2007
Instruction Execution Phases
Instruction Pipeline Design Hendra Rahmawan 23206017
Instruction Execution Phases
z
Pipelined Instruction Processing Suatu instruksi yang dieksekusi biasanya terdiri atas urutan dari operasi-operasi (stages) : (F)etches, (D)ecode, (I)ssue, (E)xecute, (W)riteback. z Adanya stages memungkinkan untuk melakukan l k k pipelining. i li i z
Instruction Execution Phases
1
1/1/2007
Instruction Execution Phases
Mechanisms for Instruction Pipelining Untuk ‘melancarkan’ aliran pada pipeline z Terdiri atas beberapa strategi : z
Prefetch Buffers Multiple Functional Units z Internal Data Forwarding z Hazard Avoidance z z
Mechanisms for Instruction Pipelining z
Mechanisms for Instruction Pipelining
Prefetch Buffers z
z
z
Meningkatkan performa pada Fetch stage dengan menambah beberapa buffer instruksi yang akan diumpankan pada pipeline stages berikutnya. Mempertimbangkan 2 jenis pipelining : insequence, out-of-sequence(branching target). 3 Jenis Buffer FIFO : z z z
Sequential BufferÆin-sequence Target BufferÆout-of-sequence Loop Buffer
2
1/1/2007
Mechanisms for Instruction Pipelining z
Multiple Functional Units z
z z
Suatu stage dalam da a pipeline p pe e dapat menimbulkan e bu a masalah ketika stage ini banyak dikunjungi (dapat dilihat dari reservation table)Æ bottleneck. Solusi : dibuat beberapa copy dari stage yang sama dan akan berjalan secara simultan. Model yang diajukan Sohi(1990): z
z
Menggunakan Reservation Station (RS) sebagai “ruang tunggu” bagi instruksi-instruksi yang mengalamai masalah data dependence ataupun resource dependence sebelum memasuki stage. RS juga digunakan sebagai antarmuka antara (D)ecode dan (I)ssue unit dengan pipelined functional units lainnya. Tag Unit akan memonitor penggunaan RS dan registers.
Mechanisms for Instruction Pipelining z
Mechanisms for Instruction Pipelining
Mechanisms for Instruction Pipelining
Internal Data Forwarding z
z
z
Beberapa operasi memory memory-access access dapat digantikan dengan dengan operasi register transer. Dengan demikian akan mengurangi memory traffic yang akan menghasilkan waktu eksekusi yang lebih pendek. Ada 3 jenis DF : z z z
Store-load forwarding Load-load forwarding Store-store forwarding
3
1/1/2007
Mechanisms for Instruction Pipelining
Mechanisms for Instruction Pipelining z
Hazard Avoidance z
z
Read dan Write pada shared variables oleh instruksi-instruksi yang berbeda berpotensi menghasilkan nilai yang berbeda (tidak diinginkan) ketika urutan instruksi tidak semestinyaÆHazards. Ada 3 jenis logic hazards : z z z
z
Mechanisms for Instruction Pipelining
Read-after-Write (RAW) hazardÆflow dependece W it ft W it (WAW) hazardÆoutput Write-after-Write h dÆ t t dpendence d d Write-after-Read (WAR) hazardÆantidependence
Hazards yang terkandung dalam instruksi-instruksi harus ditanggulangi sebelum memasuki pipeline.
Mechanisms for Instruction Pipelining z
Hazard Avoidance z
Kondisi-kondisi yang memungkinkan munculnya hazards (necessary but not sufficient) : R(I) ∩ D(J) ≠ ∅ pada RAW hazard R(I) ∩ R(J) ≠ ∅ pada WAW hazard z D(I) ∩ R(J) ≠ ∅ pada d WAR h hazard d z z
4
1/1/2007
Dynamic Instruction Scheduling Untuk memperkecil waktu eksekusi pipeline i li maka k perlu l dil dilakuka k k scheduling h d li terhadap instruksi-instruksi. z Ada 2 jenis scheduling : z
Dynamic Instruction Scheduling z
Static Scheduling z
z
Static scheduling z Dynamic scheduling z
z z
Dynamic Instruction Scheduling z
Tumasulo’s Algorithm z z
z
z
Hardware dependence dependence-resolution resolution scheme scheme. Menggunakan arsitektur hardware seperti pada model Sohi(1990). Pada Model 91 : 3 RS pada floating-poing adder dan 2 pasang RS pada floating-poing multiplier. Meresolve resource conflicts dan data dependences dengan menggunakan register tagging untuk mengalokasikan atau mendealokasikan source dan destination register.
Data ata dependencies depe de c es a antar-instruksi ta st u s a akan a menimbulkan interlocked relationship antarinstruksiÆexecution time menjadi lama karena harus ada proses menunggu data. Static scheduling oleh compiler dapat meningkatkan pemisahan antara interlocked instructions. Static scheduling oleh compiler lebih murah untuk dii l diimplementasikan. t ik Pada high performance computer diperlukan special hardware untuk melakukan dynamic scheduling.
Dynamic Instruction Scheduling z
Tumasulo’s Algorithm z z
z z z
Issued instruction yang operandnya belum lengkap diforward k sebuah ke b h RS milik ilik ffunctional ti l unit it yang akan k di digunakan. k Instruksi tersebut akan menunggu hingga data dependeces telah diresolve sehingga operandnya menjadi lengkap/tersedia. Proses resolve dilakukan dengan memonitor result bus (common bus). Setelah seluruh operand lengkap, instruksi akan dikrim ke functional unit untuk dieksekusi. Seluruh register yang digukanan dalam eksekusi instruksi ((working g register) g ) akan dcatat/dimonitor ((tagged). gg ) Jika ada instruksi lain issued, tetapi source register sedang digunakan (busy) maka tag untuk source register akan diforward ke suab RS. Ketika register sudah tidak digunakan, tag tersebut (tag di RS) akan menysinyalkan hal tersebut.
5
1/1/2007
Dynamic Instruction Scheduling
Dynamic Instruction Scheduling z
CDC Scoreboarding z
z
z
z
Dynamic Instruction Scheduling
Menggunakan multiple functional units+instruction buffer, tampak sebagai multiple execution pipelines. Adanya parallel units memungkinkan instruksiinstruksi tereksekusi sempurna di luar urutan program semestinya. Instruksi-instruksi akan selalu dimasukkan (issued) ke functional unit meskipun datanya belum lengkap (karena reigster masih digunakan). Menggunakan scoreboard untuk menentukan rute yang sesuai antara execution unts dengan register.
Branch Handling Technique Performa dari pipelined processor dib t i oleh dibatasi l h adanya d d data t d dependeces d dan branch instructions. z Data dependences dapat ditangani dengan instructions scheduling. z Branch instructions yang sarat dengan probabilitas juga harus diatasi dengan strategi-strategi yang baik. z
6
1/1/2007
Branch Handling Technique z
Branching Problem
Branch Handling Technique z
Effect of Branching Adanya penalti akibat munculnya delay slot (jumlah pipeline cycle yang terbuang (tak berguna) antara branch taken dan branch target. z Throughput dari pipeline harus dihitung d dengan melibatkan lib tk penalti lti tersebut. t b t z
Branch Handling Technique z
Effect of Branching
Branch Handling Technique z
Effect of Branching
7
1/1/2007
Branch Handling Technique z
Branch Handling Technique
Branch Prediction z
z z
z
Branch ((taken or not taken)) dapat p diprediksi p berdasarkan code types secara statistik atau berdasarkan branch history selama suatu program dieksekusi. Hasil prediksi (taken or not taken) biasanya ditanamkan (wired) ke dalam prosesorÆstatic, semi-static. Dynamic branch strategy menggunakan recent branch history untuk memprediksi. Agar akurat idealnya seluruh history digunakan untuk memprediksiÆinfeasibleÆdibatasi pada recent history y Biasanya menggunakan BTB (Branch Target Buffer) untuk menyimpan recent branch information
Branch Handling Technique z
Delayed Branches Mereduksi/meminimasi delay slot (b) bahkan kalau bisa hingga 0 penalti. z Menyusun ulang susunan instruksi-instruksi dalam suatu program sehingga branch instructions terjadi pada waktu yang akan d t datang. z Memindahkan useful instruction ke dalam usefull slot. z
8
