Place and route

This is just a small write-up detailing the place and route algorithm in VSRTL

Placement

• Topologically sort the circuit graph - cut at registers/memories to avoid loops
• Place components in equal depth in same column

Routing

Step 1: Tile generation

Based on the bounding area of all components ("chip rectangle") as well as each component itself, a routing tile graph is generated. This graph is what is used initially to do coarse grained routing, and later, fine grained routing.

• For each component
  • Extrude the line of each edge of the component until it touches either the chip rectangle or another component
  • This provides a set of horizontal and vertical lines within the chip rect. These lines are sorted wrt. their x (vertical) and y (horizontal) positions.
  • Iterating over each combination of these lines, in order, we create the set of rectangles which the lines define. If a rectangle encloses a component, it is ignored. Else, we create a routing tile
• Finally, each routing tile registers itself with its neighbours, creating a sparse grid graph. The sparsity arises from the fact that "holes" exist where a component is present.

Below shows the extrusion of component edges to form tiles:

Below shows all of the tiles created after placement has been performed. Each tile has been labelled with a unique ID and its bounding box is drawn.

Below shows a corresponding sprase grid graph representing the network of tiles.

Step 2: Coarse grained routing

• Find shortest path (A star)
  • The set of adjacent nodes for each vertex in the grid graph is transformed to its flattened butterfly topology representation. By this, adjacent vertices to a vertex are all vertices in the same row and column of a vertex, with equal cost to each vertex. This essentially allows the algorithm to favor long rectilinear jumps (without modifying the cost function of the algorithm) instead of zig-zagging across the diagonal of vertices which has the smallest manhatten distance from source to sink.
• Register routes:
  • All nets are registered to each tile in terms of the direction which they traverse the tile. This increments a counter for each tile for the number of horizontal and vertical routes passing through them. Routes that bend occupy both a horizontal and vertical channel.
• Tile expansion:
  • Tiles are expanded based on the maximum horizontal channel requirement in a row, and maximum vertical channel requirement in a column.
  • Components are then "re-placed" to reflect the new dimensions of the routing tiles

Step 3: Fine grained routing