Routing Heat Map

[eddieh-xlnx]

Originally posted by @coherent17 at #1183 (comment)

I'd like to share some of my work recently, perhaps you can suggest a better implementation method. I'm now implementing a tool that takes a DCP(might be fully routed, or partial routed due to site pin conflict) and generate a routing heat map as I discussed with @clavin-xlnx in #1144 & #1145.

However, in the PR #1145, didn't consider the partial routed net, so that the route heat map reported might be too optimistic since for some partial routed net, the PIP didn't actually occupy the INT-tile.

What I want to achieve is something that Vivado GUI mode shows "interconnect density" metric, ex:

Below is the code snippet that calculate the routing heat map with the tile for partial routed net's PIP marked as util rate as 1.

private static void dumpRouteHeatMap() {

    // mark the unrouted nets in the tile as 1
    double [][] routeHeatMap = new double[maxRow][maxCol];

    // just calculate the PIP usage inside the INT_TILE
    double [][] switchboxUtilMap = new double[maxRow][maxCol];

    // check whether the net is routed or not routed
    ArrayList<Net> unroutedNets = new ArrayList<>();

    for (Net n : design.getNets()) {
        // skip for the nets that has no pip and the static net
        if (!n.hasPIPs() || n.getName().contains("GLOBAL_LOGIC")) continue;


        // iterate the site pins to check whether the net is routed or not
        for (SitePinInst pin : n.getPins()) {
            if (!pin.isRouted() && !pin.isOutPin()) {
                System.out.println("Net " + n.getName() + " has unrouted pin: " + pin.getName() + " in tile: " + pin.getTile().getName());
                unroutedNets.add(n);
                break;
            }
        }

        // calculate the switchbox util rate by pip usage
        for (PIP p : n.getPIPs()) {
            if (p.getTile().getTileTypeEnum() == TileTypeEnum.INT) {
                // add 2.0 to the heatmap, since for each PIP, it will be connected to 2 nodes
                routeHeatMap[p.getTile().getRow()][p.getTile().getColumn()] += 2.0;
                switchboxUtilMap[p.getTile().getRow()][p.getTile().getColumn()] += 2.0;
            }
        }
    }

    System.out.println("Routed Nets: " + (design.getNets().size() - unroutedNets.size()));
    System.out.println("Unrouted Nets: " + unroutedNets.size());

    // divide the value with the wirecount
    for (int i = 0; i < maxRow; i++) {
        for (int j = 0; j < maxCol; j++) {
            Tile t = tiles[i][j];
            if (!(t.getTileTypeEnum() == TileTypeEnum.INT)) continue;
            int wireCount = t.getWireCount();
            if (wireCount == 0) {
                continue;
            } else {
                routeHeatMap[i][j] /= (double) wireCount;
                switchboxUtilMap[i][j] /= (double) wireCount;
            }
        }
    }

    // for unrouted nets, set the congestion value to 1
    for (Net n : unroutedNets) {
        for (PIP p : n.getPIPs()) {
            Tile t = p.getTile();
            if (t == null) continue;
            routeHeatMap[t.getRow()][t.getColumn()] = 1.0;
        }
    }

    // For each tile, if it is not an INT tile, make it share the same congestion value as the INT tile
    Set<TileTypeEnum> tileTypes = new HashSet<TileTypeEnum>();
    tileTypes.add(TileTypeEnum.CLEL_L);
    tileTypes.add(TileTypeEnum.CLEL_R);
    tileTypes.add(TileTypeEnum.CLEM);
    for (int i = 0; i < maxRow; i++) {
        for (int j = 0; j < maxCol; j++) {
            Tile t = tiles[i][j];
            TileTypeEnum tileType = t.getTileTypeEnum();

            // skip for the INT tile and the non-CLB tile
            if (tileType == TileTypeEnum.INT || !tileTypes.contains(tileType)) continue;

            Site [] sites = t.getSites();
            if (sites.length == 0) continue;

            Tile intTile = sites[0].getIntTile();
            if (intTile == null) continue;

            routeHeatMap[i][j] = routeHeatMap[intTile.getRow()][intTile.getColumn()];
            switchboxUtilMap[i][j] = switchboxUtilMap[intTile.getRow()][intTile.getColumn()];
        }
    }
    System.out.println("Route Heat Map files generated.");
}

The partial visualization of the routeHeatMap is:

However, I think the result of the routeHeatMap might be too pessimistic because I mark 1 for all PIP in unrouted net.

If there's any suggestion or bug in the above code snippet, please point out and let me know it, thanks in advance!!

[coherent17]

Not sure if I correctly understood the net being partial routed due to site pin conflict.
The router in Vivado will try its best to minimize the wire length and also try to meet the user timing constraint settings.

For those partial routed net with site pin conflict, I discover that some of the PIP from this net in the INT-tile are routed, but some of them are shown as the fly line in Vivado points to the site pin.

Is there a better way to estimate those route heat map (routing congestion) with partial routed net routing demand in RapidWright?

Thanks

[eddieh-xlnx]

Thanks for sharing your use case @coherent17. Let me first make sure I understand what you're saying:

I'm now implementing a tool that takes a DCP(might be fully routed, or partial routed due to site pin conflict)

Are you saying that the only reason a net is partially routed would be due to a site pin conflict? Are you expecting to see other issues like non-site-pin node conflicts on an otherwise fully-routed net, or antennas where the net does not even reach the site pin?

However, in the PR #1145, didn't consider the partial routed net, so that the route heat map reported might be too optimistic since for some partial routed net, the PIP didn't actually occupy the INT-tile.

My understanding is that #1145 merged the following code:

RapidWright/src/com/xilinx/rapidwright/router/RoutingHeatMap.java

Lines 50 to 56 in 790066a

	for (Net n : d.getNets()) {
	for (PIP p : n.getPIPs()) {
	if (p.getTile().getTileTypeEnum() == TileTypeEnum.INT) {
	heatMap.merge(p.getTile(), 1, Integer::sum);
	}
	}
	}

which analyzes all INT-tile PIPs on all nets -- regardless of if they form a full or partial route. The routed state of a net shouldn't matter. However, you're correct in that the above code skips all PIPs that are outside of an INT tile -- which is where we would expect to see almost all routing congestion -- are you seeing otherwise?

Are the following two images of the same SLR from the same design, and that you are working to align?

Not sure if I correctly understood the net being partial routed due to site pin conflict.

For those partial routed net with site pin conflict, I discover that some of the PIP from this net in the INT-tile are routed, but some of them are shown as the fly line in Vivado points to the site pin.

Can you give an example of a site-pin conflict that you're seeing? I've seen cases where a router may choose to connect two nets to the "A1" site pin, but clearly only one of those nets will be able to win out. The net that wins will not have a flyline since it is correctly routed (but with conflicts) but the other net will lose out and will be shown as a flyine. Is this what you're seeing?

Is there a better way to estimate those route heat map (routing congestion) with partial routed net routing demand in RapidWright?

I'd like to understand what you mean by "partial routed net" before I can give you a good answer here. What do you plan to use this routing congestion map for? For example, it's possible to generate a design (e.g. by hand) site pin conflicts in a tile that only has low routing utilization; typically though, there is likely a correlation between PIP utilization and site pin conflict in that tile. Is that what you're trying to identify?

[eddieh-xlnx]

In my past experience, the value in the row # of nets with some unrouted pins is always the same as the value in the row # of nets with antennas/islands.

I think that makes sense for the Vivado router -- it will try and connect everything up even if it causes a site pin conflict. For site pin conflicts though, only one net will "win" and the others will be treated as partially routed pins with antennae, showing as flylines.

I'm curious if almost all routing congestion are contributed from the CLB-tile? Will INT-tile switchbox encounter the congestion?

INT tiles serve two purposes -- allow a signal to enter/exit a CLE tile (which is the only one way for the CLE to be accessed, so it makes sense that the CLE inherits the interconnect density of its neigbouring INT tile) as well as allow inter-INT tiles to serve as a "stop" for switching between inter-tile nodes (e.g. for a north node to turn east). Both of these are lumped together into one density figure.

Besides, if there exist a model that takes placement info and predict the route heat map.

It looks like Vivado might have such a heatmap. For "Interconnect Density" you have the option to examine the "Estimated" or "Routing" density. The implication is that "estimated" shows that what you're asking for might be possible.

That's all I've got for now; I'm still in the process of understanding/thinking more about/experimenting on what you're trying to achieve so I'll add more when it comes to me. Hopefully the above helps for now.

Thanks!

[coherent17]

Hi Eddie,

For "Interconnect Density" you have the option to examine the "Estimated" or "Routing" density. The implication is that "estimated" shows that what you're asking for might be possible.

Can you share more insight on the difference of "Estimated" & "Routing" density result? Where can I get those result? So far as I know report_design_analysis -congestion Vivado TCL command will report the congestion level for the FPGA in place final & router initial stages. For example, the congestion level 5 equals there's a region with 32x32 (2^5) reported as congested region. Does this report the same as you mentioned above?

Thanks for all your effort!! It helps a lot on these discussions!!

[coherent17]

Hi @eddieh-xlnx,

Can you help me to understand the main reason of site pin conflict error in Vivado?

I found out these sentences in AMD documentation:

Site pin conflict: The logical net that is connected to the given site pin from inside the site is different from the logical net that is connected via the route to the outside of the site.

In the below image, the red net connects to the site pin in intra routing, but the blue net connects to the site pin in the inter routing. Is that correct understanding?

1. Why Vivado router tends to connect 2 different nets to the same site pin?

2. Not sure if I correct understanding the switchbox node attribute. If there exists the 1-to-1 mapping between the node in switchbox with the site pin in nearby CLB tile? If yes, since route-through pip inside the switchbox will not occupy those nodes, why site pin conflict happens in this case?

Thanks in advance!

[eddieh-xlnx]

Hi @coherent17. Sorry for the late reply.

Can you share more insight on the difference of "Estimated" & "Routing" density result? Where can I get those result?

I'm afraid I don't have any more information that in UG906: https://docs.amd.com/r/en-US/ug906-vivado-design-analysis/Congestion-Metrics-for-UltraScale-and-Newer-Device-Families

1. Why Vivado router tends to connect 2 different nets to the same site pin?

It's my understanding that this situation occurs because the Vivado router was not able to find error-free route for all nets in the design. In those cases, it will show you the solution that it did find -- which is blue net to D1 and red net to D3.

Now, a legal solution may exist here if you were to perform LUT pin swapping (a legitimate optimization that the Vivado router does) so that the blue net goes all the way through D1 to the DLUT6.A1 pin, and the same for red net through D3 to A3. I assume the Vivado router doesn't bother with this final step because it still won't lead to a legal solution -- perhaps the blue and/or red net have conflicts elsewhere, or other nets have conflicts.

If you want to try fixing this manually -- select the cell inside Vivado, and then go to the "Cell Pins" tab. Here, you can manually reassign pins which will also update the intra-site routing. This may fix "site pin conflict" issue, but may not fix other errors on these nets, or indeed other errors/conflicts for the rest of the design.

2. Not sure if I correct understanding the switchbox node attribute. If there exists the 1-to-1 mapping between the node in switchbox with the site pin in nearby CLB tile? If yes, since route-through pip inside the switchbox will not occupy those nodes, why site pin conflict happens in this case

There is a 1-to-1 mapping between nodes in the INT tile and CLB site pins. By "route-through PIPs" I think you're referring to PIPs that connect together nodes that enter and leave the tile. Outside of those, I think your question is for PIPs that connect together nodes that enter the tile but then (eventually) connect to the CLE, right?

As I stated above, site pin conflicts may simply exist because the Vivado router knows that it cannot find a valid solution and does not do all the "cleanup" that it would otherwise do.

[coherent17]

Hi @eddieh-xlnx.

Thanks for sharing your insight for the site pin conflict & swiitchbox node property. I'm now have more understanding on these issues!! As for the route heat map, I will go with Chris's PR #1145 to calculate the PIP utilization rate inside the switchbox!

I have no question now, thanks for your answer and patience!!!

Thanks,
Coherent