Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-11-14
2006-11-14
Whitmore, Stacy A. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
07137081
ABSTRACT:
A method, apparatus, and computer program product for performing density biased buffer insertion in an integrated circuit design are provided. A tiled Steiner tree topology map is used in which density values are associated with each tile in the map. A directed acyclic graph (DAG) is created over an initial set of potential candidate points. A subset of the candidate points is selected by associating costs with each tile, and with each path or edge, to each tile. The total costs associated with placement of a buffer at a position within each tile are calculated. The lowest cost tile is then selected as a candidate position for buffer insertion. This process is then repeated to obtain an asymmetrically distributed set of candidate buffer insertion points between a source and a sink.
REFERENCES:
patent: 6314547 (2001-11-01), Donath et al.
patent: 6401234 (2002-06-01), Alpert et al.
patent: 6487697 (2002-11-01), Lu et al.
patent: 6819538 (2003-12-01), Alpert et al.
patent: 6678871 (2004-01-01), Takeyama et al.
patent: 6725438 (2004-04-01), van Ginneken
patent: 6898774 (2005-05-01), Alpert et al.
patent: 6925624 (2005-08-01), Komoda
patent: 6996512 (2006-02-01), Alpert et al.
patent: 7062743 (2006-06-01), Kahng et al.
patent: 2002/0184607 (2002-12-01), Alpert et al.
patent: 2004/0216072 (2004-10-01), Alpert et al.
Liu et al., “An efficient buffer insertion algorithm for large networks based on Lagrangian relaxation”, Oct. 10-13, 1999, Computer Design, 1999. (ICCD '99) International Conference on, pp. 210-215.
Lu et al., “Interconnect planning with local area constrained retiming logic IC layout”, 2003, Design, Automation and Test in Europe Conference and Exhibition, pp. 442-447.
Zhou et al, “Simultaneous Routing and Buffer Insertion with Restrictions on Buffer Location”, IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, vol. 19, No. 7, Jul. 2000, pp. 819-824.
Gupta et al, “The Elmore Delay as a Bound for RC Trees with Generalized Input Signals”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, No. 1, Jan. 1997, pp. 95-104.
Cong et al., “Routing Tree Construction Under Fixed Buffer Locations”, ACM Digital Library, 2000, pp. 379-384.
Tang et al., “A New Algorithm for Routing Tree Construction with Buffer Insertion and Wire Sizing Under Obstacle Constraints”, University of Texas at Austin, Austin, TX, IEEE, 2001, pp. 49-56.
Jagannathan et al., “A Fast Algorithm for Context-Aware Buffer Insertion”, ACM Digital Library, 2000, pp. 368-373, Dec. 7, 2003.
Cormen et al., “Interval Trees”, Introduction to Algorithms, MIT Press, 2001, pp. 311-316, Dec. 7, 2003.
Hrkic et al., “Buffer Tree Synthesis with Consideration of Temporal Locality, Sink Polarity Requirements, Solution Cost and Blockages”, University of Illinois at Chicago, CS Dept., Chicago, IL 60607, ISPD 2002, pp. 98-103, Dec. 7, 2003.
Hu et al., “Buffer Insertion with Adaptive Blockage Avoidance”, ISPD 2002, San Diego, CA, USA, pp. 92-97.
Hrkic et al., “S-Tree: A Technique for Buffered Routing Tree Synthesis”, University of Illinois at Chicago, CS Dept., Chicago, IL 60607, DAC 2002, pp. 578-583, Dec. 7, 2003.
Donath et al., “Transformational Placement and Synthesis”, International Business Machines Corporation, Abstract, 8 pages, 2003.
Hrkic et al., “Buffer Tree Synthesis With Consideration of Temporal Locality, Sink Polarity Requirements, Solution Cost, Congestion, and Blockages”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, No. 4, Apr. 2003, pp. 481-491.
Alpert et al., “Porosity-Aware Buffered Steiner Tree Construction”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 23, No. 4, Apr. 2004, pp. 517-526.
Sze et al., “A Place and Route Aware Buffered Steiner Tree Construction”, IEEE, 2004, pp. 355-498.
Alpert et al., “Steiner Tree Optimization for Buffers, Blockages, and Bays”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, No. 4, Apr. 2001, pp. 556-562.
Alpert et al., “Buffered Steiner Trees for Difficult Instances”, International Symposium on Physical Design, Apr. 2001, pp. 4-8.
Alpert et al., “Wire Segmenting for Improved Buffer Insertion”, IEEE/ACM DAC, 1997, pp. 588-593.
Alpert et al., “Buffer Insertion for Noise and Delay Optimization”, IEEE/ACM DAC, 1998, pp. 362-367.
Alpert et al., “Buffer Insertion with Accurate Gate and Interconnect Delay Computation”, IEEE/ACM DAC, 1999, pp. 479-484.
Alpert et al., “Porosity Aware Buffered Steiner Tree Construction”, International Symposium on Physical Design, Apr. 2003, pp. 158-165.
Lai et al., “Maze Routing with Buffer Insertion and Wiresizing”, IEEE/ACM DAC, 2000, pp. 374-378.
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.
Lillis et al., “Simultaneous Routing and Buffer Insertion for High Performance Interconnect”, Sixth Great Lakes Symposium on VLSI, 1996, pp. 148-153.
Okamoto et al., “Buffer Steiner Tree Construction with Wire Sizing for Internconnect Layout Optimization”, IEEE/ACM Int. Conf. Computer-Aided Design, 1996, pp. 44-49.
van Ginneken, “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay”, Intl. Symposium on Circuits and Systems, 1990, pp. 865-868.
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.
Cormen et al., “Introduction to Algorithms, Second Edition”, MIT Press, 2001, pp. 549-552.
Cong, “Challenges and Opportunities for Design Innovations in Nanometer Technologies”, SRC Working Papers, Dec. 1997, pp. 1-15.
Cong et al., “Buffer Block Planning for Interconnect-Driven Floorplanning”, IEEE/ACM Intl. Conf. on Computer-Aided Design, 1999, pp. 358-363.
Dhar et al., “Optimum Buffer Circuits for Driving Long Uniform Lines”, IEEE Journal of Solid-State Circuits, vol. 26, No. 1, Jan. 1991, pp. 32-40.
Gao et al., “A Graph Based Algorithm for Optimal Buffer Insertion Under Accurate Delay Models”, Design Automation and Test in Europe, 2001, pp. 535-539.
Saxena et al., “The Scaling Challenge: Can Correct-by-Construction Design Help?”, Proc. Intl. Symposium on Physical Design, 2003, pp. 51-58.
Shi et al., “An O(nlogn) Time Algorithm for Optimal Buffer Insertion”, IEEE/ACM DAC, 2003, pp. 580-585.
10.4 Downhill Simplex Method in Multidimensions, Chapter 10 Minimization or Maximization of Functions, Numerical Recipes in C: the Art of Scientific Computing, Copyright 1998-1992, pp. 408-412.
Bhola et al., “Exactly-once Delivery in a Content-based Publish-Subscribe System”, Proc. of the Intl Conf. on Dependable Systems and Networks, 2002 IEEE, 10 pages.
Corana et al., “Minimizing Multimodal Functions of Continuous Variables with the “Simulated Annealing” Algorithm”, ACM Transactions on Mathematical Software, vol. 13, No. 3, Sep. 1987, pp. 262-280.
Barton et al., “Modifications of the Nelder-Mead Simplex Method for Stochastic Simulation Response Optimization”, Proc of the 1991 Winter Simulation Conf., pp. 945-953.
Swisher et al., “A Survey of Simulation Optimization Techniques and Procedures&#x
Alpert Charles Jay
Hrkic Milos
Quay Stephen Thomas
Bailey Wayne P.
Salys Casimer K.
Whitmore Stacy A.
Yee Duke W.
LandOfFree
Method and apparatus for performing density-biased buffer... 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 performing density-biased buffer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing density-biased buffer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3660105