12#include "llvm/ADT/BitVector.h"
13#include "llvm/ADT/MapVector.h"
14#include "llvm/Support/Debug.h"
25#define DEBUG_TYPE "aie-sa-placer"
32static size_t drawBoundedIndex(std::mt19937 &rng,
size_t upperExclusive) {
33 return static_cast<size_t>(rng()) % upperExclusive;
37static double drawUnitReal(std::mt19937 &rng) {
38 constexpr double denominator =
static_cast<double>(std::mt19937::max()) + 1.0;
39 return static_cast<double>(rng()) / denominator;
43static void deterministicShuffle(MutableArrayRef<TileID> values,
45 for (
size_t i = values.size(); i > 1; --i)
46 std::swap(values[i - 1], values[drawBoundedIndex(rng, i)]);
51static SmallVector<TileID>
53 SmallVector<TileID> neighbors;
54 for (std::optional<TileID> candidate :
57 if (candidate && *candidate != tilePos &&
58 ObjectFifoCreateOp::delegateReaches(targetModel, *candidate, tilePos,
60 neighbors.push_back(*candidate);
65static int64_t alignedBufferBytes(
const AIETargetModel &targetModel,
66 AIETileType tileType, int64_t bytes) {
68 return llvm::alignTo(bytes,
79 int greedyIters,
const SAConfig &cfg)
80 : temperature(startTemp), movesPerIter(movesPerIter), maxIters(maxIters),
81 greedyIters(greedyIters),
82 windowSize(std::max(movesPerIter, cfg.windowSize)), config(cfg) {}
85 return currIteration >= maxIters ||
86 (inGreedyStage && currGreedyIteration >= greedyIters);
90 int total = acceptCount + rejectCount;
91 return (total == 0) ? 1.0 :
static_cast<double>(acceptCount) / total;
95 history.push_back(accepted ? 1 : 0);
96 ++(accepted ? acceptCount : rejectCount);
101 if (!inGreedyStage) {
103 double adaptiveFactor;
105 adaptiveFactor = config.coolFast;
106 else if (ratio > 0.8)
107 adaptiveFactor = config.coolSteady;
108 else if (ratio > 0.15)
109 adaptiveFactor = config.coolBalanced;
111 adaptiveFactor = config.coolStuck;
113 temperature *= adaptiveFactor;
115 if (ratio < config.greedyThreshold || temperature < 1e-8) {
116 inGreedyStage =
true;
120 currGreedyIteration++;
125void SASchedule::trimWindow() {
126 while (
static_cast<int>(history.size()) > windowSize) {
127 if (history.front() == 1)
139void SAPlacer::buildNetModel(SmallVector<ObjectFifoCreateOp> &objectFifos,
140 SmallVector<ObjectFifoLinkOp> &objectFifoLinks) {
142 tileToNetIndices.clear();
144 for (
auto ofOp : objectFifos) {
146 Value producerTile = ofOp.getProducerTile();
147 if (
auto *prodOp = producerTile.getDefiningOp())
148 if (isa<LogicalTileOp>(prodOp))
151 for (Value consumerTile : ofOp.getConsumerTiles()) {
152 if (
auto *consOp = consumerTile.getDefiningOp())
153 if (isa<LogicalTileOp>(consOp))
162 net.
isMulticast = (ofOp.getConsumerTiles().size() >
163 static_cast<unsigned>(config.multicastThreshold));
165 size_t idx = nets.size();
170 tileToNetIndices[ep].push_back(idx);
178void SAPlacer::buildRouteModel(
179 DeviceOp device, ArrayRef<FlowOp> flows, ArrayRef<PacketFlowOp> pktFlows,
180 ArrayRef<RouteOp> routes,
181 ArrayRef<DMAChannelAnalysis::ChannelClaim> claims) {
184 for (
auto &[tile, inOut] :
186 for (
int i = 0; i < inOut.first; ++i)
187 routeEnds.push_back({tile, false});
188 for (
int i = 0; i < inOut.second; ++i)
189 routeEnds.push_back({tile, true});
191 for (RouteOp route : routes) {
193 auto addEnd = [&](StringRef name,
bool output) {
194 auto endpoint = SymbolTable::lookupNearestSymbolFrom<RouteEndpoint>(
195 route, StringAttr::get(route.getContext(), name));
198 Operation *tileOp = endpoint.getTile().getDefiningOp();
199 if (!isa_and_nonnull<LogicalTileOp>(tileOp))
203 for (StringRef source : route.getSourceNames())
204 addEnd(source,
true);
205 for (StringRef dest : route.getDestinationNames())
209 unsigned threshold =
static_cast<unsigned>(config.multicastThreshold);
210 net.
isMulticast = route.getDestinations().size() > threshold ||
211 route.getSources().size() > threshold;
212 size_t idx = nets.size();
215 tileToNetIndices[ep].push_back(idx);
218 for (
auto pool : device.getOps<ObjectFifoPoolOp>()) {
219 Operation *tileOp = pool.getTile().getDefiningOp();
220 if (!isa_and_nonnull<TileLike>(tileOp))
222 staticBufferSizes[tileOp] += pool.getObjectSizeInBytes() * pool.getDepth();
226 for (
auto endpoint : device.getOps<RouteEndpoint>()) {
227 auto tile = dyn_cast_or_null<TileLike>(endpoint.getTile().getDefiningOp());
228 if (endpoint.getRouteBundle() != WireBundle::DMA || !tile ||
229 tile.getTileType() != AIETileType::MemTile)
231 std::optional<int> channel = endpoint.getRouteChannel();
232 PlannedDmaEnd end{0,
nullptr, -1, 0,
false, 0, 0, channel};
233 if (
auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(endpoint.getOperation())) {
234 ObjectFifoPoolOp pool = dma.getPoolOp();
235 end = {dma.getNumBDs(),
240 pool.getObjectSizeInBytes(),
241 pool.getContiguous() ? pool.getObjectsPerBuffer() : 0,
244 memTileEnds[tile].push_back({endpoint.getRouteDirection(), end});
248int SAPlacer::computeNetHPWL(
const NetInfo &net)
const {
251 int hpwl = spanCol + spanRow;
253 hpwl *= config.multicastMultiplier;
257 int area = spanCol * spanRow;
261int SAPlacer::computeTotalHPWL()
const {
263 for (
const auto &net : nets)
264 total += computeNetHPWL(net);
268void SAPlacer::initBoundingBoxes() {
269 for (
auto &net : nets) {
274 net.
bb = {first.col, first.col, first.row, first.row, 1, 1, 1, 1};
276 for (
size_t i = 1; i < net.
endpoints.size(); i++) {
282 }
else if (pos.col == net.
bb.
minCol) {
289 }
else if (pos.col == net.
bb.
maxCol) {
296 }
else if (pos.row == net.
bb.
minRow) {
303 }
else if (pos.row == net.
bb.
maxRow) {
314int SAPlacer::evaluateMove(
315 Operation *tile,
TileID newPos,
316 SmallVector<std::pair<size_t, NetBoundingBox>> &backups) {
320 auto it = tileToNetIndices.find(tile);
321 if (it == tileToNetIndices.end())
324 for (
size_t netIdx : it->second) {
325 NetInfo &net = nets[netIdx];
326 backups.push_back({netIdx, net.
bb});
327 int oldCost = computeNetHPWL(net);
330 int newMinCol = INT_MAX, newMaxCol = INT_MIN;
331 int newMinRow = INT_MAX, newMaxRow = INT_MIN;
332 int cMinCol = 0, cMaxCol = 0, cMinRow = 0, cMaxRow = 0;
335 TileID pos = (ep == tile) ? newPos : currentPlacement[ep];
337 if (pos.col < newMinCol) {
340 }
else if (pos.col == newMinCol) {
343 if (pos.col > newMaxCol) {
346 }
else if (pos.col == newMaxCol) {
349 if (pos.row < newMinRow) {
352 }
else if (pos.row == newMinRow) {
355 if (pos.row > newMaxRow) {
358 }
else if (pos.row == newMaxRow) {
363 net.
bb = {newMinCol, newMaxCol, newMinRow, newMaxRow,
364 cMinCol, cMaxCol, cMinRow, cMaxRow};
366 deltaCost += computeNetHPWL(net) - oldCost;
372void SAPlacer::revertMove(
373 SmallVector<std::pair<size_t, NetBoundingBox>> &backups) {
374 for (
auto &[netIdx, savedBB] : backups)
375 nets[netIdx].bb = savedBB;
382bool SAPlacer::isLegalPosition(Operation *tile,
TileID pos)
const {
383 auto it = tileTypes.find(tile);
384 if (it == tileTypes.end())
387 AIETileType needed = it->second;
388 AIETileType actual =
targetModel->getTileType(pos.col, pos.row);
389 if (needed != actual)
393 if (needed == AIETileType::CoreTile) {
394 auto occIt = physToLogical.find(pos);
395 if (occIt != physToLogical.end() && occIt->second != tile)
403SmallVector<Operation *> SAPlacer::namedAt(Operation *tile,
TileID pos,
404 Operation *leaving)
const {
405 SmallVector<Operation *> here;
409 if (other != tile && other != leaving && positionOf(other) == pos)
410 here.push_back(other);
418std::optional<TileID> SAPlacer::positionOf(Operation *tile)
const {
419 if (
auto it = currentPlacement.find(tile);
420 tile && it != currentPlacement.end())
422 if (
auto tileOp = dyn_cast_or_null<TileOp>(tile))
423 return tileOp.getTileID();
428void SAPlacer::addRouteEndContribution(
size_t endIdx,
int sign) {
429 const RouteEndInfo &end = routeEnds[endIdx];
430 std::optional<TileID> pos = positionOf(end.tile);
434 currentDMAUsage[*pos].second += sign;
436 currentDMAUsage[*pos].first += sign;
439void SAPlacer::addFifoContribution(
size_t fifoIdx,
int sign) {
440 const auto &fb = fifoBuffers[fifoIdx];
441 std::optional<TileID> prodAt = positionOf(fb.producerTile);
445 const FifoEndTypes &types = fifoEndTypes[fifoIdx];
450 std::optional<TileID> delegatePos = positionOf(fb.delegate);
455 bool prodCharged =
false;
456 bool prodNeedsDMA =
false;
459 auto heldLocks = [&](int64_t depth) {
461 fb.producerCore, fb.rearmed);
463 auto addLocks = [&](
TileID pos,
int segments, int64_t depth,
bool needed) {
464 if (!needed || !segments)
466 SmallVector<int> counts =
468 addLockDemand(pos, sign * std::accumulate(counts.begin(), counts.end(), 0));
470 using LinkPool = FifoBufferInfo::LinkPool;
471 auto chargeLinkPool = [&](
TileID pos,
const PlannedDmaEnd &end) {
472 int count = end.contiguousObjects ? 1 : end.depth;
474 end.objectBytes * std::max<int64_t>(end.contiguousObjects, 1);
475 currentMemUsage[pos] +=
478 targetModel->getTileType(pos.col, pos.row), bytes);
479 chargeCoreFifo(pos, bytes, sign * count);
483 bool prodLinked = fb.producerLinkPool != LinkPool::None;
484 if (
const std::optional<PlannedDmaEnd> &plan = fb.producerLinkPlan) {
485 chargeLinkPool(prodPos, *plan);
486 addLocks(prodPos, fb.producerLinkSegments, plan->depth,
true);
489 for (
size_t ci = 0; ci < fb.consumerTiles.size(); ci++) {
490 std::optional<TileID> consAt = positionOf(fb.consumerTiles[ci]);
497 SharedMemory shared = fb.forcesDMA
499 : ObjectFifoCreateOp::sharedMemoryOf(
501 positionOf(fb.linkTile));
502 bool isSharedMem = shared != SharedMemory::None;
503 int64_t sharedBytes =
504 std::max(fb.producerSizeBytes, fb.consumerSizeBytes) * fb.sharedDepth;
506 int64_t sharedRaw = std::max(fb.producerRawBytes, fb.consumerRawBytes);
507 bool consLinked = fb.consumerLinkPools[ci] != LinkPool::None;
508 if (
const std::optional<PlannedDmaEnd> &plan = fb.consumerLinkPlans[ci]) {
509 chargeLinkPool(consPos, *plan);
510 addLocks(consPos, fb.consumerLinkSegments[ci], plan->depth,
true);
512 bool sharedPool = isSharedMem && !prodLinked && !consLinked;
513 if (prodPos == consPos && sharedPool) {
514 currentMemUsage[delegatePos.value_or(prodPos)] += sign * sharedBytes;
515 chargeCoreFifo(delegatePos.value_or(prodPos), sharedRaw,
516 sign * fb.sharedDepth);
518 addLocks(delegatePos.value_or(prodPos), 1, fb.sharedDepth,
519 heldLocks(fb.sharedDepth));
520 }
else if (sharedPool) {
523 bufTile = *delegatePos;
524 }
else if (shared == SharedMemory::Either) {
526 int64_t prodUsed = currentMemUsage.lookup(prodPos);
527 int64_t consUsed = currentMemUsage.lookup(consPos);
528 bufTile = (prodUsed <= consUsed) ? prodPos : consPos;
532 if (fb.consumers.size() == 1)
533 sharedMemDestination[fifoIdx] = bufTile;
535 auto it = sharedMemDestination.find(fifoIdx);
536 bufTile = (it != sharedMemDestination.end()) ? it->second : prodPos;
538 }
else if (shared == SharedMemory::Second) {
543 currentMemUsage[bufTile] += sign * sharedBytes;
544 chargeCoreFifo(bufTile, sharedRaw, sign * fb.sharedDepth);
546 addLocks(bufTile, 1, fb.sharedDepth, heldLocks(fb.sharedDepth));
547 }
else if (!isSharedMem) {
548 if (!prodCharged && !prodLinked && !prodIsShim && !fb.linkSharedProd) {
549 currentMemUsage[prodPos] +=
550 sign * fb.producerSizeBytes * fb.producerDepth;
551 chargeCoreFifo(prodPos, fb.producerRawBytes, sign * fb.producerDepth);
553 addLocks(prodPos, 1, fb.producerDepth, heldLocks(fb.producerDepth));
556 if (!consLinked && !consIsShim) {
557 currentMemUsage[consPos] +=
558 sign * fb.consumerSizeBytes * fb.consumerDepths[ci];
559 chargeCoreFifo(consPos, fb.consumerRawBytes,
560 sign * fb.consumerDepths[ci]);
561 if (fb.consumerEnds[ci])
562 addLocks(consPos, 1, fb.consumerDepths[ci], !fb.unsynchronized);
571 bool plio = cast<ObjectFifoCreateOp>(fb.fifoOp).getPlio();
572 if (consIsShim ? !plio : fb.consumerEnds[ci].has_value())
573 drawChannel(consPos,
false, fb.consumerPins[ci], sign);
574 prodNeedsDMA = prodIsShim ? !plio : fb.producerEnd.has_value();
579 drawChannel(prodPos,
true, fb.producerPin, sign);
582void SAPlacer::drawChannel(
TileID position,
bool output,
583 const std::optional<PinnedChannels::End> &pin,
587 taken = pinUse.place(position, *pin, sign);
588 pinLog.push_back({position, *pin, sign});
590 auto &[in, out] = currentDMAUsage[position];
591 (output ? out : in) += taken;
594void SAPlacer::addLockDemand(
TileID pos,
int locks) {
595 int &demand = currentLockDemand[pos];
596 int held =
targetModel->getNumLocks(pos.col, pos.row);
597 positionsOverLocks += (demand + locks > held) - (demand > held);
601void SAPlacer::initResourceTracking() {
602 currentMemUsage.clear();
603 currentLockDemand.clear();
604 positionsOverLocks = 0;
605 SmallVector<std::pair<unsigned, int64_t>> depths;
606 auto at = [
this](Value tile) {
return positionOf(tile.getDefiningOp()); };
607 for (
auto [index, variable] : llvm::enumerate(variableLinks))
608 depths.push_back({index, variable.plan.depthAt(*
targetModel, at)});
610 currentDMAUsage.clear();
612 sharedMemDestination.clear();
613 coreFifoBuffers.clear();
616 auto typeOf = [&](Operation *tile) -> std::optional<AIETileType> {
617 if (
auto it = tileTypes.find(tile); it != tileTypes.end())
619 if (
auto placed = dyn_cast_or_null<TileOp>(tile))
620 return placed.getTileType();
623 fifoEndTypes.clear();
624 for (
const auto &fb : fifoBuffers) {
625 FifoEndTypes &types = fifoEndTypes.emplace_back();
626 types.producer = typeOf(fb.producerTile);
627 for (Operation *cons : fb.consumerTiles)
628 types.consumers.push_back(typeOf(cons));
632 tileToFifoIndices.clear();
633 for (
size_t i = 0; i < fifoBuffers.size(); i++) {
634 const auto &fb = fifoBuffers[i];
636 tileToFifoIndices[fb.producer].push_back(i);
637 for (
auto *cons : fb.consumers)
639 tileToFifoIndices[cons].push_back(i);
641 tileToFifoIndices[fb.delegate].push_back(i);
646 for (
auto &[op, bufSize] : staticBufferSizes)
647 if (std::optional<TileID> pos = positionOf(op))
648 currentMemUsage[*pos] += bufSize;
650 for (
auto &[op, bytes] : stackSizes)
651 if (std::optional<TileID> pos = positionOf(op))
652 currentMemUsage[*pos] += bytes;
654 for (
size_t i = 0; i < fifoBuffers.size(); i++)
655 addFifoContribution(i, +1);
656 coreUnplacedAt.clear();
657 for (
auto &[op, _] : coreContents)
658 if (std::optional<TileID> pos = positionOf(op))
659 coreDirty.insert(*pos);
660 refreshCoreUnplaced();
662 tileToRouteEnds.clear();
663 for (
size_t i = 0; i < routeEnds.size(); i++) {
664 tileToRouteEnds[routeEnds[i].tile].push_back(i);
665 addRouteEndContribution(i, +1);
667 for (
auto &[tile, claims] :
claimsOf)
668 if (std::optional<TileID> pos = positionOf(tile))
669 for (
const DMAChannelAnalysis::ChannelClaim &claim : claims)
670 pinUse.claim(*pos, claim, 1);
672 for (
auto &[tile, locks] : fixedLocks)
673 homeLocks[tile] += locks;
674 for (
const InputLockGroup &group : inputLockGroups)
675 homeLocks[group.home] += group.locks;
676 for (
auto &[tile, locks] : homeLocks)
677 if (std::optional<TileID> pos = positionOf(tile))
678 addLockDemand(*pos, locks);
679 for (
auto &[at, locks] : placedLocks)
680 addLockDemand(at, locks);
683 if (std::optional<TileID> pos = positionOf(shim);
684 pos && !runtimeBdAt.contains(*pos))
685 chargeRuntimeBds(*pos);
688 for (
auto &[op, _] : memTileEnds)
689 spillTiles.insert(op);
690 for (
auto &[op, _] : memTileFixed)
691 spillTiles.insert(op);
692 spillTiles.insert(logicalMemTiles.begin(), logicalMemTiles.end());
693 delegateTermTiles.clear();
694 for (
const auto &fb : fifoBuffers) {
697 delegateTermTiles.insert(fb.delegate);
698 delegateTermTiles.insert(fb.producer);
699 delegateTermTiles.insert(fb.consumers.begin(), fb.consumers.end());
702 for (
const Adjacency *adj : {&cascadeAdjacency, &sharedMemAdjacency})
703 for (
auto [first, second] : adj->edges) {
704 pairedTiles.insert(first.getOperation());
705 pairedTiles.insert(second.getOperation());
708 memSpilloverPenalty = computeMemSpilloverPenalty();
709 bdCountPenalty = computeBDCountPenalty();
710 delegatePenalty = computeDelegatePenalty();
711 dmaPenalty = computeDMAChannelPenalty();
712 coreOverflowTiles = overflowingCoreTiles();
713 coreOverflowPenalty = computeCoreOverflowPenalty();
716 columnSouthPorts.clear();
717 for (
int col = 0; col <
targetModel->columns(); ++col) {
718 for (
int row = 0; row <
targetModel->rows(); ++row)
720 {static_cast<int>(targetModel->getNumSourceSwitchboxConnections(
721 col, row, WireBundle::North)),
722 static_cast<int>(targetModel->getNumDestSwitchboxConnections(
723 col, row, WireBundle::North)),
724 static_cast<int>(targetModel->getNumSourceSwitchboxConnections(
725 col, row, WireBundle::South)),
726 static_cast<int>(targetModel->getNumDestSwitchboxConnections(
727 col, row, WireBundle::South))});
731 while (bottom < targetModel->rows() &&
734 columnSouthPorts.push_back(
735 bottom < targetModel->rows()
736 ?
static_cast<int>(
targetModel->getNumSourceSwitchboxConnections(
737 col, bottom, WireBundle::South))
742 incomingCount.clear();
745 if (std::optional<TileID> at = positionOf(op))
746 chargeStreams(op, *at, 1);
747 auto columnOf = [
this](Operation *op) -> std::optional<int> {
748 std::optional<TileID> at = positionOf(op);
749 return at ? std::optional(at->col) : std::nullopt;
753 for (
auto [index, group] : llvm::enumerate(
ddrGroups)) {
754 int64_t score =
ddrGroupSpread(group, columnOf, config.ddrWeight);
755 ddrScoreOf[index] = score;
758 ddrPenalty =
static_cast<int>(ddrTotal);
763 if (std::optional<TileID> at = positionOf(op))
765 llvm::SmallVector<TileID> positions;
766 for (
auto &[at, key] : keyAt)
767 positions.push_back(at);
768 for (
const DenseMap<TileID, unsigned> &neighbour :
neighbourCores)
769 for (
auto &[at, key] : neighbour)
770 positions.push_back(at);
771 llvm::sort(positions);
772 positions.erase(llvm::unique(positions), positions.end());
773 for (
TileID at : positions)
774 coresChanged += coresChangedAt(at);
777 auto placed = [
this](Operation *op) {
return positionOf(op); };
778 for (
auto [index, net] : llvm::enumerate(
streamNets)) {
779 auto &[src, dsts] = netStreams[index];
780 if (
streamOf(net, placed, src, dsts))
781 cuts.add(src, dsts, net.packet, 1);
783 streamCutPenalty = config.streamCutPenaltyPerChannel * cuts.over();
784 cachedResourcePenalty = memSpilloverPenalty + coreOverflowPenalty +
785 computeLockPenalty() + dmaPenalty + bdCountPenalty +
786 delegatePenalty + streamCutPenalty;
787 cachedPressure = computeMemoryPressure() + computeSoftTerms();
790int SAPlacer::portExcess(
TileID at)
const {
791 StreamDemand streams = streamsAt.lookup(at);
792 const StreamDemand &ports = portsAt[at.col *
targetModel->rows() + at.row];
799int SAPlacer::columnExcess(
int col)
const {
800 return std::max(0, incomingAt.lookup(col) - columnSouthPorts[col]);
803void SAPlacer::chargeStreams(Operation *op,
TileID at,
int sign) {
807 portsOver -= portExcess(at);
808 StreamDemand &streams = streamsAt[at];
809 streams.
northIn += sign * demand->second.northIn;
810 streams.
northOut += sign * demand->second.northOut;
811 streams.
southIn += sign * demand->second.southIn;
812 streams.
southOut += sign * demand->second.southOut;
813 portsOver += portExcess(at);
817 portsOver -= columnExcess(at.col);
818 for (Operation *fifo : incoming->second) {
819 int &count = incomingCount[{at.col, fifo}];
820 if (!count || count + sign == 0)
821 incomingAt[at.col] += sign;
824 portsOver += columnExcess(at.col);
827int SAPlacer::computeSoftTerms()
const {
828 return static_cast<int>(config.streamNearWeight *
829 cuts.near(config.streamNearFraction) +
830 config.portOverWeight * portsOver + ddrPenalty +
831 config.coresChangedWeight * coresChanged);
834int SAPlacer::coresChangedAt(
TileID pos)
const {
835 unsigned mine = keyAt.lookup(pos);
837 for (
const DenseMap<TileID, unsigned> &neighbour :
neighbourCores) {
838 unsigned theirs = neighbour.lookup(pos);
840 writes += (mine != 0) + (theirs != 0);
845int SAPlacer::computeMemoryPressure()
const {
846 int64_t coreCapacity =
targetModel->getLocalMemorySize();
847 int64_t memTileCapacity =
targetModel->getMemTileSize();
850 for (
auto &[tilePos, used] : currentMemUsage) {
851 auto tileType =
targetModel->getTileType(tilePos.col, tilePos.row);
852 if (
targetModel->isShimNOCorPLTile(tilePos.col, tilePos.row))
855 (tileType == AIETileType::MemTile) ? memTileCapacity : coreCapacity;
856 double utilization =
static_cast<double>(used) / capacity;
857 if (utilization > config.pressureThreshold) {
858 double excess = (utilization - config.pressureThreshold) /
859 (1.0 - config.pressureThreshold);
860 pressure +=
static_cast<int>(config.pressurePerKB * excess * excess);
871int SAPlacer::computeDelegatePenalty(SmallVectorImpl<TileID> *charged)
const {
873 for (
const auto &fb : fifoBuffers) {
874 std::optional<TileID> delegatePos = positionOf(fb.delegate);
877 std::optional<TileID> prodPos = positionOf(fb.producerTile);
878 std::optional<TileID> consPos = positionOf(fb.consumerTiles.front());
879 if (!prodPos || !consPos)
881 std::optional<TileID> linkPos = positionOf(fb.linkTile);
882 bool home = ObjectFifoCreateOp::allocatedHome(
883 *
targetModel, *prodPos, *consPos, *delegatePos, linkPos);
884 if (home ? fb.fitsLinkPool : fb.allocateFallsBackToDMA)
887 penalty += config.delegateWeightPerDist;
889 charged->append({*delegatePos, *prodPos, *consPos});
892 for (std::optional<TileID> held : {delegatePos, linkPos}) {
895 for (
TileID end : {*prodPos, *consPos}) {
896 if (ObjectFifoCreateOp::delegateReaches(*
targetModel, *held, end, end))
899 std::abs(held->col - end.col) + std::abs(held->row - end.row);
900 penalty += config.delegateWeightPerDist * std::max(dist - 1, 1);
902 charged->append({*held, end});
911int SAPlacer::computeMemSpilloverPenalty(SmallVectorImpl<TileID> *charged) {
912 std::vector<int64_t> key;
913 auto keyPosition = [&](Operation *op) {
914 std::optional<TileID> at = positionOf(op);
915 key.push_back(at ? at->col : -1);
916 key.push_back(at ? at->row : -1);
918 for (
auto &[op, _] : memTileEnds)
920 for (
auto &[op, _] : memTileFixed)
922 for (Operation *tile : logicalMemTiles)
924 for (
const VariableLink &variable : variableLinks)
925 key.push_back(variable.depth);
926 if (
const int *known = charged ?
nullptr : spillPenaltyOf.find(key))
929 if (memTileIndex.empty())
930 for (
int col = 0; col <
targetModel->columns(); ++col)
931 for (
int row = 0; row <
targetModel->rows(); ++row)
932 if (
targetModel->getTileType(col, row) == AIETileType::MemTile) {
933 memTileIndex[{col, row}] = memTiles.size();
934 memTiles.push_back({
targetModel->getMemTileSize(), {}});
935 spillNeighbours[{col, row}] =
938 SmallVector<MemTileSpillSearch::Tile> tiles = memTiles;
939 const DenseMap<TileID, unsigned> &index = memTileIndex;
940 auto neighboursOf = [&](
TileID at) {
941 auto it = spillNeighbours.find(at);
942 return it != spillNeighbours.end()
946 for (
auto &[op, fixed] : memTileFixed)
947 if (std::optional<TileID> at = positionOf(op))
948 llvm::append_range(tiles[index.lookup(*at)].fixed, fixed);
953 llvm::MapVector<std::pair<Operation *, int>,
954 std::pair<const PlannedDmaEnd *, std::pair<int, int>>>
957 SmallVector<int64_t> bytes;
960 llvm::MapVector<TileID, SmallVector<Operation *>> tilesAt;
961 for (
auto &[tile, _] : memTileEnds)
962 if (std::optional<TileID> at = positionOf(tile))
963 tilesAt[*at].push_back(tile);
964 SmallVector<Position> positions;
965 for (
auto &[at, here] : tilesAt) {
966 Position &position = positions.emplace_back();
968 (void)bdShortfall(at, here, &position.sets, &position.bytes);
969 for (Operation *op : here)
970 for (
const MemTileEnd &end : memTileEnds.find(op)->second) {
971 const PlannedDmaEnd &plan = end.end;
972 auto split = dyn_cast_or_null<ObjectFifoPoolOp>(plan.
pool);
973 if (!plan.
pool || (split && split.getBuffers()))
975 auto &[first, demand] = position.pools[{plan.
pool, plan.
id}];
976 first = first ? first : &plan;
977 ++(end.dir == DMAChannelDir::S2MM ? demand.first : demand.second);
980 llvm::sort(positions, [](
const Position &a,
const Position &b) {
981 return std::make_pair(a.at.col, a.at.row) <
982 std::make_pair(b.at.col, b.at.row);
985 !chargedPools.empty() || llvm::any_of(positions, [](
const Position &p) {
986 return !p.sets.empty();
991 using Walk =
const SmallVector<std::pair<Operation *, int>> *;
992 auto unsortedShapes = [&](ArrayRef<unsigned> members, ArrayRef<Walk> walk) {
993 SmallVector<std::pair<SpillPool, TileID>> shaped;
994 for (
unsigned member : members) {
995 const Position &position = positions[member];
996 unsigned home = index.lookup(position.at);
997 for (
auto &[key, entry] : position.pools) {
998 auto [plan, demand] = entry;
999 int busier = std::max(demand.first, demand.second);
1000 int64_t whole = plan->contiguousObjects;
1002 (chargedPools.contains(plan->pool) ||
1003 (walk[member] && llvm::is_contained(*walk[member], key))))
1004 whole = plan->depth;
1005 shaped.push_back({{plan->objectBytes * std::max<int64_t>(whole, 1),
1006 whole ? 1 : plan->depth, home, busier},
1012 auto shapes = [&](ArrayRef<unsigned> members, ArrayRef<Walk> walk) {
1013 SmallVector<std::pair<SpillPool, TileID>> shaped =
1014 unsortedShapes(members, walk);
1015 llvm::stable_sort(shaped, [](
const auto &a,
const auto &b) {
1016 return std::make_pair(a.second.col, a.second.row) <
1017 std::make_pair(b.second.col, b.second.row);
1020 [](
const auto &pool) {
return pool.first.bytes; });
1024 auto attempt = [&](ArrayRef<std::pair<SpillPool, TileID>> pools,
1025 ArrayRef<unsigned> order) {
1026 SmallVector<MemTileSpillSearch::Buffer> buffers;
1027 for (
unsigned i : order) {
1028 auto [pool, at] = pools[i];
1029 SmallVector<unsigned, 2> neighbours;
1030 for (
TileID neighbour : neighboursOf(at))
1031 if (
auto it = index.find(neighbour); it != index.end())
1032 neighbours.push_back(it->second);
1033 buffers.append(pool.count, {pool.bytes, pool.home, true, neighbours});
1035 MemTileSpillSearch search(tiles,
1037 return search.place(buffers) ? int64_t{0}
1038 : std::max<int64_t>(search.unplacedBytes, 1);
1040 auto inOrder = [](
size_t size) {
1041 return llvm::to_vector(llvm::seq<unsigned>(0, size));
1046 DenseMap<TileID, std::vector<Operation *>> opsAt;
1047 for (
auto &[op, _] : memTileEnds)
1048 if (std::optional<TileID> at = positionOf(op))
1049 opsAt[*at].push_back(op);
1050 for (
auto &[op, _] : memTileFixed)
1051 if (std::optional<TileID> at = positionOf(op))
1052 opsAt[*at].push_back(op);
1053 for (Operation *tile : logicalMemTiles)
1054 if (std::optional<TileID> at = positionOf(tile))
1055 opsAt[*at].push_back(tile);
1056 for (
auto &[at, tiles] : physicalTiles)
1057 llvm::append_range(opsAt[at], tiles);
1058 for (
auto &[_, ops] : opsAt) {
1060 ops.erase(llvm::unique(ops), ops.end());
1062 SmallVector<TileID> homes =
1063 llvm::map_to_vector(positions, [](
const Position &p) {
return p.at; });
1064 SmallVector<unsigned> componentOf =
1066 unsigned components =
1067 componentOf.empty() ? 0 : *llvm::max_element(componentOf) + 1;
1068 SmallVector<Walk> walk(positions.size(),
nullptr);
1069 int64_t unplaced = 0;
1070 bool anyOverfull =
false;
1071 for (
unsigned component = 0; component < components; ++component) {
1072 SmallVector<unsigned> members;
1073 for (
auto [i, c] : llvm::enumerate(componentOf))
1075 members.push_back(i);
1076 std::vector<uintptr_t> tilesKey;
1077 SmallVector<std::pair<int, int>> reach;
1078 for (
unsigned member : members) {
1079 reach.push_back({positions[member].at.col, positions[member].at.row});
1080 for (
TileID n : neighboursOf(positions[member].at))
1081 reach.push_back({n.col, n.row});
1084 reach.erase(llvm::unique(reach), reach.end());
1085 for (
auto [col, row] : reach) {
1086 tilesKey.push_back(col);
1087 tilesKey.push_back(row);
1088 std::vector<Operation *> ops = opsAt.lookup({col, row});
1089 tilesKey.push_back(ops.size());
1090 for (Operation *op : ops)
1091 tilesKey.push_back(
reinterpret_cast<uintptr_t
>(op));
1093 for (
const VariableLink &variable : variableLinks)
1094 tilesKey.push_back(
static_cast<uintptr_t
>(variable.depth));
1095 SmallVector<SmallVector<int64_t>> bytes;
1096 for (
unsigned member : members)
1097 bytes.push_back(positions[member].sets.empty() ? SmallVector<int64_t>{0}
1098 : positions[member].bytes);
1100 auto places = [&](ArrayRef<unsigned> choice) {
1101 std::vector<uintptr_t> key = tilesKey;
1102 for (
auto [member, set] : llvm::zip_equal(members, choice)) {
1104 walk[member] = positions[member].sets.empty()
1106 : &positions[member].sets[set];
1108 if (
const int64_t *known = unplacedOf.find(key))
1109 return (last = *known) == 0;
1110 auto shaped = shapes(members, walk);
1111 last = attempt(shaped, inOrder(shaped.size()));
1112 unplacedOf.record(key, last);
1117 int64_t needed = 0, room = 0;
1118 for (
auto &[pool, _] :
1119 unsortedShapes(members, SmallVector<Walk>(walk.size())))
1120 needed += pool.bytes * pool.count;
1121 for (
auto [col, row] : reach) {
1123 for (
const BufferAllocation &buffer :
1124 tiles[index.lookup({col, row})].fixed)
1125 room -= buffer.size;
1127 DMAChannelAnalysis::WalkChoice choice;
1128 choice.
sets.assign(members.size(), 0);
1129 anyOverfull |= needed > room;
1133 (void)places(choice.
sets);
1134 for (
auto [member, set] : llvm::zip_equal(members, choice.
sets))
1135 walk[member] = positions[member].sets.empty()
1137 : &positions[member].sets[set];
1139 if (charged && last)
1140 for (
unsigned member : members)
1141 charged->push_back(positions[member].at);
1144 if (unplaced && !anyWalked && !anyOverfull) {
1145 SmallVector<unsigned> all =
1146 llvm::to_vector(llvm::seq<unsigned>(0, positions.size()));
1147 auto split = shapes(all, SmallVector<Walk>(positions.size(),
nullptr));
1148 SmallVector<SpillPool> records;
1149 for (
auto &[pool, _] : split)
1150 records.push_back(pool);
1154 int penalty = ((unplaced + 1023) / 1024) * config.memPenaltyPerKB;
1156 spillPenaltyOf.record(key, penalty);
1162SmallVector<TileID> SAPlacer::overflowingCoreTiles()
const {
1163 SmallVector<TileID> tiles;
1164 for (
auto &[tilePos, unplaced] : coreUnplacedAt)
1166 tiles.push_back(tilePos);
1171void SAPlacer::chargeCoreFifo(
TileID pos, int64_t bytes,
int count) {
1173 targetModel->getTileType(pos.col, pos.row) != AIETileType::CoreTile)
1175 BufferCounts &held = coreFifoBuffers[pos];
1176 if ((held[bytes] += count) == 0)
1177 held.erase(held.find(bytes));
1178 coreFifoLog.push_back({pos, bytes, count});
1181int64_t SAPlacer::coreUnplaced(
TileID pos,
const BufferCounts &added,
1182 const BufferCounts &removed)
const {
1183 SmallVector<const CoreTileContents *, 2> here;
1184 int numBanks =
targetModel->getNumBanks(pos.col, pos.row);
1186 std::vector<int64_t> tileKey = {numBanks};
1187 auto addOp = [&](Operation *op) {
1188 if (
auto it = coreContents.find(op); it != coreContents.end()) {
1189 here.push_back(&it->second);
1190 tileKey.push_back(
reinterpret_cast<intptr_t
>(op));
1193 if (
auto physical = physicalTiles.find(pos); physical != physicalTiles.end())
1194 for (Operation *op : physical->second)
1196 if (Operation *op = physToLogical.lookup(pos))
1197 if (
auto at = currentPlacement.find(op);
1198 at != currentPlacement.end() && at->second == pos)
1200 tileKey.push_back(-1);
1201 static const BufferCounts none;
1202 auto held = coreFifoBuffers.find(pos);
1203 const BufferCounts &base =
1204 held == coreFifoBuffers.end() ? none : held->second;
1205 BufferCounts adjusted;
1206 if (!added.empty() || !removed.empty()) {
1208 for (
auto [bytes, count] : added)
1209 adjusted[bytes] += count;
1210 for (
auto [bytes, count] : removed)
1211 adjusted[bytes] -= count;
1213 const BufferCounts &fifo = added.empty() && removed.empty() ? base : adjusted;
1214 for (
auto [bytes, count] : fifo)
1216 tileKey.insert(tileKey.end(), {bytes, count});
1217 if (
auto cached = coreUnplacedByTile.find(tileKey);
1218 cached != coreUnplacedByTile.end())
1219 return cached->second;
1221 TileMemoryLimits limits =
1223 TileLayoutProblem problem;
1228 problem.
budget = config.placementBudget;
1229 for (
auto [bytes, count] : fifo) {
1230 TileLayoutBuffer buffer;
1231 buffer.
size = bytes;
1235 for (
int i = 0; i < count; ++i)
1236 problem.
buffers.push_back(buffer);
1238 for (
const CoreTileContents *contents : here) {
1239 llvm::append_range(problem.
buffers, contents->buffers);
1240 if (contents->hasCore) {
1242 problem.
stackRun = contents->stackRun;
1243 problem.
stackBank = contents->stackBank;
1249 std::vector<int64_t> key = {problem.
numBanks,
1255 for (
const TileLayoutBuffer &buffer : problem.
buffers) {
1256 key.insert(key.end(),
1257 {buffer.size, buffer.alignBytes, buffer.sectionAlignBytes,
1258 buffer.aligned, buffer.address.value_or(-1),
1259 buffer.memBank.value_or(-1), buffer.initialized,
1260 static_cast<int64_t>(buffer.spaceBanks.size())});
1264 if (coreUnplacedByTile.size() > (1u << 18))
1265 coreUnplacedByTile.clear();
1266 if (
auto cached = coreUnplacedOf.find(key); cached != coreUnplacedOf.end()) {
1267 coreUnplacedByTile[std::move(tileKey)] = cached->second;
1268 return cached->second;
1270 if (coreUnplacedOf.size() > (1u << 16))
1271 coreUnplacedOf.clear();
1275 for (
const TileLayoutBuffer &buffer : problem.
buffers)
1276 bytes += buffer.
size;
1279 coreUnplacedOf[std::move(key)] = excess;
1280 coreUnplacedByTile[std::move(tileKey)] = excess;
1283 TileLayoutStats stats;
1284 TileLayout layout =
layoutTile(problem, stats);
1285 int64_t unplaced = 0;
1291 for (
const TileLayoutBuffer &buffer : problem.
buffers)
1292 unplaced += buffer.
size;
1293 unplaced = std::max<int64_t>(unplaced, 1);
1295 coreUnplacedOf[std::move(key)] = unplaced;
1296 coreUnplacedByTile[std::move(tileKey)] = unplaced;
1300SmallVector<TileID> SAPlacer::refreshCoreUnplaced() {
1302 llvm::SmallDenseMap<std::pair<TileID, int64_t>, int, 8> net;
1303 for (
auto &[pos, bytes, count] : coreFifoLog)
1304 net[{pos, bytes}] += count;
1305 for (
auto &[charge, count] : net)
1307 coreDirty.insert(charge.first);
1308 SmallVector<TileID> changed;
1309 for (
TileID pos : coreDirty) {
1310 if (
targetModel->getTileType(pos.col, pos.row) != AIETileType::CoreTile)
1312 coreUnplacedAt[pos] = coreUnplaced(pos);
1313 changed.push_back(pos);
1319DenseSet<TileID> SAPlacer::coreOverflowReads()
const {
1320 DenseSet<TileID> reads;
1321 for (
TileID pos : coreOverflowTiles) {
1330SAPlacer::planCoreFit(
TileID pos, DenseMap<TileID, BufferCounts> &lent,
1331 SmallVectorImpl<std::pair<size_t, TileID>> *moves)
const {
1334 SmallVector<std::pair<size_t, int64_t>, 8> relocatable;
1335 if (Operation *op = physToLogical.lookup(pos))
1336 if (
auto fifoIt = tileToFifoIndices.find(op);
1337 fifoIt != tileToFifoIndices.end()) {
1338 DenseSet<size_t> seen;
1339 for (
size_t fi : fifoIt->second) {
1340 if (!seen.insert(fi).second)
1342 const auto &fb = fifoBuffers[fi];
1343 if (fb.consumers.size() != 1 || !fb.producer || !fb.consumers[0] ||
1344 fb.delegate || fb.forcesDMA)
1346 auto prodIt = currentPlacement.find(fb.producer);
1347 auto consIt = currentPlacement.find(fb.consumers[0]);
1348 if (prodIt == currentPlacement.end() ||
1349 consIt == currentPlacement.end() || prodIt->second != pos ||
1350 consIt->second != pos)
1352 relocatable.push_back(
1353 {fi, std::max(fb.producerSizeBytes, fb.consumerSizeBytes) *
1357 llvm::stable_sort(relocatable, [&](
const auto &a,
const auto &b) {
1358 const FifoBufferInfo &x = fifoBuffers[a.first];
1359 const FifoBufferInfo &y = fifoBuffers[b.first];
1360 return std::make_tuple(b.second,
1361 std::max(y.producerRawBytes, y.consumerRawBytes),
1362 firstAcquire.lookup_or(x.fifoOp, UINT_MAX),
1363 collected.rank.lookup(x.fifoOp)) <
1364 std::make_tuple(a.second,
1365 std::max(x.producerRawBytes, x.consumerRawBytes),
1366 firstAcquire.lookup_or(y.fifoOp, UINT_MAX),
1367 collected.rank.lookup(y.fifoOp));
1371 SmallVector<TileID, 4> neighbours(getMemAffinityNeighbors(*
targetModel, pos));
1372 llvm::sort(neighbours);
1374 BufferCounts removed;
1375 for (
auto [fi, size] : relocatable) {
1376 const auto &fb = fifoBuffers[fi];
1377 int64_t bytes = std::max(fb.producerRawBytes, fb.consumerRawBytes);
1378 for (
TileID nbr : neighbours) {
1379 BufferCounts added = lent.lookup(nbr);
1380 added[bytes] += fb.sharedDepth;
1381 if (coreUnplaced(nbr, added) != 0)
1383 lent[nbr] = std::move(added);
1384 removed[bytes] += fb.sharedDepth;
1386 moves->push_back({fi, nbr});
1390 return coreUnplaced(pos, lent.lookup(pos), removed);
1393int SAPlacer::computeCoreOverflowPenalty(
1394 SmallVectorImpl<TileID> *charged)
const {
1398 DenseMap<TileID, BufferCounts> lent;
1399 for (
TileID tilePos : overflowingCoreTiles()) {
1400 int64_t unresolved = planCoreFit(tilePos, lent,
nullptr);
1401 if (unresolved <= 0)
1403 penalty += ((unresolved + 1023) / 1024) * config.memPenaltyPerKB;
1405 charged->push_back(tilePos);
1410SmallVector<std::pair<int, SmallVector<std::pair<TileID, bool>, 2>>>
1411SAPlacer::lockGroups()
const {
1412 SmallVector<std::pair<int, SmallVector<std::pair<TileID, bool>, 2>>> groups;
1413 auto add = [&](
const SmallVector<std::pair<TileID, bool>, 2> &users,
1414 int segments, int64_t depth) {
1416 groups.push_back({count, users});
1418 auto isCore = [](std::optional<AIETileType> type) {
1419 return type == AIETileType::CoreTile;
1423 auto endUsers = [&](
TileID at,
bool core, std::optional<AIETileType> type) {
1424 SmallVector<std::pair<TileID, bool>, 2> users;
1426 users.push_back({at,
false});
1427 users.push_back({at, isCore(type)});
1430 using LinkPool = FifoBufferInfo::LinkPool;
1431 for (
size_t index = 0; index < fifoBuffers.size(); ++index) {
1432 const FifoBufferInfo &fb = fifoBuffers[index];
1433 std::optional<TileID> prodPos = positionOf(fb.producerTile);
1436 auto heldLocks = [&](int64_t depth) {
1438 fb.producerCore, fb.rearmed);
1440 const FifoEndTypes &types = fifoEndTypes[index];
1441 std::optional<TileID> delegatePos = positionOf(fb.delegate);
1442 bool prodLinked = fb.producerLinkPool != LinkPool::None;
1443 if (
const std::optional<PlannedDmaEnd> &plan = fb.producerLinkPlan)
1444 add(endUsers(*prodPos, fb.producerCore, types.producer),
1445 fb.producerLinkSegments, plan->depth);
1446 bool prodPool =
false;
1447 for (
size_t ci = 0; ci < fb.consumerTiles.size(); ++ci) {
1448 std::optional<TileID> consPos = positionOf(fb.consumerTiles[ci]);
1451 bool consLinked = fb.consumerLinkPools[ci] != LinkPool::None;
1452 if (
const std::optional<PlannedDmaEnd> &plan = fb.consumerLinkPlans[ci])
1453 add(endUsers(*consPos, fb.consumerCore[ci], types.consumers[ci]),
1454 fb.consumerLinkSegments[ci], plan->depth);
1456 if (!fb.forcesDMA && ObjectFifoCreateOp::sharedMemoryOf(
1458 positionOf(fb.linkTile)) != SharedMemory::None) {
1459 if (prodLinked || consLinked || ci != 0 || !heldLocks(fb.sharedDepth))
1461 SmallVector<std::pair<TileID, bool>, 2> users;
1462 if (fb.producerCore)
1463 users.push_back({*prodPos,
false});
1464 if (fb.consumerCore[ci])
1465 users.push_back({*consPos,
false});
1466 add(users, 1, fb.sharedDepth);
1469 if (!prodPool && !prodLinked && !
isShimEndType(types.producer) &&
1470 !fb.linkSharedProd && fb.producerEnd) {
1472 if (heldLocks(fb.producerDepth))
1473 add(endUsers(*prodPos, fb.producerCore, types.producer), 1,
1477 fb.consumerEnds[ci] && !fb.unsynchronized)
1478 add(endUsers(*consPos, fb.consumerCore[ci], types.consumers[ci]), 1,
1479 fb.consumerDepths[ci]);
1482 for (
const InputLockGroup &group : inputLockGroups) {
1483 SmallVector<std::pair<TileID, bool>, 2> users;
1485 for (
auto [tile, localOnly] : group.users) {
1486 std::optional<TileID> at = positionOf(tile);
1487 placed &= at.has_value();
1489 users.push_back({*at, localOnly});
1492 groups.push_back({group.locks, users});
1497int SAPlacer::computeLockPenalty(
bool *stopped,
1498 SmallVectorImpl<TileID> *charged)
const {
1502 if (!positionsOverLocks)
1505 auto groups = lockGroups();
1506 SmallVector<TileID> positions;
1507 for (
auto &[op, at] : currentPlacement)
1508 positions.push_back(at);
1509 llvm::append_range(positions, placedTiles);
1511 return std::make_pair(a.col, a.row) < std::make_pair(b.col, b.row);
1513 positions.erase(llvm::unique(positions), positions.end());
1519 bool recording = !charged && lockVerdictMissRun < kLockVerdictMissRun;
1520 std::vector<int64_t> key;
1521 auto known = lockVerdicts.end();
1523 bool unanchored =
false;
1526 BitVector anchored(reached.size());
1527 SmallVector<TileID> anchors;
1528 for (
auto &[locks, users] : groups) {
1529 llvm::append_values(key, locks,
static_cast<int64_t
>(users.size()));
1530 for (
auto [at, localOnly] : users)
1531 llvm::append_values(key, at.col, at.row,
1532 static_cast<int64_t
>(localOnly));
1535 else if (
auto [first, localOnly] = users.front(); localOnly)
1536 reached.set(first.col * rows + first.row);
1537 else if (!anchored.test(first.col * rows + first.row)) {
1538 anchored.set(first.col * rows + first.row);
1539 anchors.push_back(first);
1542 for (
TileID anchor : anchors)
1543 for (
TileID at : lockReach.find(anchor)->second)
1544 reached.set(at.col * rows + at.row);
1546 for (
auto &[tile, locks] : fixedLocks) {
1547 std::optional<TileID> at = positionOf(tile);
1548 llvm::append_values(key, at ? at->col : -1, at ? at->row : -1, locks);
1550 llvm::append_values(key, -1,
static_cast<int64_t
>(positions.empty()));
1551 for (
TileID at : positions)
1552 if (unanchored || reached.test(at.col * rows + at.row))
1553 llvm::append_values(key, at.col, at.row);
1554 known = lockVerdicts.find(key);
1555 if (known != lockVerdicts.end()) {
1556 lockVerdictMissRun = 0;
1557#ifndef EXPENSIVE_CHECKS
1559 *stopped = known->second.second;
1560 return known->second.first;
1566 DenseMap<TileID, unsigned> index;
1567 auto tileAt = [&](
TileID at) {
1568 auto [entry, fresh] = index.try_emplace(at, 0);
1570 entry->second = plan.addTile({{at}, at});
1571 return entry->second;
1574 for (
auto &[tile, locks] : fixedLocks)
1575 if (std::optional<TileID> at = positionOf(tile))
1576 if (!plan.reserve(tileAt(*at), locks)) {
1577 penalty += locks * config.dmaPenaltyPerChannel;
1579 charged->push_back(*at);
1581 for (
auto &[at, locks] : placedLocks)
1582 if (!plan.reserve(tileAt(at), locks)) {
1583 penalty += locks * config.dmaPenaltyPerChannel;
1585 charged->push_back(at);
1587 SmallVector<unsigned> ranked;
1588 for (
TileID at : positions)
1589 ranked.push_back(tileAt(at));
1594 SmallVector<LockPlan::Group> planned;
1595 for (
auto &[locks, users] : groups) {
1596 SmallVector<LockPlan::User> records;
1597 for (
auto [at, localOnly] : users)
1598 records.push_back({tileAt(at), localOnly});
1599 auto reachesAt = [&](std::pair<TileID, bool> user,
TileID at) {
1600 return user.first == at ||
1602 llvm::is_contained(lockReach.find(user.first)->second, at));
1604 SmallVector<unsigned> eligible;
1605 if (users.empty()) {
1608 auto [first, localOnly] = users.front();
1609 for (
TileID at : localOnly ? ArrayRef<TileID>(first)
1610 : ArrayRef(lockReach.find(first)->second))
1611 if (index.contains(at) &&
1612 llvm::all_of(users, [&](
auto user) { return reachesAt(user, at); }))
1613 eligible.push_back(index.lookup(at));
1615#ifdef EXPENSIVE_CHECKS
1616 for (
unsigned tile : ranked)
1617 assert(llvm::is_contained(eligible, tile) ==
1618 llvm::all_of(records,
1619 [&](
const LockPlan::User &user) {
1620 return plan.reaches(user, tile);
1622 "a lock group's tiles differ from those every user reaches");
1624 planned.push_back({locks, std::move(eligible), std::move(records)});
1628 LockPlan::Assignment assignment =
1629 plan.assign(planned, &lockMemo,
false);
1631 *stopped = assignment.
stopped;
1632 for (
auto [group, tile, grouped] :
1633 llvm::zip(planned, assignment.
tiles, groups)) {
1636 penalty += group.count * config.dmaPenaltyPerChannel;
1638 for (
auto [at, localOnly] : grouped.second)
1639 charged->push_back(at);
1641#ifdef EXPENSIVE_CHECKS
1642 assert((known == lockVerdicts.end() ||
1643 known->second == std::pair(penalty, assignment.
stopped)) &&
1644 "a recorded lock verdict differs from a fresh one");
1646 if (recording && known == lockVerdicts.end()) {
1647 if (++lockVerdictMissRun == kLockVerdictMissRun) {
1648 decltype(lockVerdicts)().swap(lockVerdicts);
1649 lockVerdictBytes = 0;
1653 key.shrink_to_fit();
1654 size_t bytes = key.capacity() *
sizeof(int64_t);
1655 if (lockVerdictBytes + bytes > kLockVerdictBytes) {
1656 lockVerdicts.clear();
1657 lockVerdictBytes = 0;
1659 lockVerdictBytes += bytes;
1660 lockVerdicts.emplace(std::move(key),
1661 std::pair(penalty, assignment.
stopped));
1666void SAPlacer::replanLinks(ArrayRef<std::pair<unsigned, int64_t>> depths) {
1667 auto at = [
this](Value tile) {
return positionOf(tile.getDefiningOp()); };
1668 SmallVector<unsigned> changed;
1669 for (
auto [index, depth] : depths) {
1670 VariableLink &variable = variableLinks[index];
1671 if (depth == variable.depth)
1673 variable.depth = depth;
1674 changed.push_back(index);
1676 if (changed.empty())
1679 std::vector<int64_t> all;
1680 for (
const VariableLink &variable : variableLinks)
1681 all.push_back(variable.depth);
1682 for (
unsigned index : changed) {
1683 VariableLink &variable = variableLinks[index];
1684 auto [replan, added] = variable.replans.try_emplace(all);
1688 for (
size_t fifoIndex : variable.fifos) {
1689 FifoBufferInfo &fb = fifoBuffers[fifoIndex];
1690 auto fifo = cast<ObjectFifoCreateOp>(fb.fifoOp);
1691 auto &ends = replan->second.ends.emplace_back();
1692 for (
unsigned ci = 0, e = fb.consumerEnds.size(); ci < e; ++ci)
1693 ends.push_back(fifo.plannedDmaEnd(ci, at));
1694 ends.push_back(fifo.plannedDmaEnd(std::nullopt, at));
1695 for (
const std::optional<PlannedDmaEnd> &end : ends)
1696 if (!replan->second.held && end &&
1697 end->pool == variable.link.getOperation())
1698 replan->second.held = end;
1701 for (
auto [fifoIndex, ends] :
1702 llvm::zip_equal(variable.fifos, replan->second.ends)) {
1703 FifoBufferInfo &fb = fifoBuffers[fifoIndex];
1704 auto install = [&](std::optional<PlannedDmaEnd> &end,
1705 const std::optional<PlannedDmaEnd> &plan,
1706 std::optional<unsigned> entry, Operation *tile) {
1709 memTileEnds.find(tile)->second[*entry].end = *end;
1711 for (
unsigned ci = 0, e = fb.consumerEnds.size(); ci < e; ++ci)
1712 install(fb.consumerEnds[ci], ends[ci], fb.consumerMemTileEntries[ci],
1713 fb.consumerTiles[ci]);
1714 install(fb.producerEnd, ends.back(), fb.producerMemTileEntry,
1717 for (
auto [fifoIndex, consumer] : variable.holds) {
1718 FifoBufferInfo &fb = fifoBuffers[fifoIndex];
1719 (consumer ? fb.consumerLinkPlans[*consumer] : fb.producerLinkPlan) =
1720 replan->second.held;
1725int SAPlacer::computeTileDMAPenalty(
TileID tilePos,
int *bdIds)
const {
1726 auto usage = currentDMAUsage.lookup(tilePos);
1728 SmallVector<Operation *> tilesHere;
1730 for (Operation *tile : overlayTiles)
1731 if (positionOf(tile) == tilePos)
1732 tilesHere.push_back(tile);
1735 int used[2] = {usage.first, usage.second + overlay.channels};
1736 int max[2] = {maxIn, maxOut};
1740 (pinUse.clashes(tilePos) + !overlay.fits) * config.dmaPenaltyPerChannel;
1741 for (
int dir : {0, 1}) {
1742 if (used[dir] <= max[dir])
1745 AIETileType::ShimNOCTile) {
1746 SmallVector<const ShimSide *> sides;
1748 if (positionOf(lt) == tilePos)
1749 sides.push_back(&own[dir]);
1751 SmallVector<StringAttr> extra;
1752 if (dir == 1 && overlay.own)
1753 extra.push_back(
shimSpans->overlayEnd(tilePos.col));
1755 pinUse.channelsAt(tilePos, dir == 1));
1757 penalty += std::max(0, used[dir] - max[dir]) * config.dmaPenaltyPerChannel;
1759 int ids = runtimeBdAt.lookup(tilePos);
1766void SAPlacer::chargeRuntimeBds(
TileID pos) {
1767 if (
targetModel->getTileType(pos.col, pos.row) != AIETileType::ShimNOCTile)
1769 SmallVector<Operation *> onTile;
1771 if (
auto at = currentPlacement.find(lt);
1772 at != currentPlacement.end() && at->second == pos)
1773 onTile.push_back(lt);
1775 runtimeBdIds.shortfall(onTile, pos) * config.dmaPenaltyPerChannel;
1778int SAPlacer::computeDMAChannelPenalty() {
1779 dmaPenaltyAt.clear();
1781 for (
auto &[tilePos, _] : currentDMAUsage) {
1782 int at = computeTileDMAPenalty(tilePos);
1783 dmaPenaltyAt[tilePos] = at;
1789SmallVector<Operation *> SAPlacer::memTilesAt(
TileID position)
const {
1790 SmallVector<Operation *> tiles;
1791 for (
auto &[tile, ends] : memTileEnds)
1792 if (positionOf(tile) == position)
1793 tiles.push_back(tile);
1797int64_t SAPlacer::bdShortfall(
TileID position, ArrayRef<Operation *> tiles,
1799 SmallVector<int64_t> *walkBytes) {
1800 auto [layout, added] = bdLayoutOf.try_emplace(position, position);
1802 auto access = [&](
TileID at) {
1803 std::vector<bool> bits;
1804 int channels =
targetModel->getNumSourceSwitchboxConnections(
1805 at.col, at.row, WireBundle::DMA);
1806 for (
int channel = 0; channel < channels; ++channel)
1807 for (uint32_t bd = 0, e =
targetModel->getNumBDs(at.col, at.row);
1810 targetModel->isBdChannelAccessible(at.col, at.row, bd, channel));
1813 for (
auto &[other, rep] : bdLayoutOf)
1814 if (other == rep && !(other == position) &&
1815 access(other) == access(position)) {
1816 layout->second = other;
1824 SmallVector<Operation *> holders(tiles);
1825 for (Operation *tile : logicalMemTiles)
1826 if (
auto at = currentPlacement.find(tile);
1827 at != currentPlacement.end() && at->second == position &&
1828 !llvm::is_contained(holders, tile))
1829 holders.push_back(tile);
1830 for (Operation *tile : physicalTiles.lookup(position))
1831 if (!llvm::is_contained(holders, tile))
1832 holders.push_back(tile);
1833 std::vector<uintptr_t> key = {
static_cast<uintptr_t
>(layout->second.col),
1834 static_cast<uintptr_t
>(layout->second.row),
1836 for (Operation *tile : holders)
1837 key.push_back(
reinterpret_cast<uintptr_t
>(tile));
1838 for (
const VariableLink &variable : variableLinks)
1839 key.push_back(
static_cast<uintptr_t
>(variable.depth));
1840 if (
const BDShortfall *cached = bdShortfallOf.find(key)) {
1842 *walkSets = cached->sets;
1844 *walkBytes = cached->bytes;
1847 SmallVector<const MemTileEnd *> ends;
1848 for (Operation *tile : tiles)
1849 if (
auto *it = memTileEnds.find(tile); it != memTileEnds.end())
1850 for (
const MemTileEnd &end : it->second)
1851 ends.push_back(&end);
1852 auto [col, row] = position;
1854 static_cast<int>(
targetModel->getNumDestSwitchboxConnections(
1855 col, row, WireBundle::DMA)),
1856 static_cast<int>(
targetModel->getNumSourceSwitchboxConnections(
1857 col, row, WireBundle::DMA))};
1859 SmallVector<std::optional<bool>> freeChannels[2];
1860 for (SmallVector<std::optional<bool>> &known : freeChannels)
1861 known.resize(std::max(channels[0], channels[1]));
1862 auto free = [&](DMAChannelDir dir,
int channel) {
1863 std::optional<bool> &known =
1864 freeChannels[dir == DMAChannelDir::MM2S][channel];
1866 known = llvm::all_of(holders, [&](Operation *tile) {
1867 return channelAnalysis->isChannelFree(cast<TileLike>(tile), dir,
1872 DenseMap<int, int64_t> taken = takenBDs.at(*
targetModel, col, row, holders);
1873 auto spent = [&](
int channel) {
return taken.lookup(channel); };
1874 SmallVector<DMAChannelAnalysis::BDPlanEnd> planned;
1875 SmallVector<unsigned> poolOf;
1876 SmallVector<DMAChannelAnalysis::BDWalkPool> pools;
1877 SmallVector<std::pair<Operation *, int>> poolKeys;
1878 for (
const MemTileEnd *end : ends) {
1879 std::pair<Operation *, int> poolKey{end->end.pool, end->end.id};
1880 auto *at = llvm::find(poolKeys, poolKey);
1881 if (at == poolKeys.end()) {
1882 poolKeys.push_back(poolKey);
1883 pools.push_back({end->end.depth, end->end.objectBytes,
false});
1884 at = std::prev(poolKeys.end());
1886 unsigned pool = at - poolKeys.begin();
1887 pools[pool].walkable |= end->end.walkable;
1888 poolOf.push_back(pool);
1889 planned.push_back({end->dir, end->end.bds,
1890 channels[end->dir == DMAChannelDir::MM2S],
1895 *
targetModel, col, row, planned, poolOf, pools, free, spent,
1898 for (ArrayRef<unsigned> set : found.
sets)
1899 sets.push_back(llvm::map_to_vector(
1900 set, [&](
unsigned pool) {
return poolKeys[pool]; }));
1901 SmallVector<int64_t> bytes = found.
bytes;
1902 int64_t shortfall = 0;
1907 sets.emplace_back();
1909 for (
auto [pool, walkable] : llvm::enumerate(pools))
1910 if (walkable.walkable) {
1911 sets.back().push_back(poolKeys[pool]);
1912 bytes.back() += walkable.depth * walkable.objectBytes;
1915 DenseSet<std::pair<Operation *, int>> whole;
1917 whole.insert(sets.front().begin(), sets.front().end());
1919 for (
auto [end, pool] : llvm::zip_equal(planned, poolOf))
1920 total += whole.contains(poolKeys[pool]) ? 1 : end.bds;
1921 for (
auto [channel, held] : taken)
1924 shortfall = found.
channelShort ? std::max<int64_t>(0, total - ids)
1925 : std::max<int64_t>(1, total - ids);
1927 bdShortfallOf.record(std::move(key), {shortfall, sets, bytes});
1929 *walkSets = std::move(sets);
1931 *walkBytes = std::move(bytes);
1936int SAPlacer::computeBDCountPenalty() {
1937 bdShortfallAt.clear();
1938 int64_t penalty = 0;
1939 for (
auto &[tile, ends] : memTileEnds) {
1940 std::optional<TileID> at = positionOf(tile);
1941 if (!at || bdShortfallAt.contains(*at))
1943 int64_t shortfall = bdShortfall(*at, memTilesAt(*at));
1944 bdShortfallAt[*at] = shortfall;
1945 penalty += shortfall * config.dmaPenaltyPerChannel;
1947 return static_cast<int>(penalty);
1950int SAPlacer::computeAdjacencyPenalty(
1951 const Adjacency &adj, ArrayRef<std::pair<int, int>> validOffsets,
1952 int weight, SmallVectorImpl<TileID> *charged)
const {
1954 for (
auto [first, second] : adj.edges) {
1955 auto firstIt = currentPlacement.find(first.getOperation());
1956 auto secondIt = currentPlacement.find(second.getOperation());
1957 if (firstIt == currentPlacement.end() || secondIt == currentPlacement.end())
1960 TileID firstPos = firstIt->second;
1961 TileID secondPos = secondIt->second;
1964 int minDist = INT_MAX;
1965 for (
auto [dc, dr] : validOffsets) {
1966 int dist = std::abs(secondPos.col - (firstPos.col + dc)) +
1967 std::abs(secondPos.row - (firstPos.row + dr));
1968 minDist = std::min(minDist, dist);
1972 penalty += weight * minDist;
1974 charged->append({firstPos, secondPos});
1979int SAPlacer::computePairingPenalty(SmallVectorImpl<TileID> *charged)
const {
1981 computeAdjacencyPenalty(cascadeAdjacency,
targetModel->getCascadeSteps(),
1982 config.cascadeWeightPerDist, charged);
1983 for (
auto [first, second] : sharedMemAdjacency.edges) {
1984 auto firstIt = currentPlacement.find(first.getOperation());
1985 auto secondIt = currentPlacement.find(second.getOperation());
1986 if (firstIt == currentPlacement.end() || secondIt == currentPlacement.end())
1988 TileID a = firstIt->second, b = secondIt->second;
1989 if (a == b ||
targetModel->isLegalMemAffinity(a.col, a.row, b.col, b.row) ||
1990 targetModel->isLegalMemAffinity(b.col, b.row, a.col, a.row))
1992 int distance = std::abs(a.col - b.col) + std::abs(a.row - b.row);
1993 penalty += config.sharedMemWeightPerDist * std::max(1, distance - 1);
1995 charged->append({a, b});
2000void SAPlacer::generateAllocates() {
2001 DenseSet<size_t> emittedFifoIndices;
2004 DenseMap<TileID, BufferCounts> lent;
2005 for (
TileID tilePos : overflowingCoreTiles()) {
2006 SmallVector<std::pair<size_t, TileID>> moves;
2007 (void)planCoreFit(tilePos, lent, &moves);
2008 for (
auto [fifoIdx, nbrPos] : moves) {
2009 if (!emittedFifoIndices.insert(fifoIdx).second)
2011 const auto &fb = fifoBuffers[fifoIdx];
2012 currentMemUsage[nbrPos] +=
2013 std::max(fb.producerSizeBytes, fb.consumerSizeBytes) * fb.sharedDepth;
2014 allocates.push_back({fb.fifoOp, nbrPos});
2021 for (
auto &[fifoIdx, destTile] : sharedMemDestination) {
2022 if (emittedFifoIndices.contains(fifoIdx))
2024 const auto &fb = fifoBuffers[fifoIdx];
2025 std::optional<TileID> prodPos = positionOf(fb.producerTile);
2026 std::optional<TileID> consPos = positionOf(fb.consumerTiles[0]);
2027 if (!prodPos || !consPos || *prodPos == *consPos)
2029 if (destTile != *prodPos)
2030 allocates.push_back({fb.fifoOp, destTile});
2034int SAPlacer::updateResourcePenalty(
2035 const SmallVector<std::pair<Operation *, TileID>> &oldPlacements) {
2037 DenseSet<size_t> affectedFifos;
2038 for (
auto &[op, _] : oldPlacements) {
2039 auto it = tileToFifoIndices.find(op);
2040 if (it != tileToFifoIndices.end())
2041 for (
size_t idx : it->second)
2042 affectedFifos.insert(idx);
2046 replannedLinks.clear();
2047 auto at = [
this](Value tile) {
return positionOf(tile.getDefiningOp()); };
2048 for (
unsigned index = 0, e = variableLinks.size(); index < e; ++index) {
2049 const VariableLink &variable = variableLinks[index];
2050 if (llvm::none_of(oldPlacements, [&](
const auto &moved) {
2051 return llvm::is_contained(variable.tiles, moved.first);
2054 int64_t depth = variable.plan.depthAt(*
targetModel, at);
2055 if (depth == variable.depth)
2057 replannedLinks.push_back({index, variable.depth, depth});
2058 affectedFifos.insert(variable.fifos.begin(), variable.fifos.end());
2062 for (
auto &[op, oldPos] : oldPlacements) {
2063 auto bufIt = staticBufferSizes.find(op);
2064 if (bufIt != staticBufferSizes.end())
2065 currentMemUsage[oldPos] -= bufIt->second;
2066 auto stackIt = stackSizes.find(op);
2067 if (stackIt != stackSizes.end())
2068 currentMemUsage[oldPos] -= stackIt->second;
2074 SmallVector<std::pair<Operation *, TileID>, 3> savedPositions;
2075 for (
auto &[op, oldPos] : oldPlacements) {
2076 TileID &pos = currentPlacement[op];
2077 savedPositions.push_back({op, pos});
2080 for (
size_t fi : affectedFifos)
2081 addFifoContribution(fi, -1);
2082 SetVector<unsigned> movedNets;
2083 for (
auto &[op, _] : oldPlacements)
2085 movedNets.insert_range(nets->second);
2086 for (
unsigned net : movedNets) {
2087 auto stream = netStreams.find(net);
2088 cuts.add(stream->second.first, stream->second.second,
2091 for (
auto &[op, _] : oldPlacements) {
2092 for (
size_t ei : tileToRouteEnds.lookup(op))
2093 addRouteEndContribution(ei, -1);
2094 for (
const DMAChannelAnalysis::ChannelClaim &claim :
claimsOf.lookup(op)) {
2095 pinUse.claim(currentPlacement[op], claim, -1);
2096 claimLog.push_back({currentPlacement[op], claim, -1});
2101 for (
auto &[op, newPos] : savedPositions)
2102 currentPlacement[op] = newPos;
2103 replanLinks(llvm::map_to_vector(replannedLinks, [](ReplannedLink replanned) {
2104 return std::make_pair(replanned.index, replanned.to);
2106 for (
size_t fi : affectedFifos)
2107 addFifoContribution(fi, +1);
2108 auto placed = [
this](Operation *op) {
return positionOf(op); };
2109 for (
unsigned net : movedNets) {
2110 auto &[src, dsts] = netStreams[net];
2112 cuts.add(src, dsts,
streamNets[net].packet, 1);
2114 streamCutPenalty = config.streamCutPenaltyPerChannel * cuts.over();
2115 for (
auto &[op, oldPos] : oldPlacements) {
2116 chargeStreams(op, oldPos, -1);
2117 chargeStreams(op, currentPlacement[op], 1);
2120 SmallVector<TileID, 4> changed;
2121 for (
auto &[op, oldPos] : oldPlacements)
2123 changed.append({oldPos, currentPlacement[op]});
2124 llvm::sort(changed);
2125 changed.erase(llvm::unique(changed), changed.end());
2126 for (
TileID at : changed)
2127 coresChanged -= coresChangedAt(at);
2128 for (
auto &[op, oldPos] : oldPlacements)
2131 for (
auto &[op, oldPos] : oldPlacements)
2132 if (
unsigned key =
coreKeys.lookup(op))
2133 keyAt[currentPlacement[op]] = key;
2134 for (
TileID at : changed)
2135 coresChanged += coresChangedAt(at);
2137 SmallVector<unsigned> ddrMoved;
2138 for (
auto &[op, _] : oldPlacements)
2140 llvm::append_range(ddrMoved, it->second);
2141 if (!ddrMoved.empty()) {
2142 llvm::sort(ddrMoved);
2143 ddrMoved.erase(llvm::unique(ddrMoved), ddrMoved.end());
2144 auto columnOf = [
this](Operation *op) -> std::optional<int> {
2145 std::optional<TileID> at = positionOf(op);
2146 return at ? std::optional(at->col) : std::nullopt;
2148 for (
unsigned index : ddrMoved) {
2151 int64_t &at = ddrScoreOf[index];
2152 ddrTotal += score - at;
2155 ddrPenalty =
static_cast<int>(ddrTotal);
2157 for (
auto &[op, _] : oldPlacements) {
2158 for (
size_t ei : tileToRouteEnds.lookup(op))
2159 addRouteEndContribution(ei, +1);
2160 for (
const DMAChannelAnalysis::ChannelClaim &claim :
claimsOf.lookup(op)) {
2161 pinUse.claim(currentPlacement[op], claim, 1);
2162 claimLog.push_back({currentPlacement[op], claim, 1});
2166 for (
auto &[op, oldPos] : oldPlacements)
2167 if (
int locks = homeLocks.lookup(op)) {
2168 addLockDemand(oldPos, -locks);
2169 addLockDemand(currentPlacement[op], locks);
2173 for (
auto &[op, _] : oldPlacements) {
2174 TileID newPos = currentPlacement[op];
2175 auto bufIt = staticBufferSizes.find(op);
2176 if (bufIt != staticBufferSizes.end())
2177 currentMemUsage[newPos] += bufIt->second;
2178 auto stackIt = stackSizes.find(op);
2179 if (stackIt != stackSizes.end())
2180 currentMemUsage[newPos] += stackIt->second;
2182 for (
auto &[op, oldPos] : oldPlacements)
2183 if (coreContents.count(op)) {
2184 coreDirty.insert(oldPos);
2185 coreDirty.insert(currentPlacement[op]);
2189 if (SmallVector<TileID> coreChanged = refreshCoreUnplaced();
2190 !coreChanged.empty()) {
2191 SmallVector<TileID> overflowing = overflowingCoreTiles();
2192 DenseSet<TileID> overflowReads = coreOverflowReads();
2193 if (overflowing != coreOverflowTiles ||
2194 llvm::any_of(coreChanged,
2195 [&](
TileID pos) {
return overflowReads.contains(pos); })) {
2196 coreOverflowTiles = std::move(overflowing);
2197 coreOverflowPenalty = computeCoreOverflowPenalty();
2201 auto reads = [&](
const DenseSet<Operation *> &tiles) {
2202 return llvm::any_of(oldPlacements, [&](
const auto &moved) {
2203 return tiles.contains(moved.first);
2206 if (reads(spillTiles) || !replannedLinks.empty())
2207 memSpilloverPenalty = computeMemSpilloverPenalty();
2208 SmallVector<TileID> bdTouched;
2209 for (ReplannedLink replanned : replannedLinks)
2210 if (std::optional<TileID> pos =
2211 positionOf(variableLinks[replanned.index].tiles.front());
2213 targetModel->getTileType(pos->col, pos->row) == AIETileType::MemTile)
2214 bdTouched.push_back(*pos);
2215 for (
auto &[op, oldPos] : oldPlacements)
2216 if (memTileEnds.count(op) || llvm::is_contained(logicalMemTiles, op))
2217 for (
TileID pos : {oldPos, currentPlacement[op]})
2218 if (!llvm::is_contained(bdTouched, pos))
2219 bdTouched.push_back(pos);
2220 for (
TileID pos : bdTouched) {
2221 int64_t &at = bdShortfallAt[pos];
2222 bdCountPenalty -=
static_cast<int>(at * config.dmaPenaltyPerChannel);
2223 at = bdShortfall(pos, memTilesAt(pos));
2224 bdCountPenalty +=
static_cast<int>(at * config.dmaPenaltyPerChannel);
2226 if (reads(delegateTermTiles))
2227 delegatePenalty = computeDelegatePenalty();
2231 llvm::SmallDenseSet<TileID, 16> dmaTouched;
2232 for (
auto &[op, oldPos] : oldPlacements) {
2233 dmaTouched.insert(oldPos);
2234 dmaTouched.insert(currentPlacement[op]);
2236 for (
size_t fi : affectedFifos) {
2237 const auto &fb = fifoBuffers[fi];
2238 SmallVector<Operation *, 4> ends = {fb.producer};
2239 llvm::append_range(ends, fb.consumers);
2240 for (Operation *end : ends)
2241 if (
auto it = currentPlacement.find(end); it != currentPlacement.end())
2242 dmaTouched.insert(it->second);
2244 for (
auto &[op, oldPos] : oldPlacements)
2246 for (
TileID pos : {oldPos, currentPlacement[op]})
2247 chargeRuntimeBds(pos);
2248 for (
TileID tile : dmaTouched) {
2249 int &at = dmaPenaltyAt[tile];
2250 int now = computeTileDMAPenalty(tile);
2251 dmaPenalty += now - at;
2255 cachedResourcePenalty = memSpilloverPenalty + coreOverflowPenalty +
2256 computeLockPenalty() + dmaPenalty + bdCountPenalty +
2257 delegatePenalty + streamCutPenalty;
2258 return cachedResourcePenalty;
2265bool SAPlacer::generateMove(
2266 SmallVector<std::pair<Operation *, TileID>> &moves) {
2267 if (movableTiles.empty())
2270 for (
int attempt = 0; attempt < config.maxMoveAttempts; attempt++) {
2272 Operation *tile = movableTiles[drawBoundedIndex(rng, movableTiles.size())];
2274 auto typeIt = tileTypes.find(tile);
2275 if (typeIt == tileTypes.end())
2277 AIETileType type = typeIt->second;
2280 const auto &candidates = (type == AIETileType::CoreTile)
2283 if (candidates.empty())
2286 TileID targetPos = candidates[drawBoundedIndex(rng, candidates.size())];
2289 if (type != AIETileType::CoreTile &&
2290 targetModel->getTileType(targetPos.col, targetPos.row) != type)
2293 TileID currentPos = currentPlacement[tile];
2294 if (targetPos == currentPos)
2301 Operation *occupant =
nullptr;
2302 for (
auto *t : movableTiles) {
2303 if (t != tile && currentPlacement[t] == targetPos) {
2313 (type != AIETileType::CoreTile && drawBoundedIndex(rng, 2) == 0)) {
2314 if (!isLegalPosition(tile, targetPos))
2317 moves.push_back({tile, targetPos});
2320 if (tileTypes[occupant] != type)
2323 namedClash(tile, namedAt(tile, targetPos, occupant)) ||
2324 namedClash(occupant, namedAt(occupant, currentPos, tile)))
2327 moves.push_back({tile, targetPos});
2328 moves.push_back({occupant, currentPos});
2339double SAPlacer::estimateInitialTemperature(
int numSamples) {
2341 std::vector<double> deltaCosts;
2342 deltaCosts.reserve(numSamples);
2344 SmallVector<std::pair<size_t, NetBoundingBox>> backups;
2346 for (
int i = 0; i < numSamples; i++) {
2347 SmallVector<std::pair<Operation *, TileID>> moves;
2348 if (!generateMove(moves))
2352 int delta = evaluateMove(moves[0].first, moves[0].second, backups);
2353 deltaCosts.push_back(delta);
2354 revertMove(backups);
2357 if (deltaCosts.empty())
2363 double maxDelta = 0.0;
2364 for (
double d : deltaCosts)
2365 maxDelta = std::max(maxDelta, std::abs(d));
2367 if (maxDelta == 0.0)
2370 auto getExpectedValue = [&](
double T) ->
double {
2372 for (
double d : deltaCosts) {
2376 ev += d * std::exp(-d / T);
2382 double highT = config.tempSearchCeiling * maxDelta;
2385 for (
int iter = 0; iter < config.tempSearchIters; iter++) {
2386 double ev = getExpectedValue(T);
2387 if (std::abs(highT - lowT) / std::max(T, config.tempSearchEpsilon) <
2388 config.tempSearchTolerance)
2399 T = (lowT + highT) / 2.0;
2409int64_t SAPlacer::computeTileMemoryWeight(Operation *tile)
const {
2413 auto bufIt = staticBufferSizes.find(tile);
2414 if (bufIt != staticBufferSizes.end())
2415 weight += bufIt->second;
2418 auto stackIt = stackSizes.find(tile);
2419 if (stackIt != stackSizes.end())
2420 weight += stackIt->second;
2423 for (
const auto &fb : fifoBuffers) {
2424 bool isProd = (fb.producer == tile);
2426 for (
size_t ci = 0; ci < fb.consumers.size(); ci++) {
2427 if (fb.consumers[ci] == tile) {
2428 consIdx =
static_cast<int>(ci);
2432 if (!isProd && consIdx < 0)
2435 if (isProd && consIdx >= 0) {
2437 std::max(fb.producerSizeBytes, fb.consumerSizeBytes) * fb.sharedDepth;
2438 }
else if (isProd) {
2439 weight += fb.producerSizeBytes * fb.producerDepth;
2441 weight += fb.consumerSizeBytes * fb.consumerDepths[consIdx];
2452 startTime = std::chrono::steady_clock::now();
2456 rng.seed(std::random_device{}());
2462 if (failed(collectAndBuildModel(device)))
2465 if (failed(generateInitialPlacement()))
2468 initializeSAState();
2472 return finalizePlacement(device);
2475LogicalResult SAPlacer::collectAndBuildModel(DeviceOp device) {
2482 if (logicalTiles.empty())
2486 for (
auto lt : logicalTiles)
2487 tileTypes[lt.getOperation()] = lt.getTileType();
2490 device.walk([&](BufferOp bufOp) {
2491 auto tile = dyn_cast_or_null<TileLike>(bufOp.getTile().getDefiningOp());
2494 int64_t bytes = bufOp.getAllocationSize();
2495 if (tile.getTileType() == AIETileType::MemTile)
2496 memTileFixed[tile].push_back(
2500 bufOp.getAddress()});
2503 staticBufferSizes[tile] +=
2506 if (tile.getTileType() == AIETileType::CoreTile)
2512 for (
auto pool : device.getOps<ObjectFifoPoolOp>()) {
2513 auto tile = dyn_cast_or_null<TileLike>(pool.getTile().getDefiningOp());
2514 if (!tile || tile.getTileType() != AIETileType::CoreTile ||
2518 buffer.
size = pool.getObjectSizeInBytes() * pool.getObjectsPerBuffer();
2523 for (
int i = 0, e = pool.getContiguous() ? 1 : pool.getDepth(); i < e; ++i)
2524 coreContents[tile].buffers.push_back(buffer);
2527 for (LogicalTileOp tile : logicalTiles)
2528 for (Operation *user : tile->getUsers())
2529 if (isa<LockOp>(user))
2531 device.walk([&](LockOp lock) {
2532 if (
auto placed = dyn_cast_or_null<TileOp>(lock.getTile().getDefiningOp()))
2533 ++placedLocks[placed.getTileID()];
2535 for (
auto tile : device.getOps<TileOp>())
2536 placedTiles.push_back(tile.getTileID());
2537 llvm::StringMap<Operation *> fifoNamed;
2538 for (ObjectFifoCreateOp fifo : collected.objectFifos)
2539 fifoNamed[fifo.getSymName()] = fifo;
2540 firstAcquire.clear();
2541 device.walk([&](ObjectFifoAcquireOp acquire) {
2542 if (Operation *fifo = fifoNamed.lookup(acquire.getObjFifoName()))
2543 firstAcquire.try_emplace(fifo, firstAcquire.size());
2546 for (
int col = 0; col <
targetModel->columns(); ++col)
2547 for (
int row = 0; row <
targetModel->rows(); ++row) {
2549 SmallVector<TileID> &reach = lockReach[user];
2555 reach.push_back(at);
2558 PoolLocks poolLocks(device);
2559 for (
auto pool : device.getOps<ObjectFifoPoolOp>()) {
2560 if (!poolLocks.needsLocks(pool))
2562 SmallVector<Operation *> owners =
2564 SmallVector<int> counts =
2566 for (
auto [index, entry] : llvm::enumerate(owners)) {
2567 Operation *owner = entry;
2568 InputLockGroup &group = inputLockGroups.emplace_back();
2569 group.home = pool.getTile().getDefiningOp();
2570 group.locks = counts[index];
2572 auto addUser = [&](Operation *endpoint,
auto selected,
bool dma) {
2573 if (owner != pool && !llvm::is_contained(selected, owner))
2575 auto *tile = endpoint->getOperand(0).getDefiningOp();
2576 group.users.push_back(
2578 cast<TileLike>(tile).getTileType())});
2580 for (
auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>())
2581 if (endpoint.getPoolOp() == pool)
2582 addUser(endpoint, endpoint.getSelectedSegments(),
false);
2583 for (
auto endpoint : device.getOps<ObjectFifoDmaEndpointOp>())
2584 if (endpoint.getPoolOp() == pool)
2585 addUser(endpoint, endpoint.getSelectedSegments(),
true);
2591 for (
auto [ordinal, coreOp] : llvm::enumerate(device.getOps<CoreOp>())) {
2592 auto *tileOp = coreOp.getTile().getDefiningOp();
2593 if (!isa_and_nonnull<TileLike>(tileOp))
2597 int64_t bytes = alignedBufferBytes(*
targetModel, AIETileType::CoreTile,
2598 coreOp.getEffectiveStackSize());
2599 CoreTileContents &contents = coreContents[tileOp];
2600 contents.hasCore =
true;
2601 contents.stackRun = coreOp.getStackRun();
2602 std::optional<uint32_t> stackBank = coreOp.getStackBank();
2603 if (!coreOp.getStackAddress() && stackBank) {
2604 contents.stackBank =
static_cast<int>(*stackBank);
2605 contents.stackAlignBytes =
targetModel->getCoreStackAlignment();
2607 SmallVector<CoreSectionReservation> reservations =
2608 coreOp.getSectionReservations();
2609 if (!coreOp.getDataSize() && !coreOp.getMeasuredDataSize())
2610 if (
auto charge = config.coreDataCharges.find(ordinal);
2611 charge != config.coreDataCharges.end() && charge->second.bytes)
2613 charge->second.bytes, 0,
2614 charge->second.alignBytes});
2615 for (
auto [held, holder] : llvm::zip_equal(
2616 reservations, coreOp.getSectionReservationBuffers(reservations)))
2620 contents.buffers.push_back(buffer);
2622 stackSizes[tileOp] = bytes;
2626 buildNetModel(objectFifos, objectFifoLinks);
2627 buildFifoBufferInfo(device, objectFifos, objectFifoLinks);
2630 if (pinnedRule.failed())
2632 llvm::ArrayRef<DMAChannelAnalysis::ChannelClaim> claims =
2633 channelAnalysis.emplace(device).getChannelClaims();
2634 buildRouteModel(device, collected.flows, collected.pktFlows, collected.routes,
2638 takenBDs = DMAChannelAnalysis::TakenBDs(device);
2639 logicalMemTiles.clear();
2640 for (
auto tile : device.getOps<LogicalTileOp>())
2641 if (tile.getTileType() == AIETileType::MemTile)
2642 logicalMemTiles.push_back(tile);
2643 physicalTiles.clear();
2644 for (TileOp tile : device.getOps<TileOp>())
2645 physicalTiles[{tile.getCol(), tile.getRow()}].push_back(tile);
2647 LLVM_DEBUG(llvm::dbgs() <<
"[SA] Cascade adjacency: "
2648 << cascadeAdjacency.edges.size() <<
" edges\n");
2649 for (ObjectFifoCreateOp fifo : objectFifos)
2650 if (fifo.forcesSharedMemory() && fifo.getConsumerTiles().size() == 1)
2651 sharedMemAdjacency.addEdgeFromValues(fifo.getProducerTile(),
2652 fifo.getConsumerTiles()[0]);
2656 chargedPools.clear();
2657 for (
auto &[tile, ends] : memTileEnds)
2658 for (
const MemTileEnd &end : ends) {
2659 std::optional<StringRef> fifo;
2660 if (
auto create = dyn_cast_or_null<ObjectFifoCreateOp>(end.end.pool))
2661 fifo = create.name().getValue();
2662 else if (
auto link = dyn_cast_or_null<ObjectFifoLinkOp>(end.end.pool))
2663 fifo = link.getPoolOwner().name().getValue();
2664 else if (
auto pool = dyn_cast_or_null<ObjectFifoPoolOp>(end.end.pool))
2665 fifo = pool.getFifoName();
2666 if (fifo && llvm::is_contained(config.walkedFifos, *fifo))
2667 chargedPools.insert(end.end.pool);
2673void SAPlacer::buildFifoBufferInfo(DeviceOp device,
2674 ArrayRef<ObjectFifoCreateOp> objectFifos,
2675 ArrayRef<ObjectFifoLinkOp> objectFifoLinks) {
2676 mlir::DataLayout dataLayout(device->getParentOfType<ModuleOp>());
2678 memTileEnds.clear();
2679 PoolLocks poolLocks(device);
2680 llvm::StringMap<Operation *> delegates;
2681 for (
auto alloc : device.getOps<ObjectFifoAllocateOp>())
2682 delegates[alloc.getObjFifoName()] = alloc.getDelegateTile().getDefiningOp();
2684 for (
auto ofOp : objectFifos) {
2686 fb.fifoOp = ofOp.getOperation();
2687 fb.delegate = delegates.lookup(ofOp.getSymName());
2690 auto *prodOp = ofOp.getProducerTile().getDefiningOp();
2691 fb.producer = (isa_and_nonnull<LogicalTileOp>(prodOp)) ? prodOp : nullptr;
2692 fb.producerTile = prodOp;
2695 for (Value ct : ofOp.getConsumerTiles()) {
2696 auto *consOp = ct.getDefiningOp();
2697 fb.consumers.push_back(isa_and_nonnull<LogicalTileOp>(consOp) ? consOp
2699 fb.consumerTiles.push_back(consOp);
2703 auto fifoType = llvm::cast<AIEObjectFifoType>(ofOp.getElemType());
2704 auto elemType = llvm::cast<MemRefType>(fifoType.getElementType());
2706 auto prodLike = dyn_cast_or_null<TileLike>(prodOp);
2707 AIETileType prodType =
2708 prodLike ? prodLike.getTileType() : AIETileType::CoreTile;
2709 fb.producerSizeBytes =
2710 alignedBufferBytes(*
targetModel, prodType, producerBytes);
2711 fb.producerRawBytes = producerBytes;
2714 int64_t consumerBytes = producerBytes;
2715 if (
auto consType = ofOp.getConsumerElemType()) {
2716 auto consOFType = llvm::cast<AIEObjectFifoType>(consType.value());
2717 auto consMemref = llvm::cast<MemRefType>(consOFType.getElementType());
2722 bool coreConsumer = llvm::any_of(fb.consumerTiles, [&](Operation *cons) {
2723 auto tile = dyn_cast_or_null<TileLike>(cons);
2724 return tile && tile.getTileType() == AIETileType::CoreTile;
2726 fb.consumerSizeBytes = alignedBufferBytes(
2728 coreConsumer ? AIETileType::CoreTile : AIETileType::MemTile,
2730 fb.consumerRawBytes = consumerBytes;
2732 fb.sharedDepth = ofOp.sharedDepth();
2733 fb.producerDepth = ofOp.dmaDepth(std::nullopt);
2734 for (
unsigned ci = 0, e = fb.consumers.size(); ci < e; ++ci)
2735 fb.consumerDepths.push_back(ofOp.dmaDepth(ci));
2737 auto at = [
this](Value tile) {
return positionOf(tile.getDefiningOp()); };
2738 fb.producerEnd = ofOp.plannedDmaEnd(std::nullopt, at);
2739 for (
unsigned ci = 0, e = fb.consumers.size(); ci < e; ++ci)
2740 fb.consumerEnds.push_back(ofOp.plannedDmaEnd(ci, at));
2741 auto onMemTile = [&](Operation *tile) {
2742 auto like = dyn_cast_or_null<TileLike>(tile);
2743 return like && like.getTileType() == AIETileType::MemTile;
2745 auto drawsChannel = [&](Operation *tile,
bool planned) {
2746 auto like = dyn_cast_or_null<TileLike>(tile);
2749 return isShimEndType(like.getTileType()) ? !ofOp.getPlio() : planned;
2751 if (drawsChannel(fb.producerTile, fb.producerEnd.has_value()))
2752 fb.producerPin = PinnedChannels::endOf(ofOp, std::nullopt);
2754 pinnedRule.share(*fb.producerPin, collected.rank);
2755 for (
unsigned ci = 0, e = fb.consumers.size(); ci < e; ++ci) {
2756 std::optional<PinnedChannels::End> pin;
2757 if (drawsChannel(fb.consumerTiles[ci], fb.consumerEnds[ci].has_value()))
2758 pin = PinnedChannels::endOf(ofOp, ci);
2760 pinnedRule.share(*pin, collected.rank);
2761 fb.consumerPins.push_back(pin);
2763 if (fb.producerEnd && onMemTile(fb.producerTile)) {
2764 SmallVector<MemTileEnd> &ends = memTileEnds[fb.producerTile];
2765 fb.producerMemTileEntry = ends.size();
2766 ends.push_back({DMAChannelDir::MM2S, *fb.producerEnd});
2768 for (
unsigned ci = 0, e = fb.consumers.size(); ci < e; ++ci) {
2769 std::optional<unsigned> &entry = fb.consumerMemTileEntries.emplace_back();
2770 if (
const std::optional<PlannedDmaEnd> &end = fb.consumerEnds[ci];
2771 end && onMemTile(fb.consumerTiles[ci])) {
2772 SmallVector<MemTileEnd> &ends = memTileEnds[fb.consumerTiles[ci]];
2773 entry = ends.size();
2774 ends.push_back({DMAChannelDir::S2MM, *end});
2778 std::optional<ObjectFifoLinkOp> link = ofOp.getLink();
2779 fb.forcesDMA = ofOp.dmaReason().has_value();
2781 fb.linkTile = link->getOptionalSharedTile()->getDefiningOp();
2783 fb.allocateFallsBackToDMA = ofOp.allocateFallsBackToDMA();
2788 link && llvm::is_contained(link->getOutputObjectFifos(), ofOp);
2789 fb.unsynchronized = ofOp.getDisableSynchronization();
2790 if (
auto init = ofOp.getInitValues())
2791 fb.initObjects = init->size();
2792 fb.rearmed = poolLocks.rearms().contains(ofOp.getSymName());
2793 fb.producerCore =
hasCoreAccess(device, ofOp.getProducerTile(), ofOp,
2794 ObjectFifoPort::Produce);
2795 for (Value tile : ofOp.getConsumerTiles())
2796 fb.consumerCore.push_back(
2797 hasCoreAccess(device, tile, ofOp, ObjectFifoPort::Consume));
2798 fifoBuffers.push_back(fb);
2805 DenseMap<Operation *, PlannedDmaEnd> linkPlans;
2806 for (FifoBufferInfo &fb : fifoBuffers)
2807 for (
const std::optional<PlannedDmaEnd> &end :
2808 llvm::concat<
const std::optional<PlannedDmaEnd>>(
2809 fb.consumerEnds, ArrayRef(fb.producerEnd)))
2810 if (end && isa_and_nonnull<ObjectFifoLinkOp>(end->pool))
2811 linkPlans.try_emplace(end->pool, *end);
2812 DenseSet<Operation *> heldLinkPools;
2813 for (FifoBufferInfo &fb : fifoBuffers) {
2814 auto fifo = cast<ObjectFifoCreateOp>(fb.fifoOp);
2815 auto linkPoolOf = [&](std::optional<unsigned> consumer)
2816 -> std::pair<FifoBufferInfo::LinkPool, std::optional<PlannedDmaEnd>> {
2817 using LinkPool = FifoBufferInfo::LinkPool;
2818 ObjectFifoLinkOp link =
2819 consumer ? fifo.getConsumerLink(*consumer) : fifo.getProducerLink();
2820 auto plan = link ? linkPlans.find(link) : linkPlans.end();
2821 if (plan == linkPlans.end())
2822 return {LinkPool::None, std::nullopt};
2823 if (!heldLinkPools.insert(link).second)
2824 return {LinkPool::Shares, std::nullopt};
2825 return {LinkPool::Holds, plan->second};
2827 for (
unsigned ci = 0, e = fb.consumerEnds.size(); ci < e; ++ci) {
2828 auto [pool, plan] = linkPoolOf(ci);
2829 fb.consumerLinkPools.push_back(pool);
2830 fb.consumerLinkPlans.push_back(plan);
2832 std::tie(fb.producerLinkPool, fb.producerLinkPlan) =
2833 linkPoolOf(std::nullopt);
2836 auto linkSegments = [](
const std::optional<PlannedDmaEnd> &plan) {
2839 auto link = cast<ObjectFifoLinkOp>(plan->pool);
2840 auto unsynchronized = [](ObjectFifoCreateOp participant) {
2841 return participant.getDisableSynchronization();
2843 if (llvm::any_of(link.getInputObjectFifos(), unsynchronized) ||
2844 llvm::any_of(link.getOutputObjectFifos(), unsynchronized))
2846 return static_cast<int>(link.getPoolSegments().size());
2848 for (
const std::optional<PlannedDmaEnd> &plan : fb.consumerLinkPlans)
2849 fb.consumerLinkSegments.push_back(linkSegments(plan));
2850 fb.producerLinkSegments = linkSegments(fb.producerLinkPlan);
2853 variableLinks.clear();
2854 DenseMap<Operation *, size_t> fifoIndex;
2855 for (
auto [index, fb] : llvm::enumerate(fifoBuffers))
2856 fifoIndex[fb.fifoOp] = index;
2857 auto at = [
this](Value tile) {
return positionOf(tile.getDefiningOp()); };
2858 for (ObjectFifoLinkOp link : objectFifoLinks) {
2859 LinkPoolPlan plan = link.getPoolPlan();
2862 Operation *point = plan.
linkTile.getDefiningOp();
2863 VariableLink variable{link, std::move(plan), 0, {point}, {}, {}, {}};
2864 for (
const LinkPoolSharer &sharer : variable.plan.sharers)
2865 variable.tiles.append({sharer.
producer.getDefiningOp(),
2868 std::vector<ObjectFifoCreateOp> ins = link.getInputObjectFifos();
2869 std::vector<ObjectFifoCreateOp> outs = link.getOutputObjectFifos();
2870 for (ObjectFifoCreateOp fifo : llvm::concat<ObjectFifoCreateOp>(ins, outs))
2871 if (
auto index = fifoIndex.find(fifo.getOperation());
2872 index != fifoIndex.end())
2873 variable.fifos.push_back(index->second);
2874 llvm::sort(variable.fifos);
2875 variable.fifos.erase(llvm::unique(variable.fifos), variable.fifos.end());
2876 using LinkPool = FifoBufferInfo::LinkPool;
2877 for (
size_t index : variable.fifos) {
2878 FifoBufferInfo &fb = fifoBuffers[index];
2879 auto fifo = cast<ObjectFifoCreateOp>(fb.fifoOp);
2880 for (
unsigned ci = 0, e = fb.consumerLinkPools.size(); ci < e; ++ci)
2881 if (fb.consumerLinkPools[ci] == LinkPool::Holds &&
2882 fifo.getConsumerLink(ci) == link)
2883 variable.holds.push_back({index, ci});
2884 if (fb.producerLinkPool == LinkPool::Holds &&
2885 fifo.getProducerLink() == link)
2886 variable.holds.push_back({index, std::nullopt});
2888 variable.depth = variable.plan.depthAt(*
targetModel, at);
2889 variableLinks.push_back(std::move(variable));
2892 LLVM_DEBUG(llvm::dbgs() <<
"[SA] seed=" << rngSeed <<
"\n");
2893 LLVM_DEBUG(llvm::dbgs() <<
"[SA] Collected " << fifoBuffers.size()
2894 <<
" ObjectFifo buffer requirements\n");
2897LogicalResult SAPlacer::generateInitialPlacement() {
2898 auto &logicalTiles = collected.logicalTiles;
2901 std::vector<TileID> availComp =
availability.compTiles;
2902 std::vector<TileID> availMem, availShim;
2904 AIETileType type =
targetModel->getTileType(t.col, t.row);
2905 if (type == AIETileType::MemTile)
2906 availMem.push_back(t);
2907 else if (type == AIETileType::ShimNOCTile)
2908 availShim.push_back(t);
2916 int phaseA = (a.col + a.row) % 2;
2917 int phaseB = (b.col + b.row) % 2;
2918 if (phaseA != phaseB)
2919 return phaseA < phaseB;
2921 return a.row < b.row;
2922 return a.col < b.col;
2928 int phaseA = a.col % 2;
2929 int phaseB = b.col % 2;
2930 if (phaseA != phaseB)
2931 return phaseA < phaseB;
2932 return a.col < b.col;
2934 deterministicShuffle(availShim, rng);
2936 size_t compIdx = 0, memIdx = 0, shimIdx = 0;
2941 SmallVector<TileID> pinnedMem, pinnedShim;
2942 for (
auto lt : logicalTiles) {
2943 Operation *op = lt.getOperation();
2944 auto col = lt.tryGetCol();
2945 auto row = lt.tryGetRow();
2946 AIETileType type = lt.getTileType();
2951 currentPlacement[op] = pos;
2952 physToLogical[pos] = op;
2953 constrainedTiles.insert(op);
2955 if (type == AIETileType::CoreTile) {
2956 llvm::erase(availComp, pos);
2957 }
else if (llvm::is_contained(availMem, pos)) {
2958 llvm::erase(availMem, pos);
2959 pinnedMem.push_back(pos);
2960 }
else if (llvm::is_contained(availShim, pos)) {
2961 llvm::erase(availShim, pos);
2962 pinnedShim.push_back(pos);
2966 llvm::append_range(availMem, pinnedMem);
2967 llvm::append_range(availShim, pinnedShim);
2972 auto byMemWeightDesc = [
this](Operation *a, Operation *b) {
2973 int64_t wa = computeTileMemoryWeight(a);
2974 int64_t wb = computeTileMemoryWeight(b);
2977 return collected.rank.lookup(a) < collected.rank.lookup(b);
2980 SmallVector<Operation *> sortedCoreTiles;
2981 for (
auto lt : logicalTiles) {
2982 Operation *op = lt.getOperation();
2983 if (constrainedTiles.contains(op))
2985 if (lt.getTileType() == AIETileType::CoreTile)
2986 sortedCoreTiles.push_back(op);
2988 llvm::stable_sort(sortedCoreTiles, byMemWeightDesc);
2990 for (
auto *op : sortedCoreTiles) {
2993 for (
size_t i = compIdx; i < availComp.size(); i++) {
2994 if (isLegalPosition(op, availComp[i])) {
2996 std::swap(availComp[i], availComp[compIdx]);
3003 return cast<LogicalTileOp>(op).emitError(
3004 "no available physical tile for placement");
3005 currentPlacement[op] = pos;
3006 physToLogical[pos] = op;
3007 movableTiles.push_back(op);
3014 SmallVector<Operation *> sortedMemTiles, shimTiles;
3015 for (
auto lt : logicalTiles) {
3016 Operation *op = lt.getOperation();
3017 if (constrainedTiles.contains(op))
3019 AIETileType type = lt.getTileType();
3020 if (type == AIETileType::MemTile)
3021 sortedMemTiles.push_back(op);
3022 else if (type == AIETileType::ShimNOCTile)
3023 shimTiles.push_back(op);
3025 llvm::stable_sort(sortedMemTiles, byMemWeightDesc);
3028 auto placeIn = [&](ArrayRef<Operation *> ops, ArrayRef<TileID> pool,
3029 size_t &next) -> LogicalResult {
3030 for (Operation *op : ops) {
3031 std::optional<TileID> pos, named;
3032 for (
size_t i = 0; i < pool.size() && !pos; ++i) {
3033 TileID at = pool[(next + i) % pool.size()];
3034 if (isLegalPosition(op, at))
3041 if (
auto clash =
namedClash(op, namedAt(op, *named)))
3044 return cast<LogicalTileOp>(op).emitError(
3045 "no available physical tile for placement");
3047 currentPlacement[op] = *pos;
3048 movableTiles.push_back(op);
3052 if (failed(placeIn(sortedMemTiles, availMem, memIdx)) ||
3053 failed(placeIn(shimTiles, availShim, shimIdx)))
3060void SAPlacer::initializeSAState() {
3061 initBoundingBoxes();
3062 initResourceTracking();
3064 cascadePen = computePairingPenalty();
3065 int memPressure = computeMemoryPressure() + computeSoftTerms();
3067 computeTotalHPWL() + getResourcePenalty() + cascadePen + memPressure;
3069 deviceSlots =
availability.compTiles.size() + movableTiles.size();
3071 LLVM_DEBUG(llvm::dbgs() <<
"[SA] Initial cost: " << totalCost
3072 <<
" (HPWL=" << computeTotalHPWL()
3073 <<
", resPenalty=" << getResourcePenalty()
3074 <<
"), movable tiles: " << movableTiles.size()
3075 <<
", nets: " << nets.size()
3076 <<
", fifos: " << fifoBuffers.size() <<
"\n");
3079void SAPlacer::runSAMainLoop() {
3081 bool hasCostTerms = !nets.empty() || !fifoBuffers.empty() ||
3082 !cascadeAdjacency.edges.empty() ||
3084 if (movableTiles.empty() || !hasCostTerms)
3088 int numMovable = movableTiles.size();
3089 int numNets = nets.size();
3092 std::clamp(
static_cast<int>(numMovable * std::sqrt(std::max(numNets, 1))),
3093 config.minMovesPerIter, config.maxMovesPerIter);
3095 int maxIters = std::max(
3097 static_cast<int>(1000 * std::sqrt(
static_cast<double>(numMovable) *
3098 std::max(numNets, 1))));
3100 int greedyIters = config.greedyMultiplier * numMovable;
3103 auto scaled = [&](
int budget) {
3104 double v = std::min(budget * config.effort,
3105 static_cast<double>(std::numeric_limits<int>::max()));
3106 return std::max(1,
static_cast<int>(v));
3108 movesPerIter = scaled(movesPerIter);
3113 greedyIters = scaled(greedyIters);
3115 int numSamples = std::max(10 * numMovable, 50);
3116 double estimatedT = estimateInitialTemperature(numSamples);
3118 std::min(config.tempScaleEstimate * estimatedT,
3119 static_cast<double>(totalCost) * config.tempScaleCost);
3120 initTemp = std::max(initTemp, 1.0);
3122 LLVM_DEBUG(llvm::dbgs() <<
"[SA] Schedule: movesPerIter=" << movesPerIter
3123 <<
" maxIters=" << maxIters
3124 <<
" initTemp=" << initTemp <<
"\n");
3126 schedule = SASchedule(initTemp, movesPerIter, maxIters, greedyIters, config);
3128 bestPlacement = currentPlacement;
3130 (getResourcePenalty() == 0 && cascadePen == 0) ? totalCost : INT_MAX;
3131 bestOverallPlacement = currentPlacement;
3132 bestOverallCost = totalCost;
3133 zeroDeltaMoves = posDeltaMoves = negDeltaMoves = 0;
3134 acceptedUphill = rejectedMoves = 0;
3136 while (!schedule.limitReached()) {
3137 for (
int m = 0; m < schedule.getMovesPerIter(); m++) {
3139 SmallVector<std::pair<Operation *, TileID>> moves;
3140 if (!generateMove(moves))
3145 if (schedule.getIteration() % config.debugInterval == 0)
3146 LLVM_DEBUG(llvm::dbgs()
3147 <<
"[SA] Iter " << schedule.getIteration()
3148 <<
" T=" << llvm::format(
"%.3e", schedule.getTemperature())
3149 <<
" cost=" << totalCost <<
" best=" << bestCost <<
" accept="
3150 << llvm::format(
"%.3f", schedule.getAcceptanceRatio())
3151 <<
" d0=" << zeroDeltaMoves <<
" d+=" << posDeltaMoves
3152 <<
" d-=" << negDeltaMoves <<
" uphill=" << acceptedUphill
3153 <<
" rej=" << rejectedMoves
3154 << (schedule.isGreedy() ?
" (greedy)" :
"") <<
"\n");
3157 if (schedule.getIteration() % config.fullRecomputeInterval == 0 &&
3158 schedule.getIteration() > 0) {
3159 initResourceTracking();
3160 cascadePen = computePairingPenalty();
3161 totalCost = computeTotalHPWL() + getResourcePenalty() + cascadePen +
3162 computeMemoryPressure() + computeSoftTerms();
3173void SAPlacer::tryMove(SmallVector<std::pair<Operation *, TileID>> &moves) {
3177 SmallVector<std::pair<Operation *, TileID>> oldPlacements;
3178 for (
auto &[t, _] : moves)
3179 oldPlacements.push_back({t, currentPlacement[t]});
3180 int oldResPenalty = cachedResourcePenalty;
3181 int oldMemSpillover = memSpilloverPenalty, oldBDCount = bdCountPenalty,
3182 oldDelegate = delegatePenalty, oldDMA = dmaPenalty;
3183 int oldCoreOverflow = coreOverflowPenalty;
3184 SmallVector<TileID> oldCoreOverflowTiles = coreOverflowTiles;
3185 int oldPositionsOverLocks = positionsOverLocks;
3186 StreamCuts oldCuts = cuts;
3187 int oldStreamCut = streamCutPenalty;
3188 int oldPortsOver = portsOver;
3189 int oldDdr = ddrPenalty;
3190 int64_t oldDdrTotal = ddrTotal;
3191 int oldCoresChanged = coresChanged;
3194 for (
auto &[t, _] : moves)
3195 physToLogical.erase(currentPlacement[t]);
3196 SmallVector<SmallVector<std::pair<size_t, NetBoundingBox>>> allBackups(
3199 for (
size_t i = 0; i < moves.size(); i++) {
3200 hpwlDelta += evaluateMove(moves[i].first, moves[i].second, allBackups[i]);
3201 currentPlacement[moves[i].first] = moves[i].second;
3203 for (
auto &[t, pos] : moves)
3204 physToLogical[pos] = t;
3207 int oldCascade = cascadePen;
3208 int oldPressure = cachedPressure;
3209 int newResPenalty = updateResourcePenalty(oldPlacements);
3210 int newCascade = llvm::any_of(moves,
3211 [&](
const auto &move) {
3212 return pairedTiles.contains(move.first);
3214 ? computePairingPenalty()
3216 int newPressure = computeMemoryPressure() + computeSoftTerms();
3217 int delta = hpwlDelta + (newResPenalty - oldResPenalty) +
3218 (newCascade - oldCascade) + (newPressure - oldPressure);
3231 (schedule.getTemperature() > 0 &&
3232 drawUnitReal(rng) < std::exp(-delta / schedule.getTemperature()));
3238 cascadePen = newCascade;
3239 cachedPressure = newPressure;
3240 schedule.record(
true);
3241 if (totalCost < bestOverallCost) {
3242 bestOverallCost = totalCost;
3243 bestOverallPlacement = currentPlacement;
3247 if (totalCost < bestCost && newResPenalty == 0 && newCascade == 0) {
3248 bestCost = totalCost;
3249 bestPlacement = currentPlacement;
3253 for (
auto &[t, pos] : moves)
3254 physToLogical.erase(pos);
3255 for (
int i = moves.size() - 1; i >= 0; i--) {
3256 revertMove(allBackups[i]);
3257 currentPlacement[moves[i].first] = oldPlacements[i].second;
3259 for (
auto &[op, oldPos] : oldPlacements)
3260 physToLogical[oldPos] = op;
3262 llvm::map_to_vector(replannedLinks, [](ReplannedLink replanned) {
3263 return std::make_pair(replanned.index, replanned.from);
3266 positionsOverLocks = oldPositionsOverLocks;
3267 cuts = std::move(oldCuts);
3268 streamCutPenalty = oldStreamCut;
3269 portsOver = oldPortsOver;
3270 ddrPenalty = oldDdr;
3271 ddrTotal = oldDdrTotal;
3272 coresChanged = oldCoresChanged;
3273 cachedResourcePenalty = oldResPenalty;
3274 memSpilloverPenalty = oldMemSpillover;
3275 bdCountPenalty = oldBDCount;
3276 delegatePenalty = oldDelegate;
3277 dmaPenalty = oldDMA;
3278 coreOverflowPenalty = oldCoreOverflow;
3279 coreOverflowTiles = std::move(oldCoreOverflowTiles);
3281 schedule.record(
false);
3285void SAPlacer::commitMove() {
3286 currentMemUsage.commit();
3287 currentLockDemand.commit();
3288 currentDMAUsage.commit();
3289 sharedMemDestination.commit();
3290 coreFifoBuffers.commit();
3291 coreUnplacedAt.commit();
3292 bdShortfallAt.commit();
3293 dmaPenaltyAt.commit();
3294 ddrScoreOf.commit();
3295 runtimeBdAt.commit();
3296 netStreams.commit();
3299 incomingAt.commit();
3300 incomingCount.commit();
3303 coreFifoLog.clear();
3306void SAPlacer::rollbackMove() {
3307 currentMemUsage.rollback();
3308 currentLockDemand.rollback();
3309 currentDMAUsage.rollback();
3310 sharedMemDestination.rollback();
3311 coreFifoBuffers.rollback();
3312 coreUnplacedAt.rollback();
3313 bdShortfallAt.rollback();
3314 dmaPenaltyAt.rollback();
3315 ddrScoreOf.rollback();
3316 runtimeBdAt.rollback();
3317 netStreams.rollback();
3319 streamsAt.rollback();
3320 incomingAt.rollback();
3321 incomingCount.rollback();
3322 for (
auto &[at, end, sign] : llvm::reverse(pinLog))
3323 pinUse.place(at, end, -sign);
3324 for (
auto &[at, claim, sign] : llvm::reverse(claimLog))
3325 pinUse.claim(at, claim, -sign);
3328 coreFifoLog.clear();
3335void SAPlacer::printPlacementStats(int64_t elapsedMs)
const {
3336 int finalHPWL = computeTotalHPWL();
3337 int finalHardPenalty = getResourcePenalty();
3338 int finalPressure = computeMemoryPressure() + computeSoftTerms();
3339 int finalCascade = computePairingPenalty();
3340 bool isLegal = (finalHardPenalty == 0 && finalCascade == 0);
3342 llvm::dbgs() <<
"[SA] seed=" << rngSeed <<
" Final HPWL=" << finalHPWL
3343 <<
", resPenalty=" << finalHardPenalty
3344 <<
", pressure=" << finalPressure <<
", cascade=" << finalCascade
3345 <<
", cut=" << cuts.over() <<
", ddr=" << ddrPenalty
3346 <<
", cores-changed=" << coresChanged
3347 <<
", legal=" << (isLegal ?
"yes" :
"NO") <<
"\n";
3348 llvm::dbgs() <<
"[SA] " << schedule.getIteration() <<
" iters, "
3349 << movableTiles.size() <<
" tiles, " << nets.size() <<
" nets, "
3350 <<
allocates.size() <<
" allocates, " << elapsedMs <<
" ms\n";
3351 llvm::dbgs() <<
"[SA] Moves: d-=" << negDeltaMoves <<
" d0=" << zeroDeltaMoves
3352 <<
" d+=" << posDeltaMoves <<
" uphill=" << acceptedUphill
3353 <<
" rej=" << rejectedMoves <<
"\n";
3356 int64_t coreCap =
targetModel->getLocalMemorySize();
3358 for (
auto &[pos, used] : currentMemUsage) {
3359 auto type =
targetModel->getTileType(pos.col, pos.row);
3360 int64_t cap = (type == AIETileType::MemTile) ? memCap : coreCap;
3361 if (used > cap * 3 / 4)
3362 llvm::dbgs() <<
"[SA-RES] mem(" << pos.col <<
"," << pos.row
3363 <<
"): " << used <<
"/" << cap
3364 << (used > cap ?
" OVERFLOW" :
"") <<
"\n";
3366 for (
auto &[pos, usage] : currentDMAUsage) {
3368 if (usage.first >= maxIn || usage.second >= maxOut)
3369 llvm::dbgs() <<
"[SA-RES] dma(" << pos.col <<
"," << pos.row
3370 <<
"): in=" << usage.first <<
"/" << maxIn
3371 <<
" out=" << usage.second <<
"/" << maxOut
3372 << (usage.first > maxIn || usage.second > maxOut
3379 for (
auto &[pos, used] : currentMemUsage) {
3380 auto type =
targetModel->getTileType(pos.col, pos.row);
3381 if (type != AIETileType::CoreTile || used <= coreCap)
3383 int64_t overflow = used - coreCap;
3385 auto it = currentMemUsage.find(n);
3386 int64_t nbrUsed = it != currentMemUsage.end() ? it->second : 0;
3387 llvm::dbgs() <<
" nbr(" << n.col <<
"," << n.row <<
"): used=" << nbrUsed
3388 <<
" spare=" << std::max(coreCap - nbrUsed, int64_t{0})
3391 llvm::dbgs() <<
"[SA-PENALTY] tile(" << pos.col <<
"," << pos.row
3392 <<
"): used=" << used <<
" cap=" << coreCap
3393 <<
" overflow=" << overflow <<
"\n";
3401LogicalResult SAPlacer::finalizePlacement(DeviceOp device) {
3404 finalCost = totalCost;
3405 if (bestOverallCost < INT_MAX) {
3406 if (bestCost < INT_MAX) {
3407 currentPlacement = bestPlacement;
3408 finalCost = bestCost;
3410 currentPlacement = bestOverallPlacement;
3411 finalCost = bestOverallCost;
3413 physToLogical.clear();
3414 for (
auto &[op, pos] : currentPlacement)
3415 physToLogical[pos] = op;
3416 initResourceTracking();
3420 generateAllocates();
3421 finalLockGroups = lockGroups().size();
3422 finalLockPenalty = computeLockPenalty(&finalLockStopped);
3424 auto endTime = std::chrono::steady_clock::now();
3425 auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(
3426 endTime - startTime);
3428 LLVM_DEBUG(printPlacementStats(elapsed.count()));
3437 int finalPairing = computePairingPenalty();
3438 int finalDelegate = computeDelegatePenalty();
3439 if (finalPairing != 0 || finalDelegate != 0) {
3440 InFlightDiagnostic diag =
3441 device.emitError(
"SA placer failed to find a legal placement (cascade "
3442 "and shared memory penalty=")
3443 << finalPairing <<
", delegate penalty=" << finalDelegate
3444 <<
"); try increasing --sa-effort";
3445 explainPenalties(diag);
3448 if (
int estimated = getResourcePenalty() - finalDelegate; estimated != 0) {
3449 InFlightDiagnostic diag =
3450 device.emitWarning(
"SA placer's resource estimate is over capacity "
3453 <<
"); later passes check exactly, and increasing --sa-effort may help";
3454 explainPenalties(diag);
3457 result = currentPlacement;
3461void SAPlacer::explainPenalties(InFlightDiagnostic &diag) {
3462 SmallVector<TileID> spill, core, locks, channels, bds, delegates, pairing,
3464 int spillPenalty = computeMemSpilloverPenalty(&spill);
3465 int corePenalty = computeCoreOverflowPenalty(&core);
3466 int lockPenalty = computeLockPenalty(
nullptr, &locks);
3467 int channelPenalty = 0;
3468 int bdPenalty = computeBDCountPenalty();
3469 for (
auto &[at, ids] : bdShortfallAt)
3472 for (
auto &[at, _] : currentDMAUsage) {
3474 int penalty = computeTileDMAPenalty(at, &ids);
3475 if (penalty != ids) {
3476 channelPenalty += penalty - ids;
3477 channels.push_back(at);
3484 int delegatePenalty = computeDelegatePenalty(&delegates);
3485 int cutPenalty = config.streamCutPenaltyPerChannel * cuts.over();
3486 int pairingPenalty = computePairingPenalty(&pairing);
3489 std::tuple<StringRef, int, SmallVector<TileID> &> terms[] = {
3490 {
"memory spillover", spillPenalty, spill},
3491 {
"core overflow", corePenalty, core},
3492 {
"locks", lockPenalty, locks},
3493 {
"DMA channels", channelPenalty, channels},
3494 {
"BD ids", bdPenalty, bds},
3495 {
"delegates", delegatePenalty, delegates},
3496 {
"cascade and shared memory pairing", pairingPenalty, pairing},
3497 {
"stream cuts", cutPenalty, none}};
3498 for (
auto &[term, penalty, tiles] : terms) {
3502 tiles.erase(llvm::unique(tiles), tiles.end());
3503 Operation *anchor =
nullptr;
3505 auto consider = [&](Operation *op) {
3506 unsigned rank = collected.rank.lookup(op);
3507 if (!anchor || rank < collected.rank.lookup(anchor) ||
3508 (rank == collected.rank.lookup(anchor) &&
3509 op->isBeforeInBlock(anchor)))
3512 if (!tiles.empty()) {
3513 for (
auto &[op, at] : currentPlacement)
3514 if (at == tiles.front())
3516 for (Operation *op : physicalTiles.lookup(tiles.front()))
3520 anchor ? diag.attachNote(anchor->getLoc()) : diag.attachNote();
3521 note << term <<
" penalty=" << penalty;
3522 for (
auto [i, at] : llvm::enumerate(tiles))
3523 note << (i ?
", " :
" on ") <<
"(" << at.col <<
", " << at.row <<
")";
virtual std::optional< TileID > getMemNorth(TileID src) const =0
Return the tile ID of the memory to the north of the given tile, if it exists.
virtual AIETileType getTileType(int col, int row) const =0
Return the tile type for the given tile coordinates.
virtual std::optional< TileID > getMemSouth(TileID src) const =0
Return the tile ID of the memory to the south of the given tile, if it exists.
virtual std::optional< TileID > getMemEast(TileID src) const =0
Return the tile ID of the memory to the east of the given tile, if it exists.
virtual std::optional< TileID > getMemWest(TileID src) const =0
Return the tile ID of the memory to the west of the given tile, if it exists.
virtual uint32_t getMemTileLoadStoreBusWidth() const
Return the data bus width (in bits) for load/store operations of a memory tile.
SharedMemory
Which of two tiles' memory modules both of them can address.
static WalkChoice searchWalkProduct(llvm::ArrayRef< llvm::SmallVector< int64_t > > bytes, llvm::function_ref< bool(llvm::ArrayRef< unsigned >)> places, unsigned maxTries)
Tries the choices of one set per tile, bytes[tile] giving each of its sets' bytes walked whole,...
static BDWalkSets walkSetsThatFit(const AIETargetModel &target, int col, int row, llvm::ArrayRef< BDPlanEnd > ends, llvm::ArrayRef< unsigned > poolOf, llvm::ArrayRef< BDWalkPool > pools, llvm::function_ref< bool(DMAChannelDir, int)> free, llvm::function_ref< int64_t(int)> spent, unsigned maxSets=std::numeric_limits< unsigned >::max())
Every set of walkable pools whose walk lets planBDChannels fit ends (poolOf gives each end's pool),...
static llvm::SmallVector< mlir::Operation * > lockOwners(const AIETargetModel &target, ObjectFifoPoolOp pool)
The ops whose locks allocation and the SA each make for pool: with semaphore locks,...
static llvm::SmallVector< int > groupCounts(const AIETargetModel &target, int64_t depth, int owners)
The lock groups owners lock owners of a pool of depth objects take, by count.
static bool dmaLocalOnly(AIETileType type)
Whether a DMA on a tile of type uses only its own tile's locks: every DMA does but a mem tile's.
static bool reaches(const AIETargetModel &target, llvm::ArrayRef< TileID > user, llvm::ArrayRef< TileID > memory, bool localOnly)
Whether a tile at one of user reaches memory at one of memory; with localOnly, only at its own positi...
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< DMAChannelAnalysis::ChannelClaim > > claimsOf
static Adjacency buildCascadeAdjacency(llvm::ArrayRef< CascadeFlowOp > cascadeFlows)
llvm::SmallVector< mlir::Operation * > overlayTileOps() const
static bool satisfiesConstraints(mlir::Operation *tile, TileID pos)
static llvm::MapVector< mlir::Operation *, std::pair< int, int > > flowChannelDemand(llvm::ArrayRef< FlowOp > flows, llvm::ArrayRef< PacketFlowOp > pktFlows, llvm::ArrayRef< RouteOp > routes, llvm::ArrayRef< DMAChannelAnalysis::ChannelClaim > claims, llvm::DenseMap< mlir::Operation *, llvm::SmallVector< std::pair< int, int > > > *named=nullptr, llvm::DenseMap< mlir::Operation *, mlir::Operation * > *keys=nullptr)
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned > > ddrGroupsOf
void buildStreamNets(DeviceOp device, const CollectedOps &collected)
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< unsigned > > streamNetsOf
int64_t ddrGroupSpread(const DdrGroup &group, llvm::function_ref< std::optional< int >(mlir::Operation *)> columnOf, int weight) const
llvm::DenseMap< mlir::Operation *, StreamDemand > streamDemand
llvm::SmallVector< StreamNet > streamNets
llvm::DenseMap< mlir::Operation *, unsigned > coreKeys
RuntimeBdIds runtimeBdIds
const AIETargetModel * targetModel
bool overlayChannels(TileID tile) const
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< std::pair< int, int > > > namedChannels
llvm::SmallVector< AllocateInfo > allocates
llvm::SmallVector< llvm::DenseMap< TileID, unsigned > > neighbourCores
std::optional< std::pair< mlir::Operation *, std::pair< int, int > > > namedClash(mlir::Operation *tile, llvm::ArrayRef< mlir::Operation * > others) const
bool streamOf(const StreamNet &net, llvm::function_ref< std::optional< TileID >(mlir::Operation *)> at, TileID &src, llvm::SmallVectorImpl< TileID > &dsts) const
ShareableShimEnds shareableShimEnds
std::optional< ShimTransferSpans > shimSpans
void buildShimModel(DeviceOp device, llvm::ArrayRef< ObjectFifoCreateOp > objectFifos, llvm::ArrayRef< DMAChannelAnalysis::ChannelClaim > claims, const llvm::DenseMap< mlir::Operation *, unsigned > &rank, const llvm::DenseMap< mlir::Operation *, mlir::Operation * > &routeKeys={})
TileAvailability availability
void buildStreamDemand(llvm::ArrayRef< ObjectFifoCreateOp > objectFifos)
static int shimChannelsSaved(const ShimTransferSpans &spans, llvm::ArrayRef< const ShimSide * > sides, llvm::ArrayRef< mlir::StringAttr > extra, llvm::ArrayRef< int > pinnedHere)
OverlayFit overlayAt(TileID at, const PinnedChannelUse &pins, llvm::ArrayRef< PinnedChannels::End > extra, llvm::ArrayRef< mlir::Operation * > tilesHere, const ShimTransferSpans *spans) const
llvm::DenseMap< mlir::Operation *, llvm::SmallVector< mlir::Operation * > > incomingFifos
mlir::LogicalResult emitNamedClash(mlir::Operation *tile, TileID at, std::pair< mlir::Operation *, std::pair< int, int > > clash) const
static CollectedOps collectOperations(DeviceOp device)
llvm::SmallVector< DdrGroup > ddrGroups
bool needsLocks(ObjectFifoPoolOp pool) const
Whether pool gets locks.
static bool isShimEndType(std::optional< AIETileType > type)
mlir::LogicalResult place(DeviceOp device) override
void record(bool accepted)
bool limitReached() const
double getAcceptanceRatio() const
void sortLargestBufferFirst(Range &&buffers, BytesFn bytes)
Buffers are laid out, and given a tile, largest buffer first: by the address layout below,...
TileLayout layoutTile(const TileLayoutProblem &problem, TileLayoutStats &stats)
Lays out problem as assign-buffer-addresses does, without touching IR.
TileLayoutBuffer tileLayoutBuffer(BufferOp buffer, const TileMemoryLimits &limits)
What assign-buffer-addresses lays buffer out as, on a tile with limits.
llvm::SmallVector< unsigned > demandFirstOrder(llvm::ArrayRef< SpillPool > pools)
aie-objectfifo-allocate's demand-first packing order of pools, given in its size-first order,...
bool hasCoreAccess(DeviceOp device, mlir::Value tile, ObjectFifoCreateOp fifo, ObjectFifoPort port)
int64_t getMemRefSizeInBytes(mlir::MemRefType type, const mlir::DataLayout &layout)
llvm::SmallVector< TileID, 2 > memTileSpillNeighbours(const AIETargetModel &target, TileID home)
The tiles a mem tile buffer homed at home may spill to: those in its row home shares memory with,...
struct TileID { friend std::ostream &operator<<(std::ostream &os, const TileID &s) { os<< "TileID("<< s.col<< ", "<< s.row<< ")"; return os; } friend std::string to_string(const TileID &s) { std::ostringstream ss; ss<< s; return ss.str(); } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const TileID &s) { os<< to_string(s); return os; } inline bool operator<(const TileID &rhs) const { return std::tie(col, row)< std::tie(rhs.col, rhs.row); } bool operator==(const TileID &rhs) const { return std::tie(col, row)==std::tie(rhs.col, rhs.row); } bool operator!=(const TileID &rhs) const { return !(*this==rhs);} int col, row;} TileID
std::pair< int, int > getDMACapacity(const AIETargetModel &tm, TileID tile)
Get DMA channel capacity (maxIn, maxOut) for a tile position: its S2MM and MM2S channel counts.
uint32_t requiredBufferAlignBits(uint32_t busAlignBits, uint32_t maxVecAlignBits, int64_t sizeBytes)
Return the alignment (in bits) a buffer of sizeBytes must satisfy.
int64_t bufferAlignBytes(BufferOp buffer, uint32_t tileAlignBitWidth, uint32_t maxVecAlignBits)
The alignment assign-buffer-addresses places buffer at, in bytes: the vector rule when aligned,...
TileMemoryLimits tileMemoryLimits(const AIETargetModel &targetModel, AIETileType tileType)
llvm::SmallVector< unsigned > memTileSpillComponents(llvm::ArrayRef< TileID > homes, llvm::function_ref< llvm::SmallVector< TileID, 2 >(TileID)> neighboursOf)
For each of homes, the index of its component: homes whose buffers may spill to a tile in common,...
llvm::SmallVector< int64_t > bytes
The bytes each set walks whole.
llvm::SmallVector< llvm::SmallVector< unsigned > > sets
llvm::SmallVector< unsigned > sets
llvm::SmallVector< LinkPoolSharer > sharers
llvm::SmallVector< std::optional< unsigned > > tiles
bool stopped
The exact packing ran out of kPackBudget steps before it decided.
llvm::SmallVector< mlir::Operation * > endpoints
llvm::SmallVector< ObjectFifoLinkOp > objectFifoLinks
llvm::SmallVector< ObjectFifoCreateOp > objectFifos
llvm::SmallVector< LogicalTileOp > logicalTiles
One buffer of a tile, as assign-buffer-addresses lays it out.
int64_t alignBytes
bufferAlignBytes.
llvm::SmallVector< int, 2 > spaceBanks
The banks the buffer's memory space allows, when it names some.
llvm::SmallVector< TileLayoutBuffer > buffers
In the order the device holds them.
bool hasCore
Whether the tile runs a core, whose sections need a contiguous region.
MemoryRun stackRun
The core's stack; empty without one.
int64_t maxDataMemorySize
std::optional< int > stackBank
For a stack pinned to a bank but not an address: the bank, and the alignment of the address chosen in...
int64_t budget
Placements each search may try before it gives up.
uint32_t tileAlignBitWidth
@ NoRoom
Buffer failed fits nowhere once the others are placed.
int64_t unplacedBytes
Bytes of the buffers left without an address on NoRoom.
A memtile is reached by DMA rather than by core vector load and store, so its bus width also covers t...
int64_t maxDataMemorySize
uint32_t tileAlignBitWidth