CIRCT  18.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 basic problem using linear programming and an external LP solver.
66 /// The objective is to minimize the start time of the given \p lastOp. Fails if
67 /// the dependence graph contains cycles, or \p prob does not include \p lastOp.
68 LogicalResult scheduleLP(Problem &prob, Operation *lastOp);
69 
70 /// Solve the resource-free cyclic problem using integer linear programming and
71 /// an external ILP solver. The objectives are to determine the smallest
72 /// feasible initiation interval, and to minimize the start time of the given \p
73 /// lastOp. Fails if the dependence graph contains cycles that do not include at
74 /// least one edge with a non-zero distance, or \p prob does not include
75 /// \p lastOp.
76 LogicalResult scheduleLP(CyclicProblem &prob, Operation *lastOp);
77 
78 /// Solve the acyclic problem with shared operators using constraint programming
79 /// and an external SAT solver. The objective is to minimize the start time of
80 /// the given \p lastOp. Fails if the dependence graph contains cycles, or \p
81 /// prob does not include \p lastOp.
82 LogicalResult scheduleCPSAT(SharedOperatorsProblem &prob, Operation *lastOp);
83 
84 } // namespace scheduling
85 } // namespace circt
86 
87 #endif // CIRCT_SCHEDULING_ALGORITHMS_H
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
Definition: Problems.h:340
This class models a cyclic scheduling problem.
Definition: Problems.h:292
This class models the modulo scheduling problem as the composition of the cyclic problem and the reso...
Definition: Problems.h:446
This class models the most basic scheduling problem.
Definition: Problems.h:87
This class models a resource-constrained scheduling problem.
Definition: Problems.h:408
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.
This file defines an intermediate representation for circuits acting as an abstraction for constraint...