CIRCT  20.0.0git
Algorithms.h
Go to the documentation of this file.
1 //===- Algorithms.h - Library of scheduling algorithms ----------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines a library of scheduling algorithms.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef CIRCT_SCHEDULING_ALGORITHMS_H
14 #define CIRCT_SCHEDULING_ALGORITHMS_H
15 
17 
18 namespace circt {
19 namespace scheduling {
20 
21 /// This is a simple list scheduler for solving the basic scheduling problem.
22 /// Its objective is to assign each operation its earliest possible start time,
23 /// or in other words, to schedule each operation as soon as possible (hence the
24 /// name). Fails if the dependence graph contains cycles.
25 LogicalResult scheduleASAP(Problem &prob);
26 
27 /// Solve the basic problem using linear programming and a handwritten
28 /// implementation of the simplex algorithm. The objective is to minimize the
29 /// start time of the given \p lastOp. Fails if the dependence graph contains
30 /// cycles, or \p prob does not include \p lastOp.
31 LogicalResult scheduleSimplex(Problem &prob, Operation *lastOp);
32 
33 /// Solve the resource-free cyclic problem using linear programming and a
34 /// handwritten implementation of the simplex algorithm. The objectives are to
35 /// determine the smallest feasible initiation interval, and to minimize the
36 /// start time of the given \p lastOp. Fails if the dependence graph contains
37 /// cycles that do not include at least one edge with a non-zero distance, or
38 /// \p prob does not include \p lastOp.
39 LogicalResult scheduleSimplex(CyclicProblem &prob, Operation *lastOp);
40 
41 /// Solve the acyclic problem with shared operators using a linear
42 /// programming-based heuristic. The approach tries to minimize the start time
43 /// of the given \p lastOp, but optimality is not guaranteed. Fails if the
44 /// dependence graph contains cycles, or \p prob does not include \p lastOp.
45 LogicalResult scheduleSimplex(SharedOperatorsProblem &prob, Operation *lastOp);
46 
47 /// Solve the modulo scheduling problem using a linear programming-based
48 /// heuristic. The approach tries to determine the smallest feasible initiation
49 /// interval, and to minimize the start time of the given \p lastOp, but
50 /// optimality is not guaranteed. Fails if the dependence graph contains cycles
51 /// that do not include at least one edge with a non-zero distance, \p prob
52 /// does not include \p lastOp, or \p lastOp is not the unique sink of the
53 /// dependence graph.
54 LogicalResult scheduleSimplex(ModuloProblem &prob, Operation *lastOp);
55 
56 /// Solve the acyclic, chaining-enabled problem using linear programming and a
57 /// handwritten implementation of the simplex algorithm. This approach strictly
58 /// adheres to the given maximum \p cycleTime. The objective is to minimize the
59 /// start time of the given \p lastOp. Fails if the dependence graph contains
60 /// cycles, or individual operator types have delays larger than \p cycleTime,
61 /// or \p prob does not include \p lastOp.
62 LogicalResult scheduleSimplex(ChainingProblem &prob, Operation *lastOp,
63  float cycleTime);
64 
65 /// Solve the resource-free cyclic, chaining-enabled problem using a linear
66 /// programming-based and a handwritten implementation of the simplex algorithm.
67 /// This approach is an hybrid approach of the ChainingProblem simplex scheduler
68 /// and the CyclicProblem simplex scheduler. The objectives include determining
69 /// the smallest feasible initiation interval, and to minimize the start time of
70 /// a given \p lastOp. Fails if the dependence graph contains cycles that does
71 /// not include at least one edge with a non-zero distance, individual operator
72 /// types have delays larger than \p cycleTime, or \p prob does not include
73 /// \p lastOp.
74 LogicalResult scheduleSimplex(ChainingCyclicProblem &prob, Operation *lastOp,
75  float cycleTime);
76 
77 /// Solve the basic problem using linear programming and an external LP solver.
78 /// The objective is to minimize the start time of the given \p lastOp. Fails if
79 /// the dependence graph contains cycles, or \p prob does not include \p lastOp.
80 LogicalResult scheduleLP(Problem &prob, Operation *lastOp);
81 
82 /// Solve the resource-free cyclic problem using integer linear programming and
83 /// an external ILP solver. The objectives are to determine the smallest
84 /// feasible initiation interval, and to minimize the start time of the given \p
85 /// lastOp. Fails if the dependence graph contains cycles that do not include at
86 /// least one edge with a non-zero distance, or \p prob does not include
87 /// \p lastOp.
88 LogicalResult scheduleLP(CyclicProblem &prob, Operation *lastOp);
89 
90 /// Solve the acyclic problem with shared operators using constraint programming
91 /// and an external SAT solver. The objective is to minimize the start time of
92 /// the given \p lastOp. Fails if the dependence graph contains cycles, or \p
93 /// prob does not include \p lastOp.
94 LogicalResult scheduleCPSAT(SharedOperatorsProblem &prob, Operation *lastOp);
95 
96 } // namespace scheduling
97 } // namespace circt
98 
99 #endif // CIRCT_SCHEDULING_ALGORITHMS_H
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
Definition: Problems.h:485
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
Definition: Problems.h:339
This class models a cyclic scheduling problem.
Definition: Problems.h:286
This class models the modulo scheduling problem as the composition of the cyclic problem and the reso...
Definition: Problems.h:456
This class models the most basic scheduling problem.
Definition: Problems.h:75
This class models a resource-constrained scheduling problem.
Definition: Problems.h:413
LogicalResult scheduleLP(Problem &prob, Operation *lastOp)
Solve the basic problem using linear programming and an external LP solver.
LogicalResult scheduleCPSAT(SharedOperatorsProblem &prob, Operation *lastOp)
Solve the acyclic problem with shared operators using constraint programming and an external SAT solv...
LogicalResult scheduleSimplex(Problem &prob, Operation *lastOp)
Solve the basic problem using linear programming and a handwritten implementation of the simplex algo...
LogicalResult scheduleASAP(Problem &prob)
This is a simple list scheduler for solving the basic scheduling problem.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21