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::ChainingProblem::clearStartTimeInCycle(), 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
	)

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().

◆ 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.

Namespaces

Classes

Typedefs

Functions

Typedef Documentation

◆ HandleOpFn

Function Documentation

◆ computeChainBreakingDependences()

◆ computeStartTimesInCycle()

◆ dumpAsDOT() [1/2]

◆ dumpAsDOT() [2/2]

◆ handleOperationsInTopologicalOrder()

◆ scheduleASAP()

◆ scheduleCPSAT()

◆ scheduleLP() [1/2]

◆ scheduleLP() [2/2]

◆ scheduleSimplex() [1/6]

◆ scheduleSimplex() [2/6]

◆ scheduleSimplex() [3/6]

◆ scheduleSimplex() [4/6]

◆ scheduleSimplex() [5/6]

◆ scheduleSimplex() [6/6]