Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
An algorithm for integrated pin assignment and buffer planning
Xiang H., Tang X., Wong M. ACM Transactions on Design Automation of Electronic Systems10 (3):561-572,2005.Type:Article
Date Reviewed: Nov 30 2005

With a drastic reduction in minimum feature sizes, interconnects are dominating deep sub-micron very large-scale integration (VLSI) physical design. As such, several techniques have evolved to reduce the interconnect delay. One effective and often-used method for reducing the interconnect delay is the use of buffers. It is estimated that the number of inserted buffers for an on-chip interconnect may be up to 800,000 in 50-nanometer (nm) technology. The use of buffers yields many challenging problems in physical design. Buffers are often grouped together as buffer blocks for convenience in floorplanning and routing. A related problem is the assignment of the locations of pins on macro blocks.

For an initial placement of macro and buffer blocks, this paper considers the simultaneous assignment of pins and planning buffer insertions for a given set of nets, such that the distance between two buffers, or two pins, or a pin and a buffer, is within a range. Buffer planning determines buffer usage along net connections to maintain required delay constraints. A composite cost function, &agr; · W + &bgr; · R, is considered for any positive constants &agr; and &bgr;, where W is the total wire length, and R is the number of buffers.

The problem is mapped into a minimum cost network flow problem, and a polynomial-time algorithm is proposed for simultaneous pin assignment and buffer planning for all two-pin nets. One macro block is considered as the source block, and all other blocks are considered as sink blocks. This basic algorithm is then iteratively applied, each time considering one block as the source block, and the remaining blocks as the sink blocks. This yields a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. For larger circuits, in order to keep the problem within a manageable size and to speed up the computation, node clustering-based preprocessing is used.

The algorithms were implemented in C++ on a PC, and compared with a two-step procedure where pin assignment was followed by buffer planning, using some randomly generated test cases. Results demonstrate the effectiveness of the proposed algorithm. For node clustering, the running time of the algorithm was reduced to a large extent, with minor degradation of the solution quality in terms of increased wire length, and larger numbers of buffers used.

Reviewer:  Parthasarathi Dasgupta Review #: CR132102 (0606-0602)
Bookmark and Share
 
Placement And Routing (B.7.2 ... )
 
 
Computer-Aided Design (CAD) (J.6 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Placement And Routing": Date
A 2d channel router for the diagonal model
Lodi E., Luccio F., Song X. Integration, the VLSI Journal 11(2): 111-125, 1991. Type: Article
Aug 1 1992
Tree placement in Cascode-switch macros
Sarrafzadeh M. Integration, the VLSI Journal 11(2): 127-139, 1991. Type: Article
Oct 1 1992
VYUHA
Ravikumar C., Sastry S. Integration, the VLSI Journal 11(2): 141-157, 1991. Type: Article
Aug 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy