skip to main content
10.5555/996070.1009967acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
Article

Stable Multiway Circuit Partitioning for ECO

Published: 09 November 2003 Publication History

Abstract

We propose a new stable multiway partitioning algorithm,where stability is defined as an additional quality of a partitioningsolution. The stability of a partitioning algorithm isan important criterion for a partitioning based placement toachieve timing closure through the repetition of the placementprocedure [Invited talk: Important Placement Considerations for Modern VLSI Chips]. Given a previous partitioning result P*on an original netlist hypergraph H* and a partially modifiednetlist hypergraph H, a new cost function with similarityfactor is defined to produce a new partition P on Hwhich is similar to the original partition P*. The proposedalgorithm is the first approach that quantifies the degree ofsimilarity of a current partition to the original partition usingsimilarity cost. Our goal is to build a new partition ina relatively short run time, whose cut quality is not muchdegraded from that of the original partition P* while it preservesas much of the previous groupings in P* as possible.The proposed partitioner is especially beneficial to engineeringchange order (ECO) applications, where partial modificationsof a netlist are handled by the incremental methodologyin a design iteration cycle. Our approach helps ECOplacers maximize the incremental capability since the portionsto be re-placed are minimized. Experimental resultsshow that the proposed algorithm achieves a high qualitypartition comparable to a state-of-the-art multilevel partitionerhMetis [Multilevel k-way hypergraph partitioning], while many portions of the groupings in the previous partition are preserved in the current partition.The tradeoff between similarity and cut quality with respectto a varying similarity coefficient is also shown.

References

[1]
{1} IC placement integrates with other design tasks. EE Times, April, 2003. {Online}. Available: http://www.eetimes.com/story/OEG20030408S0034
[2]
{2} P. Villarrubia. Invited talk: Important Placement Considerations for Modern VLSI Chips. In Proc. ACM International Symposium on Physical Design, 2003.
[3]
{3} C. J. Alpert and A. B. Kahng. Recent directions in netlist partitioning: A survey. Integration, the VLSI Journal, pages 1-81, 1995.
[4]
{4} C. Alpert. The ISPD98 Circuit Benchmark Suite. In Proc. ACM International Symposium on Physical Design, pages 18-25, 1998.
[5]
{5} C.-S. Choy, T.-S. Cheung, and K.-K. Wong. Incremental layout placement modification algorithms. IEEE Trans. Computer-Aided Design, vol. 15, no. 4, pages 437-445, 1996.
[6]
{6} J. Cong and M. Sarrafzadeh. Incremental physical design. In Proc. ACM International Symposium on Physical Design, pages 84-92, 2000.
[7]
{7} J. Crenshaw, M. Sarrafzadeh, P. Banerjee, and P. Prabhakaran. An incremental floorplanner. In Proc. Great Lakes Symposium on VLSI, 1999.
[8]
{8} C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In Proc. ACM/IEEE Design Automation Conference, pages 175-181, 1982.
[9]
{9} G. Karypis, R. Aggarwal, V. Kumar, and S. Sheckhar. Multilevel hypergraph partitioning: Application in VLSI domain. In Proc. ACM/IEEE Design Automation Conference, pages 526-529, 1997.
[10]
{10} G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. In Proc. ACM/IEEE Design Automation Conference, pages 343-348, 1999.
[11]
{11} B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning of electrical circuits. Bell System Technical Journal, vol. 49, no. 2, pages 291-307, 1970.
[12]
{12} Z. Li, W. Wu, X. Hong, and J. Gu. Incremental placement algorithm for standard-cell layout. In Proc. International Symposium on Circuit and Systems, pages 752-759, 2002.
[13]
{13} C.-I. Park and Y.-B. Park. An efficient algorithm for VLSI network partitioning problem using a cost function with balancing factor. IEEE Trans. Computer-Aided Design, vol. 12, no. 11, pages 1686-1694, 1993.
[14]
{14} L. A. Sanchis. Multiple-way network partitioning. IEEE Trans. Computer, vol. 38, pages 62-81, 1989.
[15]
{15} D. P. Singh and S. D. Brown. Incremental placement for layout-driven optimizations on FPGAs. In Proc. Int'l. Conf. on Computer-Aided Design, pages 752-759, 2002.
[16]
{16} N. Togawa, K. Hagi, M. Yanagisawa, and T. Ohtsuki. An incremental placement and global routing algorithm for field-programmable gate arrays. In Proc. Asia Pacific Design Automation Conf., pages 519-526, 1998.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICCAD '03: Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design
November 2003
899 pages
ISBN:1581137621

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 09 November 2003

Check for updates

Author Tags

  1. Stable circuit partitioning
  2. engineering change order
  3. incremental partitioning
  4. placement
  5. similarity cost

Qualifiers

  • Article

Conference

ICCAD03
Sponsor:

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 146
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 09 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media