Method for optimizing track assignment in a grid-based channel r

Details Method for optimizing track assignment in a grid-based channel r Method for optimizing track assignment in a grid-based channel r

1996-03-12

1998-11-24

Teska, Kevin J.

Boots, shoes, and leggings

364488, 364489, 364491, G06F 1700, G06F 1550

Patent

active

058416641

ABSTRACT:
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 grid map is then built and marked with existing objects. Next, a vertical constraint graph specifying the relative positions of the mapped segments 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.

REFERENCES:
patent: 4615011 (1986-09-01), Linsker
patent: 5272645 (1993-12-01), Kawakami et al.
patent: 5375069 (1994-12-01), Sato et al.
Tong Gao & L. Liu. "Minimum Crosstalk Channel Routing". Jul. 11, 1993. Urbana, Il.
Peter M. Maurer. "Automatic Routing of Integrated Circuit Connections: A Tutorial". Apr. 15, 1990. Tampa, Fl.
C.-L. Tse and W. Kinsner. "A graph-based heuristic channel router." Sep. 1988. Amsterdam, The Netherlands.
Howard H. Chen. "Breaking Cycles and Vertical Constraints in Deutsch's New and More Difficult Channel-Routing Problems." Aug. 14, 1989. Yorktown Heights, NY.
T.W. Her & D.F. Wong. "On Over-the-Cell Channel Routing with Cell Orientations Consideration." Jun. 1, 1995. NY.
P. Saratachandran "Dynamic Programming Approach for Multilayers Neural Network Optimization," IEEE, pp. 1397-1402, Jul. 1991.

Affiliated with

Also associated with

Rating

Method for optimizing track assignment in a grid-based channel r does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for optimizing track assignment in a grid-based channel r, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimizing track assignment in a grid-based channel r will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1710172