| 摘要 |
<p>A method for optimal track assignment in a grid-based channel router. Initially, interconnection information is extracted from a global routing result. Multiple pin nets derived from the interconnection information are decomposed into simpler mapped segments. A channel grip map is then built and marked with existing objects. Next, a vertical constraint graph specifying the relative positions of the mapped segment is constructed. A first track is computed. A track assignment loop is repeated until all requisite connections are realized. The track assignment loop includes the steps of breaking cycles and long paths and collecting a set of feasible links. One or more weighting functions are assigned to each such feasible link. A dynamic programming approach is used to select an optimal set of feasible links according to the weighting functions. In addition, an optimal set of feasible links corresponding to unpreferred layers is collected by applying dynamic programming. Finally, the chosen feasible links are physically realized on the current track.</p> |
