Qrouter is a tool to generate metal layers and vias to physically connect together a netlist in a VLSI fabrication technology. It is a maze router, otherwise known as an "over-the-cell" router or "sea-of-gates" router. That is, unlike a channel router, it begins with a description of placed standard cells, usually packed together at minimum spacing, and places metal routes over the standard cells.
Qrouter uses the open standard LEF and DEF formats as file input and output. It takes the cell definitions from a LEF file, and analyzes the geometry for each cell to determine contact points and route obstructions. It then reads the cell placement, pin placement, and netlist from a DEF file, performs the detailed route, and writes an annotated DEF file as output.
Qrouter is based on the standard Lee maze router algorithm. The area to route is partitioned into a 2-dimensional grid of routing tracks, with all routing confined to the track position (with the exception of terminal connections to the standard cell, which may require positioning off-grid to avoid design rule violations). A source and target node to route are identified, then a flood-fill (or "wave propagation") method works outward from the source, avoiding obstructions and calculating a cost to reach each position. The path that reaches the target node with the lowest cost is then traced back to the source node, and the route is committed to memory. The grid positions used by the route become obstructions for future routes on other nets, or they become additional source or target nodes for further routing of the same network.
The Lee algorithm has been slightly modified to handle networks with more than two nodes efficiently. Instead of choosing two nodes from the network to route on each pass, one node is chosen as source and all other nodes are treated as potential targets. The Lee algorithm proceeds as usual from the source node to all target nodes. At the end of routing, the lowest cost path to any target node is chosen. Only then is the actual target node identified. The path is committed, the routed target becomes part of the source node, and the process repeats until all targets have been routed.
Routing is completed in two stages. The first stage attempts a simple routing of each net, and nets that fail to route are recorded in a list. In the second stage, each failed route is routed again while allowing the route to short other nets. The nets that are shorted are removed so that the route may be completed, and the removed routes are added to the list of failed routes. This process continues until all nets have been routed. To avoid infinite loops in this process, the same sequence of rip-up and re-route for two nets is not allowed to happen twice.
Because input and output formats are open standards, qrouter should be compatible with most fabrication processes. Process vendors generally supply standard cell definitions in a compatible LEF file, and most EDA layout tools can read the output DEF file with the detailed routing geometry.
Qrouter is provided to the public as open-source software under the GNU public license (GPL).
Graphic visualization of routing in qrouter 1.2. The design routed is i2c_master_top from Open Cores.
Detail of a layout generated by qrouter.
Last updated: August 5, 2016 at 7:14pm