13#include "llvm/ADT/MapVector.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/SetVector.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/Support/CommandLine.h"
18#include "llvm/Support/Debug.h"
19#include "llvm/Support/ErrorHandling.h"
20#include "llvm/Support/FormatVariadic.h"
29#define DEBUG_TYPE "aie-pathfinder"
31STATISTIC(numReplaysSkipped,
"Attempts skipped as replays of an earlier one");
32STATISTIC(numReplaysVerified,
"Attempts routed and verified to replay one");
34static llvm::cl::opt<bool> clVerifyReplays(
35 "aie-pathfinder-verify-replays", llvm::cl::Hidden,
36 llvm::cl::desc(
"Route the attempts of a relax ladder that replay an "
37 "earlier one anyway, and abort unless each iteration's "
38 "routing and the result are the earlier attempt's"),
39 llvm::cl::init(
false));
41static llvm::hash_code hashRouting(
const Routing &routing) {
42 llvm::hash_code h = llvm::hash_value(routing.
settings.size());
44 for (
const auto &[tile, s] : ss) {
45 h = llvm::hash_combine(h, tile.col, tile.row, s.srcs.size(),
47 for (
const Port &p : s.srcs)
48 h = llvm::hash_combine(h, p.bundle, p.channel);
49 for (
const Port &p : s.dsts)
50 h = llvm::hash_combine(h, p.bundle, p.channel);
54 h = llvm::hash_combine(h, e.coords.col, e.coords.row, e.port.bundle,
57 for (
const auto &[src, ss] : routing.
settings) {
61 for (
const auto &[key, ss] : routing.
idSettings) {
63 h = llvm::hash_combine(h, key.second);
66 for (
const auto &[src, hops] : routing.
packetTrees) {
68 for (
const TreeHop &hop : hops) {
71 h = llvm::hash_combine(h, hop.joined);
81constexpr double overCapacityCoeff = 0.1;
82constexpr double usedCapacityCoeff = 0.02;
83constexpr double demandBase = 1.0;
86constexpr double demandCoeff = 1.1;
87constexpr double priorityDemandCoeff =
88 static_cast<double>(std::numeric_limits<int>::max());
89constexpr int maxCircuitStreamCapacity = 1;
90constexpr int maxPacketStreamCapacity = 32;
93constexpr double avoidedPortDemand = 100.0;
95constexpr int routingCheckPenalty = 5;
97constexpr int maxSteers = 16;
101constexpr int maxPriorityFaults = 16;
104constexpr int maxMeetFaults = 4;
106constexpr double conflictSharePenalty = 4;
110constexpr int packetFanoutCap = 2;
115constexpr double treeSeedFactor = 0.9;
117constexpr double rerouteMinSaving = 1e-6;
120constexpr int stallIterations = 50;
123constexpr int maxReorderedStall = 300;
127constexpr int maxOverusedStall = 400;
131constexpr int maxRejectedStall = 600;
134constexpr int stallHistory = 4;
139 c.demand = (demandBase + overCapacityCoeff * c.overCapacity) *
140 (demandBase + usedCapacityCoeff * c.usedCapacity) +
160 LLVM_DEBUG(llvm::dbgs() <<
"\t---Begin DynamicTileAnalysis Constructor---\n");
162 maxCol = device.getTargetModel().columns();
163 maxRow = device.getTargetModel().rows();
165 pathfinder.initialize(maxCol, maxRow, device.getTargetModel());
173 for (PacketFlowOp pktFlowOp : device.getOps<PacketFlowOp>()) {
174 Region &r = pktFlowOp.getPorts();
175 Block &b = r.front();
176 SmallVector<std::pair<TileID, Port>, 4> sources;
178 for (Operation &Op : b.getOperations()) {
179 if (
auto pktSource = dyn_cast<PacketSourceOp>(Op)) {
180 auto srcTile = cast<TileOp>(pktSource.getTile().getDefiningOp());
182 {{srcTile.colIndex(), srcTile.rowIndex()}, pktSource.port()});
186 bool priorityFlow = pktFlowOp.getPriorityRoute().value_or(
false);
189 for (Operation &Op : b.getOperations()) {
190 if (
auto pktDest = dyn_cast<PacketDestOp>(Op)) {
191 auto dstTile = cast<TileOp>(pktDest.getTile().getDefiningOp());
192 Port dstPort = pktDest.port();
193 TileID dstCoords = {dstTile.colIndex(), dstTile.rowIndex()};
194 for (
auto &[srcCoords, srcPort] : sources) {
195 LLVM_DEBUG(llvm::dbgs()
196 <<
"\tAdding Packet Flow: (" << srcCoords.col <<
", "
197 << srcCoords.row <<
")"
198 << stringifyWireBundle(srcPort.bundle) << srcPort.channel
199 <<
" -> (" << dstCoords.col <<
", " << dstCoords.row <<
")"
200 << stringifyWireBundle(dstPort.bundle) << dstPort.channel
202 pathfinder.addFlow(srcCoords, srcPort, dstCoords, dstPort,
203 pktFlowOp.IDInt(), priorityFlow,
211 for (FlowOp flowOp : device.getOps<FlowOp>()) {
212 TileOp srcTile = cast<TileOp>(flowOp.getSource().getDefiningOp());
213 TileOp dstTile = cast<TileOp>(flowOp.getDest().getDefiningOp());
214 TileID srcCoords = {srcTile.colIndex(), srcTile.rowIndex()};
215 TileID dstCoords = {dstTile.colIndex(), dstTile.rowIndex()};
216 Port srcPort = {flowOp.getSourceBundle(), flowOp.getSourceChannel()};
217 Port dstPort = {flowOp.getDestBundle(), flowOp.getDestChannel()};
218 LLVM_DEBUG(llvm::dbgs()
219 <<
"\tAdding Flow: (" << srcCoords.col <<
", " << srcCoords.row
220 <<
")" << stringifyWireBundle(srcPort.bundle) << srcPort.channel
221 <<
" -> (" << dstCoords.col <<
", " << dstCoords.row <<
")"
222 << stringifyWireBundle(dstPort.bundle) << dstPort.channel
224 pathfinder.addFlow(srcCoords, srcPort, dstCoords, dstPort,
234 for (SwitchboxOp switchboxOp : device.getOps<SwitchboxOp>()) {
235 if (failed(
pathfinder.addFixedConnection(switchboxOp)))
236 return llvm::make_error<RoutingFailure>(
237 llvm::formatv(
"cannot add the fixed connections of the switchbox "
238 "at tile ({0}, {1})",
239 switchboxOp.colIndex(), switchboxOp.rowIndex()),
246 llvm::Expected<Routing> found =
pathfinder.findPaths(maxIterations);
248 return found.takeError();
253 coordToSwitchbox.clear();
254 coordToShimMux.clear();
255 for (
auto tileOp : device.getOps<TileOp>()) {
256 [[maybe_unused]]
bool fresh =
257 coordToTile.try_emplace(tileOp.getTileID(), tileOp).second;
260 for (
auto switchboxOp : device.getOps<SwitchboxOp>()) {
261 [[maybe_unused]]
bool fresh =
263 .try_emplace({switchboxOp.colIndex(), switchboxOp.rowIndex()},
268 for (
auto shimmuxOp : device.getOps<ShimMuxOp>()) {
269 [[maybe_unused]]
bool fresh =
271 .try_emplace({shimmuxOp.colIndex(), shimmuxOp.rowIndex()},
277 LLVM_DEBUG(llvm::dbgs() <<
"\t---End DynamicTileAnalysis Constructor---\n");
278 return llvm::Error::success();
282 TileOp &tileOp = coordToTile[{col, row}];
284 tileOp = TileOp::create(
286 cast<DeviceOp>(builder.getInsertionBlock()->getParentOp()).getLoc(),
292 return getTile(builder, tileId.col, tileId.row);
301 auto tileOp =
getTile(builder, col, row);
302 auto switchboxOp = SwitchboxOp::create(builder, tileOp.getLoc(), tileOp);
303 SwitchboxOp::ensureTerminator(switchboxOp.getConnections(), builder,
305 coordToSwitchbox[{col, row}] = switchboxOp;
313 auto tileOp =
getTile(builder, col, 0);
314 assert(tileOp.isShimNOCorPLTile());
315 auto shimMuxOp = ShimMuxOp::create(builder, tileOp.getLoc(), tileOp);
316 ShimMuxOp::ensureTerminator(shimMuxOp.getConnections(), builder,
318 coordToShimMux[{col, 0}] = shimMuxOp;
340 wireEdgesBegin.clear();
347 std::map<WireBundle, int> maxChannels;
348 auto intraconnect = [&](
int col,
int row) {
349 TileID coords = {col, row};
351 graph.try_emplace({coords, coords}, coords).first->second;
353 for (
int i = 0, e = getMaxEnumValForWireBundle() + 1; i < e; ++i) {
354 WireBundle bundle = symbolizeWireBundle(i).value();
362 for (
int channel = 0; channel < channels; channel++) {
371 for (
int channel = 0; channel < channels; channel++) {
374 maxChannels[bundle] = channels;
378 auto isMuxed = [&](
Port p) {
381 {WireBundle::DMA, WireBundle::NOC, WireBundle::PLIO},
384 for (
auto [i, pIn] : llvm::enumerate(sb.
srcPorts))
385 for (
auto [j, pOut] : llvm::enumerate(sb.
dstPorts))
388 pOut.bundle, pOut.channel) ||
389 isMuxed(pIn) || isMuxed(pOut);
392 auto interconnect = [&](
int col,
int row,
int targetCol,
int targetRow,
393 WireBundle srcBundle, WireBundle dstBundle) {
394 TileID src = {col, row}, dst = {targetCol, targetRow};
396 graph.try_emplace({src, dst}, src, dst).first->second;
397 for (
int channel = 0; channel < maxChannels[srcBundle]; channel++) {
402 for (
size_t i = 0; i < sb.
srcPorts.size(); i++)
406 for (
int row = 0; row <= maxRow; row++) {
407 for (
int col = 0; col <= maxCol; col++) {
410 intraconnect(col, row);
415 interconnect(col, row, col, row - 1, WireBundle::South,
420 interconnect(col, row, col, row + 1, WireBundle::North,
425 interconnect(col, row, col - 1, row, WireBundle::West,
430 interconnect(col, row, col + 1, row, WireBundle::East,
440 Port dstPort, std::optional<int> packetId,
442 std::optional<mlir::Location> loc) {
443 auto pinnedIds = constraints.pinnedIds.find({srcCoords, srcPort});
444 if (constraints.pinned.count({srcCoords, srcPort}))
445 isPriorityFlow &= packetId && pinnedIds != constraints.pinnedIds.end() &&
446 pinnedIds->second.count(*packetId);
448 isPriorityFlow &= constraints.prioritize;
450 flowLocs[{srcCoords, srcPort}].try_emplace({dstCoords, dstPort}, *loc);
452 auto &ids = packetIdsTo[{{srcCoords, srcPort}, {dstCoords, dstPort}}];
453 if (!llvm::is_contained(ids, *packetId))
454 ids.push_back(*packetId);
456 priorityIds[{srcCoords, srcPort}].insert(*packetId);
459 PathEndPoint src{srcCoords, srcPort}, dst{dstCoords, dstPort};
460 auto flow = llvm::find_if(flows, [&](
const Flow &f) {
return f.
src == src; });
461 if (flow == flows.end()) {
464 Flow{packetId ? 0 : -1, isPriorityFlow, src, {dst}, packetId});
465 }
else if (isPriorityFlow) {
466 flow->isPriorityFlow =
true;
467 flow->dsts.insert(flow->dsts.begin(), dst);
469 flow->dsts.push_back(dst);
475std::optional<mlir::Location>
477 auto locs = flowLocs.find(src);
478 if (locs == flowLocs.end())
480 auto it = dst ? locs->second.find(*dst) : locs->second.begin();
481 if (it == locs->second.end())
486bool Pathfinder::shareAllChannels() {
487 shareChannels =
true;
491bool Pathfinder::capCrowdedFanOut() {
492 size_t capped = cappedTiles.size();
493 cappedTiles.insert(crowdedTiles.begin(), crowdedTiles.end());
494 return cappedTiles.size() > capped;
497std::map<PathEndPoint, std::set<int>> Pathfinder::idsBySource()
const {
498 std::map<PathEndPoint, std::set<int>> ids;
499 for (
const auto &[ends, sent] : packetIdsTo)
500 ids[ends.first].insert(sent.begin(), sent.end());
504bool Pathfinder::routeIdsApart() {
508 shareChannels =
false;
510 return llvm::any_of(idsBySource(),
511 [](
const auto &s) {
return s.second.size() > 1; });
514bool Pathfinder::splitSharedIds() {
518 shareChannels =
false;
520 std::map<PathEndPoint, std::set<int>> ids = idsBySource();
521 for (
const auto &[src, srcIds] : ids)
522 for (
const auto &[other, otherIds] : ids) {
523 const std::set<int> &theirs = otherIds;
524 if (!(src == other) &&
525 llvm::any_of(srcIds, [&](
int id) {
return theirs.count(
id); }) &&
526 llvm::any_of(srcIds, [&](
int id) {
return !theirs.count(
id); }))
534bool Pathfinder::stopMeeting() {
539 shareChannels =
false;
548bool Pathfinder::rotateLeads() {
549 std::map<PathEndPoint, std::map<PathEndPoint, std::set<int>>> to;
550 for (
const auto &[ends, ids] : packetIdsTo)
551 to[ends.first][ends.second].insert(ids.begin(), ids.end());
553 auto spans = [&](
const PathEndPoint &a,
const PathEndPoint &b) {
554 std::map<int, int> shared;
555 for (
const auto &[dst, ids] : to[a])
556 if (to[b].count(dst))
558 if (++shared[
id] > 1)
562 SmallVector<PathEndPoint, 8> srcs(llvm::make_first_range(to));
563 llvm::IntEqClasses clusters(srcs.size());
564 for (
auto [i, a] : llvm::enumerate(srcs))
565 for (
auto [j, b] : llvm::enumerate(srcs))
566 if (i < j && spans(a, b) && spans(b, a))
569 std::vector<SmallVector<PathEndPoint, 4>> members(clusters.getNumClasses());
570 for (
auto [i, src] : llvm::enumerate(srcs))
571 members[clusters[i]].push_back(src);
575 for (
const auto &cluster : members)
576 if (leadStep < cluster.size())
577 leads.insert(cluster[leadStep]);
578 return !leads.empty();
585bool Pathfinder::meetAhead() {
593enum class RelaxStep {
604constexpr RelaxStep relaxLadder[] = {
605 RelaxStep::ShareChannels, RelaxStep::CapCrowdedTiles,
606 RelaxStep::RouteIdsApart, RelaxStep::ShareChannels,
607 RelaxStep::CapCrowdedTiles, RelaxStep::SplitSharedIds,
608 RelaxStep::ShareChannels, RelaxStep::CapCrowdedTiles,
609 RelaxStep::RotateLeads, RelaxStep::MeetAhead,
610 RelaxStep::StopMeeting};
611constexpr size_t rotateLeadsStep = std::size(relaxLadder) - 3;
615 if (!packetsFailed) {
616 LLVM_DEBUG(llvm::dbgs() <<
"No packet stream crosses an overused link\n");
619 while (relaxStep < std::size(relaxLadder)) {
620 switch (relaxLadder[relaxStep++]) {
621 case RelaxStep::ShareChannels:
622 if (shareAllChannels()) {
623 LLVM_DEBUG(llvm::dbgs() <<
"Relax: share channels\n");
627 case RelaxStep::CapCrowdedTiles:
628 if (capCrowdedFanOut()) {
629 LLVM_DEBUG(llvm::dbgs() <<
"Relax: cap crowded tiles\n");
633 case RelaxStep::RouteIdsApart:
634 if (routeIdsApart()) {
635 LLVM_DEBUG(llvm::dbgs() <<
"Relax: route ids apart\n");
640 relaxStep = rotateLeadsStep;
642 case RelaxStep::SplitSharedIds:
643 if (splitSharedIds()) {
644 LLVM_DEBUG(llvm::dbgs() <<
"Relax: split shared ids\n");
647 relaxStep = rotateLeadsStep;
649 case RelaxStep::RotateLeads:
654 LLVM_DEBUG(llvm::dbgs()
655 <<
"Relax: route cluster member " << leadStep <<
" first\n");
659 case RelaxStep::MeetAhead:
661 LLVM_DEBUG(llvm::dbgs() <<
"Relax: meet ahead of same-id partners\n");
665 case RelaxStep::StopMeeting:
667 LLVM_DEBUG(llvm::dbgs() <<
"Relax: stop meeting\n");
679 for (
auto &flow : flows)
680 llvm::sort(flow.dsts);
684 llvm::IntEqClasses groups(flows.size());
685 std::map<PathEndPoint, unsigned> firstTo;
686 for (
auto [k, flow] : llvm::enumerate(flows)) {
687 if (flow.packetGroupId < 0)
690 auto [it, fresh] = firstTo.try_emplace(dst, k);
692 groups.join(k, it->second);
695 llvm::DenseMap<unsigned, int> groupOf;
696 for (
auto [k, flow] : llvm::enumerate(flows))
697 if (flow.packetGroupId >= 0)
701 : groupOf.try_emplace(groups.findLeader(k), groupOf.size())
704 auto flowRank = [](
const Flow &flow) {
705 if (flow.isPriorityFlow)
707 if (flow.packetGroupId >= 0)
711 llvm::sort(flows, [&](
const Flow &lhs,
const Flow &rhs) {
712 return std::make_tuple(flowRank(lhs), !leads.count(lhs.
src), lhs.
src) <
713 std::make_tuple(flowRank(rhs), !leads.count(rhs.
src), rhs.
src);
719 if (src.bundle == WireBundle::DMA)
720 return src.channel == 0 ? 3 : 7;
721 if (src.bundle == WireBundle::NOC)
722 return src.channel >= 2 ? src.channel + 4 : src.channel + 2;
728 if (dst.bundle == WireBundle::DMA)
729 return dst.channel == 0 ? 2 : 3;
730 if (dst.bundle == WireBundle::NOC)
731 return dst.channel + 2;
736 int col = switchboxOp.colIndex();
737 int row = switchboxOp.rowIndex();
738 TileID coords = {col, row};
739 auto &sb = graph[std::make_pair(coords, coords)];
744 llvm::SmallVector<std::pair<int, int>, 8> reserved;
745 llvm::SmallDenseSet<int, 8> claimedDsts;
746 for (ConnectOp connectOp : switchboxOp.getOps<ConnectOp>()) {
747 int srcIdx = sb.srcIndex(connectOp.sourcePort());
748 int dstIdx = sb.dstIndex(connectOp.destPort());
751 if (srcIdx < 0 || dstIdx < 0 || !sb.at(srcIdx, dstIdx).available ||
752 !claimedDsts.insert(dstIdx).second) {
755 reserved.emplace_back(srcIdx, dstIdx);
764 llvm::SmallVector<int, 8> reservedMasterDsts;
765 for (MasterSetOp masterSetOp : switchboxOp.getOps<MasterSetOp>()) {
766 int dstIdx = sb.dstIndex(masterSetOp.destPort());
769 if (dstIdx < 0 || !claimedDsts.insert(dstIdx).second) {
772 reservedMasterDsts.push_back(dstIdx);
779 for (
auto [srcIdx, dstIdx] : reserved) {
780 for (
size_t j = 0; j < sb.dstPorts.size(); j++)
781 sb.at(srcIdx, j).available =
false;
782 for (
size_t i = 0; i < sb.srcPorts.size(); i++)
783 sb.at(i, dstIdx).available =
false;
787 for (
int dstIdx : reservedMasterDsts)
788 for (
size_t i = 0; i < sb.srcPorts.size(); i++)
789 sb.at(i, dstIdx).available =
false;
792 if (switchboxOp.getTileOp().isShimNOCorPLTile()) {
793 auto isMuxed = [](
Port p) {
794 return llvm::is_contained(
795 {WireBundle::DMA, WireBundle::NOC, WireBundle::PLIO}, p.bundle);
797 llvm::SmallDenseSet<int, 8> southDsts, southSrcs;
798 for (
int dstIdx : claimedDsts)
799 if (sb.dstPorts[dstIdx].bundle == WireBundle::South)
800 southDsts.insert(sb.dstPorts[dstIdx].channel);
801 for (
auto [srcIdx, dstIdx] : reserved)
802 if (sb.srcPorts[srcIdx].bundle == WireBundle::South)
803 southSrcs.insert(sb.srcPorts[srcIdx].channel);
804 for (
size_t j = 0; j < sb.dstPorts.size(); j++)
805 if (isMuxed(sb.dstPorts[j]) &&
807 for (
size_t i = 0; i < sb.srcPorts.size(); i++)
808 sb.at(i, j).available =
false;
809 for (
size_t i = 0; i < sb.srcPorts.size(); i++)
810 if (isMuxed(sb.srcPorts[i]) &&
812 for (
size_t j = 0; j < sb.dstPorts.size(); j++)
813 sb.at(i, j).available =
false;
815 for (PacketRulesOp rulesOp : switchboxOp.getOps<PacketRulesOp>()) {
816 int srcIdx = sb.srcIndex(rulesOp.sourcePort());
819 sb.packetOnlySrc.set(srcIdx);
825 auto it = graph.find({coords, coords});
826 if (it == graph.end())
829 for (
size_t i = 0; i < sb.
srcPorts.size(); i++)
830 for (
size_t j = 0; j < sb.
dstPorts.size(); j++)
835 auto it = graph.find({coords, coords});
836 if (it == graph.end())
842 for (
size_t i = 0; i < sb.
srcPorts.size(); i++)
846static constexpr double INF = std::numeric_limits<double>::max();
849enum Color : int8_t { WHITE = 0, GRAY = 1, BLACK = 2 };
852int Pathfinder::getOrAddNodeId(
const PathEndPoint &pep) {
853 auto it = nodeIds.find(pep);
854 if (it != nodeIds.end())
856 int id =
static_cast<int>(nodes.size());
858 nodes.push_back(pep);
868void Pathfinder::buildRoutingGraph() {
872 for (
auto &f : flows) {
873 getOrAddNodeId(f.src);
874 for (
auto &d : f.dsts)
880 for (
size_t id = 0;
id < nodes.size();
id++) {
881 PathEndPoint src = nodes[id];
884 std::vector<PathEndPoint> dests;
886 if (intraIt != graph.end()) {
887 auto &sb = intraIt->second;
888 for (
auto [i, pIn] : llvm::enumerate(sb.srcPorts))
889 for (
auto [j, pOut] : llvm::enumerate(sb.dstPorts))
890 if (pIn == src.
port && sb.at(i, j).available)
891 dests.emplace_back(src.
coords, pOut);
893 std::pair<TileID, Port> neighbors[] = {
895 {WireBundle::North, src.
port.channel}},
897 {WireBundle::East, src.
port.channel}},
899 {WireBundle::South, src.
port.channel}},
901 {WireBundle::West, src.
port.channel}}};
902 for (
const auto &[neighborCoords, neighborPort] : neighbors) {
903 auto nIt = graph.find({src.
coords, neighborCoords});
904 if (nIt != graph.end() &&
906 llvm::is_contained(nIt->second.dstPorts, neighborPort))
907 dests.emplace_back(neighborCoords, neighborPort);
911 std::vector<Edge> edges;
912 edges.reserve(dests.size());
913 for (
auto &dest : dests) {
914 auto &sb = graph.at({src.
coords, dest.coords});
915 int i = sb.srcIndex(src.
port);
916 int j = sb.dstIndex(dest.port);
917 assert(i >= 0 && j >= 0);
918 int destId = getOrAddNodeId(dest);
919 edges.push_back(Edge{destId, &sb, i, j});
922 std::stable_partition(edges.begin(), edges.end(), [](
const Edge &e) {
923 return e.sb->srcCoords == e.sb->dstCoords;
925 if (wireEdgesBegin.size() < nodes.size())
926 wireEdgesBegin.resize(nodes.size());
927 wireEdgesBegin[id] = wires - edges.begin();
930 if (adjacency.size() < nodes.size())
931 adjacency.resize(nodes.size());
932 adjacency[id] = std::move(edges);
934 size_t n = nodes.size();
935 if (adjacency.size() < n)
937 wireEdgesBegin.resize(n);
941 distance.assign(2 * n, INF);
942 indexInHeap.assign(2 * n, 0);
943 colors.assign(2 * n, WHITE);
944 preds.assign(2 * n, -1);
945 predEdge.assign(2 * n, Edge{-1,
nullptr, 0, 0});
949double Pathfinder::edgeWeight(
const Edge &e, std::optional<int> packetId,
950 const llvm::BitVector *avoid,
951 const llvm::BitVector *avoidBranch)
const {
952 const SwitchboxConnect::Cell &cell = e.sb->at(e.i, e.j);
958 if (e.sb->srcCoords == e.sb->dstCoords)
959 for (
const llvm::BitVector *flows : {avoid, avoidBranch})
960 if (flows && llvm::any_of(e.sb->unitFlows(e.j),
961 [&](
int f) { return flows->test(f); }))
962 w += conflictSharePenalty;
969void Pathfinder::dijkstraShortestPaths(
970 ArrayRef<int> seeds, ArrayRef<double> seedCosts,
971 std::optional<int> packetId,
const llvm::BitVector *avoid,
972 const llvm::DenseMap<int, llvm::BitVector> *branchAvoid,
973 const llvm::DenseSet<int> *stops, ArrayRef<int> targets,
974 llvm::function_ref<
bool(
int,
int)> mayCross) {
975 llvm::fill(distance, INF);
976 llvm::fill(colors,
static_cast<int8_t
>(WHITE));
977 llvm::fill(preds, -1);
978 llvm::fill(indexInHeap, uint64_t{0});
980 using MutableQueue = d_ary_heap_indirect<
982 std::vector<uint64_t> &,
983 std::vector<double> &,
985 MutableQueue Q(distance, indexInHeap);
987 for (
auto [seed, cost] : llvm::zip_equal(seeds, seedCosts)) {
988 distance[seed] = cost;
993 SmallVector<int, 8> unsettled(targets);
997 if (llvm::is_contained(unsettled, s)) {
998 llvm::erase(unsettled, s);
999 if (unsettled.empty())
1002 if (stops && stops->count(s)) {
1010 const bool sIsOut = (s & 1) == Out;
1011 const llvm::BitVector *avoidBranch =
nullptr;
1013 if (
auto it = branchAvoid->find(s); it != branchAvoid->end())
1014 avoidBranch = &it->second;
1015 ArrayRef<Edge> out = adjacency[stateNode(s)];
1016 size_t wires = wireEdgesBegin[stateNode(s)];
1017 const bool isIntra = !sIsOut;
1018 for (
const Edge &e :
1019 sIsOut ? out.drop_front(wires) : out.take_front(wires)) {
1020 if ((isIntra && !packetId && e.sb->packetOnlySrc[e.i]) ||
1021 (isIntra && packetId && e.sb->circuitOnlyDst[e.j]))
1023 int dst = stateId(e.dst, isIntra ? Out : In);
1024 if (colors[dst] == BLACK || (isIntra && mayCross && !mayCross(s, dst)))
1026 double w = edgeWeight(e, packetId, avoid, avoidBranch);
1027 if (distance[s] + w >= distance[dst])
1029 distance[dst] = distance[s] + w;
1032 if (colors[dst] == WHITE) {
1048 SmallVector<int, 4>
idsTo(
int flow,
int dstState)
const;
1050 int splitPart(
int flow,
const std::set<int> &ids);
1061 std::map<PathEndPoint, SmallVector<int, 2>>
partsOf;
1076 std::set<std::pair<std::pair<PathEndPoint, PathEndPoint>, std::set<int>>>
1083 std::vector<llvm::DenseMap<int, std::pair<int, Edge>>>
treeOf;
1101 std::tie(other.
at, other.
a, other.
b, other.
apart);
1127 std::set<std::pair<int, int>>
met;
1141 bool mayLeave(ArrayRef<int> masters,
int next)
const;
1142 bool reorder(
int later,
int earlier,
bool again =
false);
1143 void splitOwnIds(
const std::pair<PathEndPoint, PathEndPoint> &pair);
1152 for (
auto [k, f] : llvm::enumerate(
parts)) {
1154 flowDsts.insert(f.dsts.begin(), f.dsts.end());
1156 for (
auto [k, f] : llvm::enumerate(
parts))
1158 for (
const auto &[ends, ids] :
pf.packetIdsTo)
1159 flowIds[
partsOf.at(ends.first).front()].insert(ids.begin(), ids.end());
1164 for (
size_t k = 0, n =
parts.size(); k < n; k++) {
1165 if (!isPinned(parts[k]))
1167 const PathEndPoint &src = parts[k].src;
1168 const std::set<int> &prioritized = pf.priorityIds.at(src);
1169 std::set<PathEndPoint> treeDsts;
1170 std::map<int, std::set<PathEndPoint>> dstsOf;
1171 for (const auto &[ends, ids] : pf.packetIdsTo)
1172 if (ends.first == src)
1174 (prioritized.count(id) ? treeDsts : dstsOf[id]).insert(ends.second);
1175 std::set<int> others;
1176 for (const auto &[id, dsts] : dstsOf)
1177 if (!prioritized.count(id) && dsts != treeDsts)
1179 if (!others.empty())
1180 splitPart(k, others);
1182 for (
const auto &[src, tree] :
pf.constraints.pinned) {
1183 std::map<PathEndPoint, SmallVector<int, 4>> sets;
1184 for (const TreeHop &h : tree) {
1185 auto to = pf.nodeIds.find(h.to);
1186 if (h.from.coords == h.to.coords && to != pf.nodeIds.end())
1187 sets[h.from].push_back(stateId(to->second, Out));
1189 for (
auto &[_, set] : sets) {
1200 if (!again && (
reordered.count({earlier, later}) ||
1201 !
reordered.insert({later, earlier}).second))
1204 if (!llvm::is_contained(group, earlier))
1206 group.erase(llvm::find(group, later));
1207 group.insert(llvm::find(group, earlier), later);
1214 const std::pair<PathEndPoint, PathEndPoint> &pair) {
1215 for (
auto [src, other] : {pair, std::pair{pair.second, pair.first}}) {
1216 auto srcParts =
partsOf.find(src);
1217 auto otherParts =
partsOf.find(other);
1220 std::set<int> otherIds;
1221 for (
int k : otherParts->second)
1223 for (
int k : SmallVector<int, 2>(srcParts->second)) {
1226 if (!otherIds.count(
id))
1228 if (!
parts[k].isPriorityFlow && !own.empty() &&
1229 own.size() <
flowIds[k].size())
1239 llvm::none_of(masters, [&](
int m) { return priorityMasters.count(m); }))
1241 return llvm::any_of(
prioritySets, [&](
const SmallVector<int, 4> &set) {
1242 return llvm::is_contained(set, next) && llvm::all_of(masters, [&](
int m) {
1243 return llvm::is_contained(set, m);
1257 int dstState)
const {
1258 SmallVector<int, 4> ids;
1260 pf.packetIdsTo.find({
parts[flow].src,
pf.nodes[stateNode(dstState)]});
1261 if (it !=
pf.packetIdsTo.end())
1262 for (
int id : it->second)
1271 for (
size_t a = 0; a <
parts.size(); a++)
1272 for (
size_t b = 0; b <
parts.size(); b++) {
1274 bool same = llvm::any_of(
flowIds[a],
1275 [&](
int id) {
return flowIds[b].count(
id); });
1278 if (a < b &&
parts[a].packetId &&
parts[b].packetId &&
1281 (
pf.constraints.conflict &&
1291 int part =
parts.size();
1294 llvm::dbgs() <<
"\t\tRouting ids";
1296 llvm::dbgs() <<
' ' << id;
1304 auto it =
pf.packetIdsTo.find({f.
src, p});
1305 return it !=
pf.packetIdsTo.end() &&
1306 llvm::any_of(it->second, [&](
int i) { return flowIds[k].count(i); });
1308 llvm::erase_if(f.
dsts,
1309 [&](
const PathEndPoint &p) { return !carries(part, p); });
1310 llvm::erase_if(
parts[flow].dsts,
1311 [&](
const PathEndPoint &p) {
return !carries(flow, p); });
1313 std::optional<int> &flowId =
parts[flow].packetId;
1314 if (flowId && ids.count(*flowId))
1315 flowId = *
flowIds[flow].begin();
1316 auto prioritized = [&](
const std::set<int> &carried) {
1317 auto prio =
pf.priorityIds.find(f.
src);
1318 return prio !=
pf.priorityIds.end() && llvm::any_of(carried, [&](
int id) {
1319 return prio->second.count(
id);
1323 parts[flow].isPriorityFlow = prioritized(
flowIds[flow]);
1332 for (
auto [a, b] : std::set<std::pair<int, int>>(
noJoin))
1333 if (a == flow || b == flow)
1334 noJoin.insert({a == flow ? part : a, b == flow ? part : b});
1339 for (
auto [at, a, b, apart] :
splitsOf[flow])
1340 if (ids.count(a) != ids.count(b) &&
1341 flowIds[flow].count(ids.count(a) ? b : a)) {
1354 for (
size_t i = 0; i < sb.
srcPorts.size(); i++)
1355 for (
size_t j = 0; j < sb.
dstPorts.size(); j++) {
1359 if (xbar == graph.end())
1365 for (
size_t row = 0; row < x.
srcPorts.size(); row++)
1372llvm::Error Pathfinder::explainNoRouting(
const RouteState &st)
const {
1378 return c.usedCapacity > maxCircuitStreamCapacity;
1381 auto link = [](
const SwitchboxConnect &sb) -> std::string {
1382 return llvm::formatv(
"from tile ({0}, {1}) to ({2}, {3})", sb.
srcCoords.col,
1385 const Flow *prioritized =
nullptr;
1386 llvm::SetVector<const SwitchboxConnect *> held;
1387 for (
auto [k, f] : llvm::enumerate(st.parts)) {
1388 if (!st.isPinned(f))
1390 prioritized = prioritized ? prioritized : &f;
1391 for (
const auto &[_, hop] : st.treeOf[k]) {
1392 if (overused(*hop.second.sb)) {
1393 return llvm::make_error<PinnedRoutingFailure>(
1395 ", and it holds a channel " + link(*hop.second.sb) +
1396 " the other flows need.");
1398 if (hop.second.sb->srcCoords != hop.second.sb->dstCoords)
1399 held.insert(hop.second.sb);
1402 if (prioritized && llvm::any_of(graph, [&](
const auto &entry) {
1403 return overused(entry.second);
1405 return llvm::make_error<PinnedRoutingFailure>(
1408 ", and the router found no routing for the other flows around the "
1409 "channels it holds " +
1411 llvm::map_range(llvm::make_pointee_range(held), link))) +
1415 if (!checkReason.empty())
1416 return llvm::make_error<RoutingFailure>(checkReason);
1420 const SwitchboxConnect *worst =
nullptr;
1421 int worstI = 0, worstJ = 0;
1422 std::pair<bool, int> worstRank{
false, 0};
1423 for (
const auto &[_, sb] : graph) {
1424 std::optional<bool> roomless;
1425 for (
size_t i = 0; i < sb.
srcPorts.size(); i++)
1426 for (
size_t j = 0; j < sb.
dstPorts.size(); j++) {
1430 roomless = !hasRoom(sb);
1432 if (rank > worstRank) {
1441 return llvm::make_error<RoutingFailure>(
"");
1443 std::vector<std::string> users;
1444 for (
const auto &[src, settings] : st.routing.settings) {
1445 auto it = settings.find(worst->
srcCoords);
1446 if (it == settings.end())
1448 const SwitchSetting &s = it->second;
1450 for (
size_t k = 0; k < s.
dsts.size() && !uses; k++)
1459 crossbar ? llvm::formatv(
"the connection from {0} to {1} at tile ({2}, "
1465 :
"the links " + link(*worst);
1467 return llvm::make_error<RoutingFailure>(
1468 "the router found no routing that fits " + where +
".");
1469 return llvm::make_error<RoutingFailure>(
1470 "the flows from " +
joinNames(users) +
" need " + where +
1471 ", and the router found no routing that fits them.");
1475 bool rows = a.col == b.col;
1476 return {rows, rows ? std::min(a.row, b.row) : std::min(a.col, b.col),
1477 rows ? b.row > a.row : b.col > a.col};
1480llvm::Error Pathfinder::cutOverflow()
const {
1486 auto onDevice = [&](
TileID t) {
return t.col < columns && t.row < rows; };
1487 std::map<std::tuple<bool, int, bool>,
size_t> channels;
1488 for (
const auto &[ends, sb] : graph) {
1489 const auto &[a, b] = ends;
1490 auto xbar = graph.find({a, a});
1491 if (a == b || !onDevice(a) || !onDevice(b) || xbar == graph.end())
1493 std::tuple<bool, int, bool> cut =
boundaryOf(a, b);
1494 const SwitchboxConnect &x = xbar->second;
1502 llvm::any_of(llvm::seq<size_t>(0, x.
srcPorts.size()),
1503 [&](
size_t i) { return x.at(i, k).available; }))
1507 for (
const auto &[cut, available] : channels) {
1508 bool rows = std::get<0>(cut), up = std::get<2>(cut);
1509 int below = std::get<1>(cut);
1510 auto low = [&](
TileID t) {
return (rows ? t.row : t.col) <= below; };
1511 std::vector<std::string> circuits;
1512 bool packets =
false;
1513 for (
const Flow &f : flows) {
1514 if (low(f.src.coords) != up ||
1515 llvm::none_of(f.dsts, [&](
const PathEndPoint &d) {
1516 return low(d.coords) != up;
1525 if (packets && constraints.apartAcross && available > circuits.size())
1526 apart = constraints.apartAcross(low, up, available - circuits.size());
1528 circuits.size() + std::max<size_t>(packets, apart.
flows.size());
1529 LLVM_DEBUG(llvm::dbgs() <<
"Cut " << (rows ?
"row " :
"column ") << below
1530 << (up ?
" up" :
" down") <<
": " << needed
1531 <<
" of " << available <<
" channels\n");
1532 if (needed <= available)
1534 int from = up ? below : below + 1, to = up ? below + 1 : below;
1535 auto channel = [](
size_t n) {
return n == 1 ?
"channel" :
"channels"; };
1537 circuits.empty() ?
"" :
"the circuit flows from " +
joinNames(circuits);
1538 if (apart.
flows.size() > 1)
1540 ", no two of which can share an arbiter,";
1543 circuits.empty() ?
"the packet flows" : who +
", with packet flows,";
1545 apart.
flows.size() > 1 ?
" For example, " + apart.
why :
"";
1546 return llvm::make_error<RoutingFailure>(llvm::formatv(
1547 "{0} cross from {1} {2} to {1} {3}, which takes {4} {5} across, and "
1548 "it has {6} {7}.{8}",
1549 who, rows ?
"row" :
"column", from, to, needed, channel(needed),
1550 available, channel(available), why));
1552 return llvm::Error::success();
1562 return stateId(
pf.nodeIds.at(p), Out);
1564 bool isPending(
int state)
const;
1565 void reach(ArrayRef<int> dsts);
1566 bool joinable(
int at, ArrayRef<int> dsts)
const;
1569 void meet(
int owner);
1570 void search(
const llvm::DenseSet<int> &drop, ArrayRef<int> targets,
1571 const llvm::DenseSet<int> &off = {});
1572 bool trace(
int state);
1573 llvm::DenseSet<int> splitOff(
int dst)
const;
1574 llvm::DenseSet<int> trunkOff(
int dst)
const;
1575 llvm::Error placePinned();
1579 bool join(
int state,
int predId,
const Edge &e);
1589 const std::vector<TreeHop> *
pinned =
nullptr;
1598 llvm::MapVector<int, std::pair<int, Edge>>
planned;
1613 llvm::DenseMap<int, SmallVector<int, 4>>
joins;
1624 llvm::MapVector<int, std::pair<SmallVector<int, 4>, std::set<int>>>
1636 SmallVector<std::pair<int, const SmallVector<int, 4> *>, 2>
joinedAt;
1649 int srcId =
pf.nodeIds.at(
part.src);
1650 tree.push_back(stateId(srcId, In));
1652 st.processedStamp[
tree.front()] = ++
st.curStamp;
1660 int self = stateId(srcId, Out);
1661 if (endPoint == part.src && !st.priorityMasters.count(self) &&
1662 llvm::any_of(pf.adjacency[srcId],
1663 [&](const Edge &e) { return e.dst == srcId; })) {
1670 for (
auto it = st.
trunked.lower_bound({flow, 0});
1674 SmallVector<int, 4> shared;
1676 if (llvm::is_contained(part.dsts, dst))
1677 shared.push_back(dstState(dst));
1678 if (shared.size() > 1)
1679 trunkDsts.insert(shared.begin(), shared.end());
1682 for (
const auto &[state, _] : st.
treeOf[other])
1683 if ((state & 1) == Out && pf.nodes[stateNode(state)].coords == at)
1684 partOff.insert(state);
1696 return llvm::is_contained(dsts,
dstState(p));
1704 llvm::all_of(dsts, [&](
int dst) {
return isPending(dst); });
1708 auto shared = [&](ArrayRef<int> ids,
int other) {
1709 std::set<int> common;
1711 if (
st.flowIds[other].count(
id))
1715 for (
int other :
st.sameId[
flow]) {
1717 const Flow &o =
st.parts[other];
1719 if (!
st.treeDsts[other].empty() && llvm::is_contained(o.
dsts, o.
src) &&
1722 for (
int dst :
st.treeDsts[other]) {
1723 std::set<int> common = shared(
st.idsTo(other, dst),
flow);
1732 !
st.noJoin.count({flow, other}) &&
1733 (!
part.isPriorityFlow ||
st.parts[other].isPriorityFlow);
1734 bool agree = canJoin && !(
pf.constraints.conflict &&
1735 pf.constraints.conflict(
part.src, common, o.
src,
1736 st.flowIds[other]));
1743 if (canJoin && !agree &&
isPending(dst) &&
1744 !
pf.constraints.conflict(
part.src, common, o.
src, common))
1746 for (
auto it =
st.treeOf[other].find(dst); it !=
st.treeOf[other].end();
1747 it =
st.treeOf[other].find(it->second.first)) {
1748 int up = it->second.first;
1749 if ((up & 1) != Out)
1754 if (!llvm::is_contained(
joins[up], dst))
1755 joins[up].push_back(dst);
1756 if (!llvm::is_contained(
joinOwners[up], other))
1766 if (!
part.packetId ||
part.isPriorityFlow)
1768 llvm::DenseSet<int> sameIdDsts;
1769 for (
int other :
st.sameId[
flow]) {
1776 for (
auto [other, o] : llvm::enumerate(
st.parts)) {
1778 if (k ==
flow || o.src ==
part.src || !o.packetId || o.isPriorityFlow ||
1779 st.treeDsts[k].empty() || llvm::is_contained(
st.sameId[
flow], k) ||
1780 st.noJoin.count({flow, k}))
1782 SmallVector<int, 4> dsts;
1783 for (
int dst :
st.treeDsts[k])
1784 if (
isPending(dst) && !sameIdDsts.count(dst) &&
st.treeOf[k].count(dst))
1785 dsts.push_back(dst);
1786 if (dsts.size() < 2)
1788 if (!
st.conflicting[
flow].test(k)) {
1795 std::set<int> meeting, rest;
1796 for (
int dst : dsts)
1797 for (
int id :
st.idsTo(
flow, dst))
1799 for (
int id :
st.flowIds[
flow])
1800 if (!meeting.count(
id))
1802 if (!rest.empty() &&
pf.constraints.conflict &&
1803 !
st.apartSources.count(std::minmax(
part.src, o.src)) &&
1804 !
pf.constraints.conflict(
part.src, meeting, o.src,
st.flowIds[k]))
1805 blockedIds[k] = {std::move(dsts), std::move(rest)};
1821 auto spans = [&](
int k, ArrayRef<int> dsts) {
1822 return llvm::any_of(
st.flowIds[k], [&](
int id) {
1823 return llvm::count_if(dsts, [&](int dst) {
1824 return llvm::is_contained(st.idsTo(k, dst), id);
1828 auto mustMeet = [&](
int other) {
1829 return spans(flow, sharedDsts[other]) && spans(other, sharedDsts[other]);
1833 for (
const auto &[other, dsts] : blockedDsts)
1834 if (spans(flow, dsts) && spans(other, dsts))
1835 st.meetBlocked.insert({part.src, st.
parts[other].src});
1836 for (
const auto &[other, blocked] : blockedIds)
1837 if (spans(flow, blocked.first) && spans(other, blocked.first))
1838 st.
meetSplits.insert({{part.src, st.parts[other].src}, blocked.second});
1839 SmallVector<int, 4> owners;
1840 for (
int other : llvm::make_first_range(sharedDsts))
1841 if (!disagree.count(other) && mustMeet(other))
1842 owners.push_back(other);
1843 llvm::stable_sort(owners, [&](
int a,
int b) {
1844 return sharedDsts[a].size() > sharedDsts[b].size();
1846 for (
int owner : owners) {
1847 llvm::erase_if(sharedDsts[owner], [&](
int dst) {
return !isPending(dst); });
1848 if (mustMeet(owner))
1854 st.unmet.insert({
flow, owner});
1856 bool other =
foreign.count(owner);
1857 const auto &t =
st.treeOf[owner];
1858 const Flow &o =
st.parts[owner];
1859 int root = stateId(
pf.nodeIds.at(o.
src), In);
1861 SmallVector<SmallVector<int, 16>, 4> paths;
1863 SmallVector<int, 16> &path = paths.emplace_back(1, dst);
1864 for (
auto it = t.find(dst); it != t.end(); it = t.find(it->second.first))
1865 path.push_back(it->second.first);
1866 if (path.size() == 1)
1867 path.push_back(root);
1868 if (path.back() != root)
1870 std::reverse(path.begin(), path.end());
1873 while (llvm::all_of(paths, [&](
const auto &path) {
1874 return trunk + 1 < path.size() && path[trunk] == paths[0][trunk];
1879 SmallVector<std::pair<int, Edge>, 4> hops;
1883 SmallVector<Meeting, 8> meetings;
1884 SmallVector<int, 8> targets;
1886 auto below = [&](
size_t k) {
1887 llvm::MapVector<int, std::pair<int, Edge>> hops;
1888 for (
const auto &path : paths)
1889 for (
size_t l = k + 1; l + 1 < path.size(); l++)
1890 hops.insert({path[l + 1], t.find(path[l + 1])->second});
1893 for (
size_t k = 0; k < trunk; k++) {
1894 int at = paths[0][k];
1897 SetVector<int> next;
1898 for (
const auto &path : paths)
1899 next.insert(path[k + 1]);
1900 if (!other && llvm::any_of(next, [&](
int s) {
1904 auto taken = [&](
int s) {
1905 return st.processedStamp[s] ==
st.curStamp ||
stops.count(s) ||
1908 if (other && (llvm::any_of(next, taken) ||
1909 llvm::any_of(below(k), [&](
const auto &hop) {
1910 const Edge &e = hop.second.second;
1911 return taken(hop.first) ||
1916 SmallVector<int, 4> leaving;
1917 if (llvm::any_of(next, [&](
int s) {
1918 bool ok =
st.mayLeave(leaving, s);
1919 leaving.push_back(s);
1923 TileID tile =
pf.nodes[stateNode(at)].coords;
1924 auto sb =
pf.graph.find({tile, tile});
1925 if (sb ==
pf.graph.end())
1928 auto node =
pf.nodeIds.find({tile, port});
1929 if (node ==
pf.nodeIds.end())
1931 int in = stateId(node->second, In);
1932 auto taken =
st.meetingPorts.find({owner, in});
1933 if (in == at || t.count(in) ||
1934 (taken !=
st.meetingPorts.end() && !(taken->second ==
part.src)))
1936 Meeting m{in, {}, 0, k};
1938 for (
const Edge &e :
pf.adjacency[node->second])
1939 if (e.dst == stateNode(s) && e.sb == &sb->second &&
1941 m.hops.push_back({s, e});
1942 m.cost +=
pf.edgeWeight(e,
part.packetId,
avoid,
nullptr);
1945 if (m.hops.size() == next.size()) {
1946 meetings.push_back(std::move(m));
1947 targets.push_back(in);
1951 if (meetings.empty())
1953 llvm::DenseSet<int> off;
1955 for (
const auto &[s, _] : below(0))
1957 search({}, targets, off);
1958 const Meeting *best =
nullptr;
1959 for (
const Meeting &m : meetings)
1960 if (
pf.distance[m.in] < INF &&
1962 pf.distance[m.in] + m.cost <
pf.distance[best->in] + best->cost))
1964 if (!best || !
trace(best->in))
1966 st.unmet.erase({
flow, owner});
1967 st.meetingPorts.try_emplace({owner, best->in},
part.src);
1968 st.met.insert({
flow, owner});
1970 auto add = [&](
int s,
int from,
const Edge &e,
int depth) {
1971 planned.insert({s, {from, e}});
1973 st.processedStamp[s] =
st.curStamp;
1977 for (
const auto &[s, e] : best->hops) {
1978 add(s, best->in, e, hops);
1980 st.joinedHops[
flow].push_back({owner, e});
1988 const SmallVector<int, 4> &dsts =
joins[s];
1995 for (
const auto &[s, hop] : below(best->at)) {
1996 const auto &[from, e] = hop;
1998 st.joinedHops[
flow].push_back({owner, e});
2009 ArrayRef<int> targets,
2010 const llvm::DenseSet<int> &off) {
2012 llvm::DenseMap<int, llvm::BitVector> onArbiter;
2014 for (
const auto &[state, hop] :
planned) {
2015 const auto &[from, e] = hop;
2016 if (e.sb->srcCoords != e.sb->dstCoords || drop.count(state))
2018 llvm::BitVector &away =
2019 branchAvoid.try_emplace(from,
st.conflicting.size()).first->second;
2020 llvm::BitVector &on =
2021 onArbiter.try_emplace(from,
st.conflicting.size()).first->second;
2022 for (
int other : e.sb->unitFlows(e.j)) {
2025 away |=
st.conflicting[other];
2031 away.reset(onArbiter.find(from)->second);
2036 for (
auto [state, hops] : llvm::zip_equal(
tree,
treeHops))
2037 if (!drop.count(state) && !off.count(state)) {
2038 seeds.push_back(state);
2039 seedCosts.push_back(treeSeedFactor * hops);
2041 llvm::DenseSet<int> blocked;
2044 blocked.insert(off.begin(), off.end());
2046 llvm::DenseMap<int, SmallVector<int, 4>> masters;
2047 bool limited = !
st.priorityMasters.empty();
2049 for (
const auto &[state, hop] :
planned)
2050 if ((hop.first & 1) == In && !drop.count(state))
2051 masters[hop.first].push_back(state);
2052 auto mayCross = [&](
int from,
int to) {
2053 auto it = masters.find(from);
2054 return st.mayLeave(it == masters.end() ? ArrayRef<int>{} : it->second, to);
2056 pf.dijkstraShortestPaths(
2058 off.empty() ? &
stops : &blocked, targets,
2059 limited ? llvm::function_ref<
bool(
int,
int)>(mayCross) :
nullptr);
2064 size_t grown =
tree.size();
2065 while (
st.processedStamp[state] !=
st.curStamp) {
2068 int pred =
pf.preds[state];
2071 planned.insert({state, {pred,
pf.predEdge[state]}});
2073 st.processedStamp[state] =
st.curStamp;
2074 tree.push_back(state);
2079 static_cast<int>(
tree.size() - grown);
2090 llvm::DenseSet<int> off =
partOff;
2091 auto carries = [&](
int d,
int id) {
2092 return llvm::is_contained(
st.idsTo(
flow, d),
id);
2094 auto only = [&](
int d,
int id,
int other) {
2095 return carries(d,
id) && !carries(d, other);
2097 for (
auto [at, a, b, apart] :
st.splitsOf[
flow])
2099 bool splits = !apart ? (only(dst, a, b) && only(other, b, a)) ||
2100 (only(dst, b, a) && only(other, a, b))
2101 : (only(dst, a, b) && other == *apart) ||
2102 (dst == *apart && only(other, a, b));
2105 SmallVector<int, 8> below;
2107 auto entersAt = [&, tile = at](
int state) {
2108 return (state & 1) == In &&
pf.nodes[stateNode(state)].coords == tile;
2110 for (
auto *hop =
planned.find(s); !entersAt(s) && hop !=
planned.end();
2113 s = hop->second.first;
2117 off.insert(below.begin(), below.end());
2127 llvm::DenseSet<int> off;
2130 int root =
tree.front();
2131 auto exitOf = [&](
int s) {
2132 for (
const auto *it =
planned.find(s);
2133 it !=
planned.end() && it->second.first != root; it =
planned.find(s))
2134 s = it->second.first;
2137 const auto *other = llvm::find_if(
reached, [&](
int d) {
2142 int exit = exitOf(*other);
2144 if (s == root || exitOf(s) != exit)
2151 for (
const auto &[from, to, joined] : *
pinned) {
2152 if (
toSelf && from == to)
2154 bool intra = from.coords == to.coords;
2155 auto fromId =
pf.nodeIds.find(from), toId =
pf.nodeIds.find(to);
2156 const Edge *e =
nullptr;
2157 if (fromId !=
pf.nodeIds.end() && toId !=
pf.nodeIds.end())
2158 for (
const Edge &out :
pf.adjacency[fromId->second])
2159 if (out.dst == toId->second &&
2163 return llvm::make_error<RoutingFailure>(
2164 "the route packet flows from " +
2166 " take alone does not fit this design: it goes from " +
2169 ", which the design's own switchboxes leave no connection for.",
2171 std::pair<int, std::pair<int, Edge>> hop{
2172 stateId(toId->second, intra ? Out : In),
2173 {stateId(fromId->second, intra ? In : Out), *e}};
2188 return llvm::Error::success();
2203 SmallVector<int, 8> targets;
2206 for (
const auto &[at, dsts] :
joins)
2208 targets.push_back(at);
2215 : llvm::min_element(
2221 llvm::DenseSet<int> off =
splitOff(currId);
2222 llvm::DenseSet<int> trunk =
trunkOff(currId);
2223 off.insert(trunk.begin(), trunk.end());
2225 search({}, targets, off);
2226 if (
pf.distance[currId] == INF)
2229 const SmallVector<int, 4> *joined =
nullptr;
2230 for (
const auto &[at, dsts] :
joins)
2231 if (
pf.distance[at] <
pf.distance[currId] &&
joinable(at, dsts)) {
2237 joinedAt.push_back({currId, joined});
2245 return llvm::make_error<RoutingFailure>(
2246 "no path leads from " +
2249 " through the connections the switchboxes allow and existing "
2250 "routing leaves free.",
2257 return llvm::Error::success();
2265 llvm::DenseSet<int> branch;
2267 for (
int below = 0; top !=
tree.front() &&
children.lookup(top) == below;
2270 top =
planned.find(top)->second.first;
2275 off.insert(trunk.begin(), trunk.end());
2276 search(branch, dst, off);
2279 for (
int s = dst; s != top;) {
2280 const auto &[from, e] =
planned.find(s)->second;
2284 away ==
branchAvoid.end() ?
nullptr : &away->second);
2287 if (
pf.distance[dst] + rerouteMinSaving >= cost)
2289 for (
int s : branch) {
2290 st.processedStamp[s] = 0;
2295 for (
size_t k =
tree.size(); k-- > 0;)
2296 if (branch.count(
tree[k])) {
2300 [[maybe_unused]]
bool traced =
trace(dst);
2301 assert(traced &&
"a rerouted branch reaches its destination");
2310 if (
part.packetId) {
2311 st.routing.packetTrees[
part.src].push_back({
part.src,
part.src,
false});
2313 int srcId =
pf.nodeIds.at(
part.src);
2314 for (
const Edge &e : ArrayRef<Edge>(
pf.adjacency[srcId])
2315 .take_front(
pf.wireEdgesBegin[srcId]))
2316 if (e.dst == srcId) {
2323 const std::optional<int> &packetId =
part.packetId;
2324 int packetGroupId =
part.packetGroupId;
2325 llvm::DenseMap<int, std::pair<SwitchboxConnect *, int>> branchPort;
2326 for (
const auto &[currId, hop] :
planned) {
2327 const auto &[predId, e] = hop;
2335 st.treeOf[
flow].try_emplace(currId, predId, e);
2337 st.circuitHops[
flow].push_back(e);
2349 auto mergeable = [&] {
2353 std::set<PathEndPoint> dsts;
2355 if (
auto ids =
pf.packetIdsTo.find({f.src, dst});
2356 ids !=
pf.packetIdsTo.end() &&
2357 llvm::is_contained(ids->second, *packetId))
2363 bool sameGroupUnseen =
2364 packetGroupId >= 0 && packetId.has_value() &&
2366 (seen == cell.
packetIds.end() || seen->second ==
flow || mergeable());
2367 if (sameGroupUnseen) {
2368 int packetIdValue = *packetId;
2374 for (
size_t k = 0; k < sb.
srcPorts.size(); k++)
2376 for (
size_t l = 0; l < sb.
dstPorts.size(); l++)
2377 if (l !=
static_cast<size_t>(j))
2395 auto [it,
first] = branchPort.try_emplace(predId, &sb, j);
2414 bool takesSource = !packetId ||
st.partsOf.at(
part.src).front() ==
flow;
2416 for (
auto &[ends, link] :
pf.graph) {
2417 if (ends.second !=
part.src.coords || ends.first == ends.second)
2420 if (k >= 0 && !
st.flowDsts.count({ends.first, link.srcPorts[k]}))
2425 int node =
pf.nodeIds.at(dst);
2426 for (
const Edge &e : ArrayRef<Edge>(
pf.adjacency[node])
2427 .drop_front(
pf.wireEdgesBegin[node]))
2428 takeWire(*e.sb, e.i);
2433 for (
const auto &[currId, hop] :
planned)
2434 st.routing.packetTrees[
part.src].push_back(
2435 {
pf.nodes[stateNode(hop.first)],
pf.nodes[stateNode(currId)],
false});
2441 if (!
st.treeOf[
flow].try_emplace(state, predId, e).second)
2445 st.routing.packetTrees[
part.src].push_back({pred, curr,
true});
2455 for (
const auto &[joinAt, joined] :
joinedAt) {
2457 st.joinedHops[
flow].push_back(
2458 {other,
planned.find(joinAt)->second.second});
2459 for (
int dst : *joined) {
2460 const auto &t =
st.treeOf[other];
2461 SmallVector<std::pair<int, std::pair<int, Edge>>, 8> path;
2462 auto it = t.find(dst);
2463 for (; it != t.end() && it->first != joinAt;
2464 it = t.find(it->second.first))
2465 path.push_back(*it);
2468 for (
const auto &[state, hop] : path)
2469 if (
join(state, hop.first, hop.second))
2470 st.joinedHops[
flow].push_back({other, hop.second});
2473 st.treeDsts[
flow].append(joined->begin(), joined->end());
2476 join(state, hop.first, hop.second);
2483 if (
st.partsOf.at(src).size() == 1) {
2487 for (
int id :
st.flowIds[
flow])
2491 for (
auto [in, out] : llvm::zip(setting.srcs, setting.dsts))
2492 if (!llvm::is_contained(llvm::zip(all.
srcs, all.
dsts),
2493 std::make_tuple(in, out))) {
2494 all.
srcs.push_back(in);
2495 all.
dsts.push_back(out);
2500llvm::Error Pathfinder::routePart(
RouteState &st,
int flow) {
2501 std::optional<TreeBuilder> tree;
2502 tree.emplace(*
this, st, flow);
2503 llvm::Error err = tree->pinned ? tree->placePinned() : tree->grow();
2508 for (
auto *pairs : {&st.
unmet, &st.
met})
2509 pairs->erase(pairs->lower_bound({flow, 0}),
2510 pairs->lower_bound({flow + 1, 0}));
2512 tree.emplace(*
this, st, flow);
2514 if (llvm::Error retry = tree->grow()) {
2515 llvm::consumeError(std::move(retry));
2518 llvm::consumeError(std::move(err));
2523 if (!tree->pinned && tree->reached.size() + tree->joinedAt.size() > 1)
2528 return llvm::Error::success();
2531int Pathfinder::applyRoutingFaults(
RouteState &st,
const RoutingFaults &faults,
2533 int illegalEdges = 0;
2535 for (
const TreeSplit &split : faults.
splits) {
2536 auto src = st.partsOf.find(split.
src);
2537 if (src == st.partsOf.end())
2539 auto partWith = [&](
int id) {
2540 for (
int k : src->second)
2541 if (st.flowIds[k].count(
id))
2545 int flow = partWith(split.
a), other = partWith(split.
b);
2546 if (flow < 0 || other < 0)
2548 std::optional<int> apart;
2550 auto it = nodeIds.find(*split.
apart);
2551 if (it == nodeIds.end())
2553 apart = stateId(it->second, Out);
2556 auto inseparable = [&] {
2557 const Flow &f = st.parts[flow];
2558 for (
const PathEndPoint &dst : f.
dsts) {
2559 auto ids = packetIdsTo.find({f.
src, dst});
2560 if (ids == packetIdsTo.end() ||
2561 !llvm::is_contained(ids->second, split.
a) ||
2562 !llvm::is_contained(ids->second, split.
b))
2564 const auto &tree = st.treeOf[flow];
2565 auto it = tree.find(stateId(nodeIds.at(dst), Out));
2566 if (it == tree.end() && dst == f.
src && dst.
coords == split.
at)
2568 for (; it != tree.end(); it = tree.find(it->second.first)) {
2569 int up = it->second.first;
2570 if ((up & 1) == In && nodes[stateNode(up)].coords == split.
at)
2577 !st.parts[flow].isPriorityFlow && inseparable())
2578 other = st.splitPart(flow, {split.
b});
2579 if (flow != other) {
2580 if (st.partSplits[flow].insert({split.at, other}).second) {
2584 st.partSplits[other].insert({split.
at, flow});
2585 }
else if (st.splitsOf[flow]
2586 .insert({split.at, split.a, split.b, apart})
2589 st.splitsTaught.insert({flow, {split.
at, split.
a, split.
b, apart}})
2591 LLVM_DEBUG(llvm::dbgs()
2592 <<
"Split ids " << split.
a <<
" and " << split.
b <<
" from "
2594 <<
" at tile (" << split.
at.col <<
", " << split.
at.row
2599 crowdedTiles.insert(faults.
crowded.begin(), faults.
crowded.end());
2600 bool related =
false;
2601 for (
const auto &pair : faults.
apart) {
2602 if (!st.apartSources.insert(pair).second)
2605 LLVM_DEBUG(llvm::dbgs()
2612 st.splitOwnIds(pair);
2614 for (
const auto &pair : faults.
together) {
2617 for (
int x : st.partsOf.at(pair.first))
2618 for (
int y : st.partsOf.at(pair.second))
2619 if (llvm::is_contained(st.sameId[x], y) &&
2620 llvm::count_if(st.parts[x].dsts, [&](
const PathEndPoint &dst) {
2621 return llvm::is_contained(st.parts[y].dsts, dst);
2623 st.lessons += st.noJoin.insert({x, y}).second;
2624 st.noJoin.insert({y, x});
2626 if (!st.togetherSources.insert(pair).second)
2629 LLVM_DEBUG(llvm::dbgs()
2630 <<
"Route together: "
2635 st.splitOwnIds(pair);
2642 for (
const PathEndPoint &src : faults.
untrunk)
2643 if (st.untrunked.insert(src).second) {
2644 LLVM_DEBUG(llvm::dbgs()
2650 std::set<std::pair<int, int>> faulted;
2651 bool unjoined =
false;
2652 for (
const auto &[tile, conn] : faults.
connections) {
2654 auto it = graph.find({tile, tile});
2655 if (it == graph.end())
2657 SwitchboxConnect &sb = it->second;
2663 auto takes = [&](
const Edge &e) {
2664 return e.sb == &sb && e.i == i && e.j == j;
2666 bool taken =
false, pinnedTakesAll =
true;
2667 for (
auto [k, part] : llvm::enumerate(st.parts))
2668 if (llvm::any_of(st.circuitHops[k], takes) ||
2669 llvm::any_of(st.treeOf[k], [&](
const auto &hop) {
2670 return takes(hop.second.second);
2673 pinnedTakesAll &= st.isPinned(part);
2675 pinnedOnly += taken && pinnedTakesAll;
2676 bool joined =
false;
2677 for (
auto [flow, hops] : llvm::enumerate(st.joinedHops))
2678 for (
const auto &[other, e] : hops)
2679 if (e.sb == &sb && sb.
srcPorts[e.i] == conn.src &&
2681 faulted.insert({
static_cast<int>(flow), other});
2684 unjoined |= !joined;
2688 for (
auto [flow, other] : faulted)
2689 if (unjoined && st.spared.insert({flow, other}).second)
2691 else if (st.met.count({flow, other}) &&
2692 ++st.meetFaults[{std::min(flow, other), std::max(flow, other)}] <=
2694 st.reorder(flow, other,
true);
2696 st.lessons += st.noJoin.insert({flow, other}).second;
2697 return illegalEdges;
2707 LLVM_DEBUG(llvm::dbgs() <<
"\t---Begin Pathfinder::findPaths---\n");
2708 checkReason.clear();
2709 packetsFailed =
true;
2713 buildRoutingGraph();
2714 if (llvm::Error err = cutOverflow()) {
2715 packetsFailed =
false;
2716 return std::move(err);
2718 crowdedTiles.clear();
2721 for (
auto &[_, sb] : graph) {
2723 for (
auto [j, port] : llvm::enumerate(sb.
dstPorts))
2725 port.channel >= packetFanoutCap &&
2734 return negotiate(maxIterations,
nullptr);
2743 for (
const auto &[_, sb] : graph)
2746 auto sameFlow = [](
const Flow &a,
const Flow &b) {
2748 a.
packetId) == std::tie(b.packetGroupId, b.isPriorityFlow,
2749 b.src, b.dsts, b.packetId);
2752 return llvm::equal(a.flows, now.
flows, sameFlow) &&
2754 !any((a.values ^ settings) & a.consulted);
2756 auto replayed = llvm::find_if(*
attempts, replays);
2757 if (replayed !=
attempts->end() && !clVerifyReplays) {
2758 LLVM_DEBUG(llvm::dbgs() <<
"\tPathfinder: this attempt replays attempt "
2760 <<
" of the ladder, so it is skipped\n");
2761 ++numReplaysSkipped;
2762 crowdedTiles = replayed->crowdedTiles;
2763 packetsFailed = replayed->packetsFailed;
2764 checkReason = replayed->checkReason;
2765 if (replayed->routing)
2766 return *replayed->routing;
2767 return llvm::Error(replayed->prototype->clone(
2768 replayed->reason, replayed->faults, replayed->loc));
2771 llvm::Expected<Routing> found =
2772 negotiate(maxIterations, clVerifyReplays ? &now.
trajectory :
nullptr);
2777 bool replayable =
static_cast<bool>(found);
2780 llvm::Error failure =
2781 found ? llvm::Error::success()
2782 : llvm::handleErrors(
2784 [&](std::unique_ptr<RoutingFailure> f) -> llvm::Error {
2788 now.reason = f->reason;
2789 now.faults = f->faults;
2791 now.prototype = f->clone(f->reason, f->faults, f->loc);
2792 return llvm::Error(std::move(f));
2795 bool sameFailureType =
2796 static_cast<bool>(replayed->prototype) ==
2798 (!now.
prototype || replayed->prototype->dynamicClassID() ==
2800 bool same = replayed->trajectory == now.
trajectory &&
2801 replayed->routing.has_value() == now.
routing.has_value() &&
2802 (!now.
routing || hashRouting(*replayed->routing) ==
2804 sameFailureType && replayed->reason == now.
reason &&
2809 llvm::report_fatal_error(llvm::Twine(
"aie-pathfinder-verify-replays: "
2812 " does not replay attempt " +
2813 llvm::Twine(replayed -
attempts->begin()));
2814 LLVM_DEBUG(llvm::dbgs() <<
"\tPathfinder: this attempt replays attempt "
2816 <<
" of the ladder, as verified\n");
2817 ++numReplaysVerified;
2818 }
else if (replayable) {
2819 attempts->push_back(std::move(now));
2822 return std::move(failure);
2826llvm::Expected<Routing>
2827Pathfinder::negotiate(
const int maxIterations,
2828 std::vector<llvm::hash_code> *trajectory) {
2829 RouteState st(*
this);
2831 int iterationCount = -1;
2832 int illegalEdges = 0;
2833 std::optional<Routing> usable;
2835 int fewestIllegal = std::numeric_limits<int>::max(), sinceFewest = 0;
2837 int reorderedStall = 0;
2838 int priorityFaults = 0;
2841 int fewestRejected = std::numeric_limits<int>::max(), sinceFewestRejected = 0;
2843 if (usable && (iterationCount + 1 >= maxIterations ||
2844 iterationCount - usableAt >= maxSteers)) {
2845 LLVM_DEBUG(llvm::dbgs() <<
"\t\tKeeping the usable routing\n");
2846 return std::move(*usable);
2851 if (++iterationCount >= maxIterations ||
2852 (fewestIllegal > 0 && sinceFewest >= maxOverusedStall) ||
2853 reorderedStall >= maxReorderedStall ||
2854 sinceFewestRejected >= maxRejectedStall) {
2855 LLVM_DEBUG(llvm::dbgs()
2856 <<
"\t\tPathfinder: giving up after " << iterationCount
2858 << (iterationCount >= maxIterations ?
"the iteration limit"
2859 : reorderedStall >= maxReorderedStall
2860 ?
"circuit trees routed first stopped helping"
2861 : sinceFewestRejected >= maxRejectedStall
2862 ?
"the routing check stopped making progress"
2863 :
"the overuse stalled")
2864 <<
")...unable to find routing for flows.\n");
2874 std::set<std::tuple<bool, int, bool>> full;
2875 for (
const auto &[ends, sb] : graph)
2876 if (ends.first != ends.second && llvm::any_of(sb.
cells, overused))
2877 full.insert(
boundaryOf(ends.first, ends.second));
2879 !checkReason.empty() || llvm::any_of(graph, [&](
const auto &entry) {
2880 const auto &[ends, sb] = entry;
2881 return llvm::any_of(sb.
cells, packets) &&
2882 (llvm::any_of(sb.
cells, overused) ||
2883 (ends.first != ends.second &&
2884 full.count(
boundaryOf(ends.first, ends.second))));
2886 return explainNoRouting(st);
2889 LLVM_DEBUG(llvm::dbgs() <<
"\t\t---Begin findPaths iteration #"
2890 << iterationCount <<
"---\n");
2892 for (
auto &[_, sb] : graph) {
2899 for (
auto &[_, sb] : graph) {
2900 for (SwitchboxConnect::Cell &c : sb.
cells) {
2908 for (
auto &tree : st.treeOf)
2910 for (
auto &hops : st.circuitHops)
2912 for (
auto &dsts : st.treeDsts)
2914 for (
auto &hops : st.joinedHops)
2918 st.meetingPorts.clear();
2923 for (
const auto &[_, group] : st.groupedFlows) {
2924 for (
int flow : group)
2925 if (llvm::Error err = routePart(st, flow))
2926 return std::move(err);
2927 for (
auto &[_, sb] : graph) {
2928 for (SwitchboxConnect::Cell &c : sb.
cells) {
2942 for (
auto [later, earlier] : st.unmet) {
2943 bool steered = st.reorder(later, earlier);
2944 steered |= st.trunked.insert({later, earlier}).second;
2945 steered |= st.trunked.insert({earlier, later}).second;
2950 for (
const auto &pair : st.meetBlocked)
2951 if (st.togetherSources.insert(pair).second) {
2952 LLVM_DEBUG(llvm::dbgs()
2953 <<
"Route together to meet: "
2958 st.splitOwnIds(pair);
2960 for (
int a : st.partsOf.at(pair.first))
2961 for (
int b : st.partsOf.at(pair.second)) {
2962 st.trunked.erase({a, b});
2963 st.trunked.erase({b, a});
2967 st.meetBlocked.clear();
2968 for (
const auto &[pair, ids] : st.meetSplits)
2969 for (
int k : SmallVector<int, 2>(st.partsOf.at(pair.first)))
2970 if (!st.parts[k].isPriorityFlow && ids.size() < st.flowIds[k].size() &&
2972 [&](
int id) { return st.flowIds[k].count(id); })) {
2973 LLVM_DEBUG(llvm::dbgs()
2974 <<
"Route apart to meet: "
2979 st.splitPart(k, ids);
2980 for (
int a : st.partsOf.at(pair.first))
2981 for (
int b : st.partsOf.at(pair.second)) {
2982 st.trunked.erase({a, b});
2983 st.trunked.erase({b, a});
2987 st.meetSplits.clear();
2993 for (
auto &[_, sb] : graph) {
2994 for (
size_t i = 0; i < sb.
srcPorts.size(); i++) {
2995 for (
size_t j = 0; j < sb.
dstPorts.size(); j++) {
2996 SwitchboxConnect::Cell &c = sb.
at(i, j);
3004 LLVM_DEBUG(llvm::dbgs()
3005 <<
"\t\t\tToo much capacity on (" << sb.
srcCoords.col
3010 << sb.
dstPorts[j].channel <<
", used_capacity = "
3012 <<
", over_capacity_count = " << c.
overCapacity <<
"\n");
3020 if (illegalEdges < fewestIllegal) {
3021 fewestIllegal = illegalEdges;
3022 sinceFewest = reorderedStall = 0;
3028 if (fewestIllegal == 0 && illegalEdges > 0) {
3029 sinceFewestRejected++;
3030 LLVM_DEBUG(llvm::dbgs()
3031 <<
"Rejected-routing stall " << sinceFewestRejected <<
'\n');
3033 if (illegalEdges && sinceFewest >= stallIterations) {
3034 auto losing = [&](
int flow) {
3035 return !st.parts[flow].packetId &&
3036 llvm::any_of(st.circuitHops[flow], [](
const Edge &e) {
3037 const SwitchboxConnect::Cell &c = e.sb->at(e.i, e.j);
3038 return c.usedCapacity > maxCircuitStreamCapacity &&
3039 c.packetGroupId < 0;
3043 for (
auto &[_, group] : st.groupedFlows) {
3044 moved |= llvm::any_of(group, losing);
3045 std::stable_partition(group.begin(), group.end(), losing);
3047 reorderedStall += moved;
3052 if (sinceFewest >= stallIterations && sinceFewest % stallIterations == 0) {
3053 LLVM_DEBUG(llvm::dbgs() <<
"Drop the id splits after " << sinceFewest
3054 <<
" stalled iterations\n");
3055 for (
auto &splits : st.splitsOf)
3064 llvm::Error unmoved =
3065 illegalEdges != 0 || !constraints.check
3066 ? llvm::Error::success()
3067 : llvm::handleErrors(
3068 constraints.check(st.routing),
3069 [&](std::unique_ptr<RoutingFailure> rejected) -> llvm::Error {
3070 LLVM_DEBUG(llvm::dbgs() <<
"Routing rejected: "
3071 << rejected->reason <<
'\n');
3072 int lessons = st.lessons, pinnedOnly = 0;
3074 applyRoutingFaults(st, rejected->faults, pinnedOnly);
3075 illegalEdges += faulted;
3076 if (illegalEdges < fewestRejected || st.lessons > lessons) {
3077 fewestRejected = std::min(fewestRejected, illegalEdges);
3078 sinceFewestRejected = 0;
3080 sinceFewestRejected++;
3082 LLVM_DEBUG(llvm::dbgs() <<
"Rejected-routing stall "
3083 << sinceFewestRejected <<
'\n');
3084 priorityFaults = rejected->faults.onlyPriorityMasters
3085 ? priorityFaults + 1
3089 stuck = faulted == pinnedOnly && st.lessons == lessons;
3091 if (stuck && pinnedOnly) llvm::dbgs()
3092 <<
"\t\tPathfinder: the routing check names only "
3093 "connections pinned trees take ("
3094 << pinnedOnly <<
") after " << iterationCount
3095 <<
" iterations\n");
3096 if (rejected->isA(DeadlockProneRouting::classID())) {
3098 usable = st.routing;
3099 usableAt = iterationCount;
3101 return llvm::Error::success();
3104 return llvm::Error(std::move(rejected));
3105 checkReason = std::move(rejected->reason);
3106 return llvm::Error::success();
3110 for (
const auto &[src, settings] : st.routing.settings)
3111 llvm::dbgs() <<
"\t\t\tFlow starting at (" << src.
coords.col <<
","
3112 << src.
coords.row <<
"):\t" << settings;
3114 int totalPathLength = 0;
3115 for (
const auto &[_, sb] : graph)
3117 for (
const SwitchboxConnect::Cell &c : sb.
cells)
3119 llvm::dbgs() <<
"\t\t---End findPaths iteration #" << iterationCount
3120 <<
" , illegal edges count = " << illegalEdges
3121 <<
", total path length = " << totalPathLength <<
"---\n";
3124 trajectory->push_back(hashRouting(st.routing));
3125 if (stuck && usable) {
3126 llvm::consumeError(std::move(unmoved));
3127 return std::move(*usable);
3130 return std::move(unmoved);
3131 if (priorityFaults >= maxPriorityFaults) {
3132 LLVM_DEBUG(llvm::dbgs() <<
"\t\tPathfinder: the routing check rejects "
3133 "only master sets of the prioritized flows ("
3134 << priorityFaults <<
" routings in a row)\n");
3136 return std::move(*usable);
3137 packetsFailed =
false;
3138 return explainNoRouting(st);
3141 }
while (illegalEdges > 0);
3143 LLVM_DEBUG(llvm::dbgs() <<
"\t---End Pathfinder::findPaths---\n");
3144 return std::move(st.routing);
STATISTIC(numReplaysSkipped, "Attempts skipped as replays of an earlier one")
virtual uint32_t getNumSourceShimMuxConnections(int col, int row, WireBundle bundle) const =0
Return the number of sources of connections inside a shimmux.
virtual bool isLegalTileConnection(int col, int row, WireBundle srcBundle, int srcChan, WireBundle dstBundle, int dstChan) const =0
bool isShimNOCorPLTile(int col, int row) const
Return true if the given tile is either a ShimNOC or ShimPL tile.
virtual uint32_t getNumDestShimMuxConnections(int col, int row, WireBundle bundle) const =0
Return the number of destinations of connections inside a shimmux.
virtual uint32_t getNumDestSwitchboxConnections(int col, int row, WireBundle bundle) const =0
Return the number of destinations of connections inside a switchbox.
virtual uint32_t getNumSourceSwitchboxConnections(int col, int row, WireBundle bundle) const =0
Return the number of sources of connections inside a switchbox.
ShimMuxOp getShimMux(mlir::OpBuilder &builder, int col)
SwitchboxOp getSwitchbox(mlir::OpBuilder &builder, int col, int row)
SwitchboxOp lookupSwitchbox(TileID tile) const
TileOp getTile(mlir::OpBuilder &builder, int col, int row)
llvm::Error runAnalysis(DeviceOp &device)
ShimMuxOp lookupShimMux(int col) const
std::vector< std::pair< TileID, Port > > avoidedPorts
void avoidPort(TileID coords, Port port)
std::vector< PathfinderAttempt > * attempts
llvm::Expected< Routing > findPaths(int maxIterations)
void excludeTile(TileID coords)
void addFlow(TileID srcCoords, Port srcPort, TileID dstCoords, Port dstPort, std::optional< int > packetId, bool isPriorityFlow, std::optional< mlir::Location > loc=std::nullopt)
void initialize(int maxCol, int maxRow, const AIETargetModel &targetModel)
mlir::LogicalResult addFixedConnection(SwitchboxOp switchboxOp)
void log(llvm::raw_ostream &os) const override
std::string joinNames(llvm::ArrayRef< std::string > names, size_t shown=4)
Lists names as "A, B and C", the first shown of them followed by "N more" if there are more.
int shimMuxChannelTo(Port dst)
std::string describePrioritized(llvm::ArrayRef< std::string > sources)
Says that the packet flows from sources keep the route they take alone, as a control-packet reload of...
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
bool isDirectional(WireBundle bundle)
std::tuple< bool, int, bool > boundaryOf(TileID a, TileID b)
int shimMuxChannelFrom(Port src)
std::string describeTilePort(TileID tile, Port port)
Names a tile port the way diagnostics do, e.g. "(0, 2) DMA:1".
struct Port { WireBundle bundle; int channel; bool operator==(const Port &rhs) const { return std::tie(bundle, channel)==std::tie(rhs.bundle, rhs.channel); } bool operator!=(const Port &rhs) const { return !(*this==rhs);} bool operator<(const Port &rhs) const { return std::tie(bundle, channel)< std::tie(rhs.bundle, rhs.channel); } friend std::ostream &operator<<(std::ostream &os, const Port &port) { os<< "("; os<< stringifyWireBundle(port.bundle).str(); os<< ": "<< std::to_string(port.channel)<< ")"; return os; } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Port &port) { os<< to_string(port); return os; } } Port
std::map< TileID, SwitchSetting > SwitchSettings
constexpr llvm::StringLiteral kNoLegalRouting
std::string describePort(Port port)
Names a port the way diagnostics do, e.g. "DMA:1".
WireBundle getConnectingBundle(WireBundle dir)
bool operator<(const IdSplit &other) const
std::optional< int > apart
std::set< PathEndPoint > flowDsts
std::vector< SmallVector< int, 4 > > prioritySets
std::set< std::pair< int, int > > noJoin
std::set< PathEndPoint > untrunked
std::vector< llvm::DenseMap< int, std::pair< int, Edge > > > treeOf
llvm::DenseSet< int > priorityMasters
std::map< std::pair< int, int >, int > meetFaults
void splitOwnIds(const std::pair< PathEndPoint, PathEndPoint > &pair)
std::vector< SmallVector< Edge, 8 > > circuitHops
std::set< std::pair< int, int > > reordered
std::vector< std::set< std::pair< TileID, int > > > partSplits
std::vector< uint32_t > processedStamp
std::vector< SmallVector< std::pair< int, Edge >, 8 > > joinedHops
std::set< std::pair< std::pair< PathEndPoint, PathEndPoint >, std::set< int > > > meetSplits
std::set< std::pair< int, int > > spared
std::vector< llvm::BitVector > conflicting
std::vector< SmallVector< int, 4 > > treeDsts
std::vector< std::set< IdSplit > > splitsOf
std::set< std::pair< int, int > > met
std::vector< Flow > parts
RouteState(const Pathfinder &pf)
std::set< std::pair< PathEndPoint, PathEndPoint > > togetherSources
std::set< std::pair< PathEndPoint, PathEndPoint > > meetBlocked
bool reorder(int later, int earlier, bool again=false)
std::vector< std::set< int > > flowIds
llvm::MapVector< int, SmallVector< int, 8 > > groupedFlows
bool isPinned(const Flow &f) const
std::set< std::pair< PathEndPoint, PathEndPoint > > apartSources
std::set< std::pair< int, int > > unmet
std::map< std::pair< int, int >, PathEndPoint > meetingPorts
std::set< std::pair< int, IdSplit > > splitsTaught
bool mayLeave(ArrayRef< int > masters, int next) const
std::set< std::pair< int, int > > trunked
int splitPart(int flow, const std::set< int > &ids)
std::vector< SmallVector< int, 4 > > sameId
SmallVector< int, 4 > idsTo(int flow, int dstState) const
std::map< PathEndPoint, SmallVector< int, 2 > > partsOf
int groupOf(const Flow &f) const
TreeBuilder(Pathfinder &pf, RouteState &st, int flow)
llvm::MapVector< int, SmallVector< int, 4 > > sharedDsts
bool isPending(int state) const
SmallVector< PathEndPoint, 4 > pending
SwitchSettings switchSettings
SmallVector< int, 4 > pinnedJoinDsts
llvm::DenseSet< int > foreign
llvm::DenseSet< int > stops
llvm::DenseSet< int > trunkOff(int dst) const
SmallVector< int, 16 > treeHops
llvm::MapVector< int, SmallVector< int, 4 > > blockedDsts
SmallVector< int, 16 > seeds
SmallVector< int, 4 > met
void reach(ArrayRef< int > dsts)
void search(const llvm::DenseSet< int > &drop, ArrayRef< int > targets, const llvm::DenseSet< int > &off={})
const std::vector< TreeHop > * pinned
SmallVector< double, 16 > seedCosts
llvm::DenseSet< int > unjoinable
std::optional< PathEndPoint > first
SmallVector< std::pair< int, std::pair< int, Edge > >, 8 > pinnedJoins
int dstState(const PathEndPoint &p) const
llvm::MapVector< int, std::pair< int, Edge > > planned
SmallVector< int, 16 > tree
llvm::DenseSet< int > partOff
llvm::DenseMap< int, SmallVector< int, 2 > > joinOwners
SmallVector< int, 4 > reached
llvm::DenseMap< int, llvm::BitVector > branchAvoid
llvm::DenseSet< int > disagree
llvm::Error placePinned()
bool joinable(int at, ArrayRef< int > dsts) const
llvm::MapVector< int, std::pair< SmallVector< int, 4 >, std::set< int > > > blockedIds
SmallVector< std::pair< int, const SmallVector< int, 4 > * >, 2 > joinedAt
bool join(int state, int predId, const Edge &e)
llvm::DenseSet< int > splitOff(int dst) const
llvm::DenseSet< int > trunkDsts
const llvm::BitVector * avoid
llvm::DenseMap< int, SmallVector< int, 4 > > joins
llvm::DenseMap< int, int > children
std::vector< PathEndPoint > dsts
std::optional< int > packetId
std::vector< std::string > flows
std::vector< llvm::BitVector > circuitOnly
std::vector< Flow > flows
std::vector< llvm::hash_code > trajectory
std::unique_ptr< RoutingFailure > prototype
llvm::DenseSet< TileID > crowdedTiles
std::optional< Routing > routing
std::vector< std::pair< TileID, Connect > > connections
std::vector< PathEndPoint > untrunk
std::vector< std::pair< PathEndPoint, PathEndPoint > > together
std::vector< TreeSplit > splits
std::vector< TileID > crowded
std::vector< std::pair< PathEndPoint, PathEndPoint > > apart
std::map< PathEndPoint, SwitchSettings > settings
std::map< std::pair< PathEndPoint, int >, SwitchSettings > idSettings
llvm::SmallDenseMap< int, int, 2 > packetIds
std::vector< Port > dstPorts
std::vector< Port > srcPorts
int srcIndex(Port p) const
static void bumpDemand(Cell &c)
void addToUnit(int j, int flow)
llvm::BitVector circuitOnlyDst
Cell & at(size_t i, size_t j)
std::vector< Cell > cells
int dstIndex(Port p) const
void joinUnits(int j, int k)
std::optional< PathEndPoint > apart