MLIR-AIE 1.4.6.dev
AIEPathFinder.h
Go to the documentation of this file.
1//===- AIEPathFinder.h ------------------------------------------*- 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
9#ifndef AIE_PATHFINDER_H
10#define AIE_PATHFINDER_H
11
15
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/BitVector.h"
18#include "llvm/ADT/BitmaskEnum.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/DenseSet.h"
21#include "llvm/ADT/Hashing.h"
22#include "llvm/ADT/IntEqClasses.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/Support/Error.h"
26#include "llvm/Support/raw_ostream.h"
27
28#include <functional>
29#include <map>
30#include <optional>
31#include <set>
32#include <string>
33#include <tuple>
34#include <vector>
35
36namespace xilinx::AIE {
37
38// A shim's DMA, NOC and PLIO ports reach its switchbox through the shim mux,
39// on the South channel these return for a port that sends or receives.
41int shimMuxChannelTo(Port dst);
42
43// The connections from the source ports to the destination ports of a
44// switchbox, if `srcCoords == dstCoords`, or of the wires from one switchbox
45// to its neighbour at `dstCoords`.
47 // A connection from a source port to a destination port.
48 struct Cell {
49 bool available = false;
50 // weight of Dijkstra's shortest path
51 double demand = 0;
52 // iterations the connection was over capacity
53 int overCapacity = 0;
54 // circuit streams using the connection
55 int usedCapacity = 0;
56 // packet streams using the connection
58 // only packet streams of this group may share the connection
59 int packetGroupId = -1;
60 // packet ids routed through the connection (and its crossbar row and
61 // column), by the flow routing each; it may be shared only among distinct
62 // ids.
63 llvm::SmallDenseMap<int, int, 2> packetIds;
64 // whether a prioritized flow uses the connection
65 bool isPriority = false;
66 // added to the demand, so routes keep off the connection where they can
67 double avoidance = 0;
68 };
69
70 SwitchboxConnect() = default;
71 SwitchboxConnect(TileID coords) : srcCoords(coords), dstCoords(coords) {}
74
76 std::vector<Port> srcPorts;
77 std::vector<Port> dstPorts;
78 // The connection from srcPorts[i] to dstPorts[j] is cells[i * dstPorts.size()
79 // + j].
80 std::vector<Cell> cells;
81 // Units of dst ports tied to one arbiter (see planArbiters in
82 // AIECreatePathFindFlows.cpp); a unit's leader lists the packet flows
83 // (indices into the router's flows) leaving by any of its ports
84 llvm::IntEqClasses dstUnits;
85 std::vector<llvm::SmallVector<int, 2>> unitPacketFlows;
86 // source ports the design already gives packet rules, which circuit streams
87 // cannot enter
88 llvm::BitVector packetOnlySrc;
89 // dst ports packet streams may no longer take
90 llvm::BitVector circuitOnlyDst;
91
92 Cell &at(size_t i, size_t j) { return cells[i * dstPorts.size() + j]; }
93 const Cell &at(size_t i, size_t j) const {
94 return cells[i * dstPorts.size() + j];
95 }
96
97 // The index of `p` in srcPorts or dstPorts, or -1.
98 int srcIndex(Port p) const { return indexIn(srcPorts, p); }
99 int dstIndex(Port p) const { return indexIn(dstPorts, p); }
100
101 // Size the cells and the per-port state to srcPorts and dstPorts.
102 void resize() {
103 cells.assign(srcPorts.size() * dstPorts.size(), Cell());
104 packetOnlySrc = llvm::BitVector(srcPorts.size());
105 circuitOnlyDst = llvm::BitVector(dstPorts.size());
106 unitPacketFlows.resize(dstPorts.size());
107 resetUnits();
108 }
109
110 void resetUnits() {
111 dstUnits.clear();
112 dstUnits.grow(dstPorts.size());
113 for (auto &flows : unitPacketFlows)
114 flows.clear();
115 }
116
117 llvm::ArrayRef<int> unitFlows(int j) const {
118 return unitPacketFlows[dstUnits.findLeader(j)];
119 }
120
121 void addToUnit(int j, int flow) {
122 auto &flows = unitPacketFlows[dstUnits.findLeader(j)];
123 if (!llvm::is_contained(flows, flow))
124 flows.push_back(flow);
125 }
126
127 void joinUnits(int j, int k) {
128 j = dstUnits.findLeader(j);
129 k = dstUnits.findLeader(k);
130 if (j == k)
131 return;
132 int leader = dstUnits.join(j, k);
133 int other = leader == j ? k : j;
134 for (int flow : unitPacketFlows[other])
135 addToUnit(leader, flow);
136 unitPacketFlows[other].clear();
137 }
138
139 // update demand at the beginning of each dijkstraShortestPaths iteration
140 void updateDemand();
141
142 // Bumps an over-capacity cell's demand, all but ruling it out if a
143 // prioritized flow uses it, to keep prioritized flows' routes.
144 static void bumpDemand(Cell &c);
145
146private:
147 static int indexIn(llvm::ArrayRef<Port> ports, Port p) {
148 const Port *it = llvm::find(ports, p);
149 return it == ports.end() ? -1 : it - ports.begin();
150 }
151};
152
154 PathEndPoint() = default;
156
159
160 friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
161 const PathEndPoint &s) {
162 return os << describeTilePort(s.coords, s.port);
163 }
164
165 bool operator<(const PathEndPoint &rhs) const {
166 return std::tie(coords, port) < std::tie(rhs.coords, rhs.port);
167 }
168
169 bool operator==(const PathEndPoint &rhs) const {
170 return std::tie(coords, port) == std::tie(rhs.coords, rhs.port);
171 }
172};
173
174struct Flow {
175 // -1 for a circuit flow.
177 bool isPriorityFlow = false;
179 std::vector<PathEndPoint> dsts;
180 // packet id carried by this flow (nullopt for circuit flows); a channel may
181 // be shared only among distinct ids so same-id flows never merge then fan
182 // out.
183 std::optional<int> packetId;
184};
185
186// A SwitchSetting defines the required settings for a Switchbox for a flow
187// SwitchSetting.srcs is the fanin
188// SwitchSetting.dsts is the fanout
190 SwitchSetting() = default;
191 SwitchSetting(std::vector<Port> srcs) : srcs(std::move(srcs)) {}
192 SwitchSetting(std::vector<Port> srcs, std::vector<Port> dsts)
193 : srcs(std::move(srcs)), dsts(std::move(dsts)) {}
194
195 std::vector<Port> srcs;
196 std::vector<Port> dsts;
197
198 friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
199 const SwitchSetting &s) {
200 os << "{";
201 llvm::interleaveComma(llvm::map_range(s.srcs, describePort), os);
202 os << "} -> {";
203 llvm::interleaveComma(llvm::map_range(s.dsts, describePort), os);
204 return os << "}";
205 }
206
207 bool operator<(const SwitchSetting &rhs) const { return srcs < rhs.srcs; }
208};
209
210using SwitchSettings = std::map<TileID, SwitchSetting>;
211
212inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
213 const SwitchSettings &ss) {
214 os << "\tSwitchSettings: ";
215 for (const auto &[coords, setting] : ss)
216 os << coords << ": " << setting << " | ";
217 return os << "\n";
218}
219
220// A hop of a packet flow's tree, from one port to the next; `joined` when the
221// flow takes it by joining another flow's tree.
222struct TreeHop {
224 bool joined;
225
226 bool operator==(const TreeHop &rhs) const {
227 return from == rhs.from && to == rhs.to && joined == rhs.joined;
228 }
229};
230using PacketTrees = std::map<PathEndPoint, std::vector<TreeHop>>;
231
232// Whether packet flows from the two sources, with ids among the two sets, can
233// deadlock if they share an arbiter; see StreamConflicts::conflict.
235 std::function<bool(const PathEndPoint &, const std::set<int> &,
236 const PathEndPoint &, const std::set<int> &)>;
237
238// Described packet streams, and why the first two conflict.
240 std::vector<std::string> flows;
241 std::string why;
242};
243// The most pairwise-conflicting packet streams found crossing from the tiles
244// `low` holds to the others if `up` (else back), searching no further than
245// `limit` + 1; see Pathfinder::cutOverflow.
246using PacketsApartAcross = std::function<PacketsApart(
247 llvm::function_ref<bool(TileID)> low, bool up, size_t limit)>;
248
249// Packets `src` sends with ids `a` and `b` share a master port they leave
250// tile `at` by, which puts them on one arbiter. If `apart` is set, the
251// packets with id `b` for that destination on the tile reach it by a slave
252// port of their own instead.
253struct TreeSplit {
256 int a, b;
257 std::optional<PathEndPoint> apart;
258
259 bool operator<(const TreeSplit &rhs) const {
260 return std::tie(src, at, a, b, apart) <
261 std::tie(rhs.src, rhs.at, rhs.a, rhs.b, rhs.apart);
262 }
263};
264
265// What makes a routing unusable: switchbox connections to move, and where a
266// source's tree has to branch, and crowded tiles (see Pathfinder::relax).
268 std::vector<std::pair<TileID, Connect>> connections;
269 std::vector<TreeSplit> splits;
270 std::vector<TileID> crowded;
271 // Sources whose packet flows the routing put on one arbiter or link in a
272 // hold cycle, to keep apart like conflicting ones from then on.
273 std::vector<std::pair<PathEndPoint, PathEndPoint>> apart;
274 // Sources whose packet flows wait on each other at receivers they share
275 // in a hold cycle, so their trees should meet: each routes the ids the
276 // other does not send as a part of their own from then on.
277 std::vector<std::pair<PathEndPoint, PathEndPoint>> together;
278 // Sources whose tree waits on an arbiter it holds itself; they stop
279 // trunking (see RouteState::trunked).
280 std::vector<PathEndPoint> untrunk;
281 // Whether every rejected connection would change a pinned master set.
283};
284
285// A routing findPaths found.
286struct Routing {
287 // The switch settings of each source's flows.
288 std::map<PathEndPoint, SwitchSettings> settings;
289 // The packet flows' trees, by source.
291 // The switch settings of the packets a source sends with an id, where they
292 // are routed apart from the others the source sends.
293 std::map<std::pair<PathEndPoint, int>, SwitchSettings> idSettings;
294};
295
296// How the router's message starts when the flows do not fit the links.
297inline constexpr llvm::StringLiteral kNoLegalRouting =
298 "Unable to find a legal routing";
299
300// Why no legal routing was found, reported at `loc`, or the device if unset,
301// with `reason` if the router can say. A routing check's failure also names
302// the faults the router has to move.
303class RoutingFailure : public llvm::ErrorInfo<RoutingFailure> {
304public:
305 static char ID;
306
307 explicit RoutingFailure(std::string reason, RoutingFaults faults = {},
308 std::optional<mlir::Location> loc = std::nullopt)
309 : reason(std::move(reason)), faults(std::move(faults)), loc(loc) {}
310
311 void log(llvm::raw_ostream &os) const override;
312 std::error_code convertToErrorCode() const override {
313 return llvm::inconvertibleErrorCode();
314 }
315
316 // Another failure of this error's own dynamic type, naming `reason`,
317 // `faults` and `loc`: how the replay ladder reconstructs a kept attempt's
318 // failure from its stored fields without a classID switch at each site
319 // that needs one.
320 virtual std::unique_ptr<RoutingFailure>
322 std::optional<mlir::Location> loc) const {
323 return std::make_unique<RoutingFailure>(std::move(reason),
324 std::move(faults), loc);
325 }
326
327 std::string reason;
329 std::optional<mlir::Location> loc;
330};
331
332// A routing that can deadlock only where allow-deadlock-prone lets it: usable,
333// though the router would rather move the faults it names.
335 : public llvm::ErrorInfo<DeadlockProneRouting, RoutingFailure> {
336public:
337 static char ID;
338 using ErrorInfo::ErrorInfo;
339 std::unique_ptr<RoutingFailure>
340 clone(std::string reason, RoutingFaults faults,
341 std::optional<mlir::Location> loc) const override {
342 return std::make_unique<DeadlockProneRouting>(std::move(reason),
343 std::move(faults), loc);
344 }
345};
346
347// No legal routing around the routes prioritized flows keep, which the reason
348// already blames.
350 : public llvm::ErrorInfo<PinnedRoutingFailure, RoutingFailure> {
351public:
352 static char ID;
353 using ErrorInfo::ErrorInfo;
354 std::unique_ptr<RoutingFailure>
355 clone(std::string reason, RoutingFaults faults,
356 std::optional<mlir::Location> loc) const override {
357 return std::make_unique<PinnedRoutingFailure>(std::move(reason),
358 std::move(faults), loc);
359 }
360};
361
362// Checks a routing that fits the fabric: a RoutingFailure if it is unusable,
363// success if it is accepted.
364using RoutingCheck = std::function<llvm::Error(const Routing &)>;
365
366// What packet flows are routed under.
368 // Routings the check rejects count as illegal; the connections it names
369 // are penalized like overused channels so later iterations avoid them, and
370 // the trees it splits branch where it says from then on. A routing it
371 // rejects as a DeadlockProneRouting is kept, and found if no better one is
372 // soon.
374 // Packet flows that conflict are steered off each other's master ports; see
375 // edgeWeight.
378 // The prioritized packet flows from these sources take these trees
379 // instead of being routed.
381 // The packet ids each pinned tree carries. A pinned source's other flows
382 // route with the rest of the design, prioritized or not.
383 std::map<PathEndPoint, std::set<int>> pinnedIds;
384 // Whether prioritized packet flows not pinned route first, keeping
385 // other flows off their channels; otherwise they route like the others.
386 bool prioritize = true;
387};
388
389// The relax settings an attempt reads while it routes (see Pathfinder::relax).
390enum class Relax : uint8_t {
391 None = 0,
392 IdsApart = 1 << 0,
393 SplitShared = 1 << 1,
394 // Trees that share destinations no longer meet (see TreeBuilder::meet), so
395 // what is left of their hazard is a hold cycle through those receivers.
396 MeetApart = 1 << 2,
397 // A flow meets another id's tree ahead of a same-id partner that has not
398 // routed yet (see Pathfinder::meetAhead).
400 LLVM_MARK_AS_BITMASK_ENUM(MeetAheadOfPartners)
401};
403
404// What one attempt of a relax ladder read that a relax step changes, and what
405// it found. A later attempt of the ladder that reads the same replays it
406// exactly, as routing is deterministic and the ladder's constraints are fixed.
408 std::vector<Flow> flows;
409 std::vector<llvm::BitVector> circuitOnly;
410 // The settings' values, and which of them the attempt read.
412 // The routing found, else the failure: a clone of it (so reconstructing a
413 // replay's failure needs no classID switch, just prototype->clone()) and
414 // its contents.
415 std::optional<Routing> routing;
416 std::unique_ptr<RoutingFailure> prototype;
417 std::string reason;
419 std::optional<mlir::Location> loc;
420 // What relax reads after the attempt.
421 llvm::DenseSet<TileID> crowdedTiles;
422 bool packetsFailed = false;
423 std::string checkReason;
424 // Each iteration's routing, kept under -aie-pathfinder-verify-replays.
425 std::vector<llvm::hash_code> trajectory;
426};
427
428// The boundary the wires from tile `a` to its neighbour `b` cross: between
429// rows (else columns) `below` and the next, upward (else back).
430std::tuple<bool, int, bool> boundaryOf(TileID a, TileID b);
431
432// Congestion-negotiated routing: each iteration routes every flow by
433// Dijkstra, given each connection's demand, and raises the demand of the
434// connections used over capacity, until no connection is.
436public:
437 void initialize(int maxCol, int maxRow, const AIETargetModel &targetModel);
438 // Adds a flow from `src` to `dst`; failures to route it are reported at
439 // `loc` when given.
440 void addFlow(TileID srcCoords, Port srcPort, TileID dstCoords, Port dstPort,
441 std::optional<int> packetId, bool isPriorityFlow,
442 std::optional<mlir::Location> loc = std::nullopt);
443 void sortFlows();
444 // Reserves the connections `switchboxOp` already makes, so routing avoids
445 // them. Fails if it makes one the switchbox cannot.
446 mlir::LogicalResult addFixedConnection(SwitchboxOp switchboxOp);
447 // Keeps routes out of the switchbox at `coords`.
448 void excludeTile(TileID coords);
449 // Keeps routes off an output port of a switchbox where another is free.
450 void avoidPort(TileID coords, Port port);
451 // A RoutingFailure if no legal routing is found in `maxIterations`. An
452 // attempt that replays one in `attempts` returns what that one found.
453 llvm::Expected<Routing> findPaths(int maxIterations);
454 // The attempts of the relax ladder being routed, if the caller keeps them;
455 // it routes one design under one set of constraints meanwhile.
456 std::vector<PathfinderAttempt> *attempts = nullptr;
457 void setPacketConstraints(PacketConstraints c) { constraints = std::move(c); }
458 // Loosens the packet constraints by one step after findPaths found no
459 // routing; false once no step is left or no packet stream took part in the
460 // failure. Packet flows start sharing channels only within their
461 // destination group. The steps, each skipped if it changes nothing: share
462 // channels with any packet flow; cap the fan-out of tiles the routing check
463 // found out of packet rules or msels to packetFanoutCap channels per
464 // direction; route the second id of an unbranchable split apart, which
465 // restarts sharing and caps; then share and cap again; route the ids a
466 // source sends that a source it must keep apart from does not as a part of
467 // their own, which restarts sharing and caps; then share and cap again;
468 // route each other source of a cluster that has to meet first, one per
469 // attempt (see rotateLeads); meet ahead of same-id partners; then stop
470 // meeting, which runs the steps before rotating again.
471 bool relax();
472
473private:
474 // A directed edge in the dense routing graph: from some node to node `dst`,
475 // realized by cell (i, j) of `sb`. `sb` points into `graph`, so demand reads
476 // always see the current iteration's weights.
477 struct Edge {
478 int dst;
480 int i;
481 int j;
482 };
483
484 // A `Port` is (bundle, channel) with no direction, so one dense node stands
485 // for both a switchbox port's input side and its output side. Dijkstra
486 // therefore searches over states, not nodes: a state is a node paired with
487 // the side of that port the stream is currently on. A stream enters a
488 // switchbox on an input port, crosses the crossbar once to an output port,
489 // and then rides the wire to the neighbour's input port -- so In only ever
490 // takes intra-switchbox edges and Out only ever takes inter-switchbox ones.
491 // Without the split, Dijkstra can chain two crossbar hops through one port
492 // and turn the stream around inside a switchbox; the settings it emits then
493 // dead-end and AIECreatePathFindFlows reports the flow as unroutable.
494 enum PortSide : int { In = 0, Out = 1 };
495 static int stateId(int nodeId, PortSide side) { return 2 * nodeId + side; }
496 static int stateNode(int state) { return state >> 1; }
497
498 // Build the dense integer node numbering and per-node adjacency from `graph`
499 // and `flows`. Topology is fixed across congestion iterations, so this runs
500 // once. A node's crossbar edges come before its wire edges, each in the order
501 // of the PathEndPoints they reach, so Dijkstra breaks ties the same way every
502 // run.
503 void buildRoutingGraph();
504
505 // The cost of taking `e`, as dijkstraShortestPaths weighs it.
506 double edgeWeight(const Edge &e, std::optional<int> packetId,
507 const llvm::BitVector *avoid,
508 const llvm::BitVector *avoidBranch) const;
509
510 // Dijkstra over the dense graph from the states in `seeds`, each starting at
511 // its cost in `seedCosts`. Fills `preds` (predecessor state id, or -1) and
512 // `predEdge` (the edge taken to reach each state). Reuses the scratch buffers
513 // below. Each edge costs its edgeWeight given `packetId`, `avoid` and, from a
514 // state in `branchAvoid`, the flows it maps to. States in `stops` are reached
515 // but not left, and a crossbar hop is taken only if `mayCross` allows it. The
516 // search ends once every state in `targets` is settled; only their `distance`
517 // and paths are final then.
518 void dijkstraShortestPaths(
519 llvm::ArrayRef<int> seeds, llvm::ArrayRef<double> seedCosts,
520 std::optional<int> packetId, const llvm::BitVector *avoid = nullptr,
521 const llvm::DenseMap<int, llvm::BitVector> *branchAvoid = nullptr,
522 const llvm::DenseSet<int> *stops = nullptr,
523 llvm::ArrayRef<int> targets = {},
524 llvm::function_ref<bool(int, int)> mayCross = nullptr);
525
526 struct RouteState;
527 struct TreeBuilder;
528 // Route `flow`'s tree around those routed before it this iteration. A
529 // RoutingFailure if it reaches no path to a destination.
530 llvm::Error routePart(RouteState &st, int flow);
531 // findPaths' iterations, once it has set the graph up; each routing's hash
532 // goes to `trajectory` if given.
533 llvm::Expected<Routing> negotiate(int maxIterations,
534 std::vector<llvm::hash_code> *trajectory);
535 // Steer the next iteration away from what the routing check faulted.
536 // Returns the illegal edges the faults count as; `pinnedOnly` counts those
537 // of them that are connections only pinned trees take, which no penalty
538 // moves.
539 int applyRoutingFaults(RouteState &st, const RoutingFaults &faults,
540 int &pinnedOnly);
541 // A RoutingFailure saying why the last iteration's routing does not fit.
542 llvm::Error explainNoRouting(const RouteState &st) const;
543 // A RoutingFailure if the flows crossing some row or column boundary need
544 // more channels across it than it has, however they are routed.
545 llvm::Error cutOverflow() const;
546 bool hasRoom(const SwitchboxConnect &sb) const;
547 // The steps of relax.
548 bool shareAllChannels();
549 bool capCrowdedFanOut();
550 bool routeIdsApart();
551 bool splitSharedIds();
552 bool stopMeeting();
553 bool rotateLeads();
554 bool meetAhead();
555
556 // Flows to be routed
557 std::vector<Flow> flows;
558 // The packet ids each source sends each destination.
559 std::map<std::pair<PathEndPoint, PathEndPoint>, llvm::SmallVector<int, 2>>
560 packetIdsTo;
561 // The packet ids each source sends, to any destination.
562 std::map<PathEndPoint, std::set<int>> idsBySource() const;
563 // The packet ids each source sends in prioritized flows.
564 std::map<PathEndPoint, std::set<int>> priorityIds;
565 // Where each source's flow to each destination was declared.
566 std::map<PathEndPoint, std::map<PathEndPoint, mlir::Location>> flowLocs;
567 std::optional<mlir::Location> flowLoc(const PathEndPoint &src,
568 const PathEndPoint *dst) const;
569 // The routing graph, by the tiles a SwitchboxConnect connects: a tile to
570 // itself for its switchbox, or to a neighbour for the wires between them.
571 std::map<std::pair<TileID, TileID>, SwitchboxConnect> graph;
572
573 // Dense routing graph (built once by buildRoutingGraph()).
574 bool graphBuilt = false;
575 std::map<PathEndPoint, int> nodeIds; // PathEndPoint -> dense id
576 std::vector<PathEndPoint> nodes; // dense id -> PathEndPoint
577 std::vector<std::vector<Edge>> adjacency; // dense id -> out-edges
578 std::vector<size_t> wireEdgesBegin; // dense id -> first wire edge
579
580 // Dijkstra scratch, indexed by state id (2 * nodes.size()) and reused across
581 // calls.
582 std::vector<double> distance;
583 std::vector<uint64_t> indexInHeap;
584 std::vector<int8_t> colors;
585 std::vector<int> preds;
586 std::vector<Edge> predEdge;
587
588 int getOrAddNodeId(const PathEndPoint &pep);
589
590 PacketConstraints constraints;
591 // Why the routing check rejected the last routing it rejected.
592 std::string checkReason;
593 // Whether packet streams took part in the last failure: the routing check
594 // rejected a routing, or packet streams cross a link left overused, or the
595 // boundary it crosses.
596 bool packetsFailed = true;
597 bool shareChannels = false;
598 Relax settings = Relax::None;
599 // Whether a tree met another in any attempt, so stopping meeting can change
600 // anything.
601 bool treesMet = false;
602 // The device's columns and rows; the graph has tiles one past each.
603 int columns = 0, rows = 0;
604 size_t relaxStep = 0;
605 // The sources that route first among those that have to meet, and how many
606 // turns of rotateLeads they have taken.
607 std::set<PathEndPoint> leads;
608 size_t leadStep = 0;
609 llvm::DenseSet<TileID> crowdedTiles, cappedTiles;
610 // The relax settings this attempt read; sortFlows and findPaths fold in
611 // the others (shareChannels, leads, cappedTiles) before it routes.
612 Relax consulted = Relax::None;
613 // Whether `setting` is on, noting that this attempt read it.
614 bool consult(Relax setting) {
615 consulted |= setting;
616 return any(settings & setting);
617 }
618};
619
620// Routes the flows of a device with a Pathfinder, and finds or creates the
621// tiles, switchboxes and shim muxes the routing is lowered onto.
623public:
624 // A RoutingFailure if the flows in `device` have no legal routing.
625 llvm::Error runAnalysis(DeviceOp &device);
626
627 int getMaxCol() const { return maxCol; }
628 int getMaxRow() const { return maxRow; }
629
630 TileOp getTile(mlir::OpBuilder &builder, int col, int row);
631 TileOp getTile(mlir::OpBuilder &builder, const TileID &tileId);
632 SwitchboxOp getSwitchbox(mlir::OpBuilder &builder, int col, int row);
633 ShimMuxOp getShimMux(mlir::OpBuilder &builder, int col);
634
635 // The ops at `tile` the analysis has found or created, or null.
636 TileOp lookupTile(TileID tile) const { return coordToTile.lookup(tile); }
637 SwitchboxOp lookupSwitchbox(TileID tile) const {
638 return coordToSwitchbox.lookup(tile);
639 }
640 ShimMuxOp lookupShimMux(int col) const {
641 return coordToShimMux.lookup({col, 0});
642 }
643
645 // Passed to Pathfinder::avoidPort.
646 std::vector<std::pair<TileID, Port>> avoidedPorts;
647 // The routing runAnalysis found.
649 // The sources of the circuit flows lowered so far.
650 std::set<PathEndPoint> processedFlows;
651
652private:
653 // how long until declared unroutable
654 static constexpr int maxIterations = 1000;
655
656 int maxCol = 0, maxRow = 0;
657 llvm::DenseMap<TileID, TileOp> coordToTile;
658 llvm::DenseMap<TileID, SwitchboxOp> coordToSwitchbox;
659 llvm::DenseMap<TileID, ShimMuxOp> coordToShimMux;
660};
661
662} // namespace xilinx::AIE
663
664#endif
std::unique_ptr< RoutingFailure > clone(std::string reason, RoutingFaults faults, std::optional< mlir::Location > loc) const override
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, const TileID &tileId)
TileOp lookupTile(TileID tile) const
TileOp getTile(mlir::OpBuilder &builder, int col, int row)
llvm::Error runAnalysis(DeviceOp &device)
std::set< PathEndPoint > processedFlows
ShimMuxOp lookupShimMux(int col) const
std::vector< std::pair< TileID, Port > > avoidedPorts
void avoidPort(TileID coords, Port port)
std::vector< PathfinderAttempt > * attempts
llvm::Expected< Routing > findPaths(int maxIterations)
void setPacketConstraints(PacketConstraints c)
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)
std::unique_ptr< RoutingFailure > clone(std::string reason, RoutingFaults faults, std::optional< mlir::Location > loc) const override
void log(llvm::raw_ostream &os) const override
RoutingFailure(std::string reason, RoutingFaults faults={}, std::optional< mlir::Location > loc=std::nullopt)
std::optional< mlir::Location > loc
virtual std::unique_ptr< RoutingFailure > clone(std::string reason, RoutingFaults faults, std::optional< mlir::Location > loc) const
std::error_code convertToErrorCode() const override
std::function< llvm::Error(const Routing &)> RoutingCheck
int shimMuxChannelTo(Port dst)
struct TileID { friend std::ostream &operator<<(std::ostream &os, const TileID &s) { os<< "TileID("<< s.col<< ", "<< s.row<< ")"; return os; } friend std::string to_string(const TileID &s) { std::ostringstream ss; ss<< s; return ss.str(); } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const TileID &s) { os<< to_string(s); return os; } inline bool operator<(const TileID &rhs) const { return std::tie(col, row)< std::tie(rhs.col, rhs.row); } bool operator==(const TileID &rhs) const { return std::tie(col, row)==std::tie(rhs.col, rhs.row); } bool operator!=(const TileID &rhs) const { return !(*this==rhs);} int col, row;} TileID
std::function< bool(const PathEndPoint &, const std::set< int > &, const PathEndPoint &, const std::set< int > &)> PacketConflict
llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const SwitchSettings &ss)
std::tuple< bool, int, bool > boundaryOf(TileID a, TileID b)
std::function< PacketsApart( llvm::function_ref< bool(TileID)> low, bool up, size_t limit)> PacketsApartAcross
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
LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE()
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".
std::map< PathEndPoint, std::vector< TreeHop > > PacketTrees
std::vector< PathEndPoint > dsts
std::optional< int > packetId
std::map< PathEndPoint, std::set< int > > pinnedIds
std::vector< std::string > flows
PathEndPoint(TileID coords, Port port)
bool operator==(const PathEndPoint &rhs) const
friend llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const PathEndPoint &s)
bool operator<(const PathEndPoint &rhs) const
std::optional< mlir::Location > loc
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
bool operator<(const SwitchSetting &rhs) const
friend llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const SwitchSetting &s)
SwitchSetting(std::vector< Port > srcs)
SwitchSetting(std::vector< Port > srcs, std::vector< Port > dsts)
std::vector< Port > srcs
llvm::SmallDenseMap< int, int, 2 > packetIds
llvm::IntEqClasses dstUnits
llvm::ArrayRef< int > unitFlows(int j) const
std::vector< Port > dstPorts
std::vector< Port > srcPorts
std::vector< llvm::SmallVector< int, 2 > > unitPacketFlows
SwitchboxConnect(TileID srcCoords, TileID dstCoords)
static void bumpDemand(Cell &c)
void addToUnit(int j, int flow)
Cell & at(size_t i, size_t j)
std::vector< Cell > cells
const Cell & at(size_t i, size_t j) const
bool operator==(const TreeHop &rhs) const
std::optional< PathEndPoint > apart
bool operator<(const TreeSplit &rhs) const