Loading [MathJax]/extensions/tex2jax.js
CIRCT 21.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
SimplexSchedulers.cpp
Go to the documentation of this file.
1//===- SimplexSchedulers.cpp - Linear programming-based schedulers --------===//
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 linear programming-based schedulers with a built-in simplex
10// solver.
11//
12//===----------------------------------------------------------------------===//
13
16
17#include "mlir/IR/Operation.h"
18
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/Format.h"
22
23#include <algorithm>
24#include <limits>
25
26#define DEBUG_TYPE "simplex-schedulers"
27
28using namespace circt;
29using namespace circt::scheduling;
30
31using llvm::dbgs;
32using llvm::format;
33
34namespace {
35
36/// This class provides a framework to model certain scheduling problems as
37/// lexico-parametric linear programs (LP), which are then solved with an
38/// extended version of the dual simplex algorithm.
39///
40/// The approach is described in:
41/// [1] B. D. de Dinechin, "Simplex Scheduling: More than Lifetime-Sensitive
42/// Instruction Scheduling", PRISM 1994.22, 1994.
43/// [2] B. D. de Dinechin, "Fast Modulo Scheduling Under the Simplex Scheduling
44/// Framework", PRISM 1995.01, 1995.
45///
46/// Resource-free scheduling problems (called "central problems" in the papers)
47/// have an *integer* linear programming formulation with a totally unimodular
48/// constraint matrix. Such ILPs can however be solved optimally in polynomial
49/// time with a (non-integer) LP solver (such as the simplex algorithm), as the
50/// LP solution is guaranteed to be integer. Note that this is the same idea as
51/// used by SDC-based schedulers.
52class SimplexSchedulerBase {
53protected:
54 /// The objective is to minimize the start time of this operation.
55 Operation *lastOp;
56
57 /// S is part of a mechanism to assign fixed values to the LP variables.
58 int parameterS;
59
60 /// T represents the initiation interval (II). Its minimally-feasible value is
61 /// computed by the algorithm.
62 int parameterT;
63
64 /// The simplex tableau is the algorithm's main data structure.
65 /// The dashed parts always contain the zero respectively the identity matrix,
66 /// and therefore are not stored explicitly.
67 ///
68 /// ◀───nColumns────▶
69 /// nParameters────┐
70 /// ◀─┴─▶
71 /// ┌─────┬───────────┬ ─ ─ ─ ─ ┐
72 /// ▲│. . .│. . ... . .│ 0 ▲
73 /// nObjectives││. . .│. . ... . .│ │ │
74 /// ▼│. . .│. . ... . .│ │
75 /// ├─────┼───────────┼ ─ ─ ─ ─ ┤ │
76 /// firstConstraintRow > │. . .│. . ... . .│1 │nRows
77 /// │. . .│. . ... . .│ 1 │ │
78 /// │. . .│. . ... . .│ 1 │
79 /// │. . .│. . ... . .│ 1 │ │
80 /// │. . .│. . ... . .│ 1 ▼
81 /// └─────┴───────────┴ ─ ─ ─ ─ ┘
82 /// parameter1Column ^
83 /// parameterSColumn ^
84 /// parameterTColumn ^
85 /// firstNonBasicVariableColumn ^
86 /// ─────────── ──────────
87 /// nonBasicVariables basicVariables
88 SmallVector<SmallVector<int>> tableau;
89
90 /// During the pivot operation, one column in the elided part of the tableau
91 /// is modified; this vector temporarily catches the changes.
92 SmallVector<int> implicitBasicVariableColumnVector;
93
94 /// The linear program models the operations' start times as variables, which
95 /// we identify here as 0, ..., |ops|-1.
96 /// Additionally, for each dependence (precisely, the inequality modeling the
97 /// precedence constraint), a slack variable is required; these are identified
98 /// as |ops|, ..., |ops|+|deps|-1.
99 ///
100 /// This vector stores the numeric IDs of non-basic variables. A variable's
101 /// index *i* in this vector corresponds to the tableau *column*
102 /// `firstNonBasicVariableColumn`+*i*.
103 SmallVector<unsigned> nonBasicVariables;
104
105 /// This vector store the numeric IDs of basic variables. A variable's index
106 /// *i* in this vector corresponds to the tableau *row*
107 /// `firstConstraintRow`+*i*.
108 SmallVector<unsigned> basicVariables;
109
110 /// Used to conveniently retrieve an operation's start time variable. The
111 /// alternative would be to find the op's index in the problem's list of
112 /// operations.
113 DenseMap<Operation *, unsigned> startTimeVariables;
114
115 /// This vector keeps track of the current locations (i.e. row or column) of
116 /// a start time variable in the tableau. We encode column numbers as positive
117 /// integers, and row numbers as negative integers. We do not track the slack
118 /// variables.
119 SmallVector<int> startTimeLocations;
120
121 /// Non-basic variables can be "frozen" to a specific value, which prevents
122 /// them from being pivoted into basis again.
123 DenseMap<unsigned, unsigned> frozenVariables;
124
125 /// Number of rows in the tableau = |obj| + |deps|.
126 unsigned nRows;
127 /// Number of explicitly stored columns in the tableau = |params| + |ops|.
128 unsigned nColumns;
129
130 // Number of objective rows.
131 unsigned nObjectives;
132 /// All other rows encode linear constraints.
133 unsigned &firstConstraintRow = nObjectives;
134
135 // Number of parameters (fixed for now).
136 static constexpr unsigned nParameters = 3;
137 /// The first column corresponds to the always-one "parameter" in u = (1,S,T).
138 static constexpr unsigned parameter1Column = 0;
139 /// The second column corresponds to the variable-freezing parameter S.
140 static constexpr unsigned parameterSColumn = 1;
141 /// The third column corresponds to the parameter T, i.e. the current II.
142 static constexpr unsigned parameterTColumn = 2;
143 /// All other (explicitly stored) columns represent non-basic variables.
144 static constexpr unsigned firstNonBasicVariableColumn = nParameters;
145
146 /// Allow subclasses to collect additional constraints that are not part of
147 /// the input problem, but should be modeled in the linear problem.
148 SmallVector<Problem::Dependence> additionalConstraints;
149
150 virtual Problem &getProblem() = 0;
151 virtual LogicalResult checkLastOp();
152 virtual bool fillObjectiveRow(SmallVector<int> &row, unsigned obj);
153 virtual void fillConstraintRow(SmallVector<int> &row,
155 virtual void fillAdditionalConstraintRow(SmallVector<int> &row,
157 void buildTableau();
158
159 int getParametricConstant(unsigned row);
160 SmallVector<int> getObjectiveVector(unsigned column);
161 std::optional<unsigned> findDualPivotRow();
162 std::optional<unsigned> findDualPivotColumn(unsigned pivotRow,
163 bool allowPositive = false);
164 std::optional<unsigned> findPrimalPivotColumn();
165 std::optional<unsigned> findPrimalPivotRow(unsigned pivotColumn);
166 void multiplyRow(unsigned row, int factor);
167 void addMultipleOfRow(unsigned sourceRow, int factor, unsigned targetRow);
168 void pivot(unsigned pivotRow, unsigned pivotColumn);
169 LogicalResult solveTableau();
170 LogicalResult restoreDualFeasibility();
171 bool isInBasis(unsigned startTimeVariable);
172 unsigned freeze(unsigned startTimeVariable, unsigned timeStep);
173 void translate(unsigned column, int factor1, int factorS, int factorT);
174 LogicalResult scheduleAt(unsigned startTimeVariable, unsigned timeStep);
175 void moveBy(unsigned startTimeVariable, unsigned amount);
176 unsigned getStartTime(unsigned startTimeVariable);
177
178 void dumpTableau();
179
180public:
181 explicit SimplexSchedulerBase(Operation *lastOp) : lastOp(lastOp) {}
182 virtual ~SimplexSchedulerBase() = default;
183 virtual LogicalResult schedule() = 0;
184};
185
186/// This class solves the basic, acyclic `Problem`.
187class SimplexScheduler : public SimplexSchedulerBase {
188private:
189 Problem &prob;
190
191protected:
192 Problem &getProblem() override { return prob; }
193
194public:
195 SimplexScheduler(Problem &prob, Operation *lastOp)
196 : SimplexSchedulerBase(lastOp), prob(prob) {}
197
198 LogicalResult schedule() override;
199};
200
201/// This class solves the resource-free `CyclicProblem`. The optimal initiation
202/// interval (II) is determined as a side product of solving the parametric
203/// problem, and corresponds to the "RecMII" (= recurrence-constrained minimum
204/// II) usually considered as one component in the lower II bound used by modulo
205/// schedulers.
206class CyclicSimplexScheduler : public SimplexSchedulerBase {
207private:
208 CyclicProblem &prob;
209
210protected:
211 Problem &getProblem() override { return prob; }
212 void fillConstraintRow(SmallVector<int> &row,
213 Problem::Dependence dep) override;
214
215public:
216 CyclicSimplexScheduler(CyclicProblem &prob, Operation *lastOp)
217 : SimplexSchedulerBase(lastOp), prob(prob) {}
218 LogicalResult schedule() override;
219};
220
221// This class solves acyclic, resource-constrained `SharedOperatorsProblem` with
222// a simplified version of the iterative heuristic presented in [2].
223class SharedOperatorsSimplexScheduler : public SimplexSchedulerBase {
224private:
226
227protected:
228 Problem &getProblem() override { return prob; }
229
230public:
231 SharedOperatorsSimplexScheduler(SharedOperatorsProblem &prob,
232 Operation *lastOp)
233 : SimplexSchedulerBase(lastOp), prob(prob) {}
234 LogicalResult schedule() override;
235};
236
237// This class solves the `ModuloProblem` using the iterative heuristic presented
238// in [2].
239class ModuloSimplexScheduler : public CyclicSimplexScheduler {
240private:
241 struct MRT {
242 ModuloSimplexScheduler &sched;
243
245 using ReverseTableType = SmallDenseMap<Operation *, unsigned>;
248
249 explicit MRT(ModuloSimplexScheduler &sched) : sched(sched) {}
250 LogicalResult enter(Operation *op, unsigned timeStep);
251 void release(Operation *op);
252 };
253
254 ModuloProblem &prob;
255 SmallVector<unsigned> asapTimes, alapTimes;
256 SmallVector<Operation *> unscheduled, scheduled;
257 MRT mrt;
258
259protected:
260 Problem &getProblem() override { return prob; }
261 LogicalResult checkLastOp() override;
262 enum { OBJ_LATENCY = 0, OBJ_AXAP /* i.e. either ASAP or ALAP */ };
263 bool fillObjectiveRow(SmallVector<int> &row, unsigned obj) override;
264 void updateMargins();
265 void scheduleOperation(Operation *n);
266 unsigned computeResMinII();
267
268public:
269 ModuloSimplexScheduler(ModuloProblem &prob, Operation *lastOp)
270 : CyclicSimplexScheduler(prob, lastOp), prob(prob), mrt(*this) {}
271 LogicalResult schedule() override;
272};
273
274// This class solves the `ChainingProblem` by relying on pre-computed
275// chain-breaking constraints.
276class ChainingSimplexScheduler : public SimplexSchedulerBase {
277private:
278 ChainingProblem &prob;
279 float cycleTime;
280
281protected:
282 Problem &getProblem() override { return prob; }
283 void fillAdditionalConstraintRow(SmallVector<int> &row,
284 Problem::Dependence dep) override;
285
286public:
287 ChainingSimplexScheduler(ChainingProblem &prob, Operation *lastOp,
288 float cycleTime)
289 : SimplexSchedulerBase(lastOp), prob(prob), cycleTime(cycleTime) {}
290 LogicalResult schedule() override;
291};
292
293// This class solves the resource-free `ChainingCyclicProblem` by relying on
294// pre-computed chain-breaking constraints. The optimal initiation interval (II)
295// is determined as a side product of solving the parametric problem, and
296// corresponds to the "RecMII" (= recurrence-constrained minimum II) usually
297// considered as one component in the lower II bound used by modulo schedulers.
298class ChainingCyclicSimplexScheduler : public SimplexSchedulerBase {
299private:
301 float cycleTime;
302
303protected:
304 Problem &getProblem() override { return prob; }
305 void fillConstraintRow(SmallVector<int> &row,
306 Problem::Dependence dep) override;
307 void fillAdditionalConstraintRow(SmallVector<int> &row,
308 Problem::Dependence dep) override;
309
310public:
311 ChainingCyclicSimplexScheduler(ChainingCyclicProblem &prob, Operation *lastOp,
312 float cycleTime)
313 : SimplexSchedulerBase(lastOp), prob(prob), cycleTime(cycleTime) {}
314 LogicalResult schedule() override;
315};
316
317} // anonymous namespace
318
319//===----------------------------------------------------------------------===//
320// SimplexSchedulerBase
321//===----------------------------------------------------------------------===//
322
323LogicalResult SimplexSchedulerBase::checkLastOp() {
324 auto &prob = getProblem();
325 if (!prob.hasOperation(lastOp))
326 return prob.getContainingOp()->emitError(
327 "problem does not include last operation");
328 return success();
329}
330
331bool SimplexSchedulerBase::fillObjectiveRow(SmallVector<int> &row,
332 unsigned obj) {
333 assert(obj == 0);
334 // Minimize start time of user-specified last operation.
335 row[startTimeLocations[startTimeVariables[lastOp]]] = 1;
336 return false;
337}
338
339void SimplexSchedulerBase::fillConstraintRow(SmallVector<int> &row,
341 auto &prob = getProblem();
342 Operation *src = dep.getSource();
343 Operation *dst = dep.getDestination();
344 unsigned latency = *prob.getLatency(*prob.getLinkedOperatorType(src));
345 row[parameter1Column] = -latency; // note the negation
346 if (src != dst) { // note that these coefficients just zero out in self-arcs.
347 row[startTimeLocations[startTimeVariables[src]]] = 1;
348 row[startTimeLocations[startTimeVariables[dst]]] = -1;
349 }
350}
351
352void SimplexSchedulerBase::fillAdditionalConstraintRow(
353 SmallVector<int> &row, Problem::Dependence dep) {
354 // Handling is subclass-specific, so do nothing by default.
355 (void)row;
356 (void)dep;
357}
358
359void SimplexSchedulerBase::buildTableau() {
360 auto &prob = getProblem();
361
362 // The initial tableau is constructed so that operations' start time variables
363 // are out of basis, whereas all slack variables are in basis. We will number
364 // them accordingly.
365 unsigned var = 0;
366
367 // Assign column and variable numbers to the operations' start times.
368 for (auto *op : prob.getOperations()) {
369 nonBasicVariables.push_back(var);
370 startTimeVariables[op] = var;
371 startTimeLocations.push_back(firstNonBasicVariableColumn + var);
372 ++var;
373 }
374
375 // one column for each parameter (1,S,T), and for all operations
376 nColumns = nParameters + nonBasicVariables.size();
377
378 // Helper to grow both the tableau and the implicit column vector.
379 auto addRow = [&]() -> SmallVector<int> & {
380 implicitBasicVariableColumnVector.push_back(0);
381 return tableau.emplace_back(nColumns, 0);
382 };
383
384 // Set up the objective rows.
385 nObjectives = 0;
386 bool hasMoreObjectives;
387 do {
388 auto &objRowVec = addRow();
389 hasMoreObjectives = fillObjectiveRow(objRowVec, nObjectives);
390 ++nObjectives;
391 } while (hasMoreObjectives);
392
393 // Now set up rows/constraints for the dependences.
394 for (auto *op : prob.getOperations()) {
395 for (auto &dep : prob.getDependences(op)) {
396 auto &consRowVec = addRow();
397 fillConstraintRow(consRowVec, dep);
398 basicVariables.push_back(var);
399 ++var;
400 }
401 }
402 for (auto &dep : additionalConstraints) {
403 auto &consRowVec = addRow();
404 fillAdditionalConstraintRow(consRowVec, dep);
405 basicVariables.push_back(var);
406 ++var;
407 }
408
409 // one row per objective + one row per dependence
410 nRows = tableau.size();
411}
412
413int SimplexSchedulerBase::getParametricConstant(unsigned row) {
414 auto &rowVec = tableau[row];
415 // Compute the dot-product ~B[row] * u between the constant matrix and the
416 // parameter vector.
417 return rowVec[parameter1Column] + rowVec[parameterSColumn] * parameterS +
418 rowVec[parameterTColumn] * parameterT;
419}
420
421SmallVector<int> SimplexSchedulerBase::getObjectiveVector(unsigned column) {
422 SmallVector<int> objVec;
423 // Extract the column vector C^T[column] from the cost matrix.
424 for (unsigned obj = 0; obj < nObjectives; ++obj)
425 objVec.push_back(tableau[obj][column]);
426 return objVec;
427}
428
429std::optional<unsigned> SimplexSchedulerBase::findDualPivotRow() {
430 // Find the first row in which the parametric constant is negative.
431 for (unsigned row = firstConstraintRow; row < nRows; ++row)
432 if (getParametricConstant(row) < 0)
433 return row;
434
435 return std::nullopt;
436}
437
438std::optional<unsigned>
439SimplexSchedulerBase::findDualPivotColumn(unsigned pivotRow,
440 bool allowPositive) {
441 SmallVector<int> maxQuot(nObjectives, std::numeric_limits<int>::min());
442 std::optional<unsigned> pivotCol;
443
444 // Look for non-zero entries in the constraint matrix (~A part of the
445 // tableau). If multiple candidates exist, take the one corresponding to the
446 // lexicographical maximum (over the objective rows) of the quotients:
447 // tableau[<objective row>][col] / pivotCand
448 for (unsigned col = firstNonBasicVariableColumn; col < nColumns; ++col) {
449 if (frozenVariables.count(
450 nonBasicVariables[col - firstNonBasicVariableColumn]))
451 continue;
452
453 int pivotCand = tableau[pivotRow][col];
454 // Only negative candidates bring us closer to the optimal solution.
455 // However, when freezing variables to a certain value, we accept that the
456 // value of the objective function degrades.
457 if (pivotCand < 0 || (allowPositive && pivotCand > 0)) {
458 // The constraint matrix has only {-1, 0, 1} entries by construction.
459 assert(pivotCand * pivotCand == 1);
460
461 SmallVector<int> quot;
462 for (unsigned obj = 0; obj < nObjectives; ++obj)
463 quot.push_back(tableau[obj][col] / pivotCand);
464
465 if (std::lexicographical_compare(maxQuot.begin(), maxQuot.end(),
466 quot.begin(), quot.end())) {
467 maxQuot = quot;
468 pivotCol = col;
469 }
470 }
471 }
472
473 return pivotCol;
474}
475
476std::optional<unsigned> SimplexSchedulerBase::findPrimalPivotColumn() {
477 // Find the first lexico-negative column in the cost matrix.
478 SmallVector<int> zeroVec(nObjectives, 0);
479 for (unsigned col = firstNonBasicVariableColumn; col < nColumns; ++col) {
480 if (frozenVariables.count(
481 nonBasicVariables[col - firstNonBasicVariableColumn]))
482 continue;
483
484 SmallVector<int> objVec = getObjectiveVector(col);
485 if (std::lexicographical_compare(objVec.begin(), objVec.end(),
486 zeroVec.begin(), zeroVec.end()))
487 return col;
488 }
489
490 return std::nullopt;
491}
492
493std::optional<unsigned>
494SimplexSchedulerBase::findPrimalPivotRow(unsigned pivotColumn) {
495 int minQuot = std::numeric_limits<int>::max();
496 std::optional<unsigned> pivotRow;
497
498 // Look for positive entries in the constraint matrix (~A part of the
499 // tableau). If multiple candidates exist, take the one corresponding to the
500 // minimum of the quotient:
501 // parametricConstant(row) / pivotCand
502 for (unsigned row = firstConstraintRow; row < nRows; ++row) {
503 int pivotCand = tableau[row][pivotColumn];
504 if (pivotCand > 0) {
505 // The constraint matrix has only {-1, 0, 1} entries by construction.
506 assert(pivotCand == 1);
507 int quot = getParametricConstant(row) / pivotCand;
508 if (quot < minQuot) {
509 minQuot = quot;
510 pivotRow = row;
511 }
512 }
513 }
514
515 return pivotRow;
516}
517
518void SimplexSchedulerBase::multiplyRow(unsigned row, int factor) {
519 assert(factor != 0);
520 for (unsigned col = 0; col < nColumns; ++col)
521 tableau[row][col] *= factor;
522 // Also multiply the corresponding entry in the temporary column vector.
523 implicitBasicVariableColumnVector[row] *= factor;
524}
525
526void SimplexSchedulerBase::addMultipleOfRow(unsigned sourceRow, int factor,
527 unsigned targetRow) {
528 assert(factor != 0 && sourceRow != targetRow);
529 for (unsigned col = 0; col < nColumns; ++col)
530 tableau[targetRow][col] += tableau[sourceRow][col] * factor;
531 // Again, perform row operation on the temporary column vector as well.
532 implicitBasicVariableColumnVector[targetRow] +=
533 implicitBasicVariableColumnVector[sourceRow] * factor;
534}
535
536/// The pivot operation applies elementary row operations to the tableau in
537/// order to make the \p pivotColumn (corresponding to a non-basic variable) a
538/// unit vector (only the \p pivotRow'th entry is 1). Then, a basis exchange is
539/// performed: the non-basic variable is swapped with the basic variable
540/// associated with the pivot row.
541void SimplexSchedulerBase::pivot(unsigned pivotRow, unsigned pivotColumn) {
542 // The implicit columns are part of an identity matrix.
543 implicitBasicVariableColumnVector[pivotRow] = 1;
544
545 int pivotElem = tableau[pivotRow][pivotColumn];
546 // The constraint matrix has only {-1, 0, 1} entries by construction.
547 assert(pivotElem * pivotElem == 1);
548 // Make `tableau[pivotRow][pivotColumn]` := 1
549 multiplyRow(pivotRow, 1 / pivotElem);
550
551 for (unsigned row = 0; row < nRows; ++row) {
552 if (row == pivotRow)
553 continue;
554
555 int elem = tableau[row][pivotColumn];
556 if (elem == 0)
557 continue; // nothing to do
558
559 // Make `tableau[row][pivotColumn]` := 0.
560 addMultipleOfRow(pivotRow, -elem, row);
561 }
562
563 // Swap the pivot column with the implicitly constructed column vector.
564 // We really only need to copy in one direction here, as the former pivot
565 // column is a unit vector, which is not stored explicitly.
566 for (unsigned row = 0; row < nRows; ++row) {
567 tableau[row][pivotColumn] = implicitBasicVariableColumnVector[row];
568 implicitBasicVariableColumnVector[row] = 0; // Reset for next pivot step.
569 }
570
571 // Look up numeric IDs of variables involved in this pivot operation.
572 unsigned &nonBasicVar =
573 nonBasicVariables[pivotColumn - firstNonBasicVariableColumn];
574 unsigned &basicVar = basicVariables[pivotRow - firstConstraintRow];
575
576 // Keep track of where start time variables are; ignore slack variables.
577 if (nonBasicVar < startTimeLocations.size())
578 startTimeLocations[nonBasicVar] = -pivotRow; // ...going into basis.
579 if (basicVar < startTimeLocations.size())
580 startTimeLocations[basicVar] = pivotColumn; // ...going out of basis.
581
582 // Record the swap in the variable lists.
583 std::swap(nonBasicVar, basicVar);
584}
585
586LogicalResult SimplexSchedulerBase::solveTableau() {
587 // "Solving" technically means perfoming dual pivot steps until primal
588 // feasibility is reached, i.e. the parametric constants in all constraint
589 // rows are non-negative.
590 while (auto pivotRow = findDualPivotRow()) {
591 // Look for pivot elements.
592 if (auto pivotCol = findDualPivotColumn(*pivotRow)) {
593 pivot(*pivotRow, *pivotCol);
594 continue;
595 }
596
597 // If we did not find a pivot column, then the entire row contained only
598 // positive entries, and the problem is in principle infeasible. However, if
599 // the entry in the `parameterTColumn` is positive, we can try to make the
600 // LP feasible again by increasing the II.
601 int entry1Col = tableau[*pivotRow][parameter1Column];
602 int entryTCol = tableau[*pivotRow][parameterTColumn];
603 if (entryTCol > 0) {
604 // The negation of `entry1Col` is not in the paper. I think this is an
605 // oversight, because `entry1Col` certainly is negative (otherwise the row
606 // would not have been a valid pivot row), and without the negation, the
607 // new II would be negative.
608 assert(entry1Col < 0);
609 int newParameterT = (-entry1Col - 1) / entryTCol + 1;
610 if (newParameterT > parameterT) {
611 parameterT = newParameterT;
612 LLVM_DEBUG(dbgs() << "Increased II to " << parameterT << '\n');
613 continue;
614 }
615 }
616
617 // Otherwise, the linear program is infeasible.
618 return failure();
619 }
620
621 // Optimal solution found!
622 return success();
623}
624
625LogicalResult SimplexSchedulerBase::restoreDualFeasibility() {
626 // Dual feasibility requires that all columns in the cost matrix are
627 // non-lexico-negative. This property may be violated after changing the order
628 // of the objective rows, and can be restored by performing primal pivot
629 // steps.
630 while (auto pivotCol = findPrimalPivotColumn()) {
631 // Look for pivot elements.
632 if (auto pivotRow = findPrimalPivotRow(*pivotCol)) {
633 pivot(*pivotRow, *pivotCol);
634 continue;
635 }
636
637 // Otherwise, the linear program is unbounded.
638 return failure();
639 }
640
641 // Optimal solution found!
642 return success();
643}
644
645bool SimplexSchedulerBase::isInBasis(unsigned startTimeVariable) {
646 assert(startTimeVariable < startTimeLocations.size());
647 int loc = startTimeLocations[startTimeVariable];
648 if (-loc >= (int)firstConstraintRow)
649 return true;
650 if (loc >= (int)firstNonBasicVariableColumn)
651 return false;
652 llvm_unreachable("Invalid variable location");
653}
654
655unsigned SimplexSchedulerBase::freeze(unsigned startTimeVariable,
656 unsigned timeStep) {
657 assert(startTimeVariable < startTimeLocations.size());
658 assert(!frozenVariables.count(startTimeVariable));
659
660 // Mark variable.
661 frozenVariables[startTimeVariable] = timeStep;
662
663 if (!isInBasis(startTimeVariable))
664 // That's all for non-basic variables.
665 return startTimeLocations[startTimeVariable];
666
667 // We need to pivot this variable one out of basis.
668 unsigned pivotRow = -startTimeLocations[startTimeVariable];
669
670 // Here, positive pivot elements can be considered as well, hence finding a
671 // suitable column should not fail.
672 auto pivotCol = findDualPivotColumn(pivotRow, /* allowPositive= */ true);
673 assert(pivotCol);
674
675 // Perform the exchange.
676 pivot(pivotRow, *pivotCol);
677
678 // `startTimeVariable` is now represented by `pivotCol`.
679 return *pivotCol;
680}
681
682void SimplexSchedulerBase::translate(unsigned column, int factor1, int factorS,
683 int factorT) {
684 for (unsigned row = 0; row < nRows; ++row) {
685 auto &rowVec = tableau[row];
686 int elem = rowVec[column];
687 if (elem == 0)
688 continue;
689
690 rowVec[parameter1Column] += -elem * factor1;
691 rowVec[parameterSColumn] += -elem * factorS;
692 rowVec[parameterTColumn] += -elem * factorT;
693 }
694}
695
696LogicalResult SimplexSchedulerBase::scheduleAt(unsigned startTimeVariable,
697 unsigned timeStep) {
698 assert(startTimeVariable < startTimeLocations.size());
699 assert(!frozenVariables.count(startTimeVariable));
700
701 // Freeze variable and translate its column by parameter S.
702 unsigned frozenCol = freeze(startTimeVariable, timeStep);
703 translate(frozenCol, /* factor1= */ 0, /* factorS= */ 1, /* factorT= */ 0);
704
705 // Temporarily set S to the desired value, and attempt to solve.
706 parameterS = timeStep;
707 auto solved = solveTableau();
708 parameterS = 0;
709
710 if (failed(solved)) {
711 // The LP is infeasible with the new constraint. We could try other values
712 // for S, but for now, we just roll back and signal failure to the driver.
713 translate(frozenCol, /* factor1= */ 0, /* factorS= */ -1, /* factorT= */ 0);
714 frozenVariables.erase(startTimeVariable);
715 auto solvedAfterRollback = solveTableau();
716 assert(succeeded(solvedAfterRollback));
717 (void)solvedAfterRollback;
718 return failure();
719 }
720
721 // Translate S by the other parameter(s). This means setting `factor1` to
722 // `timeStep`.
723 //
724 // This translation does not change the values of the parametric constants,
725 // hence we do not need to solve the tableau again.
726 //
727 // Note: I added a negation of the factors here, which is not mentioned in the
728 // paper's text, but apparently used in the example. Without it, the intended
729 // effect, i.e. making the S-column all-zero again, is not achieved.
730 //
731 // Note 2: For cyclic problems, the paper suggested to perform a modulo
732 // decomposition: S = `factor1` + `factorT` * T, with `factor1` < T.
733 // However, this makes the value baked into the tableau dependent on
734 // `parameterT`, and it is unclear to me how to update it correctly when
735 // changing the II. I found it much more robust to fix the operations to
736 // absolute time steps, and manually shift them by the appropriate amount
737 // whenever the II is incremented (cf. adding `phiJ`, `phiN` in the modulo
738 // scheduler's `scheduleOperation` method).
739 translate(parameterSColumn, /* factor1= */ -timeStep, /* factorS= */ 1,
740 /* factorT= */ 0);
741
742 return success();
743}
744
745void SimplexSchedulerBase::moveBy(unsigned startTimeVariable, unsigned amount) {
746 assert(startTimeVariable < startTimeLocations.size());
747 assert(frozenVariables.count(startTimeVariable));
748
749 // Bookkeeping.
750 frozenVariables[startTimeVariable] += amount;
751
752 // Moving an already frozen variable means translating it by the desired
753 // amount, and solving the tableau to restore primal feasibility...
754 translate(startTimeLocations[startTimeVariable], /* factor1= */ amount,
755 /* factorS= */ 0, /* factorT= */ 0);
756
757 // ... however, we typically batch-move multiple operations (otherwise, the
758 // tableau may become infeasible on intermediate steps), so actually defer
759 // solving to the caller.
760}
761
762unsigned SimplexSchedulerBase::getStartTime(unsigned startTimeVariable) {
763 assert(startTimeVariable < startTimeLocations.size());
764
765 if (!isInBasis(startTimeVariable))
766 // Non-basic variables that are not already fixed to a specific time step
767 // are 0 at the end of the simplex algorithm.
768 return frozenVariables.lookup(startTimeVariable);
769
770 // For the variables currently in basis, we look up the solution in the
771 // tableau.
772 return getParametricConstant(-startTimeLocations[startTimeVariable]);
773}
774
775void SimplexSchedulerBase::dumpTableau() {
776 for (unsigned j = 0; j < nColumns; ++j)
777 dbgs() << "====";
778 dbgs() << "==\n";
779 for (unsigned i = 0; i < nRows; ++i) {
780 if (i == firstConstraintRow) {
781 for (unsigned j = 0; j < nColumns; ++j) {
782 if (j == firstNonBasicVariableColumn)
783 dbgs() << "-+";
784 dbgs() << "----";
785 }
786 dbgs() << '\n';
787 }
788 for (unsigned j = 0; j < nColumns; ++j) {
789 if (j == firstNonBasicVariableColumn)
790 dbgs() << " |";
791 dbgs() << format(" %3d", tableau[i][j]);
792 }
793 if (i >= firstConstraintRow)
794 dbgs() << format(" |< %2d", basicVariables[i - firstConstraintRow]);
795 dbgs() << '\n';
796 }
797 for (unsigned j = 0; j < nColumns; ++j)
798 dbgs() << "====";
799 dbgs() << "==\n";
800 dbgs() << format(" %3d %3d %3d | ", 1, parameterS, parameterT);
801 for (unsigned j = firstNonBasicVariableColumn; j < nColumns; ++j)
802 dbgs() << format(" %2d^",
803 nonBasicVariables[j - firstNonBasicVariableColumn]);
804 dbgs() << '\n';
805}
806
807//===----------------------------------------------------------------------===//
808// SimplexScheduler
809//===----------------------------------------------------------------------===//
810
811LogicalResult SimplexScheduler::schedule() {
812 if (failed(checkLastOp()))
813 return failure();
814
815 parameterS = 0;
816 parameterT = 0;
817 buildTableau();
818
819 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
820
821 if (failed(solveTableau()))
822 return prob.getContainingOp()->emitError() << "problem is infeasible";
823
824 assert(parameterT == 0);
825 LLVM_DEBUG(
826 dbgs() << "Final tableau:\n"; dumpTableau();
827 dbgs() << "Optimal solution found with start time of last operation = "
828 << -getParametricConstant(0) << '\n');
829
830 for (auto *op : prob.getOperations())
831 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
832
833 return success();
834}
835
836//===----------------------------------------------------------------------===//
837// CyclicSimplexScheduler
838//===----------------------------------------------------------------------===//
839
840void CyclicSimplexScheduler::fillConstraintRow(SmallVector<int> &row,
842 SimplexSchedulerBase::fillConstraintRow(row, dep);
843 if (auto dist = prob.getDistance(dep))
844 row[parameterTColumn] = *dist;
845}
846
847LogicalResult CyclicSimplexScheduler::schedule() {
848 if (failed(checkLastOp()))
849 return failure();
850
851 parameterS = 0;
852 parameterT = 1;
853 buildTableau();
854
855 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
856
857 if (failed(solveTableau()))
858 return prob.getContainingOp()->emitError() << "problem is infeasible";
859
860 LLVM_DEBUG(dbgs() << "Final tableau:\n"; dumpTableau();
861 dbgs() << "Optimal solution found with II = " << parameterT
862 << " and start time of last operation = "
863 << -getParametricConstant(0) << '\n');
864
865 prob.setInitiationInterval(parameterT);
866 for (auto *op : prob.getOperations())
867 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
868
869 return success();
870}
871
872//===----------------------------------------------------------------------===//
873// SharedOperatorsSimplexScheduler
874//===----------------------------------------------------------------------===//
875
876static bool isLimited(Operation *op, SharedOperatorsProblem &prob) {
877 auto maybeRsrcs = prob.getLinkedResourceTypes(op);
878 if (!maybeRsrcs)
879 return false;
880 return llvm::any_of(*maybeRsrcs, [&](Problem::ResourceType rsrc) {
881 return prob.getLimit(rsrc).value_or(0) > 0;
882 });
883}
884
885LogicalResult SharedOperatorsSimplexScheduler::schedule() {
886 if (failed(checkLastOp()))
887 return failure();
888
889 parameterS = 0;
890 parameterT = 0;
891 buildTableau();
892
893 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
894
895 if (failed(solveTableau()))
896 return prob.getContainingOp()->emitError() << "problem is infeasible";
897
898 LLVM_DEBUG(dbgs() << "After solving resource-free problem:\n"; dumpTableau());
899
900 // The *heuristic* part of this scheduler starts here:
901 // We will now *choose* start times for operations using a shared operator
902 // type, in a way that respects the allocation limits, and consecutively solve
903 // the LP with these added constraints. The individual LPs are still solved to
904 // optimality (meaning: the start times of the "last" operation is still
905 // optimal w.r.t. the already fixed operations), however the heuristic choice
906 // means we cannot guarantee the optimality for the overall problem.
907
908 // Determine which operations are subject to resource constraints.
909 auto &ops = prob.getOperations();
910 SmallVector<Operation *> limitedOps;
911 for (auto *op : ops)
912 if (isLimited(op, prob))
913 limitedOps.push_back(op);
914
915 // Build a priority list of the limited operations.
916 //
917 // We sort by the resource-free start times to produce a topological order of
918 // the operations. Better priority functions are known, but require computing
919 // additional properties, e.g. ASAP and ALAP times for mobility, or graph
920 // analysis for height. Assigning operators (=resources) in this order at
921 // least ensures that the (acyclic!) problem remains feasible throughout the
922 // process.
923 //
924 // TODO: Implement more sophisticated priority function.
925 std::stable_sort(limitedOps.begin(), limitedOps.end(),
926 [&](Operation *a, Operation *b) {
927 return getStartTime(startTimeVariables[a]) <
928 getStartTime(startTimeVariables[b]);
929 });
930
931 // Store the number of operations using a resource type in a particular time
932 // step.
934 reservationTable;
935
936 for (auto *op : limitedOps) {
937 auto maybeRsrcs = prob.getLinkedResourceTypes(op);
938 assert(maybeRsrcs && "Limited operation must have linked resource types");
939
940 auto &rsrcs = *maybeRsrcs;
941 assert(rsrcs.size() == 1 &&
942 "Multi-resource operations are not yet supported by this scheduler");
943
944 auto rsrc = rsrcs[0];
945 unsigned limit = prob.getLimit(rsrc).value_or(0);
946 assert(limit > 0);
947
948 // Find the first time step (beginning at the current start time in the
949 // partial schedule) in which an operator instance is available.
950 unsigned startTimeVar = startTimeVariables[op];
951 unsigned candTime = getStartTime(startTimeVar);
952 while (reservationTable[rsrc].lookup(candTime) == limit)
953 ++candTime;
954
955 // Fix the start time. As explained above, this cannot make the problem
956 // infeasible.
957 auto fixed = scheduleAt(startTimeVar, candTime);
958 assert(succeeded(fixed));
959 (void)fixed;
960
961 // Record the operator use.
962 ++reservationTable[rsrc][candTime];
963
964 LLVM_DEBUG(dbgs() << "After scheduling " << startTimeVar
965 << " to t=" << candTime << ":\n";
966 dumpTableau());
967 }
968
969 assert(parameterT == 0);
970 LLVM_DEBUG(
971 dbgs() << "Final tableau:\n"; dumpTableau();
972 dbgs() << "Feasible solution found with start time of last operation = "
973 << -getParametricConstant(0) << '\n');
974
975 for (auto *op : ops)
976 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
977
978 return success();
979}
980
981//===----------------------------------------------------------------------===//
982// ModuloSimplexScheduler
983//===----------------------------------------------------------------------===//
984
985LogicalResult ModuloSimplexScheduler::checkLastOp() {
986 auto *contOp = prob.getContainingOp();
987 if (!prob.hasOperation(lastOp))
988 return contOp->emitError("problem does not include last operation");
989
990 // Determine which operations have no outgoing *intra*-iteration dependences.
991 auto &ops = prob.getOperations();
992 DenseSet<Operation *> sinks(ops.begin(), ops.end());
993 for (auto *op : ops)
994 for (auto &dep : prob.getDependences(op))
995 if (prob.getDistance(dep).value_or(0) == 0)
996 sinks.erase(dep.getSource());
997
998 if (!sinks.contains(lastOp))
999 return contOp->emitError("last operation is not a sink");
1000 if (sinks.size() > 1)
1001 return contOp->emitError("multiple sinks detected");
1002
1003 return success();
1004}
1005
1006LogicalResult ModuloSimplexScheduler::MRT::enter(Operation *op,
1007 unsigned timeStep) {
1008 auto maybeRsrcs = sched.prob.getLinkedResourceTypes(op);
1009 assert(maybeRsrcs && "Operation must have linked resource types");
1010
1011 auto &rsrcs = *maybeRsrcs;
1012 assert(rsrcs.size() == 1 &&
1013 "Multi-resource operations are not yet supported by MRT");
1014
1015 auto rsrc = rsrcs[0];
1016 auto lim = *sched.prob.getLimit(rsrc);
1017 assert(lim > 0);
1018
1019 auto &revTab = reverseTables[rsrc];
1020 assert(!revTab.count(op));
1021
1022 unsigned slot = timeStep % sched.parameterT;
1023 auto &cell = tables[rsrc][slot];
1024 if (cell.size() < lim) {
1025 cell.insert(op);
1026 revTab[op] = slot;
1027 return success();
1028 }
1029 return failure();
1030}
1031
1032void ModuloSimplexScheduler::MRT::release(Operation *op) {
1033 auto maybeRsrcs = sched.prob.getLinkedResourceTypes(op);
1034 assert(maybeRsrcs && "Operation must have linked resource types");
1035
1036 auto &rsrcs = *maybeRsrcs;
1037 assert(rsrcs.size() == 1 &&
1038 "Multi-resource operations are not yet supported by MRT");
1039
1040 auto rsrc = rsrcs[0];
1041 auto &revTab = reverseTables[rsrc];
1042 auto it = revTab.find(op);
1043 assert(it != revTab.end());
1044 tables[rsrc][it->second].erase(op);
1045 revTab.erase(it);
1046}
1047
1048bool ModuloSimplexScheduler::fillObjectiveRow(SmallVector<int> &row,
1049 unsigned obj) {
1050 switch (obj) {
1051 case OBJ_LATENCY:
1052 // Minimize start time of user-specified last operation.
1053 row[startTimeLocations[startTimeVariables[lastOp]]] = 1;
1054 return true;
1055 case OBJ_AXAP:
1056 // Minimize sum of start times of all-but-the-last operation.
1057 for (auto *op : getProblem().getOperations())
1058 if (op != lastOp)
1059 row[startTimeLocations[startTimeVariables[op]]] = 1;
1060 return false;
1061 default:
1062 llvm_unreachable("Unsupported objective requested");
1063 }
1064}
1065
1066void ModuloSimplexScheduler::updateMargins() {
1067 // Assumption: current secondary objective is "ASAP".
1068 // Negate the objective row once to effectively maximize the sum of start
1069 // times, which yields the "ALAP" times after solving the tableau. Then,
1070 // negate it again to restore the "ASAP" objective, and store these times as
1071 // well.
1072 for (auto *axapTimes : {&alapTimes, &asapTimes}) {
1073 multiplyRow(OBJ_AXAP, -1);
1074 // This should not fail for a feasible tableau.
1075 auto dualFeasRestored = restoreDualFeasibility();
1076 auto solved = solveTableau();
1077 assert(succeeded(dualFeasRestored) && succeeded(solved));
1078 (void)dualFeasRestored, (void)solved;
1079
1080 for (unsigned stv = 0; stv < startTimeLocations.size(); ++stv)
1081 (*axapTimes)[stv] = getStartTime(stv);
1082 }
1083}
1084
1085void ModuloSimplexScheduler::scheduleOperation(Operation *n) {
1086 auto oprN = *prob.getLinkedOperatorType(n);
1087 unsigned stvN = startTimeVariables[n];
1088
1089 // Get current state of the LP. We'll try to schedule at its current time step
1090 // in the partial solution, and the II-1 following time steps. Scheduling the
1091 // op to a later time step may increase the overall latency, however, as long
1092 // as the solution is still feasible, we prefer that over incrementing the II
1093 // to resolve resource conflicts.
1094 unsigned stN = getStartTime(stvN);
1095 unsigned ubN = stN + parameterT - 1;
1096
1097 LLVM_DEBUG(dbgs() << "Attempting to schedule in [" << stN << ", " << ubN
1098 << "]: " << *n << '\n');
1099
1100 for (unsigned ct = stN; ct <= ubN; ++ct)
1101 if (succeeded(mrt.enter(n, ct))) {
1102 auto fixedN = scheduleAt(stvN, ct);
1103 if (succeeded(fixedN)) {
1104 LLVM_DEBUG(dbgs() << "Success at t=" << ct << " " << *n << '\n');
1105 return;
1106 }
1107 // Problem became infeasible with `n` at `ct`, roll back the MRT
1108 // assignment. Also, no later time can be feasible, so stop the search
1109 // here.
1110 mrt.release(n);
1111 break;
1112 }
1113
1114 // As a last resort, increase II to make room for the op. De Dinechin's
1115 // Theorem 1 lays out conditions/guidelines to transform the current partial
1116 // schedule for II to a valid one for a larger II'.
1117
1118 LLVM_DEBUG(dbgs() << "Incrementing II to " << (parameterT + 1)
1119 << " to resolve resource conflict for " << *n << '\n');
1120
1121 // Note that the approach below is much simpler than in the paper
1122 // because of the fully-pipelined operators. In our case, it's always
1123 // sufficient to increment the II by one.
1124
1125 // Decompose start time.
1126 unsigned phiN = stN / parameterT;
1127 unsigned tauN = stN % parameterT;
1128
1129 // Keep track whether the following moves free at least one operator
1130 // instance in the slot desired by the current op - then it can stay there.
1131 unsigned deltaN = 1;
1132
1133 // We're going to revisit the current partial schedule.
1134 SmallVector<Operation *> moved;
1135 for (Operation *j : scheduled) {
1136 auto oprJ = *prob.getLinkedOperatorType(j);
1137 unsigned stvJ = startTimeVariables[j];
1138 unsigned stJ = getStartTime(stvJ);
1139 unsigned phiJ = stJ / parameterT;
1140 unsigned tauJ = stJ % parameterT;
1141 unsigned deltaJ = 0;
1142
1143 if (oprN == oprJ) {
1144 // To actually resolve the resource conflicts, we will move operations
1145 // that are "preceded" (cf. de Dinechin's ≺ relation) one slot to the
1146 // right.
1147 if (tauN < tauJ || (tauN == tauJ && phiN > phiJ) ||
1148 (tauN == tauJ && phiN == phiJ && stvN < stvJ)) {
1149 // TODO: Replace the last condition with a proper graph analysis.
1150
1151 deltaJ = 1;
1152 moved.push_back(j);
1153 if (tauN == tauJ)
1154 deltaN = 0;
1155 }
1156 }
1157
1158 // Move operation.
1159 //
1160 // In order to keep the op in its current MRT slot `tauJ` after incrementing
1161 // the II, we add `phiJ`:
1162 // stJ + phiJ = (phiJ * parameterT + tauJ) + phiJ
1163 // = phiJ * (parameterT + 1) + tauJ
1164 //
1165 // Shifting an additional `deltaJ` time steps then moves the op to a
1166 // different MRT slot, in order to make room for the operation that caused
1167 // the resource conflict.
1168 moveBy(stvJ, phiJ + deltaJ);
1169 }
1170
1171 // Finally, increment the II and solve to apply the moves.
1172 ++parameterT;
1173 auto solved = solveTableau();
1174 assert(succeeded(solved));
1175 (void)solved;
1176
1177 // Re-enter moved operations into their new slots.
1178 for (auto *m : moved)
1179 mrt.release(m);
1180 for (auto *m : moved) {
1181 auto enteredM = mrt.enter(m, getStartTime(startTimeVariables[m]));
1182 assert(succeeded(enteredM));
1183 (void)enteredM;
1184 }
1185
1186 // Finally, schedule the operation. Again, adding `phiN` accounts for the
1187 // implicit shift caused by incrementing the II.
1188 auto fixedN = scheduleAt(stvN, stN + phiN + deltaN);
1189 auto enteredN = mrt.enter(n, tauN + deltaN);
1190 assert(succeeded(fixedN) && succeeded(enteredN));
1191 (void)fixedN, (void)enteredN;
1192}
1193
1194unsigned ModuloSimplexScheduler::computeResMinII() {
1195 unsigned resMinII = 1;
1197 for (auto *op : prob.getOperations()) {
1198 auto maybeRsrcs = prob.getLinkedResourceTypes(op);
1199 if (!maybeRsrcs)
1200 continue;
1201
1202 for (auto rsrc : *maybeRsrcs) {
1203 if (prob.getLimit(rsrc).value_or(0) > 0)
1204 ++uses[rsrc];
1205 }
1206 }
1207
1208 for (auto pair : uses)
1209 resMinII = std::max(
1210 resMinII, (unsigned)ceil(pair.second / *prob.getLimit(pair.first)));
1211
1212 return resMinII;
1213}
1214
1215LogicalResult ModuloSimplexScheduler::schedule() {
1216 if (failed(checkLastOp()))
1217 return failure();
1218
1219 parameterS = 0;
1220 parameterT = computeResMinII();
1221 LLVM_DEBUG(dbgs() << "ResMinII = " << parameterT << "\n");
1222 buildTableau();
1223 asapTimes.resize(startTimeLocations.size());
1224 alapTimes.resize(startTimeLocations.size());
1225
1226 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
1227
1228 if (failed(solveTableau()))
1229 return prob.getContainingOp()->emitError() << "problem is infeasible";
1230
1231 // Determine which operations are subject to resource constraints.
1232 auto &ops = prob.getOperations();
1233 for (auto *op : ops)
1234 if (isLimited(op, prob))
1235 unscheduled.push_back(op);
1236
1237 // Main loop: Iteratively fix limited operations to time steps.
1238 while (!unscheduled.empty()) {
1239 // Update ASAP/ALAP times.
1240 updateMargins();
1241
1242 // Heuristically (here: least amount of slack) pick the next operation to
1243 // schedule.
1244 auto *opIt =
1245 std::min_element(unscheduled.begin(), unscheduled.end(),
1246 [&](Operation *opA, Operation *opB) {
1247 auto stvA = startTimeVariables[opA];
1248 auto stvB = startTimeVariables[opB];
1249 auto slackA = alapTimes[stvA] - asapTimes[stvA];
1250 auto slackB = alapTimes[stvB] - asapTimes[stvB];
1251 return slackA < slackB;
1252 });
1253 Operation *op = *opIt;
1254 unscheduled.erase(opIt);
1255
1256 scheduleOperation(op);
1257 scheduled.push_back(op);
1258 }
1259
1260 LLVM_DEBUG(dbgs() << "Final tableau:\n"; dumpTableau();
1261 dbgs() << "Solution found with II = " << parameterT
1262 << " and start time of last operation = "
1263 << -getParametricConstant(0) << '\n');
1264
1265 prob.setInitiationInterval(parameterT);
1266 for (auto *op : ops)
1267 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1268
1269 return success();
1270}
1271
1272//===----------------------------------------------------------------------===//
1273// ChainingSimplexScheduler
1274//===----------------------------------------------------------------------===//
1275
1276void ChainingSimplexScheduler::fillAdditionalConstraintRow(
1277 SmallVector<int> &row, Problem::Dependence dep) {
1278 fillConstraintRow(row, dep);
1279 // One _extra_ time step breaks the chain (note that the latency is negative
1280 // in the tableau).
1281 row[parameter1Column] -= 1;
1282}
1283
1284LogicalResult ChainingSimplexScheduler::schedule() {
1285 if (failed(checkLastOp()) || failed(computeChainBreakingDependences(
1286 prob, cycleTime, additionalConstraints)))
1287 return failure();
1288
1289 parameterS = 0;
1290 parameterT = 0;
1291 buildTableau();
1292
1293 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
1294
1295 if (failed(solveTableau()))
1296 return prob.getContainingOp()->emitError() << "problem is infeasible";
1297
1298 assert(parameterT == 0);
1299 LLVM_DEBUG(
1300 dbgs() << "Final tableau:\n"; dumpTableau();
1301 dbgs() << "Optimal solution found with start time of last operation = "
1302 << -getParametricConstant(0) << '\n');
1303
1304 for (auto *op : prob.getOperations())
1305 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1306
1307 auto filledIn = computeStartTimesInCycle(prob);
1308 assert(succeeded(filledIn)); // Problem is known to be acyclic at this point.
1309 (void)filledIn;
1310
1311 return success();
1312}
1313
1314//===----------------------------------------------------------------------===//
1315// ChainingCyclicSimplexScheduler
1316//===----------------------------------------------------------------------===//
1317
1318void ChainingCyclicSimplexScheduler::fillConstraintRow(
1319 SmallVector<int> &row, Problem::Dependence dep) {
1320 SimplexSchedulerBase::fillConstraintRow(row, dep);
1321 if (auto dist = prob.getDistance(dep))
1322 row[parameterTColumn] = *dist;
1323}
1324
1325void ChainingCyclicSimplexScheduler::fillAdditionalConstraintRow(
1326 SmallVector<int> &row, Problem::Dependence dep) {
1327 fillConstraintRow(row, dep);
1328 // One _extra_ time step breaks the chain (note that the latency is negative
1329 // in the tableau).
1330 row[parameter1Column] -= 1;
1331}
1332
1333LogicalResult ChainingCyclicSimplexScheduler::schedule() {
1334 if (failed(checkLastOp()) || failed(computeChainBreakingDependences(
1335 prob, cycleTime, additionalConstraints)))
1336 return failure();
1337
1338 parameterS = 0;
1339 parameterT = 1;
1340 buildTableau();
1341
1342 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
1343
1344 if (failed(solveTableau()))
1345 return prob.getContainingOp()->emitError() << "problem is infeasible";
1346
1347 LLVM_DEBUG(dbgs() << "Final tableau:\n"; dumpTableau();
1348 dbgs() << "Optimal solution found with II = " << parameterT
1349 << " and start time of last operation = "
1350 << -getParametricConstant(0) << '\n');
1351
1352 prob.setInitiationInterval(parameterT);
1353 for (auto *op : prob.getOperations())
1354 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1355
1356 auto filledIn = computeStartTimesInCycle(prob);
1357 assert(succeeded(filledIn));
1358 (void)filledIn;
1359
1360 return success();
1361}
1362
1363//===----------------------------------------------------------------------===//
1364// Public API
1365//===----------------------------------------------------------------------===//
1366
1367LogicalResult scheduling::scheduleSimplex(Problem &prob, Operation *lastOp) {
1368 SimplexScheduler simplex(prob, lastOp);
1369 return simplex.schedule();
1370}
1371
1373 Operation *lastOp) {
1374 CyclicSimplexScheduler simplex(prob, lastOp);
1375 return simplex.schedule();
1376}
1377
1379 Operation *lastOp) {
1380 SharedOperatorsSimplexScheduler simplex(prob, lastOp);
1381 return simplex.schedule();
1382}
1383
1385 Operation *lastOp) {
1386 ModuloSimplexScheduler simplex(prob, lastOp);
1387 return simplex.schedule();
1388}
1389
1391 Operation *lastOp, float cycleTime) {
1392 ChainingSimplexScheduler simplex(prob, lastOp, cycleTime);
1393 return simplex.schedule();
1394}
1395
1397 Operation *lastOp, float cycleTime) {
1398 ChainingCyclicSimplexScheduler simplex(prob, lastOp, cycleTime);
1399 return simplex.schedule();
1400}
assert(baseType &&"element must be base type")
static bool isLimited(Operation *op, SharedOperatorsProblem &prob)
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
Definition Problems.h:558
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
Definition Problems.h:412
This class models a cyclic scheduling problem.
Definition Problems.h:359
This class models the modulo scheduling problem as the composition of the cyclic problem and the reso...
Definition Problems.h:529
This class models the most basic scheduling problem.
Definition Problems.h:75
std::optional< SmallVector< ResourceType > > getLinkedResourceTypes(Operation *op)
The linked resource type provides the available resources for op.
Definition Problems.h:265
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
A wrapper class to uniformly handle def-use and auxiliary dependence edges.
Operation * getDestination() const
Return the destination of the dependence.
Definition Problems.cpp:493
Operation * getSource() const
Return the source of the dependence.
Definition Problems.cpp:489
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 b...
LogicalResult scheduleSimplex(Problem &prob, Operation *lastOp)
Solve the basic problem using linear programming and a handwritten implementation of the simplex algo...
LogicalResult computeStartTimesInCycle(ChainingProblem &prob)
Assuming prob is scheduled and contains (integer) start times, this method fills in the start times i...
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Resource types are distinguished by name (chosen by the client).
Definition Problems.h:120