Place and route
This is just a small write-up detailing the place and route algorithm in VSRTL
- Topologically sort the circuit graph - cut at registers/memories to avoid loops
- Place components in equal depth in same column
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.
-
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