15#include "mlir/IR/PatternMatch.h"
16#include "mlir/Pass/Pass.h"
17#include "mlir/Transforms/DialectConversion.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/EquivalenceClasses.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/ScopeExit.h"
22#include "llvm/ADT/SmallBitVector.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/MathExtras.h"
37#define DEBUG_TYPE "aie-create-pathfinder-flows"
40#define GEN_PASS_DEF_AIEROUTEPATHFINDERFLOWS
41#include "aie/Dialect/AIE/Transforms/AIEPasses.h.inc"
48 std::map<PhysPort, SmallVector<std::tuple<int, int, int>, 2>>;
53 std::map<PathEndPoint, std::set<int>>
ids;
58 const int numArbiters = d.getTargetModel().getNumArbiters();
59 AIEDialect::PriorityRouteAttrHelper priority(d.getContext());
61 for (SwitchboxOp box : d.getOps<SwitchboxOp>())
62 for (PacketRulesOp port : box.getOps<PacketRulesOp>())
63 for (PacketRuleOp rule : port.getRules().front().getOps<PacketRuleOp>())
64 if (priority.isAttrPresent(port) || priority.isAttrPresent(rule)) {
65 auto amsel = cast<AMSelOp>(rule.getAmsel().getDefiningOp());
66 rules[{box.getTileOp().getTileID(),
67 {port.getSourceBundle(), port.sourceIndex()}}]
69 {rule.maskInt(), rule.valueInt(),
70 amsel.arbiterIndex() + amsel.getMselValue() * numArbiters});
81static constexpr llvm::StringLiteral sharedReceiverCycleReason =
82 "Packet flows into receivers they share can deadlock holding arbiters "
83 "across switchboxes, and no routing found avoids it: ";
84static constexpr llvm::StringLiteral allowDeadlockProneHint =
85 " Set allow-deadlock-prone (aiecc --allow-deadlock-prone-routing) to "
102struct AIEPathfinderPass
103 : xilinx::AIE::impl::AIERoutePathfinderFlowsBase<AIEPathfinderPass> {
105 xilinx::AIE::impl::AIERoutePathfinderFlowsBase<AIEPathfinderPass>;
106 AIEPathfinderPass() =
default;
107 AIEPathfinderPass(
const AIERoutePathfinderFlowsOptions &options)
109 std::vector<std::pair<TileID, Port>> avoidedPorts;
110 void runOnOperation()
override;
114 LogicalResult runOnPacketFlow(DeviceOp d, OpBuilder &builder,
117 const PacketPlan &plan,
bool warn);
121 bool circuitSwitchHops,
122 bool prioritize =
true);
127struct ConvertFlowsToInterconnect : OpConversionPattern<FlowOp> {
128 using OpConversionPattern::OpConversionPattern;
131 ConvertFlowsToInterconnect(MLIRContext *context, DeviceOp &d,
133 : OpConversionPattern(context, benefit), device(d), analyzer(a) {}
135 void addConnection(ConversionPatternRewriter &rewriter,
137 Interconnect op, FlowOp flowOp, WireBundle inBundle,
138 int inIndex, WireBundle outBundle,
int outIndex)
const {
140 Region &r = op.getConnections();
141 Block &b = r.front();
142 auto point = rewriter.saveInsertionPoint();
143 rewriter.setInsertionPoint(b.getTerminator());
145 ConnectOp::create(rewriter, flowOp.getLoc(), inBundle, inIndex, outBundle,
148 rewriter.restoreInsertionPoint(point);
150 LLVM_DEBUG(llvm::dbgs()
151 <<
"\t\taddConnection() (" << op.colIndex() <<
","
152 << op.rowIndex() <<
") " << stringifyWireBundle(inBundle)
153 << inIndex <<
" -> " << stringifyWireBundle(outBundle)
154 << outIndex <<
"\n");
158 matchAndRewrite(FlowOp flowOp, OpAdaptor adaptor,
159 ConversionPatternRewriter &rewriter)
const override {
160 Operation *Op = flowOp.getOperation();
161 DeviceOp d = flowOp->getParentOfType<DeviceOp>();
163 flowOp->emitOpError(
"This operation must be contained within a device");
166 rewriter.setInsertionPoint(d.getBody()->getTerminator());
168 auto srcTile = cast<TileOp>(flowOp.getSource().getDefiningOp());
169 TileID srcCoords = {srcTile.colIndex(), srcTile.rowIndex()};
170 auto srcBundle = flowOp.getSourceBundle();
171 auto srcChannel = flowOp.getSourceChannel();
172 Port srcPort = {srcBundle, srcChannel};
175 auto dstTile = cast<TileOp>(flowOp.getDest().getDefiningOp());
176 llvm::dbgs() <<
"\n\t---Begin rewrite() for flowOp: (" << srcCoords.col
177 <<
", " << srcCoords.row <<
")"
178 << stringifyWireBundle(srcBundle) << srcChannel <<
" -> ("
179 << dstTile.colIndex() <<
", " << dstTile.rowIndex() <<
")"
180 << stringifyWireBundle(flowOp.getDestBundle())
181 << flowOp.getDestChannel() <<
"\n\t";
186 TileID srcSbId = {srcCoords.col, srcCoords.row};
193 LLVM_DEBUG(llvm::dbgs() <<
"Flow already processed!\n");
194 rewriter.eraseOp(Op);
199 for (
const auto &[tileId, setting] : settings) {
200 int col = tileId.col;
201 int row = tileId.row;
202 SwitchboxOp swOp = analyzer.
getSwitchbox(rewriter, col, row);
203 int shimCh = srcChannel;
204 bool isShim = analyzer.
getTile(rewriter, tileId).isShimNOCorPLTile();
207 bool srcUsesShimMux = srcBundle == WireBundle::DMA ||
208 srcBundle == WireBundle::PLIO ||
209 srcBundle == WireBundle::NOC;
210 if (isShim && tileId == srcSbId && srcUsesShimMux) {
213 ShimMuxOp shimMuxOp = analyzer.
getShimMux(rewriter, col);
214 addConnection(rewriter, cast<Interconnect>(shimMuxOp.getOperation()),
215 flowOp, srcBundle, srcChannel, WireBundle::North, shimCh);
217 assert(setting.srcs.size() == setting.dsts.size());
218 for (
size_t i = 0; i < setting.srcs.size(); i++) {
219 Port src = setting.srcs[i];
220 Port dest = setting.dsts[i];
223 if (isShim && tileId == srcSbId && srcUsesShimMux && src == srcPort)
224 src = {WireBundle::South, shimCh};
225 if (isShim && (dest.bundle == WireBundle::DMA ||
226 dest.bundle == WireBundle::PLIO ||
227 dest.bundle == WireBundle::NOC)) {
230 ShimMuxOp shimMuxOp = analyzer.
getShimMux(rewriter, col);
231 addConnection(rewriter, cast<Interconnect>(shimMuxOp.getOperation()),
232 flowOp, WireBundle::North, destCh, dest.bundle,
234 dest = {WireBundle::South, destCh};
236 addConnection(rewriter, cast<Interconnect>(swOp.getOperation()), flowOp,
237 src.bundle, src.channel, dest.bundle, dest.channel);
240 LLVM_DEBUG(llvm::dbgs() << tileId <<
": " << setting <<
" | " <<
"\n");
243 LLVM_DEBUG(llvm::dbgs()
244 <<
"\n\t\tFinished adding ConnectOps to implement flowOp.\n");
247 rewriter.eraseOp(Op);
254LogicalResult AIEPathfinderPass::runOnFlow(DeviceOp d,
258 ConversionTarget target(getContext());
259 target.addLegalOp<TileOp>();
260 target.addLegalOp<ConnectOp>();
261 target.addLegalOp<SwitchboxOp>();
262 target.addLegalOp<ShimMuxOp>();
263 target.addLegalOp<EndOp>();
265 RewritePatternSet patterns(&getContext());
266 patterns.insert<ConvertFlowsToInterconnect>(d.getContext(), d, analyzer);
267 if (failed(applyPartialConversion(d, target, std::move(patterns))))
273static std::optional<std::pair<TileID, Port>> linkedInput(
TileID tile,
275 switch (out.bundle) {
276 case WireBundle::East:
277 return std::pair{
TileID{tile.col + 1, tile.row},
278 Port{WireBundle::West, out.channel}};
279 case WireBundle::West:
280 return std::pair{
TileID{tile.col - 1, tile.row},
281 Port{WireBundle::East, out.channel}};
282 case WireBundle::North:
283 return std::pair{
TileID{tile.col, tile.row + 1},
284 Port{WireBundle::South, out.channel}};
285 case WireBundle::South:
286 return std::pair{
TileID{tile.col, tile.row - 1},
287 Port{WireBundle::North, out.channel}};
297 if (tile == finalTile && out == finalPort)
299 std::optional<std::pair<TileID, Port>> next = linkedInput(tile, out);
302 TileID neighbour = next->first;
303 Port in = next->second;
304 auto setting = settings.find(neighbour);
305 if (setting == settings.end())
308 llvm::zip(setting->second.srcs, setting->second.dsts), [&](
auto link) {
309 auto [src, dest] = link;
311 findPathToDest(settings, neighbour, dest, finalTile, finalPort);
318template <
typename Node,
typename Successors>
319static std::map<Node, Node>
320breadthFirstParents(Node start, Successors successors,
321 std::optional<Node> goal = std::nullopt) {
322 std::map<Node, Node> parent{{start, start}};
323 std::deque<Node> work{start};
324 while (!work.empty() && !(goal && parent.count(*goal))) {
325 Node u = work.front();
327 for (Node v : successors(u))
328 if (parent.try_emplace(v, u).second)
339 llvm::SmallBitVector cov;
347static void bnbMinCover(ArrayRef<CoverCube> cubes,
348 const llvm::SmallBitVector &uncovered,
349 SmallVectorImpl<int> &sel,
int &bestSize,
350 SmallVectorImpl<int> &bestSel) {
353 if (uncovered.none()) {
354 if (
static_cast<int>(sel.size()) < bestSize) {
355 bestSize =
static_cast<int>(sel.size());
356 bestSel.assign(sel.begin(), sel.end());
362 if (
static_cast<int>(sel.size()) + 1 >= bestSize) {
368 int pickCount =
static_cast<int>(cubes.size()) + 1;
370 for (
int id = uncovered.find_first();
id != -1;
371 id = uncovered.find_next(
id)) {
374 for (
const CoverCube &cb : cubes) {
375 if (cb.cov.test(
id)) {
387 for (
int i = 0; i < static_cast<int>(cubes.size()); ++i) {
388 if (!cubes[i].cov.test(pick)) {
393 llvm::SmallBitVector next = uncovered;
394 next.reset(cubes[i].cov);
395 bnbMinCover(cubes, next, sel, bestSize, bestSel);
400static bool cubesIntersect(std::pair<int, int> a, std::pair<int, int> b) {
401 return ((a.second ^ b.second) & a.first & b.first) == 0;
416static SmallVector<std::pair<int, int>>
417computeSubcubeCover(
const SmallVector<int, 4> &matchIds,
418 ArrayRef<std::pair<int, int>> avoidCubes,
int idBits) {
421 const int numIds = 1 << idBits;
422 const int idMask = numIds - 1;
424 auto hitsAvoid = [&](
int mask,
int value) {
425 return llvm::any_of(avoidCubes, [&](std::pair<int, int> c) {
426 return cubesIntersect({mask, value}, c);
430 llvm::SmallBitVector matchMask(numIds);
431 for (
int id : matchIds) {
436 SmallVector<CoverCube> primes;
437 for (
int mask = 0; mask < numIds; ++mask) {
438 for (
int value = 0; value < numIds; ++value) {
440 if ((value & mask) != value) {
443 if (hitsAvoid(mask, value)) {
448 llvm::SmallBitVector cov(numIds);
449 for (
int id : matchIds) {
450 if ((
id & mask) == value) {
462 for (
int b = 0; b < idBits; ++b) {
463 if (!((mask >> b) & 1)) {
467 if (!hitsAvoid(mask & ~(1 << b), value & ~(1 << b))) {
474 primes.push_back({mask, value, std::move(cov)});
480 SmallVector<int> sel, bestSel;
481 int bestSize =
static_cast<int>(matchIds.size()) + 1;
483 bnbMinCover(primes, matchMask, sel, bestSize, bestSel);
485 SmallVector<std::pair<int, int>> chosen;
486 for (
int i : bestSel) {
487 chosen.push_back({primes[i].mask, primes[i].value});
490 if (chosen.empty()) {
492 for (
int id : matchIds) {
493 chosen.push_back({idMask,
id});
507 SmallVector<SmallVector<int, 4>, 4> assigned(chosen.size());
508 for (
int id : matchIds) {
509 for (
int c = 0; c < static_cast<int>(chosen.size()); ++c) {
510 if ((
id & chosen[c].first) == chosen[c].second) {
511 assigned[c].push_back(
id);
517 SmallVector<std::pair<int, int>> cover;
518 for (
const SmallVector<int, 4> &ids : assigned) {
524 for (
int i = 0; i < idBits; ++i) {
525 int bit = (ids.front() >> i) & 1;
527 if (((
id >> i) & 1) != bit) {
533 cover.push_back({mask, ids.front() & mask});
542static SmallVector<std::pair<int, int>>
543groupRules(ArrayRef<std::pair<int, int>> stated, ArrayRef<int> derived,
544 ArrayRef<std::pair<int, int>> avoid,
int idBits) {
545 SmallVector<std::pair<int, int>> rules(stated);
548 SmallVector<std::pair<int, int>> derivedAvoid(avoid);
549 derivedAvoid.append(stated.begin(), stated.end());
550 llvm::append_range(rules, computeSubcubeCover(SmallVector<int, 4>(derived),
551 derivedAvoid, idBits));
557 ArrayRef<std::pair<int, int>> stated;
558 ArrayRef<int> derived;
559 bool priority =
false;
570static uint64_t cubeIds(
int mask,
int value,
int idBits) {
572 for (
int id = 0;
id < (1 << idBits); ++id)
573 if ((
id & mask) == (value & mask))
574 ids |= uint64_t(1) << id;
581static std::optional<SmallVector<PortRule>>
582orderedRules(ArrayRef<GroupClaims> groups,
583 ArrayRef<std::pair<int, int>> existing,
int idBits,
587 const int idMask = (1 << idBits) - 1;
588 SmallVector<uint64_t> claims;
589 for (
const GroupClaims &group : groups) {
591 for (
auto [mask, value] : group.stated)
592 ids |= cubeIds(mask, value, idBits);
593 for (
int id : group.derived)
594 ids |= uint64_t(1) << id;
595 claims.push_back(ids);
597 uint64_t claimed = 0;
598 for (uint64_t ids : claims)
601 for (
auto [mask, value] : existing)
602 taken |= cubeIds(mask, value, idBits);
605 SmallVector<uint64_t> cubes;
606 for (
int mask = 0; mask <= idMask; ++mask)
607 for (
int value = 0; value <= idMask; ++value)
608 if ((value & mask) == value)
609 cubes.push_back(cubeIds(mask, value, idBits));
614 SmallVector<PortRule> rules;
615 std::set<std::pair<uint64_t, size_t>> dead;
616 auto search = [&](
auto &self, uint64_t taken,
size_t left) ->
bool {
617 uint64_t open = claimed & ~taken;
619 llvm::count_if(claims, [&](uint64_t ids) {
return ids & open; });
622 if (openGroups > left || dead.count({taken, left}))
624 SmallVector<std::pair<uint64_t, size_t>> moves;
625 for (uint64_t cube : cubes)
626 for (
auto [g, ids] : llvm::enumerate(claims))
627 if ((cube & open) && (cube & open & ~ids) == 0 &&
628 !llvm::is_contained(moves, std::pair{cube & open, g}))
629 moves.push_back({cube & open, g});
630 llvm::stable_sort(moves, [](
auto a,
auto b) {
631 return llvm::popcount(a.first) > llvm::popcount(b.first);
633 SmallVector<std::pair<uint64_t, size_t>> tried;
634 for (
auto [own, g] : moves) {
635 if (llvm::any_of(tried, [&, own = own, g = g](
auto t) {
636 return t.second == g && (t.first & own) == own;
639 tried.push_back({own, g});
640 int all = idMask, any = 0;
641 for (
int id = 0;
id <= idMask; ++id)
642 if ((own >>
id) & 1) {
646 int mask = idMask & ~(all ^ any);
647 rules.push_back({mask, all, g});
648 if (self(self, taken | own, left - 1))
652 dead.insert({taken, left});
655 for (
size_t length = 1; length <= budget; ++length)
656 if (search(search, taken, length))
664static SmallVector<PortRule> portRules(ArrayRef<GroupClaims> groups,
665 ArrayRef<std::pair<int, int>> existing,
666 int idBits,
size_t slots) {
667 const int idMask = (1 << idBits) - 1;
668 SmallVector<PortRule> rules;
669 for (
auto [g, group] : llvm::enumerate(groups)) {
670 SmallVector<std::pair<int, int>> avoid(existing);
671 for (
auto [o, other] : llvm::enumerate(groups)) {
674 avoid.append(other.stated.begin(), other.stated.end());
675 for (
int id : other.derived)
676 avoid.push_back({idMask,
id});
678 for (
auto [mask, value] :
679 groupRules(group.stated, group.derived, avoid, idBits))
680 rules.push_back({mask, value, g});
682 if (existing.size() + rules.size() <= slots || existing.size() >= slots)
684 if (std::optional<SmallVector<PortRule>> ordered =
685 orderedRules(groups, existing, idBits, slots - existing.size()))
690static SmallVector<PortRule>
691slavePortRules(ArrayRef<GroupClaims> groups,
692 ArrayRef<std::pair<int, int>> existing,
int idBits,
694 SmallVector<std::pair<int, int>> taken(existing);
695 SmallVector<PortRule> rules;
696 for (
bool priority : {
true,
false}) {
697 SmallVector<size_t, 4> members;
698 SmallVector<GroupClaims> claims;
699 for (
auto [g, group] : llvm::enumerate(groups))
700 if (group.priority == priority) {
701 members.push_back(g);
702 claims.push_back(group);
706 for (
const PortRule &r : portRules(claims, taken, idBits, slots))
707 rules.push_back({r.mask, r.value, members[r.group]});
708 for (
const PortRule &r : rules)
709 if (groups[r.group].priority == priority)
710 taken.push_back({r.mask, r.value});
721 SmallVector<Port, 4> masters;
728 std::map<std::pair<Port, int>,
int> slaveAmsels;
729 std::map<int, SmallVector<Port, 4>> amselMasters;
734template <
typename SlaveFlows>
735llvm::EquivalenceClasses<Port> tiedMasters(SlaveFlows &&flows) {
736 llvm::EquivalenceClasses<Port> tied;
737 for (
const SlaveFlow &f : flows)
738 for (
Port m : f.masters)
739 tied.unionSets(f.masters.front(), m);
752std::optional<ArbiterPlan>
753planArbiters(
const AIETargetModel &targetModel, ArrayRef<SlaveFlow> flows,
754 llvm::function_ref<
bool(
size_t,
size_t)> conflict,
755 llvm::function_ref<
bool(
size_t,
int)> excluded,
756 const std::set<int> &reservedAmsels,
757 SmallVectorImpl<std::pair<size_t, size_t>> &blocking) {
760 auto amselOf = [&](
int arbiter,
int msel) {
761 return arbiter + msel * numArbiters;
764 llvm::EquivalenceClasses<Port> tied = tiedMasters(flows);
767 SmallVector<size_t, 4> flows;
768 SmallVector<SmallVector<Port, 4>, 2> masterSets;
769 bool isPriority =
false;
771 std::vector<Unit> units;
772 std::map<Port, size_t> unitOf;
773 SmallVector<size_t, 8> flowUnit;
774 for (
auto [i, f] : llvm::enumerate(flows)) {
775 auto [it, inserted] =
776 unitOf.try_emplace(tied.getLeaderValue(f.masters.front()), 0);
778 it->second = units.size();
779 units.emplace_back();
781 Unit &unit = units[it->second];
782 flowUnit.push_back(it->second);
783 unit.flows.push_back(i);
784 unit.isPriority |= f.isPriority;
785 if (!llvm::is_contained(unit.masterSets, f.masters))
786 unit.masterSets.push_back(f.masters);
788 for (Unit &unit : units) {
789 auto *priorityEnd = std::stable_partition(
790 unit.masterSets.begin(), unit.masterSets.end(),
791 [&](
const SmallVector<Port, 4> &masters) {
792 return llvm::any_of(unit.flows, [&](size_t f) {
793 return flows[f].isPriority && flows[f].masters == masters;
796 std::sort(unit.masterSets.begin(), priorityEnd);
799 auto clash = [&](
size_t a,
size_t b) {
800 return flows[a].slave != flows[b].slave && conflict(a, b);
802 for (
const Unit &unit : units)
803 for (
auto [k, a] : llvm::enumerate(unit.flows))
804 for (
size_t b : llvm::drop_begin(unit.flows, k + 1))
806 blocking.push_back({a, b});
807 if (!blocking.empty())
810 std::vector<llvm::SmallDenseSet<size_t, 4>> neighbors(units.size());
811 SmallVector<std::pair<size_t, size_t>, 4> crossPairs;
812 for (
size_t a = 0; a < flows.size(); a++)
813 for (
size_t b = a + 1; b < flows.size(); b++)
814 if (flowUnit[a] != flowUnit[b] && clash(a, b)) {
815 neighbors[flowUnit[a]].insert(flowUnit[b]);
816 neighbors[flowUnit[b]].insert(flowUnit[a]);
817 crossPairs.push_back({a, b});
820 SmallVector<SmallVector<int, 4>, 6> freeMsels(numArbiters);
821 SmallVector<SmallVector<size_t, 4>, 6> excludedUnits(numArbiters);
822 for (
int a = 0; a < numArbiters; a++) {
823 for (
int m = 0; m < numMselsPerArbiter; m++)
824 if (!reservedAmsels.count(amselOf(a, m)))
825 freeMsels[a].push_back(m);
826 for (
size_t f = 0; f < flows.size(); f++)
827 if (excluded(f, a) && !llvm::is_contained(excludedUnits[a], flowUnit[f]))
828 excludedUnits[a].push_back(flowUnit[f]);
831 for (
const SmallVector<int, 4> &free : freeMsels)
832 mostFree = std::max(mostFree, free.size());
833 if (llvm::any_of(units, [&](
const Unit &unit) {
834 return unit.masterSets.size() > mostFree;
839 SmallVector<size_t, 8> order(units.size());
840 std::iota(order.begin(), order.end(), 0);
841 llvm::stable_sort(order, [&](
size_t a,
size_t b) {
842 return std::make_pair(neighbors[a].size(), units[a].masterSets.size()) >
843 std::make_pair(neighbors[b].size(), units[b].masterSets.size());
846 SmallVector<int, 8> arbiterOf(units.size(), -1);
847 SmallVector<size_t, 6> load(numArbiters, 0);
849 auto place = [&](
auto &self,
size_t depth) ->
bool {
850 if (depth == order.size())
853 LLVM_DEBUG(llvm::dbgs() <<
"Arbiter search gave up after "
857 size_t u = order[depth];
858 SmallVector<int, 6> candidates(numArbiters);
859 std::iota(candidates.begin(), candidates.end(), 0);
860 if (units[u].isPriority)
861 std::reverse(candidates.begin(), candidates.end());
863 llvm::stable_sort(candidates, [&](
int a,
int b) {
864 return load[a] + numMselsPerArbiter - freeMsels[a].size() <
865 load[b] + numMselsPerArbiter - freeMsels[b].size();
867 std::set<std::pair<size_t, SmallVector<size_t, 4>>> triedEmpty;
868 for (
int a : candidates) {
869 if (load[a] + units[u].masterSets.size() > freeMsels[a].size())
871 if (llvm::is_contained(excludedUnits[a], u) ||
872 llvm::any_of(neighbors[u],
873 [&](
size_t v) {
return arbiterOf[v] == a; }))
878 !triedEmpty.insert({freeMsels[a].size(), excludedUnits[a]}).second)
881 load[a] += units[u].masterSets.size();
882 if (self(self, depth + 1))
884 load[a] -= units[u].masterSets.size();
889 if (!place(place, 0)) {
890 blocking.append(crossPairs.begin(), crossPairs.end());
894 SmallVector<size_t, 8> mselOrder(units.size());
895 std::iota(mselOrder.begin(), mselOrder.end(), 0);
896 llvm::stable_sort(mselOrder, [&](
size_t a,
size_t b) {
897 if (!units[a].isPriority || !units[b].isPriority)
898 return units[a].isPriority > units[b].isPriority;
899 return units[a].masterSets.front() < units[b].masterSets.front();
902 SmallVector<size_t, 6> low(numArbiters, 0), high(numArbiters, 0);
903 for (
size_t u : mselOrder) {
904 const Unit &unit = units[u];
905 int a = arbiterOf[u];
906 std::map<SmallVector<Port, 4>,
int> setAmsel;
907 for (
const SmallVector<Port, 4> &masters : unit.masterSets) {
908 int msel = unit.isPriority
909 ? freeMsels[a][freeMsels[a].size() - 1 - high[a]++]
910 : freeMsels[a][low[a]++];
911 setAmsel[masters] = amselOf(a, msel);
912 plan.amselMasters[amselOf(a, msel)] = masters;
914 for (
size_t f : unit.flows)
915 plan.slaveAmsels[{flows[f].slave, flows[f].id}] =
916 setAmsel.at(flows[f].masters);
922SmallVector<TileID> cutTiles(
const AIETargetModel &targetModel,
TileID src,
924 auto neighbors = [&](
TileID t) {
925 SmallVector<TileID, 4> next;
926 for (
auto [bundle, dc, dr] : {std::tuple{WireBundle::North, 0, 1},
927 {WireBundle::South, 0, -1},
928 {WireBundle::East, 1, 0},
929 {WireBundle::West, -1, 0}}) {
930 TileID n{t.col + dc, t.row + dr};
931 if (n.col >= 0 && n.col < targetModel.
columns() && n.row >= 0 &&
932 n.row < targetModel.
rows() &&
938 auto reach = [&](std::optional<TileID> avoid) {
939 return breadthFirstParents(
942 SmallVector<TileID, 4> next = neighbors(t);
943 llvm::erase(next, avoid);
948 std::map<TileID, TileID> via = reach(std::nullopt);
951 SmallVector<TileID> interior;
952 for (
TileID t = via.at(dst); t != src; t = via.at(t))
953 interior.push_back(t);
954 llvm::erase_if(interior, [&](
TileID t) {
return reach(t).count(dst) > 0; });
960struct PrioritizedPackets {
961 std::set<std::tuple<TileID, Port, int>> packets;
962 bool contains(
const RoutedStream &s)
const {
967PrioritizedPackets prioritizedPackets(DeviceOp device) {
968 PrioritizedPackets prioritized;
969 for (PacketFlowOp flow : device.getOps<PacketFlowOp>())
970 if (flow.getPriorityRoute().value_or(
false))
971 for (
auto src : flow.getPorts().getOps<PacketSourceOp>())
972 prioritized.packets.insert(
973 {cast<TileOp>(src.getTile().getDefiningOp()).getTileID(),
974 src.port(), flow.IDInt()});
981SmallVector<size_t, 8> largestApartSet(
const StreamConflicts &conflicts,
982 ArrayRef<size_t> candidates,
984 SmallVector<size_t, 8> clique, best;
986 auto grow = [&](
auto &self, ArrayRef<size_t> cands) ->
void {
987 if (clique.size() > best.size())
989 for (
auto [k, s] : llvm::enumerate(cands)) {
991 clique.size() + cands.size() - k <= best.size())
993 SmallVector<size_t, 8> next;
994 for (
size_t t : cands.drop_front(k + 1))
1002 grow(grow, candidates);
1009std::map<TileID, std::set<int>> configuredAmsels(DeviceOp device) {
1010 const int numArbiters = device.getTargetModel().getNumArbiters();
1011 std::map<TileID, std::set<int>> amsels;
1012 for (
auto swboxOp : device.getOps<SwitchboxOp>())
1013 for (
auto amselOp : swboxOp.getConnections().getOps<AMSelOp>())
1014 amsels[swboxOp.getTileOp().getTileID()].insert(
1015 amselOp.arbiterIndex() + amselOp.getMselValue() * numArbiters);
1027std::optional<std::string>
1028tooFewArbiters(DeviceOp device,
const StreamConflicts &conflicts,
1029 llvm::function_ref<
bool(
TileID)> pinsHops,
1030 const PrioritizedPackets &prioritized) {
1031 const AIETargetModel &targetModel = device.getTargetModel();
1034 std::map<TileID, SmallVector<size_t, 8>> pinned;
1038 pinned[s.dst.tile].push_back(i);
1039 if (s.src.tile == s.dst.tile)
1041 bool circuitless = prioritized.contains(s);
1042 if (circuitless || pinsHops(s.src.tile))
1043 pinned[s.src.tile].push_back(i);
1044 for (
TileID t : cutTiles(targetModel, s.src.tile, s.dst.tile))
1045 if (circuitless || pinsHops(t))
1046 pinned[t].push_back(i);
1048 std::map<TileID, std::set<int>> reserved = configuredAmsels(device);
1050 ArrayRef<RoutedStream> streams = conflicts.
getStreams();
1051 for (
const auto &[tileId, candidates] : pinned) {
1052 const std::set<int> &taken = reserved[tileId];
1054 for (
int a = 0; a < numArbiters; a++)
1055 free += llvm::any_of(llvm::seq(numMselsPerArbiter), [&](
int m) {
1056 return !taken.count(a + m * numArbiters);
1059 std::set<std::pair<TileID, Port>> srcs, dsts;
1060 for (
size_t s : candidates) {
1061 srcs.insert({streams[s].src.tile, streams[s].src.port});
1062 dsts.insert({streams[s].dst.tile, streams[s].dst.port});
1064 if (std::min(srcs.size(), dsts.size()) <= free)
1066 SmallVector<size_t, 8> best = largestApartSet(conflicts, candidates, free);
1067 if (best.size() <= free)
1071 llvm::raw_string_ostream os(reason);
1072 if (best.size() == 1) {
1073 os <<
"at tile (" << tileId.col <<
", " << tileId.row <<
"), "
1075 <<
" takes an arbiter whatever the routing, but the switchbox has "
1079 os <<
"at tile (" << tileId.col <<
", " << tileId.row <<
"), no two of ";
1081 best, os, [&](
size_t s) { os <<
describeStream(streams[s]); },
", ");
1082 os <<
" can share an arbiter, and each takes one there whatever the "
1083 "routing, but the switchbox has "
1084 << free <<
" free. For example, " << conflicts.
explain(best[0], best[1]);
1087 return std::nullopt;
1094 std::optional<Port> slave;
1100std::pair<std::map<TileID, SmallVector<Leaving, 8>>, std::set<TileID>>
1101leavingPinnedTrees(
const StreamConflicts &conflicts,
1103 const PrioritizedPackets &prioritized) {
1105 std::map<PathEndPoint, std::map<PathEndPoint, std::optional<PathEndPoint>>>
1107 for (
const auto &[src, hops] : pinnedTrees)
1108 for (
const TreeHop &hop : hops) {
1109 auto [it, first] = preds[src].try_emplace(hop.to, hop.from);
1110 if (!first && it->second && !(*it->second == hop.from))
1113 std::map<TileID, SmallVector<Leaving, 8>> leaving;
1114 std::set<TileID> onTrees;
1119 auto tree = prioritized.contains(s) ? preds.find({s.src.tile, s.src.port})
1121 SmallVector<std::pair<Port, PathEndPoint>, 8> hops;
1122 PathEndPoint at{s.dst.tile, s.dst.port}, src{s.src.tile, s.src.port};
1124 tree != preds.end() && !(at == src) && n <= tree->second.size(); n++) {
1125 auto pred = tree->second.find(at);
1126 if (pred == tree->second.end() || !pred->second)
1128 if (pred->second->coords == at.coords)
1129 hops.push_back({pred->second->port, at});
1133 leaving[s.dst.tile].push_back({i, std::nullopt, s.dst.port});
1136 for (
auto [slave, hop] : hops) {
1137 leaving[hop.coords].push_back({i, slave, hop.port});
1138 onTrees.insert(hop.coords);
1141 return {std::move(leaving), std::move(onTrees)};
1154std::string explainSharedArbiter(
TileID tileId,
size_t a,
size_t b,
1155 ArrayRef<ArbiterLink> chain,
1156 ArrayRef<Leaving> here,
1157 const StreamConflicts &conflicts) {
1158 ArrayRef<RoutedStream> streams = conflicts.
getStreams();
1160 llvm::raw_string_ostream os(reason);
1161 os <<
"at tile (" << tileId.col <<
", " << tileId.row
1162 <<
"), the routes prioritized flows (priority_route) keep put "
1165 for (
auto [k, link] : llvm::enumerate(chain))
1166 os << (k == 0 ?
"" :
", which")
1167 << (link.rule ?
" takes one packet rule on " :
" leaves by ")
1170 os <<
", and a master port or packet rule takes one arbiter. "
1178std::optional<std::string> sharedArbiterAt(
TileID tileId,
1179 ArrayRef<Leaving> here,
1180 const StreamConflicts &conflicts) {
1181 ArrayRef<RoutedStream> streams = conflicts.
getStreams();
1186 std::map<size_t, SmallVector<ArbiterLink, 4>> with;
1187 for (
auto [x, l] : llvm::enumerate(here))
1188 for (
auto [y, m] : llvm::enumerate(here)) {
1191 if (l.master == m.master)
1192 with[x].push_back({y, l.master,
false});
1193 else if (l.slave && m.slave && *l.slave == *m.slave &&
1194 streams[l.stream].packetID == streams[m.stream].packetID)
1195 with[x].push_back({y, *l.slave,
true});
1197 for (
size_t x : llvm::make_first_range(with)) {
1199 std::map<size_t, size_t> via = breadthFirstParents(x, [&](
size_t u) {
1200 return llvm::map_range(
1201 with.at(u), [](
const ArbiterLink &link) { return link.visit; });
1203 size_t a = here[x].stream;
1204 for (
size_t y : llvm::make_first_range(via)) {
1205 size_t b = here[y].stream;
1208 SmallVector<ArbiterLink, 4> chain;
1209 for (
size_t v = y; v != x; v = via.at(v))
1211 *llvm::find_if(with.at(via.at(v)), [&](
const ArbiterLink &link) {
1212 return link.visit == v;
1214 std::reverse(chain.begin(), chain.end());
1215 return explainSharedArbiter(tileId, a, b, chain, here, conflicts);
1218 return std::nullopt;
1225llvm::Error unroutableArbiters(DeviceOp device,
1226 const StreamConflicts &conflicts,
1227 llvm::function_ref<
bool(
TileID)> pinsHops,
1229 PrioritizedPackets prioritized = prioritizedPackets(device);
1230 if (std::optional<std::string> reason =
1231 tooFewArbiters(device, conflicts, pinsHops, prioritized))
1232 return llvm::make_error<RoutingFailure>(std::move(*reason));
1233 if (pinnedTrees.empty())
1234 return llvm::Error::success();
1235 auto [leaving, onTrees] =
1236 leavingPinnedTrees(conflicts, pinnedTrees, prioritized);
1237 for (
TileID tileId : onTrees)
1238 if (std::optional<std::string> reason =
1239 sharedArbiterAt(tileId, leaving[tileId], conflicts))
1240 return llvm::make_error<PinnedRoutingFailure>(std::move(*reason));
1241 return llvm::Error::success();
1245static void getOrCreateConnect(OpBuilder &builder, ShimMuxOp shimMux,
1246 Location loc, WireBundle srcBundle,
int srcCh,
1247 WireBundle destBundle,
int destCh) {
1248 for (
auto connect : shimMux.getConnections().getOps<ConnectOp>())
1249 if (connect.getSourceBundle() == srcBundle &&
1250 connect.getSourceChannel() == srcCh &&
1251 connect.getDestBundle() == destBundle &&
1252 connect.getDestChannel() == destCh)
1254 ConnectOp::create(builder, loc, srcBundle, srcCh, destBundle, destCh);
1257static PathEndPoint sourceOf(FlowOp flow) {
1258 auto tile = cast<TileOp>(flow.getSource().getDefiningOp());
1259 return PathEndPoint{tile.getTileID(),
1260 {flow.getSourceBundle(), flow.getSourceChannel()}};
1266static void lowerShimDMAPorts(DeviceOp device, OpBuilder &builder,
1267 DynamicTileAnalysis &analyzer) {
1268 for (
auto switchbox : device.getOps<SwitchboxOp>()) {
1269 TileOp tileOp = switchbox.getTileOp();
1270 if (!tileOp.isShimNOCTile())
1272 auto connectInMux = [&](Location loc,
Port src,
Port dst) {
1273 builder.setInsertionPointAfter(tileOp);
1274 ShimMuxOp shimMux = analyzer.
getShimMux(builder, tileOp.colIndex());
1275 builder.setInsertionPointToStart(&shimMux.getConnections().front());
1276 getOrCreateConnect(builder, shimMux, loc, src.bundle, src.channel,
1277 dst.bundle, dst.channel);
1279 for (Operation &op : switchbox.getConnections().front()) {
1280 if (
auto rules = dyn_cast<PacketRulesOp>(op);
1281 rules && rules.getSourceBundle() == WireBundle::DMA) {
1283 connectInMux(rules.getLoc(), rules.sourcePort(),
1284 {WireBundle::North, ch});
1285 rules.setSourceBundle(WireBundle::South);
1286 rules.setSourceChannel(ch);
1288 if (
auto masterSet = dyn_cast<MasterSetOp>(op);
1289 masterSet && masterSet.getDestBundle() == WireBundle::DMA) {
1291 connectInMux(masterSet.getLoc(), {WireBundle::North, ch},
1292 masterSet.destPort());
1293 masterSet.setDestBundle(WireBundle::South);
1294 masterSet.setDestChannel(ch);
1304 LogicalResult emit(DeviceOp device, OpBuilder &builder,
1305 DynamicTileAnalysis &analyzer)
const;
1306 SmallVector<std::pair<int, int>, 2>
1307 statedCubes(
const std::pair<PhysPort, int> &slaveFlow,
int idMask)
const;
1311 std::optional<HoldCycle> sharedReceiverCycle;
1315 std::map<std::pair<PhysPort, int>, SmallVector<PhysPort, 4>> packetFlows;
1316 SmallVector<std::pair<PhysPort, int>, 4> slavePorts;
1319 std::map<std::pair<PhysPort, int>, SmallVector<Location, 1>> slaveFlowLocs;
1321 DenseMap<Location, unsigned> flowLocOrder;
1323 Location locOf(ArrayRef<std::pair<PhysPort, int>> slaveFlows,
1324 Location fallback)
const;
1326 DenseMap<PhysPort, BoolAttr> keepPktHeaderAttr;
1329 DenseSet<std::pair<PhysPort, int>> prioritizedFlows;
1330 DenseSet<std::pair<PhysPort, int>> markedFlows;
1331 DenseSet<PhysPort> priorityMasterPorts;
1337 std::map<std::pair<PhysPort, int>, std::set<int>> pinnedMasks;
1348 std::map<TileID, SmallVector<Connect, 4>> circuitHops;
1349 std::map<TileID, ArbiterPlan> plans;
1354struct PacketFlowRouting : PacketPlan {
1355 using FlowKey = std::pair<Port, int>;
1357 PacketFlowRouting(DeviceOp device,
const Routing &routing,
1358 const StreamConflicts &conflicts,
1359 const PinnedRoutes &pinned,
bool routeCircuit,
1360 bool circuitSwitchHops,
bool prioritize)
1361 : device(device), routing(routing), conflicts(conflicts), pinned(pinned),
1362 prioritize(prioritize), routeCircuit(routeCircuit),
1363 circuitSwitchHops(circuitSwitchHops),
1365 numArbiters(targetModel.getNumArbiters()),
1366 numMselsPerArbiter(targetModel.getNumMselsPerArbiter()),
1367 maxPacketId(targetModel.getMaxPacketId()),
1368 idBits(targetModel.getPacketIdBits()),
1369 idMask(targetModel.getPacketIdMask()) {}
1371 llvm::Expected<PacketPlan> plan();
1372 void collectFlows();
1373 void findCircuitHops();
1374 void collectSlaveFlows();
1377 std::optional<std::string> breakHoldCycles();
1378 RoutingFaults faults()
const;
1381 std::optional<int>
id = std::nullopt);
1382 std::optional<std::pair<size_t, size_t>>
1383 conflictingStreams(
TileID tileId,
const SlaveFlow &a,
const SlaveFlow &b);
1384 std::optional<ArbiterPlan>
1385 planTile(
TileID tileId, SmallVectorImpl<std::pair<size_t, size_t>> &blocking);
1386 void moveFlow(
TileID tileId,
FlowKey key,
bool priority =
false);
1388 void splitFlow(
TileID tileId,
FlowKey key, ArrayRef<FlowKey> partners);
1391 const Routing &routing;
1392 const StreamConflicts &conflicts;
1393 const PinnedRoutes &pinned;
1397 bool circuitSwitchHops;
1398 const AIETargetModel &targetModel;
1399 const int numArbiters;
1400 const int numMselsPerArbiter;
1401 const uint32_t maxPacketId;
1410 PathEndPoint src, dst;
1412 bool operator<(
const StreamEnds &rhs)
const {
1413 return std::tie(src, dst,
id) < std::tie(rhs.src, rhs.dst, rhs.id);
1416 std::map<StreamEnds, SmallVector<size_t, 1>> packetStreamIndex;
1417 DenseMap<std::pair<PhysPort, int>, SmallVector<size_t, 2>> slaveFlowStreams;
1421 std::map<std::pair<PhysPort, int>, std::map<PathEndPoint, std::set<Port>>>
1425 std::vector<SmallVector<StreamHop, 8>> routes;
1427 std::set<PathEndPoint> circuitSources;
1431 std::map<TileID, SmallVector<std::pair<Connect, int>, 8>> switchboxes;
1435 std::map<TileID, std::set<int>> reservedAmsels;
1439 std::map<TileID, std::map<FlowKey, SlaveFlow>> tileSlaveFlows;
1440 std::map<TileID, SmallVector<SlaveFlow, 8>> tileFlows;
1443 std::set<std::tuple<TileID, FlowKey, FlowKey>> apart;
1444 std::set<std::tuple<TileID, FlowKey, int>> offArbiter;
1445 std::set<std::pair<TileID, Connect>> hazardConnections;
1446 std::set<std::pair<TileID, Connect>> priorityConnections;
1451 std::set<TreeSplit> hazardSplits;
1452 std::set<std::pair<PathEndPoint, PathEndPoint>> hazardApart;
1453 std::set<std::pair<PathEndPoint, PathEndPoint>> hazardTogether;
1454 std::set<PathEndPoint> hazardUntrunk;
1455 std::set<TileID> crowdedTiles;
1456 std::optional<std::string> planFailure;
1457 std::optional<std::pair<Location, std::string>> incomplete;
1461void PacketFlowRouting::collectFlows() {
1462 for (
auto [i, s] : llvm::enumerate(conflicts.
getStreams()))
1464 packetStreamIndex[{{s.src.tile, s.src.port},
1465 {s.dst.tile, s.dst.port},
1468 for (
const RoutedStream &s : conflicts.
getStreams())
1469 routes.push_back(s.hops);
1472 for (FlowOp flow : device.getOps<FlowOp>())
1473 circuitSources.insert(sourceOf(flow));
1475 for (PacketFlowOp pktFlowOp : device.getOps<PacketFlowOp>()) {
1476 Region &r = pktFlowOp.getPorts();
1477 Block &b = r.front();
1478 int flowID = pktFlowOp.IDInt();
1479 SmallVector<std::pair<TileID, Port>, 4> sources;
1482 for (Operation &Op : b.getOperations()) {
1483 if (
auto pktSource = dyn_cast<PacketSourceOp>(Op)) {
1484 auto srcTile = cast<TileOp>(pktSource.getTile().getDefiningOp());
1486 {{srcTile.colIndex(), srcTile.rowIndex()}, pktSource.port()});
1491 for (Operation &Op : b.getOperations()) {
1492 auto pktDest = dyn_cast<PacketDestOp>(Op);
1495 auto destTile = cast<TileOp>(pktDest.getTile().getDefiningOp());
1496 Port destPort = pktDest.port();
1497 TileID destCoords = {destTile.colIndex(), destTile.rowIndex()};
1499 auto keep = pktFlowOp.getKeepPktHeader();
1500 keepPktHeaderAttr[{destTile.getTileID(), destPort}] =
1501 keep ? BoolAttr::get(Op.getContext(), *keep) : nullptr;
1503 for (
auto &[srcCoords, srcPort] : sources) {
1504 TileID srcSB = {srcCoords.col, srcCoords.row};
1505 PathEndPoint srcPoint = {srcSB, srcPort};
1506 if (circuitSources.count(srcPoint))
1511 SmallVector<size_t, 1> flowStreams;
1512 if (
auto stream = packetStreamIndex.find(
1513 {srcPoint, {destCoords, destPort}, flowID});
1514 stream != packetStreamIndex.end()) {
1515 int mask =
static_cast<int>(pktFlowOp.getMask().value_or(~0));
1516 for (
size_t i : stream->second)
1518 conflicts.
getStreams()[i].packetMask == mask)
1519 flowStreams.push_back(i);
1520 if (flowStreams.empty())
1521 flowStreams.push_back(stream->second.front());
1523 for (
size_t stream : flowStreams) {
1524 SmallVector<StreamHop, 8> &hops = routes[stream];
1527 size_t connections = 0;
1528 for (
const auto &[_, setting] : settings)
1529 connections += setting.srcs.size();
1530 std::optional<std::pair<TileID, Port>> at{{srcSB, srcPort}};
1531 while (at && hops.size() <= connections) {
1532 auto [tile, input] = *at;
1533 hops.push_back({tile, input, std::nullopt});
1535 auto setting = settings.find(tile);
1536 if (setting == settings.end())
1538 for (
auto [src, dest] :
1539 llvm::zip(setting->second.srcs, setting->second.dsts))
1540 if (src == input && !(tile == destCoords && dest == destPort) &&
1541 findPathToDest(settings, tile, dest, destCoords, destPort)) {
1542 at = linkedInput(tile, dest);
1548 bool srcRouted =
false;
1550 for (
const auto &[curr, setting] : settings) {
1551 assert(setting.srcs.size() == setting.dsts.size());
1552 TileID currTile = {curr.col, curr.row};
1553 for (
size_t i = 0; i < setting.srcs.size(); i++) {
1554 Port src = setting.srcs[i];
1555 Port dest = setting.dsts[i];
1557 if (!findPathToDest(settings, currTile, dest, destCoords, destPort))
1559 if (currTile == srcSB && src.bundle == srcPort.bundle &&
1560 src.channel == srcPort.channel)
1562 Connect connect = {{src.bundle, src.channel},
1563 {dest.bundle, dest.channel}};
1565 switchboxes[currTile].begin(), switchboxes[currTile].end(),
1566 std::pair{connect, flowID}) == switchboxes[currTile].end())
1567 switchboxes[currTile].push_back({connect, flowID});
1570 PhysPort slavePort = {currTile, {src.bundle, src.channel}};
1571 std::pair<PhysPort, int> slaveFlow = {slavePort, flowID};
1572 for (
size_t stream : flowStreams)
1573 if (!llvm::is_contained(slaveFlowStreams[slaveFlow], stream))
1574 slaveFlowStreams[slaveFlow].push_back(stream);
1575 slaveFlowSources[slaveFlow][srcPoint].insert(dest);
1576 if (!llvm::is_contained(slaveFlowLocs[slaveFlow],
1577 pktFlowOp.getLoc()))
1578 slaveFlowLocs[slaveFlow].push_back(pktFlowOp.getLoc());
1579 flowLocOrder.try_emplace(pktFlowOp.getLoc(), flowLocOrder.size());
1580 if (std::optional<uint8_t> mask = pktFlowOp.getMask()) {
1581 pinnedMasks[{{currTile, {src.bundle, src.channel}}, flowID}]
1584 if (pktFlowOp.getPriorityRoute().value_or(
false)) {
1585 markedFlows.insert(slaveFlow);
1586 if (prioritize || pinned.trees.count(srcPoint)) {
1587 prioritizedFlows.insert(slaveFlow);
1592 if (!srcRouted && !incomplete)
1596 " could not be routed to destination " +
1598 "; the pathfinder produced an incomplete routing for this "
1605Location PacketPlan::locOf(ArrayRef<std::pair<PhysPort, int>> slaveFlows,
1606 Location fallback)
const {
1607 SmallVector<Location, 2> locs;
1608 for (
const auto &flow : slaveFlows)
1609 if (
auto found = slaveFlowLocs.find(flow); found != slaveFlowLocs.end())
1610 for (Location loc : found->second)
1611 if (!llvm::is_contained(locs, loc))
1612 locs.push_back(loc);
1615 llvm::sort(locs, [&](Location a, Location b) {
1616 return flowLocOrder.lookup(a) < flowLocOrder.lookup(b);
1618 return FusedLoc::get(fallback.getContext(), locs);
1624SmallVector<std::pair<int, int>, 2>
1625PacketPlan::statedCubes(
const std::pair<PhysPort, int> &slaveFlow,
1627 SmallVector<std::pair<int, int>, 2> cubes;
1628 auto it = pinnedMasks.find(slaveFlow);
1629 if (it != pinnedMasks.end())
1630 for (
int mask : it->second)
1632 cubes.push_back({mask, slaveFlow.second});
1636const SwitchSettings &PacketFlowRouting::settingsOf(
const PathEndPoint &src,
1637 std::optional<int>
id) {
1639 if (
auto own = routing.
idSettings.find({src, *id});
1642 auto it = routing.
settings.find(src);
1643 return it == routing.
settings.end() ? noSettings : it->second;
1646void PacketFlowRouting::findCircuitHops() {
1649 reservedAmsels = configuredAmsels(device);
1652 std::set<PhysPort> claimedSlaves, claimedMasters;
1653 for (
auto swbox : device.getOps<SwitchboxOp>()) {
1654 TileID tileId = swbox.getTileOp().getTileID();
1655 Region &ops = swbox.getConnections();
1656 for (
auto connect : ops.getOps<ConnectOp>()) {
1657 claimedSlaves.insert({tileId, connect.sourcePort()});
1658 claimedMasters.insert({tileId, connect.destPort()});
1660 for (
auto rules : ops.getOps<PacketRulesOp>())
1661 claimedSlaves.insert({tileId, rules.sourcePort()});
1662 for (
auto masterSet : ops.getOps<MasterSetOp>())
1663 claimedMasters.insert({tileId, masterSet.destPort()});
1667 for (FlowOp flow : device.getOps<FlowOp>())
1668 for (
const auto &[tileId, setting] : settingsOf(sourceOf(flow))) {
1669 for (
Port p : setting.srcs)
1670 claimedSlaves.insert({tileId, p});
1671 for (
Port p : setting.dsts)
1672 claimedMasters.insert({tileId, p});
1674 for (
auto &[tileId, connects] : switchboxes) {
1675 if (!circuitSwitchHops ||
1678 std::set<Port> masters;
1679 for (
const auto &[conn, flowID] : connects)
1680 masters.insert(conn.dst);
1681 SmallVector<Port, 8> slaves;
1682 for (
const auto &[conn, flowID] : connects)
1683 if (!llvm::is_contained(slaves, conn.src))
1684 slaves.push_back(conn.src);
1685 const std::set<int> &reserved = reservedAmsels[tileId];
1686 size_t freeArbiters = llvm::count_if(llvm::seq(0, numArbiters), [&](
int a) {
1687 return llvm::none_of(llvm::seq(0, numMselsPerArbiter), [&](
int m) {
1688 return reserved.count(a + m * numArbiters);
1691 for (
Port slave : slaves) {
1692 if (masters.size() <= freeArbiters)
1694 std::set<Port> reached;
1695 std::map<int, std::set<Port>> reachedByID;
1696 for (
const auto &[conn, flowID] : connects)
1697 if (conn.src == slave) {
1698 reached.insert(conn.dst);
1699 reachedByID[flowID].insert(conn.dst);
1702 !claimedSlaves.count({tileId, slave}) &&
1703 llvm::all_of(reached,
1704 [&, tileId = tileId](
Port m) {
1706 !claimedMasters.count({tileId, m});
1710 [&](
const auto &ids) {
return ids.second == reached; }) &&
1711 llvm::all_of(connects, [&, tileId = tileId](
const auto &entry) {
1712 const auto &[other, otherID] = entry;
1713 if (!reached.count(other.dst))
1715 return other.src == slave &&
1716 !prioritizedFlows.contains({{tileId, slave}, otherID});
1720 for (
Port m : reached) {
1721 circuitHops[tileId].push_back({slave, m});
1724 llvm::erase_if(connects, [&](
const auto &entry) {
1725 return entry.first.src == slave;
1731void PacketFlowRouting::collectSlaveFlows() {
1732 LLVM_DEBUG(llvm::dbgs() <<
"Check switchboxes\n");
1734 for (
const auto &[tileId, connects] : switchboxes) {
1735 LLVM_DEBUG(llvm::dbgs() <<
"***switchbox*** " << tileId.col <<
" "
1736 << tileId.row <<
'\n');
1737 for (
const auto &[conn, flowID] : connects) {
1738 Port sourcePort = conn.src;
1739 Port destPort = conn.dst;
1741 std::make_pair(std::make_pair(tileId, sourcePort), flowID);
1742 packetFlows[sourceFlow].push_back({tileId, destPort});
1743 if (markedFlows.contains(sourceFlow))
1744 priorityMasterPorts.insert({tileId, destPort});
1745 slavePorts.push_back(sourceFlow);
1746 LLVM_DEBUG(llvm::dbgs() <<
"flowID " << flowID <<
':'
1747 << stringifyWireBundle(sourcePort.bundle) <<
" "
1748 << sourcePort.channel <<
" -> "
1749 << stringifyWireBundle(destPort.bundle) <<
" "
1750 << destPort.channel <<
"\n");
1754 for (
const auto &[flow, dests] : packetFlows) {
1755 SlaveFlow &f = tileSlaveFlows[flow.first.first]
1756 .try_emplace({flow.first.second, flow.second},
1757 SlaveFlow{flow.first.second,
1760 prioritizedFlows.contains(flow)})
1763 if (!llvm::is_contained(f.masters, dest.second))
1764 f.masters.push_back(dest.second);
1765 llvm::sort(f.masters);
1767 for (
const auto &[tileId, byFlow] : tileSlaveFlows)
1768 for (
const auto &[key, f] : byFlow)
1769 tileFlows[tileId].push_back(f);
1772std::optional<std::pair<size_t, size_t>>
1773PacketFlowRouting::conflictingStreams(
TileID tileId,
const SlaveFlow &a,
1774 const SlaveFlow &b) {
1775 auto as = slaveFlowStreams.find({{tileId, a.slave}, a.id});
1776 auto bs = slaveFlowStreams.find({{tileId, b.slave}, b.id});
1777 if (as == slaveFlowStreams.end() || bs == slaveFlowStreams.end())
1778 return std::nullopt;
1779 for (
size_t s : as->second)
1780 for (
size_t t : bs->second)
1782 return std::pair{s, t};
1783 return std::nullopt;
1786std::optional<ArbiterPlan> PacketFlowRouting::planTile(
1787 TileID tileId, SmallVectorImpl<std::pair<size_t, size_t>> &blocking) {
1788 ArrayRef<SlaveFlow> flows = tileFlows.at(tileId);
1789 auto key = [&](
size_t f) {
return FlowKey{flows[f].slave, flows[f].id}; };
1790 auto conflict = [&](
size_t a,
size_t b) {
1792 {tileId, std::min(key(a), key(b)), std::max(key(a), key(b))}) ||
1793 conflictingStreams(tileId, flows[a], flows[b]);
1795 auto excluded = [&](
size_t f,
int arbiter) {
1796 return offArbiter.count({tileId, key(f), arbiter}) > 0;
1798 SmallVector<size_t, 8> priority, others;
1799 for (
auto [i, f] : llvm::enumerate(flows))
1800 (f.isPriority ? priority : others).push_back(i);
1801 if (priority.empty() || (others.empty() && pinned.rules.empty()))
1802 return planArbiters(targetModel, flows, conflict, excluded,
1803 reservedAmsels[tileId], blocking);
1805 auto subset = [&](ArrayRef<size_t> members) {
1806 SmallVector<SlaveFlow, 8> sub;
1807 for (
size_t m : members)
1808 sub.push_back(flows[m]);
1811 auto keepPinned = [&]() -> std::optional<ArbiterPlan> {
1813 for (
size_t f : priority) {
1814 Port slave = flows[f].slave;
1815 if (slave.bundle == WireBundle::DMA &&
1818 auto rules = pinned.rules.find({tileId, slave});
1819 const std::tuple<int, int, int> *rule =
nullptr;
1820 if (rules != pinned.rules.end())
1821 rule = llvm::find_if(rules->second, [&](
const auto &r) {
1822 auto [mask, value, amsel] = r;
1823 return (flows[f].id & mask) == (value & mask);
1825 if (!rule || rule == rules->second.end())
1826 return std::nullopt;
1827 int amsel = std::get<2>(*rule);
1828 if (excluded(f, amsel % numArbiters) ||
1829 reservedAmsels[tileId].count(amsel) ||
1830 kept.amselMasters.try_emplace(amsel, flows[f].masters)
1831 .first->second != flows[f].masters)
1832 return std::nullopt;
1833 kept.slaveAmsels[key(f)] = amsel;
1835 for (
auto [k, a] : llvm::enumerate(priority))
1836 for (
size_t b : llvm::drop_begin(priority, k + 1))
1837 if (kept.slaveAmsels.at(key(a)) % numArbiters ==
1838 kept.slaveAmsels.at(key(b)) % numArbiters &&
1839 flows[a].slave != flows[b].slave && conflict(a, b)) {
1840 return std::nullopt;
1844 SmallVector<std::pair<size_t, size_t>, 4> stuck;
1845 std::optional<ArbiterPlan> plan;
1846 if (!pinned.rules.empty())
1847 plan = keepPinned();
1849 plan = planArbiters(
1850 targetModel, subset(priority),
1851 [&](
size_t a,
size_t b) {
return conflict(priority[a], priority[b]); },
1852 [&](
size_t f,
int arbiter) {
return excluded(priority[f], arbiter); },
1853 reservedAmsels[tileId], stuck);
1855 for (
auto [a, b] : stuck)
1856 blocking.push_back({priority[a], priority[b]});
1857 return std::nullopt;
1863 auto around = [&](ArbiterPlan plan, ArrayRef<size_t> planned,
1864 ArrayRef<size_t> pending,
1865 SmallVectorImpl<std::pair<size_t, size_t>> &blocking)
1866 -> std::optional<ArbiterPlan> {
1867 auto arbiterOf = [&](
size_t f) {
1868 return plan.slaveAmsels.at(key(f)) % numArbiters;
1870 SmallVector<size_t, 8> placed(planned), rest;
1871 for (
size_t f : pending) {
1872 auto same = llvm::find_if(plan.amselMasters, [&](
const auto &entry) {
1873 return entry.second == flows[f].masters;
1875 if (same == plan.amselMasters.end()) {
1879 for (
size_t g : placed)
1880 if (arbiterOf(g) == same->first % numArbiters &&
1881 flows[g].slave != flows[f].slave && conflict(f, g))
1882 blocking.push_back({g, f});
1883 if (excluded(f, same->first % numArbiters))
1884 blocking.push_back({planned.front(), f});
1885 plan.slaveAmsels[key(f)] = same->first;
1886 placed.push_back(f);
1888 if (!blocking.empty())
1889 return std::nullopt;
1895 llvm::EquivalenceClasses<Port> tied = tiedMasters(flows);
1896 std::map<Port, std::set<int>> tiedArbiters;
1897 std::set<int> reserved = reservedAmsels[tileId];
1898 for (
const auto &[amsel, masters] : plan.amselMasters) {
1899 reserved.insert(amsel);
1900 tiedArbiters[tied.getLeaderValue(masters.front())].insert(amsel %
1903 SmallVector<std::pair<size_t, size_t>, 4> stuck;
1904 std::optional<ArbiterPlan> rested = planArbiters(
1905 targetModel, subset(rest),
1906 [&](
size_t a,
size_t b) {
return conflict(rest[a], rest[b]); },
1907 [&](
size_t f,
int arbiter) {
1908 auto arbiters = tiedArbiters.find(
1909 tied.getLeaderValue(flows[rest[f]].masters.front()));
1910 return excluded(rest[f], arbiter) ||
1911 (arbiters != tiedArbiters.end() &&
1912 (arbiters->second.size() > 1 ||
1913 !arbiters->second.count(arbiter))) ||
1914 llvm::any_of(placed, [&](
size_t g) {
1915 return arbiterOf(g) == arbiter &&
1916 flows[g].slave != flows[rest[f]].slave &&
1917 conflict(rest[f], g);
1922 for (
auto [a, b] : stuck)
1923 blocking.push_back({rest[a], rest[b]});
1924 for (
size_t f : rest)
1925 for (
size_t g : placed)
1926 if (flows[g].slave != flows[f].slave && conflict(f, g))
1927 blocking.push_back({g, f});
1928 return std::nullopt;
1930 plan.slaveAmsels.insert(rested->slaveAmsels.begin(),
1931 rested->slaveAmsels.end());
1932 plan.amselMasters.insert(rested->amselMasters.begin(),
1933 rested->amselMasters.end());
1936 SmallVector<std::pair<size_t, size_t>, 4> first;
1937 if (std::optional<ArbiterPlan> placed =
1938 around(*plan, priority, others, first))
1941 llvm::EquivalenceClasses<Port> tied = tiedMasters(flows);
1942 SmallVector<size_t, 8> joint(priority), rest;
1943 for (
size_t f : others) {
1944 bool tiedToPriority = llvm::any_of(priority, [&](
size_t g) {
1945 return tied.isEquivalent(flows[g].masters.front(),
1946 flows[f].masters.front());
1948 (tiedToPriority ? joint : rest).push_back(f);
1951 std::optional<ArbiterPlan> together;
1952 if (joint.size() > priority.size())
1953 together = planArbiters(
1954 targetModel, subset(joint),
1955 [&](
size_t a,
size_t b) {
return conflict(joint[a], joint[b]); },
1956 [&](
size_t f,
int arbiter) {
return excluded(joint[f], arbiter); },
1957 reservedAmsels[tileId], stuck);
1959 blocking.append(first.begin(), first.end());
1960 return std::nullopt;
1962 return around(*together, joint, rest, blocking);
1965void PacketFlowRouting::moveFlow(
TileID tileId,
FlowKey key,
bool priority) {
1966 auto move = [&](
const Connect &c) {
1967 hazardConnections.insert({tileId, c});
1969 priorityConnections.insert({tileId, c});
1971 auto flows = tileSlaveFlows.find(tileId);
1972 if (flows != tileSlaveFlows.end())
1973 if (
auto f = flows->second.find(key); f != flows->second.end())
1974 for (
Port m : f->second.masters)
1975 move({key.first, m});
1976 for (
const Connect &hop : circuitHops[tileId])
1977 if (hop.src == key.first)
1983void PacketFlowRouting::moveUnit(
TileID tileId,
FlowKey key) {
1984 moveFlow(tileId, key);
1985 auto flows = tileSlaveFlows.find(tileId);
1986 if (flows == tileSlaveFlows.end())
1988 auto self = flows->second.find(key);
1989 if (self == flows->second.end())
1991 llvm::EquivalenceClasses<Port> tied =
1992 tiedMasters(llvm::make_second_range(flows->second));
1993 for (
const auto &[other, f] : flows->second)
1994 if (f.masters.size() > 1 &&
1995 tied.isEquivalent(f.masters.front(), self->second.masters.front()))
1996 moveFlow(tileId, other);
1999void PacketFlowRouting::splitFlow(
TileID tileId,
FlowKey key,
2000 ArrayRef<FlowKey> partners) {
2001 auto flows = tileSlaveFlows.find(tileId);
2002 if (flows == tileSlaveFlows.end())
2004 auto self = flows->second.find(key);
2005 if (self == flows->second.end())
2007 auto onlySource = [&](
FlowKey k) -> std::optional<PathEndPoint> {
2008 auto sources = slaveFlowSources.find({{tileId, k.first}, k.second});
2009 if (sources == slaveFlowSources.end() || sources->second.size() != 1)
2010 return std::nullopt;
2011 return sources->second.begin()->first;
2013 std::optional<PathEndPoint> src = onlySource(key);
2016 auto sharesMaster = [&](
const auto &f,
const std::set<Port> &ports) {
2017 return llvm::any_of(f.masters, [&](
Port m) { return ports.count(m); });
2019 std::set<Port> own(self->second.masters.begin(), self->second.masters.end());
2020 std::set<FlowKey> siblings;
2021 for (
const auto &[other, f] : flows->second)
2022 if (other != key && other.first == key.first && sharesMaster(f, own) &&
2023 onlySource(other) == src)
2024 siblings.insert(other);
2027 auto tied = [&](
FlowKey partner,
bool skipSiblings) {
2028 llvm::EquivalenceClasses<Port> classes =
2029 tiedMasters(llvm::make_filter_range(
2030 llvm::make_second_range(flows->second), [&](
const SlaveFlow &f) {
2031 FlowKey other{f.slave, f.id};
2032 return other != key && !(skipSiblings && siblings.count(other));
2034 auto unit = classes.members(flows->second.at(partner).masters.front());
2035 return std::set<Port>(unit.begin(), unit.end());
2037 auto split = [&](
FlowKey other,
2038 std::optional<PathEndPoint> apart = std::nullopt) {
2039 int a = key.second, b = other.second;
2040 if (!apart && a > b)
2042 hazardSplits.insert({*src, tileId, a, b, apart});
2044 for (
FlowKey partner : partners) {
2045 if (partner == key || !flows->second.count(partner))
2047 if (siblings.count(partner)) {
2051 std::set<Port> partnerUnit = tied(partner,
true);
2052 if (sharesMaster(self->second, partnerUnit))
2056 bool unjoined =
false;
2057 for (
FlowKey other : siblings)
2058 for (
Port m : flows->second.find(other)->second.masters)
2060 hazardConnections.insert({tileId, {other.first, m}});
2065 std::set<Port> unit = tied(partner,
false);
2066 for (
FlowKey other : siblings) {
2067 const SlaveFlow &f = flows->second.find(other)->second;
2068 if (!sharesMaster(f, unit))
2073 SmallVector<PathEndPoint, 2> apart;
2074 for (
Port m : f.masters)
2075 if (partnerUnit.count(m))
2076 apart.push_back({tileId, m});
2077 if (PathEndPoint{tileId, key.first} == *src || apart.empty() ||
2078 !llvm::all_of(apart, [&](
const PathEndPoint &p) {
2079 return packetStreamIndex.count({*src, p, other.second});
2084 for (
const PathEndPoint &p : apart)
2092llvm::Expected<PacketPlan> PacketFlowRouting::plan() {
2095 collectSlaveFlows();
2099 planFailure = breakHoldCycles();
2101 return llvm::make_error<RoutingFailure>(std::move(*planFailure), faults());
2102 return PacketPlan(std::move(*
this));
2105RoutingFaults PacketFlowRouting::faults()
const {
2106 RoutingFaults faults;
2107 faults.
connections.assign(hazardConnections.begin(), hazardConnections.end());
2108 faults.
splits.assign(hazardSplits.begin(), hazardSplits.end());
2109 faults.
crowded.assign(crowdedTiles.begin(), crowdedTiles.end());
2110 faults.
apart.assign(hazardApart.begin(), hazardApart.end());
2111 faults.
together.assign(hazardTogether.begin(), hazardTogether.end());
2112 faults.
untrunk.assign(hazardUntrunk.begin(), hazardUntrunk.end());
2114 hazardSplits.empty() && crowdedTiles.empty() &&
2115 hazardApart.empty() && hazardUntrunk.empty() &&
2116 hazardConnections == priorityConnections;
2120void PacketFlowRouting::checkRules() {
2123 std::map<PhysPort, SmallVector<std::pair<int, int>>> existingCubes;
2124 for (
auto swbox : device.getOps<SwitchboxOp>())
2125 for (
auto rules : swbox.getConnections().getOps<PacketRulesOp>())
2126 for (
auto rule : rules.getRules().getOps<PacketRuleOp>())
2127 existingCubes[{swbox.getTileOp().getTileID(), rules.sourcePort()}]
2128 .push_back({rule.maskInt(), rule.valueInt()});
2130 SmallVector<std::pair<int, int>, 4> stated;
2131 SmallVector<int, 4> derived;
2133 for (
const auto &[slaveFlow, sources] : slaveFlowSources) {
2134 const auto &[first, firstMasters] = *sources.begin();
2135 auto other = llvm::find_if(
2136 sources, [&, &firstMasters = firstMasters](
const auto &source) {
2137 return source.second != firstMasters;
2139 if (other == sources.end())
2141 const auto &[slavePort, id] = slaveFlow;
2142 TileID tileId = slavePort.first;
2143 moveFlow(tileId, {slavePort.second,
id});
2146 const PathEndPoint &second = other->first;
2147 planFailure = llvm::formatv(
2148 "at tile ({0}, {1}), packets with id {2} from {3} and {4} enter on {5} "
2149 "and leave by different ports; a switchbox routes on the id alone, so "
2150 "each source's packets would also go where the other's do.",
2155 for (
const auto &[tileId, byFlow] : tileSlaveFlows) {
2157 [&, tileId = tileId, &byFlow = byFlow](
2158 Port slave, std::optional<std::pair<PathEndPoint, Port>> without,
2160 SmallVector<SmallVector<Port, 4>> *groupMasters =
nullptr) {
2161 std::map<std::pair<bool, SmallVector<Port, 4>>, RuleGroup> groups;
2162 for (
const auto &[key, f] : byFlow) {
2163 if (f.slave != slave || (priorityOnly && !f.isPriority))
2165 SmallVector<Port, 4> masters = f.masters;
2166 auto sources = slaveFlowSources.find({{tileId, slave}, f.id});
2167 if (without && sources != slaveFlowSources.end()) {
2168 std::set<Port> kept;
2169 for (
const auto &[src, ports] : sources->second)
2170 for (
Port m : ports)
2171 if (!(src == without->first) || m != without->second)
2173 masters.assign(kept.begin(), kept.end());
2175 if (masters.empty())
2177 RuleGroup &group = groups[{f.isPriority, masters}];
2178 auto cubes = statedCubes({{tileId, f.slave}, f.id}, idMask);
2180 group.derived.push_back(f.id);
2181 for (
auto cube : cubes)
2182 if (!llvm::is_contained(group.stated, cube))
2183 group.stated.push_back(cube);
2185 SmallVector<GroupClaims> claims;
2186 for (
const auto &[masters, group] : groups) {
2187 claims.push_back({group.stated, group.derived, masters.first});
2189 groupMasters->push_back(masters.second);
2191 return slavePortRules(claims, existingCubes[{tileId, slave}], idBits,
2195 [&, tileId = tileId](
2197 std::optional<std::pair<PathEndPoint, Port>> without = {}) {
2198 return existingCubes[{tileId, slave}].size() +
2199 newRules(slave, without,
false).size();
2204 auto splitRules = [&, tileId = tileId, &byFlow = byFlow](
Port slave) {
2205 std::map<PathEndPoint, std::map<PathEndPoint, std::set<int>>> dstIds;
2206 for (
const auto &[key, f] : byFlow) {
2207 if (f.slave != slave)
2209 auto streams = slaveFlowStreams.find({{tileId, slave}, f.id});
2210 if (streams == slaveFlowStreams.end())
2212 for (
size_t i : streams->second) {
2213 const RoutedStream &s = conflicts.
getStreams()[i];
2218 std::optional<std::pair<PathEndPoint, PathEndPoint>> best;
2219 size_t fewest = rulesNeeded(slave);
2220 for (
const auto &[src, dsts] : dstIds)
2221 for (
const auto &[dst, ids] : dsts)
2222 if (dst.coords == tileId && dsts.size() > 1)
2223 if (
size_t n = rulesNeeded(slave, {{src, dst.port}}); n < fewest) {
2229 const auto &[src, apart] = *best;
2230 const std::set<int> &apartIds = dstIds[src][apart];
2231 for (
const auto &[dst, ids] : dstIds[src]) {
2232 auto carries = [&, &src = src, &dst = dst](
int id) {
2233 return packetStreamIndex.count({src, dst,
id}) > 0;
2235 auto b = llvm::find_if_not(apartIds, carries);
2236 if (!(dst == apart) && b != apartIds.end())
2237 hazardSplits.insert({src, tileId, *ids.begin(), *b, apart});
2244 auto claim = [&, tileId = tileId](
const SlaveFlow &f) {
2245 auto cubes = statedCubes({{tileId, f.slave}, f.id}, idMask);
2247 cubes.push_back({idMask, f.id});
2250 for (
auto a = byFlow.begin(); a != byFlow.end(); ++a)
2251 for (
auto b = std::next(a); b != byFlow.end(); ++b) {
2252 const SlaveFlow &fa = a->second, &fb = b->second;
2253 if (fa.slave != fb.slave || fa.masters == fb.masters)
2255 std::optional<std::pair<std::pair<int, int>, std::pair<int, int>>>
2257 for (
auto own : claim(fa))
2258 for (
auto other : claim(fb))
2259 if (!overlap && cubesIntersect(own, other))
2260 overlap = {own, other};
2263 auto [own, other] = *overlap;
2264 moveFlow(tileId, a->first);
2265 moveFlow(tileId, b->first);
2268 int witness = (own.second & own.first) |
2269 (other.second & other.first & ~own.first);
2270 planFailure = llvm::formatv(
2271 "at tile ({0}, {1}), packet flows through {2} claim rule (mask "
2272 "0x{3:X-}, id 0x{4:X-}) and rule (mask 0x{5:X-}, id 0x{6:X-}), "
2273 "which both match id 0x{7:X-}; widen one mask to carry both, or "
2274 "route them apart.",
2275 tileId.col, tileId.row,
describePort(fa.slave), own.first,
2276 own.second, other.first, other.second, witness);
2278 std::set<Port> slaves;
2279 for (
const auto &[key, f] : byFlow)
2280 slaves.insert(f.slave);
2281 std::set<Port> priorityMasters;
2282 std::set<SmallVector<Port, 4>> prioritySets;
2283 for (
const auto &[key, f] : byFlow)
2284 if (f.isPriority && !pinned.rules.empty()) {
2285 priorityMasters.insert(f.masters.begin(), f.masters.end());
2286 prioritySets.insert(f.masters);
2288 for (
const auto &[key, f] : byFlow) {
2289 const Port *shared = llvm::find_if(
2290 f.masters, [&](
Port m) { return priorityMasters.count(m); });
2291 if (f.isPriority || shared == f.masters.end() ||
2292 prioritySets.count(f.masters))
2294 moveFlow(tileId, key,
true);
2296 planFailure = llvm::formatv(
2297 "at tile ({0}, {1}), packets with id {2} entering on {3} leave by "
2298 "{4}, a master port of the prioritized flows, but not by one of "
2299 "their fixed master sets.",
2303 for (
Port slave : pinned.rules.empty() ? std::set<Port>{} : slaves) {
2304 SmallVector<SmallVector<Port, 4>> ruleMasters;
2305 SmallVector<PortRule> priority = newRules(slave, {},
true, &ruleMasters);
2306 for (
const auto &[key, f] : byFlow) {
2307 if (f.slave != slave || f.isPriority)
2309 for (
auto own : claim(f)) {
2311 llvm::find_if(priority, [&, &f = f](
const PortRule &r) {
2312 return cubesIntersect(own, {r.mask, r.value}) &&
2313 ruleMasters[r.group] != f.masters;
2315 if (rule == priority.end())
2317 moveFlow(tileId, key);
2319 planFailure = llvm::formatv(
2320 "at tile ({0}, {1}), the packet rule (mask 0x{2:X-}, id "
2321 "0x{3:X-}) of the prioritized flows on "
2322 "{4} also matches packet id 0x{5:X-}, and priority routing "
2323 "keeps their rules; use an id the rule does not match, "
2324 "or route the flow apart.",
2325 tileId.col, tileId.row, rule->mask, rule->value,
2331 for (
Port slave : slaves) {
2332 size_t needed = rulesNeeded(slave);
2335 for (
const auto &[key, f] : byFlow)
2336 if (f.slave == slave)
2337 moveFlow(tileId, key);
2338 if (!splitRules(slave))
2339 crowdedTiles.insert(tileId);
2342 planFailure = llvm::formatv(
2343 "at tile ({0}, {1}), the packet flows entering on {2} need {3} "
2344 "packet rules, and a slave port holds {4}.",
2351void PacketFlowRouting::planTiles() {
2352 for (
const auto &[tileId, flows] : tileFlows) {
2353 SmallVector<std::pair<size_t, size_t>, 4> blocking;
2354 if (std::optional<ArbiterPlan> plan = planTile(tileId, blocking)) {
2355 plans[tileId] = std::move(*plan);
2359 llvm::dbgs() <<
"No arbiter plan at tile (" << tileId.col <<
", "
2360 << tileId.row <<
"):\n";
2361 for (
const SlaveFlow &f : flows) {
2362 llvm::dbgs() <<
" " <<
describePort(f.slave) <<
" id " << f.id
2364 for (
Port m : f.masters)
2366 llvm::dbgs() <<
'\n';
2368 for (
auto [a, b] : blocking)
2369 llvm::dbgs() <<
" blocking " << a <<
' ' << b <<
'\n';
2372 llvm::raw_string_ostream os(reason);
2373 if (blocking.empty()) {
2376 for (
const SlaveFlow &f : flows)
2377 for (
const SlaveFlow &g : flows)
2378 if (f.slave == g.slave && f.id < g.id && f.masters != g.masters &&
2381 [&](
Port m) { return llvm::is_contained(g.masters, m); })) {
2382 FlowKey keys[] = {{f.slave, f.id}, {g.slave, g.id}};
2383 splitFlow(tileId, keys[0], keys);
2385 for (
const SlaveFlow &f : flows)
2386 moveFlow(tileId, {f.slave, f.id});
2387 crowdedTiles.insert(tileId);
2390 os <<
"at tile (" << tileId.col <<
", " << tileId.row
2391 <<
"), the packet flows need more arbiter msels than the switchbox "
2393 planFailure = std::move(reason);
2396 for (
auto [a, b] : blocking) {
2397 FlowKey keys[] = {{flows[a].slave, flows[a].id},
2398 {flows[b].slave, flows[b].id}};
2400 moveUnit(tileId, key);
2401 splitFlow(tileId, key, keys);
2406 std::optional<std::pair<size_t, size_t>> pair = conflictingStreams(
2407 tileId, flows[blocking.front().first], flows[blocking.front().second]);
2408 assert(pair && apart.empty() && offArbiter.empty() &&
2409 "before the hold-cycle search, only stream conflicts block a plan");
2410 auto [s, t] = *pair;
2413 <<
" can deadlock if they share an arbiter, and no routing found keeps "
2414 "them apart (last tried: tile ("
2415 << tileId.col <<
", " << tileId.row <<
")). " << conflicts.
explain(s, t);
2416 planFailure = std::move(reason);
2420std::optional<std::string> PacketFlowRouting::breakHoldCycles() {
2425 auto arbitrate = [&]() {
2429 for (StreamHop &hop : routes[s]) {
2430 hop.arbiter.reset();
2431 auto plan = plans.find(hop.tile);
2432 if (plan == plans.end())
2434 auto amsel = plan->second.slaveAmsels.find(
2435 {hop.input, *conflicts.
getStreams()[s].packetID});
2436 if (amsel != plan->second.slaveAmsels.end())
2437 hop.arbiter = amsel->second % numArbiters;
2441 ArrayRef<RoutedStream> streams = conflicts.
getStreams();
2445 SmallVector<HoldCycle, 2> cycles;
2447 bool forcedWaits =
false, definite =
false;
2448 auto search = [&](
auto &self) ->
bool {
2450 std::optional<HoldCycle> cycle =
2451 conflicts.
holdCycle(routes, forcedWaits, definite);
2454 if (!cycle && definite)
2458 cycles.push_back(*cycle);
2459 LLVM_DEBUG(llvm::dbgs()
2460 <<
"Hold cycle: " << conflicts.
explain(*cycle) <<
'\n');
2461 for (
const HoldCycle::Step &step : cycle->steps) {
2462 if (step.
wait != HoldCycle::Wait::Arbiter || step.
forced)
2466 bool sharerNew = step.
sharer < numRequested;
2467 bool holderNew = step.
holding < numRequested;
2468 std::optional<std::tuple<TileID, FlowKey, FlowKey>> pair;
2469 std::optional<std::tuple<TileID, FlowKey, int>> off;
2470 if (sharerNew && holderNew)
2471 pair = {step.
tile, std::min(sharer, holder), std::max(sharer, holder)};
2472 else if (sharerNew || holderNew)
2473 off = {step.
tile, sharerNew ? sharer : holder, step.
arbiter};
2478 if ((pair && !apart.insert(*pair).second) ||
2479 (off && !offArbiter.insert(*off).second))
2482 ArbiterPlan saved = plans.at(step.
tile);
2483 SmallVector<std::pair<size_t, size_t>, 4> blocking;
2484 if (std::optional<ArbiterPlan> plan = planTile(step.
tile, blocking)) {
2485 plans[step.
tile] = std::move(*plan);
2488 plans[step.
tile] = std::move(saved);
2493 offArbiter.erase(*off);
2501 for (
const HoldCycle &cycle : cycles)
2502 for (
const HoldCycle::Step &step : cycle.steps) {
2503 if (step.
wait == HoldCycle::Wait::Arbiter && step.
forced &&
2504 step.
sharer < numRequested && step.
holding < numRequested &&
2505 streams[step.
sharer].packetID && streams[step.
holding].packetID) {
2506 PathEndPoint a{streams[step.
sharer].src.tile,
2507 streams[step.
sharer].src.port},
2508 b{streams[step.
holding].src.tile, streams[step.
holding].src.port};
2510 hazardTogether.insert(std::minmax(a, b));
2512 if (step.
wait != HoldCycle::Wait::Drain && !step.
forced) {
2513 SmallVector<FlowKey, 3> keys;
2517 if (std::optional<int>
id = streams[s].packetID;
2518 s < numRequested && id)
2519 keys.push_back({input, *id});
2521 moveUnit(step.
tile, key);
2522 splitFlow(step.
tile, key, keys);
2527 if (behind >= numRequested || step.
holding >= numRequested ||
2528 !streams[behind].packetID || !streams[step.
holding].packetID)
2530 PathEndPoint a{streams[behind].src.tile, streams[behind].src.port},
2531 b{streams[step.
holding].src.tile, streams[step.
holding].src.port};
2534 hazardApart.insert(std::minmax(a, b));
2535 else if (step.
wait == HoldCycle::Wait::Arbiter)
2536 hazardUntrunk.insert(a);
2540 if (!search(search)) {
2542 return "packet flows can deadlock holding arbiters across "
2543 "switchboxes, and no arbiter assignment found avoids it. " +
2544 conflicts.
explain(cycles.front());
2553 if (!search(search)) {
2554 LLVM_DEBUG(llvm::dbgs() <<
"Hold cycle at a shared receiver: "
2555 << conflicts.
explain(cycles.front()) <<
'\n');
2559 if (!search(search)) {
2561 sharedReceiverCycle = cycles.front();
2564 return std::nullopt;
2567LogicalResult PacketPlan::emit(DeviceOp device, OpBuilder &builder,
2568 DynamicTileAnalysis &analyzer)
const {
2569 const AIETargetModel &targetModel = device.getTargetModel();
2575 AIEDialect::PriorityRouteAttrHelper priority(builder.getContext());
2576 UnitAttr unit = builder.getUnitAttr();
2584 std::map<std::pair<TileID, int>, SmallVector<Port, 4>> masterAMSels;
2585 DenseMap<std::pair<PhysPort, int>,
int> slaveAMSels;
2586 for (
const auto &[tileId, plan] : plans) {
2587 for (
const auto &[amsel, masters] : plan.amselMasters)
2588 masterAMSels[{tileId, amsel}].append(masters.begin(), masters.end());
2589 for (
const auto &[flow, amsel] : plan.slaveAmsels)
2590 slaveAMSels[{{tileId, flow.first}, flow.second}] = amsel;
2595 std::map<PhysPort, SmallVector<int, 4>> mastersets;
2596 for (
const auto &[tileAmsel, ports] : masterAMSels)
2597 for (
Port port : ports)
2598 mastersets[{tileAmsel.first, port}].push_back(tileAmsel.second);
2601 llvm::dbgs() <<
"CHECK mastersets\n";
2602 for (
const auto &[master, values] : mastersets) {
2603 llvm::dbgs() <<
"master " << master.first <<
" "
2604 << stringifyWireBundle(master.second.bundle) <<
" : "
2605 << master.second.channel <<
'\n';
2606 for (
int value : values)
2607 llvm::dbgs() <<
"amsel: " << value <<
'\n';
2613 SmallVector<SmallVector<std::pair<PhysPort, int>, 4>, 4> slaveGroups;
2614 SmallVector<std::pair<PhysPort, int>, 4> workList(slavePorts);
2615 while (!workList.empty()) {
2616 std::pair<PhysPort, int> slave = workList.pop_back_val();
2617 const SmallVector<PhysPort, 4> &dests = packetFlows.at(slave);
2618 auto *group = llvm::find_if(slaveGroups, [&](
const auto &candidate) {
2619 const SmallVector<PhysPort, 4> &groupDests =
2620 packetFlows.at(candidate.front());
2621 return candidate.front().first.second == slave.first.second &&
2622 prioritizedFlows.contains(candidate.front()) ==
2623 prioritizedFlows.contains(slave) &&
2624 groupDests.size() == dests.size() &&
2625 llvm::all_of(dests, [&](
const PhysPort &dest) {
2626 return llvm::is_contained(groupDests, dest);
2629 if (group != slaveGroups.end())
2630 group->push_back(slave);
2632 slaveGroups.push_back({slave});
2637 SmallVector<SmallVector<std::pair<int, int>, 4>, 4> statedRules(
2638 slaveGroups.size());
2639 SmallVector<SmallVector<int, 4>, 4> derivedIds(slaveGroups.size());
2640 for (
size_t gi = 0; gi < slaveGroups.size(); ++gi) {
2641 for (
auto member : slaveGroups[gi]) {
2642 auto cubes = statedCubes(member, idMask);
2643 if (cubes.empty()) {
2644 derivedIds[gi].push_back(member.second);
2647 for (
auto cube : cubes)
2648 if (!llvm::is_contained(statedRules[gi], cube))
2649 statedRules[gi].push_back(cube);
2654 [[maybe_unused]]
auto claimsOf = [&](
size_t gi) {
2655 SmallVector<std::pair<int, int>, 8> claims(statedRules[gi].begin(),
2656 statedRules[gi].end());
2657 for (
int id : derivedIds[gi])
2658 claims.push_back({idMask,
id});
2666 std::map<TileID, Operation *> tiles;
2667 for (
auto tileOp : device.getOps<TileOp>())
2668 tiles[tileOp.getTileID()] = tileOp;
2669 for (
const PhysPort &master : llvm::make_first_range(mastersets))
2670 tiles.try_emplace(master.first, analyzer.
getTile(builder, master.first));
2672 for (Operation *tileOp : llvm::make_second_range(tiles)) {
2673 TileOp tile = cast<TileOp>(tileOp);
2674 TileID tileId = tile.getTileID();
2675 Location tileLoc = tile.getLoc();
2678 builder.setInsertionPointAfter(tileOp);
2680 analyzer.
getSwitchbox(builder, tile.colIndex(), tile.rowIndex());
2681 SwitchboxOp::ensureTerminator(swbox.getConnections(), builder, tileLoc);
2682 Block &b = swbox.getConnections().front();
2683 builder.setInsertionPoint(b.getTerminator());
2685 if (
auto hops = circuitHops.find(tileId); hops != circuitHops.end())
2686 for (
const Connect &hop : hops->second) {
2687 SmallVector<std::pair<PhysPort, int>, 4> passing;
2688 for (
const auto &flow : llvm::make_first_range(slaveFlowLocs))
2689 if (flow.first ==
PhysPort{tileId, hop.src})
2690 passing.push_back(flow);
2691 ConnectOp::create(builder, locOf(passing, tileLoc), hop.src.bundle,
2692 hop.src.channel, hop.dst.bundle, hop.dst.channel);
2696 auto tileMastersets =
2697 llvm::make_filter_range(mastersets, [&](
const auto &entry) {
2698 return entry.first.first == tileId;
2700 llvm::SmallBitVector amselNeeded(numMselsPerArbiter * numArbiters);
2701 for (
const auto &[master, amsels] : tileMastersets)
2702 for (
int amsel : amsels)
2703 amselNeeded.set(amsel);
2704 std::map<int, AMSelOp> amselOps;
2705 for (
int msel = 0; msel < numMselsPerArbiter; msel++)
2706 for (
int arbiter = 0; arbiter < numArbiters; arbiter++)
2707 if (
int amsel = arbiter + msel * numArbiters; amselNeeded.test(amsel))
2708 amselOps[amsel] = AMSelOp::create(builder, tileLoc, arbiter, msel);
2709 for (
const auto &[master, msels] : tileMastersets) {
2710 SmallVector<Value, 4> amsels;
2711 for (
int msel : msels)
2712 amsels.push_back(amselOps.at(msel));
2713 SmallVector<std::pair<PhysPort, int>, 4> feeding;
2714 for (
const auto &[flow, dests] : packetFlows)
2715 if (llvm::is_contained(dests, master))
2716 feeding.push_back(flow);
2717 auto msOp = MasterSetOp::create(
2718 builder, locOf(feeding, tileLoc), builder.getIndexType(),
2719 master.second.bundle, master.second.channel, amsels,
2720 keepPktHeaderAttr.lookup(master));
2721 if (priorityMasterPorts.contains(master))
2722 priority.setAttr(msOp, unit);
2726 DenseMap<Port, PacketRulesOp> slaveRules;
2727 DenseMap<Port, SmallVector<PacketRuleOp>> existingRules;
2729 SmallVector<size_t, 4> groups;
2730 SmallVector<PortRule> rules;
2733 std::map<Port, PortPlan> portPlans;
2734 for (
auto rulesOp : b.getOps<PacketRulesOp>()) {
2735 slaveRules[rulesOp.sourcePort()] = rulesOp;
2736 llvm::append_range(existingRules[rulesOp.sourcePort()],
2737 rulesOp.getRules().getOps<PacketRuleOp>());
2739 for (
size_t gi = 0; gi < slaveGroups.size(); ++gi) {
2740 const auto &group = slaveGroups[gi];
2741 builder.setInsertionPoint(b.getTerminator());
2743 auto port = group.front().first;
2744 if (tileId != port.first)
2747 Port slave = port.second;
2749 SmallVector<int, 4> matchIds =
2750 llvm::to_vector<4>(llvm::make_second_range(group));
2751 for (
int id : matchIds)
2752 if (
id >
static_cast<int>(maxPacketId)) {
2753 SmallVector<std::pair<PhysPort, int>> offending;
2754 for (
const auto &flow : group)
2755 if (flow.second ==
id)
2756 offending.push_back(flow);
2757 return mlir::emitError(locOf(offending, tileLoc))
2758 <<
"packet id " <<
id <<
" exceeds the maximum of "
2763 for (PacketRuleOp rule : existingRules.lookup(slave))
2764 for (
int id : matchIds)
2765 if ((
id & rule.maskInt()) == rule.valueInt()) {
2766 rule->emitOpError(
"can lead to false packet id match for id ")
2767 <<
id <<
", which is not supposed to pass through this port.";
2768 rule->emitRemark(
"Please consider changing all uses of packet id ")
2769 <<
id <<
" to avoid deadlock.";
2775 assert(llvm::all_of(
2776 llvm::seq<size_t>(0, slaveGroups.size()),
2778 return oi == gi || slaveGroups[oi].front().first != port ||
2779 llvm::none_of(claimsOf(gi), [&](auto own) {
2780 return llvm::any_of(claimsOf(oi), [&](auto other) {
2781 return cubesIntersect(own, other);
2785 "groups on one slave port claim the same id");
2789 auto [planIt, fresh] = portPlans.try_emplace(slave);
2790 PortPlan &plan = planIt->second;
2792 SmallVector<GroupClaims> claims;
2793 for (
size_t oi = 0; oi < slaveGroups.size(); ++oi) {
2794 if (slaveGroups[oi].front().first != port)
2796 plan.groups.push_back(oi);
2798 {statedRules[oi], derivedIds[oi],
2799 prioritizedFlows.contains(slaveGroups[oi].front())});
2801 SmallVector<std::pair<int, int>> existing;
2802 for (PacketRuleOp rule : existingRules.lookup(slave))
2803 existing.push_back({rule.maskInt(), rule.valueInt()});
2804 plan.rules = slavePortRules(claims, existing, idBits,
2807 llvm::dbgs() <<
"packet rules " <<
describePort(slave) <<
":";
2808 for (
const PortRule &r : plan.rules)
2809 llvm::dbgs() <<
" rule(" << r.mask <<
", " << r.value
2810 <<
") -> group " << plan.groups[r.group];
2811 llvm::dbgs() <<
'\n';
2817 llvm::seq(0, idMask + 1),
2819 bool own = llvm::is_contained(derivedIds[gi],
id) ||
2820 llvm::any_of(statedRules[gi], [&](
auto c) {
2821 return (
id & c.first) == (c.second & c.first);
2824 llvm::find_if(plan.rules, [&](
const PortRule &r) {
2825 return (id & r.mask) == r.value;
2828 (first != plan.rules.end() &&
2830 slaveGroups[plan.groups[first->group]].front()) ==
2831 slaveAMSels.at(slaveGroups[gi].front()));
2833 "packet rules send a claimed id elsewhere");
2835 size_t last = plan.emitted;
2836 for (
size_t r = plan.emitted; r < plan.rules.size(); ++r)
2837 if (plan.groups[plan.rules[r].group] == gi)
2840 PacketRulesOp packetrules = slaveRules.lookup(slave);
2842 packetrules = PacketRulesOp::create(builder, locOf(group, tileLoc),
2843 slave.bundle, slave.channel);
2844 PacketRulesOp::ensureTerminator(packetrules.getRules(), builder,
2846 slaveRules[slave] = packetrules;
2849 packetrules->moveBefore(b.getTerminator());
2850 if (Location more = locOf(group, tileLoc); more != tileLoc)
2851 packetrules->setLoc(FusedLoc::get(builder.getContext(),
2852 {packetrules->getLoc(), more}));
2855 Block &rules = packetrules.getRules().front();
2857 assert(llvm::range_size(rules.getOps<PacketRuleOp>()) +
2858 (last - plan.emitted) <=
2860 "checkRules lets a slave port take more rules than it holds");
2862 builder.setInsertionPoint(rules.getTerminator());
2863 for (; plan.emitted < last; ++plan.emitted) {
2864 const PortRule &r = plan.rules[plan.emitted];
2865 const auto &ruleGroup = slaveGroups[plan.groups[r.group]];
2866 auto rule = PacketRuleOp::create(
2867 builder, locOf(ruleGroup, tileLoc), r.mask, r.value,
2868 amselOps.at(slaveAMSels.at(ruleGroup.front())));
2869 if (llvm::all_of(ruleGroup, [&](
const auto &member) {
2870 return markedFlows.contains(member);
2872 priority.setAttr(rule, unit);
2876 for (
auto rulesOp : b.getOps<PacketRulesOp>()) {
2877 auto rules = rulesOp.getRules().front().getOps<PacketRuleOp>();
2878 if (rules.empty() || !llvm::all_of(rules, [&](PacketRuleOp rule) {
2879 return priority.isAttrPresent(rule);
2882 priority.setAttr(rulesOp, unit);
2883 for (
auto rule : rules)
2884 priority.removeAttr(rule);
2890LogicalResult AIEPathfinderPass::runOnPacketFlow(
2891 DeviceOp device, OpBuilder &builder, DynamicTileAnalysis &analyzer,
2892 const StreamConflicts &conflicts,
const PacketPlan &plan,
bool warn) {
2893 if (warn && plan.sharedReceiverCycle)
2894 emitWarning(device.getLoc(), sharedReceiverCycleReason)
2895 << conflicts.
explain(*plan.sharedReceiverCycle);
2896 if (failed(plan.emit(device, builder, analyzer)))
2898 lowerShimDMAPorts(device, builder, analyzer);
2899 for (PacketFlowOp flow :
2900 llvm::make_early_inc_range(device.getOps<PacketFlowOp>()))
2906static DeviceOp cloneInScratch(DeviceOp d, OwningOpRef<ModuleOp> &scratch) {
2907 scratch = ModuleOp::create(d.getLoc());
2908 if (Operation *parent = d->getParentOp())
2909 (*scratch)->setAttrs(parent->getAttrDictionary());
2910 DeviceOp copy = d.clone();
2911 scratch->push_back(copy);
2919static void unmuxShimDMAPacketPorts(DeviceOp device) {
2920 for (
auto shimMux : device.getOps<ShimMuxOp>()) {
2921 auto hasConnect = [&](
Port src,
Port dst) {
2922 return llvm::any_of(shimMux.getConnections().getOps<ConnectOp>(),
2924 return c.sourcePort() == src && c.destPort() == dst;
2927 for (
auto switchbox : device.getOps<SwitchboxOp>()) {
2928 if (switchbox.getTileOp() != shimMux.getTileOp())
2930 for (
auto rules : switchbox.getConnections().getOps<PacketRulesOp>())
2931 for (
int ch : {0, 1}) {
2932 Port dma{WireBundle::DMA, ch};
2934 if (rules.sourcePort() ==
Port{WireBundle::South, north.channel} &&
2935 hasConnect(dma, north)) {
2936 rules.setSourceBundle(WireBundle::DMA);
2937 rules.setSourceChannel(ch);
2941 for (
auto masterSet : switchbox.getConnections().getOps<MasterSetOp>())
2942 for (
int ch : {0, 1}) {
2943 Port dma{WireBundle::DMA, ch};
2945 if (masterSet.destPort() ==
Port{WireBundle::South, north.channel} &&
2946 hasConnect(north, dma)) {
2947 masterSet.setDestBundle(WireBundle::DMA);
2948 masterSet.setDestChannel(ch);
2956llvm::Expected<PacketPlan> AIEPathfinderPass::route(
2957 DeviceOp d, DynamicTileAnalysis &analyzer,
const StreamConflicts &conflicts,
2958 const PinnedRoutes &pinned,
bool circuitSwitchHops,
bool prioritize) {
2962 std::map<PathEndPoint, SmallVector<size_t, 4>> streamsFrom;
2963 PacketConstraints constraints;
2967 if (clRoutePacket && !d.getOps<PacketFlowOp>().empty()) {
2968 const AIETargetModel &targetModel = d.getTargetModel();
2969 if (llvm::Error err = unroutableArbiters(
2972 return !circuitSwitchHops ||
2976 return std::move(err);
2979 streamsFrom[{s.src.tile, s.src.port}].push_back(i);
2982 ArrayRef<RoutedStream> streams = conflicts.
getStreams();
2983 SmallVector<size_t, 16> crossing;
2984 std::set<std::pair<TileID, Port>> srcs, dsts;
2986 if (s.packetID && low(s.src.tile) == up && low(s.dst.tile) != up) {
2987 crossing.push_back(i);
2988 srcs.insert({s.src.tile, s.src.port});
2989 dsts.insert({s.dst.tile, s.dst.port});
2993 size_t most = std::min(srcs.size(), dsts.size());
2994 SmallVector<size_t, 8> best =
2996 ? largestApartSet(conflicts, crossing, limit)
2997 : SmallVector<size_t, 8>(
2999 crossing.begin() + std::min<size_t>(1, crossing.size()));
3000 for (
size_t s : best)
3002 if (best.size() > 1)
3003 apart.
why = conflicts.
explain(best[0], best[1]);
3006 constraints.
conflict = [&](
const PathEndPoint &a,
const std::set<int> &aIds,
3007 const PathEndPoint &b,
3008 const std::set<int> &bIds) {
3009 auto as = streamsFrom.find(a), bs = streamsFrom.find(b);
3010 if (as == streamsFrom.end() || bs == streamsFrom.end())
3012 ArrayRef<RoutedStream> streams = conflicts.
getStreams();
3013 for (
size_t s : as->second)
3014 for (
size_t t : bs->second)
3015 if (aIds.count(*streams[s].packetID) &&
3016 bIds.count(*streams[t].packetID) && conflicts.
conflict(s, t))
3020 constraints.
check = [&](
const Routing &routing) -> llvm::Error {
3021 PacketFlowRouting check(d, routing, conflicts, pinned, clRouteCircuit,
3022 circuitSwitchHops, prioritize);
3023 llvm::Expected<PacketPlan> plan = check.plan();
3025 return plan.takeError();
3026 RoutingFaults all = check.faults(), faults;
3030 if (!plan->sharedReceiverCycle ||
3033 return llvm::Error::success();
3034 return llvm::make_error<DeadlockProneRouting>(
3035 conflicts.
explain(*plan->sharedReceiverCycle), std::move(faults));
3042 return std::move(routed);
3044 return PacketPlan();
3045 PacketFlowRouting found(d, analyzer.
routing, conflicts, pinned,
3046 clRouteCircuit, circuitSwitchHops, prioritize);
3047 llvm::Expected<PacketPlan> plan = found.plan();
3048 if (found.incomplete) {
3049 llvm::consumeError(plan.takeError());
3050 return llvm::make_error<RoutingFailure>(std::move(found.incomplete->second),
3052 found.incomplete->first);
3056 if (!plan || clAllowDeadlockProne)
3058 const std::optional<HoldCycle> &cycle = plan->sharedReceiverCycle;
3061 return llvm::make_error<DeadlockProneRouting>(
3062 (llvm::Twine(sharedReceiverCycleReason) + conflicts.
explain(*cycle) +
3063 allowDeadlockProneHint)
3067static LogicalResult checkFixedFlowEndpoints(DeviceOp device) {
3068 DenseMap<PhysPort, Operation *> inputs, outputs;
3069 for (SwitchboxOp box : device.getOps<SwitchboxOp>()) {
3070 TileID tile = box.getTileOp().getTileID();
3071 for (ConnectOp connect : box.getOps<ConnectOp>()) {
3072 inputs[{tile, connect.sourcePort()}] = connect;
3073 outputs[{tile, connect.destPort()}] = connect;
3075 for (MasterSetOp master : box.getOps<MasterSetOp>())
3076 outputs[{tile, master.destPort()}] = master;
3077 for (PacketRulesOp rules : box.getOps<PacketRulesOp>())
3078 inputs[{tile, rules.sourcePort()}] = rules;
3080 AIEDialect::IsCtrlPktOverlayAttrHelper overlay(device.getContext());
3081 auto check = [&](Operation *flow, Value value,
Port port,
3082 bool source) -> LogicalResult {
3083 auto tile = cast<TileOp>(value.getDefiningOp());
3084 auto &reservations = source ? inputs : outputs;
3085 Operation *reserved = reservations.lookup({tile.getTileID(), port});
3086 if (!reserved && tile.isShimNOCorPLTile() &&
3087 llvm::is_contained({WireBundle::DMA, WireBundle::NOC, WireBundle::PLIO},
3089 Port south{WireBundle::South,
3091 reserved = reservations.lookup({tile.getTileID(), south});
3093 auto packet = dyn_cast<PacketFlowOp>(flow);
3094 if (!reserved || (packet && isa<PacketRulesOp>(reserved)))
3096 bool fromOverlay = overlay.isAttrPresent(reserved);
3097 if (
auto rules = dyn_cast<PacketRulesOp>(reserved))
3098 fromOverlay |= llvm::any_of(
3099 rules.getRules().getOps<PacketRuleOp>(),
3100 [&](PacketRuleOp rule) { return overlay.isAttrPresent(rule); });
3101 auto diag = emitError(flow->getLoc());
3102 diag <<
"Unable to find a legal routing: ";
3104 diag <<
"packet flow " << packet.IDInt();
3106 diag <<
"circuit flow";
3107 diag << (source ?
" starts at " :
" ends at ")
3109 << (source ?
"input" :
"output") <<
" port is reserved by ";
3111 diag <<
"the control packet overlay";
3113 diag <<
"a fixed " << reserved->getName();
3114 diag.attachNote(reserved->getLoc())
3115 << (source ?
"input" :
"output") <<
" port reserved here by "
3116 << reserved->getName();
3119 for (PacketFlowOp flow : device.getOps<PacketFlowOp>()) {
3120 for (PacketSourceOp source : flow.getPorts().getOps<PacketSourceOp>())
3121 if (failed(check(flow, source.getTile(), source.port(),
true)))
3123 for (PacketDestOp dest : flow.getPorts().getOps<PacketDestOp>())
3124 if (failed(check(flow, dest.getTile(), dest.port(),
false)))
3127 for (FlowOp flow : device.getOps<FlowOp>())
3128 if (failed(check(flow, flow.getSource(),
3129 {flow.getSourceBundle(), flow.getSourceChannel()},
3131 failed(check(flow, flow.getDest(),
3132 {flow.getDestBundle(), flow.getDestChannel()},
false)))
3137void AIEPathfinderPass::runOnOperation() {
3140 LLVM_DEBUG(llvm::dbgs() <<
"---Begin AIEPathfinderPass---\n");
3142 DeviceOp d = getOperation();
3144 return signalPassFailure();
3145 OpBuilder builder = OpBuilder::atBlockTerminator(d.getBody());
3147 unmuxShimDMAPacketPorts(d);
3148 if (failed(checkFixedFlowEndpoints(d)))
3149 return signalPassFailure();
3151 StreamConflicts conflicts(d);
3152 if (
auto pairs = conflicts.
unavoidable(); !pairs.empty()) {
3153 InFlightDiagnostic diag =
3154 (clAllowDeadlockProne ? emitWarning(d.getLoc()) : emitError(d.getLoc()))
3155 <<
"Flows can deadlock however they are routed: "
3156 << conflicts.explain(pairs[0].first, pairs[0].second);
3157 if (pairs.size() > 1)
3158 diag <<
" So can " << pairs.size() - 1 <<
" other pair"
3159 << (pairs.size() > 2 ?
"s" :
"") <<
" of flows.";
3160 if (!clAllowDeadlockProne) {
3161 diag << allowDeadlockProneHint;
3162 return signalPassFailure();
3165 DynamicTileAnalysis analyzer;
3171 auto sourcesOf = [](PacketFlowOp flow) {
3172 return llvm::map_range(
3173 flow.getPorts().getOps<PacketSourceOp>(), [](PacketSourceOp src) {
3174 return PathEndPoint{
3175 cast<TileOp>(src.getTile().getDefiningOp()).getTileID(),
3179 std::set<PathEndPoint> prioritized;
3180 std::set<std::pair<PathEndPoint, int>> prioritizedIds;
3181 for (PacketFlowOp flow : d.getOps<PacketFlowOp>())
3182 if (flow.getPriorityRoute().value_or(false))
3183 for (PathEndPoint src : sourcesOf(flow)) {
3184 prioritized.insert(src);
3185 prioritizedIds.insert({src, flow.IDInt()});
3187 auto isPrioritized = [&](PacketFlowOp flow) {
3188 return llvm::any_of(sourcesOf(flow), [&](
const PathEndPoint &src) {
3189 return prioritizedIds.count({src, flow.IDInt()}) > 0;
3192 auto routesAlone = isPrioritized;
3193 bool pinned =
false;
3194 PinnedRoutes priority;
3195 bool othersToRoute = !d.getOps<FlowOp>().empty() ||
3196 !llvm::all_of(d.getOps<PacketFlowOp>(), routesAlone);
3201 if (clRoutePacket && !prioritized.empty() && othersToRoute) {
3202 OwningOpRef<ModuleOp> scratch;
3203 DeviceOp alone = cloneInScratch(d, scratch);
3204 SmallVector<Operation *> others;
3205 for (Operation &op : alone.getBody()->without_terminator()) {
3206 auto flow = dyn_cast<PacketFlowOp>(op);
3207 if (flow ? !routesAlone(flow) : isa<FlowOp>(op))
3208 others.push_back(&op);
3210 for (Operation *op : others)
3211 op->dropAllReferences();
3212 for (Operation *op : others)
3214 std::map<PathEndPoint, std::set<int>> aloneIds;
3215 for (PacketFlowOp flow : alone.getOps<PacketFlowOp>())
3216 for (
auto src : flow.getPorts().getOps<PacketSourceOp>()) {
3217 auto tile = cast<TileOp>(src.getTile().getDefiningOp());
3218 aloneIds[{{tile.colIndex(), tile.rowIndex()}, src.port()}].insert(
3221 DynamicTileAnalysis aloneAnalyzer;
3223 StreamConflicts aloneConflicts(alone);
3224 llvm::Expected<PacketPlan> alonePlan =
3225 route(alone, aloneAnalyzer, aloneConflicts, {},
3228 llvm::consumeError(alonePlan.takeError());
3232 OpBuilder aloneBuilder = OpBuilder::atBlockTerminator(alone.getBody());
3233 if (failed(runOnPacketFlow(alone, aloneBuilder, aloneAnalyzer,
3234 aloneConflicts, *alonePlan,
false)))
3235 return signalPassFailure();
3237 std::move(aloneIds), priorityRules(alone)};
3245 auto routeRelaxing = [&](DeviceOp dev, DynamicTileAnalysis &an,
3246 const StreamConflicts &c,
const PinnedRoutes &pin,
3248 true) -> llvm::Expected<PacketPlan> {
3251 std::vector<PathfinderAttempt> attempts;
3252 an.pathfinder.attempts = &attempts;
3253 llvm::scope_exit detach([&] { an.pathfinder.attempts =
nullptr; });
3254 llvm::Expected<PacketPlan> plan =
3255 route(dev, an, c, pin, clCircuitSwitchHops, prioritize);
3258 llvm::Error first = plan.takeError();
3259 while (an.pathfinder.relax()) {
3260 plan = route(dev, an, c, pin, clCircuitSwitchHops, prioritize);
3262 llvm::consumeError(std::move(first));
3265 llvm::Error err = plan.takeError();
3266 if (err.isA<DeadlockProneRouting>() && !first.isA<DeadlockProneRouting>())
3267 std::swap(first, err);
3268 llvm::consumeError(std::move(err));
3270 return std::move(first);
3272 llvm::Expected<PacketPlan> plan =
3273 routeRelaxing(d, analyzer, conflicts, priority);
3274 if (!plan && !prioritized.empty()) {
3275 llvm::Error err = plan.takeError();
3277 DynamicTileAnalysis freeAnalyzer;
3278 plan = routeRelaxing(d, freeAnalyzer, conflicts, priority,
3281 llvm::consumeError(std::move(err));
3282 analyzer = std::move(freeAnalyzer);
3284 llvm::Error freeErr = plan.takeError();
3285 if (freeErr.isA<DeadlockProneRouting>() ||
3286 !err.isA<DeadlockProneRouting>())
3287 std::swap(err, freeErr);
3288 llvm::consumeError(std::move(freeErr));
3289 plan = std::move(err);
3294 llvm::handleAllErrors(plan.takeError(), [&](RoutingFailure &f) {
3297 if (pinned && !f.reason.empty() &&
3298 !f.isA(PinnedRoutingFailure::classID())) {
3299 OwningOpRef<ModuleOp> scratch;
3300 DeviceOp free = cloneInScratch(d, scratch);
3301 DynamicTileAnalysis freeAnalyzer;
3302 StreamConflicts freeConflicts(free);
3303 llvm::Expected<PacketPlan> freePlan = routeRelaxing(
3304 free, freeAnalyzer, freeConflicts, {}, false);
3306 llvm::consumeError(freePlan.takeError());
3308 f.reason = describePrioritized(llvm::to_vector(llvm::map_range(
3310 [](const PathEndPoint &src) {
3311 return describeTilePort(src.coords, src.port);
3313 ", and the other flows route only if it moves. Around "
3318 emitError(f.
loc.value_or(d.getLoc())) << f.message();
3320 signalPassFailure();
3323 for (
auto flowOp : d.getOps<FlowOp>()) {
3324 if (!flowOp.getVias().empty()) {
3325 flowOp.emitOpError(
"cannot be routed while it carries via waypoints; run "
3326 "--aie-split-flow-vias first to lower the vias into "
3327 "switchbox connections");
3328 signalPassFailure();
3332 for (
auto flowOp : d.getOps<PacketFlowOp>()) {
3333 if (!flowOp.getVias().empty()) {
3334 flowOp.emitOpError(
"cannot be routed while it carries via waypoints; run "
3335 "--aie-split-flow-vias first to lower the vias into "
3336 "switchbox connections");
3337 signalPassFailure();
3342 if (clRouteCircuit && failed(runOnFlow(d, analyzer))) {
3343 signalPassFailure();
3346 if (clRoutePacket && failed(runOnPacketFlow(d, builder, analyzer, conflicts,
3348 signalPassFailure();
3354 builder.setInsertionPoint(d.getBody()->getTerminator());
3355 llvm::DenseSet<std::tuple<Value, int, Value, int>> existingWires;
3358 auto recordWire = [&](Value source,
int sourceBundle, Value dest,
3361 !existingWires.contains({source, sourceBundle, dest, destBundle}) &&
3362 !existingWires.contains({dest, destBundle, source, sourceBundle});
3363 existingWires.insert({source, sourceBundle, dest, destBundle});
3364 existingWires.insert({dest, destBundle, source, sourceBundle});
3367 for (
auto wire : d.getOps<WireOp>()) {
3368 recordWire(wire.getSource(),
static_cast<int>(wire.getSourceBundle()),
3369 wire.getDest(),
static_cast<int>(wire.getDestBundle()));
3371 auto wire = [&](Location loc, Value source, WireBundle sourceBundle,
3372 Value dest, WireBundle destBundle) {
3373 if (recordWire(source,
static_cast<int>(sourceBundle), dest,
3374 static_cast<int>(destBundle))) {
3375 WireOp::create(builder, loc, source, sourceBundle, dest, destBundle);
3378 for (
int col = 0; col <= analyzer.
getMaxCol(); col++) {
3379 for (
int row = 0; row <= analyzer.
getMaxRow(); row++) {
3380 TileOp tile = analyzer.
lookupTile({col, row});
3384 Location loc = tile.getLoc();
3388 wire(loc, westsw, WireBundle::East, sw, WireBundle::West);
3391 wire(loc, tile, WireBundle::Core, sw, WireBundle::Core);
3393 wire(loc, tile, WireBundle::DMA, sw, WireBundle::DMA);
3397 wire(loc, southsw, WireBundle::North, sw, WireBundle::South);
3398 }
else if (tile.isShimNOCTile()) {
3402 sw, WireBundle::South);
3405 wire(loc, tile, WireBundle::DMA, shimsw, WireBundle::DMA);
3413 return std::make_unique<AIEPathfinderPass>();
3416std::unique_ptr<OperationPass<DeviceOp>>
3418 return std::make_unique<AIEPathfinderPass>(options);
3421std::unique_ptr<OperationPass<DeviceOp>>
3423 ArrayRef<std::pair<TileID, Port>> avoidedPorts) {
3424 auto pass = std::make_unique<AIEPathfinderPass>(options);
3425 pass->avoidedPorts.assign(avoidedPorts.begin(), avoidedPorts.end());
constexpr int maxSearchSteps
std::pair< TileID, Port > PhysPort
constexpr int maxHoldCycleReplans
std::map< PhysPort, SmallVector< std::tuple< int, int, int >, 2 > > PriorityRules
(mask, value, amsel) by slave port, in slot order.
std::tuple< int, int, int, int, int, int, int, int, int, int > FlowKey
virtual uint32_t getNumMselsPerArbiter() const =0
Return the number of master select values per stream-switch arbiter.
int getPacketIdMask() const
virtual uint32_t getNumArbiters() const =0
Return the number of arbiters per stream switch.
bool isShimNOCorPLTile(int col, int row) const
Return true if the given tile is either a ShimNOC or ShimPL tile.
virtual int rows() const =0
Return the number of rows in the device.
bool isShimNOCTile(int col, int row) const
Return true if the given tile is a ShimNOC tile.
virtual uint32_t getMaxPacketId() const =0
Return the largest packet id the stream switch can route.
virtual int columns() const =0
Return the number of columns in the device.
int getPacketIdBits() const
Bits a packet id spans, and the mask a switch's id match uses.
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 getNumSlaveSlots() const =0
Return the number of packet-rule slots per stream-switch slave port.
ShimMuxOp getShimMux(mlir::OpBuilder &builder, int col)
SwitchboxOp getSwitchbox(mlir::OpBuilder &builder, int col, int row)
SwitchboxOp lookupSwitchbox(TileID tile) const
TileOp lookupTile(TileID tile) const
TileOp getTile(mlir::OpBuilder &builder, int col, int row)
llvm::Error runAnalysis(DeviceOp &device)
std::set< PathEndPoint > processedFlows
ShimMuxOp lookupShimMux(int col) const
std::vector< std::pair< TileID, Port > > avoidedPorts
void setPacketConstraints(PacketConstraints c)
std::optional< mlir::Location > loc
The streams a device asks for or already routes, and which pairs of them must not share an arbiter or...
llvm::ArrayRef< RoutedStream > getRequestedStreams() const
The streams the flow ops ask for, which come first in getStreams().
llvm::SmallVector< std::pair< size_t, size_t > > unavoidable() const
The requested streams where the first can hold up the second however they are routed,...
bool mustSeparate(size_t s, size_t t) const
Whether a routing that puts packet streams s and t on one arbiter anywhere has a hold cycle: they con...
llvm::ArrayRef< RoutedStream > getStreams() const
bool conflict(size_t s, size_t t) const
Whether s and t can deadlock if they share an arbiter or a link.
std::optional< HoldCycle > holdCycle(llvm::ArrayRef< llvm::SmallVector< StreamHop, 8 > > routes, bool forcedWaits=false, bool definite=false) const
A cycle of waits the packet streams can deadlock in when routed along routes, indexed like getStreams...
std::string explain(size_t s, size_t t) const
Why s and t conflict.
int shimMuxChannelTo(Port dst)
struct Connect { Port src; Port dst; bool operator==(const Connect &rhs) const { return std::tie(src, dst)==std::tie(rhs.src, rhs.dst); } bool operator!=(const Connect &rhs) const { return !(*this==rhs);} bool operator<(const Connect &rhs) const { return std::tie(src, dst)< std::tie(rhs.src, rhs.dst); } } Connect
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::string describeStream(const RoutedStream &stream)
Names the stream by its endpoints and packet id, e.g.
const AIETargetModel & getTargetModel(mlir::Operation *op)
mlir::LogicalResult verifyDMAChannelsResolved(DeviceOp device)
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
std::unique_ptr< mlir::OperationPass< DeviceOp > > createAIEPathfinderPass()
std::string describePort(Port port)
Names a port the way diagnostics do, e.g. "DMA:1".
std::map< PathEndPoint, std::vector< TreeHop > > PacketTrees
std::map< PathEndPoint, std::set< int > > ids
bool forced
The wait holds however the arbiters are planned, as sharer and holding go into a receiver they share ...
std::map< PathEndPoint, std::set< int > > pinnedIds
PacketsApartAcross apartAcross
std::vector< std::string > flows
std::optional< int > packetID
The packet id carried, if any.
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