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, but is in effect a hybrid method (described below). 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.
Graphic visualization of routing in qrouter 1.2. The design routed is i2c_master_top from Open Cores.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.
Because the maze algorithm is inefficient and compute-intensive, qrouter uses a hybrid method in which it first determines an optimal trunk-and-branches route, and then creates a mask from this route, encompassing an area expanded outward from the optimal route choice by a few tracks in every direction. Additional possible good route options, such as short-cuts between branches, are added to the mask. The maze algorithm is limited to this mask area, making it much more efficient. Searching is prioritized along the preferred direction for each metal layer, also increasing the route algorithm's efficiency. The route search is done in a number of passes. If a route cannot be found within the mask area, the mask is expanded outward by one track and the expanded area is searched. In the worst case, the mask can be ignored, in which case the maze algorithm runs in its "pure" form. In general, route scripts avoid doing this except as a last resort.
In the "standard" route script, routing is completed in three 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. In the third stage, each net is ripped up and rerouted by itself, which cleans up routing inefficiencies caused by multiple cycles of ripping up and rerouting in the second stage.
The "standard" route script is designed to provide the most likely best sequence of route stages and parameters. Normally, there will not be any need to change the script. However, it is always possible that pathological cases may require a custom script. Each route stage in qrouter is a Tcl command (see the reference documentation), and these can be arranged into a custom script and passed to qrouter as an option. Also, qrouter can be run interactively, with route stages entered on the command line in the console. Each route stage is run independently, so many different combinations of stages and parameters can be attempted interactively. Graphic visualization of the route solution provides feedback to the interactive routing process.
Because the input and output formats qrouter uses 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). This means you are free to alter it, distribute it, and so forth, under the generous license terms, but it must always remain open source and must credit the developer. By accepted convention of open source development, bug fixes and new features should be sent to the developer for review and incorporation into the distribution, if deemed appropriate. Contributors should acknowledge their own work in the source code, and will be acknowledged in the code history (git commit record).
Qrouter is recommended to be used with qflow, which combines a number of open source tools to provide a complete synthesis toolchain for digital synthesis. However, qrouter uses only industry-standard format files and so may be used as a standalone router. Qrouter does not attempt to do any adjustment of the placement, so its solution can only be as good as the placement allows. For large designs (several thousand standard cells or more), it is usually possible to create an unroutable placement simply by clustering dense combinational logic together. Such an arrangement is simply physically unroutable. If qrouter gets to the end and dumps a list of failed routes, it means that the placement is too dense and should be padded with fill cells to decrease the density.
Detail of a layout generated by qrouter.
| email: | 
|
Last updated: August 8, 2017 at 9:46am