Unroutable connection on SymbiFlow tests

[acomodi]

Expected Behaviour

Routing passes correctly.

Current Behaviour

Routing fails to find a connection between SOURCE and SINK.

## Initializing router criticalities took 0.02 seconds (max_rss 654.6 MiB, delta_rss +0.0 MiB)
---- ------ ------- ---- ------- ------- ------- ----------------- --------------- -------- ---------- ---------- ---------- ---------- --------
Iter   Time    pres  BBs    Heap  Re-Rtd  Re-Rtd Overused RR Nodes      Wirelength      CPD       sTNS       sWNS       hTNS       hWNS Est Succ
      (sec)     fac Updt    push    Nets   Conns                                       (ns)       (ns)       (ns)       (ns)       (ns)     Iter
---- ------ ------- ---- ------- ------- ------- ----------------- --------------- -------- ---------- ---------- ---------- ---------- --------
Warning 62: No routing path for connection to sink_rr 255038, retrying with full device bounding box
Warning 63: No routing path for connection to sink_rr 189168, retrying with full device bounding box
Cannot route from SYN-GND[0].GND[0] (RR node: 103354 type: SOURCE location: (30,27) class: 0 capacity: 1 fan-in: 0 fan-out: 1) to BLK-TL-BRAM_L[0].BRAM_FIFO18_DIADI5[0] (RR node: 189168 type: SINK location: (20,53) class: 43 capacity: 1 fan-in: 1 fan-out: 0) -- no possible path
Failed to route connection from '$false' to 'murax.system_ram.ram_symbol1.0.0.0' for net '$false' (#0)
Routing failed for net 0
# Routing took 2.48 seconds (max_rss 654.6 MiB, delta_rss +0.0 MiB)
Circuit is unroutable with a channel width factor of 500.
For a detailed report on the RR node overuse information (report_overused_nodes.rpt), specify --generate_rr_node_overuse_report on.

Possible Solution

I have tracked down the source of this error being in this piece of code:

vtr-verilog-to-routing/vpr/src/route/rr_graph2.cpp

Lines 1139 to 1181 in 489eb5b

	for (int ipin = 0; ipin < type->num_pins; ++ipin) {
	bool assigned_to_rr_node = false;
	for (e_side side : wanted_sides) {
	for (int width_offset = 0; width_offset < type->width; ++width_offset) {
	int x_tile = x + width_offset;
	for (int height_offset = 0; height_offset < type->height; ++height_offset) {
	int y_tile = y + height_offset;
	if (type->pinloc[width_offset][height_offset][side][ipin]) {
	int iclass = type->pin_class[ipin];
	auto class_type = type->class_inf[iclass].type;
	if (class_type == DRIVER) {
	indices[OPIN][x_tile][y_tile][side].push_back(*index);
	indices[IPIN][x_tile][y_tile][side].push_back(OPEN);
	assigned_to_rr_node = true;
	} else {
	VTR_ASSERT(class_type == RECEIVER);
	indices[OPIN][x_tile][y_tile][side].push_back(OPEN);
	indices[IPIN][x_tile][y_tile][side].push_back(*index);
	assigned_to_rr_node = true;
	}
	} else {
	indices[IPIN][x_tile][y_tile][side].push_back(OPEN);
	indices[OPIN][x_tile][y_tile][side].push_back(OPEN);
	}
	}
	}
	}
	/* A pin may locate on multiple sides of a tile.
	* Instead of allocating multiple rr_nodes for the pin,
	* we just create a rr_node and make it indexable on these sides
	* As such, we can avoid redundant rr_node to be allocated
	* and multiple nets to be mapped to the pin
	*
	* Considering that some pin could be just dangling, we do not need
	* to create a void rr_node for it.
	* As such, we only allocate a rr node when the pin is indeed located
	* on at least one side
	*/
	if (assigned_to_rr_node) {
	++(*index);
	}
	}

More specifically, the issue seems to be due to the one time increase of the index pointer whenever a pin is assigned to an RR node. Previously, the pin could be associated with multiple nodes depending on the four possible sides of the tile.

The flow to generate the RR graph in SymbiFlow is the following:

• Generate a "virtual" RR graph
• Fill the RR graph with all the CHANX/CHANY information with external scripts
• Validate the RR graph and re-generate a real RR graph through VPR.

The issue, I believe, is the fact that the "virtual" RR graph might not contain all the necessary nodes to patch it correctly, ending up in a situation where some of the connections required are now missing, causing the unroutability issue reported above.
This because, instead of increasing the index counter and, as far as I understood, creating a single node for each tile pin's sides, only one node is generated.

By re-allowing the increase of the index for each side of the pin within the tile solved the issue.

Steps to Reproduce

1. Working on trying to pack a reproducible test.

Your Environment

• VTR revision used: Fix inconsistent buffering #1568
• Operating System and version:
• Compiler version:

[acomodi]

@litghost @vaughnbetz FYI.

@tangxifan tagging also you as I see these changes were included in the RR graph fixup PR. Maybe you can have some additional insights on this.

[vaughnbetz]

The prior code wasn't correct for pins that could occur on multiple sides/locations; they were each given their own rr-node rather than having one rr-node with more switches. If symbiflow was relying on the same pin number on different sides / locations on a block being different rr-nodes, the right fix would be to make two different pins for the two distinct inputs. I'm not sure of exactly how symbiflow finds the rr-nodes to which it wants to add connections; perhaps there is a fragility there where it is getting the rr-node index to add connections to in a way that had some implicit assumptions, and hence is not working with the new rr-graph.

[acomodi]

@vaughnbetz Thanks for the insight.

I think I have solved the issue on the symbiflow side, as suggested. Basically, with the local fix in symbiflow, now multiple switches are generated for the same node that is related to a pin that can occur on multiple sides.

I'll need to further test this and make sure that everything is working as supposed.

[github-actions]

This issue has been inactive for a year and has been marked as stale. It will be closed in 15 days if it continues to be stale. If you believe this is still an issue, please add a comment.

[github-actions]

This issue has been marked stale for 15 days and has been automatically closed.