A probability-based approach to VLSI circuit partitioning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A probability-based approach to VLSI circuit partitioning

Full text

Pdf (198 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 33rd annual Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 100 - 105

Year of Publication: 1996

ISBN:0-89791-779-0

Authors

Shantanu Dutt	Department of Electrical Engineering, University of Minnesota, Minneapolis, MN
Wenyong Deng	Department of Electrical Engineering, University of Minnesota, Minneapolis, MN

Sponsors

IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 18, Citation Count: 20

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/240518.240538 What is a DOI?

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	C. J. Alpert , A. B. Kahng, A general framework for vertex orderings, with applications to netlist clustering, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.63-67, November 06-10, 1994, San Jose, California, United States
	2	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]
	3	D. G. Schweikert , B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th workshop on Design automation, p.57-62, June 26-28, 1972 [doi>10.1145/800153.804930]
	4	Shantanu Dutt, New faster Kernighan-Lin-type graph-partitioning algorithms, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.370-377, November 07-11, 1993, Santa Clara, California, United States
	5	S. Dutt and W. Deng, "A Probability-Based Approach to VLSI Circuit Partitioning", Tech. Report, EE Dept., Univ. of Minnesota, 1996- available at ftp site ftp-mount.ee.umn.edu in file/pub/faculty/dutt/vlsicad/papers/dac96-ext.ps.
	6	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
	7	L. Hagen and A. Kahng, "Fast spectral methods for ratio cut partitioning and clustering", Proc. Int' l. Conf. Computer-Aided Design, 1991, pp. 10- 13.
	8	M.A.B. Jackson, A. Srinivasan and E.S. Kuh, "A fast algorithm for performance driven placement", Proc. IEEE/ACM International Conference on CAD, 1990, pp. 328-331.
	9	B.W. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs", Bell System Tech. Journal, vol. 49, Feb. 1970, pp. 291-307.
	10	B. Krishnamurthy, "An improved min-cut algorithm for partitioning VLSI networks", IEEE Trans. on Comput., vol. C-33, May 1984, pp. 438-446.
	11	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]
	12	C. Sechen, VLSI Placement and Global Routing Using Simulated Annealing, Kluwer, B.V., Deventer, The Netherlands.
	13	Y.C. Wei and C.K. Cheng, "Towards efficient hierarchical designs by ratio cut partitioning", Proc. Int'l. Conf. Computer-Aided Design, 1989, pp. 298-301.
	14	Y.C. Wei and C.K. Cheng, "A two-level two-way partitioning algorithm", Proc. Int'l. Conf. Computer-Aided Design, 1990, pp. 516-519.

CITED BY 20

	Shantanu Dutt , Halim Theny, Partitioning around roadblocks: tackling constraints with intermediate relaxations, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.350-355, November 09-13, 1997, San Jose, California, United States
	K. S. Seong , C. M. Kyung, Two-way partitioning based on direction vector, Proceedings of the 1997 European conference on Design and Test, p.306, March 17-20, 1997
	Sachin B. Patkar , Himanshu Sharma , H. Narayanan, Efficient network flow based ratio-cut netlist hypergraph partitioning, Proceedings of the 2nd WSEAS International Conference on Electronics, Control and Signal Processing, p.1-7, December 07-09, 2003, Singapore
	Hsun-Cheng Lee , Ting-Chi Wang, Feasible two-way circuit partitioning with complex resource constraints, Proceedings of the 2000 conference on Asia South Pacific design automation, p.435-440, January 2000, Yokohama, Japan
	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
	Wray L. Buntine , Lixin Su , A. Richard Newton , Andrew Mayer, Adaptive methods for netlist partitioning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.356-363, November 09-13, 1997, San Jose, California, United States
	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
	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
	Morgan Enos , Scott Hauck , Majid Sarrafzadeh, Replication for logic bipartitioning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.342-349, November 09-13, 1997, San Jose, California, United States
	Yong-Hyuk Kim , Byung-Ro Moon, Investigation of the Fitness Landscapes in Graph Bipartitioning: An Empirical Study, Journal of Heuristics, v.10 n.2, p.111-133, March 2004
	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
	Ke Zhong , Shantanu Dutt, Effective partition-driven placement with simultaneous level processing and global net views, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	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
	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
	Yong-Hyuk Kim , Byung-Ro Moon, Lock-Gain Based Graph Partitioning, Journal of Heuristics, v.10 n.1, p.37-57, January 2004
	Frank M. Johannes, Partitioning of VLSI circuits and systems, Proceedings of the 33rd annual conference on Design automation, p.83-87, June 03-07, 1996, Las Vegas, Nevada, United States
	Sverre Wichlund, On multilevel circuit partitioning, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.505-511, November 08-12, 1998, San Jose, California, United States
	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
	Sheldon X.-D. Tan , C.-J. Richard Shi, Balanced multi-level multi-way partitioning of analog integrated circuits for hierarchical symbolic analysis, Integration, the VLSI Journal, v.34 n.1-2, p.65-86, May 2003
	Aleksandar Trifunović , William J. Knottenbelt, Parallel multilevel algorithms for hypergraph partitioning, Journal of Parallel and Distributed Computing, v.68 n.5, p.563-581, May, 2008