Loading [MathJax]/jax/output/HTML-CSS/config.js
CIRCT 20.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 return prob.getLimit(*prob.getLinkedOperatorType(op)).value_or(0) > 0;
878}
879
880LogicalResult SharedOperatorsSimplexScheduler::schedule() {
881 if (failed(checkLastOp()))
882 return failure();
883
884 parameterS = 0;
885 parameterT = 0;
886 buildTableau();
887
888 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
889
890 if (failed(solveTableau()))
891 return prob.getContainingOp()->emitError() << "problem is infeasible";
892
893 LLVM_DEBUG(dbgs() << "After solving resource-free problem:\n"; dumpTableau());
894
895 // The *heuristic* part of this scheduler starts here:
896 // We will now *choose* start times for operations using a shared operator
897 // type, in a way that respects the allocation limits, and consecutively solve
898 // the LP with these added constraints. The individual LPs are still solved to
899 // optimality (meaning: the start times of the "last" operation is still
900 // optimal w.r.t. the already fixed operations), however the heuristic choice
901 // means we cannot guarantee the optimality for the overall problem.
902
903 // Determine which operations are subject to resource constraints.
904 auto &ops = prob.getOperations();
905 SmallVector<Operation *> limitedOps;
906 for (auto *op : ops)
907 if (isLimited(op, prob))
908 limitedOps.push_back(op);
909
910 // Build a priority list of the limited operations.
911 //
912 // We sort by the resource-free start times to produce a topological order of
913 // the operations. Better priority functions are known, but require computing
914 // additional properties, e.g. ASAP and ALAP times for mobility, or graph
915 // analysis for height. Assigning operators (=resources) in this order at
916 // least ensures that the (acyclic!) problem remains feasible throughout the
917 // process.
918 //
919 // TODO: Implement more sophisticated priority function.
920 std::stable_sort(limitedOps.begin(), limitedOps.end(),
921 [&](Operation *a, Operation *b) {
922 return getStartTime(startTimeVariables[a]) <
923 getStartTime(startTimeVariables[b]);
924 });
925
926 // Store the number of operations using an operator type in a particular time
927 // step.
929 reservationTable;
930
931 for (auto *op : limitedOps) {
932 auto opr = *prob.getLinkedOperatorType(op);
933 unsigned limit = prob.getLimit(opr).value_or(0);
934 assert(limit > 0);
935
936 // Find the first time step (beginning at the current start time in the
937 // partial schedule) in which an operator instance is available.
938 unsigned startTimeVar = startTimeVariables[op];
939 unsigned candTime = getStartTime(startTimeVar);
940 while (reservationTable[opr].lookup(candTime) == limit)
941 ++candTime;
942
943 // Fix the start time. As explained above, this cannot make the problem
944 // infeasible.
945 auto fixed = scheduleAt(startTimeVar, candTime);
946 assert(succeeded(fixed));
947 (void)fixed;
948
949 // Record the operator use.
950 ++reservationTable[opr][candTime];
951
952 LLVM_DEBUG(dbgs() << "After scheduling " << startTimeVar
953 << " to t=" << candTime << ":\n";
954 dumpTableau());
955 }
956
957 assert(parameterT == 0);
958 LLVM_DEBUG(
959 dbgs() << "Final tableau:\n"; dumpTableau();
960 dbgs() << "Feasible solution found with start time of last operation = "
961 << -getParametricConstant(0) << '\n');
962
963 for (auto *op : ops)
964 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
965
966 return success();
967}
968
969//===----------------------------------------------------------------------===//
970// ModuloSimplexScheduler
971//===----------------------------------------------------------------------===//
972
973LogicalResult ModuloSimplexScheduler::checkLastOp() {
974 auto *contOp = prob.getContainingOp();
975 if (!prob.hasOperation(lastOp))
976 return contOp->emitError("problem does not include last operation");
977
978 // Determine which operations have no outgoing *intra*-iteration dependences.
979 auto &ops = prob.getOperations();
980 DenseSet<Operation *> sinks(ops.begin(), ops.end());
981 for (auto *op : ops)
982 for (auto &dep : prob.getDependences(op))
983 if (prob.getDistance(dep).value_or(0) == 0)
984 sinks.erase(dep.getSource());
985
986 if (!sinks.contains(lastOp))
987 return contOp->emitError("last operation is not a sink");
988 if (sinks.size() > 1)
989 return contOp->emitError("multiple sinks detected");
990
991 return success();
992}
993
994LogicalResult ModuloSimplexScheduler::MRT::enter(Operation *op,
995 unsigned timeStep) {
996 auto opr = *sched.prob.getLinkedOperatorType(op);
997 auto lim = *sched.prob.getLimit(opr);
998 assert(lim > 0);
999
1000 auto &revTab = reverseTables[opr];
1001 assert(!revTab.count(op));
1002
1003 unsigned slot = timeStep % sched.parameterT;
1004 auto &cell = tables[opr][slot];
1005 if (cell.size() < lim) {
1006 cell.insert(op);
1007 revTab[op] = slot;
1008 return success();
1009 }
1010 return failure();
1011}
1012
1013void ModuloSimplexScheduler::MRT::release(Operation *op) {
1014 auto opr = *sched.prob.getLinkedOperatorType(op);
1015 auto &revTab = reverseTables[opr];
1016 auto it = revTab.find(op);
1017 assert(it != revTab.end());
1018 tables[opr][it->second].erase(op);
1019 revTab.erase(it);
1020}
1021
1022bool ModuloSimplexScheduler::fillObjectiveRow(SmallVector<int> &row,
1023 unsigned obj) {
1024 switch (obj) {
1025 case OBJ_LATENCY:
1026 // Minimize start time of user-specified last operation.
1027 row[startTimeLocations[startTimeVariables[lastOp]]] = 1;
1028 return true;
1029 case OBJ_AXAP:
1030 // Minimize sum of start times of all-but-the-last operation.
1031 for (auto *op : getProblem().getOperations())
1032 if (op != lastOp)
1033 row[startTimeLocations[startTimeVariables[op]]] = 1;
1034 return false;
1035 default:
1036 llvm_unreachable("Unsupported objective requested");
1037 }
1038}
1039
1040void ModuloSimplexScheduler::updateMargins() {
1041 // Assumption: current secondary objective is "ASAP".
1042 // Negate the objective row once to effectively maximize the sum of start
1043 // times, which yields the "ALAP" times after solving the tableau. Then,
1044 // negate it again to restore the "ASAP" objective, and store these times as
1045 // well.
1046 for (auto *axapTimes : {&alapTimes, &asapTimes}) {
1047 multiplyRow(OBJ_AXAP, -1);
1048 // This should not fail for a feasible tableau.
1049 auto dualFeasRestored = restoreDualFeasibility();
1050 auto solved = solveTableau();
1051 assert(succeeded(dualFeasRestored) && succeeded(solved));
1052 (void)dualFeasRestored, (void)solved;
1053
1054 for (unsigned stv = 0; stv < startTimeLocations.size(); ++stv)
1055 (*axapTimes)[stv] = getStartTime(stv);
1056 }
1057}
1058
1059void ModuloSimplexScheduler::scheduleOperation(Operation *n) {
1060 auto oprN = *prob.getLinkedOperatorType(n);
1061 unsigned stvN = startTimeVariables[n];
1062
1063 // Get current state of the LP. We'll try to schedule at its current time step
1064 // in the partial solution, and the II-1 following time steps. Scheduling the
1065 // op to a later time step may increase the overall latency, however, as long
1066 // as the solution is still feasible, we prefer that over incrementing the II
1067 // to resolve resource conflicts.
1068 unsigned stN = getStartTime(stvN);
1069 unsigned ubN = stN + parameterT - 1;
1070
1071 LLVM_DEBUG(dbgs() << "Attempting to schedule in [" << stN << ", " << ubN
1072 << "]: " << *n << '\n');
1073
1074 for (unsigned ct = stN; ct <= ubN; ++ct)
1075 if (succeeded(mrt.enter(n, ct))) {
1076 auto fixedN = scheduleAt(stvN, ct);
1077 if (succeeded(fixedN)) {
1078 LLVM_DEBUG(dbgs() << "Success at t=" << ct << " " << *n << '\n');
1079 return;
1080 }
1081 // Problem became infeasible with `n` at `ct`, roll back the MRT
1082 // assignment. Also, no later time can be feasible, so stop the search
1083 // here.
1084 mrt.release(n);
1085 break;
1086 }
1087
1088 // As a last resort, increase II to make room for the op. De Dinechin's
1089 // Theorem 1 lays out conditions/guidelines to transform the current partial
1090 // schedule for II to a valid one for a larger II'.
1091
1092 LLVM_DEBUG(dbgs() << "Incrementing II to " << (parameterT + 1)
1093 << " to resolve resource conflict for " << *n << '\n');
1094
1095 // Note that the approach below is much simpler than in the paper
1096 // because of the fully-pipelined operators. In our case, it's always
1097 // sufficient to increment the II by one.
1098
1099 // Decompose start time.
1100 unsigned phiN = stN / parameterT;
1101 unsigned tauN = stN % parameterT;
1102
1103 // Keep track whether the following moves free at least one operator
1104 // instance in the slot desired by the current op - then it can stay there.
1105 unsigned deltaN = 1;
1106
1107 // We're going to revisit the current partial schedule.
1108 SmallVector<Operation *> moved;
1109 for (Operation *j : scheduled) {
1110 auto oprJ = *prob.getLinkedOperatorType(j);
1111 unsigned stvJ = startTimeVariables[j];
1112 unsigned stJ = getStartTime(stvJ);
1113 unsigned phiJ = stJ / parameterT;
1114 unsigned tauJ = stJ % parameterT;
1115 unsigned deltaJ = 0;
1116
1117 if (oprN == oprJ) {
1118 // To actually resolve the resource conflicts, we will move operations
1119 // that are "preceded" (cf. de Dinechin's ≺ relation) one slot to the
1120 // right.
1121 if (tauN < tauJ || (tauN == tauJ && phiN > phiJ) ||
1122 (tauN == tauJ && phiN == phiJ && stvN < stvJ)) {
1123 // TODO: Replace the last condition with a proper graph analysis.
1124
1125 deltaJ = 1;
1126 moved.push_back(j);
1127 if (tauN == tauJ)
1128 deltaN = 0;
1129 }
1130 }
1131
1132 // Move operation.
1133 //
1134 // In order to keep the op in its current MRT slot `tauJ` after incrementing
1135 // the II, we add `phiJ`:
1136 // stJ + phiJ = (phiJ * parameterT + tauJ) + phiJ
1137 // = phiJ * (parameterT + 1) + tauJ
1138 //
1139 // Shifting an additional `deltaJ` time steps then moves the op to a
1140 // different MRT slot, in order to make room for the operation that caused
1141 // the resource conflict.
1142 moveBy(stvJ, phiJ + deltaJ);
1143 }
1144
1145 // Finally, increment the II and solve to apply the moves.
1146 ++parameterT;
1147 auto solved = solveTableau();
1148 assert(succeeded(solved));
1149 (void)solved;
1150
1151 // Re-enter moved operations into their new slots.
1152 for (auto *m : moved)
1153 mrt.release(m);
1154 for (auto *m : moved) {
1155 auto enteredM = mrt.enter(m, getStartTime(startTimeVariables[m]));
1156 assert(succeeded(enteredM));
1157 (void)enteredM;
1158 }
1159
1160 // Finally, schedule the operation. Again, adding `phiN` accounts for the
1161 // implicit shift caused by incrementing the II.
1162 auto fixedN = scheduleAt(stvN, stN + phiN + deltaN);
1163 auto enteredN = mrt.enter(n, tauN + deltaN);
1164 assert(succeeded(fixedN) && succeeded(enteredN));
1165 (void)fixedN, (void)enteredN;
1166}
1167
1168unsigned ModuloSimplexScheduler::computeResMinII() {
1169 unsigned resMinII = 1;
1171 for (auto *op : prob.getOperations())
1172 if (isLimited(op, prob))
1173 ++uses[*prob.getLinkedOperatorType(op)];
1174
1175 for (auto pair : uses)
1176 resMinII = std::max(
1177 resMinII, (unsigned)ceil(pair.second / *prob.getLimit(pair.first)));
1178
1179 return resMinII;
1180}
1181
1182LogicalResult ModuloSimplexScheduler::schedule() {
1183 if (failed(checkLastOp()))
1184 return failure();
1185
1186 parameterS = 0;
1187 parameterT = computeResMinII();
1188 LLVM_DEBUG(dbgs() << "ResMinII = " << parameterT << "\n");
1189 buildTableau();
1190 asapTimes.resize(startTimeLocations.size());
1191 alapTimes.resize(startTimeLocations.size());
1192
1193 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
1194
1195 if (failed(solveTableau()))
1196 return prob.getContainingOp()->emitError() << "problem is infeasible";
1197
1198 // Determine which operations are subject to resource constraints.
1199 auto &ops = prob.getOperations();
1200 for (auto *op : ops)
1201 if (isLimited(op, prob))
1202 unscheduled.push_back(op);
1203
1204 // Main loop: Iteratively fix limited operations to time steps.
1205 while (!unscheduled.empty()) {
1206 // Update ASAP/ALAP times.
1207 updateMargins();
1208
1209 // Heuristically (here: least amount of slack) pick the next operation to
1210 // schedule.
1211 auto *opIt =
1212 std::min_element(unscheduled.begin(), unscheduled.end(),
1213 [&](Operation *opA, Operation *opB) {
1214 auto stvA = startTimeVariables[opA];
1215 auto stvB = startTimeVariables[opB];
1216 auto slackA = alapTimes[stvA] - asapTimes[stvA];
1217 auto slackB = alapTimes[stvB] - asapTimes[stvB];
1218 return slackA < slackB;
1219 });
1220 Operation *op = *opIt;
1221 unscheduled.erase(opIt);
1222
1223 scheduleOperation(op);
1224 scheduled.push_back(op);
1225 }
1226
1227 LLVM_DEBUG(dbgs() << "Final tableau:\n"; dumpTableau();
1228 dbgs() << "Solution found with II = " << parameterT
1229 << " and start time of last operation = "
1230 << -getParametricConstant(0) << '\n');
1231
1232 prob.setInitiationInterval(parameterT);
1233 for (auto *op : ops)
1234 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1235
1236 return success();
1237}
1238
1239//===----------------------------------------------------------------------===//
1240// ChainingSimplexScheduler
1241//===----------------------------------------------------------------------===//
1242
1243void ChainingSimplexScheduler::fillAdditionalConstraintRow(
1244 SmallVector<int> &row, Problem::Dependence dep) {
1245 fillConstraintRow(row, dep);
1246 // One _extra_ time step breaks the chain (note that the latency is negative
1247 // in the tableau).
1248 row[parameter1Column] -= 1;
1249}
1250
1251LogicalResult ChainingSimplexScheduler::schedule() {
1252 if (failed(checkLastOp()) || failed(computeChainBreakingDependences(
1253 prob, cycleTime, additionalConstraints)))
1254 return failure();
1255
1256 parameterS = 0;
1257 parameterT = 0;
1258 buildTableau();
1259
1260 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
1261
1262 if (failed(solveTableau()))
1263 return prob.getContainingOp()->emitError() << "problem is infeasible";
1264
1265 assert(parameterT == 0);
1266 LLVM_DEBUG(
1267 dbgs() << "Final tableau:\n"; dumpTableau();
1268 dbgs() << "Optimal solution found with start time of last operation = "
1269 << -getParametricConstant(0) << '\n');
1270
1271 for (auto *op : prob.getOperations())
1272 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1273
1274 auto filledIn = computeStartTimesInCycle(prob);
1275 assert(succeeded(filledIn)); // Problem is known to be acyclic at this point.
1276 (void)filledIn;
1277
1278 return success();
1279}
1280
1281//===----------------------------------------------------------------------===//
1282// ChainingCyclicSimplexScheduler
1283//===----------------------------------------------------------------------===//
1284
1285void ChainingCyclicSimplexScheduler::fillConstraintRow(
1286 SmallVector<int> &row, Problem::Dependence dep) {
1287 SimplexSchedulerBase::fillConstraintRow(row, dep);
1288 if (auto dist = prob.getDistance(dep))
1289 row[parameterTColumn] = *dist;
1290}
1291
1292void ChainingCyclicSimplexScheduler::fillAdditionalConstraintRow(
1293 SmallVector<int> &row, Problem::Dependence dep) {
1294 fillConstraintRow(row, dep);
1295 // One _extra_ time step breaks the chain (note that the latency is negative
1296 // in the tableau).
1297 row[parameter1Column] -= 1;
1298}
1299
1300LogicalResult ChainingCyclicSimplexScheduler::schedule() {
1301 if (failed(checkLastOp()) || failed(computeChainBreakingDependences(
1302 prob, cycleTime, additionalConstraints)))
1303 return failure();
1304
1305 parameterS = 0;
1306 parameterT = 1;
1307 buildTableau();
1308
1309 LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
1310
1311 if (failed(solveTableau()))
1312 return prob.getContainingOp()->emitError() << "problem is infeasible";
1313
1314 LLVM_DEBUG(dbgs() << "Final tableau:\n"; dumpTableau();
1315 dbgs() << "Optimal solution found with II = " << parameterT
1316 << " and start time of last operation = "
1317 << -getParametricConstant(0) << '\n');
1318
1319 prob.setInitiationInterval(parameterT);
1320 for (auto *op : prob.getOperations())
1321 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1322
1323 auto filledIn = computeStartTimesInCycle(prob);
1324 assert(succeeded(filledIn));
1325 (void)filledIn;
1326
1327 return success();
1328}
1329
1330//===----------------------------------------------------------------------===//
1331// Public API
1332//===----------------------------------------------------------------------===//
1333
1334LogicalResult scheduling::scheduleSimplex(Problem &prob, Operation *lastOp) {
1335 SimplexScheduler simplex(prob, lastOp);
1336 return simplex.schedule();
1337}
1338
1340 Operation *lastOp) {
1341 CyclicSimplexScheduler simplex(prob, lastOp);
1342 return simplex.schedule();
1343}
1344
1346 Operation *lastOp) {
1347 SharedOperatorsSimplexScheduler simplex(prob, lastOp);
1348 return simplex.schedule();
1349}
1350
1352 Operation *lastOp) {
1353 ModuloSimplexScheduler simplex(prob, lastOp);
1354 return simplex.schedule();
1355}
1356
1358 Operation *lastOp, float cycleTime) {
1359 ChainingSimplexScheduler simplex(prob, lastOp, cycleTime);
1360 return simplex.schedule();
1361}
1362
1364 Operation *lastOp, float cycleTime) {
1365 ChainingCyclicSimplexScheduler simplex(prob, lastOp, cycleTime);
1366 return simplex.schedule();
1367}
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: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
std::optional< OperatorType > getLinkedOperatorType(Operation *op)
The linked operator type provides the runtime characteristics for op.
Definition Problems.h:196
This class models a resource-constrained scheduling problem.
Definition Problems.h:413
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:427
A wrapper class to uniformly handle def-use and auxiliary dependence edges.
Operation * getDestination() const
Return the destination of the dependence.
Definition Problems.cpp:449
Operation * getSource() const
Return the source of the dependence.
Definition Problems.cpp:445
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.