search

nod-ai / iree-amd-aie

IREE plugin repository for the AMD AIE accelerator
Apache License 2.0
69 stars 30 forks source link

[Router] Consider channel ID demand and congestion in Dijkstra #802

Closed jtuyls closed 1 month ago

jtuyls commented 2 months ago

Pulls in changes from: https://github.com/Xilinx/mlir-aie/pull/1643:

Changes on router behaviours: Previously, the router used a two-step process: first finding paths with Dijkstra's algorithm and then allocating channel IDs based on heuristics. Now, channel ID allocation is integrated into Dijkstra's algorithm to consider demand and congestion on individual channels directly.

NOTE: I had to bump the DEMAND_COEFF from 1.1 to 1.5 to find a solution for the unit_vecmul_4x4.mlir testcase. Not sure whether this makes sense or there might be an underlying issue? cc @Yu-Zhewen

makslevental commented 1 month ago

Not sure whether this makes sense or there might be an underlying issue?

I'm trying to think how these behave differently - looking at the code closely I don't actually see how this PR handles congestion differently? It's still basically 

      double history = 1.0 + OVER_CAPACITY_COEFF * overCapacity[&ch];
      double congestion = 1.0 + USED_CAPACITY_COEFF * usedCapacity[&ch];
      demand[&ch] = history * congestion;

right?

jtuyls commented 1 month ago

Not sure whether this makes sense or there might be an underlying issue?

I'm trying to think how these behave differently - looking at the code closely I don't actually see how this PR handles congestion differently? It's still basically

      double history = 1.0 + OVER_CAPACITY_COEFF * overCapacity[&ch];
      double congestion = 1.0 + USED_CAPACITY_COEFF * usedCapacity[&ch];
      demand[&ch] = history * congestion;

right?

It might just be the coefficients? I do see the load being spread over more connections.