+++
title = "Trace scheduling"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["1c2h", "1c2e"]
forwardlinks = ["1c2b", "1c2g"]
zettelid = "1c2f"
+++

Trace scheduling \[1\], \[2\], is a technique used to do global
scheduling of the code. This is different to list scheduling ([\#1c2b]),
where the scheduling is only done for one basic block.

The way this is done is by looking through the most common trace through
a program and then regarding that path as not containing any control
flow. Normal scheduling techniques can then be applied on this path,
which is now straight-line code, such as placing instructions into
larger instruction words, like with VLIW processors.

However, to counter-act this, instructions need to also be placed into
other possible execution paths apart from the trace, as the above
scheduling might have gotten rid of instructions and change the
behaviour of the program.

After the correctness has been restored, another trace is taken and the
same operation is performed.

<div id="refs" class="references csl-bib-body" markdown="1">

<div id="ref-fisher81_trace_sched" class="csl-entry" markdown="1">

<span class="csl-left-margin">\[1\]
</span><span class="csl-right-inline">J. A. Fisher, “Trace scheduling: A
technique for global microcode compaction,” *IEEE Transactions on
Computers*, vol. C–30, no. 7, pp. 478–490, 1981, doi:
[10.1109/TC.1981.1675827].</span>

</div>

<div id="ref-colwell88_vliw" class="csl-entry" markdown="1">

<span class="csl-left-margin">\[2\]
</span><span class="csl-right-inline">R. P. Colwell, R. P. Nix, J. J.
O’Donnell, D. B. Papworth, and P. K. Rodman, “A VLIW architecture for a
trace scheduling compiler,” *IEEE Transactions on Computers*, vol. 37,
no. 8, pp. 967–979, 1988, doi: [10.1109/12.2247].</span>

</div>

</div>

  [\#1c2b]: /zettel/1c2b
  [10.1109/TC.1981.1675827]: https://doi.org/10.1109/TC.1981.1675827
  [10.1109/12.2247]: https://doi.org/10.1109/12.2247