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"
28 using namespace circt;
52 class 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;
187 class SimplexScheduler :
public SimplexSchedulerBase {
192 Problem &getProblem()
override {
return prob; }
195 SimplexScheduler(
Problem &prob, Operation *lastOp)
196 : SimplexSchedulerBase(lastOp), prob(prob) {}
198 LogicalResult schedule()
override;
206 class 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;
223 class SharedOperatorsSimplexScheduler :
public SimplexSchedulerBase {
228 Problem &getProblem()
override {
return prob; }
233 : SimplexSchedulerBase(lastOp), prob(prob) {}
234 LogicalResult schedule()
override;
239 class 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;
276 class 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;
299 LogicalResult SimplexSchedulerBase::checkLastOp() {
300 auto &prob = getProblem();
301 if (!prob.hasOperation(lastOp))
302 return prob.getContainingOp()->emitError(
303 "problem does not include last operation");
307 bool SimplexSchedulerBase::fillObjectiveRow(SmallVector<int> &row,
311 row[startTimeLocations[startTimeVariables[lastOp]]] = 1;
315 void SimplexSchedulerBase::fillConstraintRow(SmallVector<int> &row,
317 auto &prob = getProblem();
320 unsigned latency = *prob.getLatency(*prob.getLinkedOperatorType(src));
321 row[parameter1Column] = -latency;
323 row[startTimeLocations[startTimeVariables[src]]] = 1;
324 row[startTimeLocations[startTimeVariables[dst]]] = -1;
328 void SimplexSchedulerBase::fillAdditionalConstraintRow(
335 void SimplexSchedulerBase::buildTableau() {
336 auto &prob = getProblem();
344 for (
auto *op : prob.getOperations()) {
345 nonBasicVariables.push_back(var);
346 startTimeVariables[op] = var;
347 startTimeLocations.push_back(firstNonBasicVariableColumn + var);
352 nColumns = nParameters + nonBasicVariables.size();
355 auto addRow = [&]() -> SmallVector<int> & {
356 implicitBasicVariableColumnVector.push_back(0);
357 return tableau.emplace_back(nColumns, 0);
362 bool hasMoreObjectives;
364 auto &objRowVec = addRow();
365 hasMoreObjectives = fillObjectiveRow(objRowVec, nObjectives);
367 }
while (hasMoreObjectives);
370 for (
auto *op : prob.getOperations()) {
371 for (
auto &dep : prob.getDependences(op)) {
372 auto &consRowVec = addRow();
373 fillConstraintRow(consRowVec, dep);
374 basicVariables.push_back(var);
378 for (
auto &dep : additionalConstraints) {
379 auto &consRowVec = addRow();
380 fillAdditionalConstraintRow(consRowVec, dep);
381 basicVariables.push_back(var);
386 nRows = tableau.size();
389 int SimplexSchedulerBase::getParametricConstant(
unsigned row) {
390 auto &rowVec = tableau[row];
393 return rowVec[parameter1Column] + rowVec[parameterSColumn] * parameterS +
394 rowVec[parameterTColumn] * parameterT;
397 SmallVector<int> SimplexSchedulerBase::getObjectiveVector(
unsigned column) {
398 SmallVector<int> objVec;
400 for (
unsigned obj = 0; obj < nObjectives; ++obj)
401 objVec.push_back(tableau[obj][column]);
405 std::optional<unsigned> SimplexSchedulerBase::findDualPivotRow() {
407 for (
unsigned row = firstConstraintRow; row < nRows; ++row)
408 if (getParametricConstant(row) < 0)
414 std::optional<unsigned>
415 SimplexSchedulerBase::findDualPivotColumn(
unsigned pivotRow,
416 bool allowPositive) {
417 SmallVector<int> maxQuot(nObjectives, std::numeric_limits<int>::min());
418 std::optional<unsigned> pivotCol;
424 for (
unsigned col = firstNonBasicVariableColumn; col < nColumns; ++col) {
425 if (frozenVariables.count(
426 nonBasicVariables[col - firstNonBasicVariableColumn]))
429 int pivotCand = tableau[pivotRow][col];
433 if (pivotCand < 0 || (allowPositive && pivotCand > 0)) {
435 assert(pivotCand * pivotCand == 1);
437 SmallVector<int> quot;
438 for (
unsigned obj = 0; obj < nObjectives; ++obj)
439 quot.push_back(tableau[obj][col] / pivotCand);
441 if (std::lexicographical_compare(maxQuot.begin(), maxQuot.end(),
442 quot.begin(), quot.end())) {
452 std::optional<unsigned> SimplexSchedulerBase::findPrimalPivotColumn() {
454 SmallVector<int> zeroVec(nObjectives, 0);
455 for (
unsigned col = firstNonBasicVariableColumn; col < nColumns; ++col) {
456 if (frozenVariables.count(
457 nonBasicVariables[col - firstNonBasicVariableColumn]))
460 SmallVector<int> objVec = getObjectiveVector(col);
461 if (std::lexicographical_compare(objVec.begin(), objVec.end(),
462 zeroVec.begin(), zeroVec.end()))
469 std::optional<unsigned>
470 SimplexSchedulerBase::findPrimalPivotRow(
unsigned pivotColumn) {
471 int minQuot = std::numeric_limits<int>::max();
472 std::optional<unsigned> pivotRow;
478 for (
unsigned row = firstConstraintRow; row < nRows; ++row) {
479 int pivotCand = tableau[row][pivotColumn];
483 int quot = getParametricConstant(row) / pivotCand;
484 if (quot < minQuot) {
494 void SimplexSchedulerBase::multiplyRow(
unsigned row,
int factor) {
496 for (
unsigned col = 0; col < nColumns; ++col)
497 tableau[row][col] *= factor;
499 implicitBasicVariableColumnVector[row] *= factor;
502 void SimplexSchedulerBase::addMultipleOfRow(
unsigned sourceRow,
int factor,
503 unsigned targetRow) {
504 assert(factor != 0 && sourceRow != targetRow);
505 for (
unsigned col = 0; col < nColumns; ++col)
506 tableau[targetRow][col] += tableau[sourceRow][col] * factor;
508 implicitBasicVariableColumnVector[targetRow] +=
509 implicitBasicVariableColumnVector[sourceRow] * factor;
517 void SimplexSchedulerBase::pivot(
unsigned pivotRow,
unsigned pivotColumn) {
519 implicitBasicVariableColumnVector[pivotRow] = 1;
521 int pivotElem = tableau[pivotRow][pivotColumn];
523 assert(pivotElem * pivotElem == 1);
525 multiplyRow(pivotRow, 1 / pivotElem);
527 for (
unsigned row = 0; row < nRows; ++row) {
531 int elem = tableau[row][pivotColumn];
536 addMultipleOfRow(pivotRow, -elem, row);
542 for (
unsigned row = 0; row < nRows; ++row) {
543 tableau[row][pivotColumn] = implicitBasicVariableColumnVector[row];
544 implicitBasicVariableColumnVector[row] = 0;
548 unsigned &nonBasicVar =
549 nonBasicVariables[pivotColumn - firstNonBasicVariableColumn];
550 unsigned &basicVar = basicVariables[pivotRow - firstConstraintRow];
553 if (nonBasicVar < startTimeLocations.size())
554 startTimeLocations[nonBasicVar] = -pivotRow;
555 if (basicVar < startTimeLocations.size())
556 startTimeLocations[basicVar] = pivotColumn;
559 std::swap(nonBasicVar, basicVar);
562 LogicalResult SimplexSchedulerBase::solveTableau() {
566 while (
auto pivotRow = findDualPivotRow()) {
568 if (
auto pivotCol = findDualPivotColumn(*pivotRow)) {
569 pivot(*pivotRow, *pivotCol);
577 int entry1Col = tableau[*pivotRow][parameter1Column];
578 int entryTCol = tableau[*pivotRow][parameterTColumn];
585 int newParameterT = (-entry1Col - 1) / entryTCol + 1;
586 if (newParameterT > parameterT) {
587 parameterT = newParameterT;
588 LLVM_DEBUG(
dbgs() <<
"Increased II to " << parameterT <<
'\n');
601 LogicalResult SimplexSchedulerBase::restoreDualFeasibility() {
606 while (
auto pivotCol = findPrimalPivotColumn()) {
608 if (
auto pivotRow = findPrimalPivotRow(*pivotCol)) {
609 pivot(*pivotRow, *pivotCol);
621 bool SimplexSchedulerBase::isInBasis(
unsigned startTimeVariable) {
622 assert(startTimeVariable < startTimeLocations.size());
623 int loc = startTimeLocations[startTimeVariable];
624 if (-loc >= (
int)firstConstraintRow)
626 if (loc >= (
int)firstNonBasicVariableColumn)
628 llvm_unreachable(
"Invalid variable location");
631 unsigned SimplexSchedulerBase::freeze(
unsigned startTimeVariable,
633 assert(startTimeVariable < startTimeLocations.size());
634 assert(!frozenVariables.count(startTimeVariable));
637 frozenVariables[startTimeVariable] = timeStep;
639 if (!isInBasis(startTimeVariable))
641 return startTimeLocations[startTimeVariable];
644 unsigned pivotRow = -startTimeLocations[startTimeVariable];
648 auto pivotCol = findDualPivotColumn(pivotRow,
true);
652 pivot(pivotRow, *pivotCol);
658 void SimplexSchedulerBase::translate(
unsigned column,
int factor1,
int factorS,
660 for (
unsigned row = 0; row < nRows; ++row) {
661 auto &rowVec = tableau[row];
662 int elem = rowVec[column];
666 rowVec[parameter1Column] += -elem * factor1;
667 rowVec[parameterSColumn] += -elem * factorS;
668 rowVec[parameterTColumn] += -elem * factorT;
672 LogicalResult SimplexSchedulerBase::scheduleAt(
unsigned startTimeVariable,
674 assert(startTimeVariable < startTimeLocations.size());
675 assert(!frozenVariables.count(startTimeVariable));
678 unsigned frozenCol = freeze(startTimeVariable, timeStep);
679 translate(frozenCol, 0, 1, 0);
682 parameterS = timeStep;
683 auto solved = solveTableau();
686 if (failed(solved)) {
689 translate(frozenCol, 0, -1, 0);
690 frozenVariables.erase(startTimeVariable);
691 auto solvedAfterRollback = solveTableau();
692 assert(succeeded(solvedAfterRollback));
693 (void)solvedAfterRollback;
715 translate(parameterSColumn, -timeStep, 1,
721 void SimplexSchedulerBase::moveBy(
unsigned startTimeVariable,
unsigned amount) {
722 assert(startTimeVariable < startTimeLocations.size());
723 assert(frozenVariables.count(startTimeVariable));
726 frozenVariables[startTimeVariable] += amount;
730 translate(startTimeLocations[startTimeVariable], amount,
738 unsigned SimplexSchedulerBase::getStartTime(
unsigned startTimeVariable) {
739 assert(startTimeVariable < startTimeLocations.size());
741 if (!isInBasis(startTimeVariable))
744 return frozenVariables.lookup(startTimeVariable);
748 return getParametricConstant(-startTimeLocations[startTimeVariable]);
751 void SimplexSchedulerBase::dumpTableau() {
752 for (
unsigned j = 0; j < nColumns; ++j)
755 for (
unsigned i = 0; i < nRows; ++i) {
756 if (i == firstConstraintRow) {
757 for (
unsigned j = 0; j < nColumns; ++j) {
758 if (j == firstNonBasicVariableColumn)
764 for (
unsigned j = 0; j < nColumns; ++j) {
765 if (j == firstNonBasicVariableColumn)
767 dbgs() << format(
" %3d", tableau[i][j]);
769 if (i >= firstConstraintRow)
770 dbgs() << format(
" |< %2d", basicVariables[i - firstConstraintRow]);
773 for (
unsigned j = 0; j < nColumns; ++j)
776 dbgs() << format(
" %3d %3d %3d | ", 1, parameterS, parameterT);
777 for (
unsigned j = firstNonBasicVariableColumn; j < nColumns; ++j)
778 dbgs() << format(
" %2d^",
779 nonBasicVariables[j - firstNonBasicVariableColumn]);
787 LogicalResult SimplexScheduler::schedule() {
788 if (failed(checkLastOp()))
795 LLVM_DEBUG(
dbgs() <<
"Initial tableau:\n"; dumpTableau());
797 if (failed(solveTableau()))
798 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
802 dbgs() <<
"Final tableau:\n"; dumpTableau();
803 dbgs() <<
"Optimal solution found with start time of last operation = "
804 << -getParametricConstant(0) <<
'\n');
806 for (
auto *op : prob.getOperations())
807 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
816 void CyclicSimplexScheduler::fillConstraintRow(SmallVector<int> &row,
818 SimplexSchedulerBase::fillConstraintRow(row, dep);
819 if (
auto dist = prob.getDistance(dep))
820 row[parameterTColumn] = *dist;
823 LogicalResult CyclicSimplexScheduler::schedule() {
824 if (failed(checkLastOp()))
831 LLVM_DEBUG(
dbgs() <<
"Initial tableau:\n"; dumpTableau());
833 if (failed(solveTableau()))
834 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
836 LLVM_DEBUG(
dbgs() <<
"Final tableau:\n"; dumpTableau();
837 dbgs() <<
"Optimal solution found with II = " << parameterT
838 <<
" and start time of last operation = "
839 << -getParametricConstant(0) <<
'\n');
841 prob.setInitiationInterval(parameterT);
842 for (
auto *op : prob.getOperations())
843 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
856 LogicalResult SharedOperatorsSimplexScheduler::schedule() {
857 if (failed(checkLastOp()))
864 LLVM_DEBUG(
dbgs() <<
"Initial tableau:\n"; dumpTableau());
866 if (failed(solveTableau()))
867 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
869 LLVM_DEBUG(
dbgs() <<
"After solving resource-free problem:\n"; dumpTableau());
880 auto &ops = prob.getOperations();
881 SmallVector<Operation *> limitedOps;
884 limitedOps.push_back(op);
896 std::stable_sort(limitedOps.begin(), limitedOps.end(),
897 [&](Operation *a, Operation *b) {
898 return getStartTime(startTimeVariables[a]) <
899 getStartTime(startTimeVariables[b]);
907 for (
auto *op : limitedOps) {
908 auto opr = *prob.getLinkedOperatorType(op);
909 unsigned limit = prob.getLimit(opr).value_or(0);
914 unsigned startTimeVar = startTimeVariables[op];
915 unsigned candTime = getStartTime(startTimeVar);
916 while (reservationTable[opr].lookup(candTime) == limit)
921 auto fixed = scheduleAt(startTimeVar, candTime);
926 ++reservationTable[opr][candTime];
928 LLVM_DEBUG(
dbgs() <<
"After scheduling " << startTimeVar
929 <<
" to t=" << candTime <<
":\n";
935 dbgs() <<
"Final tableau:\n"; dumpTableau();
936 dbgs() <<
"Feasible solution found with start time of last operation = "
937 << -getParametricConstant(0) <<
'\n');
940 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
949 LogicalResult ModuloSimplexScheduler::checkLastOp() {
950 auto *contOp = prob.getContainingOp();
951 if (!prob.hasOperation(lastOp))
952 return contOp->emitError(
"problem does not include last operation");
955 auto &ops = prob.getOperations();
956 DenseSet<Operation *> sinks(ops.begin(), ops.end());
958 for (
auto &dep : prob.getDependences(op))
959 if (prob.getDistance(dep).value_or(0) == 0)
962 if (!sinks.contains(lastOp))
963 return contOp->emitError(
"last operation is not a sink");
964 if (sinks.size() > 1)
965 return contOp->emitError(
"multiple sinks detected");
970 LogicalResult ModuloSimplexScheduler::MRT::enter(Operation *op,
972 auto opr = *sched.prob.getLinkedOperatorType(op);
973 auto lim = *sched.prob.getLimit(opr);
976 auto &revTab = reverseTables[opr];
977 assert(!revTab.count(op));
979 unsigned slot = timeStep % sched.parameterT;
980 auto &cell = tables[opr][slot];
981 if (cell.size() < lim) {
989 void ModuloSimplexScheduler::MRT::release(Operation *op) {
990 auto opr = *sched.prob.getLinkedOperatorType(op);
991 auto &revTab = reverseTables[opr];
992 auto it = revTab.find(op);
993 assert(it != revTab.end());
994 tables[opr][it->second].erase(op);
998 bool ModuloSimplexScheduler::fillObjectiveRow(SmallVector<int> &row,
1003 row[startTimeLocations[startTimeVariables[lastOp]]] = 1;
1007 for (
auto *op : getProblem().getOperations())
1009 row[startTimeLocations[startTimeVariables[op]]] = 1;
1012 llvm_unreachable(
"Unsupported objective requested");
1016 void ModuloSimplexScheduler::updateMargins() {
1022 for (
auto *axapTimes : {&alapTimes, &asapTimes}) {
1023 multiplyRow(OBJ_AXAP, -1);
1025 auto dualFeasRestored = restoreDualFeasibility();
1026 auto solved = solveTableau();
1027 assert(succeeded(dualFeasRestored) && succeeded(solved));
1028 (void)dualFeasRestored, (
void)solved;
1030 for (
unsigned stv = 0; stv < startTimeLocations.size(); ++stv)
1031 (*axapTimes)[stv] = getStartTime(stv);
1035 void ModuloSimplexScheduler::scheduleOperation(Operation *n) {
1036 auto oprN = *prob.getLinkedOperatorType(n);
1037 unsigned stvN = startTimeVariables[n];
1044 unsigned stN = getStartTime(stvN);
1045 unsigned ubN = stN + parameterT - 1;
1047 LLVM_DEBUG(
dbgs() <<
"Attempting to schedule in [" << stN <<
", " << ubN
1048 <<
"]: " << *n <<
'\n');
1050 for (
unsigned ct = stN; ct <= ubN; ++ct)
1051 if (succeeded(mrt.enter(n, ct))) {
1052 auto fixedN = scheduleAt(stvN, ct);
1053 if (succeeded(fixedN)) {
1054 LLVM_DEBUG(
dbgs() <<
"Success at t=" << ct <<
" " << *n <<
'\n');
1068 LLVM_DEBUG(
dbgs() <<
"Incrementing II to " << (parameterT + 1)
1069 <<
" to resolve resource conflict for " << *n <<
'\n');
1076 unsigned phiN = stN / parameterT;
1077 unsigned tauN = stN % parameterT;
1081 unsigned deltaN = 1;
1084 SmallVector<Operation *> moved;
1085 for (Operation *j : scheduled) {
1086 auto oprJ = *prob.getLinkedOperatorType(j);
1087 unsigned stvJ = startTimeVariables[j];
1088 unsigned stJ = getStartTime(stvJ);
1089 unsigned phiJ = stJ / parameterT;
1090 unsigned tauJ = stJ % parameterT;
1091 unsigned deltaJ = 0;
1097 if (tauN < tauJ || (tauN == tauJ && phiN > phiJ) ||
1098 (tauN == tauJ && phiN == phiJ && stvN < stvJ)) {
1118 moveBy(stvJ, phiJ + deltaJ);
1123 auto solved = solveTableau();
1124 assert(succeeded(solved));
1128 for (
auto *m : moved)
1130 for (
auto *m : moved) {
1131 auto enteredM = mrt.enter(m, getStartTime(startTimeVariables[m]));
1132 assert(succeeded(enteredM));
1138 auto fixedN = scheduleAt(stvN, stN + phiN + deltaN);
1139 auto enteredN = mrt.enter(n, tauN + deltaN);
1140 assert(succeeded(fixedN) && succeeded(enteredN));
1141 (void)fixedN, (
void)enteredN;
1144 unsigned ModuloSimplexScheduler::computeResMinII() {
1145 unsigned resMinII = 1;
1147 for (
auto *op : prob.getOperations())
1149 ++uses[*prob.getLinkedOperatorType(op)];
1151 for (
auto pair : uses)
1152 resMinII = std::max(
1153 resMinII, (
unsigned)ceil(pair.second / *prob.getLimit(pair.first)));
1158 LogicalResult ModuloSimplexScheduler::schedule() {
1159 if (failed(checkLastOp()))
1163 parameterT = computeResMinII();
1164 LLVM_DEBUG(
dbgs() <<
"ResMinII = " << parameterT <<
"\n");
1166 asapTimes.resize(startTimeLocations.size());
1167 alapTimes.resize(startTimeLocations.size());
1169 LLVM_DEBUG(
dbgs() <<
"Initial tableau:\n"; dumpTableau());
1171 if (failed(solveTableau()))
1172 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
1175 auto &ops = prob.getOperations();
1176 for (
auto *op : ops)
1178 unscheduled.push_back(op);
1181 while (!unscheduled.empty()) {
1188 std::min_element(unscheduled.begin(), unscheduled.end(),
1189 [&](Operation *opA, Operation *opB) {
1190 auto stvA = startTimeVariables[opA];
1191 auto stvB = startTimeVariables[opB];
1192 auto slackA = alapTimes[stvA] - asapTimes[stvA];
1193 auto slackB = alapTimes[stvB] - asapTimes[stvB];
1194 return slackA < slackB;
1196 Operation *op = *opIt;
1197 unscheduled.erase(opIt);
1199 scheduleOperation(op);
1200 scheduled.push_back(op);
1203 LLVM_DEBUG(
dbgs() <<
"Final tableau:\n"; dumpTableau();
1204 dbgs() <<
"Solution found with II = " << parameterT
1205 <<
" and start time of last operation = "
1206 << -getParametricConstant(0) <<
'\n');
1208 prob.setInitiationInterval(parameterT);
1209 for (
auto *op : ops)
1210 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1219 void ChainingSimplexScheduler::fillAdditionalConstraintRow(
1221 fillConstraintRow(row, dep);
1224 row[parameter1Column] -= 1;
1227 LogicalResult ChainingSimplexScheduler::schedule() {
1229 prob, cycleTime, additionalConstraints)))
1236 LLVM_DEBUG(
dbgs() <<
"Initial tableau:\n"; dumpTableau());
1238 if (failed(solveTableau()))
1239 return prob.getContainingOp()->emitError() <<
"problem is infeasible";
1243 dbgs() <<
"Final tableau:\n"; dumpTableau();
1244 dbgs() <<
"Optimal solution found with start time of last operation = "
1245 << -getParametricConstant(0) <<
'\n');
1247 for (
auto *op : prob.getOperations())
1248 prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1251 assert(succeeded(filledIn));
1262 SimplexScheduler simplex(prob, lastOp);
1263 return simplex.schedule();
1267 Operation *lastOp) {
1268 CyclicSimplexScheduler simplex(prob, lastOp);
1269 return simplex.schedule();
1273 Operation *lastOp) {
1274 SharedOperatorsSimplexScheduler simplex(prob, lastOp);
1275 return simplex.schedule();
1279 Operation *lastOp) {
1280 ModuloSimplexScheduler simplex(prob, lastOp);
1281 return simplex.schedule();
1285 Operation *lastOp,
float cycleTime) {
1286 ChainingSimplexScheduler simplex(prob, lastOp, cycleTime);
1287 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 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< OperatorType > getLinkedOperatorType(Operation *op)
The linked operator type provides the runtime characteristics for op.
This class models a resource-constrained scheduling problem.
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...
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...
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
mlir::raw_indented_ostream & dbgs()