17#include "mlir/IR/Operation.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/Format.h"
26#define DEBUG_TYPE "simplex-schedulers"
52class SimplexSchedulerBase {
88 SmallVector<SmallVector<int>> tableau;
92 SmallVector<int> implicitBasicVariableColumnVector;
103 SmallVector<unsigned> nonBasicVariables;
108 SmallVector<unsigned> basicVariables;
113 DenseMap<Operation *, unsigned> startTimeVariables;
119 SmallVector<int> startTimeLocations;
123 DenseMap<unsigned, unsigned> frozenVariables;
131 unsigned nObjectives;
133 unsigned &firstConstraintRow = nObjectives;
136 static constexpr unsigned nParameters = 3;
138 static constexpr unsigned parameter1Column = 0;
140 static constexpr unsigned parameterSColumn = 1;
142 static constexpr unsigned parameterTColumn = 2;
144 static constexpr unsigned firstNonBasicVariableColumn = nParameters;
148 SmallVector<Problem::Dependence> additionalConstraints;
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,
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);
181 explicit SimplexSchedulerBase(Operation *lastOp) : lastOp(lastOp) {}
182 virtual ~SimplexSchedulerBase() =
default;
183 virtual LogicalResult schedule() = 0;
187class SimplexScheduler :
public SimplexSchedulerBase {
192 Problem &getProblem()
override {
return prob; }
195 SimplexScheduler(
Problem &prob, Operation *lastOp)
196 : SimplexSchedulerBase(lastOp), prob(prob) {}
198 LogicalResult schedule()
override;
206class CyclicSimplexScheduler :
public SimplexSchedulerBase {
211 Problem &getProblem()
override {
return prob; }
212 void fillConstraintRow(SmallVector<int> &row,
216 CyclicSimplexScheduler(
CyclicProblem &prob, Operation *lastOp)
217 : SimplexSchedulerBase(lastOp), prob(prob) {}
218 LogicalResult schedule()
override;
223class SharedOperatorsSimplexScheduler :
public SimplexSchedulerBase {
228 Problem &getProblem()
override {
return prob; }
233 : SimplexSchedulerBase(lastOp), prob(prob) {}
234 LogicalResult schedule()
override;
239class ModuloSimplexScheduler :
public CyclicSimplexScheduler {
242 ModuloSimplexScheduler &sched;
249 explicit MRT(ModuloSimplexScheduler &sched) : sched(sched) {}
250 LogicalResult enter(Operation *op,
unsigned timeStep);
251 void release(Operation *op);
255 SmallVector<unsigned> asapTimes, alapTimes;
256 SmallVector<Operation *> unscheduled, scheduled;
260 Problem &getProblem()
override {
return prob; }
261 LogicalResult checkLastOp()
override;
262 enum { OBJ_LATENCY = 0, OBJ_AXAP };
263 bool fillObjectiveRow(SmallVector<int> &row,
unsigned obj)
override;
264 void updateMargins();
265 void scheduleOperation(Operation *n);
266 unsigned computeResMinII();
269 ModuloSimplexScheduler(
ModuloProblem &prob, Operation *lastOp)
270 : CyclicSimplexScheduler(prob, lastOp), prob(prob), mrt(*
this) {}
271 LogicalResult schedule()
override;
276class ChainingSimplexScheduler :
public SimplexSchedulerBase {
282 Problem &getProblem()
override {
return prob; }
283 void fillAdditionalConstraintRow(SmallVector<int> &row,
289 : SimplexSchedulerBase(lastOp), prob(prob), cycleTime(cycleTime) {}
290 LogicalResult schedule()
override;
298class ChainingCyclicSimplexScheduler :
public SimplexSchedulerBase {
304 Problem &getProblem()
override {
return prob; }
305 void fillConstraintRow(SmallVector<int> &row,
307 void fillAdditionalConstraintRow(SmallVector<int> &row,
313 : SimplexSchedulerBase(lastOp), prob(prob), cycleTime(cycleTime) {}
314 LogicalResult schedule()
override;
323LogicalResult SimplexSchedulerBase::checkLastOp() {
324 auto &prob = getProblem();
325 if (!prob.hasOperation(lastOp))
326 return prob.getContainingOp()->emitError(
327 "problem does not include last operation");
331bool SimplexSchedulerBase::fillObjectiveRow(SmallVector<int> &row,
335 row[startTimeLocations[startTimeVariables[lastOp]]] = 1;
339void SimplexSchedulerBase::fillConstraintRow(SmallVector<int> &row,
341 auto &prob = getProblem();
344 unsigned latency = *prob.getLatency(*prob.getLinkedOperatorType(src));
345 row[parameter1Column] = -latency;
347 row[startTimeLocations[startTimeVariables[src]]] = 1;
348 row[startTimeLocations[startTimeVariables[dst]]] = -1;
352void SimplexSchedulerBase::fillAdditionalConstraintRow(
359void SimplexSchedulerBase::buildTableau() {
360 auto &prob = getProblem();
368 for (
auto *op : prob.getOperations()) {
369 nonBasicVariables.push_back(var);
370 startTimeVariables[op] = var;
371 startTimeLocations.push_back(firstNonBasicVariableColumn + var);
376 nColumns = nParameters + nonBasicVariables.size();
379 auto addRow = [&]() -> SmallVector<int> & {
380 implicitBasicVariableColumnVector.push_back(0);
381 return tableau.emplace_back(nColumns, 0);
386 bool hasMoreObjectives;
388 auto &objRowVec = addRow();
389 hasMoreObjectives = fillObjectiveRow(objRowVec, nObjectives);
391 }
while (hasMoreObjectives);
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);
402 for (
auto &dep : additionalConstraints) {
403 auto &consRowVec = addRow();
404 fillAdditionalConstraintRow(consRowVec, dep);
405 basicVariables.push_back(var);
410 nRows = tableau.size();
413int SimplexSchedulerBase::getParametricConstant(
unsigned row) {
414 auto &rowVec = tableau[row];
417 return rowVec[parameter1Column] + rowVec[parameterSColumn] * parameterS +
418 rowVec[parameterTColumn] * parameterT;
421SmallVector<int> SimplexSchedulerBase::getObjectiveVector(
unsigned column) {
422 SmallVector<int> objVec;
424 for (
unsigned obj = 0; obj < nObjectives; ++obj)
425 objVec.push_back(tableau[obj][column]);
429std::optional<unsigned> SimplexSchedulerBase::findDualPivotRow() {
431 for (
unsigned row = firstConstraintRow; row < nRows; ++row)
432 if (getParametricConstant(row) < 0)
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;
448 for (
unsigned col = firstNonBasicVariableColumn; col < nColumns; ++col) {
449 if (frozenVariables.count(
450 nonBasicVariables[col - firstNonBasicVariableColumn]))
453 int pivotCand = tableau[pivotRow][col];
457 if (pivotCand < 0 || (allowPositive && pivotCand > 0)) {
459 assert(pivotCand * pivotCand == 1);
461 SmallVector<int> quot;
462 for (
unsigned obj = 0; obj < nObjectives; ++obj)
463 quot.push_back(tableau[obj][col] / pivotCand);
465 if (std::lexicographical_compare(maxQuot.begin(), maxQuot.end(),
466 quot.begin(), quot.end())) {
476std::optional<unsigned> SimplexSchedulerBase::findPrimalPivotColumn() {
478 SmallVector<int> zeroVec(nObjectives, 0);
479 for (
unsigned col = firstNonBasicVariableColumn; col < nColumns; ++col) {
480 if (frozenVariables.count(
481 nonBasicVariables[col - firstNonBasicVariableColumn]))
484 SmallVector<int> objVec = getObjectiveVector(col);
485 if (std::lexicographical_compare(objVec.begin(), objVec.end(),
486 zeroVec.begin(), zeroVec.end()))
493std::optional<unsigned>
494SimplexSchedulerBase::findPrimalPivotRow(
unsigned pivotColumn) {
495 int minQuot = std::numeric_limits<int>::max();
496 std::optional<unsigned> pivotRow;
502 for (
unsigned row = firstConstraintRow; row < nRows; ++row) {
503 int pivotCand = tableau[row][pivotColumn];
507 int quot = getParametricConstant(row) / pivotCand;
508 if (quot < minQuot) {
518void SimplexSchedulerBase::multiplyRow(
unsigned row,
int factor) {
520 for (
unsigned col = 0; col < nColumns; ++col)
521 tableau[row][col] *= factor;
523 implicitBasicVariableColumnVector[row] *= factor;
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;
532 implicitBasicVariableColumnVector[targetRow] +=
533 implicitBasicVariableColumnVector[sourceRow] * factor;
541void SimplexSchedulerBase::pivot(
unsigned pivotRow,
unsigned pivotColumn) {
543 implicitBasicVariableColumnVector[pivotRow] = 1;
545 int pivotElem = tableau[pivotRow][pivotColumn];
547 assert(pivotElem * pivotElem == 1);
549 multiplyRow(pivotRow, 1 / pivotElem);
551 for (
unsigned row = 0; row < nRows; ++row) {
555 int elem = tableau[row][pivotColumn];
560 addMultipleOfRow(pivotRow, -elem, row);
566 for (
unsigned row = 0; row < nRows; ++row) {
567 tableau[row][pivotColumn] = implicitBasicVariableColumnVector[row];
568 implicitBasicVariableColumnVector[row] = 0;
572 unsigned &nonBasicVar =
573 nonBasicVariables[pivotColumn - firstNonBasicVariableColumn];
574 unsigned &basicVar = basicVariables[pivotRow - firstConstraintRow];
577 if (nonBasicVar < startTimeLocations.size())
578 startTimeLocations[nonBasicVar] = -pivotRow;
579 if (basicVar < startTimeLocations.size())
580 startTimeLocations[basicVar] = pivotColumn;
583 std::swap(nonBasicVar, basicVar);
586LogicalResult SimplexSchedulerBase::solveTableau() {
590 while (
auto pivotRow = findDualPivotRow()) {
592 if (
auto pivotCol = findDualPivotColumn(*pivotRow)) {
593 pivot(*pivotRow, *pivotCol);
601 int entry1Col = tableau[*pivotRow][parameter1Column];
602 int entryTCol = tableau[*pivotRow][parameterTColumn];
609 int newParameterT = (-entry1Col - 1) / entryTCol + 1;
610 if (newParameterT > parameterT) {
611 parameterT = newParameterT;
612 LLVM_DEBUG(dbgs() <<
"Increased II to " << parameterT <<
'\n');
625LogicalResult SimplexSchedulerBase::restoreDualFeasibility() {
630 while (
auto pivotCol = findPrimalPivotColumn()) {
632 if (
auto pivotRow = findPrimalPivotRow(*pivotCol)) {
633 pivot(*pivotRow, *pivotCol);
645bool SimplexSchedulerBase::isInBasis(
unsigned startTimeVariable) {
646 assert(startTimeVariable < startTimeLocations.size());
647 int loc = startTimeLocations[startTimeVariable];
648 if (-loc >= (
int)firstConstraintRow)
650 if (loc >= (
int)firstNonBasicVariableColumn)
652 llvm_unreachable(
"Invalid variable location");
655unsigned SimplexSchedulerBase::freeze(
unsigned startTimeVariable,
657 assert(startTimeVariable < startTimeLocations.size());
658 assert(!frozenVariables.count(startTimeVariable));
661 frozenVariables[startTimeVariable] = timeStep;
663 if (!isInBasis(startTimeVariable))
665 return startTimeLocations[startTimeVariable];
668 unsigned pivotRow = -startTimeLocations[startTimeVariable];
672 auto pivotCol = findDualPivotColumn(pivotRow,
true);
676 pivot(pivotRow, *pivotCol);
682void SimplexSchedulerBase::translate(
unsigned column,
int factor1,
int factorS,
684 for (
unsigned row = 0; row < nRows; ++row) {
685 auto &rowVec = tableau[row];
686 int elem = rowVec[column];
690 rowVec[parameter1Column] += -elem * factor1;
691 rowVec[parameterSColumn] += -elem * factorS;
692 rowVec[parameterTColumn] += -elem * factorT;
696LogicalResult SimplexSchedulerBase::scheduleAt(
unsigned startTimeVariable,
698 assert(startTimeVariable < startTimeLocations.size());
699 assert(!frozenVariables.count(startTimeVariable));
702 unsigned frozenCol = freeze(startTimeVariable, timeStep);
703 translate(frozenCol, 0, 1, 0);
706 parameterS = timeStep;
707 auto solved = solveTableau();
710 if (failed(solved)) {
713 translate(frozenCol, 0, -1, 0);
714 frozenVariables.erase(startTimeVariable);
715 auto solvedAfterRollback = solveTableau();
716 assert(succeeded(solvedAfterRollback));
717 (void)solvedAfterRollback;
739 translate(parameterSColumn, -timeStep, 1,
745void SimplexSchedulerBase::moveBy(
unsigned startTimeVariable,
unsigned amount) {
746 assert(startTimeVariable < startTimeLocations.size());
747 assert(frozenVariables.count(startTimeVariable));
750 frozenVariables[startTimeVariable] += amount;
754 translate(startTimeLocations[startTimeVariable], amount,
762unsigned SimplexSchedulerBase::getStartTime(
unsigned startTimeVariable) {
763 assert(startTimeVariable < startTimeLocations.size());
765 if (!isInBasis(startTimeVariable))
768 return frozenVariables.lookup(startTimeVariable);
772 return getParametricConstant(-startTimeLocations[startTimeVariable]);
775void SimplexSchedulerBase::dumpTableau() {
776 for (
unsigned j = 0; j < nColumns; ++j)
779 for (
unsigned i = 0; i < nRows; ++i) {
780 if (i == firstConstraintRow) {
781 for (
unsigned j = 0; j < nColumns; ++j) {
782 if (j == firstNonBasicVariableColumn)
788 for (
unsigned j = 0; j < nColumns; ++j) {
789 if (j == firstNonBasicVariableColumn)
791 dbgs() << format(
" %3d", tableau[i][j]);
793 if (i >= firstConstraintRow)
794 dbgs() << format(
" |< %2d", basicVariables[i - firstConstraintRow]);
797 for (
unsigned j = 0; j < nColumns; ++j)
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]);
811LogicalResult SimplexScheduler::schedule() {
812 if (failed(checkLastOp()))
819 LLVM_DEBUG(dbgs() <<
"Initial tableau:\n"; dumpTableau());
821 if (failed(solveTableau()))
822 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
826 dbgs() <<
"Final tableau:\n"; dumpTableau();
827 dbgs() <<
"Optimal solution found with start time of last operation = "
828 << -getParametricConstant(0) <<
'\n');
830 for (
auto *op : prob.getOperations())
831 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
840void CyclicSimplexScheduler::fillConstraintRow(SmallVector<int> &row,
842 SimplexSchedulerBase::fillConstraintRow(row, dep);
843 if (
auto dist = prob.getDistance(dep))
844 row[parameterTColumn] = *dist;
847LogicalResult CyclicSimplexScheduler::schedule() {
848 if (failed(checkLastOp()))
855 LLVM_DEBUG(dbgs() <<
"Initial tableau:\n"; dumpTableau());
857 if (failed(solveTableau()))
858 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
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');
865 prob.setInitiationInterval(parameterT);
866 for (
auto *op : prob.getOperations())
867 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
881 return prob.
getLimit(rsrc).value_or(0) > 0;
885LogicalResult SharedOperatorsSimplexScheduler::schedule() {
886 if (failed(checkLastOp()))
893 LLVM_DEBUG(dbgs() <<
"Initial tableau:\n"; dumpTableau());
895 if (failed(solveTableau()))
896 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
898 LLVM_DEBUG(dbgs() <<
"After solving resource-free problem:\n"; dumpTableau());
909 auto &ops = prob.getOperations();
910 SmallVector<Operation *> limitedOps;
913 limitedOps.push_back(op);
925 std::stable_sort(limitedOps.begin(), limitedOps.end(),
926 [&](Operation *a, Operation *b) {
927 return getStartTime(startTimeVariables[a]) <
928 getStartTime(startTimeVariables[b]);
936 for (
auto *op : limitedOps) {
937 auto maybeRsrcs = prob.getLinkedResourceTypes(op);
938 assert(maybeRsrcs &&
"Limited operation must have linked resource types");
940 auto &rsrcs = *maybeRsrcs;
941 assert(rsrcs.size() == 1 &&
942 "Multi-resource operations are not yet supported by this scheduler");
944 auto rsrc = rsrcs[0];
945 unsigned limit = prob.getLimit(rsrc).value_or(0);
950 unsigned startTimeVar = startTimeVariables[op];
951 unsigned candTime = getStartTime(startTimeVar);
952 while (reservationTable[rsrc].lookup(candTime) == limit)
957 auto fixed = scheduleAt(startTimeVar, candTime);
962 ++reservationTable[rsrc][candTime];
964 LLVM_DEBUG(dbgs() <<
"After scheduling " << startTimeVar
965 <<
" to t=" << candTime <<
":\n";
971 dbgs() <<
"Final tableau:\n"; dumpTableau();
972 dbgs() <<
"Feasible solution found with start time of last operation = "
973 << -getParametricConstant(0) <<
'\n');
976 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
985LogicalResult ModuloSimplexScheduler::checkLastOp() {
986 auto *contOp = prob.getContainingOp();
987 if (!prob.hasOperation(lastOp))
988 return contOp->emitError(
"problem does not include last operation");
991 auto &ops = prob.getOperations();
992 DenseSet<Operation *> sinks(ops.begin(), ops.end());
994 for (auto &dep : prob.getDependences(op))
995 if (prob.getDistance(dep).value_or(0) == 0)
996 sinks.erase(dep.getSource());
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");
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");
1011 auto &rsrcs = *maybeRsrcs;
1012 assert(rsrcs.size() == 1 &&
1013 "Multi-resource operations are not yet supported by MRT");
1015 auto rsrc = rsrcs[0];
1016 auto lim = *sched.prob.getLimit(rsrc);
1019 auto &revTab = reverseTables[rsrc];
1020 assert(!revTab.count(op));
1022 unsigned slot = timeStep % sched.parameterT;
1023 auto &cell = tables[rsrc][slot];
1024 if (cell.size() < lim) {
1032void ModuloSimplexScheduler::MRT::release(Operation *op) {
1033 auto maybeRsrcs = sched.prob.getLinkedResourceTypes(op);
1034 assert(maybeRsrcs &&
"Operation must have linked resource types");
1036 auto &rsrcs = *maybeRsrcs;
1037 assert(rsrcs.size() == 1 &&
1038 "Multi-resource operations are not yet supported by MRT");
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);
1048bool ModuloSimplexScheduler::fillObjectiveRow(SmallVector<int> &row,
1053 row[startTimeLocations[startTimeVariables[lastOp]]] = 1;
1057 for (
auto *op : getProblem().getOperations())
1059 row[startTimeLocations[startTimeVariables[op]]] = 1;
1062 llvm_unreachable(
"Unsupported objective requested");
1066void ModuloSimplexScheduler::updateMargins() {
1072 for (
auto *axapTimes : {&alapTimes, &asapTimes}) {
1073 multiplyRow(OBJ_AXAP, -1);
1075 auto dualFeasRestored = restoreDualFeasibility();
1076 auto solved = solveTableau();
1077 assert(succeeded(dualFeasRestored) && succeeded(solved));
1078 (void)dualFeasRestored, (
void)solved;
1080 for (
unsigned stv = 0; stv < startTimeLocations.size(); ++stv)
1081 (*axapTimes)[stv] = getStartTime(stv);
1085void ModuloSimplexScheduler::scheduleOperation(Operation *n) {
1086 auto oprN = *prob.getLinkedOperatorType(n);
1087 unsigned stvN = startTimeVariables[n];
1094 unsigned stN = getStartTime(stvN);
1095 unsigned ubN = stN + parameterT - 1;
1097 LLVM_DEBUG(dbgs() <<
"Attempting to schedule in [" << stN <<
", " << ubN
1098 <<
"]: " << *n <<
'\n');
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');
1118 LLVM_DEBUG(dbgs() <<
"Incrementing II to " << (parameterT + 1)
1119 <<
" to resolve resource conflict for " << *n <<
'\n');
1126 unsigned phiN = stN / parameterT;
1127 unsigned tauN = stN % parameterT;
1131 unsigned deltaN = 1;
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;
1147 if (tauN < tauJ || (tauN == tauJ && phiN > phiJ) ||
1148 (tauN == tauJ && phiN == phiJ && stvN < stvJ)) {
1168 moveBy(stvJ, phiJ + deltaJ);
1173 auto solved = solveTableau();
1174 assert(succeeded(solved));
1178 for (
auto *m : moved)
1180 for (
auto *m : moved) {
1181 auto enteredM = mrt.enter(m, getStartTime(startTimeVariables[m]));
1182 assert(succeeded(enteredM));
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;
1194unsigned ModuloSimplexScheduler::computeResMinII() {
1195 unsigned resMinII = 1;
1197 for (
auto *op : prob.getOperations()) {
1198 auto maybeRsrcs = prob.getLinkedResourceTypes(op);
1202 for (
auto rsrc : *maybeRsrcs) {
1203 if (prob.getLimit(rsrc).value_or(0) > 0)
1208 for (
auto pair : uses)
1209 resMinII = std::max(
1210 resMinII, (unsigned)ceil(pair.second / *prob.getLimit(pair.first)));
1215LogicalResult ModuloSimplexScheduler::schedule() {
1216 if (failed(checkLastOp()))
1220 parameterT = computeResMinII();
1221 LLVM_DEBUG(dbgs() <<
"ResMinII = " << parameterT <<
"\n");
1223 asapTimes.resize(startTimeLocations.size());
1224 alapTimes.resize(startTimeLocations.size());
1226 LLVM_DEBUG(dbgs() <<
"Initial tableau:\n"; dumpTableau());
1228 if (failed(solveTableau()))
1229 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
1232 auto &ops = prob.getOperations();
1233 for (
auto *op : ops)
1235 unscheduled.push_back(op);
1238 while (!unscheduled.empty()) {
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;
1253 Operation *op = *opIt;
1254 unscheduled.erase(opIt);
1256 scheduleOperation(op);
1257 scheduled.push_back(op);
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');
1265 prob.setInitiationInterval(parameterT);
1266 for (
auto *op : ops)
1267 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1276void ChainingSimplexScheduler::fillAdditionalConstraintRow(
1278 fillConstraintRow(row, dep);
1281 row[parameter1Column] -= 1;
1284LogicalResult ChainingSimplexScheduler::schedule() {
1286 prob, cycleTime, additionalConstraints)))
1293 LLVM_DEBUG(dbgs() <<
"Initial tableau:\n"; dumpTableau());
1295 if (failed(solveTableau()))
1296 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
1300 dbgs() <<
"Final tableau:\n"; dumpTableau();
1301 dbgs() <<
"Optimal solution found with start time of last operation = "
1302 << -getParametricConstant(0) <<
'\n');
1304 for (
auto *op : prob.getOperations())
1305 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1308 assert(succeeded(filledIn));
1318void ChainingCyclicSimplexScheduler::fillConstraintRow(
1320 SimplexSchedulerBase::fillConstraintRow(row, dep);
1321 if (
auto dist = prob.getDistance(dep))
1322 row[parameterTColumn] = *dist;
1325void ChainingCyclicSimplexScheduler::fillAdditionalConstraintRow(
1327 fillConstraintRow(row, dep);
1330 row[parameter1Column] -= 1;
1333LogicalResult ChainingCyclicSimplexScheduler::schedule() {
1335 prob, cycleTime, additionalConstraints)))
1342 LLVM_DEBUG(dbgs() <<
"Initial tableau:\n"; dumpTableau());
1344 if (failed(solveTableau()))
1345 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
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');
1352 prob.setInitiationInterval(parameterT);
1353 for (
auto *op : prob.getOperations())
1354 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1357 assert(succeeded(filledIn));
1368 SimplexScheduler simplex(prob, lastOp);
1369 return simplex.schedule();
1373 Operation *lastOp) {
1374 CyclicSimplexScheduler simplex(prob, lastOp);
1375 return simplex.schedule();
1379 Operation *lastOp) {
1380 SharedOperatorsSimplexScheduler simplex(prob, lastOp);
1381 return simplex.schedule();
1385 Operation *lastOp) {
1386 ModuloSimplexScheduler simplex(prob, lastOp);
1387 return simplex.schedule();
1391 Operation *lastOp,
float cycleTime) {
1392 ChainingSimplexScheduler simplex(prob, lastOp, cycleTime);
1393 return simplex.schedule();
1397 Operation *lastOp,
float cycleTime) {
1398 ChainingCyclicSimplexScheduler simplex(prob, lastOp, cycleTime);
1399 return simplex.schedule();
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...
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
This class models a cyclic scheduling problem.
This class models the modulo scheduling problem as the composition of the cyclic problem and the reso...
This class models the most basic scheduling problem.
std::optional< SmallVector< ResourceType > > getLinkedResourceTypes(Operation *op)
The linked resource type provides the available resources for op.
This class models a resource-constrained scheduling problem.
std::optional< unsigned > getLimit(ResourceType rsrc)
The limit is the maximum number of operations using rsrc that are available in the target hardware.
A wrapper class to uniformly handle def-use and auxiliary dependence edges.
Operation * getDestination() const
Return the destination of the dependence.
Operation * getSource() const
Return the source of the dependence.
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).