Trace scheduling is an optimization technique developed by Josh Fisher used in compilers for computer programs.[1]

A compiler often can, by rearranging its generated machine instructions for faster execution, improve program performance. It increases ILP (Instruction Level Parallelism) along the important execution path by statically predicting frequent execution path. Trace scheduling is one of many known techniques for doing so.[2]

A trace is a sequence of instructions, including branches but not including loops, that is executed for some input data. Trace scheduling uses a basic block scheduling method to schedule the instructions in each entire trace, beginning with the trace with the highest frequency. It then adds compensation code at the entry and exit of each trace to compensate for any effects that out-of-order execution may have had.

This can result in large increases in code sizes and poor or erratic performance if program's behavior varies significantly with the input.

Trace scheduling was originally developed for Very Long Instruction Word, or VLIW machines, and is a form of global code motion. It works by converting a loop to long straight-line code sequence using loop unrolling and static branch prediction. This process separates out "unlikely" code and adds handlers for exits from trace. The goal is to have the most common case executed as a sequential set of instructions without branches.

See also

edit

References

edit
  1. ^ Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2. Trace scheduling .
  2. ^ Fisher, Joseph (7 July 1981). "Trace Scheduling: A Technique for Global Microcode Compaction" (PDF). IEEE Transactions on Computers. c-30 (7): 478–490. doi:10.1109/TC.1981.1675827. S2CID 1650655.
Stub icon

This programming-language-related article is a stub. You can help Wikipedia by adding missing information.

📚 Artikel Terkait di Wikipedia

Josh Fisher

but offering large amounts of instruction-level parallelism scheduled by a trace scheduling or similar compiler. VLIWs are now used extensively, especially

Instruction scheduling

different iterations of an inner loop. Trace scheduling: the first practical approach for global scheduling, trace scheduling tries to optimize the control flow

Multiflow

period 1979-1981. VLIW was motivated by a compiler scheduling technique, called trace scheduling, that Fisher had developed as a graduate student at

Very long instruction word

developed region scheduling methods to identify parallelism beyond basic blocks. Trace scheduling is such a method, and involves scheduling the most likely

Trace Adkins

Tracy Darrell Adkins (born January 13, 1962) known professionally as Trace Adkins, is an American country music singer and actor. Adkins made his debut

Automated planning and scheduling

Automated planning and scheduling, sometimes denoted as simply AI planning, is a branch of artificial intelligence that concerns the realization of strategies

Buffalo Trace Distillery

Buffalo Trace Distillery (formerly the George T. Stagg Distillery and the Old Fashioned Copper (O.F.C.) Distillery) is a distillery in Frankfort, Kentucky

Monica (2022 film)

Andrea Pallaoro from a screenplay by Pallaoro and Orlando Tirado. It stars Trace Lysette, Patricia Clarkson, Emily Browning, and Adriana Barraza. The film