Describes two linear-time river-routing algorithms for respectively optimizing and computing channel separation between the interior rows and columns of synthesized random-logic cells for custom module generation. The method uses river routing within the cells to virtually eliminate routing channels between the cell rows and columns while producing little or no increase in cell area. The first algorithm is a terminal-position assignment procedure that can be used in conjunction with the optimal-placement-for-river-routing algorithm given by C.E. Leiserson and R.Y. Pinter (see SIAM J. Computing, vol.12, no.3, p.447-462, 1983) to eliminate, or greatly reduce, the routing area that is computed by the second proposed algorithm. The second algorithm computes embedded river-routing channel separations between the rows and columns of cells. Use of these algorithms for optimizing the interconnections between custom-synthesized cells provides a significant improvement in area usage in comparison with using standard river routing methods.>

This paper describes a switchbox-type router for custom VLSI module generation as performed by a module planner. A module is decomposed into abstract cells consisting of global routes and Boolean functional specifications. Each abstract cell is given to a cell synthesizer which generates the circuit layout and through-the-cell routing. Abstract routing for a module planner is in some sense similar to switchbox routing to the degree that all of the routes are generated internally within a rectangular boundary (routes are coming from four sides). The principle difference with respect to standard switchbox routing is at the geometric level, where a cell synthesizer generates the routing conduction layers along with circuit devices for each abstract cell within this rectangular region. The aspects of this paper which are thought to be novel contributions are 1) a relative pin assignment algorithm for the abstract cells; 2) a global routing penalty function which not only considers previous routes, but also considers gate complexity within the cells; 3) an efficient optimization algorithm for minimizing the number of tracks running through the module.

This paper describes a module compiler for decomposing arbitrary functional units of any complexity into abstract cells for customized VLSI layouts. The compiler takes the description of a functional unit as input and builds a dependence graph representation. The graph is then partitioned and the nodes are packed into abstract cell output descriptions. The algorithm will tailor the design to a given area and aspect ratio. Routing is done automatically through the cells.