Loading [MathJax]/extensions/tex2jax.js
CIRCT 21.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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
25using namespace circt;
26using namespace circt::scheduling;
27using namespace operations_research;
28using namespace operations_research::sat;
29
30using llvm::dbgs;
31using 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::ResourceType, 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 opr = prob.getLinkedOperatorType(task);
79 unsigned duration = *prob.getLatency(*opr);
80 IntervalVar taskInterval =
81 cpModel.NewIntervalVar(startVar, duration, endVar)
82 .WithName((Twine("task_interval_") + Twine(i)).str());
83
84 auto resourceListOpt = prob.getLinkedResourceTypes(task);
85 if (resourceListOpt) {
86 for (const auto &resource : *resourceListOpt) {
87 if (auto limitOpt = prob.getLimit(resource))
88 resourcesToTaskIntervals[resource].push_back(taskInterval);
89 }
90 }
91 }
92
93 // Check for cycles and otherwise establish operation ordering
94 // constraints.
95 for (Operation *task : tasks) {
96 for (auto dep : prob.getDependences(task)) {
97 Operation *src = dep.getSource();
98 Operation *dst = dep.getDestination();
99 if (src == dst)
100 return containingOp->emitError() << "dependence cycle detected";
101 cpModel.AddLessOrEqual(taskEnds[src], taskStarts[dst]);
102 }
103 }
104
105 // Establish "cumulative" constraints in order to constrain maximum
106 // concurrent usage of operators.
107 for (auto resourceToTaskIntervals : resourcesToTaskIntervals) {
108 Problem::ResourceType &resource = resourceToTaskIntervals.getFirst();
109 auto capacity = prob.getLimit(resource);
110 SmallVector<IntervalVar, 4> &taskIntervals =
111 resourceToTaskIntervals.getSecond();
112 // The semantics of cumulative constraints in or-tools are such that
113 // for any integer point, the sum of the demands across all
114 // intervals containing that point does not exceed the capacity of the
115 // resource. Thus tasks, in 1-1 correspondence with their intervals, are
116 // constrained to satisfy maximum resource requirements.
117 // See https://or.stackexchange.com/a/3363 for more details.
118 CumulativeConstraint cumu = cpModel.AddCumulative(capacity.value());
119 for (const auto &item : llvm::enumerate(taskIntervals)) {
120 auto i = item.index();
121 auto taskInterval = item.value();
122 IntVar demandVar = cpModel.NewIntVar(Domain(1)).WithName(
123 (Twine("demand_") + Twine(i) + Twine("_") +
124 Twine(resource.getAttr().strref()))
125 .str());
126 // Conventional formulation for SharedOperatorsProblem;
127 // interval during which the resource is occupied has size 1.
128 IntervalVar start =
129 cpModel.NewFixedSizeIntervalVar(taskInterval.StartExpr(), 1);
130 cumu.AddDemand(start, demandVar);
131 }
132 }
133
134 cpModel.Minimize(taskEnds[lastOp]);
135
136 Model model;
137
138 int numSolutions = 0;
139 model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse &r) {
140 LLVM_DEBUG(dbgs() << "Solution " << numSolutions << '\n');
141 LLVM_DEBUG(dbgs() << "Solution status" << r.status() << '\n');
142 ++numSolutions;
143 }));
144
145 LLVM_DEBUG(dbgs() << "Starting solver\n");
146 const CpSolverResponse response = SolveCpModel(cpModel.Build(), &model);
147
148 if (response.status() == CpSolverStatus::OPTIMAL ||
149 response.status() == CpSolverStatus::FEASIBLE) {
150 for (auto *task : tasks)
151 prob.setStartTime(task, SolutionIntegerValue(response, taskStarts[task]));
152
153 return success();
154 }
155 return containingOp->emitError() << "infeasible";
156}
std::optional< unsigned > getLatency(OperatorType opr)
The latency is the number of cycles opr needs to compute its result.
Definition Problems.h:273
bool hasOperation(Operation *op)
Return true if op is part of this problem.
Definition Problems.h:224
std::optional< SmallVector< ResourceType > > getLinkedResourceTypes(Operation *op)
The linked resource type provides the available resources for op.
Definition Problems.h:265
std::optional< OperatorType > getLinkedOperatorType(Operation *op)
The linked operator type provides the runtime characteristics for op.
Definition Problems.h:256
void setStartTime(Operation *op, unsigned val)
Definition Problems.h:284
const OperationSet & getOperations()
Return the set of operations.
Definition Problems.h:226
DependenceRange getDependences(Operation *op)
Return a range object to transparently iterate over op's incoming 1) implicit def-use dependences (ba...
Definition Problems.cpp:59
Operation * getContainingOp()
Return the operation containing this problem, e.g. to emit diagnostics.
Definition Problems.h:219
This class models a resource-constrained scheduling problem.
Definition Problems.h:486
std::optional< unsigned > getLimit(ResourceType rsrc)
The limit is the maximum number of operations using rsrc that are available in the target hardware.
Definition Problems.h:500
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.
Resource types are distinguished by name (chosen by the client).
Definition Problems.h:120
mlir::StringAttr getAttr() const
Definition Problems.h:130