An improved model for solving the optimal placement for river-routing problem

摘要

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.