Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-10-24
2006-10-24
Chiang, Jack (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
07127696
ABSTRACT:
A mechanism for constructing Steiner trees using simultaneous blockage avoidance, delay optimization, and design density management are provided. An initial tiled timing-driven Steiner tree is obtained for an integrated circuit design. The Steiner tree is broken into 2-paths for which plates are generated designated the permissible area in which a Steiner point may migrate. Each 2-path is optimized by calculating a cost for each tile in the plate as a function of an environmental cost, a tile delay cost, and a trade-off value. A minimum cost tile is then selected as the point to which the Steiner point in the 2-path, if any, is to migrate. Once each 2-path is processed in this manner, routing is performed so as to minimize the cost at the source. This process may be iteratively repeated with new trade-off values until all of the nets have zero or positive slew.
REFERENCES:
Hu et al., “Buffer Insertion with Adaptive Blockage Avoidance”, ISPD, Apr. 2002, pp. 92-97.
Apert et al., “Steiner Tree Optimization for Buffers, Blockages, and Bays”, IEEE transaction, Apr. 2001, pp. 556-562.
Hrkic et al., “Buffer Tree Synthesis With consideration of Temporal Locality, Sink Polarity Requirements, Solution Cost, Congestion, and Blockages”, IEEE Transaction vol. 22, Issue 4, Apr. 2003, pp. 481-491.
Alpert et al., “Porosity Aware Buffered Steiner Tree Construction”, ISPD, Apr. 2003, pp. 158-165.
Alpert et al., “Buffered Steiner Trees for Difficult Instances”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, No. 1, Jan. 2002, pp. 3-14.
Alpert et al., “A Practical Methodology for Early Buffer and Wire Resource Allocation”, IEEE/ACM DAC, 2001, pp. 189-195.
Cong, “Challenges and Opportunities for Design Innovations in Nanometer Technologies”, SRC Working Papers, 1997, pp. 1-15.
Cong et al., “Routing Tree Construction Under Fixed Buffer Locations”, IEEE/ACM DAC 2000, pp. 379-384.
Hrkic et al., “S-Tree: A Technique for Buffered Routing Tree Synthesis”, IEEE/ACM DAC 2002, pp. 578-583.
Jagannathan et al., “A Fast Algorithm for Context-Aware Buffer Insertion”, DAC 2000, pp. 368-373.
Lai et al., “Maze Routing with Buffer Insertion and Wiresizing”, IEEE/ACM DAC 2000, pp. 374-378.
Lee, “An Algorithm for Path Connections and Its Applications”, IRE Trans. on Electronic Computers, 1961, pp. 346-365.
Lillis et al., “New Performance Driven Routing Techniques with Explicit Area/Delay Tradeoff and Simultaneous Wire Sizing”, 33th IEEE/ACM DAC 1996, pp. 395-400.
Lillis et al., “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model”, IEEE Journal of Solid-State Circuits, vol. 31, No. 3, Mar. 1996, pp. 437-447.
Otten, “Global Wires Harmful?”, ACM/IEEE ISPD, pp. 104-109, 1998.
Saxena et al., “The Scaling Challenge: Can Correct-by-Construction Design Help?”, Proc. ISPD, 2003, pp. 51-58.
Tang et al., “A New Algorithm for Routing Tree Construction with Buffer Insertion and Wire Sizing under Obstacle Constraints”, IEEE/ACM ICCAD, 2001, pp. 49-56.
van Ginneken, “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay”, Intl. Symposium on Circuits and Systems, 1990, pp. 865-868.
Zhou et al., “Simultaneous Routing and Buffer Insertion with Restrictions on Buffer Locations”, IEEE/ACM DAC, 1999, pp. 96-99.
U.S. Appl. No. 10/418,469, Alpert et al., Porosity Aware Buffered Steiner Tree Construction, Apr. 17, 2003.
U.S. Appl. No. 10/738,714, Alpert et al., Method and Apparatus for Performing Density-Biased Buffer Insertion in an Integrated Circuit Design, Dec. 17, 2003.
Alpert Charles Jay
Gandham Rama Gopal
Hrkic Milos
Quay Stephen Thomas
Chiang Jack
Fay III Theodore D.
International Business Machines - Corporation
Salys Casimer K.
To Tuyen
LandOfFree
Method and apparatus for generating steiner trees using... 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 and apparatus for generating steiner trees using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating steiner trees using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3710480