Ant colony system application to macrocell overlap removal

被引：15

作者：

Alupoaei, S ^{[1
]}

Katkoori, S ^{[1
]}

机构：

[1] Univ S Florida, Dept Comp Sci & Engn, Tampa, FL 33620 USA

来源：

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS | 2004年 / 12卷 / 10期

关键词：

ant colony optimization; floorplanning; macrocell placement; overlap removal; wirelength minimization;

D O I：

10.1109/TVLSI.2004.832926

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 [计算机科学与技术];

摘要：

We present a novel macrocell overlap removal algorithm, based on the ant colony optimization metaheuristic. The procedure generates a feasible placement from a relative placement with overlaps produced by some placement algorithms such as quadratic programming and force-directed. It uses the concept of ant colonies, a set of agents that work together to improve an existing solution. Each ant in the colony will generate a placement based on the relative positions of the cells and feedback information about the best placements generated by previous colonies. The solution of each ant is improved by using a local optimization procedure which reduces the unused space. The worst runtime is O(n(3)), but the average runtime can be reduced to O(n(2)).

引用

页码：1118 / 1122

页数：5

共 13 条

[1]

Asato BA, 1996, 38TH MIDWEST SYMPOSIUM ON CIRCUITS AND SYSTEMS, PROCEEDINGS, VOLS 1 AND 2, P310, DOI 10.1109/MWSCAS.1995.504439

[2]

Chang YC, 2000, DES AUT CON, P458

[3]

Dorigo M., 1997, IEEE Transactions on Evolutionary Computation, V1, P53, DOI 10.1109/4235.585892

[4]

Ant system: Optimization by a colony of cooperating agents [J].

Dorigo, M ;

Maniezzo, V ;

Colorni, A .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01) :29-41

[5]

Constrained floorplanning using network flows [J].

Feng, Y ;

Mehta, DR ;

Yang, H .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2004, 23 (04) :572-580

[6]

An ant colony system hybridized with a new local search for the sequential ordering problem [J].

Gambardella, LM ;

Dorigo, M .

INFORMS JOURNAL ON COMPUTING, 2000, 12 (03) :237-255

[7]

Gamberdella LM., 1995, P 12 INT C MACH LEAR, P252

[8]

Floorplanning using a tree representation [J].

Guo, PN ;

Takahashi, T ;

Cheng, CK ;

Yoshimura, T .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2001, 20 (02) :281-289

[9]

A force-directed macro-cell placer [J].

Mo, F ;

Tabbara, A ;

Brayton, RK .

ICCAD - 2000 : IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER AIDED DESIGN, 2000, :177-180

[10]

VLSI module placement based on rectangle-packing by the sequence-pair [J].

Murata, H ;

Fujiyoshi, K ;

Nakatake, S ;

Kajitani, Y .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1996, 15 (12) :1518-1524

← 1 2 →