DocumentCode :
527848
Title :
A GRASP based algorithm for multi-constraint circuit partitioning
Author :
Zhan, Qingqing ; Zhu, Wenxing ; He, Xiuping
Author_Institution :
Center for Discrete Math. & Theor. Comput. Sci., Fuzhou Univ., Fuzhou, China
Volume :
6
fYear :
2010
fDate :
10-12 Aug. 2010
Firstpage :
3110
Lastpage :
3114
Abstract :
We study the circuit partitioning problem with area and delay constraints to optimize the circuit performance. We integrate delay constraints into the greedy randomized adaptive search procedure (GRASP), so that GRASP can be used to deal with delay problems. The GRASP with area and delay constraints can generate better initial partitions. Then the initial partition is iteratively improved by an extended FM algorithm. Finally we obtain the partition satisfying area and delay constraints. Our hybrid algorithm can solve bi-partition with area and delay constraints successfully. The experimental results indicate that, compared with FM algorithm and clustering algorithm, our hybrid algorithm improves the solution quality in a reasonable computational time, and obtains a better partition, especially in terms of the minimum cut-size and the average cut-size.
Keywords :
circuit analysis computing; constraint handling; greedy algorithms; pattern clustering; search problems; GRASP based algorithm; circuit performance; clustering algorithm; computational time; delay constraints; extended FM algorithm; greedy randomized adaptive search procedure; hybrid algorithm; multiconstraint circuit partitioning; Algorithm design and analysis; Clustering algorithms; Construction industry; Delay; Frequency modulation; Partitioning algorithms; FM algorithm; GRASP; area constraint; circuit partition; delay constraint;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Natural Computation (ICNC), 2010 Sixth International Conference on
Conference_Location :
Yantai, Shandong
Print_ISBN :
978-1-4244-5958-2
Type :
conf
DOI :
10.1109/ICNC.2010.5584618
Filename :
5584618
Link To Document :
بازگشت