ComputerArchitectureOut of Order ExecutionComputerArchitecture
Computer Architecture Computer Architecture Out of Order Execu3on
Tomasulo AlgorithmHistory:In today's perspective:1966: scoreboarding inthe implementationCDC6600,implementingbelongsto reservation-limited dynamicbased dynamic schedulingschedulingThree years later:The merit is the use of tagTomasuloinIBM360/91to identify instructions inintroducing registerthe fly: register renamingrenaming and reservationstationreservation station, tagbroadcastNowappearingintodaysDec Alpha, SGI MIPS, SUNUltraSparc,Intel Pentium,It is an“algorithm"firstIBM PowerPC, and othersComputerArchitecture
Computer Architecture Tomasulo Algorithm History: • 1966: scoreboarding in CDC6600, implemen?ng limited dynamic scheduling • Three years later: Tomasulo in IBM 360/91, introducing register renaming and reserva?on sta?on • Now appearing in todays Dec Alpha, SGI MIPS, SUN UltraSparc, Intel Pen?um, IBM PowerPC, and others In today’s perspec?ve: • the implementa?on belongs to reserva?onbased dynamic scheduling • The merit is the use of tag to iden?fy instruc?ons in the fly: register renaming, reserva?on sta?on, tag broadcast It is an “algorithm” first
TomasuloOrganizationFrom instruction unitInstructionFPregistersqueueLoad-storeoperationsOperandFloating-pointAddressunitbusesoperationsStorebuffersLoadbuffersVOperation bus32121ReservationstationsAddressData?FPmultipliersFP addersMemoryunltCommondata bus (CDB)ComputerArchitecture
Computer Architecture Tomasulo Organiza?on
ReservationStationComponentsOp-Operation to perform in the unit (e.g., + or -)Vi,Vk-ValueofSourceoperands-StorebuffershasVfield,resulttobestoredQi,Qk-Reservationstationsproducingsourceregisters(value to be written)- Note: No ready flags as in Scoreboard; Qj,Qk=0 => ready- Store buffers onlyhave Qifor RS producingresultBusy-lndicates reservation station or FU is busyComputerArchitecture
Computer Architecture Reserva?on Sta?on Components Op—Opera?on to perform in the unit (e.g., + or –) Vj, Vk—Value of Source operands – Store buffers has V field, result to be stored Qj, Qk—Reserva?on sta?ons producing source registers (value to be wri_en) – Note: No ready flags as in Scoreboard; Qj,Qk=0 => ready – Store buffers only have Qi for RS producing result Busy—Indicates reserva?on sta?on or FU is busy
RenamingTableIndicateswhich RSwill write each register,if oneexists. Blank when no pending instructions that willwrite that register.-Called“Registerresult status"in thetext book.ComputerArchitecture
Computer Architecture Renaming Table • Indicates which RS will write each register, if one exists. Blank when no pending instruc?ons that will write that register. – Called “Register result status” in the text book