CIRCT
20.0.0git

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 resourceconstrained scheduling problem. More...  
class  ModuloProblem 
This class models the modulo scheduling problem as the composition of the cyclic problem and the resourceconstrained problem with fullypipelined 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 resourcefree 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 programmingbased heuristic. More...  
LogicalResult  scheduleSimplex (ModuloProblem &prob, Operation *lastOp) 
Solve the modulo scheduling problem using a linear programmingbased heuristic. More...  
LogicalResult  scheduleSimplex (ChainingProblem &prob, Operation *lastOp, float cycleTime) 
Solve the acyclic, chainingenabled problem using linear programming and a handwritten implementation of the simplex algorithm. More...  
LogicalResult  scheduleSimplex (ChainingCyclicProblem &prob, Operation *lastOp, float cycleTime) 
Solve the resourcefree cyclic, chainingenabled problem using a linear programmingbased 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 resourcefree 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...  
using circt::scheduling::HandleOpFn = typedef std::function<LogicalResult(Operation *)> 
Definition at line 25 of file Utilities.h.
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.
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::ChainingProblem::clearStartTimeInCycle(), circt::scheduling::Problem::getDependences(), circt::scheduling::Problem::getStartTime(), handleOperationsInTopologicalOrder(), and circt::scheduling::ChainingProblem::setStartTimeInCycle().
void circt::scheduling::dumpAsDOT  (  Problem &  prob, 
raw_ostream &  stream  
) 
Print prob
as a DOT graph onto stream
.
Definition at line 62 of file Utilities.cpp.
References circt::scheduling::Problem::getDependences(), circt::scheduling::Problem::getOperations(), circt::scheduling::Problem::getOperatorTypes(), and circt::scheduling::Problem::getProperties().
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().
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().
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().
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 highfidelity translation of https://github.com/google/ortools/blob/stable/examples/python/rcpsp_sat.py but a gentler introduction (though with differing formulation) is https://pythonmip.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().
LogicalResult circt::scheduling::scheduleLP  (  CyclicProblem &  prob, 
Operation *  lastOp  
) 
Solve the resourcefree 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 nonzero 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().
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().
LogicalResult circt::scheduling::scheduleSimplex  (  ChainingCyclicProblem &  prob, 
Operation *  lastOp,  
float  cycleTime  
) 
Solve the resourcefree cyclic, chainingenabled problem using a linear programmingbased 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 nonzero distance, individual operator types have delays larger than cycleTime
, or prob
does not include lastOp
.
Definition at line 1363 of file SimplexSchedulers.cpp.
LogicalResult circt::scheduling::scheduleSimplex  (  ChainingProblem &  prob, 
Operation *  lastOp,  
float  cycleTime  
) 
Solve the acyclic, chainingenabled 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.
LogicalResult circt::scheduling::scheduleSimplex  (  CyclicProblem &  prob, 
Operation *  lastOp  
) 
Solve the resourcefree 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 nonzero distance, or prob
does not include lastOp
.
Definition at line 1339 of file SimplexSchedulers.cpp.
LogicalResult circt::scheduling::scheduleSimplex  (  ModuloProblem &  prob, 
Operation *  lastOp  
) 
Solve the modulo scheduling problem using a linear programmingbased 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 nonzero 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.
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().
LogicalResult circt::scheduling::scheduleSimplex  (  SharedOperatorsProblem &  prob, 
Operation *  lastOp  
) 
Solve the acyclic problem with shared operators using a linear programmingbased 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.