MLIR-AIE 1.4.6.dev
AIEPathFinder.cpp
Go to the documentation of this file.
1//===- AIEPathFinder.cpp ----------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2021-2022 Xilinx, Inc.
4// Copyright (C) 2022-2026 Advanced Micro Devices, Inc.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
11#include "d_ary_heap.h"
12
13#include "llvm/ADT/MapVector.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/SetVector.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/Support/CommandLine.h"
18#include "llvm/Support/Debug.h"
19#include "llvm/Support/ErrorHandling.h"
20#include "llvm/Support/FormatVariadic.h"
21
22#include <iterator>
23#include <limits>
24
25using namespace mlir;
26using namespace xilinx;
27using namespace xilinx::AIE;
28
29#define DEBUG_TYPE "aie-pathfinder"
30
31STATISTIC(numReplaysSkipped, "Attempts skipped as replays of an earlier one");
32STATISTIC(numReplaysVerified, "Attempts routed and verified to replay one");
33
34static llvm::cl::opt<bool> clVerifyReplays(
35 "aie-pathfinder-verify-replays", llvm::cl::Hidden,
36 llvm::cl::desc("Route the attempts of a relax ladder that replay an "
37 "earlier one anyway, and abort unless each iteration's "
38 "routing and the result are the earlier attempt's"),
39 llvm::cl::init(false));
40
41static llvm::hash_code hashRouting(const Routing &routing) {
42 llvm::hash_code h = llvm::hash_value(routing.settings.size());
43 auto settings = [&](const SwitchSettings &ss) {
44 for (const auto &[tile, s] : ss) {
45 h = llvm::hash_combine(h, tile.col, tile.row, s.srcs.size(),
46 s.dsts.size());
47 for (const Port &p : s.srcs)
48 h = llvm::hash_combine(h, p.bundle, p.channel);
49 for (const Port &p : s.dsts)
50 h = llvm::hash_combine(h, p.bundle, p.channel);
51 }
52 };
53 auto endpoint = [&](const PathEndPoint &e) {
54 h = llvm::hash_combine(h, e.coords.col, e.coords.row, e.port.bundle,
55 e.port.channel);
56 };
57 for (const auto &[src, ss] : routing.settings) {
58 endpoint(src);
59 settings(ss);
60 }
61 for (const auto &[key, ss] : routing.idSettings) {
62 endpoint(key.first);
63 h = llvm::hash_combine(h, key.second);
64 settings(ss);
65 }
66 for (const auto &[src, hops] : routing.packetTrees) {
67 endpoint(src);
68 for (const TreeHop &hop : hops) {
69 endpoint(hop.from);
70 endpoint(hop.to);
71 h = llvm::hash_combine(h, hop.joined);
72 }
73 }
74 return h;
75}
76
77namespace {
78// A connection's demand, the cost Dijkstra weighs it by, is
79// (demandBase + overCapacityCoeff * iterations it was over capacity) *
80// (demandBase + usedCapacityCoeff * streams using it), plus its avoidance.
81constexpr double overCapacityCoeff = 0.1;
82constexpr double usedCapacityCoeff = 0.02;
83constexpr double demandBase = 1.0;
84// A full connection's demand grows by this factor, or a prioritized flow's
85// by priorityDemandCoeff, each time another stream takes it.
86constexpr double demandCoeff = 1.1;
87constexpr double priorityDemandCoeff =
88 static_cast<double>(std::numeric_limits<int>::max());
89constexpr int maxCircuitStreamCapacity = 1;
90constexpr int maxPacketStreamCapacity = 32;
91// Demand added to a connection into an avoided port. It exceeds what a long
92// detour costs, so a route takes the port only when every other is taken.
93constexpr double avoidedPortDemand = 100.0;
94// History added to a connection each time the routing check rejects it.
95constexpr int routingCheckPenalty = 5;
96// Iterations spent steering away from a usable routing the check rejects.
97constexpr int maxSteers = 16;
98// Routings in a row the check rejects only for onlyPriorityMasters before
99// routing gives up: the penalties move such a flow between the ports of the
100// switchbox it has to leave by.
101constexpr int maxPriorityFaults = 16;
102// Times the routing check may fault where two trees meet before they stop
103// meeting; each fault moves the meeting elsewhere.
104constexpr int maxMeetFaults = 4;
105// Cost added to a hop that shares an arbiter unit with a flow to avoid.
106constexpr double conflictSharePenalty = 4;
107// Channels per direction packet streams leave a capped tile by (see
108// Pathfinder::relax). A heuristic: fewer channels mean fewer master
109// sets per tile, but more flows on each.
110constexpr int packetFanoutCap = 2;
111// A multicast's next destination may branch off any hop its tree already
112// takes, starting at this cost per hop back to the source: enough of a
113// discount to share hops, while still preferring the shortest path to each
114// destination.
115constexpr double treeSeedFactor = 0.9;
116// A destination's branch is rerouted only when that saves more than this.
117constexpr double rerouteMinSaving = 1e-6;
118// Iterations without fewer overused channels before the circuit trees that
119// overuse one route first (see findPaths).
120constexpr int stallIterations = 50;
121// Iterations of a stall that route the losing circuit trees first, without
122// fewer overused channels, before the attempt gives up.
123constexpr int maxReorderedStall = 300;
124// Iterations without fewer overused channels before an attempt that has never
125// fit the fabric gives up. In the nightly's designs, none that routed took
126// over 275.
127constexpr int maxOverusedStall = 400;
128// Iterations, once a routing has fit the fabric, without the routing check
129// naming fewer faults than before or teaching a split, relation, untrunk or
130// no-join pair it never taught this attempt, before the attempt gives up.
131constexpr int maxRejectedStall = 600;
132// How much faster a stalled routing's overused channels that only circuit
133// trees take accrue history, so the trees spread out sooner.
134constexpr int stallHistory = 4;
135} // namespace
136
138 for (Cell &c : cells)
139 c.demand = (demandBase + overCapacityCoeff * c.overCapacity) *
140 (demandBase + usedCapacityCoeff * c.usedCapacity) +
141 c.avoidance;
142}
143
145 if (c.usedCapacity >= maxCircuitStreamCapacity)
146 c.demand *= c.isPriority ? priorityDemandCoeff : demandCoeff;
147}
148
149char RoutingFailure::ID = 0;
152
153void RoutingFailure::log(llvm::raw_ostream &os) const {
154 os << kNoLegalRouting;
155 if (!reason.empty())
156 os << ": " << reason;
157}
158
159llvm::Error DynamicTileAnalysis::runAnalysis(DeviceOp &device) {
160 LLVM_DEBUG(llvm::dbgs() << "\t---Begin DynamicTileAnalysis Constructor---\n");
161 // find the maxCol and maxRow
162 maxCol = device.getTargetModel().columns();
163 maxRow = device.getTargetModel().rows();
164
165 pathfinder.initialize(maxCol, maxRow, device.getTargetModel());
166 for (const auto &[coords, port] : avoidedPorts)
167 pathfinder.avoidPort(coords, port);
168
169 // For each flow (circuit + packet) in the device, add it to pathfinder. Each
170 // source can map to multiple different destinations (fanout). Control packet
171 // flows to be routed (as prioritized routings). Then followed by normal
172 // packet flows.
173 for (PacketFlowOp pktFlowOp : device.getOps<PacketFlowOp>()) {
174 Region &r = pktFlowOp.getPorts();
175 Block &b = r.front();
176 SmallVector<std::pair<TileID, Port>, 4> sources;
177 // Pass 1: collect all sources (order-independent; supports fan-in).
178 for (Operation &Op : b.getOperations()) {
179 if (auto pktSource = dyn_cast<PacketSourceOp>(Op)) {
180 auto srcTile = cast<TileOp>(pktSource.getTile().getDefiningOp());
181 sources.push_back(
182 {{srcTile.colIndex(), srcTile.rowIndex()}, pktSource.port()});
183 }
184 }
185
186 bool priorityFlow = pktFlowOp.getPriorityRoute().value_or(false);
187 // Pass 2: add a flow from every source to every destination so
188 // fan-in topologies are routed (not just the last source).
189 for (Operation &Op : b.getOperations()) {
190 if (auto pktDest = dyn_cast<PacketDestOp>(Op)) {
191 auto dstTile = cast<TileOp>(pktDest.getTile().getDefiningOp());
192 Port dstPort = pktDest.port();
193 TileID dstCoords = {dstTile.colIndex(), dstTile.rowIndex()};
194 for (auto &[srcCoords, srcPort] : sources) {
195 LLVM_DEBUG(llvm::dbgs()
196 << "\tAdding Packet Flow: (" << srcCoords.col << ", "
197 << srcCoords.row << ")"
198 << stringifyWireBundle(srcPort.bundle) << srcPort.channel
199 << " -> (" << dstCoords.col << ", " << dstCoords.row << ")"
200 << stringifyWireBundle(dstPort.bundle) << dstPort.channel
201 << "\n");
202 pathfinder.addFlow(srcCoords, srcPort, dstCoords, dstPort,
203 pktFlowOp.IDInt(), priorityFlow,
204 pktFlowOp.getLoc());
205 }
206 }
207 }
208 }
209
210 // Add circuit flows.
211 for (FlowOp flowOp : device.getOps<FlowOp>()) {
212 TileOp srcTile = cast<TileOp>(flowOp.getSource().getDefiningOp());
213 TileOp dstTile = cast<TileOp>(flowOp.getDest().getDefiningOp());
214 TileID srcCoords = {srcTile.colIndex(), srcTile.rowIndex()};
215 TileID dstCoords = {dstTile.colIndex(), dstTile.rowIndex()};
216 Port srcPort = {flowOp.getSourceBundle(), flowOp.getSourceChannel()};
217 Port dstPort = {flowOp.getDestBundle(), flowOp.getDestChannel()};
218 LLVM_DEBUG(llvm::dbgs()
219 << "\tAdding Flow: (" << srcCoords.col << ", " << srcCoords.row
220 << ")" << stringifyWireBundle(srcPort.bundle) << srcPort.channel
221 << " -> (" << dstCoords.col << ", " << dstCoords.row << ")"
222 << stringifyWireBundle(dstPort.bundle) << dstPort.channel
223 << "\n");
224 pathfinder.addFlow(srcCoords, srcPort, dstCoords, dstPort,
225 /*packetId=*/std::nullopt, /*isPriorityFlow=*/false,
226 flowOp.getLoc());
227 }
228
229 // Canonicalize all flows after both packet and circuit flows are collected.
230 pathfinder.sortFlows();
231
232 // add existing connections so Pathfinder knows which resources are
233 // available search all existing SwitchBoxOps for exising connections
234 for (SwitchboxOp switchboxOp : device.getOps<SwitchboxOp>()) {
235 if (failed(pathfinder.addFixedConnection(switchboxOp)))
236 return llvm::make_error<RoutingFailure>(
237 llvm::formatv("cannot add the fixed connections of the switchbox "
238 "at tile ({0}, {1})",
239 switchboxOp.colIndex(), switchboxOp.rowIndex()),
240 RoutingFaults{}, switchboxOp.getLoc());
241 }
242
243 // all flows are now populated, call the congestion-aware pathfinder
244 // algorithm
245 // check whether the pathfinder algorithm creates a legal routing
246 llvm::Expected<Routing> found = pathfinder.findPaths(maxIterations);
247 if (!found)
248 return found.takeError();
249 routing = std::move(*found);
250
251 // fill in coords to TileOps, SwitchboxOps, and ShimMuxOps
252 coordToTile.clear();
253 coordToSwitchbox.clear();
254 coordToShimMux.clear();
255 for (auto tileOp : device.getOps<TileOp>()) {
256 [[maybe_unused]] bool fresh =
257 coordToTile.try_emplace(tileOp.getTileID(), tileOp).second;
258 assert(fresh);
259 }
260 for (auto switchboxOp : device.getOps<SwitchboxOp>()) {
261 [[maybe_unused]] bool fresh =
262 coordToSwitchbox
263 .try_emplace({switchboxOp.colIndex(), switchboxOp.rowIndex()},
264 switchboxOp)
265 .second;
266 assert(fresh);
267 }
268 for (auto shimmuxOp : device.getOps<ShimMuxOp>()) {
269 [[maybe_unused]] bool fresh =
270 coordToShimMux
271 .try_emplace({shimmuxOp.colIndex(), shimmuxOp.rowIndex()},
272 shimmuxOp)
273 .second;
274 assert(fresh);
275 }
276
277 LLVM_DEBUG(llvm::dbgs() << "\t---End DynamicTileAnalysis Constructor---\n");
278 return llvm::Error::success();
279}
280
281TileOp DynamicTileAnalysis::getTile(OpBuilder &builder, int col, int row) {
282 TileOp &tileOp = coordToTile[{col, row}];
283 if (!tileOp)
284 tileOp = TileOp::create(
285 builder,
286 cast<DeviceOp>(builder.getInsertionBlock()->getParentOp()).getLoc(),
287 col, row);
288 return tileOp;
289}
290
291TileOp DynamicTileAnalysis::getTile(OpBuilder &builder, const TileID &tileId) {
292 return getTile(builder, tileId.col, tileId.row);
293}
294
295SwitchboxOp DynamicTileAnalysis::getSwitchbox(OpBuilder &builder, int col,
296 int row) {
297 assert(col >= 0);
298 assert(row >= 0);
299 if (SwitchboxOp switchboxOp = lookupSwitchbox({col, row}))
300 return switchboxOp;
301 auto tileOp = getTile(builder, col, row);
302 auto switchboxOp = SwitchboxOp::create(builder, tileOp.getLoc(), tileOp);
303 SwitchboxOp::ensureTerminator(switchboxOp.getConnections(), builder,
304 tileOp.getLoc());
305 coordToSwitchbox[{col, row}] = switchboxOp;
306 return switchboxOp;
307}
308
309ShimMuxOp DynamicTileAnalysis::getShimMux(OpBuilder &builder, int col) {
310 assert(col >= 0);
311 if (ShimMuxOp shimMuxOp = lookupShimMux(col))
312 return shimMuxOp;
313 auto tileOp = getTile(builder, col, 0);
314 assert(tileOp.isShimNOCorPLTile());
315 auto shimMuxOp = ShimMuxOp::create(builder, tileOp.getLoc(), tileOp);
316 ShimMuxOp::ensureTerminator(shimMuxOp.getConnections(), builder,
317 tileOp.getLoc());
318 coordToShimMux[{col, 0}] = shimMuxOp;
319 return shimMuxOp;
320}
321
322void Pathfinder::initialize(int maxCol, int maxRow,
323 const AIETargetModel &targetModel) {
324 // Reset the graph and flows so a Pathfinder can be reused across analyses
325 // and devices; the dense-graph cache must be rebuilt for the new topology.
326 // The relax state (shareChannels, settings, relaxStep, leads, leadStep,
327 // cappedTiles, crowdedTiles) survives, so the ladder advances across
328 // attempts.
329 graph.clear();
330 flows.clear();
331 packetIdsTo.clear();
332 priorityIds.clear();
333 flowLocs.clear();
334 graphBuilt = false;
335 columns = maxCol;
336 rows = maxRow;
337 nodeIds.clear();
338 nodes.clear();
339 adjacency.clear();
340 wireEdgesBegin.clear();
341 distance.clear();
342 indexInHeap.clear();
343 colors.clear();
344 preds.clear();
345 predEdge.clear();
346
347 std::map<WireBundle, int> maxChannels;
348 auto intraconnect = [&](int col, int row) {
349 TileID coords = {col, row};
350 SwitchboxConnect &sb =
351 graph.try_emplace({coords, coords}, coords).first->second;
352
353 for (int i = 0, e = getMaxEnumValForWireBundle() + 1; i < e; ++i) {
354 WireBundle bundle = symbolizeWireBundle(i).value();
355 // get all ports into current switchbox
356 int channels =
357 targetModel.getNumSourceSwitchboxConnections(col, row, bundle);
358 if (channels == 0 && targetModel.isShimNOCorPLTile(col, row)) {
359 // wordaround for shimMux
360 channels = targetModel.getNumSourceShimMuxConnections(col, row, bundle);
361 }
362 for (int channel = 0; channel < channels; channel++) {
363 sb.srcPorts.push_back(Port{bundle, channel});
364 }
365 // get all ports out of current switchbox
366 channels = targetModel.getNumDestSwitchboxConnections(col, row, bundle);
367 if (channels == 0 && targetModel.isShimNOCorPLTile(col, row)) {
368 // wordaround for shimMux
369 channels = targetModel.getNumDestShimMuxConnections(col, row, bundle);
370 }
371 for (int channel = 0; channel < channels; channel++) {
372 sb.dstPorts.push_back(Port{bundle, channel});
373 }
374 maxChannels[bundle] = channels;
375 }
376 sb.resize();
377 // A shim's mux reaches its DMA, NOC and PLIO ports from any port.
378 auto isMuxed = [&](Port p) {
379 return targetModel.isShimNOCorPLTile(col, row) &&
380 llvm::is_contained(
381 {WireBundle::DMA, WireBundle::NOC, WireBundle::PLIO},
382 p.bundle);
383 };
384 for (auto [i, pIn] : llvm::enumerate(sb.srcPorts))
385 for (auto [j, pOut] : llvm::enumerate(sb.dstPorts))
386 sb.at(i, j).available =
387 targetModel.isLegalTileConnection(col, row, pIn.bundle, pIn.channel,
388 pOut.bundle, pOut.channel) ||
389 isMuxed(pIn) || isMuxed(pOut);
390 };
391
392 auto interconnect = [&](int col, int row, int targetCol, int targetRow,
393 WireBundle srcBundle, WireBundle dstBundle) {
394 TileID src = {col, row}, dst = {targetCol, targetRow};
395 SwitchboxConnect &sb =
396 graph.try_emplace({src, dst}, src, dst).first->second;
397 for (int channel = 0; channel < maxChannels[srcBundle]; channel++) {
398 sb.srcPorts.push_back(Port{srcBundle, channel});
399 sb.dstPorts.push_back(Port{dstBundle, channel});
400 }
401 sb.resize();
402 for (size_t i = 0; i < sb.srcPorts.size(); i++)
403 sb.at(i, i).available = true;
404 };
405
406 for (int row = 0; row <= maxRow; row++) {
407 for (int col = 0; col <= maxCol; col++) {
408 maxChannels.clear();
409 // connections within the same switchbox
410 intraconnect(col, row);
411
412 // connections between switchboxes
413 if (row > 0) {
414 // from south to north
415 interconnect(col, row, col, row - 1, WireBundle::South,
416 WireBundle::North);
417 }
418 if (row < maxRow) {
419 // from north to south
420 interconnect(col, row, col, row + 1, WireBundle::North,
421 WireBundle::South);
422 }
423 if (col > 0) {
424 // from east to west
425 interconnect(col, row, col - 1, row, WireBundle::West,
426 WireBundle::East);
427 }
428 if (col < maxCol) {
429 // from west to east
430 interconnect(col, row, col + 1, row, WireBundle::East,
431 WireBundle::West);
432 }
433 }
434 }
435}
436
437// Add a flow from src to dst can have an arbitrary number of dst locations
438// due to fanout.
439void Pathfinder::addFlow(TileID srcCoords, Port srcPort, TileID dstCoords,
440 Port dstPort, std::optional<int> packetId,
441 bool isPriorityFlow,
442 std::optional<mlir::Location> loc) {
443 auto pinnedIds = constraints.pinnedIds.find({srcCoords, srcPort});
444 if (constraints.pinned.count({srcCoords, srcPort}))
445 isPriorityFlow &= packetId && pinnedIds != constraints.pinnedIds.end() &&
446 pinnedIds->second.count(*packetId);
447 else
448 isPriorityFlow &= constraints.prioritize;
449 if (loc)
450 flowLocs[{srcCoords, srcPort}].try_emplace({dstCoords, dstPort}, *loc);
451 if (packetId) {
452 auto &ids = packetIdsTo[{{srcCoords, srcPort}, {dstCoords, dstPort}}];
453 if (!llvm::is_contained(ids, *packetId))
454 ids.push_back(*packetId);
455 if (isPriorityFlow)
456 priorityIds[{srcCoords, srcPort}].insert(*packetId);
457 }
458 // A source has one flow, with all its destinations.
459 PathEndPoint src{srcCoords, srcPort}, dst{dstCoords, dstPort};
460 auto flow = llvm::find_if(flows, [&](const Flow &f) { return f.src == src; });
461 if (flow == flows.end()) {
462 // sortFlows assigns the packet groups.
463 flows.push_back(
464 Flow{packetId ? 0 : -1, isPriorityFlow, src, {dst}, packetId});
465 } else if (isPriorityFlow) {
466 flow->isPriorityFlow = true;
467 flow->dsts.insert(flow->dsts.begin(), dst);
468 } else {
469 flow->dsts.push_back(dst);
470 }
471}
472
473// Where the flow from `src` to `dst`, or to any destination if `dst` is null,
474// was declared.
475std::optional<mlir::Location>
476Pathfinder::flowLoc(const PathEndPoint &src, const PathEndPoint *dst) const {
477 auto locs = flowLocs.find(src);
478 if (locs == flowLocs.end())
479 return std::nullopt;
480 auto it = dst ? locs->second.find(*dst) : locs->second.begin();
481 if (it == locs->second.end())
482 return std::nullopt;
483 return it->second;
484}
485
486bool Pathfinder::shareAllChannels() {
487 shareChannels = true;
488 return llvm::any_of(flows, [](const Flow &f) { return f.packetGroupId > 0; });
489}
490
491bool Pathfinder::capCrowdedFanOut() {
492 size_t capped = cappedTiles.size();
493 cappedTiles.insert(crowdedTiles.begin(), crowdedTiles.end());
494 return cappedTiles.size() > capped;
495}
496
497std::map<PathEndPoint, std::set<int>> Pathfinder::idsBySource() const {
498 std::map<PathEndPoint, std::set<int>> ids;
499 for (const auto &[ends, sent] : packetIdsTo)
500 ids[ends.first].insert(sent.begin(), sent.end());
501 return ids;
502}
503
504bool Pathfinder::routeIdsApart() {
505 if (any(settings & Relax::IdsApart))
506 return false;
507 settings |= Relax::IdsApart;
508 shareChannels = false;
509 cappedTiles.clear();
510 return llvm::any_of(idsBySource(),
511 [](const auto &s) { return s.second.size() > 1; });
512}
513
514bool Pathfinder::splitSharedIds() {
515 if (any(settings & Relax::SplitShared))
516 return false;
517 settings |= Relax::SplitShared;
518 shareChannels = false;
519 cappedTiles.clear();
520 std::map<PathEndPoint, std::set<int>> ids = idsBySource();
521 for (const auto &[src, srcIds] : ids)
522 for (const auto &[other, otherIds] : ids) {
523 const std::set<int> &theirs = otherIds;
524 if (!(src == other) &&
525 llvm::any_of(srcIds, [&](int id) { return theirs.count(id); }) &&
526 llvm::any_of(srcIds, [&](int id) { return !theirs.count(id); }))
527 return true;
528 }
529 return false;
530}
531
532// The steps before it bent the routing around the meetings, so the ladder
533// starts over without them.
534bool Pathfinder::stopMeeting() {
535 if (any(settings & Relax::MeetApart) || !treesMet)
536 return false;
537 settings |= Relax::MeetApart;
538 settings &= ~(Relax::IdsApart | Relax::SplitShared);
539 shareChannels = false;
540 cappedTiles.clear();
541 relaxStep = 0;
542 return true;
543}
544
545// Which tree routes first decides where the others meet it, and a switchbox
546// takes trees in to one master set only by slave ports of matching channels,
547// so the first a cluster routes can leave the rest no switchbox to meet at.
548bool Pathfinder::rotateLeads() {
549 std::map<PathEndPoint, std::map<PathEndPoint, std::set<int>>> to;
550 for (const auto &[ends, ids] : packetIdsTo)
551 to[ends.first][ends.second].insert(ids.begin(), ids.end());
552 // Whether `a` sends some id to two or more receivers `b` reaches too.
553 auto spans = [&](const PathEndPoint &a, const PathEndPoint &b) {
554 std::map<int, int> shared;
555 for (const auto &[dst, ids] : to[a])
556 if (to[b].count(dst))
557 for (int id : ids)
558 if (++shared[id] > 1)
559 return true;
560 return false;
561 };
562 SmallVector<PathEndPoint, 8> srcs(llvm::make_first_range(to));
563 llvm::IntEqClasses clusters(srcs.size());
564 for (auto [i, a] : llvm::enumerate(srcs))
565 for (auto [j, b] : llvm::enumerate(srcs))
566 if (i < j && spans(a, b) && spans(b, a))
567 clusters.join(i, j);
568 clusters.compress();
569 std::vector<SmallVector<PathEndPoint, 4>> members(clusters.getNumClasses());
570 for (auto [i, src] : llvm::enumerate(srcs))
571 members[clusters[i]].push_back(src);
572 // The first member of each cluster leads already.
573 ++leadStep;
574 leads.clear();
575 for (const auto &cluster : members)
576 if (leadStep < cluster.size())
577 leads.insert(cluster[leadStep]);
578 return !leads.empty();
579}
580
581// A flow with a same-id partner meets another id's tree only on the way to
582// destinations the partner does not reach, as the partner, routed first, has
583// to be met there. A partner routed later meets the flow's tree instead, so
584// in a cluster of two such pairs the first of each can meet the other's.
585bool Pathfinder::meetAhead() {
586 if (any(settings & Relax::MeetAheadOfPartners) || !treesMet)
587 return false;
588 settings |= Relax::MeetAheadOfPartners;
589 return true;
590}
591
592namespace {
593enum class RelaxStep {
594 ShareChannels,
595 CapCrowdedTiles,
596 RouteIdsApart,
597 SplitSharedIds,
598 RotateLeads,
599 MeetAhead,
600 StopMeeting
601};
602// Stopping meetings comes last, and runs the ladder once more: what it routes
603// can hold arbiters in a cycle through the receivers trees share.
604constexpr RelaxStep relaxLadder[] = {
605 RelaxStep::ShareChannels, RelaxStep::CapCrowdedTiles,
606 RelaxStep::RouteIdsApart, RelaxStep::ShareChannels,
607 RelaxStep::CapCrowdedTiles, RelaxStep::SplitSharedIds,
608 RelaxStep::ShareChannels, RelaxStep::CapCrowdedTiles,
609 RelaxStep::RotateLeads, RelaxStep::MeetAhead,
610 RelaxStep::StopMeeting};
611constexpr size_t rotateLeadsStep = std::size(relaxLadder) - 3;
612} // namespace
613
615 if (!packetsFailed) {
616 LLVM_DEBUG(llvm::dbgs() << "No packet stream crosses an overused link\n");
617 return false;
618 }
619 while (relaxStep < std::size(relaxLadder)) {
620 switch (relaxLadder[relaxStep++]) {
621 case RelaxStep::ShareChannels:
622 if (shareAllChannels()) {
623 LLVM_DEBUG(llvm::dbgs() << "Relax: share channels\n");
624 return true;
625 }
626 break;
627 case RelaxStep::CapCrowdedTiles:
628 if (capCrowdedFanOut()) {
629 LLVM_DEBUG(llvm::dbgs() << "Relax: cap crowded tiles\n");
630 return true;
631 }
632 break;
633 case RelaxStep::RouteIdsApart:
634 if (routeIdsApart()) {
635 LLVM_DEBUG(llvm::dbgs() << "Relax: route ids apart\n");
636 return true;
637 }
638 // With one id per source, the steps up to the last two would only
639 // repeat.
640 relaxStep = rotateLeadsStep;
641 break;
642 case RelaxStep::SplitSharedIds:
643 if (splitSharedIds()) {
644 LLVM_DEBUG(llvm::dbgs() << "Relax: split shared ids\n");
645 return true;
646 }
647 relaxStep = rotateLeadsStep;
648 break;
649 case RelaxStep::RotateLeads:
650 // Each member of a cluster leads in turn, the step repeating till all
651 // have.
652 if (rotateLeads()) {
653 --relaxStep;
654 LLVM_DEBUG(llvm::dbgs()
655 << "Relax: route cluster member " << leadStep << " first\n");
656 return true;
657 }
658 break;
659 case RelaxStep::MeetAhead:
660 if (meetAhead()) {
661 LLVM_DEBUG(llvm::dbgs() << "Relax: meet ahead of same-id partners\n");
662 return true;
663 }
664 break;
665 case RelaxStep::StopMeeting:
666 if (stopMeeting()) {
667 LLVM_DEBUG(llvm::dbgs() << "Relax: stop meeting\n");
668 return true;
669 }
670 break;
671 }
672 }
673 return false;
674}
675
676// Sort flows to (1) get deterministic routing, and (2) perform routings on
677// prioritized flows before others, for routing consistency on those flows.
679 for (auto &flow : flows)
680 llvm::sort(flow.dsts);
681
682 // The groups shareAllChannels merges, whatever order the flows were
683 // added in: packet flows to a common destination are in one.
684 llvm::IntEqClasses groups(flows.size());
685 std::map<PathEndPoint, unsigned> firstTo;
686 for (auto [k, flow] : llvm::enumerate(flows)) {
687 if (flow.packetGroupId < 0)
688 continue;
689 for (const PathEndPoint &dst : flow.dsts) {
690 auto [it, fresh] = firstTo.try_emplace(dst, k);
691 if (!fresh)
692 groups.join(k, it->second);
693 }
694 }
695 llvm::DenseMap<unsigned, int> groupOf;
696 for (auto [k, flow] : llvm::enumerate(flows))
697 if (flow.packetGroupId >= 0)
698 flow.packetGroupId =
699 shareChannels
700 ? 0
701 : groupOf.try_emplace(groups.findLeader(k), groupOf.size())
702 .first->second;
703
704 auto flowRank = [](const Flow &flow) {
705 if (flow.isPriorityFlow)
706 return 0;
707 if (flow.packetGroupId >= 0)
708 return 1;
709 return 2;
710 };
711 llvm::sort(flows, [&](const Flow &lhs, const Flow &rhs) {
712 return std::make_tuple(flowRank(lhs), !leads.count(lhs.src), lhs.src) <
713 std::make_tuple(flowRank(rhs), !leads.count(rhs.src), rhs.src);
714 });
715}
716
718 // DMA0 -> N3, DMA1 -> N7; NOC0/1 -> N2/3, NOC2/3 -> N6/7.
719 if (src.bundle == WireBundle::DMA)
720 return src.channel == 0 ? 3 : 7;
721 if (src.bundle == WireBundle::NOC)
722 return src.channel >= 2 ? src.channel + 4 : src.channel + 2;
723 return src.channel;
724}
725
727 // N2 -> DMA0, N3 -> DMA1; N2-5 -> NOC0-3.
728 if (dst.bundle == WireBundle::DMA)
729 return dst.channel == 0 ? 2 : 3;
730 if (dst.bundle == WireBundle::NOC)
731 return dst.channel + 2;
732 return dst.channel;
733}
734
735LogicalResult Pathfinder::addFixedConnection(SwitchboxOp switchboxOp) {
736 int col = switchboxOp.colIndex();
737 int row = switchboxOp.rowIndex();
738 TileID coords = {col, row};
739 auto &sb = graph[std::make_pair(coords, coords)];
740 // Validate every connect against the original connectivity before reserving
741 // any resource, so a broadcast (one source fanning out to several dests) does
742 // not invalidate its own sibling connects mid-scan. A destination port may be
743 // driven only once; a source port may legally recur across a broadcast.
744 llvm::SmallVector<std::pair<int, int>, 8> reserved;
745 llvm::SmallDenseSet<int, 8> claimedDsts;
746 for (ConnectOp connectOp : switchboxOp.getOps<ConnectOp>()) {
747 int srcIdx = sb.srcIndex(connectOp.sourcePort());
748 int dstIdx = sb.dstIndex(connectOp.destPort());
749 // Reject an illegal pair (absent from the switchbox model) or a second
750 // driver on the same output port; a repeated source port is a broadcast.
751 if (srcIdx < 0 || dstIdx < 0 || !sb.at(srcIdx, dstIdx).available ||
752 !claimedDsts.insert(dstIdx).second) {
753 return failure();
754 }
755 reserved.emplace_back(srcIdx, dstIdx);
756 }
757 // A pre-placed packet-switched output (an aie.masterset) also monopolizes its
758 // destination port. That stream-switch output is already configured for
759 // packet switching, so no circuit stream may drive it, and the router cannot
760 // emit a second masterset on the same port for another packet flow. The
761 // circuit pathfinder does not read packet ops, so without this reservation it
762 // may route a flow onto an output the masterset owns and produce two ops
763 // driving one destination.
764 llvm::SmallVector<int, 8> reservedMasterDsts;
765 for (MasterSetOp masterSetOp : switchboxOp.getOps<MasterSetOp>()) {
766 int dstIdx = sb.dstIndex(masterSetOp.destPort());
767 // Reject an output port absent from the switchbox model or already driven
768 // by a circuit connect or another masterset.
769 if (dstIdx < 0 || !claimedDsts.insert(dstIdx).second) {
770 return failure();
771 }
772 reservedMasterDsts.push_back(dstIdx);
773 }
774 // A circuit-switched ConnectOp monopolizes both its source port (the stream
775 // switch input) and its destination port (the output): no other stream may
776 // inject on that input, and the output can carry only this one stream.
777 // Reserving the whole column also reserves the outgoing wire, since that wire
778 // is reachable only by driving this output port.
779 for (auto [srcIdx, dstIdx] : reserved) {
780 for (size_t j = 0; j < sb.dstPorts.size(); j++)
781 sb.at(srcIdx, j).available = false;
782 for (size_t i = 0; i < sb.srcPorts.size(); i++)
783 sb.at(i, dstIdx).available = false;
784 }
785 // A masterset fixes only its output port. Its inputs arrive through arbiters
786 // that packet flows share, so the source rows stay free.
787 for (int dstIdx : reservedMasterDsts)
788 for (size_t i = 0; i < sb.srcPorts.size(); i++)
789 sb.at(i, dstIdx).available = false;
790 // A fixed op on a shim's South channel claims the port the shim mux carries
791 // on it (see shimMuxChannelFrom).
792 if (switchboxOp.getTileOp().isShimNOCorPLTile()) {
793 auto isMuxed = [](Port p) {
794 return llvm::is_contained(
795 {WireBundle::DMA, WireBundle::NOC, WireBundle::PLIO}, p.bundle);
796 };
797 llvm::SmallDenseSet<int, 8> southDsts, southSrcs;
798 for (int dstIdx : claimedDsts)
799 if (sb.dstPorts[dstIdx].bundle == WireBundle::South)
800 southDsts.insert(sb.dstPorts[dstIdx].channel);
801 for (auto [srcIdx, dstIdx] : reserved)
802 if (sb.srcPorts[srcIdx].bundle == WireBundle::South)
803 southSrcs.insert(sb.srcPorts[srcIdx].channel);
804 for (size_t j = 0; j < sb.dstPorts.size(); j++)
805 if (isMuxed(sb.dstPorts[j]) &&
806 southDsts.count(shimMuxChannelTo(sb.dstPorts[j])))
807 for (size_t i = 0; i < sb.srcPorts.size(); i++)
808 sb.at(i, j).available = false;
809 for (size_t i = 0; i < sb.srcPorts.size(); i++)
810 if (isMuxed(sb.srcPorts[i]) &&
811 southSrcs.count(shimMuxChannelFrom(sb.srcPorts[i])))
812 for (size_t j = 0; j < sb.dstPorts.size(); j++)
813 sb.at(i, j).available = false;
814 }
815 for (PacketRulesOp rulesOp : switchboxOp.getOps<PacketRulesOp>()) {
816 int srcIdx = sb.srcIndex(rulesOp.sourcePort());
817 if (srcIdx < 0)
818 return failure();
819 sb.packetOnlySrc.set(srcIdx);
820 }
821 return success();
822}
823
825 auto it = graph.find({coords, coords});
826 if (it == graph.end())
827 return;
828 SwitchboxConnect &sb = it->second;
829 for (size_t i = 0; i < sb.srcPorts.size(); i++)
830 for (size_t j = 0; j < sb.dstPorts.size(); j++)
831 sb.at(i, j).available = false;
832}
833
835 auto it = graph.find({coords, coords});
836 if (it == graph.end())
837 return;
838 SwitchboxConnect &sb = it->second;
839 int j = sb.dstIndex(port);
840 if (j < 0)
841 return;
842 for (size_t i = 0; i < sb.srcPorts.size(); i++)
843 sb.at(i, j).avoidance = avoidedPortDemand;
844}
845
846static constexpr double INF = std::numeric_limits<double>::max();
847
848namespace {
849enum Color : int8_t { WHITE = 0, GRAY = 1, BLACK = 2 };
850} // namespace
851
852int Pathfinder::getOrAddNodeId(const PathEndPoint &pep) {
853 auto it = nodeIds.find(pep);
854 if (it != nodeIds.end())
855 return it->second;
856 int id = static_cast<int>(nodes.size());
857 nodeIds[pep] = id;
858 nodes.push_back(pep);
859 return id;
860}
861
862// Build the dense integer node numbering and per-node adjacency once. The graph
863// topology is fixed across congestion iterations (only the demand weights
864// change), so this is computed a single time and the edges carry live pointers
865// into `graph` for demand lookups. A node's crossbar edges come first, then its
866// wire edges, each sorted by the PathEndPoint they reach, so Dijkstra breaks
867// ties the same way every run.
868void Pathfinder::buildRoutingGraph() {
869 // Seed the dense node set with all flow endpoints (the only nodes Dijkstra is
870 // ever started from or traced back to). Remaining nodes are discovered as
871 // edge destinations below.
872 for (auto &f : flows) {
873 getOrAddNodeId(f.src);
874 for (auto &d : f.dsts)
875 getOrAddNodeId(d);
876 }
877
878 // Process nodes by growing index; getOrAddNodeId() may append new nodes as
879 // edge destinations are discovered, so re-read nodes.size() each iteration.
880 for (size_t id = 0; id < nodes.size(); id++) {
881 PathEndPoint src = nodes[id];
882 // The ports the crossbar connects this one to, and the neighbours' ports
883 // its wire reaches.
884 std::vector<PathEndPoint> dests;
885 auto intraIt = graph.find({src.coords, src.coords});
886 if (intraIt != graph.end()) {
887 auto &sb = intraIt->second;
888 for (auto [i, pIn] : llvm::enumerate(sb.srcPorts))
889 for (auto [j, pOut] : llvm::enumerate(sb.dstPorts))
890 if (pIn == src.port && sb.at(i, j).available)
891 dests.emplace_back(src.coords, pOut);
892 }
893 std::pair<TileID, Port> neighbors[] = {
894 {{src.coords.col, src.coords.row - 1},
895 {WireBundle::North, src.port.channel}},
896 {{src.coords.col - 1, src.coords.row},
897 {WireBundle::East, src.port.channel}},
898 {{src.coords.col, src.coords.row + 1},
899 {WireBundle::South, src.port.channel}},
900 {{src.coords.col + 1, src.coords.row},
901 {WireBundle::West, src.port.channel}}};
902 for (const auto &[neighborCoords, neighborPort] : neighbors) {
903 auto nIt = graph.find({src.coords, neighborCoords});
904 if (nIt != graph.end() &&
905 src.port.bundle == getConnectingBundle(neighborPort.bundle) &&
906 llvm::is_contained(nIt->second.dstPorts, neighborPort))
907 dests.emplace_back(neighborCoords, neighborPort);
908 }
909 llvm::sort(dests);
910
911 std::vector<Edge> edges;
912 edges.reserve(dests.size());
913 for (auto &dest : dests) {
914 auto &sb = graph.at({src.coords, dest.coords});
915 int i = sb.srcIndex(src.port);
916 int j = sb.dstIndex(dest.port);
917 assert(i >= 0 && j >= 0);
918 int destId = getOrAddNodeId(dest);
919 edges.push_back(Edge{destId, &sb, i, j});
920 }
921 auto wires =
922 std::stable_partition(edges.begin(), edges.end(), [](const Edge &e) {
923 return e.sb->srcCoords == e.sb->dstCoords;
924 });
925 if (wireEdgesBegin.size() < nodes.size())
926 wireEdgesBegin.resize(nodes.size());
927 wireEdgesBegin[id] = wires - edges.begin();
928 // getOrAddNodeId above may have reallocated `adjacency` via index growth in
929 // later iterations, but we only assign this node's edges now.
930 if (adjacency.size() < nodes.size())
931 adjacency.resize(nodes.size());
932 adjacency[id] = std::move(edges);
933 }
934 size_t n = nodes.size();
935 if (adjacency.size() < n)
936 adjacency.resize(n);
937 wireEdgesBegin.resize(n);
938
939 // Size the reusable Dijkstra scratch buffers. These are indexed by state id,
940 // i.e. two entries per node -- one per side of the port.
941 distance.assign(2 * n, INF);
942 indexInHeap.assign(2 * n, 0);
943 colors.assign(2 * n, WHITE);
944 preds.assign(2 * n, -1);
945 predEdge.assign(2 * n, Edge{-1, nullptr, 0, 0});
946 graphBuilt = true;
947}
948
949double Pathfinder::edgeWeight(const Edge &e, std::optional<int> packetId,
950 const llvm::BitVector *avoid,
951 const llvm::BitVector *avoidBranch) const {
952 const SwitchboxConnect::Cell &cell = e.sb->at(e.i, e.j);
953 double w = cell.demand;
954 // Sharing it would take a second stream's capacity, which the demand
955 // only shows once the group is routed.
956 if (packetId && cell.packetFlowCount > 0 && cell.packetIds.count(*packetId))
957 w *= demandCoeff;
958 if (e.sb->srcCoords == e.sb->dstCoords)
959 for (const llvm::BitVector *flows : {avoid, avoidBranch})
960 if (flows && llvm::any_of(e.sb->unitFlows(e.j),
961 [&](int f) { return flows->test(f); }))
962 w += conflictSharePenalty;
963 return w;
964}
965
966// Dijkstra over the dense graph from the states in `seeds`, searching states
967// (node, PortSide) rather than bare nodes. Fills the `preds` and `predEdge`
968// scratch buffers, both indexed by state id.
969void Pathfinder::dijkstraShortestPaths(
970 ArrayRef<int> seeds, ArrayRef<double> seedCosts,
971 std::optional<int> packetId, const llvm::BitVector *avoid,
972 const llvm::DenseMap<int, llvm::BitVector> *branchAvoid,
973 const llvm::DenseSet<int> *stops, ArrayRef<int> targets,
974 llvm::function_ref<bool(int, int)> mayCross) {
975 llvm::fill(distance, INF);
976 llvm::fill(colors, static_cast<int8_t>(WHITE));
977 llvm::fill(preds, -1);
978 llvm::fill(indexInHeap, uint64_t{0});
979
980 using MutableQueue = d_ary_heap_indirect<
981 /*Value=*/int, /*Arity=*/4,
982 /*IndexInHeapPropertyMap=*/std::vector<uint64_t> &,
983 /*DistanceMap=*/std::vector<double> &,
984 /*Compare=*/std::less<>>;
985 MutableQueue Q(distance, indexInHeap);
986
987 for (auto [seed, cost] : llvm::zip_equal(seeds, seedCosts)) {
988 distance[seed] = cost;
989 colors[seed] = GRAY;
990 Q.push(seed);
991 }
992 // A settled state's distance and predecessor never change again.
993 SmallVector<int, 8> unsettled(targets);
994 while (!Q.empty()) {
995 int s = Q.top();
996 Q.pop();
997 if (llvm::is_contained(unsettled, s)) {
998 llvm::erase(unsettled, s);
999 if (unsettled.empty())
1000 break;
1001 }
1002 if (stops && stops->count(s)) {
1003 colors[s] = BLACK;
1004 continue;
1005 }
1006 // In takes crossbar edges and lands on the Out side of the port it picks;
1007 // Out takes the wire to the neighbour and lands on that tile's In side. Any
1008 // other pairing would either turn the stream around inside a switchbox or
1009 // ride a wire the crossbar was never set to drive.
1010 const bool sIsOut = (s & 1) == Out;
1011 const llvm::BitVector *avoidBranch = nullptr;
1012 if (branchAvoid)
1013 if (auto it = branchAvoid->find(s); it != branchAvoid->end())
1014 avoidBranch = &it->second;
1015 ArrayRef<Edge> out = adjacency[stateNode(s)];
1016 size_t wires = wireEdgesBegin[stateNode(s)];
1017 const bool isIntra = !sIsOut;
1018 for (const Edge &e :
1019 sIsOut ? out.drop_front(wires) : out.take_front(wires)) {
1020 if ((isIntra && !packetId && e.sb->packetOnlySrc[e.i]) ||
1021 (isIntra && packetId && e.sb->circuitOnlyDst[e.j]))
1022 continue;
1023 int dst = stateId(e.dst, isIntra ? Out : In);
1024 if (colors[dst] == BLACK || (isIntra && mayCross && !mayCross(s, dst)))
1025 continue;
1026 double w = edgeWeight(e, packetId, avoid, avoidBranch);
1027 if (distance[s] + w >= distance[dst])
1028 continue;
1029 distance[dst] = distance[s] + w;
1030 preds[dst] = s;
1031 predEdge[dst] = e;
1032 if (colors[dst] == WHITE) {
1033 colors[dst] = GRAY;
1034 Q.push(dst);
1035 } else {
1036 Q.update(dst);
1037 }
1038 }
1039 colors[s] = BLACK;
1040 }
1041}
1042
1043// What findPaths keeps from one flow and iteration to the next.
1045 explicit RouteState(const Pathfinder &pf);
1046
1047 int groupOf(const Flow &f) const;
1048 SmallVector<int, 4> idsTo(int flow, int dstState) const;
1049 void relateParts();
1050 int splitPart(int flow, const std::set<int> &ids);
1051 bool isPinned(const Flow &f) const;
1052
1055 // Stamp-based "processed" set (avoids O(n) clears per flow).
1056 std::vector<uint32_t> processedStamp;
1057 uint32_t curStamp = 0;
1058 // The flows to route: one per source, less the packets split off into parts
1059 // of their own (see below), which route as flows from the same source.
1060 std::vector<Flow> parts;
1061 std::map<PathEndPoint, SmallVector<int, 2>> partsOf;
1062 std::set<PathEndPoint> flowDsts;
1063 // group flows based on packetGroupId; pinned trees go in first, so the
1064 // flows routed around them see them.
1065 llvm::MapVector<int, SmallVector<int, 8>> groupedFlows;
1066 // Packet flows that conflict, by the ids each carries or by
1067 // RoutingFaults::apart.
1068 std::vector<llvm::BitVector> conflicting;
1069 std::set<std::pair<PathEndPoint, PathEndPoint>> apartSources;
1070 std::set<std::pair<PathEndPoint, PathEndPoint>> togetherSources;
1071 // Sources a tree had to meet this iteration but whose other ids conflict
1072 // with it (see TreeBuilder::meet), which route together from then on.
1073 std::set<std::pair<PathEndPoint, PathEndPoint>> meetBlocked;
1074 // Ids a source routes as a part of their own so the rest of its tree can
1075 // meet another source's, by that pair (see TreeBuilder::findJoins).
1076 std::set<std::pair<std::pair<PathEndPoint, PathEndPoint>, std::set<int>>>
1078 // The packet ids each flow carries, in all and to each destination.
1079 std::vector<std::set<int>> flowIds;
1080 std::vector<SmallVector<int, 4>> sameId;
1081 // Each packet flow's tree as routed so far this iteration: the state each
1082 // hop reaches, from which state and by which edge; and its destinations.
1083 std::vector<llvm::DenseMap<int, std::pair<int, Edge>>> treeOf;
1084 // Each circuit flow's hops this iteration, which treeOf keeps for packet
1085 // flows only.
1086 std::vector<SmallVector<Edge, 8>> circuitHops;
1087 std::vector<SmallVector<int, 4>> treeDsts;
1088 // The hops each flow takes only by joining another flow's tree, by the flow
1089 // it joined. A join the routing check faults is not made again.
1090 std::vector<SmallVector<std::pair<int, Edge>, 8>> joinedHops;
1091 std::set<std::pair<int, int>> noJoin;
1092 // Where the routing check split a flow's tree: the tile it branches at, the
1093 // ids to branch apart there, and the state of the destination that reaches
1094 // the tile apart, if one does.
1095 struct IdSplit {
1097 int a, b;
1098 std::optional<int> apart;
1099 bool operator<(const IdSplit &other) const {
1100 return std::tie(at, a, b, apart) <
1101 std::tie(other.at, other.a, other.b, other.apart);
1102 }
1103 };
1104 std::vector<std::set<IdSplit>> splitsOf;
1105 // Each split, relation, untrunk and no-join pair the routing check has taught
1106 // this attempt, counted once: a stall drops splitsOf, and the check teaching
1107 // the same split again is no progress.
1108 std::set<std::pair<int, IdSplit>> splitsTaught;
1109 int lessons = 0;
1110 // A split one tree cannot make, since a destination takes both ids, moves
1111 // the second id to a part of its own. Parts of a source split apart at a
1112 // tile leave it by different master ports: the part routed later keeps off
1113 // those the other's tree takes there.
1114 std::vector<std::set<std::pair<TileID, int>>> partSplits;
1115 // Flows that found no one switchbox to meet a tree routed before them at,
1116 // by that tree's flow; each such pair routes the other way round once.
1117 std::set<std::pair<int, int>> unmet, reordered;
1118 // A tree branching for two destinations at its source switchbox may leave
1119 // no slave port there to meet it by. Each of an unmet pair then reaches the
1120 // destinations it shares with the other by one master port out of it.
1121 std::set<std::pair<int, int>> trunked;
1122 // Sources whose trunk took their tree back through a switchbox it holds an
1123 // arbiter in (RoutingFaults::untrunk), which branch freely from then on.
1124 std::set<PathEndPoint> untrunked;
1125 // The flows that met a tree this iteration, by its flow, and how often the
1126 // routing check faulted a meeting of each pair.
1127 std::set<std::pair<int, int>> met;
1128 // The source whose tree met another's by each slave port this iteration, by
1129 // the tree it met: a tree from another source meeting it there would only
1130 // share the first one's way in, not meet.
1131 std::map<std::pair<int, int>, PathEndPoint> meetingPorts;
1132 std::map<std::pair<int, int>, int> meetFaults;
1133 // Joined pairs the routing check faulted along with hops neither joined,
1134 // which were left to the penalties on those hops once.
1135 std::set<std::pair<int, int>> spared;
1136 // A control-packet reload keeps the master sets the prioritized flows' trees
1137 // leave each switchbox by, so another flow leaving by one of those master
1138 // ports leaves by all of one such set and no others.
1139 llvm::DenseSet<int> priorityMasters;
1140 std::vector<SmallVector<int, 4>> prioritySets;
1141 bool mayLeave(ArrayRef<int> masters, int next) const;
1142 bool reorder(int later, int earlier, bool again = false);
1143 void splitOwnIds(const std::pair<PathEndPoint, PathEndPoint> &pair);
1144};
1145
1147 : pf(pf), processedStamp(2 * pf.nodes.size(), 0), parts(pf.flows),
1148 conflicting(parts.size(), llvm::BitVector(parts.size())),
1149 flowIds(parts.size()), treeOf(parts.size()), circuitHops(parts.size()),
1150 treeDsts(parts.size()), joinedHops(parts.size()), splitsOf(parts.size()),
1151 partSplits(parts.size()) {
1152 for (auto [k, f] : llvm::enumerate(parts)) {
1153 partsOf[f.src].push_back(k);
1154 flowDsts.insert(f.dsts.begin(), f.dsts.end());
1155 }
1156 for (auto [k, f] : llvm::enumerate(parts))
1157 groupedFlows[groupOf(f)].push_back(k);
1158 for (const auto &[ends, ids] : pf.packetIdsTo)
1159 flowIds[partsOf.at(ends.first).front()].insert(ids.begin(), ids.end());
1160 relateParts();
1161 // A pinned source's other packets follow the pinned tree where they go
1162 // everywhere it goes, so they leave each switchbox by its master sets, and
1163 // otherwise route as a part of their own.
1164 for (size_t k = 0, n = parts.size(); k < n; k++) {
1165 if (!isPinned(parts[k]))
1166 continue;
1167 const PathEndPoint &src = parts[k].src;
1168 const std::set<int> &prioritized = pf.priorityIds.at(src);
1169 std::set<PathEndPoint> treeDsts;
1170 std::map<int, std::set<PathEndPoint>> dstsOf;
1171 for (const auto &[ends, ids] : pf.packetIdsTo)
1172 if (ends.first == src)
1173 for (int id : ids)
1174 (prioritized.count(id) ? treeDsts : dstsOf[id]).insert(ends.second);
1175 std::set<int> others;
1176 for (const auto &[id, dsts] : dstsOf)
1177 if (!prioritized.count(id) && dsts != treeDsts)
1178 others.insert(id);
1179 if (!others.empty())
1180 splitPart(k, others);
1181 }
1182 for (const auto &[src, tree] : pf.constraints.pinned) {
1183 std::map<PathEndPoint, SmallVector<int, 4>> sets;
1184 for (const TreeHop &h : tree) {
1185 auto to = pf.nodeIds.find(h.to);
1186 if (h.from.coords == h.to.coords && to != pf.nodeIds.end())
1187 sets[h.from].push_back(stateId(to->second, Out));
1188 }
1189 for (auto &[_, set] : sets) {
1190 llvm::sort(set);
1191 priorityMasters.insert(set.begin(), set.end());
1192 prioritySets.push_back(std::move(set));
1193 }
1194 }
1195}
1196
1197// Route `later` before `earlier` from the next iteration on, unless the two
1198// were reordered before and this is not `again`.
1199bool Pathfinder::RouteState::reorder(int later, int earlier, bool again) {
1200 if (!again && (reordered.count({earlier, later}) ||
1201 !reordered.insert({later, earlier}).second))
1202 return false;
1203 SmallVector<int, 8> &group = groupedFlows[groupOf(parts[later])];
1204 if (!llvm::is_contained(group, earlier))
1205 return false;
1206 group.erase(llvm::find(group, later));
1207 group.insert(llvm::find(group, earlier), later);
1208 return true;
1209}
1210
1211// Trees with an id in common join where they meet, so the ids a source sends
1212// that the other does not route apart as a part of their own.
1214 const std::pair<PathEndPoint, PathEndPoint> &pair) {
1215 for (auto [src, other] : {pair, std::pair{pair.second, pair.first}}) {
1216 auto srcParts = partsOf.find(src);
1217 auto otherParts = partsOf.find(other);
1218 if (srcParts == partsOf.end() || otherParts == partsOf.end())
1219 continue;
1220 std::set<int> otherIds;
1221 for (int k : otherParts->second)
1222 otherIds.insert(flowIds[k].begin(), flowIds[k].end());
1223 for (int k : SmallVector<int, 2>(srcParts->second)) {
1224 std::set<int> own;
1225 for (int id : flowIds[k])
1226 if (!otherIds.count(id))
1227 own.insert(id);
1228 if (!parts[k].isPriorityFlow && !own.empty() &&
1229 own.size() < flowIds[k].size())
1230 splitPart(k, own);
1231 }
1232 }
1233}
1234
1235// Whether a tree whose packets leave a switchbox by `masters` from one slave
1236// port may leave it by `next` too; see priorityMasters.
1237bool Pathfinder::RouteState::mayLeave(ArrayRef<int> masters, int next) const {
1238 if (!priorityMasters.count(next) &&
1239 llvm::none_of(masters, [&](int m) { return priorityMasters.count(m); }))
1240 return true;
1241 return llvm::any_of(prioritySets, [&](const SmallVector<int, 4> &set) {
1242 return llvm::is_contained(set, next) && llvm::all_of(masters, [&](int m) {
1243 return llvm::is_contained(set, m);
1244 });
1245 });
1246}
1247
1249 return f.isPriorityFlow && pf.constraints.pinned.count(f.src);
1250}
1251
1253 return isPinned(f) ? std::numeric_limits<int>::min() : f.packetGroupId;
1254}
1255
1256SmallVector<int, 4> Pathfinder::RouteState::idsTo(int flow,
1257 int dstState) const {
1258 SmallVector<int, 4> ids;
1259 auto it =
1260 pf.packetIdsTo.find({parts[flow].src, pf.nodes[stateNode(dstState)]});
1261 if (it != pf.packetIdsTo.end())
1262 for (int id : it->second)
1263 if (flowIds[flow].count(id))
1264 ids.push_back(id);
1265 return ids;
1266}
1267
1269 sameId.assign(parts.size(), {});
1270 conflicting.assign(parts.size(), llvm::BitVector(parts.size()));
1271 for (size_t a = 0; a < parts.size(); a++)
1272 for (size_t b = 0; b < parts.size(); b++) {
1273 // Trees with an id in common join where they meet, so are never apart.
1274 bool same = llvm::any_of(flowIds[a],
1275 [&](int id) { return flowIds[b].count(id); });
1276 if (a != b && same)
1277 sameId[a].push_back(b);
1278 if (a < b && parts[a].packetId && parts[b].packetId &&
1279 ((!same &&
1280 apartSources.count(std::minmax(parts[a].src, parts[b].src))) ||
1281 (pf.constraints.conflict &&
1282 pf.constraints.conflict(parts[a].src, flowIds[a], parts[b].src,
1283 flowIds[b])))) {
1284 conflicting[a].set(b);
1285 conflicting[b].set(a);
1286 }
1287 }
1288}
1289
1290int Pathfinder::RouteState::splitPart(int flow, const std::set<int> &ids) {
1291 int part = parts.size();
1292 Flow f = parts[flow];
1293 LLVM_DEBUG({
1294 llvm::dbgs() << "\t\tRouting ids";
1295 for (int id : ids)
1296 llvm::dbgs() << ' ' << id;
1297 llvm::dbgs() << " from " << describeTilePort(f.src.coords, f.src.port)
1298 << " apart\n";
1299 });
1300 for (int id : ids)
1301 flowIds[flow].erase(id);
1302 flowIds.push_back(ids);
1303 auto carries = [&](int k, const PathEndPoint &p) {
1304 auto it = pf.packetIdsTo.find({f.src, p});
1305 return it != pf.packetIdsTo.end() &&
1306 llvm::any_of(it->second, [&](int i) { return flowIds[k].count(i); });
1307 };
1308 llvm::erase_if(f.dsts,
1309 [&](const PathEndPoint &p) { return !carries(part, p); });
1310 llvm::erase_if(parts[flow].dsts,
1311 [&](const PathEndPoint &p) { return !carries(flow, p); });
1312 f.packetId = *ids.begin();
1313 std::optional<int> &flowId = parts[flow].packetId;
1314 if (flowId && ids.count(*flowId))
1315 flowId = *flowIds[flow].begin();
1316 auto prioritized = [&](const std::set<int> &carried) {
1317 auto prio = pf.priorityIds.find(f.src);
1318 return prio != pf.priorityIds.end() && llvm::any_of(carried, [&](int id) {
1319 return prio->second.count(id);
1320 });
1321 };
1322 f.isPriorityFlow = prioritized(ids);
1323 parts[flow].isPriorityFlow = prioritized(flowIds[flow]);
1324 parts.push_back(f);
1325 partsOf[f.src].push_back(part);
1326 groupedFlows[groupOf(f)].push_back(part);
1327 relateParts();
1328 treeOf.emplace_back();
1329 circuitHops.emplace_back();
1330 treeDsts.emplace_back();
1331 joinedHops.emplace_back();
1332 for (auto [a, b] : std::set<std::pair<int, int>>(noJoin))
1333 if (a == flow || b == flow)
1334 noJoin.insert({a == flow ? part : a, b == flow ? part : b});
1335 splitsOf.push_back(splitsOf[flow]);
1336 partSplits.push_back(partSplits[flow]);
1337 for (auto [at, other] : partSplits[flow])
1338 partSplits[other].insert({at, part});
1339 for (auto [at, a, b, apart] : splitsOf[flow])
1340 if (ids.count(a) != ids.count(b) &&
1341 flowIds[flow].count(ids.count(a) ? b : a)) {
1342 partSplits[flow].insert({at, part});
1343 partSplits[part].insert({at, flow});
1344 }
1345 return part;
1346}
1347
1348// A link with a channel no flow takes and a free master port driving it
1349// was overused only by the way the flows went; its flows could spread.
1350bool Pathfinder::hasRoom(const SwitchboxConnect &sb) const {
1351 if (sb.srcCoords == sb.dstCoords)
1352 return true;
1353 auto xbar = graph.find({sb.srcCoords, sb.srcCoords});
1354 for (size_t i = 0; i < sb.srcPorts.size(); i++)
1355 for (size_t j = 0; j < sb.dstPorts.size(); j++) {
1356 const SwitchboxConnect::Cell &c = sb.at(i, j);
1357 if (!c.available || c.usedCapacity > 0)
1358 continue;
1359 if (xbar == graph.end())
1360 return true;
1361 const SwitchboxConnect &x = xbar->second;
1362 int k = x.dstIndex(sb.srcPorts[i]);
1363 if (k < 0)
1364 return true;
1365 for (size_t row = 0; row < x.srcPorts.size(); row++)
1366 if (x.at(row, k).available)
1367 return true;
1368 }
1369 return false;
1370}
1371
1372llvm::Error Pathfinder::explainNoRouting(const RouteState &st) const {
1373 // A prioritized flow keeps the route it takes alone, so the others
1374 // may have had to fit around it.
1375 auto overused = [](const SwitchboxConnect &sb) {
1376 return sb.srcCoords != sb.dstCoords &&
1377 llvm::any_of(sb.cells, [](const SwitchboxConnect::Cell &c) {
1378 return c.usedCapacity > maxCircuitStreamCapacity;
1379 });
1380 };
1381 auto link = [](const SwitchboxConnect &sb) -> std::string {
1382 return llvm::formatv("from tile ({0}, {1}) to ({2}, {3})", sb.srcCoords.col,
1383 sb.srcCoords.row, sb.dstCoords.col, sb.dstCoords.row);
1384 };
1385 const Flow *prioritized = nullptr;
1386 llvm::SetVector<const SwitchboxConnect *> held;
1387 for (auto [k, f] : llvm::enumerate(st.parts)) {
1388 if (!st.isPinned(f))
1389 continue;
1390 prioritized = prioritized ? prioritized : &f;
1391 for (const auto &[_, hop] : st.treeOf[k]) {
1392 if (overused(*hop.second.sb)) {
1393 return llvm::make_error<PinnedRoutingFailure>(
1394 describePrioritized(describeTilePort(f.src.coords, f.src.port)) +
1395 ", and it holds a channel " + link(*hop.second.sb) +
1396 " the other flows need.");
1397 }
1398 if (hop.second.sb->srcCoords != hop.second.sb->dstCoords)
1399 held.insert(hop.second.sb);
1400 }
1401 }
1402 if (prioritized && llvm::any_of(graph, [&](const auto &entry) {
1403 return overused(entry.second);
1404 })) {
1405 return llvm::make_error<PinnedRoutingFailure>(
1407 describeTilePort(prioritized->src.coords, prioritized->src.port)) +
1408 ", and the router found no routing for the other flows around the "
1409 "channels it holds " +
1410 joinNames(llvm::to_vector(
1411 llvm::map_range(llvm::make_pointee_range(held), link))) +
1412 ".");
1413 }
1414 // The routing check says more than the overuse it led to.
1415 if (!checkReason.empty())
1416 return llvm::make_error<RoutingFailure>(checkReason);
1417 // Name the channel the last iteration overused that was overused in the
1418 // most iterations, on a link with no room if there is one, and the flows
1419 // the last one routed through it.
1420 const SwitchboxConnect *worst = nullptr;
1421 int worstI = 0, worstJ = 0;
1422 std::pair<bool, int> worstRank{false, 0};
1423 for (const auto &[_, sb] : graph) {
1424 std::optional<bool> roomless;
1425 for (size_t i = 0; i < sb.srcPorts.size(); i++)
1426 for (size_t j = 0; j < sb.dstPorts.size(); j++) {
1427 if (sb.at(i, j).usedCapacity <= maxCircuitStreamCapacity)
1428 continue;
1429 if (!roomless)
1430 roomless = !hasRoom(sb);
1431 std::pair<bool, int> rank{*roomless, sb.at(i, j).overCapacity};
1432 if (rank > worstRank) {
1433 worst = &sb;
1434 worstI = i;
1435 worstJ = j;
1436 worstRank = rank;
1437 }
1438 }
1439 }
1440 if (!worst)
1441 return llvm::make_error<RoutingFailure>("");
1442 bool crossbar = worst->srcCoords == worst->dstCoords;
1443 std::vector<std::string> users;
1444 for (const auto &[src, settings] : st.routing.settings) {
1445 auto it = settings.find(worst->srcCoords);
1446 if (it == settings.end())
1447 continue;
1448 const SwitchSetting &s = it->second;
1449 bool uses = false;
1450 for (size_t k = 0; k < s.dsts.size() && !uses; k++)
1451 uses = crossbar
1452 ? k < s.srcs.size() && s.srcs[k] == worst->srcPorts[worstI] &&
1453 s.dsts[k] == worst->dstPorts[worstJ]
1454 : llvm::is_contained(worst->srcPorts, s.dsts[k]);
1455 if (uses)
1456 users.push_back(describeTilePort(src.coords, src.port));
1457 }
1458 std::string where =
1459 crossbar ? llvm::formatv("the connection from {0} to {1} at tile ({2}, "
1460 "{3})",
1461 describePort(worst->srcPorts[worstI]),
1462 describePort(worst->dstPorts[worstJ]),
1463 worst->srcCoords.col, worst->srcCoords.row)
1464 .str()
1465 : "the links " + link(*worst);
1466 if (users.empty())
1467 return llvm::make_error<RoutingFailure>(
1468 "the router found no routing that fits " + where + ".");
1469 return llvm::make_error<RoutingFailure>(
1470 "the flows from " + joinNames(users) + " need " + where +
1471 ", and the router found no routing that fits them.");
1472}
1473
1474std::tuple<bool, int, bool> xilinx::AIE::boundaryOf(TileID a, TileID b) {
1475 bool rows = a.col == b.col;
1476 return {rows, rows ? std::min(a.row, b.row) : std::min(a.col, b.col),
1477 rows ? b.row > a.row : b.col > a.col};
1478}
1479
1480llvm::Error Pathfinder::cutOverflow() const {
1481 // Each circuit tree crossing a boundary needs a channel of its own, and the
1482 // packet flows one more, or one each for streams no two of which may share
1483 // an arbiter, since a channel's master port has one. Channels fixed
1484 // connections hold are not the router's to use, so this rejects only what
1485 // it could not route anyway.
1486 auto onDevice = [&](TileID t) { return t.col < columns && t.row < rows; };
1487 std::map<std::tuple<bool, int, bool>, size_t> channels;
1488 for (const auto &[ends, sb] : graph) {
1489 const auto &[a, b] = ends;
1490 auto xbar = graph.find({a, a});
1491 if (a == b || !onDevice(a) || !onDevice(b) || xbar == graph.end())
1492 continue;
1493 std::tuple<bool, int, bool> cut = boundaryOf(a, b);
1494 const SwitchboxConnect &x = xbar->second;
1495 // A boundary with no available channel at all (every one is a fixed
1496 // connection's) still needs an entry, so flows that must cross it are
1497 // not skipped as if the boundary did not exist.
1498 channels[cut] += 0;
1499 for (Port port : sb.srcPorts) {
1500 int k = x.dstIndex(port);
1501 if (k >= 0 &&
1502 llvm::any_of(llvm::seq<size_t>(0, x.srcPorts.size()),
1503 [&](size_t i) { return x.at(i, k).available; }))
1504 channels[cut]++;
1505 }
1506 }
1507 for (const auto &[cut, available] : channels) {
1508 bool rows = std::get<0>(cut), up = std::get<2>(cut);
1509 int below = std::get<1>(cut);
1510 auto low = [&](TileID t) { return (rows ? t.row : t.col) <= below; };
1511 std::vector<std::string> circuits;
1512 bool packets = false;
1513 for (const Flow &f : flows) {
1514 if (low(f.src.coords) != up ||
1515 llvm::none_of(f.dsts, [&](const PathEndPoint &d) {
1516 return low(d.coords) != up;
1517 }))
1518 continue;
1519 if (f.packetId)
1520 packets = true;
1521 else
1522 circuits.push_back(describeTilePort(f.src.coords, f.src.port));
1523 }
1524 PacketsApart apart;
1525 if (packets && constraints.apartAcross && available > circuits.size())
1526 apart = constraints.apartAcross(low, up, available - circuits.size());
1527 size_t needed =
1528 circuits.size() + std::max<size_t>(packets, apart.flows.size());
1529 LLVM_DEBUG(llvm::dbgs() << "Cut " << (rows ? "row " : "column ") << below
1530 << (up ? " up" : " down") << ": " << needed
1531 << " of " << available << " channels\n");
1532 if (needed <= available)
1533 continue;
1534 int from = up ? below : below + 1, to = up ? below + 1 : below;
1535 auto channel = [](size_t n) { return n == 1 ? "channel" : "channels"; };
1536 std::string who =
1537 circuits.empty() ? "" : "the circuit flows from " + joinNames(circuits);
1538 if (apart.flows.size() > 1)
1539 who += (who.empty() ? "" : ", and ") + joinNames(apart.flows) +
1540 ", no two of which can share an arbiter,";
1541 else if (packets)
1542 who =
1543 circuits.empty() ? "the packet flows" : who + ", with packet flows,";
1544 std::string why =
1545 apart.flows.size() > 1 ? " For example, " + apart.why : "";
1546 return llvm::make_error<RoutingFailure>(llvm::formatv(
1547 "{0} cross from {1} {2} to {1} {3}, which takes {4} {5} across, and "
1548 "it has {6} {7}.{8}",
1549 who, rows ? "row" : "column", from, to, needed, channel(needed),
1550 available, channel(available), why));
1551 }
1552 return llvm::Error::success();
1553}
1554
1555// One flow's tree, grown by routePart.
1558
1559 // A destination port is driven by its switchbox, so it is reached on
1560 // the Out side.
1561 int dstState(const PathEndPoint &p) const {
1562 return stateId(pf.nodeIds.at(p), Out);
1563 }
1564 bool isPending(int state) const;
1565 void reach(ArrayRef<int> dsts);
1566 bool joinable(int at, ArrayRef<int> dsts) const;
1567 void findJoins();
1568 void meet();
1569 void meet(int owner);
1570 void search(const llvm::DenseSet<int> &drop, ArrayRef<int> targets,
1571 const llvm::DenseSet<int> &off = {});
1572 bool trace(int state);
1573 llvm::DenseSet<int> splitOff(int dst) const;
1574 llvm::DenseSet<int> trunkOff(int dst) const;
1575 llvm::Error placePinned();
1576 llvm::Error grow();
1577 void reroute();
1578 void claim();
1579 bool join(int state, int predId, const Edge &e);
1580 void joinTrees();
1581 void record();
1582
1585 int flow;
1586 const Flow &part;
1587 const llvm::BitVector *avoid;
1588 // The route the flow takes alone, if it is pinned to it.
1589 const std::vector<TreeHop> *pinned = nullptr;
1591 // The states the tree reaches, and how many hops from the source each is.
1592 SmallVector<int, 16> tree, treeHops;
1593 SmallVector<int, 16> seeds;
1594 SmallVector<double, 16> seedCosts;
1595 // The tree's hops, by the state each reaches, from which state and by
1596 // which edge, in the order they were traced. They take effect once the
1597 // tree is final.
1598 llvm::MapVector<int, std::pair<int, Edge>> planned;
1599 llvm::DenseMap<int, int> children;
1600 // A branch off a port the tree already crosses joins that port's unit
1601 // (see planArbiters), so it avoids the flows conflicting with any flow
1602 // on those arbiters too.
1603 llvm::DenseMap<int, llvm::BitVector> branchAvoid;
1604 SmallVector<PathEndPoint, 4> pending;
1605 bool toSelf = false;
1606 // The destination to reach first, if not the nearest.
1607 std::optional<PathEndPoint> first;
1608 // A switchbox routes on the id alone, so packets that reach a master
1609 // port another source's tree takes an id they share by go wherever
1610 // that id goes from there. The flow may join the tree there only if
1611 // it still has to reach each of those destinations, with just the ids
1612 // they share.
1613 llvm::DenseMap<int, SmallVector<int, 4>> joins;
1614 llvm::DenseMap<int, SmallVector<int, 2>> joinOwners;
1615 llvm::DenseSet<int> stops, unjoinable;
1616 // The destinations the flow still has to reach that each other source's
1617 // tree reaches with the ids they share, less the trees it may not join.
1618 llvm::MapVector<int, SmallVector<int, 4>> sharedDsts;
1619 // The destinations it shares with trees it could meet but for the other
1620 // ids those trees carry.
1621 llvm::MapVector<int, SmallVector<int, 4>> blockedDsts;
1622 // The destinations it shares with trees with other ids it could meet but
1623 // for its own ids that go elsewhere, and those ids.
1624 llvm::MapVector<int, std::pair<SmallVector<int, 4>, std::set<int>>>
1626 llvm::DenseSet<int> disagree, foreign;
1627 // The destinations the flow reaches where it meets another tree.
1628 SmallVector<int, 4> met;
1629 // The master ports the source's other parts take at the tiles the flow
1630 // was split apart from them at.
1631 llvm::DenseSet<int> partOff;
1632 // The destinations the flow reaches by one master port out of its source
1633 // switchbox (see RouteState::trunked).
1634 llvm::DenseSet<int> trunkDsts;
1635 SmallVector<int, 4> reached;
1636 SmallVector<std::pair<int, const SmallVector<int, 4> *>, 2> joinedAt;
1637 SmallVector<std::pair<int, std::pair<int, Edge>>, 8> pinnedJoins;
1638 SmallVector<int, 4> pinnedJoinDsts;
1639};
1640
1642 : pf(pf), st(st), flow(flow), part(st.parts[flow]),
1643 avoid(part.packetId ? &st.conflicting[flow] : nullptr) {
1644 if (st.isPinned(part))
1645 pinned = &pf.constraints.pinned.at(part.src);
1646 // The flow source port feeds into its switchbox, so the tree starts
1647 // on its In side and the first edge taken is necessarily a crossbar
1648 // hop.
1649 int srcId = pf.nodeIds.at(part.src);
1650 tree.push_back(stateId(srcId, In));
1651 treeHops.push_back(0);
1652 st.processedStamp[tree.front()] = ++st.curStamp;
1653 for (const PathEndPoint &endPoint : part.dsts) {
1654 // Route to self: the port is both ends. Where its switchbox cannot
1655 // connect it to itself (Core to Core), the stream has to leave and
1656 // come back, which Dijkstra finds from the In side to the Out side.
1657 // A tree the flow joins may reach the port for it instead. A port in
1658 // priorityMasters is reached like any other destination, so mayLeave
1659 // still holds.
1660 int self = stateId(srcId, Out);
1661 if (endPoint == part.src && !st.priorityMasters.count(self) &&
1662 llvm::any_of(pf.adjacency[srcId],
1663 [&](const Edge &e) { return e.dst == srcId; })) {
1664 toSelf = true;
1665 continue;
1666 }
1667 pending.push_back(endPoint);
1668 }
1669 findJoins();
1670 for (auto it = st.trunked.lower_bound({flow, 0});
1671 !st.untrunked.count(part.src) && it != st.trunked.end() &&
1672 it->first == flow;
1673 ++it) {
1674 SmallVector<int, 4> shared;
1675 for (const PathEndPoint &dst : st.parts[it->second].dsts)
1676 if (llvm::is_contained(part.dsts, dst))
1677 shared.push_back(dstState(dst));
1678 if (shared.size() > 1)
1679 trunkDsts.insert(shared.begin(), shared.end());
1680 }
1681 for (auto [at, other] : st.partSplits[flow])
1682 for (const auto &[state, _] : st.treeOf[other])
1683 if ((state & 1) == Out && pf.nodes[stateNode(state)].coords == at)
1684 partOff.insert(state);
1685}
1686
1688 return (toSelf && state == dstState(part.src)) ||
1689 llvm::any_of(pending, [&](const PathEndPoint &p) {
1690 return dstState(p) == state;
1691 });
1692}
1693
1694void Pathfinder::TreeBuilder::reach(ArrayRef<int> dsts) {
1695 llvm::erase_if(pending, [&](const PathEndPoint &p) {
1696 return llvm::is_contained(dsts, dstState(p));
1697 });
1698 if (llvm::is_contained(dsts, dstState(part.src)))
1699 toSelf = false;
1700}
1701
1702bool Pathfinder::TreeBuilder::joinable(int at, ArrayRef<int> dsts) const {
1703 return !unjoinable.count(at) &&
1704 llvm::all_of(dsts, [&](int dst) { return isPending(dst); });
1705}
1706
1708 auto shared = [&](ArrayRef<int> ids, int other) {
1709 std::set<int> common;
1710 for (int id : ids)
1711 if (st.flowIds[other].count(id))
1712 common.insert(id);
1713 return common;
1714 };
1715 for (int other : st.sameId[flow]) {
1716 // A tree reaching its own source port takes no hop for it.
1717 const Flow &o = st.parts[other];
1718 int self = dstState(o.src);
1719 if (!st.treeDsts[other].empty() && llvm::is_contained(o.dsts, o.src) &&
1720 isPending(self) && !shared(st.idsTo(other, self), flow).empty())
1721 sharedDsts[other].push_back(self);
1722 for (int dst : st.treeDsts[other]) {
1723 std::set<int> common = shared(st.idsTo(other, dst), flow);
1724 if (common.empty())
1725 continue;
1726 // Joining shares the other flow's arbiters below the join with the
1727 // packets it takes there. A prioritized flow's tree is pinned, so it
1728 // joins only trees pinned with it. A destination of the other flow alone
1729 // keeps the flow off the hops toward it, as no join there is joinable.
1730 bool canJoin =
1731 (!isPending(dst) || common == shared(st.idsTo(flow, dst), other)) &&
1732 !st.noJoin.count({flow, other}) &&
1733 (!part.isPriorityFlow || st.parts[other].isPriorityFlow);
1734 bool agree = canJoin && !(pf.constraints.conflict &&
1735 pf.constraints.conflict(part.src, common, o.src,
1736 st.flowIds[other]));
1737 if (!agree)
1738 disagree.insert(other);
1739 else if (isPending(dst))
1740 sharedDsts[other].push_back(dst);
1741 // Only the conflict kept it from joining, and only the ids it shares
1742 // with the tree are left to conflict if those leave apart.
1743 if (canJoin && !agree && isPending(dst) &&
1744 !pf.constraints.conflict(part.src, common, o.src, common))
1745 blockedDsts[other].push_back(dst);
1746 for (auto it = st.treeOf[other].find(dst); it != st.treeOf[other].end();
1747 it = st.treeOf[other].find(it->second.first)) {
1748 int up = it->second.first;
1749 if ((up & 1) != Out)
1750 continue;
1751 stops.insert(up);
1752 if (!agree)
1753 unjoinable.insert(up);
1754 if (!llvm::is_contained(joins[up], dst))
1755 joins[up].push_back(dst);
1756 if (!llvm::is_contained(joinOwners[up], other))
1757 joinOwners[up].push_back(other);
1758 }
1759 }
1760 }
1761 // A tree with other ids reaching two of the flow's destinations is met the
1762 // same way, the flow taking its hops below the meeting with its own ids.
1763 // Not for a destination a tree with one of its ids also reaches, which the
1764 // flow has to meet on the way there instead; after meetAhead, only a tree
1765 // routed already, as one routed later meets the flow's tree and so this one.
1766 if (!part.packetId || part.isPriorityFlow)
1767 return;
1768 llvm::DenseSet<int> sameIdDsts;
1769 for (int other : st.sameId[flow]) {
1770 if (pf.consult(Relax::MeetAheadOfPartners) && st.treeDsts[other].empty())
1771 continue;
1772 for (const PathEndPoint &dst : st.parts[other].dsts)
1773 if (!shared(st.idsTo(other, dstState(dst)), flow).empty())
1774 sameIdDsts.insert(dstState(dst));
1775 }
1776 for (auto [other, o] : llvm::enumerate(st.parts)) {
1777 int k = other;
1778 if (k == flow || o.src == part.src || !o.packetId || o.isPriorityFlow ||
1779 st.treeDsts[k].empty() || llvm::is_contained(st.sameId[flow], k) ||
1780 st.noJoin.count({flow, k}))
1781 continue;
1782 SmallVector<int, 4> dsts;
1783 for (int dst : st.treeDsts[k])
1784 if (isPending(dst) && !sameIdDsts.count(dst) && st.treeOf[k].count(dst))
1785 dsts.push_back(dst);
1786 if (dsts.size() < 2)
1787 continue;
1788 if (!st.conflicting[flow].test(k)) {
1789 sharedDsts[k] = std::move(dsts);
1790 foreign.insert(k);
1791 continue;
1792 }
1793 // Where only ids the flow sends elsewhere conflict with the tree, those
1794 // can leave as a part of their own and the rest meet it.
1795 std::set<int> meeting, rest;
1796 for (int dst : dsts)
1797 for (int id : st.idsTo(flow, dst))
1798 meeting.insert(id);
1799 for (int id : st.flowIds[flow])
1800 if (!meeting.count(id))
1801 rest.insert(id);
1802 if (!rest.empty() && pf.constraints.conflict &&
1803 !st.apartSources.count(std::minmax(part.src, o.src)) &&
1804 !pf.constraints.conflict(part.src, meeting, o.src, st.flowIds[k]))
1805 blockedIds[k] = {std::move(dsts), std::move(rest)};
1806 }
1807}
1808
1809// Trees from two sources wait on each other wherever they meet (see HoldCycle),
1810// so two trees meeting at two switchboxes can each hold one arbiter and wait at
1811// the other. The flow meets each tree it shares destinations with at one
1812// switchbox, those it shares the most with first, on that tree's way from its
1813// source to where it branches for them, by a slave port that takes each master
1814// port the tree takes there toward them. Only a packet going to two of them can
1815// hold the arbiter where the trees meet for one and wait where they meet for
1816// the other, so two trees meet only when each sends some id to two shared
1817// destinations.
1819 if (pf.consult(Relax::MeetApart))
1820 return;
1821 auto spans = [&](int k, ArrayRef<int> dsts) {
1822 return llvm::any_of(st.flowIds[k], [&](int id) {
1823 return llvm::count_if(dsts, [&](int dst) {
1824 return llvm::is_contained(st.idsTo(k, dst), id);
1825 }) > 1;
1826 });
1827 };
1828 auto mustMeet = [&](int other) {
1829 return spans(flow, sharedDsts[other]) && spans(other, sharedDsts[other]);
1830 };
1831 // A tree it has to meet but for the other ids it carries leaves those ids to
1832 // a part of their own, which findPaths splits off once the iteration ends.
1833 for (const auto &[other, dsts] : blockedDsts)
1834 if (spans(flow, dsts) && spans(other, dsts))
1835 st.meetBlocked.insert({part.src, st.parts[other].src});
1836 for (const auto &[other, blocked] : blockedIds)
1837 if (spans(flow, blocked.first) && spans(other, blocked.first))
1838 st.meetSplits.insert({{part.src, st.parts[other].src}, blocked.second});
1839 SmallVector<int, 4> owners;
1840 for (int other : llvm::make_first_range(sharedDsts))
1841 if (!disagree.count(other) && mustMeet(other))
1842 owners.push_back(other);
1843 llvm::stable_sort(owners, [&](int a, int b) {
1844 return sharedDsts[a].size() > sharedDsts[b].size();
1845 });
1846 for (int owner : owners) {
1847 llvm::erase_if(sharedDsts[owner], [&](int dst) { return !isPending(dst); });
1848 if (mustMeet(owner))
1849 meet(owner);
1850 }
1851}
1852
1854 st.unmet.insert({flow, owner});
1855 pf.treesMet = true;
1856 bool other = foreign.count(owner);
1857 const auto &t = st.treeOf[owner];
1858 const Flow &o = st.parts[owner];
1859 int root = stateId(pf.nodeIds.at(o.src), In);
1860 // The owner's states from its source down to each shared destination.
1861 SmallVector<SmallVector<int, 16>, 4> paths;
1862 for (int dst : sharedDsts[owner]) {
1863 SmallVector<int, 16> &path = paths.emplace_back(1, dst);
1864 for (auto it = t.find(dst); it != t.end(); it = t.find(it->second.first))
1865 path.push_back(it->second.first);
1866 if (path.size() == 1)
1867 path.push_back(root);
1868 if (path.back() != root)
1869 return;
1870 std::reverse(path.begin(), path.end());
1871 }
1872 size_t trunk = 0;
1873 while (llvm::all_of(paths, [&](const auto &path) {
1874 return trunk + 1 < path.size() && path[trunk] == paths[0][trunk];
1875 }))
1876 trunk++;
1877 struct Meeting {
1878 int in;
1879 SmallVector<std::pair<int, Edge>, 4> hops;
1880 double cost;
1881 size_t at;
1882 };
1883 SmallVector<Meeting, 8> meetings;
1884 SmallVector<int, 8> targets;
1885 // Below a meeting with other ids the flow takes the owner's hops itself.
1886 auto below = [&](size_t k) {
1887 llvm::MapVector<int, std::pair<int, Edge>> hops;
1888 for (const auto &path : paths)
1889 for (size_t l = k + 1; l + 1 < path.size(); l++)
1890 hops.insert({path[l + 1], t.find(path[l + 1])->second});
1891 return hops;
1892 };
1893 for (size_t k = 0; k < trunk; k++) {
1894 int at = paths[0][k];
1895 if ((at & 1) != In)
1896 continue;
1897 SetVector<int> next;
1898 for (const auto &path : paths)
1899 next.insert(path[k + 1]);
1900 if (!other && llvm::any_of(next, [&](int s) {
1901 return !isPending(s) && !(joins.count(s) && joinable(s, joins[s]));
1902 }))
1903 continue;
1904 auto taken = [&](int s) {
1905 return st.processedStamp[s] == st.curStamp || stops.count(s) ||
1906 partOff.count(s);
1907 };
1908 if (other && (llvm::any_of(next, taken) ||
1909 llvm::any_of(below(k), [&](const auto &hop) {
1910 const Edge &e = hop.second.second;
1911 return taken(hop.first) ||
1912 (e.sb->srcCoords == e.sb->dstCoords &&
1913 e.sb->circuitOnlyDst[e.j]);
1914 })))
1915 continue;
1916 SmallVector<int, 4> leaving;
1917 if (llvm::any_of(next, [&](int s) {
1918 bool ok = st.mayLeave(leaving, s);
1919 leaving.push_back(s);
1920 return !ok;
1921 }))
1922 continue;
1923 TileID tile = pf.nodes[stateNode(at)].coords;
1924 auto sb = pf.graph.find({tile, tile});
1925 if (sb == pf.graph.end())
1926 continue;
1927 for (Port port : sb->second.srcPorts) {
1928 auto node = pf.nodeIds.find({tile, port});
1929 if (node == pf.nodeIds.end())
1930 continue;
1931 int in = stateId(node->second, In);
1932 auto taken = st.meetingPorts.find({owner, in});
1933 if (in == at || t.count(in) ||
1934 (taken != st.meetingPorts.end() && !(taken->second == part.src)))
1935 continue;
1936 Meeting m{in, {}, 0, k};
1937 for (int s : next)
1938 for (const Edge &e : pf.adjacency[node->second])
1939 if (e.dst == stateNode(s) && e.sb == &sb->second &&
1940 !(part.packetId && e.sb->circuitOnlyDst[e.j])) {
1941 m.hops.push_back({s, e});
1942 m.cost += pf.edgeWeight(e, part.packetId, avoid, nullptr);
1943 break;
1944 }
1945 if (m.hops.size() == next.size()) {
1946 meetings.push_back(std::move(m));
1947 targets.push_back(in);
1948 }
1949 }
1950 }
1951 if (meetings.empty())
1952 return;
1953 llvm::DenseSet<int> off;
1954 if (other)
1955 for (const auto &[s, _] : below(0))
1956 off.insert(s);
1957 search({}, targets, off);
1958 const Meeting *best = nullptr;
1959 for (const Meeting &m : meetings)
1960 if (pf.distance[m.in] < INF &&
1961 (!best ||
1962 pf.distance[m.in] + m.cost < pf.distance[best->in] + best->cost))
1963 best = &m;
1964 if (!best || !trace(best->in))
1965 return;
1966 st.unmet.erase({flow, owner});
1967 st.meetingPorts.try_emplace({owner, best->in}, part.src);
1968 st.met.insert({flow, owner});
1969 int hops = treeHops[llvm::find(tree, best->in) - tree.begin()] + 1;
1970 auto add = [&](int s, int from, const Edge &e, int depth) {
1971 planned.insert({s, {from, e}});
1972 ++children[from];
1973 st.processedStamp[s] = st.curStamp;
1974 tree.push_back(s);
1975 treeHops.push_back(depth);
1976 };
1977 for (const auto &[s, e] : best->hops) {
1978 add(s, best->in, e, hops);
1979 if (other) {
1980 st.joinedHops[flow].push_back({owner, e});
1981 continue;
1982 }
1983 if (isPending(s)) {
1984 met.push_back(s);
1985 reach(s);
1986 continue;
1987 }
1988 const SmallVector<int, 4> &dsts = joins[s];
1989 reach(dsts);
1990 joinedAt.push_back({s, &dsts});
1991 ++children[s];
1992 }
1993 if (!other)
1994 return;
1995 for (const auto &[s, hop] : below(best->at)) {
1996 const auto &[from, e] = hop;
1997 add(s, from, e, treeHops[llvm::find(tree, from) - tree.begin()] + 1);
1998 st.joinedHops[flow].push_back({owner, e});
1999 }
2000 for (int dst : sharedDsts[owner]) {
2001 met.push_back(dst);
2002 reach(dst);
2003 }
2004}
2005
2006// Dijkstra from the tree, less the states in `drop`, and not through
2007// those in `off`, until the states in `targets` are settled.
2008void Pathfinder::TreeBuilder::search(const llvm::DenseSet<int> &drop,
2009 ArrayRef<int> targets,
2010 const llvm::DenseSet<int> &off) {
2011 branchAvoid.clear();
2012 llvm::DenseMap<int, llvm::BitVector> onArbiter;
2013 if (avoid)
2014 for (const auto &[state, hop] : planned) {
2015 const auto &[from, e] = hop;
2016 if (e.sb->srcCoords != e.sb->dstCoords || drop.count(state))
2017 continue;
2018 llvm::BitVector &away =
2019 branchAvoid.try_emplace(from, st.conflicting.size()).first->second;
2020 llvm::BitVector &on =
2021 onArbiter.try_emplace(from, st.conflicting.size()).first->second;
2022 for (int other : e.sb->unitFlows(e.j)) {
2023 on.set(other);
2024 if (other != flow)
2025 away |= st.conflicting[other];
2026 }
2027 }
2028 // A flow sharing an arbiter with itself is no conflict, and flows
2029 // already on those arbiters share them whatever the branch does.
2030 for (auto &[from, away] : branchAvoid) {
2031 away.reset(onArbiter.find(from)->second);
2032 away.reset(flow);
2033 }
2034 seeds.clear();
2035 seedCosts.clear();
2036 for (auto [state, hops] : llvm::zip_equal(tree, treeHops))
2037 if (!drop.count(state) && !off.count(state)) {
2038 seeds.push_back(state);
2039 seedCosts.push_back(treeSeedFactor * hops);
2040 }
2041 llvm::DenseSet<int> blocked;
2042 if (!off.empty()) {
2043 blocked = stops;
2044 blocked.insert(off.begin(), off.end());
2045 }
2046 llvm::DenseMap<int, SmallVector<int, 4>> masters;
2047 bool limited = !st.priorityMasters.empty();
2048 if (limited)
2049 for (const auto &[state, hop] : planned)
2050 if ((hop.first & 1) == In && !drop.count(state))
2051 masters[hop.first].push_back(state);
2052 auto mayCross = [&](int from, int to) {
2053 auto it = masters.find(from);
2054 return st.mayLeave(it == masters.end() ? ArrayRef<int>{} : it->second, to);
2055 };
2056 pf.dijkstraShortestPaths(
2057 seeds, seedCosts, part.packetId, avoid, &branchAvoid,
2058 off.empty() ? &stops : &blocked, targets,
2059 limited ? llvm::function_ref<bool(int, int)>(mayCross) : nullptr);
2060}
2061
2062// Trace the path Dijkstra found to `state` back to the tree.
2064 size_t grown = tree.size();
2065 while (st.processedStamp[state] != st.curStamp) {
2066 // If Dijkstra never reached this node it has no predecessor; the
2067 // destination is unroutable under the current demand.
2068 int pred = pf.preds[state];
2069 if (pred < 0)
2070 return false;
2071 planned.insert({state, {pred, pf.predEdge[state]}});
2072 ++children[pred];
2073 st.processedStamp[state] = st.curStamp;
2074 tree.push_back(state);
2075 state = pred;
2076 }
2077 // The new hops were traced from the destination back to the tree.
2078 int hops = treeHops[llvm::find(tree, state) - tree.begin()] +
2079 static_cast<int>(tree.size() - grown);
2080 while (treeHops.size() < tree.size())
2081 treeHops.push_back(hops--);
2082 return true;
2083}
2084
2085// The path to `dst` stays off the hops another destination's path
2086// takes below where the check split the two apart, and off the
2087// slave port it takes there too if one of them has to reach the tile
2088// on its own.
2089llvm::DenseSet<int> Pathfinder::TreeBuilder::splitOff(int dst) const {
2090 llvm::DenseSet<int> off = partOff;
2091 auto carries = [&](int d, int id) {
2092 return llvm::is_contained(st.idsTo(flow, d), id);
2093 };
2094 auto only = [&](int d, int id, int other) {
2095 return carries(d, id) && !carries(d, other);
2096 };
2097 for (auto [at, a, b, apart] : st.splitsOf[flow])
2098 for (int other : reached) {
2099 bool splits = !apart ? (only(dst, a, b) && only(other, b, a)) ||
2100 (only(dst, b, a) && only(other, a, b))
2101 : (only(dst, a, b) && other == *apart) ||
2102 (dst == *apart && only(other, a, b));
2103 if (!splits)
2104 continue;
2105 SmallVector<int, 8> below;
2106 int s = other;
2107 auto entersAt = [&, tile = at](int state) {
2108 return (state & 1) == In && pf.nodes[stateNode(state)].coords == tile;
2109 };
2110 for (auto *hop = planned.find(s); !entersAt(s) && hop != planned.end();
2111 hop = planned.find(s)) {
2112 below.push_back(s);
2113 s = hop->second.first;
2114 }
2115 if (!entersAt(s))
2116 continue;
2117 off.insert(below.begin(), below.end());
2118 if (apart)
2119 off.insert(s);
2120 }
2121 return off;
2122}
2123
2124// The path to a trunked destination leaves the tree below the master port
2125// the others it has reached leave the source switchbox by.
2126llvm::DenseSet<int> Pathfinder::TreeBuilder::trunkOff(int dst) const {
2127 llvm::DenseSet<int> off;
2128 if (!trunkDsts.count(dst))
2129 return off;
2130 int root = tree.front();
2131 auto exitOf = [&](int s) {
2132 for (const auto *it = planned.find(s);
2133 it != planned.end() && it->second.first != root; it = planned.find(s))
2134 s = it->second.first;
2135 return s;
2136 };
2137 const auto *other = llvm::find_if(reached, [&](int d) {
2138 return d != dst && trunkDsts.count(d) && planned.count(d);
2139 });
2140 if (other == reached.end())
2141 return off;
2142 int exit = exitOf(*other);
2143 for (int s : tree)
2144 if (s == root || exitOf(s) != exit)
2145 off.insert(s);
2146 return off;
2147}
2148
2149// Lay the tree along the route the flow takes alone.
2151 for (const auto &[from, to, joined] : *pinned) {
2152 if (toSelf && from == to)
2153 continue;
2154 bool intra = from.coords == to.coords;
2155 auto fromId = pf.nodeIds.find(from), toId = pf.nodeIds.find(to);
2156 const Edge *e = nullptr;
2157 if (fromId != pf.nodeIds.end() && toId != pf.nodeIds.end())
2158 for (const Edge &out : pf.adjacency[fromId->second])
2159 if (out.dst == toId->second &&
2160 (out.sb->srcCoords == out.sb->dstCoords) == intra)
2161 e = &out;
2162 if (!e)
2163 return llvm::make_error<RoutingFailure>(
2164 "the route packet flows from " +
2165 describeTilePort(part.src.coords, part.src.port) +
2166 " take alone does not fit this design: it goes from " +
2167 describeTilePort(from.coords, from.port) + " to " +
2168 describeTilePort(to.coords, to.port) +
2169 ", which the design's own switchboxes leave no connection for.",
2170 RoutingFaults{}, pf.flowLoc(part.src, nullptr));
2171 std::pair<int, std::pair<int, Edge>> hop{
2172 stateId(toId->second, intra ? Out : In),
2173 {stateId(fromId->second, intra ? In : Out), *e}};
2174 if (joined)
2175 pinnedJoins.push_back(hop);
2176 else
2177 planned.insert(hop);
2178 }
2179 int self = dstState(part.src);
2180 if (toSelf && llvm::is_contained(llvm::make_first_range(pinnedJoins), self)) {
2181 toSelf = false;
2182 pinnedJoinDsts.push_back(self);
2183 }
2184 for (const PathEndPoint &p : pending)
2185 (planned.count(dstState(p)) ? reached : pinnedJoinDsts)
2186 .push_back(dstState(p));
2187 pending.clear();
2188 return llvm::Error::success();
2189}
2190
2191// Grow the tree one destination at a time: Dijkstra, given the current
2192// demand, from everything the tree reaches so far to the next destination,
2193// whose path is then traced back to the tree. Growing from the tree rather
2194// than the source lets destinations share hops; see treeSeedFactor for what
2195// a branch off the tree costs.
2197 // A path to another tree can leave the destination to reach first no way
2198 // to it, so the tree meets the others once it reaches it.
2199 bool metTrees = !first || !llvm::is_contained(pending, *first);
2200 if (metTrees)
2201 meet();
2202 while (!pending.empty()) {
2203 SmallVector<int, 8> targets;
2204 for (const PathEndPoint &p : pending)
2205 targets.push_back(dstState(p));
2206 for (const auto &[at, dsts] : joins)
2207 if (joinable(at, dsts))
2208 targets.push_back(at);
2209 search({}, targets);
2210 // The nearest destination joins the tree next, or the nearest join
2211 // brings every destination below it.
2212 auto *nearest =
2213 first && llvm::is_contained(pending, *first)
2214 ? llvm::find(pending, *first)
2215 : llvm::min_element(
2216 pending, [&](const PathEndPoint &a, const PathEndPoint &b) {
2217 return pf.distance[dstState(a)] < pf.distance[dstState(b)];
2218 });
2219 PathEndPoint endPoint = *nearest;
2220 int currId = dstState(endPoint);
2221 llvm::DenseSet<int> off = splitOff(currId);
2222 llvm::DenseSet<int> trunk = trunkOff(currId);
2223 off.insert(trunk.begin(), trunk.end());
2224 if (!off.empty()) {
2225 search({}, targets, off);
2226 if (pf.distance[currId] == INF)
2227 search({}, targets);
2228 }
2229 const SmallVector<int, 4> *joined = nullptr;
2230 for (const auto &[at, dsts] : joins)
2231 if (pf.distance[at] < pf.distance[currId] && joinable(at, dsts)) {
2232 currId = at;
2233 joined = &dsts;
2234 }
2235 if (joined) {
2236 reach(*joined);
2237 joinedAt.push_back({currId, joined});
2238 // The tree it joins goes on below.
2239 ++children[currId];
2240 } else {
2241 pending.erase(nearest);
2242 reached.push_back(currId);
2243 }
2244 if (!trace(currId))
2245 return llvm::make_error<RoutingFailure>(
2246 "no path leads from " +
2247 describeTilePort(part.src.coords, part.src.port) + " to " +
2248 describeTilePort(endPoint.coords, endPoint.port) +
2249 " through the connections the switchboxes allow and existing "
2250 "routing leaves free.",
2251 RoutingFaults{}, pf.flowLoc(part.src, &endPoint));
2252 if (!metTrees) {
2253 metTrees = true;
2254 meet();
2255 }
2256 }
2257 return llvm::Error::success();
2258}
2259
2260// A destination's path was chosen before the tree reached the later
2261// ones, so reroute each destination's own branch from the rest of the
2262// tree where that is cheaper.
2264 for (int dst : reached) {
2265 llvm::DenseSet<int> branch;
2266 int top = dst;
2267 for (int below = 0; top != tree.front() && children.lookup(top) == below;
2268 below = 1) {
2269 branch.insert(top);
2270 top = planned.find(top)->second.first;
2271 }
2272 if (branch.empty())
2273 continue;
2274 llvm::DenseSet<int> off = splitOff(dst), trunk = trunkOff(dst);
2275 off.insert(trunk.begin(), trunk.end());
2276 search(branch, dst, off);
2277 double cost =
2278 treeSeedFactor * treeHops[llvm::find(tree, top) - tree.begin()];
2279 for (int s = dst; s != top;) {
2280 const auto &[from, e] = planned.find(s)->second;
2281 auto away = branchAvoid.find(from);
2282 cost +=
2283 pf.edgeWeight(e, part.packetId, avoid,
2284 away == branchAvoid.end() ? nullptr : &away->second);
2285 s = from;
2286 }
2287 if (pf.distance[dst] + rerouteMinSaving >= cost)
2288 continue;
2289 for (int s : branch) {
2290 st.processedStamp[s] = 0;
2291 planned.erase(s);
2292 children.erase(s);
2293 }
2294 --children[top];
2295 for (size_t k = tree.size(); k-- > 0;)
2296 if (branch.count(tree[k])) {
2297 tree.erase(tree.begin() + k);
2298 treeHops.erase(treeHops.begin() + k);
2299 }
2300 [[maybe_unused]] bool traced = trace(dst);
2301 assert(traced && "a rerouted branch reaches its destination");
2302 }
2303}
2304
2305// Take the channels the tree's hops cross.
2307 if (toSelf) {
2308 switchSettings[part.src.coords].srcs.push_back(part.src.port);
2309 switchSettings[part.src.coords].dsts.push_back(part.src.port);
2310 if (part.packetId) {
2311 st.routing.packetTrees[part.src].push_back({part.src, part.src, false});
2312 // On the tree too, so a tree that has to meet this one finds the port.
2313 int srcId = pf.nodeIds.at(part.src);
2314 for (const Edge &e : ArrayRef<Edge>(pf.adjacency[srcId])
2315 .take_front(pf.wireEdgesBegin[srcId]))
2316 if (e.dst == srcId) {
2317 st.treeOf[flow].try_emplace(dstState(part.src), tree.front(), e);
2318 st.treeDsts[flow].push_back(dstState(part.src));
2319 break;
2320 }
2321 }
2322 }
2323 const std::optional<int> &packetId = part.packetId;
2324 int packetGroupId = part.packetGroupId;
2325 llvm::DenseMap<int, std::pair<SwitchboxConnect *, int>> branchPort;
2326 for (const auto &[currId, hop] : planned) {
2327 const auto &[predId, e] = hop;
2328 const PathEndPoint &curr = pf.nodes[stateNode(currId)];
2329 const PathEndPoint &pred = pf.nodes[stateNode(predId)];
2330 SwitchboxConnect &sb = *e.sb;
2331 int i = e.i;
2332 int j = e.j;
2333 SwitchboxConnect::Cell &cell = sb.at(i, j);
2334 if (packetId)
2335 st.treeOf[flow].try_emplace(currId, predId, e);
2336 else
2337 st.circuitHops[flow].push_back(e);
2338 cell.isPriority |= part.isPriorityFlow;
2339 // Two trees with the same id may merge onto one only where nothing fans out
2340 // after, or where both take the id to the same destinations, so a merged id
2341 // never fans back out to one tree's destinations alone. The flow's own tree
2342 // branching at a port never merges back.
2343 // packetGroupId only becomes >= 0 when packetId has a value (see
2344 // Pathfinder::addFlow), so the dereferences below are safe; the
2345 // checker just can't correlate the two across this loop's back edge.
2346 // NOLINTBEGIN(bugprone-unchecked-optional-access)
2347 auto seen =
2348 packetId ? cell.packetIds.find(*packetId) : cell.packetIds.end();
2349 auto mergeable = [&] {
2350 if (!isDirectional(sb.dstPorts[j].bundle))
2351 return true;
2352 auto reached = [&](const Flow &f) {
2353 std::set<PathEndPoint> dsts;
2354 for (const PathEndPoint &dst : f.dsts)
2355 if (auto ids = pf.packetIdsTo.find({f.src, dst});
2356 ids != pf.packetIdsTo.end() &&
2357 llvm::is_contained(ids->second, *packetId))
2358 dsts.insert(dst);
2359 return dsts;
2360 };
2361 return reached(part) == reached(st.parts[seen->second]);
2362 };
2363 bool sameGroupUnseen =
2364 packetGroupId >= 0 && packetId.has_value() &&
2365 (cell.packetGroupId == -1 || cell.packetGroupId == packetGroupId) &&
2366 (seen == cell.packetIds.end() || seen->second == flow || mergeable());
2367 if (sameGroupUnseen) {
2368 int packetIdValue = *packetId;
2369 // NOLINTEND(bugprone-unchecked-optional-access)
2370 auto claim = [&](SwitchboxConnect::Cell &c) {
2371 c.packetGroupId = packetGroupId;
2372 c.packetIds.try_emplace(packetIdValue, flow);
2373 };
2374 for (size_t k = 0; k < sb.srcPorts.size(); k++)
2375 claim(sb.at(k, j));
2376 for (size_t l = 0; l < sb.dstPorts.size(); l++)
2377 if (l != static_cast<size_t>(j))
2378 claim(sb.at(i, l));
2379 // maximum packet stream sharing per channel
2380 if (++cell.packetFlowCount >= maxPacketStreamCapacity) {
2381 cell.packetFlowCount = 0;
2382 cell.usedCapacity++;
2383 }
2384 } else {
2385 cell.usedCapacity++;
2386 }
2387 // if at capacity, bump demand to discourage using this Channel
2388 // this means the order matters!
2390 if (pred.coords == curr.coords) {
2391 switchSettings[pred.coords].srcs.push_back(pred.port);
2392 switchSettings[curr.coords].dsts.push_back(curr.port);
2393 if (packetId) {
2394 sb.addToUnit(j, flow);
2395 auto [it, first] = branchPort.try_emplace(predId, &sb, j);
2396 if (!first)
2397 sb.joinUnits(it->second.second, j);
2398 }
2399 }
2400 }
2401 // A flow from a switchbox port (as --aie-split-flow-vias leaves a via, or a
2402 // packet source on a port) takes the wire that port is fed by, and a circuit
2403 // to one the wire it drives, though no hop of its tree crosses them.
2404 auto takeWire = [](SwitchboxConnect &link, int k) {
2405 if (k < 0)
2406 return;
2407 SwitchboxConnect::Cell &c = link.at(k, k);
2408 c.usedCapacity++;
2410 };
2411 // A via's next segment starts where the last one ended, on the wire that
2412 // one already takes. A packet source's parts share its wire, which the first
2413 // takes.
2414 bool takesSource = !packetId || st.partsOf.at(part.src).front() == flow;
2415 if (takesSource && isDirectional(part.src.port.bundle))
2416 for (auto &[ends, link] : pf.graph) {
2417 if (ends.second != part.src.coords || ends.first == ends.second)
2418 continue;
2419 int k = link.dstIndex(part.src.port);
2420 if (k >= 0 && !st.flowDsts.count({ends.first, link.srcPorts[k]}))
2421 takeWire(link, k);
2422 }
2423 for (const PathEndPoint &dst : part.dsts)
2424 if (!packetId && isDirectional(dst.port.bundle)) {
2425 int node = pf.nodeIds.at(dst);
2426 for (const Edge &e : ArrayRef<Edge>(pf.adjacency[node])
2427 .drop_front(pf.wireEdgesBegin[node]))
2428 takeWire(*e.sb, e.i);
2429 }
2430 if (packetId) {
2431 st.treeDsts[flow].append(reached.begin(), reached.end());
2432 st.treeDsts[flow].append(met.begin(), met.end());
2433 for (const auto &[currId, hop] : planned)
2434 st.routing.packetTrees[part.src].push_back(
2435 {pf.nodes[stateNode(hop.first)], pf.nodes[stateNode(currId)], false});
2436 }
2437}
2438
2439// Below a join the flow's packets follow the tree they joined.
2440bool Pathfinder::TreeBuilder::join(int state, int predId, const Edge &e) {
2441 if (!st.treeOf[flow].try_emplace(state, predId, e).second)
2442 return false;
2443 const PathEndPoint &pred = pf.nodes[stateNode(predId)];
2444 const PathEndPoint &curr = pf.nodes[stateNode(state)];
2445 st.routing.packetTrees[part.src].push_back({pred, curr, true});
2446 if (pred.coords == curr.coords) {
2447 switchSettings[pred.coords].srcs.push_back(pred.port);
2448 switchSettings[curr.coords].dsts.push_back(curr.port);
2449 e.sb->addToUnit(e.j, flow);
2450 }
2451 return true;
2452}
2453
2455 for (const auto &[joinAt, joined] : joinedAt) {
2456 for (int other : joinOwners[joinAt]) {
2457 st.joinedHops[flow].push_back(
2458 {other, planned.find(joinAt)->second.second});
2459 for (int dst : *joined) {
2460 const auto &t = st.treeOf[other];
2461 SmallVector<std::pair<int, std::pair<int, Edge>>, 8> path;
2462 auto it = t.find(dst);
2463 for (; it != t.end() && it->first != joinAt;
2464 it = t.find(it->second.first))
2465 path.push_back(*it);
2466 if (it == t.end())
2467 continue;
2468 for (const auto &[state, hop] : path)
2469 if (join(state, hop.first, hop.second))
2470 st.joinedHops[flow].push_back({other, hop.second});
2471 }
2472 }
2473 st.treeDsts[flow].append(joined->begin(), joined->end());
2474 }
2475 for (const auto &[state, hop] : pinnedJoins)
2476 join(state, hop.first, hop.second);
2477 st.treeDsts[flow].append(pinnedJoinDsts.begin(), pinnedJoinDsts.end());
2478}
2479
2480// Add the tree to the routing.
2482 const PathEndPoint &src = part.src;
2483 if (st.partsOf.at(src).size() == 1) {
2484 st.routing.settings[src] = switchSettings;
2485 return;
2486 }
2487 for (int id : st.flowIds[flow])
2488 st.routing.idSettings[{src, id}] = switchSettings;
2489 for (const auto &[tile, setting] : switchSettings) {
2490 SwitchSetting &all = st.routing.settings[src][tile];
2491 for (auto [in, out] : llvm::zip(setting.srcs, setting.dsts))
2492 if (!llvm::is_contained(llvm::zip(all.srcs, all.dsts),
2493 std::make_tuple(in, out))) {
2494 all.srcs.push_back(in);
2495 all.dsts.push_back(out);
2496 }
2497 }
2498}
2499
2500llvm::Error Pathfinder::routePart(RouteState &st, int flow) {
2501 std::optional<TreeBuilder> tree;
2502 tree.emplace(*this, st, flow);
2503 llvm::Error err = tree->pinned ? tree->placePinned() : tree->grow();
2504 // Kept to the prioritized flows' master sets, the branch a tree takes first
2505 // can leave it no way to another destination; each is then tried first.
2506 if (err && !tree->pinned && !st.priorityMasters.empty())
2507 for (const PathEndPoint &dst : st.parts[flow].dsts) {
2508 for (auto *pairs : {&st.unmet, &st.met})
2509 pairs->erase(pairs->lower_bound({flow, 0}),
2510 pairs->lower_bound({flow + 1, 0}));
2511 st.joinedHops[flow].clear();
2512 tree.emplace(*this, st, flow);
2513 tree->first = dst;
2514 if (llvm::Error retry = tree->grow()) {
2515 llvm::consumeError(std::move(retry));
2516 continue;
2517 }
2518 llvm::consumeError(std::move(err));
2519 break;
2520 }
2521 if (err)
2522 return err;
2523 if (!tree->pinned && tree->reached.size() + tree->joinedAt.size() > 1)
2524 tree->reroute();
2525 tree->claim();
2526 tree->joinTrees();
2527 tree->record();
2528 return llvm::Error::success();
2529}
2530
2531int Pathfinder::applyRoutingFaults(RouteState &st, const RoutingFaults &faults,
2532 int &pinnedOnly) {
2533 int illegalEdges = 0;
2534 pinnedOnly = 0;
2535 for (const TreeSplit &split : faults.splits) {
2536 auto src = st.partsOf.find(split.src);
2537 if (src == st.partsOf.end())
2538 continue;
2539 auto partWith = [&](int id) {
2540 for (int k : src->second)
2541 if (st.flowIds[k].count(id))
2542 return k;
2543 return -1;
2544 };
2545 int flow = partWith(split.a), other = partWith(split.b);
2546 if (flow < 0 || other < 0)
2547 continue;
2548 std::optional<int> apart;
2549 if (split.apart) {
2550 auto it = nodeIds.find(*split.apart);
2551 if (it == nodeIds.end())
2552 continue;
2553 apart = stateId(it->second, Out);
2554 }
2555 // Whether a destination taking both ids is reached through the tile.
2556 auto inseparable = [&] {
2557 const Flow &f = st.parts[flow];
2558 for (const PathEndPoint &dst : f.dsts) {
2559 auto ids = packetIdsTo.find({f.src, dst});
2560 if (ids == packetIdsTo.end() ||
2561 !llvm::is_contained(ids->second, split.a) ||
2562 !llvm::is_contained(ids->second, split.b))
2563 continue;
2564 const auto &tree = st.treeOf[flow];
2565 auto it = tree.find(stateId(nodeIds.at(dst), Out));
2566 if (it == tree.end() && dst == f.src && dst.coords == split.at)
2567 return true;
2568 for (; it != tree.end(); it = tree.find(it->second.first)) {
2569 int up = it->second.first;
2570 if ((up & 1) == In && nodes[stateNode(up)].coords == split.at)
2571 return true;
2572 }
2573 }
2574 return false;
2575 };
2576 if (consult(Relax::IdsApart) && flow == other && !split.apart &&
2577 !st.parts[flow].isPriorityFlow && inseparable())
2578 other = st.splitPart(flow, {split.b});
2579 if (flow != other) {
2580 if (st.partSplits[flow].insert({split.at, other}).second) {
2581 illegalEdges++;
2582 st.lessons++;
2583 }
2584 st.partSplits[other].insert({split.at, flow});
2585 } else if (st.splitsOf[flow]
2586 .insert({split.at, split.a, split.b, apart})
2587 .second) {
2588 st.lessons +=
2589 st.splitsTaught.insert({flow, {split.at, split.a, split.b, apart}})
2590 .second;
2591 LLVM_DEBUG(llvm::dbgs()
2592 << "Split ids " << split.a << " and " << split.b << " from "
2593 << describeTilePort(split.src.coords, split.src.port)
2594 << " at tile (" << split.at.col << ", " << split.at.row
2595 << ")\n");
2596 illegalEdges++;
2597 }
2598 }
2599 crowdedTiles.insert(faults.crowded.begin(), faults.crowded.end());
2600 bool related = false;
2601 for (const auto &pair : faults.apart) {
2602 if (!st.apartSources.insert(pair).second)
2603 continue;
2604 related = true;
2605 LLVM_DEBUG(llvm::dbgs()
2606 << "Route apart: "
2607 << describeTilePort(pair.first.coords, pair.first.port)
2608 << " and "
2609 << describeTilePort(pair.second.coords, pair.second.port)
2610 << "\n");
2611 if (consult(Relax::SplitShared))
2612 st.splitOwnIds(pair);
2613 }
2614 for (const auto &pair : faults.together) {
2615 // Trees with one id that share a single receiver wait on each other
2616 // wherever they join above it, so they fan in at that receiver alone.
2617 for (int x : st.partsOf.at(pair.first))
2618 for (int y : st.partsOf.at(pair.second))
2619 if (llvm::is_contained(st.sameId[x], y) &&
2620 llvm::count_if(st.parts[x].dsts, [&](const PathEndPoint &dst) {
2621 return llvm::is_contained(st.parts[y].dsts, dst);
2622 }) < 2) {
2623 st.lessons += st.noJoin.insert({x, y}).second;
2624 st.noJoin.insert({y, x});
2625 }
2626 if (!st.togetherSources.insert(pair).second)
2627 continue;
2628 related = true;
2629 LLVM_DEBUG(llvm::dbgs()
2630 << "Route together: "
2631 << describeTilePort(pair.first.coords, pair.first.port)
2632 << " and "
2633 << describeTilePort(pair.second.coords, pair.second.port)
2634 << "\n");
2635 st.splitOwnIds(pair);
2636 }
2637 if (related) {
2638 illegalEdges++;
2639 st.lessons++;
2640 st.relateParts();
2641 }
2642 for (const PathEndPoint &src : faults.untrunk)
2643 if (st.untrunked.insert(src).second) {
2644 LLVM_DEBUG(llvm::dbgs()
2645 << "Untrunk: " << describeTilePort(src.coords, src.port)
2646 << "\n");
2647 illegalEdges++;
2648 st.lessons++;
2649 }
2650 std::set<std::pair<int, int>> faulted;
2651 bool unjoined = false;
2652 for (const auto &[tile, conn] : faults.connections) {
2653 illegalEdges++;
2654 auto it = graph.find({tile, tile});
2655 if (it == graph.end())
2656 continue;
2657 SwitchboxConnect &sb = it->second;
2658 int i = sb.srcIndex(conn.src);
2659 int j = sb.dstIndex(conn.dst);
2660 if (i < 0 || j < 0)
2661 continue;
2662 sb.at(i, j).overCapacity += routingCheckPenalty;
2663 auto takes = [&](const Edge &e) {
2664 return e.sb == &sb && e.i == i && e.j == j;
2665 };
2666 bool taken = false, pinnedTakesAll = true;
2667 for (auto [k, part] : llvm::enumerate(st.parts))
2668 if (llvm::any_of(st.circuitHops[k], takes) ||
2669 llvm::any_of(st.treeOf[k], [&](const auto &hop) {
2670 return takes(hop.second.second);
2671 })) {
2672 taken = true;
2673 pinnedTakesAll &= st.isPinned(part);
2674 }
2675 pinnedOnly += taken && pinnedTakesAll;
2676 bool joined = false;
2677 for (auto [flow, hops] : llvm::enumerate(st.joinedHops))
2678 for (const auto &[other, e] : hops)
2679 if (e.sb == &sb && sb.srcPorts[e.i] == conn.src &&
2680 sb.dstPorts[e.j] == conn.dst) {
2681 faulted.insert({static_cast<int>(flow), other});
2682 joined = true;
2683 }
2684 unjoined |= !joined;
2685 }
2686 // Moving the hops neither joined may be enough, so a joined pair is first
2687 // left to their penalties.
2688 for (auto [flow, other] : faulted)
2689 if (unjoined && st.spared.insert({flow, other}).second)
2690 continue;
2691 else if (st.met.count({flow, other}) &&
2692 ++st.meetFaults[{std::min(flow, other), std::max(flow, other)}] <=
2693 maxMeetFaults)
2694 st.reorder(flow, other, /*again=*/true);
2695 else
2696 st.lessons += st.noJoin.insert({flow, other}).second;
2697 return illegalEdges;
2698}
2699
2700// Perform congestion-aware routing for all flows which have been added.
2701// Use Dijkstra's shortest path to find routes, and use "demand" as the
2702// weights. If the routing finds too much congestion, update the demand
2703// weights and repeat the process until a valid solution is found. Returns
2704// the switchbox settings for all flows, or a RoutingFailure if no legal
2705// routing is found after maxIterations.
2706llvm::Expected<Routing> Pathfinder::findPaths(const int maxIterations) {
2707 LLVM_DEBUG(llvm::dbgs() << "\t---Begin Pathfinder::findPaths---\n");
2708 checkReason.clear();
2709 packetsFailed = true;
2710 // Build the dense routing graph once; topology is invariant across
2711 // iterations.
2712 if (!graphBuilt)
2713 buildRoutingGraph();
2714 if (llvm::Error err = cutOverflow()) {
2715 packetsFailed = false;
2716 return std::move(err);
2717 }
2718 crowdedTiles.clear();
2719 consulted = Relax::None;
2720 // initialize all Channel histories to 0
2721 for (auto &[_, sb] : graph) {
2722 if (sb.srcCoords == sb.dstCoords)
2723 for (auto [j, port] : llvm::enumerate(sb.dstPorts))
2724 sb.circuitOnlyDst[j] = cappedTiles.contains(sb.srcCoords) &&
2725 port.channel >= packetFanoutCap &&
2726 isDirectional(port.bundle);
2727 for (SwitchboxConnect::Cell &c : sb.cells) {
2728 c.usedCapacity = 0;
2729 c.overCapacity = 0;
2730 c.isPriority = false;
2731 }
2732 }
2733 if (!attempts)
2734 return negotiate(maxIterations, nullptr);
2735
2736 // Of what a relax step changes, an attempt reads the flows as sortFlows
2737 // left them, the circuit-only ports, and the settings it consults while it
2738 // routes. One that reads all of these as an earlier attempt did, the
2739 // settings only where that one consulted them, routes as it did: the two
2740 // run alike up to the first read that differs, which the earlier one made.
2742 now.flows = flows;
2743 for (const auto &[_, sb] : graph)
2744 now.circuitOnly.push_back(sb.circuitOnlyDst);
2745 now.values = settings;
2746 auto sameFlow = [](const Flow &a, const Flow &b) {
2747 return std::tie(a.packetGroupId, a.isPriorityFlow, a.src, a.dsts,
2748 a.packetId) == std::tie(b.packetGroupId, b.isPriorityFlow,
2749 b.src, b.dsts, b.packetId);
2750 };
2751 auto replays = [&](const PathfinderAttempt &a) {
2752 return llvm::equal(a.flows, now.flows, sameFlow) &&
2753 a.circuitOnly == now.circuitOnly &&
2754 !any((a.values ^ settings) & a.consulted);
2755 };
2756 auto replayed = llvm::find_if(*attempts, replays);
2757 if (replayed != attempts->end() && !clVerifyReplays) {
2758 LLVM_DEBUG(llvm::dbgs() << "\tPathfinder: this attempt replays attempt "
2759 << (replayed - attempts->begin())
2760 << " of the ladder, so it is skipped\n");
2761 ++numReplaysSkipped;
2762 crowdedTiles = replayed->crowdedTiles;
2763 packetsFailed = replayed->packetsFailed;
2764 checkReason = replayed->checkReason;
2765 if (replayed->routing)
2766 return *replayed->routing;
2767 return llvm::Error(replayed->prototype->clone(
2768 replayed->reason, replayed->faults, replayed->loc));
2769 }
2770
2771 llvm::Expected<Routing> found =
2772 negotiate(maxIterations, clVerifyReplays ? &now.trajectory : nullptr);
2773 now.consulted = consulted;
2774 now.crowdedTiles = crowdedTiles;
2775 now.packetsFailed = packetsFailed;
2776 now.checkReason = checkReason;
2777 bool replayable = static_cast<bool>(found);
2778 if (found)
2779 now.routing = *found;
2780 llvm::Error failure =
2781 found ? llvm::Error::success()
2782 : llvm::handleErrors(
2783 found.takeError(),
2784 [&](std::unique_ptr<RoutingFailure> f) -> llvm::Error {
2785 // Reaching this handler already means f is a
2786 // RoutingFailure or a registered subclass of it.
2787 replayable = true;
2788 now.reason = f->reason;
2789 now.faults = f->faults;
2790 now.loc = f->loc;
2791 now.prototype = f->clone(f->reason, f->faults, f->loc);
2792 return llvm::Error(std::move(f));
2793 });
2794 if (replayed != attempts->end()) {
2795 bool sameFailureType =
2796 static_cast<bool>(replayed->prototype) ==
2797 static_cast<bool>(now.prototype) &&
2798 (!now.prototype || replayed->prototype->dynamicClassID() ==
2799 now.prototype->dynamicClassID());
2800 bool same = replayed->trajectory == now.trajectory &&
2801 replayed->routing.has_value() == now.routing.has_value() &&
2802 (!now.routing || hashRouting(*replayed->routing) ==
2803 hashRouting(*now.routing)) &&
2804 sameFailureType && replayed->reason == now.reason &&
2805 replayed->crowdedTiles == now.crowdedTiles &&
2806 replayed->packetsFailed == now.packetsFailed &&
2807 replayed->checkReason == now.checkReason;
2808 if (!same)
2809 llvm::report_fatal_error(llvm::Twine("aie-pathfinder-verify-replays: "
2810 "attempt ") +
2811 llvm::Twine(attempts->size()) +
2812 " does not replay attempt " +
2813 llvm::Twine(replayed - attempts->begin()));
2814 LLVM_DEBUG(llvm::dbgs() << "\tPathfinder: this attempt replays attempt "
2815 << (replayed - attempts->begin())
2816 << " of the ladder, as verified\n");
2817 ++numReplaysVerified;
2818 } else if (replayable) {
2819 attempts->push_back(std::move(now));
2820 }
2821 if (failure)
2822 return std::move(failure);
2823 return found;
2824}
2825
2826llvm::Expected<Routing>
2827Pathfinder::negotiate(const int maxIterations,
2828 std::vector<llvm::hash_code> *trajectory) {
2829 RouteState st(*this);
2830
2831 int iterationCount = -1;
2832 int illegalEdges = 0;
2833 std::optional<Routing> usable;
2834 int usableAt = 0;
2835 int fewestIllegal = std::numeric_limits<int>::max(), sinceFewest = 0;
2836 // Iterations of the current stall that moved circuit trees first.
2837 int reorderedStall = 0;
2838 int priorityFaults = 0;
2839 // Once a routing has fit the fabric, the iterations since the routing check
2840 // last named fewer faults or taught a lesson, overused ones included.
2841 int fewestRejected = std::numeric_limits<int>::max(), sinceFewestRejected = 0;
2842 do {
2843 if (usable && (iterationCount + 1 >= maxIterations ||
2844 iterationCount - usableAt >= maxSteers)) {
2845 LLVM_DEBUG(llvm::dbgs() << "\t\tKeeping the usable routing\n");
2846 return std::move(*usable);
2847 }
2848 // if reach maxIterations, throw an error since no routing can be found;
2849 // so too once the overuse stalls for good, or routing the losing circuit
2850 // trees first has stopped helping
2851 if (++iterationCount >= maxIterations ||
2852 (fewestIllegal > 0 && sinceFewest >= maxOverusedStall) ||
2853 reorderedStall >= maxReorderedStall ||
2854 sinceFewestRejected >= maxRejectedStall) {
2855 LLVM_DEBUG(llvm::dbgs()
2856 << "\t\tPathfinder: giving up after " << iterationCount
2857 << " iterations ("
2858 << (iterationCount >= maxIterations ? "the iteration limit"
2859 : reorderedStall >= maxReorderedStall
2860 ? "circuit trees routed first stopped helping"
2861 : sinceFewestRejected >= maxRejectedStall
2862 ? "the routing check stopped making progress"
2863 : "the overuse stalled")
2864 << ")...unable to find routing for flows.\n");
2865 // Packet streams took part if they share a switchbox or link with an
2866 // overused channel, or cross a boundary one does: a channel they take
2867 // across it is one fewer for the rest.
2868 auto overused = [](const SwitchboxConnect::Cell &c) {
2869 return c.usedCapacity > maxCircuitStreamCapacity;
2870 };
2871 auto packets = [](const SwitchboxConnect::Cell &c) {
2872 return c.packetGroupId >= 0;
2873 };
2874 std::set<std::tuple<bool, int, bool>> full;
2875 for (const auto &[ends, sb] : graph)
2876 if (ends.first != ends.second && llvm::any_of(sb.cells, overused))
2877 full.insert(boundaryOf(ends.first, ends.second));
2878 packetsFailed =
2879 !checkReason.empty() || llvm::any_of(graph, [&](const auto &entry) {
2880 const auto &[ends, sb] = entry;
2881 return llvm::any_of(sb.cells, packets) &&
2882 (llvm::any_of(sb.cells, overused) ||
2883 (ends.first != ends.second &&
2884 full.count(boundaryOf(ends.first, ends.second))));
2885 });
2886 return explainNoRouting(st);
2887 }
2888
2889 LLVM_DEBUG(llvm::dbgs() << "\t\t---Begin findPaths iteration #"
2890 << iterationCount << "---\n");
2891 // update demand at the beginning of each iteration
2892 for (auto &[_, sb] : graph) {
2893 sb.updateDemand();
2894 }
2895
2896 // "rip up" all routes
2897 illegalEdges = 0;
2898 st.routing = {};
2899 for (auto &[_, sb] : graph) {
2900 for (SwitchboxConnect::Cell &c : sb.cells) {
2901 c.usedCapacity = 0;
2902 c.packetFlowCount = 0;
2903 c.packetGroupId = -1;
2904 c.packetIds.clear();
2905 }
2906 sb.resetUnits();
2907 }
2908 for (auto &tree : st.treeOf)
2909 tree.clear();
2910 for (auto &hops : st.circuitHops)
2911 hops.clear();
2912 for (auto &dsts : st.treeDsts)
2913 dsts.clear();
2914 for (auto &hops : st.joinedHops)
2915 hops.clear();
2916 st.unmet.clear();
2917 st.met.clear();
2918 st.meetingPorts.clear();
2919
2920 // for each flow, find the shortest path from source to destination
2921 // update used_capacity for the path between them
2922
2923 for (const auto &[_, group] : st.groupedFlows) {
2924 for (int flow : group)
2925 if (llvm::Error err = routePart(st, flow))
2926 return std::move(err);
2927 for (auto &[_, sb] : graph) {
2928 for (SwitchboxConnect::Cell &c : sb.cells) {
2929 // fix used capacity for packet flows
2930 if (c.packetFlowCount > 0) {
2931 c.packetFlowCount = 0;
2932 c.usedCapacity++;
2933 }
2935 }
2936 }
2937 }
2938
2939 // The tree routed first may branch where none from elsewhere can meet it
2940 // at one switchbox, though it could meet a tree routed before it, or one
2941 // that leaves its source switchbox by one master port for them.
2942 for (auto [later, earlier] : st.unmet) {
2943 bool steered = st.reorder(later, earlier);
2944 steered |= st.trunked.insert({later, earlier}).second;
2945 steered |= st.trunked.insert({earlier, later}).second;
2946 if (steered)
2947 illegalEdges++;
2948 }
2949 bool split = false;
2950 for (const auto &pair : st.meetBlocked)
2951 if (st.togetherSources.insert(pair).second) {
2952 LLVM_DEBUG(llvm::dbgs()
2953 << "Route together to meet: "
2954 << describeTilePort(pair.first.coords, pair.first.port)
2955 << " and "
2956 << describeTilePort(pair.second.coords, pair.second.port)
2957 << "\n");
2958 st.splitOwnIds(pair);
2959 // Trunks steered them to where they could not meet; split, they can.
2960 for (int a : st.partsOf.at(pair.first))
2961 for (int b : st.partsOf.at(pair.second)) {
2962 st.trunked.erase({a, b});
2963 st.trunked.erase({b, a});
2964 }
2965 split = true;
2966 }
2967 st.meetBlocked.clear();
2968 for (const auto &[pair, ids] : st.meetSplits)
2969 for (int k : SmallVector<int, 2>(st.partsOf.at(pair.first)))
2970 if (!st.parts[k].isPriorityFlow && ids.size() < st.flowIds[k].size() &&
2971 llvm::all_of(ids,
2972 [&](int id) { return st.flowIds[k].count(id); })) {
2973 LLVM_DEBUG(llvm::dbgs()
2974 << "Route apart to meet: "
2975 << describeTilePort(pair.first.coords, pair.first.port)
2976 << " and "
2977 << describeTilePort(pair.second.coords, pair.second.port)
2978 << "\n");
2979 st.splitPart(k, ids);
2980 for (int a : st.partsOf.at(pair.first))
2981 for (int b : st.partsOf.at(pair.second)) {
2982 st.trunked.erase({a, b});
2983 st.trunked.erase({b, a});
2984 }
2985 split = true;
2986 }
2987 st.meetSplits.clear();
2988 if (split) {
2989 st.relateParts();
2990 illegalEdges++;
2991 }
2992
2993 for (auto &[_, sb] : graph) {
2994 for (size_t i = 0; i < sb.srcPorts.size(); i++) {
2995 for (size_t j = 0; j < sb.dstPorts.size(); j++) {
2996 SwitchboxConnect::Cell &c = sb.at(i, j);
2997 // check that every channel does not exceed max capacity
2998 if (c.usedCapacity > maxCircuitStreamCapacity) {
2999 c.overCapacity +=
3000 sinceFewest >= stallIterations && c.packetGroupId < 0
3001 ? stallHistory
3002 : 1;
3003 illegalEdges++;
3004 LLVM_DEBUG(llvm::dbgs()
3005 << "\t\t\tToo much capacity on (" << sb.srcCoords.col
3006 << "," << sb.srcCoords.row << ") "
3007 << sb.srcPorts[i].bundle << sb.srcPorts[i].channel
3008 << " -> (" << sb.dstCoords.col << "," << sb.dstCoords.row
3009 << ") " << sb.dstPorts[j].bundle
3010 << sb.dstPorts[j].channel << ", used_capacity = "
3011 << c.usedCapacity << ", demand = " << c.demand
3012 << ", over_capacity_count = " << c.overCapacity << "\n");
3013 }
3014 }
3015 }
3016 }
3017 // Once the overuse stalls, circuit trees that overuse a circuit-only
3018 // channel route first, so the same tree stops losing it. Packet-shared
3019 // overuse is left to the packet steering.
3020 if (illegalEdges < fewestIllegal) {
3021 fewestIllegal = illegalEdges;
3022 sinceFewest = reorderedStall = 0;
3023 } else {
3024 sinceFewest++;
3025 }
3026 // Overuse after a fit is out of reach of maxOverusedStall, which needs the
3027 // attempt never to have fit, so it stalls the routing check's count.
3028 if (fewestIllegal == 0 && illegalEdges > 0) {
3029 sinceFewestRejected++;
3030 LLVM_DEBUG(llvm::dbgs()
3031 << "Rejected-routing stall " << sinceFewestRejected << '\n');
3032 }
3033 if (illegalEdges && sinceFewest >= stallIterations) {
3034 auto losing = [&](int flow) {
3035 return !st.parts[flow].packetId &&
3036 llvm::any_of(st.circuitHops[flow], [](const Edge &e) {
3037 const SwitchboxConnect::Cell &c = e.sb->at(e.i, e.j);
3038 return c.usedCapacity > maxCircuitStreamCapacity &&
3039 c.packetGroupId < 0;
3040 });
3041 };
3042 bool moved = false;
3043 for (auto &[_, group] : st.groupedFlows) {
3044 moved |= llvm::any_of(group, losing);
3045 std::stable_partition(group.begin(), group.end(), losing);
3046 }
3047 reorderedStall += moved;
3048 }
3049 // Each stall period without a legal routing, the packet trees drop their
3050 // id splits: the routing that faulted them may be gone, and the routing
3051 // check adds back any still needed.
3052 if (sinceFewest >= stallIterations && sinceFewest % stallIterations == 0) {
3053 LLVM_DEBUG(llvm::dbgs() << "Drop the id splits after " << sinceFewest
3054 << " stalled iterations\n");
3055 for (auto &splits : st.splitsOf)
3056 splits.clear();
3057 }
3058
3059 // A routing that fits the fabric can still be one the caller cannot use;
3060 // steer away from the connections it names as if they were overused. One
3061 // it rejects naming nothing to move is as far as steering gets, leaving
3062 // the usable routing found, if any, or the rejection.
3063 bool stuck = false;
3064 llvm::Error unmoved =
3065 illegalEdges != 0 || !constraints.check
3066 ? llvm::Error::success()
3067 : llvm::handleErrors(
3068 constraints.check(st.routing),
3069 [&](std::unique_ptr<RoutingFailure> rejected) -> llvm::Error {
3070 LLVM_DEBUG(llvm::dbgs() << "Routing rejected: "
3071 << rejected->reason << '\n');
3072 int lessons = st.lessons, pinnedOnly = 0;
3073 int faulted =
3074 applyRoutingFaults(st, rejected->faults, pinnedOnly);
3075 illegalEdges += faulted;
3076 if (illegalEdges < fewestRejected || st.lessons > lessons) {
3077 fewestRejected = std::min(fewestRejected, illegalEdges);
3078 sinceFewestRejected = 0;
3079 } else {
3080 sinceFewestRejected++;
3081 }
3082 LLVM_DEBUG(llvm::dbgs() << "Rejected-routing stall "
3083 << sinceFewestRejected << '\n');
3084 priorityFaults = rejected->faults.onlyPriorityMasters
3085 ? priorityFaults + 1
3086 : 0;
3087 // Penalties on connections only pinned trees take move
3088 // nothing, so such faults are as stuck as none.
3089 stuck = faulted == pinnedOnly && st.lessons == lessons;
3090 LLVM_DEBUG(
3091 if (stuck && pinnedOnly) llvm::dbgs()
3092 << "\t\tPathfinder: the routing check names only "
3093 "connections pinned trees take ("
3094 << pinnedOnly << ") after " << iterationCount
3095 << " iterations\n");
3096 if (rejected->isA(DeadlockProneRouting::classID())) {
3097 if (!usable) {
3098 usable = st.routing;
3099 usableAt = iterationCount;
3100 }
3101 return llvm::Error::success();
3102 }
3103 if (stuck)
3104 return llvm::Error(std::move(rejected));
3105 checkReason = std::move(rejected->reason);
3106 return llvm::Error::success();
3107 });
3108
3109 LLVM_DEBUG({
3110 for (const auto &[src, settings] : st.routing.settings)
3111 llvm::dbgs() << "\t\t\tFlow starting at (" << src.coords.col << ","
3112 << src.coords.row << "):\t" << settings;
3113 // total path length, across switchboxes
3114 int totalPathLength = 0;
3115 for (const auto &[_, sb] : graph)
3116 if (sb.srcCoords != sb.dstCoords)
3117 for (const SwitchboxConnect::Cell &c : sb.cells)
3118 totalPathLength += c.usedCapacity;
3119 llvm::dbgs() << "\t\t---End findPaths iteration #" << iterationCount
3120 << " , illegal edges count = " << illegalEdges
3121 << ", total path length = " << totalPathLength << "---\n";
3122 });
3123 if (trajectory)
3124 trajectory->push_back(hashRouting(st.routing));
3125 if (stuck && usable) {
3126 llvm::consumeError(std::move(unmoved));
3127 return std::move(*usable);
3128 }
3129 if (unmoved)
3130 return std::move(unmoved);
3131 if (priorityFaults >= maxPriorityFaults) {
3132 LLVM_DEBUG(llvm::dbgs() << "\t\tPathfinder: the routing check rejects "
3133 "only master sets of the prioritized flows ("
3134 << priorityFaults << " routings in a row)\n");
3135 if (usable)
3136 return std::move(*usable);
3137 packetsFailed = false;
3138 return explainNoRouting(st);
3139 }
3140 // continue iterations until a legal routing is found
3141 } while (illegalEdges > 0);
3142
3143 LLVM_DEBUG(llvm::dbgs() << "\t---End Pathfinder::findPaths---\n");
3144 return std::move(st.routing);
3145}
STATISTIC(numReplaysSkipped, "Attempts skipped as replays of an earlier one")
virtual uint32_t getNumSourceShimMuxConnections(int col, int row, WireBundle bundle) const =0
Return the number of sources of connections inside a shimmux.
virtual bool isLegalTileConnection(int col, int row, WireBundle srcBundle, int srcChan, WireBundle dstBundle, int dstChan) const =0
bool isShimNOCorPLTile(int col, int row) const
Return true if the given tile is either a ShimNOC or ShimPL tile.
virtual uint32_t getNumDestShimMuxConnections(int col, int row, WireBundle bundle) const =0
Return the number of destinations of connections inside a shimmux.
virtual uint32_t getNumDestSwitchboxConnections(int col, int row, WireBundle bundle) const =0
Return the number of destinations of connections inside a switchbox.
virtual uint32_t getNumSourceSwitchboxConnections(int col, int row, WireBundle bundle) const =0
Return the number of sources of connections inside a switchbox.
ShimMuxOp getShimMux(mlir::OpBuilder &builder, int col)
SwitchboxOp getSwitchbox(mlir::OpBuilder &builder, int col, int row)
SwitchboxOp lookupSwitchbox(TileID tile) const
TileOp getTile(mlir::OpBuilder &builder, int col, int row)
llvm::Error runAnalysis(DeviceOp &device)
ShimMuxOp lookupShimMux(int col) const
std::vector< std::pair< TileID, Port > > avoidedPorts
void avoidPort(TileID coords, Port port)
std::vector< PathfinderAttempt > * attempts
llvm::Expected< Routing > findPaths(int maxIterations)
void excludeTile(TileID coords)
void addFlow(TileID srcCoords, Port srcPort, TileID dstCoords, Port dstPort, std::optional< int > packetId, bool isPriorityFlow, std::optional< mlir::Location > loc=std::nullopt)
void initialize(int maxCol, int maxRow, const AIETargetModel &targetModel)
mlir::LogicalResult addFixedConnection(SwitchboxOp switchboxOp)
void log(llvm::raw_ostream &os) const override
std::string joinNames(llvm::ArrayRef< std::string > names, size_t shown=4)
Lists names as "A, B and C", the first shown of them followed by "N more" if there are more.
int shimMuxChannelTo(Port dst)
std::string describePrioritized(llvm::ArrayRef< std::string > sources)
Says that the packet flows from sources keep the route they take alone, as a control-packet reload of...
struct TileID { friend std::ostream &operator<<(std::ostream &os, const TileID &s) { os<< "TileID("<< s.col<< ", "<< s.row<< ")"; return os; } friend std::string to_string(const TileID &s) { std::ostringstream ss; ss<< s; return ss.str(); } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const TileID &s) { os<< to_string(s); return os; } inline bool operator<(const TileID &rhs) const { return std::tie(col, row)< std::tie(rhs.col, rhs.row); } bool operator==(const TileID &rhs) const { return std::tie(col, row)==std::tie(rhs.col, rhs.row); } bool operator!=(const TileID &rhs) const { return !(*this==rhs);} int col, row;} TileID
bool isDirectional(WireBundle bundle)
Definition AIEDialect.h:525
std::tuple< bool, int, bool > boundaryOf(TileID a, TileID b)
int shimMuxChannelFrom(Port src)
std::string describeTilePort(TileID tile, Port port)
Names a tile port the way diagnostics do, e.g. "(0, 2) DMA:1".
struct Port { WireBundle bundle; int channel; bool operator==(const Port &rhs) const { return std::tie(bundle, channel)==std::tie(rhs.bundle, rhs.channel); } bool operator!=(const Port &rhs) const { return !(*this==rhs);} bool operator<(const Port &rhs) const { return std::tie(bundle, channel)< std::tie(rhs.bundle, rhs.channel); } friend std::ostream &operator<<(std::ostream &os, const Port &port) { os<< "("; os<< stringifyWireBundle(port.bundle).str(); os<< ": "<< std::to_string(port.channel)<< ")"; return os; } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Port &port) { os<< to_string(port); return os; } } Port
Definition AIEDialect.h:265
std::map< TileID, SwitchSetting > SwitchSettings
constexpr llvm::StringLiteral kNoLegalRouting
std::string describePort(Port port)
Names a port the way diagnostics do, e.g. "DMA:1".
WireBundle getConnectingBundle(WireBundle dir)
bool operator<(const IdSplit &other) const
std::vector< SmallVector< int, 4 > > prioritySets
std::set< std::pair< int, int > > noJoin
std::vector< llvm::DenseMap< int, std::pair< int, Edge > > > treeOf
std::map< std::pair< int, int >, int > meetFaults
void splitOwnIds(const std::pair< PathEndPoint, PathEndPoint > &pair)
std::vector< SmallVector< Edge, 8 > > circuitHops
std::set< std::pair< int, int > > reordered
std::vector< std::set< std::pair< TileID, int > > > partSplits
std::vector< uint32_t > processedStamp
std::vector< SmallVector< std::pair< int, Edge >, 8 > > joinedHops
std::set< std::pair< std::pair< PathEndPoint, PathEndPoint >, std::set< int > > > meetSplits
std::set< std::pair< int, int > > spared
std::vector< llvm::BitVector > conflicting
std::vector< SmallVector< int, 4 > > treeDsts
std::vector< std::set< IdSplit > > splitsOf
std::set< std::pair< int, int > > met
std::set< std::pair< PathEndPoint, PathEndPoint > > togetherSources
std::set< std::pair< PathEndPoint, PathEndPoint > > meetBlocked
bool reorder(int later, int earlier, bool again=false)
std::vector< std::set< int > > flowIds
llvm::MapVector< int, SmallVector< int, 8 > > groupedFlows
bool isPinned(const Flow &f) const
std::set< std::pair< PathEndPoint, PathEndPoint > > apartSources
std::set< std::pair< int, int > > unmet
std::map< std::pair< int, int >, PathEndPoint > meetingPorts
std::set< std::pair< int, IdSplit > > splitsTaught
bool mayLeave(ArrayRef< int > masters, int next) const
std::set< std::pair< int, int > > trunked
int splitPart(int flow, const std::set< int > &ids)
std::vector< SmallVector< int, 4 > > sameId
SmallVector< int, 4 > idsTo(int flow, int dstState) const
std::map< PathEndPoint, SmallVector< int, 2 > > partsOf
TreeBuilder(Pathfinder &pf, RouteState &st, int flow)
llvm::MapVector< int, SmallVector< int, 4 > > sharedDsts
SmallVector< PathEndPoint, 4 > pending
llvm::DenseSet< int > trunkOff(int dst) const
llvm::MapVector< int, SmallVector< int, 4 > > blockedDsts
void search(const llvm::DenseSet< int > &drop, ArrayRef< int > targets, const llvm::DenseSet< int > &off={})
const std::vector< TreeHop > * pinned
SmallVector< double, 16 > seedCosts
std::optional< PathEndPoint > first
SmallVector< std::pair< int, std::pair< int, Edge > >, 8 > pinnedJoins
int dstState(const PathEndPoint &p) const
llvm::MapVector< int, std::pair< int, Edge > > planned
llvm::DenseMap< int, SmallVector< int, 2 > > joinOwners
llvm::DenseMap< int, llvm::BitVector > branchAvoid
bool joinable(int at, ArrayRef< int > dsts) const
llvm::MapVector< int, std::pair< SmallVector< int, 4 >, std::set< int > > > blockedIds
SmallVector< std::pair< int, const SmallVector< int, 4 > * >, 2 > joinedAt
bool join(int state, int predId, const Edge &e)
llvm::DenseSet< int > splitOff(int dst) const
llvm::DenseMap< int, SmallVector< int, 4 > > joins
llvm::DenseMap< int, int > children
std::vector< PathEndPoint > dsts
std::optional< int > packetId
std::vector< std::string > flows
std::vector< llvm::BitVector > circuitOnly
std::vector< llvm::hash_code > trajectory
std::unique_ptr< RoutingFailure > prototype
llvm::DenseSet< TileID > crowdedTiles
std::optional< Routing > routing
std::vector< std::pair< TileID, Connect > > connections
std::vector< PathEndPoint > untrunk
std::vector< std::pair< PathEndPoint, PathEndPoint > > together
std::vector< TreeSplit > splits
std::vector< TileID > crowded
std::vector< std::pair< PathEndPoint, PathEndPoint > > apart
std::map< PathEndPoint, SwitchSettings > settings
std::map< std::pair< PathEndPoint, int >, SwitchSettings > idSettings
std::vector< Port > dsts
std::vector< Port > srcs
llvm::SmallDenseMap< int, int, 2 > packetIds
std::vector< Port > dstPorts
std::vector< Port > srcPorts
static void bumpDemand(Cell &c)
void addToUnit(int j, int flow)
Cell & at(size_t i, size_t j)
std::vector< Cell > cells
std::optional< PathEndPoint > apart