Bài giảng Bộ xử lý đường ống (Bản đẹp)

Processor PipeliningBộ xử lý đường ốngNội dung• So sánh tốc độ xử lý – Single ‐ cycle datapath (from the previous lecture) – Multi‐cycle – Pipelining• Kỹ thuật đường ống – Kỹ thuật đường ống là gì? – Tại sao lại sử dụng kỹ thuật đường ống?• Xây dựng bộ xử lý đường ống – Chia cắt từ bộ xử lý đơn xung nhịp – Hoạt động của MIPS pipeline – Điều khiển PipelineTốc độ xử lý(What limits our clock?)Đường dữ liệu bộ xử lý đơn xung nhịpTốc độ xác định bởi lệnh có đường dữ liệu dài nhất.A: 70%•1/2 = 35% of the time.70% các lệnh cần một nửa chu kỳ để xử lý. Như vậy 35% thời gian để lãng phí.If slowest path is for load, all instructions go this slowly.Q: Nếu truy cập vào bộ nhớ dữ liệu dài hơn gấp 2 lần các lệnh khác và 30% lệnh của chương trình là loads/stores, bao nhiêu phần trăm thời gian bộ xử lý nhàn rỗi?20% of the time35% of the time40% of the timeThời gian thực thi đơn xung nhịp• Lệnh thực thi chậm nhất là lệnh có thời gian thực thi bằng 1 chu kỳ • Lãng phí thời gianGiải pháp: Bộ xử lý đa xung nhịp• Lệnh nhanh nhất xác định tương ứng với 1 chu kỳ• Lệnh chậm hơn sẽ chiếm nhiều chu kỳCách nào tốt hơn?• Chia lệnh thành các giai đoạn khác nhau• Giai đoạn dài nhất sẽ xác định tốc độ xử lý Chia thành 5 parts → đồng hồ nhanh hơn 5x lần → nhưng cần nhiều hơn 5x chu kỳ cho một lệnhCần nhiều chu kỳ cho một lệnh!Ví dụ MIPS: 5 giai đoạn đường ống Kỹ thuật này có tốt hơn không?Hoạt động trong đường ốngĐây là điều chúng ta cần từ đường ống: sử dụng tất cả các phần của bộ xử lý đối với các lệnh khác nhau tại cùng một thời điểm Kỹ thuật đường ống là gì?Một số ví dụ trong đời sốngKỹ thuật đường ống 1: quy trình giặt là (serial - pipeline)• 4 hoạt động cho một tải:– Wash (1h), Dry (1h), Fold (1h), Put away (1h)• 4 tải mất bao lâu?– Wash + Dray + Fold + Put away = 4h– 4 loads * 4h/load = 16hQ: Bao nhiêu phần trăm tài nguyên đã sử dụng?1. 100%2. 50%3. 25%A: 25%Chỉ sử dụng một pha: wash, dry, fold, và put away ở mỗi thời điểm. Còn 3 pha khác là nhàn rỗi.How can pipelining help?Ví dụ: Quy trình giặt là (pipelined)• Hãy thử xếp chồng các hoạt động• Bao lâu cho 4 lần tải?– 4 lần tải trong 7 giờ (mỗi lần tải trong 4h)– 7h vs. 16h nhanh hơn 2.3x!Đường ống hóa giúp cho việc sử dụng tất cả các tài nguyên tại cùng một thời điểm khi thực hiện nhiều hoạt động khác nhau.Q: Cần bao nhiêu người để thực hiện 4 hoạt động trong cùng một thời điểm ?124Đạt được hiệu xuất cao hơn. Khi cần 4 tải tại một thời điểm sử dụng toàn bộ tài nguyên.A: 4Để thực hiện 4 thao tác một lúc cần 4 người. Tương đương với việc cần điều khiển logic cho 4 lệnh tại một thời điểm.Ví dụ về kỹ thuật đường ống 2: lắp ráp xe (serial)• Công nghệ của Henry Ford• Sản xuất theo đường ốngPipelining example 2: car assembly (serial)Q: Hiệu xuất hoạt động sẽ như thế nào nếu đường ống không đầy?Goes upStays the sameGoes downA: Goes down Nếu đường ống không đầy, sẽ không sử dụng hết tài nguyên làm hiệu năng giảm xuống.Đường ống đầy. Hiệu năng tối ưu bởi vì tất cả tài nguyên đều được sử dụng trong cùng một khoảng thời gian..Tại sao lại sử dụng Pipeline ?(Hint: performance)Tại sao lựa chọn pipeline?• Nếu có thể giữ cho đường ống luôn đầy sẽ có throughput (số công việc thực hiện được trong một khoảng thời gian) tốt hơn.– Laundry: 1 load of laundry/hour– Car: 1 car/hour – MIPS: 1 instruction/cycle• Xuất hiện trễ (total time per)– Laundry: 4 giờ cho mỗi lần giặt là– Car: 4 giờ cho một xe ô tô– MIPS: 5 chu kỳ cho mỗi lệnh• Pipelining nhanh hơn bởi vì sử dụng tất cả tài nguyên tại cùng một thời điểm – Laundry: máy giặt, máy sấy, gập, cất vào tủ– Car: lắp đế, lắp giáp động cơ, lắp lốp, lắp buồng lái– MIPS: Nạp lệnh, đọc thanh ghi, ALU, Truy cập bộ nhớ và ghi vào thanh ghi. (Instruction fetch, register read, ALU, memory, and register write).Hiệu năng đường ống hóa trong bộ xử lý • Chương trình tải 3 lệnh mỗi lệnh cần 800ps (0.8ns)• Nếu đường ống hóa và xếp chồng sẽ sử dụng được tất cả tài nguyên một cách song song và thực hiện 3 lệnh trên nhanh hơn.Q: Thông lượng tăng lên bao nhiêu lần trong đường ống 5 giai đoạn?1.7lần4lần5lầnA: 1.7 lầnĐối với đường ống, throughput là một lênh trong mỗi 200ps và 800ps không có không đường ống hóa. Tuy nhiên phải tăng độ trễ lênh tới 1000ps trên một lệnh để cân bằng 5 pha đường ống. Tốc độ tuyệt đối cho 3 lệnh riêng biệt là 1.7x (1400ps/2400ps).Nhanh hơn bao nhiêu?• Tăng tốc Pipeline – Nếu tất cả các pha có cùng chiều dài.• Ví dụ : Pipelined– Thời gian cho một tải giặt là = 4h/4 giai đoạn = 1 load /1h (throughput)– Thời gian cho một ô tô = 4h/4 giai đoạn = 1 car /1h (throughput)• Nhưng – Thời gian cho tải giặt là vẫn là 4h (latency)– Thời gian tạo một xe ô tô vẫn là 4h (latency)• Đường ống hóa chỉ tăng thông lượng khi đường ống đầy – Tốc độ tăng lên 2.3x.Tại sao không chia nhiều giai đoạn hơn?• Ý tưởng là sẽ tăng tốc được Nx đối với một pipeline N pha?• Why not use a zillion stages to get a zillion x speedup?• Two problems: – Most things can’t be broken down into infinitely small chunks• Think about the processor we built:• How much can we chop up the ALU? or the RF?• Practical limit to logic design – There is an overhead for every stage• We need to store the state (which instruction) for each stage• This requires a register, and it takes some timeCác thanh ghi Pipeline và mào đầu (phí tổn điều khiển)• Mỗi trạng thái đường ống là một tổ hơp logic (ALU, sign extension)• Cần lưu trữ trạng thái các pha (which instruction)• Cần các thanh ghi pipeline giữa các pha để lưu trữ lệnh cho các pha. Đồng hồ trong bộ xử lý Pipeline• Tốc độ đồng hồ xác định bởi register → stage → register– Clock dịch chuyển dữ liệu đi đến thanh ghi đầu tiên– Dữ liệu tính toán trong các trạng thái (combinational: think an adder)– Dữ liệu cần đến thanh ghi tiếp theo đúng giờ tương ứng với xung đồng hồ tiếp theoHiệu năng của việc đường ống hóa MIPS• Thiết kế đơn xung nhịp (Single‐cycle):– Đồng hồ đặt cho lệnh chậm nhất: 800ps clock time• Thiết kế đường ống hóa Pipelined:– Đồng hồ được đặt cho pha chậm nhất: 200ps• Chú ý rằng một vài lệnh không sử dụng hết các pha.– Cần điều khiển để chắc chắn rằng các pha hoạt động đồng bộ Xây dựng bộ xử lý đường ống Cắt ra từ bộ xử lý đơn xung nhịpLàm thế nào để chia các lệnh MIPS?(You’ve already seen it)1. IF: Instruction fetch from memory2. ID: Instruction decode and register read3. EX: Execute operation or calculate address4. MEM: Access memory5. WB: Write result back to registerQ: Thiếu cái gì trong hình vẽ?Balanced stagesPipeline registersWrite back for the RFA: Pipeline registersCần chúng để lưu trạng thái (lệnh và kết quả) giữa các pha.Các thanh ghi pipeline.• Các thanh ghi lưu giữ thông tin thủ tục giữa các pha. • Dịch chuyển dữ liệu đến các pha tiếp kế tiếp theo xung đồng hồClockChiều chuyển động của đường ống trong MIPS.• Làm thế nào để tải lệnh đi trong pipeline• Chú ý: – Cái gì kết nối trong mỗi giai đoạn?(combinational) – Cái gì được lưu trữ trong thanh ghi? (state)IF for loadID for loadEX for loadMEM for loadWB for loadFixing the WB stageĐường dữ liệu MIPS pipelineHUST-FET, 22/08/202134Thanh ghi trạng thái giữa các giai đoạn thực hiện lệnh để phân cáchIF:IFetchID:DecEX:ExecuteMEM:MemAccessWB:WriteBackReadAddressInstructionMemoryAddPC4Write DataRead Addr 1Read Addr 2Write AddrRegisterFileRead Data 1Read Data 21632ALUShiftleft 2AddDataMemoryAddressWrite DataReadDataIF/IDSignExtendID/EXEX/MEMMEM/WBSystem ClockThe MIPS pipelineLuồng lệnh trong đường ống. Q: Có bao nhiêu lệnh trên một chu kỳ - Instructions Per Cycle (IPC) nếu thực hiện lệnh tải?1.00.2 (one every 5 cycles)5.0A: 1.0Khi đường ống đầy, chỉ nhận được một lệnh mỗi chu kỳ IPC = 1.0.Chu kỳ 4 có 3 lệnh “cùng hoạt động”: Inst 1 is accessing the data memory (MEM) Inst 2 is using the ALU (EX)Inst 3 is access the register file (ID)Điều khiển logic trong Pipeline(Làm thế nào để giải mã các lệnh trong đường ống?)Điều khiển Pipeline• Có cần toàn bộ thanh ghi lệnh trong các giai đường ống ?• Không, chỉ cần một vài bit cho mỗi pha.Điều khiển MIPS pipelineHUST-FET, 22/08/202139Các tín hiệu điều khiển được xác định trong giai đoạn giải mã và được lưu trong các thanh ghi trạng thái giữa các giai đoạn pipelineReadAddressInstructionMemoryAddPC4Write DataRead Addr 1Read Addr 2Write AddrRegisterFileRead Data 1Read Data 21632ALUShiftleft 2AddDataMemoryAddressWrite DataReadDataIF/IDSignExtendID/EXEX/MEMMEM/WBControlALUcntrlRegWriteMemReadMemtoRegRegDstALUOpALUSrcBranchPCSrcChi tiết về điều khiển PipelineQ: Nơi nào tín hiệu Write Register đi đến?The MEM/WB control bits (top)instruction in the IF/ID registerData in the MEM/WB registerA: Data in the MEM/WB register Các bit thứ tự 20‐16 hoặc 11‐15 được gửi tới thanh ghi MEM/WB để xác định thanh ghi cần ghi dữ liệu Xung đột PipelineHUST-FET, 22/08/202141Xung đột cấu trúc: yêu cầu sử dụng cùng một tài nguyên cho 2 lệnh khác nhau tại cùng 1 thời điểmXung đột dữ liệu: yêu cầu sử dụng dữ liệu trước khi nó sẵn sàngCác toán hạng nguồn của 1 lệnh được tạo ra bởi lệnh phía trước vẫn đang nằm trong pipelineXung đột điều khiển: yêu cầu quyết định điều khiển dòng chương trình trước khi điều kiện rẽ nhánh và giá trị PC mới được tính toánCác lệnh rẽ nhánh, nhảy và ngắtGiải quyết xung đột bằng cách chờ đợiKhối điều khiển pipeline cần phát hiện xung độtVà hành động để giải quyết xung độtBộ nhớ đơn: Xung đột cấu trúcHUST-FET, 22/08/202142Instr.OrderTime (clock cycles)lwInst 1Inst 2Inst 4Inst 3ALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegALUMemRegMemRegĐọc dữ liệu từ bộ nhớĐọc lệnh từ bộ nhớSửa: Bộ nhớ dữ liệu và lệnh riêng rẽ(Instr. and Data )Truy cập tệp thanh ghiHUST-FET, 22/08/202143Instr.OrderInst 1Inst 2ALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegSửa xung đột truy cập tệp thanh ghhi bằng cách đọc trong nửa đầu chu kỳ và ghi trong nửa sau chu kỳadd $1,add $2,$1,Sườn đồng hồ điều khiển ghi Sườn đồng hồ điều khiển đọcSử dụng thanh ghi: Xung đột dữ liệuHUST-FET, 22/08/202144Instr.Orderadd $1,sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9ALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegXung đột đọc trước khi ghi (Read before write)Phụ thuộc dữ liệu ngược theo thời gian gây ra xung độtSử dụng thanh ghi: Xung đột dữ liệuHUST-FET, 22/08/202145Instr.Orderadd $1,sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9ALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegPhụ thuộc dữ liệu ngược theo thời gian gây ra xung độtXung đột đọc trước khi ghi (Read before write)Đọc từ bộ nhớ gây xung đột dữ liệuHUST-FET, 22/08/202146Instr.OrderlwInst 4Inst 3beqALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegDependencies backward in time cause hazardsGiải quyết xung đột: Tạm dừngHUST-FET, 22/08/202147stallstallInstr.Orderadd $1,ALUIMRegDMRegsub $4,$1,$5and $6,$1,$7ALUIMRegDMRegALUIMRegDMRegCó thể giải quyết xung đột dữ liệu bằng dừng chờ– stall – ảnh hưởng tới CPIVí dụ:HUST-FET, 22/08/2021481: addi $s0, $zero, 102: addi $s1, $zero, 0L1: 3: add $t0, $t0, $s14: addi $s1, $s1, 15: bne $s1, $s0, L11234567891011121IFIDEXMEMWB2IFIDEXMEMWB3IFIDEXMEMWB4IFIDEXMEMWB5IFIDEXMEMWB3*IFIDEXMEMWB4IFIDEXMEMWB5IFIDEXMEMWBTính CPI cho chương trình1234567891011121314151IFIDEXMEMWB2IFIDEXMEMWB3**IFIDEXMEMWB4IFIDEXMEMWB5**IFIDEXMEMWB3****IFID4IF5Chuyển tiếp dữ liệuHUST-FET, 22/08/202150Lấy kết quả ở thời điểm nó xuất hiện sớm nhất trong bất kỳ thanh ghi pipeline nào, và chuyển tiếp nó đến khối chức năng (VD. ALU) mà cần kết quả tại chu kỳ đồng hồ đóVới khối chức năng ALU: đầu vào có thể từ bất kỳ thanh ghi pipeline nào chứ không cần từ ID/EX bằng cáchThêm bộ chọn vào trước đầu vào của ALUNối dữ liệu ghi Rd ở EX/MEM hoặc MEM/WB tới một trong 2 hoăc cả 2 thanh ghi pipeline Rs và Rt thuộc giai đoạn EX. Thêm phần điều khiển phần cứng để điều khiển bộ chọnCác khối chức năng khác cũng cần được thêm tương tự (VD. DM)Với chuyển tiếp có thể đạt được CPI = 1 ngay khi có sự phụ thuộc dữ liệuGiải quyết xung đột: Chuyển tiếp dữ liệuHUST-FET, 22/08/202151Instr.Orderadd $1,ALUIMRegDMRegsub $4,$1,$5and $6,$1,$7ALUIMRegDMRegALUIMRegDMRegGiải quyết xung đột dữ liệu bằng chuyển tiếp kết quả ngay khi chúng sẵn sàng tới nơi cầnxor $4,$1,$5or $8,$1,$9ALUIMRegDMRegALUIMRegDMRegGiải quyết xung đột: Chuyển tiếp dữ liệuHUST-FET, 22/08/202152ALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegGiải quyết xung đột dữ liệu bằng chuyển tiếp kết quả ngay khi chúng sẵn sàng tới nơi cầnALUIMRegDMRegALUIMRegDMRegInstr.Orderadd $1,sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9Minh họa triển khai chuyển tiếpHUST-FET, 22/08/202153Instr.Orderadd $1,sub $4,$1,$5and $6,$7,$1ALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegEX forwardingMEM forwardingXung đột dữ liệu khi chuyển tiếpHUST-FET, 22/08/202154Instr.Orderadd $1,$1,$2ALUIMRegDMRegadd $1,$1,$3add $1,$1,$4ALUIMRegDMRegALUIMRegDMRegMột loại xung đột dữ liệu xuất hiện khi chuyển tiếp: Xung đột giữa kết quả của lệnh đang ở giai đoạn WB và lệnh đang ở giai đoạn MEM – kết quả nào cần được chuyển tiếp?Xung đột dữ liệu khi có lệnh lwHUST-FET, 22/08/202155Instr.Orderlw $1,4($2)and $6,$1,$7xor $4,$1,$5or $8,$1,$9ALUIMRegDMRegALUIMRegDMALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegsub $4,$1,$5Xung đột dữ liệu khi có lệnh lwHUST-FET, 22/08/202156stallInstr.Orderlw $1,4($2)sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9ALUIMRegDMRegALUIMRegDMALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegSẽ vẫn cần một chu kỳ chờ ngay cả khi có chuyển tiếpXung đột điều khiểnHUST-FET, 22/08/202157Khi địa chỉ các lệnh không tuần tự (i.e., PC = PC + 4); xuất hiện khi có các lệnh thay đổi dòng chương trìnhLệnh rẽ nhánh không điều kiện (j, jal, jr)Lệnh rẽ nhánh có điều kiện (beq, bne)Ngắt, ExceptionsGiải phápTạm dừng (ảnh hưởng CPI)Tín toán điều kiện rẽ nhánh càng sớm càng tốt trong giai đoạn pipeline giảm số chu kỳ phải dừngRẽ nhánh chậm (Delayed branches - Cần hỗ trợ của trình dịch)Dự đoán và hy vọng điều tốt nhất!Xung đột điều khiển ít xảy ra, nhưng không có giải pháp giải quyết hiệu quả như chuyển tiếp đối với xung đột dữ liệuLệnh nhảy: Cần một chu kỳ dừngHUST-FET, 22/08/202158flushInstr.Orderjj targetALUIMRegDMRegALUIMRegDMRegLệnh nhảy rất ít xuất hiện – chỉ chiếm 3% số lệnh trong SPECintLệnh nhảy không được giải mã cho đến giai đoạn ID, cần một lệnh xóa (flush)Để xóa, đặt trường mã lệnh của thanh ghi pipeline IF/ID bằng 0 (làm nó trở thành 1 lệnh noop)Giải quyết xung đột lệnh nhảy bằng cách chờ – flushALUIMRegDMRegXung đột điều khiển lệnh rẽ nhánhHUST-FET, 22/08/202159Instr.OrderlwInst 4Inst 3beqALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegGiải quyết xung đột điều khiển lệnh rẽ nhánhHUST-FET, 22/08/202160flushflushflushInstr.OrderbeqALUIMRegDMRegbeq targetALUIMRegDMRegALU Inst 3IMRegDMGiải quyết xung đột bằng chờ– flush – nhưng ảnh hưởng CPIALUIMRegDMRegALUIMRegDMRegALUIMRegDMRegGiải quyết xung đột điều khiển lệnh rẽ nhánhHUST-FET, 22/08/202161flushInstr.Orderbeqbeq targetALUIMRegDMReg Inst 3ALUIMRegDMFix branch hazard by waiting – flushALUIMRegDMRegTính toán điều kiện rẽ nhánh càng sớm càng tốt, tức là trong giai đoạn giải mã  chỉ cần 1 chu kỳ chờALUIMRegDMRegRẽ nhánh chậmHUST-FET, 22/08/202162Nếu phần cứng cho rẽ nhánh nằm ở giai đoạn ID, ta có thể loại bỏ các chu kỳ chờ rẽ nhánh bằng cách sử dụng rẽ nhánh chậm (delayed branches) – luôn thực hiện lệnh theo sau lệnh lệnh rẽ nhánh – rẽ nhánh có tác dụng sau lệnh kế tiếp nóTrình dịch MIPS compiler chuyển 1 lệnh an toàn (không bị ảnh hưởng bởi lệnh rẽ nhánh) tới sau lệnh rẽ nhánh (vào khe trễ). Vì vậy sẽ dấu được sự rẽ nhánh chậmVới pipeline sâu (nhiều giai đoạn), trễ rẽ nhánh tăng cần nhiều lệnh được chèn vào sau lệnh rẽ nhánhRẽ nhánh chậm đang được thay thế bởi các phương pháp khác tốn kém hơn nhưng mềm dẻo (động) hơn như dự đoán rẽ nhánhSự phát triển của IC cho phép có bộ dự đoán rẽ nhánh ít tốn kém hơnSắp xếp lệnh trong rẽ nhánh chậmHUST-FET, 22/08/202163TH A là lựa chọn tốt nhất, điền được khe trễ và giảm ITH B , lệnh sub cần sao chép lại, tăng ITH B và C, phải đảm bảo thực hiện lệnh sub không ảnh hưởng khi không rẽ nhánhadd $1,$2,$3if $2=0 thendelay slotA. Từ trước lệnh rẽ nhánhB. Từ đích lệnh rẽ nhánhC. Từ nhánh saiadd $1,$2,$3if $1=0 thendelay slotadd $1,$2,$3if $1=0 thendelay slotsub $4,$5,$6sub $4,$5,$6becomesbecomesbecomes if $2=0 thenadd $1,$2,$3add $1,$2,$3if $1=0 thensub $4,$5,$6add $1,$2,$3if $1=0 thensub $4,$5,$6Real world pipelinesWe saw this earlierQ: Which one is going to run at a faster clock frequency? Little Big SameA: BigThe big processor has a longer pipeline, which means each stage will be shorter, so a higher clock frequency.Q: Which pipeline will waste more time on pipeline registers? Little Big SameA: BigRunning at a higher frequency means that a larger percentage of the time will be spent in pipeline registers. Equally important, because there are so many more stages, there will be more registers, which use more power and area.What is AMD doing?Tóm tắtHUST-FET, 22/08/202167Các bộ xử lý hiện đại đều dùng kỹ thuật pipelinePipelining không làm giảm độ trễ của 1 nhiệm vụ đơn lẻ, nó giúp tăng thông lượng của toàn bộTăng tốc tiềm năng: CPI = 1 và đồng hồ nhanh, Tc nhỏ Tốc độ đồng hồ bị hạn chế bởi giai đoạn pipeline chậm nhất Các giai đoạn pipeline không cân bằng làm giảm hiệu suấtThời gian “làm đầy” pipeline và thời gian “làm trống” pipeline ảnh hưởng đến độ tăng tốc khi pipeline sâu (nhiều giai đoạn) và đoạn mã ngắnCần phát hiện và giải quyết xung độtDừng ảnh hưởng xấu tới CPI (làm CPI lớn hơn giá trị lý tưởng 1)