Large scale circuit partitioning with loose/stable net removal and signal flow based clustering

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Large scale circuit partitioning with loose/stable net removal and signal flow based clustering

Full text

Publisher Site , Pdf

Pdf (220 KB)

Source

International Conference on Computer Aided Design archive
Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design table of contents

San Jose, California, United States

Pages: 441 - 446

Year of Publication: 1997

ISBN:0-8186-8200-0

Authors

Jason Cong	UCLA Department of Computer Science, Los Angeles, CA
Honching Peter Li	UCLA Department of Computer Science, Los Angeles, CA
Sung Kyu Lim	UCLA Department of Computer Science, Los Angeles, CA
Toshiyuki Shibuya	Fujitsu Laboratories Ltd., Kawasaki, Japan
Dongmin Xu	UCLA Department of Computer Science, Los Angeles, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS : Computer Society

Publisher

IEEE Computer Society Washington, DC, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 18, Citation Count: 29

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

In this paper, we present an efficient Iterative Improvement based Partitioning (IIP) algorithm called LSR/MFFS, that combines signal flow based Maximum Fanout Free Subgraph (MFFS) clustering algorithm with Loose and Stable net Removal (LSR) partitioning algorithm. The MFFS algorithm generalizes existing MFFC decomposition method from combinational circuits to general sequential circuits in order to handle cycles naturally. We also study the properties of the nets that straddle the cutline carefully, and introduce the concepts of the loose and stable nets as well as effective ways to remove them out of the cutset. The LSR/MFFS algorithm first applies LSR algorithm to clustered netlist generated by MFFS algorithm for global-level cutsize optimization and then declusters netlist for further cutsize refinement. As a result, the LSR/MFFS algorithm has achieved the best cutsize result among all the bipartitioning algorithms published in the literatures with very promising runtime performance. In particular, it outperforms the recent state-of-the-art IIP algorithms LA3-CDIP, CLIP-PROPf, Strawman, hMetis-FM, and MLc by 17.4%, 12.1%, 5.9%, 3.1%, and 1.9%, respectively. It also outperforms the state-of-the-art non-IIP algorithms Paraboli, FBB, and PANZA by 32.0%, 21.4%, and 1.4%, respectively.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Charles J. Alpert , Jen-Hsin Huang , Andrew B. Kahng, Multilevel circuit partitioning, Proceedings of the 34th annual conference on Design automation, p.530-533, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266275]
	2	Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
	3	Charles J. Alpert , So-Zen Yao, Spectral partitioning: the more eigenvectors, the better, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.195-200, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217529]
	4	Jason Cong , Yuzheng Ding, On area/depth trade-off in LUT-based FPGA technology mapping, Proceedings of the 30th international conference on Design automation, p.213-218, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164675]
	5	J. Cong, P. Li, S. K. Lira, T. Shibuya, and D. Xu. "Large scale circuit partitioning with loose/stable net removal and signal flow based hierarchical clustering". Technical Report 970005, CS Dept. of UCLA, 1997.
	6	Jason Cong , Zheng Li , Rajive Bagrodia, Acyclic multi-way partitioning of Boolean networks, Proceedings of the 31st annual conference on Design automation, p.670-675, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196609]
	7	Jason Cong , Dongmin Xu, Exploiting signal flow and logic dependency in standard cell placement, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.63-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224931]
	8	Shantanu Dutt , Wenyong Deng, VLSI circuit partitioning by cluster-removal using iterative improvement techniques, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.194-200, November 10-14, 1996, San Jose, California, United States
	9	C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
	10	Lars W. Hagen , Dennis J.-H. Huang , Andrew B. Kahng, On implementation choices for iterative improvement partitioning algorithms, Proceedings of the conference on European design automation, p.144-149, September 18-22, 1995, Brighton, England
	11	Lars Hagen , Andrew B. Kahng, A new approach to effective circuit clustering, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.422-427, November 1992, Santa Clara, California, United States
	12	S. Hauck and G. Borriello. "An evaluation of bipartitioning techniques", submitted to IEEE Trans. on Computer-Aided Design, 1996.
	13	George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
	14	B. Kernighan and S. Lin. "An efficient heuristic procedure for partitioning of electrical circuits". Bell System Technical Journal, 1970.
	15	B. Krishnamurthy. "An improved rain-cut algorithm for partitioning VLSI networks". IEEE Trans. on Computers, pages 438-446, 1984.
	16	Jianmin Li , John Lillis , Chung-Kuan Cheng, Linear decomposition algorithm for VLSI design applications, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.223-228, November 05-09, 1995, San Jose, California, United States
	17	Bernhard M. Riess , Konrad Doll , Frank M. Johannes, Partitioning very large circuits using analytical placement techniques, Proceedings of the 31st annual conference on Design automation, p.646-651, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196602]
	18	T. Shibuya, I. Nitta, and K. Kawamura. "SMINCUT: VLSI placement tool using rain-cut". Fujitsu Scientific Technical Journal, pages 197-207, 1995.
	19	Honghua Yang , D. F. Wong, Efficient network flow based min-cut balanced partitioning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.50-55, November 06-10, 1994, San Jose, California, United States

CITED BY 29

	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Improved algorithms for hypergraph bipartitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.661-666, January 2000, Yokohama, Japan
	Mango Chia-Tso Chao , Guang-Ming Wu , Iris Hui-Ru Jiang , Yao-Wen Chang, A clustering- and probability-based approach for time-multiplexed FPGA partitioning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.364-369, November 07-11, 1999, San Jose, California, United States
	Youssef Saab, A new effective and efficient multi-level partitioning algorithm, Proceedings of the conference on Design, automation and test in Europe, p.112-116, March 27-30, 2000, Paris, France
	Jason Cong , Sung Kyu Lim , Chang Wu, Performance driven multi-level and multiway partitioning with retiming, Proceedings of the 37th conference on Design automation, p.274-279, June 05-09, 2000, Los Angeles, California, United States
	Michael Hutton , Khosrow Adibsamii , Andrew Leaver, Timing-driven placement for hierarchical programmable logic devices, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.3-11, February 2001, Monterey, California, United States
	Jason Cong , Sung Kyu Lim, Performance driven multiway partitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.441-446, January 2000, Yokohama, Japan
	Jason Cong , Songjie Xu, Invited talk: synthesis challenges for next-generation high-performance and high-density PLDs, Proceedings of the 2000 conference on Asia South Pacific design automation, p.157-162, January 2000, Yokohama, Japan
	Kenneth Yan, Practical logic synthesis for CPLDs and FPGAs with PLA-style logic blocks, Proceedings of the 2001 conference on Asia South Pacific design automation, p.231-234, January 2001, Yokohama, Japan
	Huiqun Liu , Kai Zhu , D. F. Wong, Circuit partitioning with complex resource constraints in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.77-84, February 22-25, 1998, Monterey, California, United States
	Jason Cong , Songjie Xu, Technology mapping for FPGAs with embedded memory blocks, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.179-188, February 22-25, 1998, Monterey, California, United States
	Jason Cong , Sung Kyu Lim, Multiway partitioning with pairwise movement, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.512-516, November 08-12, 1998, San Jose, California, United States
	Jason Cong , Michail Romesis , Min Xie, Optimality, scalability and stability study of partitioning and placement algorithms, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Jason Cong , Majid Sarrafzadeh, Incremental physical design, Proceedings of the 2000 international symposium on Physical design, p.84-92, May 2000, San Diego, California, United States
	Shantanu Dutt , Wenyong Deng, Cluster-aware iterative improvement techniques for partitioning large VLSI circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.91-121, January 2002
	Shantanu Dutt , Halim Theny, Partitioning using second-order information and stochastic-gain functions, Proceedings of the 1998 international symposium on Physical design, p.112-117, April 06-08, 1998, Monterey, California, United States
	Jason Cong , Honching Li , Chang Wu, Simultaneous circuit partitioning/clustering with retiming for performance optimization, Proceedings of the 36th ACM/IEEE conference on Design automation, p.460-465, June 21-25, 1999, New Orleans, Louisiana, United States
	Jason Cong , Sung Kyu Lim, Edge separability based circuit clustering with application to circuit partitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.429-434, January 2000, Yokohama, Japan
	Andrew E. Caldwell , Andrew B. Kahng , Andrew A. Kennings , Igor L. Markov, Hypergraph partitioning for VLSI CAD: methodology for heuristic development, experimentation and reporting, Proceedings of the 36th ACM/IEEE conference on Design automation, p.349-354, June 21-25, 1999, New Orleans, Louisiana, United States
	Jason Cong , Kenneth Yan, Synthesis for FPGAs with embedded memory blocks, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.75-82, February 10-11, 2000, Monterey, California, United States
	Michael Hutton , Khosrow Adibsamii , Andrew Leaver, Adaptive delay estimation for partitioning-driven PLD placement, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.1, p.60-63, February 2003
	Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States
	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Design and implementation of move-based heuristics for VLSI hypergraph partitioning, Journal of Experimental Algorithmics (JEA), 5, p.5-es, 2000
	Maogang Wang , Sung Lim , Jason Cong , Majid Sarrafzadeh, Multi-way partitioning using bi-partition heuristics, Proceedings of the 2000 conference on Asia South Pacific design automation, p.667, January 2000, Yokohama, Japan
	Andrés Martinelli , René Krenz , Elena Dubrova, Disjoint-support Boolean decomposition combining functional and structural methods, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.597-599, January 27-30, 2004, Yokohama, Japan
	Navaratnasothie Selvakkumaran , Abhishek Ranjan , Salil Raje , George Karypis, Multi-resource aware partitioning algorithms for FPGAs with heterogeneous resources, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Guang-Ming Wu , Mango Chia-Tso Chao , Yao-Wen Chang, A clustering- and probability-based approach for time-multiplexed FPGA partitioning, Integration, the VLSI Journal, v.38 n.2, p.245-265, December 2004
	Youssef G. Saab, An Effective Multilevel Algorithm for Bisecting Graphs and Hypergraphs, IEEE Transactions on Computers, v.53 n.6, p.641-652, June 2004
	Chanseok Hwang , Massoud Pedram, PMP: performance-driven multilevel partitioning by aggregating the preferred signal directions of I/O conduits, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Fei Li , Lei He , Kewal K. Saluja, Estimation of Maximum Power-up Current, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.51, January 07-11, 2002