CIRCT  19.0.0git
Namespaces | Classes | Typedefs | Functions
circt::scheduling Namespace Reference

Namespaces

 detail
 

Classes

class  Problem
 This class models the most basic scheduling problem. More...
 
class  CyclicProblem
 This class models a cyclic scheduling problem. More...
 
class  ChainingProblem
 This class models the accumulation of physical propagation delays on combinational paths along SSA dependences. More...
 
class  SharedOperatorsProblem
 This class models a resource-constrained scheduling problem. More...
 
class  ModuloProblem
 This class models the modulo scheduling problem as the composition of the cyclic problem and the resource-constrained problem with fully-pipelined shared operators. More...
 
class  ChainingCyclicProblem
 This class models the accumulation of physical propagation delays on combinational paths along SSA dependences on a cyclic scheduling problem. More...
 

Typedefs

using HandleOpFn = std::function< LogicalResult(Operation *)>
 

Functions

LogicalResult scheduleASAP (Problem &prob)
 This is a simple list scheduler for solving the basic scheduling problem. More...
 
LogicalResult scheduleSimplex (Problem &prob, Operation *lastOp)
 Solve the basic problem using linear programming and a handwritten implementation of the simplex algorithm. More...
 
LogicalResult scheduleSimplex (CyclicProblem &prob, Operation *lastOp)
 Solve the resource-free cyclic problem using linear programming and a handwritten implementation of the simplex algorithm. More...
 
LogicalResult scheduleSimplex (SharedOperatorsProblem &prob, Operation *lastOp)
 Solve the acyclic problem with shared operators using a linear programming-based heuristic. More...
 
LogicalResult scheduleSimplex (ModuloProblem &prob, Operation *lastOp)
 Solve the modulo scheduling problem using a linear programming-based heuristic. More...
 
LogicalResult scheduleSimplex (ChainingProblem &prob, Operation *lastOp, float cycleTime)
 Solve the acyclic, chaining-enabled problem using linear programming and a handwritten implementation of the simplex algorithm. More...
 
LogicalResult scheduleSimplex (ChainingCyclicProblem &prob, Operation *lastOp, float cycleTime)
 Solve the resource-free cyclic, chaining-enabled problem using a linear programming-based and a handwritten implementation of the simplex algorithm. More...
 
LogicalResult scheduleLP (Problem &prob, Operation *lastOp)
 Solve the basic problem using linear programming and an external LP solver. More...
 
LogicalResult scheduleLP (CyclicProblem &prob, Operation *lastOp)
 Solve the resource-free cyclic problem using integer linear programming and an external ILP solver. More...
 
LogicalResult scheduleCPSAT (SharedOperatorsProblem &prob, Operation *lastOp)
 Solve the acyclic problem with shared operators using constraint programming and an external SAT solver. More...
 
LogicalResult handleOperationsInTopologicalOrder (Problem &prob, HandleOpFn fun)
 Visit prob's operations in topological order, using an internal worklist. More...
 
LogicalResult computeChainBreakingDependences (ChainingProblem &prob, float cycleTime, SmallVectorImpl< Problem::Dependence > &result)
 Analyse combinational chains in prob's dependence graph and determine pairs of operations that must be separated by at least one time step in order to prevent the accumulated delays exceeding the given cycleTime. More...
 
LogicalResult computeStartTimesInCycle (ChainingProblem &prob)
 Assuming prob is scheduled and contains (integer) start times, this method fills in the start times in cycle in an ASAP fashion. More...
 
void dumpAsDOT (Problem &prob, StringRef fileName)
 Export prob as a DOT graph into fileName. More...
 
void dumpAsDOT (Problem &prob, raw_ostream &stream)
 Print prob as a DOT graph onto stream. More...
 

Typedef Documentation

◆ HandleOpFn

using circt::scheduling::HandleOpFn = typedef std::function<LogicalResult(Operation *)>

Definition at line 25 of file Utilities.h.

Function Documentation

◆ computeChainBreakingDependences()

LogicalResult circt::scheduling::computeChainBreakingDependences ( ChainingProblem prob,
float  cycleTime,
SmallVectorImpl< Problem::Dependence > &  result 
)

Analyse combinational chains in prob's dependence graph and determine pairs of operations that must be separated by at least one time step in order to prevent the accumulated delays exceeding the given cycleTime.

The dependences in the result vector require special handling in the concrete scheduling algorithm.

Fails if prob contains operator types with incoming/outgoing delays greater than cycleTime, or if the dependence graph contains cycles.

◆ computeStartTimesInCycle()

LogicalResult circt::scheduling::computeStartTimesInCycle ( ChainingProblem prob)

Assuming prob is scheduled and contains (integer) start times, this method fills in the start times in cycle in an ASAP fashion.

Fails if the dependence graph contains cycles.

Definition at line 93 of file ChainingSupport.cpp.

References circt::scheduling::Problem::getDependences(), circt::scheduling::Problem::getStartTime(), handleOperationsInTopologicalOrder(), and circt::scheduling::ChainingProblem::setStartTimeInCycle().

◆ dumpAsDOT() [1/2]

void circt::scheduling::dumpAsDOT ( Problem prob,
raw_ostream &  stream 
)

◆ dumpAsDOT() [2/2]

void circt::scheduling::dumpAsDOT ( Problem prob,
StringRef  fileName 
)

Export prob as a DOT graph into fileName.

Definition at line 55 of file Utilities.cpp.

Referenced by printInstance().

◆ handleOperationsInTopologicalOrder()

LogicalResult circt::scheduling::handleOperationsInTopologicalOrder ( Problem prob,
HandleOpFn  fun 
)

Visit prob's operations in topological order, using an internal worklist.

fun is expected to report success if the given operation was handled successfully, and failure if an unhandled predecessor was detected.

Fails if the dependence graph contains cycles.

Definition at line 21 of file Utilities.cpp.

References circt::scheduling::Problem::getContainingOp(), and circt::scheduling::Problem::getOperations().

Referenced by computeStartTimesInCycle(), and scheduleASAP().

◆ scheduleASAP()

LogicalResult circt::scheduling::scheduleASAP ( Problem prob)

This is a simple list scheduler for solving the basic scheduling problem.

Its objective is to assign each operation its earliest possible start time, or in other words, to schedule each operation as soon as possible (hence the name). Fails if the dependence graph contains cycles.

Definition at line 19 of file ASAPScheduler.cpp.

References circt::scheduling::Problem::getDependences(), handleOperationsInTopologicalOrder(), and circt::scheduling::Problem::setStartTime().

Referenced by scheduleWithASAP().

◆ scheduleCPSAT()

LogicalResult circt::scheduling::scheduleCPSAT ( SharedOperatorsProblem prob,
Operation *  lastOp 
)

Solve the acyclic problem with shared operators using constraint programming and an external SAT solver.

Solve the shared operators problem by modeling it as a Resource Constrained Project Scheduling Problem (RCPSP), which in turn is formulated as a Constraint Programming (CP) Satisfiability (SAT) problem.

The objective is to minimize the start time of the given lastOp. Fails if the dependence graph contains cycles, or prob does not include lastOp.

This is a high-fidelity translation of https://github.com/google/or-tools/blob/stable/examples/python/rcpsp_sat.py but a gentler introduction (though with differing formulation) is https://python-mip.readthedocs.io/en/latest/examples.html

Definition at line 41 of file CPSATSchedulers.cpp.

References circt::scheduling::Problem::getContainingOp(), circt::scheduling::Problem::getDependences(), circt::scheduling::Problem::getLatency(), circt::scheduling::SharedOperatorsProblem::getLimit(), circt::scheduling::Problem::getLinkedOperatorType(), circt::scheduling::Problem::getOperations(), circt::scheduling::Problem::hasOperation(), and circt::scheduling::Problem::setStartTime().

◆ scheduleLP() [1/2]

LogicalResult circt::scheduling::scheduleLP ( CyclicProblem prob,
Operation *  lastOp 
)

Solve the resource-free cyclic problem using integer linear programming and an external ILP solver.

The objectives are to determine the smallest feasible initiation interval, and to minimize the start time of the given lastOp. Fails if the dependence graph contains cycles that do not include at least one edge with a non-zero distance, or prob does not include lastOp.

Definition at line 81 of file LPSchedulers.cpp.

References assert(), circt::scheduling::Problem::getContainingOp(), circt::scheduling::Problem::getDependences(), circt::scheduling::CyclicProblem::getDistance(), circt::scheduling::Problem::getLatency(), circt::scheduling::Problem::getLinkedOperatorType(), circt::scheduling::Problem::getOperations(), circt::scheduling::Problem::hasOperation(), circt::scheduling::CyclicProblem::setInitiationInterval(), and circt::scheduling::Problem::setStartTime().

◆ scheduleLP() [2/2]

LogicalResult circt::scheduling::scheduleLP ( Problem prob,
Operation *  lastOp 
)

Solve the basic problem using linear programming and an external LP solver.

The objective is to minimize the start time of the given lastOp. Fails if the dependence graph contains cycles, or prob does not include lastOp.

Definition at line 24 of file LPSchedulers.cpp.

References assert(), circt::scheduling::Problem::getContainingOp(), circt::scheduling::Problem::getDependences(), circt::scheduling::Problem::getLatency(), circt::scheduling::Problem::getLinkedOperatorType(), circt::scheduling::Problem::getOperations(), circt::scheduling::Problem::hasOperation(), and circt::scheduling::Problem::setStartTime().

◆ scheduleSimplex() [1/6]

LogicalResult circt::scheduling::scheduleSimplex ( ChainingCyclicProblem prob,
Operation *  lastOp,
float  cycleTime 
)

Solve the resource-free cyclic, chaining-enabled problem using a linear programming-based and a handwritten implementation of the simplex algorithm.

This approach is an hybrid approach of the ChainingProblem simplex scheduler and the CyclicProblem simplex scheduler. The objectives include determining the smallest feasible initiation interval, and to minimize the start time of a given lastOp. Fails if the dependence graph contains cycles that does not include at least one edge with a non-zero distance, individual operator types have delays larger than cycleTime, or prob does not include lastOp.

Definition at line 1363 of file SimplexSchedulers.cpp.

◆ scheduleSimplex() [2/6]

LogicalResult circt::scheduling::scheduleSimplex ( ChainingProblem prob,
Operation *  lastOp,
float  cycleTime 
)

Solve the acyclic, chaining-enabled problem using linear programming and a handwritten implementation of the simplex algorithm.

This approach strictly adheres to the given maximum cycleTime. The objective is to minimize the start time of the given lastOp. Fails if the dependence graph contains cycles, or individual operator types have delays larger than cycleTime, or prob does not include lastOp.

Definition at line 1357 of file SimplexSchedulers.cpp.

◆ scheduleSimplex() [3/6]

LogicalResult circt::scheduling::scheduleSimplex ( CyclicProblem prob,
Operation *  lastOp 
)

Solve the resource-free cyclic problem using linear programming and a handwritten implementation of the simplex algorithm.

The objectives are to determine the smallest feasible initiation interval, and to minimize the start time of the given lastOp. Fails if the dependence graph contains cycles that do not include at least one edge with a non-zero distance, or prob does not include lastOp.

Definition at line 1339 of file SimplexSchedulers.cpp.

◆ scheduleSimplex() [4/6]

LogicalResult circt::scheduling::scheduleSimplex ( ModuloProblem prob,
Operation *  lastOp 
)

Solve the modulo scheduling problem using a linear programming-based heuristic.

The approach tries to determine the smallest feasible initiation interval, and to minimize the start time of the given lastOp, but optimality is not guaranteed. Fails if the dependence graph contains cycles that do not include at least one edge with a non-zero distance, prob does not include lastOp, or lastOp is not the unique sink of the dependence graph.

Definition at line 1351 of file SimplexSchedulers.cpp.

◆ scheduleSimplex() [5/6]

LogicalResult circt::scheduling::scheduleSimplex ( Problem prob,
Operation *  lastOp 
)

Solve the basic problem using linear programming and a handwritten implementation of the simplex algorithm.

The objective is to minimize the start time of the given lastOp. Fails if the dependence graph contains cycles, or prob does not include lastOp.

Definition at line 1334 of file SimplexSchedulers.cpp.

Referenced by scheduleChainingCyclicProblemWithSimplex(), scheduleChainingProblemWithSimplex(), and scheduleProblemTWithSimplex().

◆ scheduleSimplex() [6/6]

LogicalResult circt::scheduling::scheduleSimplex ( SharedOperatorsProblem prob,
Operation *  lastOp 
)

Solve the acyclic problem with shared operators using a linear programming-based heuristic.

The approach tries to minimize the start time of the given lastOp, but optimality is not guaranteed. Fails if the dependence graph contains cycles, or prob does not include lastOp.

Definition at line 1345 of file SimplexSchedulers.cpp.