+++
title = "List scheduling"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["1c2f", "1c2a"]
forwardlinks = ["1a1", "1c2c", "1c2b1"]
zettelid = "1c2b"
+++

List scheduling \[1\] is another example of scheduling which is more
algorithmic than the ILP expression shown in ILP scheduling. However,
this is much easier to implement, especially if the initial
representation is a data-flow graph (DFG) ([\#1a1]).

The DFG already encodes all the necessary information to schedule each
assignment at the earliest possible time when its dependencies are met.
This means that one can just iterate through the DFG and pick all the
instructions that have their dependencies met, add them to the list of
instructions that should be scheduled for this clock cycle and let the
other instructions that depend on it know that it is met. Once all the
nodes in the DFG have been processed, everything should have been
scheduled properly.

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

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

<span class="csl-left-margin">\[1\]
</span><span class="csl-right-inline">S. Hauck and A. DeHon,
*Reconfigurable computing: The theory and practice of FPGA-based
computation*. Elsevier, 2010.</span>

</div>

</div>

  [\#1a1]: /zettel/1a1