Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-01-12
2009-08-04
Chiang, Jack (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
07571411
ABSTRACT:
A method of producing a flexible timing-driven routing tree is provided. Two or more target nodes are sorted in accordance with data criticality. A source-sink grid is built from one or more source nodes and the two or more target nodes. An initial routing tree is built comprising the one or more source nodes. A routing tree generation algorithm is executed on the initial routing tree, utilizing the sorted two or more target nodes and the source-sink grid in accordance with a user-defined timing factor to construct a flexible timing-driven routing tree. The user-defined timing factor specifies an extent of isolation for a routing path from a given one of the one or more source nodes to a given one of the two or more target nodes.
REFERENCES:
patent: 6898774 (2005-05-01), Alpert et al.
patent: 6952813 (2005-10-01), Rahut
patent: 7010767 (2006-03-01), Elassaad et al.
C.J. Alpert et al., “Fast and Flexible Buffer Trees that Navigate the Physical Layout Environment,” Proc. of the 41stDAC, pp. 24-29, Jun. 2004.
C.J. Alpert et al., “Prim-Dijkstra Tradeoffs for Improved Performance-Driven Routing Tree Design,” IEEE Trans On Computer-Aided Design of Integrated Circuits and Systems, vol. 14, No. 7, pp. 1-17, Jul. 1995.
K.D. Boese et al., “Near-Optimal Critical Sink Routing Tree Constructions,” IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, vol. 14, No. 12, pp. 1-40, Jul. 1995.
M. Borah et al., “An Edge-Based Heuristic for Steiner Routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, No. 12, pp. 1563-1568, Jul. 1994.
J. Cong et al., “Efficient Algorithms for the Minimum Shortest Path Steiner Arborescence Problem with Applications to VLSI Physical Design,” IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, vol. 17, Issue 1, pp. 24-39, Jan. 1998.
J. Cong et al., “Provably Good Performance-Driven Global Routing,” IEEE Transactions on Computer-Aided Design, vol. 11, No. 6, pp. 739-752, Jun. 1992.
J.-M. Ho et al., “New Algorithms for the Rectilinear Steiner Tree Problem,” IEEE Transactions on Computer-Aided Design, vol. 9, No. 2, pp. 185-193, Feb. 1990.
X. Hong et al., “Performance-Driven Steiner Tree Algorithms for Global Routing,” Proc. of the 30thACM/IEEE Design Automation Conference, pp. 177-181, Jun. 1993.
S.-W. Hur et al., “Timing-Driven Maze Routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 19, No. 2, pp. 234-241, Feb. 2000.
S. Prasitjutrakul et al., “A Timing-Driven Global Router for Custom Chip Design,” Proc. of the Int. Conf. on Computer-Aided Design, pp. 48-51, Nov. 11-15, 1990.
K. Suzuki et al., “A Hardware Maze Router with Application to Interactive Rip-Up and Reroute,” IEEE Transactions on Computer-Aided Design, vol. CAD.-5, No. 4, pp. 466-476, Oct. 1986.
M. Johann et al., “A New Bidirectional Heuristic Shortest Path Search Algorithm,” International ICSC Congress on Artificial Intelligence and Applications, Australia, 7 pages, Dec. 2000.
H.J. Xu et al., “An Efficient Hierarchical Timing Driven Steiner Tree Algorithm for Global Routing,” Proc. Of the ASP-DAC, 6 pages, 2002.
de Luz Reis Ricardo Augusto
Hentschke Renato Fernandes
Johann Marcelo de Oliveira
Narasimhan Jagannathan
Chiang Jack
International Business Machines - Corporation
Ryan & Mason & Lewis, LLP
Tat Binh C
Verminski Brian P.
LandOfFree
Methods and apparatus for providing flexible timing-driven... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for providing flexible timing-driven..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for providing flexible timing-driven... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4058001