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.
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
.
DOI: 10.1007/s12204-011-1138-z
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.
