Porosity aware buffered steiner tree construction

Details Porosity aware buffered steiner tree construction Porosity aware buffered steiner tree construction

2006-06-20

2006-06-20

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

07065730

ABSTRACT:
A method, computer program product, and data processing system for porosity-aware buffered Steiner tree construction are disclosed. A preferred embodiment begins with a timing-driven Steiner tree generated without regard for porosity, then applies a plate-based adjustment guided by length-based buffer insertion. After performing localized blockage avoidance, the resulting tree is then passed to a buffer placement algorithm, such as van Ginneken's algorithm, to obtain a porosity-aware buffered Steiner tree.

REFERENCES:
patent: 6401234 (2002-06-01), Alpert et al.
patent: 6442745 (2002-08-01), Arunachalam et al.
patent: 6519745 (2003-02-01), Srinivas et al.
patent: 6557145 (2003-04-01), Boyle et al.
patent: 2003/0188286 (2003-10-01), Teig et al.
patent: 2004/0123261 (2004-06-01), Alpert et al.
Hrkic et al., “Buffer Tree Synthesis with Consideration of Temporal Locality, Sink Polariy Requirements, Solution Cost, Congestion, and Blockages,” IEEE, Apr. 23, 2003, pp. 481-491.
Alpert et al., “Porisity-Aware Buffered Steiner Tree Construction,” Apr. 2004, pp. 517-526.
Alpert et al., “Buffer Insertion with Adaptive Blockage Avoidance,” IEEE, Apr. 2, 2003, pp. 492-498.
Sze et al., “A Place and Route Aware Buffered Steiner Tree Construction,” IEEE, 2004, pp. 355-498.
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.
van Ginneken, “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay”, International Business Machines Corporation, Abstract, pp. 865-868.
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.
Alpert et al., “Buffer Insertion with Accurate Gate and Interconnect Delay Computation”, International Business Machines Corporation, Abstract, pp. 479-484.
Alpert et al., “Wire Segmenting for Improved Buffer Insertion”, IBM Austin Research Laboratory, Austin, Texas, Abstract, pp. 588-593.
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.
Cong et al., “Buffer Block Planning for Interconnect-Driven Floorplanning”, Department of Computer Science, University of California, Los Angeles, CA, Abstract, pp. 358-363.
Alpert et al., “Buffer Insertion for Noise and Delay Optimization”, International Business Machines Corporation, Abstract, pp. 362-367.
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.
Lai et al., “Maze Routing with Buffer Insertion and Wiresizing”, ACM Digital Library, 2000, pp. 374-378.
Jagannathan et al., “A Fast Algorithm for Context-Aware Buffer Insertion”, ACM Digital Library, 2000, pp. 368-373.
Lillis et al., “Simultaneous Routing and Buffer Insertion for High Performance Interconnect”, University of California, San Diego, La Jolla, CA, IEEE 1996, pp. 148-153.
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-13.
Cormen et al., “Interval Trees”, Introduction to Algorithms, MIT Press, 2001, pp. 311-316.
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.
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.
Donath et al., “Transformational Placement and Synthesis”, International Business Machines Corporation, Abstract, pp. 1-8.
Alpert et al., “A Practical Methodology for Early Buffer and Wire Resource Allocation”, International Business Machines Corporation, Abstract, pp. 189-194.
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.
U.S. Appl. No. 10/324,732, Alpert et al., Buffer Insertion with Adaptive Blockage Avoidance, filed Dec. 18, 2002.
U.S. Appl. No. 10/264,165, Alpert et al., Optimal Buffered Routing Path Constructions for Single and Multiple Clock Domain Systems, filed Oct. 3, 2002.
Alpert et al., “Porosity Aware Buffered Steiner Tree Construction”, ISPD'03 Monterey California 2003, ACM Digital Library 2003, pp. 1-8.

Affiliated with

Also associated with

Rating

Porosity aware buffered steiner tree construction does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Porosity aware buffered steiner tree construction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Porosity aware buffered steiner tree construction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3683736