Efficient Clustering and Simulated Annealing Approach  
for Circuit Partitioning

doi:10.1007/s12204-011-1138-z

上海交通大学学报（英文版） ›› 2011, Vol. 16 ›› Issue (6): 708-712.doi: 10.1007/s12204-011-1138-z

Efficient Clustering and Simulated Annealing Approach
for Circuit Partitioning

SANDEEP Singh Gill, RAJEEVAN Chandel, ASHWANI Kumar Chandel

(1. Department of Electronics and Communication
Engineering, Guru Nanak Dev Engineering College,
Ludhiana 141001, India; 2. National Institute of Technology,
Hamirpur 177005, India)

收稿日期:2010-03-15 出版日期:2011-12-30 发布日期:2012-01-12
通讯作者: SANDEEP Singh Gill E-mail: sandeepgill27@yahoo.in

Efficient Clustering and Simulated Annealing Approach
for Circuit Partitioning

SANDEEP Singh Gill, RAJEEVAN Chandel, ASHWANI Kumar Chandel

(1. Department of Electronics and Communication
Engineering, Guru Nanak Dev Engineering College,
Ludhiana 141001, India; 2. National Institute of Technology,
Hamirpur 177005, India)

Received:2010-03-15 Online:2011-12-30 Published:2012-01-12
Contact: SANDEEP Singh Gill E-mail: sandeepgill27@yahoo.in

摘要/Abstract

摘要： Circuit net list bipartitioning using
simulated annealing technique has been proposed in the paper. The
method converges asymptotically and probabilistically to global
optimization. The circuit net list is partitioned into two
partitions such that the number of interconnections between the
partitions is minimized. The proposed method begins with an
innovative clustering technique to obtain a good initial solution.
Results obtained show the versatility of the proposed method in
solving non polynomial hard problems of circuit net list
partitioning and show an improvement over those available in
literature.

关键词: cut size, non polynomial hard, partitioning,
simulated annealing, interconnections, very large scale integration
(VLSI) design

Abstract: Circuit net list bipartitioning using
simulated annealing technique has been proposed in the paper. The
method converges asymptotically and probabilistically to global
optimization. The circuit net list is partitioned into two
partitions such that the number of interconnections between the
partitions is minimized. The proposed method begins with an
innovative clustering technique to obtain a good initial solution.
Results obtained show the versatility of the proposed method in
solving non polynomial hard problems of circuit net list
partitioning and show an improvement over those available in
literature.

Key words: cut size, non polynomial hard, partitioning,
simulated annealing, interconnections, very large scale integration
(VLSI) design

中图分类号:

TN401

SANDEEP Singh Gill, RAJEEVAN Chandel, ASHWANI Kumar Chandel. Efficient Clustering and Simulated Annealing Approach
for Circuit Partitioning[J]. 上海交通大学学报（英文版）, 2011, 16(6): 708-712.

SANDEEP Singh Gill, RAJEEVAN Chandel, ASHWANI Kumar Chandel. Efficient Clustering and Simulated Annealing Approach
for Circuit Partitioning[J]. Journal of shanghai Jiaotong University (Science), 2011, 16(6): 708-712.

参考文献

1 Areibi S.   Recursive and flat partitioning for VLSI

circuit design [C]//   The 13th International Conference on

Micro-electronics.   Rabat, Morocco: IEEE Press, 2001: 237-240.

    2 Lawler E L, Levitt K N, Turner J.   Module clustering to minimize

delay in digital networks [J].    IEEE Transactions on

Computers, 1969,     18 (1): 47-57.

    3 Kernighan B W, Lin S.   An efficient heuristic procedure for

partitioning graphs [J].    Bell System Tech Journal, 1970, 49: 291-307.

    4 Schweikert D G, Kernighan B W.   A proper model for the partitioning

of electrical circuits [C]//    Proceedings ACM/IEEE Design

Automation Workshop. Dallas, Texas: IEEE Press, 1972: 57-62.

    5 Fiduccia C M, Mattheyses A.   Linear time heuristic for improving

network partitions [C]//    Proceedings 19th IEEE Design and

Automation Conference.   Piscataway, NJ: IEEE Press, 1982: 175-182.

    6 Krishnamurthy B.   An improved min-cut algorithm for partitioning VLSI

circuits [J].    IEEE Transactions on Computers,   1984, 33 (5): 438-446.

    7 Sanchis L A.   Multiple way networks partitioning [J].    IEEE

   Transactions on Computers, 1989,     38 (1): 62-81.

    8 Wei   Yen-Cheun, Cheng   Chung-Kuan. Ratio-cut partitioning for

hierarchical design [J].    IEEE Transactions on Computer Aided

Design, 1991,     10 (7): 911-921.

    9 Cong J, Hagen L, Kahng A.   Net partitions yield better module

partitions [C]//    29th ACM/IEEE Design Automation

Conference.   Anaheim, CA: IEEE Press, 1992: 47-52.

    10 Areibi S, Vannelli A.   Circuit partitioning using a tabu search

approach [C]//   IEEE International Symposium on Circuits and

Systems.   Chicago, Illinois: IEEE Press, 1993: 1643-1646.

    11 Shahookar K, Mazumder P.   Genetic multiway partitioning [C]//

   IEEE 8th International Conference on VLSI Design.   New Delhi, India: IEEE Press, 1995: 365-369.

    12 Karypis G, Aggarwal R, Kumar V, et al. Multilevel hyper graph

partitioning: Applications in VLSI domain [C]//    IEEE 34th

Design Automation Conference. Anaheim, California: ACM Press, 1997:

526-529.

    13 Areibi S.   Memetic algorithms for VLSI physical design:

Implementation issues [C]//    Genetic and Evolutionary

computation Conference. San Franscisco, California: ISGEC, 2001:

140-145.

    14 Ababei C, Navaratnasothie S, Bazargan K, et al. Multi-objective

circuit partitioning for cutsize and path-based delay minimization

[C]//    IEEE/ACM International Conference on Computer Aided

Design. San Jose, CA: IEEE Press, 2002: 181-185.

    15 Palesian M, Givargis T.   Multi-objective design space exploration

using genetic algorithms [C]//    Proceedings of the 10th

International Symposium on Hardware/Software Co-design. Estes Park,

Colorado: ACM Press, 2002: 67-72.

    16 Stitt G, Lysecky R, Vahid F.   Dynamic hardware/software partitioning:

A first approach [C]//    ACM/IEEE Design Automation

Conference. Anaheim, California: ACM Press, 2003: 250-255.

    17 Kolar D, Puksec J D, Branica I.   VLSI circuit partitioning using

simulated annealing algorithm [C]//    Proceedings of the 12th

IEEE Mediterranean Electro-technical Conference. Dubrovnik,

Croatia: IEEE Press, 2004: 205-208.

    18 Ghafari P, Mirhard E, Anis M, et al. A low power partitioning

methodology by maximizing sleep time and minimizing cut nets [C]//

   Proceedings of the Fifth International Workshop on

System-on-Chip for Real-time-Applications.   Bauf, Alberta, Canada:

IEEE Press, 2005: 368-371.

    19 Wang G, Gang W, Kastner R.   Application partitioning on programmable

platforms using ant colony optimization [J].    Journal of

Embedded Computing, 2006,     2 (1): 1-20.

    20 Sumitra Devi K A, Banashree N P, Abraham A.   Comparative study of

evolutionary model and clustering methods in circuit partitioning

pertaining to VLSI design [J].    World Academy of Science,

Engineering and Technology, 2007,     26 : 42-45.

    21   Gill Sandeep Singh, Chandel Rajeevan, Chandel Ashwani. Comparative

study of ant colony and genetic algorithm for VLSI circuit

partitioning [J].     International Journal of Intelligent

Systems and Technologies, 2009,     4 (2): 104-108.

    22 Sherwani N.   Algorithms for VLSI physical design and automation [M].

New Delhi, India: Springer-Verlag, 2005.

    23 Kirkpatrick S, Gellat C D, Vecchi M P.   Optimization by simulated

annealing [J].    Science, 1983,     220 : 671-680.

Efficient Clustering and Simulated Annealing Approach
for Circuit Partitioning

Efficient Clustering and Simulated Annealing Approach
for Circuit Partitioning

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

Efficient Clustering and Simulated Annealing Approach for Circuit Partitioning

Efficient Clustering and Simulated Annealing Approach for Circuit Partitioning

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

Efficient Clustering and Simulated Annealing Approach
for Circuit Partitioning

Efficient Clustering and Simulated Annealing Approach
for Circuit Partitioning