مفهوم پردازش خط لوله ای

مفهوم پردازش خط لوله ای

اسلاید 1: مفهوم پردازش خط لوله اي1

اسلاید 2: مفهوم پردازش خط لوله ايمثال: شستن لباسهاAli, Bahram, Cathy, Dara هر كدام مقداري لباس دارند كه مي خواهند بشورند، خشك كنند و اتو كنند. عمل شستن 30 دقيقه طول مي كشد.عمل خشك كردن 40 دقيقه طول مي كشد.اتو زدن 20 دقيقه طول مي كشد.ABCD2

اسلاید 3: لباسشويي به صورت متواليدر انجام متوالي اعمال مذكور 6 ساعت براي كار چهار نفر طول ميكشد.ABCD3040203040203040203040206 PM7891011MidnightTaskOrderTime3

اسلاید 4: لباسشويي به صورت خط لوله ايانجام اعمال مذكور به صورت خط لوله اي 3.5 ساعت براي كار چهار نفر طول ميكشد.ABCD6 PM7891011MidnightTaskOrderTime3040404040204

اسلاید 5: مفهوم پايهخط لوله: چندین دستورالعمل به طور همزمان در حال اجر هستند.خط لوله به بخش ها یا قطعات تقسیم می شود.چرخه ماشین بوسیله کندترین مرحله خط لوله معین می گردد.معمولا چرخه ماشین = پالس ساعت5

اسلاید 6: خط لوله ای کردناگر n تکلیف (Task) داشته باشیم که زمان اجرای هر کدام از آن ها برابر با tn باشد (زمان انجام کل تکالیف = n*tn)، با فرض اینکه تعداد قطعات خط لوله k باشد و هر قطعه در tp انجام پذیر باشد (پالس ساعت = tp):Task اول در k پالس (k*tp) انجام می پذیرد.Task های دیگر هر کدام در پالس زمانی بعدی (یک پالس زمانی) تکمیل خواهند شد، پس زمان لازم برای انجام (n-1) تکلیف دیگر برابر با (n-1)*tp خواهد شد.در نتیجه افزایش سرعت پردازش خط لوله نسبت به پردازش غیر خط لوله ای از فرمول زیر محاسبه می گردد: S = ntn / (k + n - 1)tp6

اسلاید 7: نكاتي در مورد پردازش خط لوله ايپردازش خط لوله اي يك كار خاص را سريعتر نميكند، بلكه توان عملياتي كل را بهبود ميبخشد.سرعت خط لوله توسط كندترين مرحله محدود ميگردد. با استفاده از منابع مختلف چند كار همزمان باهم اجرا ميشوند.در حالت ايده آل، تسريع به تعداد مراحل خط لوله است. مراحل نامتعادل (با زمان اجراي نامساوي) سرعت و كارايي خط لوله را كاهش ميدهد. زماني كه براي پر كردن و خالي كردن خط لوله صرف ميشود نيز باعث كاهش سرعت خط لوله ميگردد.ABCD6 PM789TaskOrderTime3040404040207

اسلاید 8: پنج مرحله سيكل دستورالعملIfetch: Instruction FetchFetch the instruction from the Instruction MemoryReg/Dec: Registers Fetch and Instruction DecodeExec: Calculate the memory addressMem: Read the data from the Data MemoryWr: Write the data back to the register fileCycle 1Cycle 2Cycle 3Cycle 4Cycle 5IfetchReg/DecExecMemWrlw8

اسلاید 9: IF: InstructionFetchID Instr. DecodeReg. Readپنج مرحله مسير داده پردازنده MIPS MEM:MemoryAccessWB: WriteBackEX: ExecuteAddr. Calc

اسلاید 10: رجیسترهای بین مراحل خط لولهNeed registers between stagesTo hold information produced in previous cycle

اسلاید 11: تجسم خط لولهInstr.OrderTime (clock cycles)RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegCycle 1Cycle 2Cycle 3Cycle 4Cycle 6Cycle 7Cycle 511

اسلاید 12: مشكلاتي كه در پردازش خط لوله اي بوجود مي آيدLimits to pipelining: Hazards prevent next instruction from executing during its designated clock cycleStructural hazards: HW cannot support this combination of instructions Data hazards: Instruction depends on result of prior instruction still in the pipelineControl hazards: Caused by delay between the fetching of instructions and decisions about changes in control flow (branches and jumps).12

اسلاید 13: One Memory Port/ Structural Hazards Instr.OrderTime (clock cycles)LoadInstr 1Instr 2Instr 3Instr 4RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegCycle 1Cycle 2Cycle 3Cycle 4Cycle 6Cycle 7Cycle 5RegALUDMemIfetchReg13Reading data from memoryReading instruction from memory

اسلاید 14: One Memory Port/ Structural Hazards Instr.OrderTime (clock cycles)LoadInstr 1Instr 2StallInstr 3RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegCycle 1Cycle 2Cycle 3Cycle 4Cycle 6Cycle 7Cycle 5RegALUDMemIfetchRegBubbleBubbleBubbleBubbleBubble14

اسلاید 15: Data Hazard on $115add $1,$3,$0sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9

اسلاید 16: وابستگيهاي رو به عقب در زمانInstr.OrderTime (clock cycles)add $1,$3,$0sub $4,$1,$3and $6,$1,$7or r$,$1,$9xor $10,$1,$11IFID/RFEXMEMWBALUImRegDmRegALUImRegDmRegALUImRegDmRegImALURegDmRegALUImRegDmReg16

اسلاید 17: نتيجه يك مرحله را به محض آماده شدن به جلو برانيمروش Forwarding براي حل مشكل Data Hazard Instr.OrderTime (clock cycles)ALUImRegDmALUImRegDmRegALUImRegDmRegImALURegDmRegALUImRegDmReg17IFID/RFEXMEMWBadd $1,$3,$0sub $4,$1,$3and $6,$1,$7or r$,$1,$9xor $10,$1,$11

اسلاید 18: تغييرات سخت افزاري براي پشتيباني ازForwarding MEM/WRID/EXEX/MEM DataMemoryALUmuxmuxRegistersNextPCImmediatemux18

اسلاید 19: Read After Write (RAW) InstrJ tries to read operand before InstrI writes it Caused by a “Dependence” (in compiler nomenclature). This hazard results from an actual need for communication.I: add r1,r2,r3J: sub r4,r1,r319سه نوع Data Hazard

اسلاید 20: Write After Read (WAR) InstrJ writes operand before InstrI reads it Called an “anti-dependence” by compiler writers. This results from reuse of the name “r1”. I: sub r4,r1,r3 J: add r1,r2,r3K: mul r6,r1,r720سه نوع Data Hazard

اسلاید 21: Write After Write (WAW) InstrJ writes operand before InstrI writes it. Called an “output dependence” by compiler writers This also results from the reuse of name “r1”.I: sub r1,r4,r3 J: add r1,r2,r3K: mul r6,r1,r721سه نوع Data Hazard

اسلاید 22: Data Hazard حتي با استفاده از Forwarding 22

اسلاید 23: 23Data Hazard حتي با استفاده از Forwarding

اسلاید 24: Try producing fast code fora = b + c;d = e – f;assuming a, b, c, d ,e, and f in memory. Slow code:LW Rb,bLW Rc,cADD Ra,Rb,RcSW a,Ra LW Re,e LW Rf,fSUB Rd,Re,RfSWd,RdSoftware Scheduling to Avoid Load HazardsFast code:LW Rb,bLW Rc,cLW Re,e ADD Ra,Rb,RcLW Rf,fSW a,Ra SUB Rd,Re,RfSWd,Rd24

اسلاید 25: Control Hazard on Branches - Three Stage Stall10: beq r1,r3,3614: and r2,r3,r5 18: or r6,r1,r722: add r8,r1,r936: xor r10,r1,r11RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchReg25

اسلاید 26: Branch Stall ImpactIf CPI = 1, 30% branch, Stall 3 cycles => new CPI = 1.9!Two part solution:Determine branch taken or not sooner, ANDCompute taken branch address earlier26

اسلاید 27: Four Branch Hazard Alternatives1: Stall until branch direction is clear2: Predict Branch Not Taken3: Predict Branch Taken4: Delayed Branch27

اسلاید 28: Superscalarابر عددي يا پردازشاستفاده از چند خط لوله به صورت موازي28

اسلاید 29: Summary : Control and PipeliningJust overlap tasks; easy if tasks are independentSpeed Up  Pipeline Depth; if ideal CPI is 1, then: Hazards limit performance on computers:Structural: need more HW resourcesData (RAW,WAR,WAW): need forwarding, compiler schedulingControl: Delayed branch, prediction29

اسلاید 30: Single Cycle, Mult-Cycle, vs. PipelineMultiple Cycle Implementation:ClkCycle 1IFetchDecExecMemWBCycle 2Cycle 3Cycle 4Cycle 5Cycle 6Cycle 7Cycle 8Cycle 9Cycle 10IFetchDecExecMemlwswIFetchR-typelwIFetchDecExecMemWBPipeline Implementation:IFetchDecExecMemWBswIFetchDecExecMemWBR-typeClkSingle Cycle Implementation:lwswWasteCycle 1Cycle 2

اسلاید 31: 31Questio