Tomasulo's algorithm: Difference between revisions

Revision as of 21:27, 20 May 2024

Latest revision as of 07:23, 10 August 2024

(3 intermediate revisions by 3 users not shown)

Line 100:

!Action or bookkeeping

|-

|FP operation

|Issue

|Station {{mono|r}} empty

|<syntaxhighlight lang="c">

Line 239:

By tracking operands for instructions in the reservation stations and register renaming in hardware the algorithm minimizes [[Read after write (Hazard)|read-after-write]] (RAW) and eliminates [[Write after write (hazard)#Write after write .28WAW.29|write-after-write]] (WAW) and [[Write after read (hazard)#Write after read .28WAR.29|Write-after-Read]] (WAR) [[computer architecture]] [[hazard (computer architecture)|hazard]]s. This improves performance by reducing wasted time that would otherwise be required for stalls.<ref name="tomasulo"/>{{rp|33}}

An equally important improvement in the algorithm is the design is not limited to a specific pipeline structure. This improvement allows the algorithm to be more widely adopted by [[multiple issue|multiple-issue]] processors. Additionally, the algorithm is easily extended to enable branch speculation.<ref name="hennessy" /> {{rp|182}}

== Applications and legacy ==

Tomasulo's algorithm, outsidewas ofimplemented IBM,in wasthe unusedSystem/360 forModel several91 yearsarchitecture. afterOutside itsof implementationIBM, init thewent System/360unused Modelfor 91several architectureyears. However, it saw a vast increase in usage during the 1990s for 3 reasons:

# Once caches became commonplace, the Tomasulo algorithm's ability to maintain concurrency during unpredictable load times caused by cache misses became valuable in processors.

# Dynamic scheduling and the branch speculation thatfrom the algorithm enables helpedimproved performance as processors issued more and more instructions.

# Proliferation of mass-market software meant that programmers would not want to compile for a specific pipeline structure. The algorithm can function with any pipeline architecture and thus software requires few architecture-specific modifications.<ref name="hennessy" /> {{rp|183}}

Many modern processors implement dynamic scheduling schemes that are derivativevariants of Tomasulo's original algorithm, including popular [[Intel]] [[x86-64]] chips.<ref name="intel" >{{Cite report

| date = September 2014

| title = Intel 64 and IA-32 Architectures Software Developer's Manual