9#ifndef AIE_PATHFINDER_H
10#define AIE_PATHFINDER_H
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"
93 const Cell &
at(
size_t i,
size_t j)
const {
123 if (!llvm::is_contained(flows, flow))
124 flows.push_back(flow);
133 int other = leader == j ? k : j;
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();
179 std::vector<PathEndPoint>
dsts;
214 os <<
"\tSwitchSettings: ";
215 for (
const auto &[coords, setting] : ss)
216 os << coords <<
": " << setting <<
" | ";
235 std::function<bool(
const PathEndPoint &,
const std::set<int> &,
247 llvm::function_ref<
bool(
TileID)> low,
bool up,
size_t limit)>;
273 std::vector<std::pair<PathEndPoint, PathEndPoint>>
apart;
277 std::vector<std::pair<PathEndPoint, PathEndPoint>>
together;
298 "Unable to find a legal routing";
308 std::optional<mlir::Location>
loc = std::nullopt)
311 void log(llvm::raw_ostream &os)
const override;
313 return llvm::inconvertibleErrorCode();
320 virtual std::unique_ptr<RoutingFailure>
322 std::optional<mlir::Location>
loc)
const {
323 return std::make_unique<RoutingFailure>(std::move(
reason),
329 std::optional<mlir::Location>
loc;
335 :
public llvm::ErrorInfo<DeadlockProneRouting, RoutingFailure> {
338 using ErrorInfo::ErrorInfo;
339 std::unique_ptr<RoutingFailure>
341 std::optional<mlir::Location> loc)
const override {
342 return std::make_unique<DeadlockProneRouting>(std::move(reason),
343 std::move(faults), loc);
350 :
public llvm::ErrorInfo<PinnedRoutingFailure, RoutingFailure> {
353 using ErrorInfo::ErrorInfo;
354 std::unique_ptr<RoutingFailure>
356 std::optional<mlir::Location> loc)
const override {
357 return std::make_unique<PinnedRoutingFailure>(std::move(reason),
358 std::move(faults), loc);
419 std::optional<mlir::Location>
loc;
441 std::optional<int> packetId,
bool isPriorityFlow,
442 std::optional<mlir::Location> loc = std::nullopt);
453 llvm::Expected<Routing>
findPaths(
int maxIterations);
456 std::vector<PathfinderAttempt> *
attempts =
nullptr;
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; }
503 void buildRoutingGraph();
506 double edgeWeight(
const Edge &e, std::optional<int> packetId,
507 const llvm::BitVector *avoid,
508 const llvm::BitVector *avoidBranch)
const;
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);
530 llvm::Error routePart(
RouteState &st,
int flow);
533 llvm::Expected<Routing> negotiate(
int maxIterations,
534 std::vector<llvm::hash_code> *trajectory);
539 int applyRoutingFaults(
RouteState &st,
const RoutingFaults &faults,
542 llvm::Error explainNoRouting(
const RouteState &st)
const;
545 llvm::Error cutOverflow()
const;
546 bool hasRoom(
const SwitchboxConnect &sb)
const;
548 bool shareAllChannels();
549 bool capCrowdedFanOut();
550 bool routeIdsApart();
551 bool splitSharedIds();
557 std::vector<Flow> flows;
559 std::map<std::pair<PathEndPoint, PathEndPoint>, llvm::SmallVector<int, 2>>
562 std::map<PathEndPoint, std::set<int>> idsBySource()
const;
564 std::map<PathEndPoint, std::set<int>> priorityIds;
566 std::map<PathEndPoint, std::map<PathEndPoint, mlir::Location>> flowLocs;
567 std::optional<mlir::Location> flowLoc(
const PathEndPoint &src,
568 const PathEndPoint *dst)
const;
571 std::map<std::pair<TileID, TileID>, SwitchboxConnect> graph;
574 bool graphBuilt =
false;
575 std::map<PathEndPoint, int> nodeIds;
576 std::vector<PathEndPoint> nodes;
577 std::vector<std::vector<Edge>> adjacency;
578 std::vector<size_t> wireEdgesBegin;
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;
588 int getOrAddNodeId(
const PathEndPoint &pep);
590 PacketConstraints constraints;
592 std::string checkReason;
596 bool packetsFailed =
true;
597 bool shareChannels =
false;
601 bool treesMet =
false;
603 int columns = 0, rows = 0;
604 size_t relaxStep = 0;
607 std::set<PathEndPoint> leads;
609 llvm::DenseSet<TileID> crowdedTiles, cappedTiles;
614 bool consult(
Relax setting) {
615 consulted |= setting;
616 return any(settings & setting);
630 TileOp
getTile(mlir::OpBuilder &builder,
int col,
int row);
632 SwitchboxOp
getSwitchbox(mlir::OpBuilder &builder,
int col,
int row);
633 ShimMuxOp
getShimMux(mlir::OpBuilder &builder,
int col);
638 return coordToSwitchbox.lookup(tile);
641 return coordToShimMux.lookup({col, 0});
654 static constexpr int maxIterations = 1000;
656 int maxCol = 0, maxRow = 0;
657 llvm::DenseMap<TileID, TileOp> coordToTile;
658 llvm::DenseMap<TileID, SwitchboxOp> coordToSwitchbox;
659 llvm::DenseMap<TileID, ShimMuxOp> coordToShimMux;
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
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
PacketsApartAcross apartAcross
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< Flow > flows
std::vector< llvm::hash_code > trajectory
std::unique_ptr< RoutingFailure > prototype
llvm::DenseSet< TileID > crowdedTiles
std::optional< Routing > routing
std::vector< std::pair< TileID, Connect > > connections
std::vector< PathEndPoint > untrunk
std::vector< std::pair< PathEndPoint, PathEndPoint > > together
std::vector< TreeSplit > splits
std::vector< TileID > crowded
std::vector< std::pair< PathEndPoint, PathEndPoint > > apart
std::map< PathEndPoint, SwitchSettings > settings
std::map< std::pair< PathEndPoint, int >, SwitchSettings > idSettings
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)
llvm::SmallDenseMap< int, int, 2 > packetIds
llvm::IntEqClasses dstUnits
llvm::ArrayRef< int > unitFlows(int j) const
std::vector< Port > dstPorts
llvm::BitVector packetOnlySrc
std::vector< Port > srcPorts
std::vector< llvm::SmallVector< int, 2 > > unitPacketFlows
SwitchboxConnect(TileID srcCoords, TileID dstCoords)
int srcIndex(Port p) const
SwitchboxConnect()=default
static void bumpDemand(Cell &c)
void addToUnit(int j, int flow)
llvm::BitVector circuitOnlyDst
SwitchboxConnect(TileID coords)
Cell & at(size_t i, size_t j)
std::vector< Cell > cells
int dstIndex(Port p) const
void joinUnits(int j, int k)
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