CIRCT  19.0.0git
CPSATSchedulers.cpp
Go to the documentation of this file.
1 //===- CPSATSchedulers.cpp - Schedulers using external CPSAT solvers
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 // Implementation of cp-sat programming-based schedulers using external solvers
10 // via OR-Tools.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 
16 #include "mlir/IR/Operation.h"
17 
18 #include "ortools/sat/cp_model.h"
19 
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/Format.h"
22 
23 #define DEBUG_TYPE "cpsat-schedulers"
24 
25 using namespace circt;
26 using namespace circt::scheduling;
27 using namespace operations_research;
28 using namespace operations_research::sat;
29 
30 using llvm::dbgs;
31 using llvm::format;
32 
33 /// Solve the shared operators problem by modeling it as a Resource
34 /// Constrained Project Scheduling Problem (RCPSP), which in turn is formulated
35 /// as a Constraint Programming (CP) Satisfiability (SAT) problem.
36 ///
37 /// This is a high-fidelity translation of
38 /// https://github.com/google/or-tools/blob/stable/examples/python/rcpsp_sat.py
39 /// but a gentler introduction (though with differing formulation) is
40 /// https://python-mip.readthedocs.io/en/latest/examples.html
42  Operation *lastOp) {
43  Operation *containingOp = prob.getContainingOp();
44  if (!prob.hasOperation(lastOp))
45  return containingOp->emitError("problem does not include last operation");
46 
47  CpModelBuilder cpModel;
48  auto &tasks = prob.getOperations();
49 
50  DenseMap<Operation *, IntVar> taskStarts;
51  DenseMap<Operation *, IntVar> taskEnds;
52  DenseMap<Problem::OperatorType, SmallVector<IntervalVar, 4>>
53  resourcesToTaskIntervals;
54 
55  // First get horizon, i.e., the time taken if all operations were executed
56  // sequentially.
57  unsigned horizon = 0;
58  for (auto *task : tasks) {
59  unsigned duration = *prob.getLatency(*prob.getLinkedOperatorType(task));
60  horizon += duration;
61  }
62 
63  // Build task-interval decision variables, which effectively serve to
64  // constrain startVar and endVar to be duration apart. Then map them
65  // to the resources (operators) consumed during those intervals. Note,
66  // resources are in fact not constrained to be occupied for the whole of the
67  // task interval, but only during the first "tick". See comment below
68  // regarding cpModel.NewFixedSizeIntervalVar.
69  for (auto item : llvm::enumerate(tasks)) {
70  auto i = item.index();
71  auto *task = item.value();
72  IntVar startVar = cpModel.NewIntVar(Domain(0, horizon))
73  .WithName((Twine("start_of_task_") + Twine(i)).str());
74  IntVar endVar = cpModel.NewIntVar(Domain(0, horizon))
75  .WithName((Twine("end_of_task_") + Twine(i)).str());
76  taskStarts[task] = startVar;
77  taskEnds[task] = endVar;
78  auto resource = prob.getLinkedOperatorType(task);
79  unsigned duration = *prob.getLatency(*resource);
80  IntervalVar taskInterval =
81  cpModel.NewIntervalVar(startVar, duration, endVar)
82  .WithName((Twine("task_interval_") + Twine(i)).str());
83 
84  if (prob.getLimit(*resource))
85  resourcesToTaskIntervals[resource.value()].emplace_back(taskInterval);
86  }
87 
88  // Check for cycles and otherwise establish operation ordering
89  // constraints.
90  for (Operation *task : tasks) {
91  for (auto dep : prob.getDependences(task)) {
92  Operation *src = dep.getSource();
93  Operation *dst = dep.getDestination();
94  if (src == dst)
95  return containingOp->emitError() << "dependence cycle detected";
96  cpModel.AddLessOrEqual(taskEnds[src], taskStarts[dst]);
97  }
98  }
99 
100  // Establish "cumulative" constraints in order to constrain maximum
101  // concurrent usage of operators.
102  for (auto resourceToTaskIntervals : resourcesToTaskIntervals) {
103  Problem::OperatorType &resource = resourceToTaskIntervals.getFirst();
104  auto capacity = prob.getLimit(resource);
105  SmallVector<IntervalVar, 4> &taskIntervals =
106  resourceToTaskIntervals.getSecond();
107  // The semantics of cumulative constraints in or-tools are such that
108  // for any integer point, the sum of the demands across all
109  // intervals containing that point does not exceed the capacity of the
110  // resource. Thus tasks, in 1-1 correspondence with their intervals, are
111  // constrained to satisfy maximum resource requirements.
112  // See https://or.stackexchange.com/a/3363 for more details.
113  CumulativeConstraint cumu = cpModel.AddCumulative(capacity.value());
114  for (const auto &item : llvm::enumerate(taskIntervals)) {
115  auto i = item.index();
116  auto taskInterval = item.value();
117  IntVar demandVar = cpModel.NewIntVar(Domain(1)).WithName(
118  (Twine("demand_") + Twine(i) + Twine("_") + Twine(resource.strref()))
119  .str());
120  // Conventional formulation for SharedOperatorsProblem;
121  // interval during which the resource is occupied has size 1.
122  IntervalVar start =
123  cpModel.NewFixedSizeIntervalVar(taskInterval.StartExpr(), 1);
124  cumu.AddDemand(start, demandVar);
125  }
126  }
127 
128  cpModel.Minimize(taskEnds[lastOp]);
129 
130  Model model;
131 
132  int numSolutions = 0;
133  model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse &r) {
134  LLVM_DEBUG(dbgs() << "Solution " << numSolutions << '\n');
135  LLVM_DEBUG(dbgs() << "Solution status" << r.status() << '\n');
136  ++numSolutions;
137  }));
138 
139  LLVM_DEBUG(dbgs() << "Starting solver\n");
140  const CpSolverResponse response = SolveCpModel(cpModel.Build(), &model);
141 
142  if (response.status() == CpSolverStatus::OPTIMAL ||
143  response.status() == CpSolverStatus::FEASIBLE) {
144  for (auto *task : tasks)
145  prob.setStartTime(task, SolutionIntegerValue(response, taskStarts[task]));
146 
147  return success();
148  }
149  return containingOp->emitError() << "infeasible";
150 }
std::optional< OperatorType > getLinkedOperatorType(Operation *op)
The linked operator type provides the runtime characteristics for op.
Definition: Problems.h:202
bool hasOperation(Operation *op)
Return true if op is part of this problem.
Definition: Problems.h:176
void setStartTime(Operation *op, unsigned val)
Definition: Problems.h:221
DependenceRange getDependences(Operation *op)
Return a range object to transparently iterate over op's incoming 1) implicit def-use dependences (ba...
Definition: Problems.cpp:53
const OperationSet & getOperations()
Return the set of operations.
Definition: Problems.h:178
mlir::StringAttr OperatorType
Operator types are distinguished by name (chosen by the client).
Definition: Problems.h:104
std::optional< unsigned > getLatency(OperatorType opr)
The latency is the number of cycles opr needs to compute its result.
Definition: Problems.h:210
Operation * getContainingOp()
Return the operation containing this problem, e.g. to emit diagnostics.
Definition: Problems.h:171
This class models a resource-constrained scheduling problem.
Definition: Problems.h:409
std::optional< unsigned > getLimit(OperatorType opr)
The limit is the maximum number of operations using opr that are allowed to start in the same time st...
Definition: Problems.h:418
Domain
The number of values each bit of a type can assume.
Definition: MooreTypes.h:27
LogicalResult scheduleCPSAT(SharedOperatorsProblem &prob, Operation *lastOp)
Solve the acyclic problem with shared operators using constraint programming and an external SAT solv...
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21