GENETIC ALGORITHM FOR NODE PARTITIONING PROBLEM AND APPLICATIONS IN VLSI DESIGN

被引：14

作者：

CHANDRASEKHARAM, R ^{[1
]}

SUBHRAMANIAN, S ^{[1
]}

CHAUDHURY, S ^{[1
]}

机构：

[1] INDIAN INST TECHNOL,DEPT ELECT ENGN,NEW DELHI 110007,INDIA

来源：

IEE PROCEEDINGS-E COMPUTERS AND DIGITAL TECHNIQUES | 1993年 / 140卷 / 05期

关键词：

GENETIC ALGORITHMS; NODE PARTITIONING PROBLEM; VLSI DESIGN;

D O I：

10.1049/ip-e.1993.0037

中图分类号：

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

学科分类号：

0812 ;

摘要：

The group of classical graph-theoretic problems, including graph colouring, clique cover, and maximal clique, may be viewed as instances of a general node partitioning problem (NPP). A wide variety of real life problems can be modelled as instances of NPP. Finding an optimal partition for the NPP is said to be NP-complete. In this work a stochastic search by a genetic algorithm (GA) is employed to find a near optimal solution for the NPP. The critical aspects of the GA for NPP, such as the solution representation by elegant data structure, together with genetic operations and selection policies employed in the GA procedure, are also presented. The proposed GA does not require the number of disjunct node sets to be given a priori. Three application problems is VLSI design are solved as instances of NPP. The experimental results presented in each case of these application problems bring out the efficacy of genetic algorithms.

引用

页码：255 / 260

页数：6

共 18 条

[1]

BASU A, 1990, IFIP WG105 WORKSH DE

[2]

CHRISTOFIDES N, 1979, COMBINATORIAL OPTIMA

[3] DISTRIBUTED GENETIC ALGORITHMS FOR THE FLOORPLAN DESIGN PROBLEM [J].

COHOON, JP ;

HEGDE, SU ;

MARTIN, WN ;

RICHARDS, DS .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1991, 10 (04) :483-492

[4]

DAVIS L, 1987, P INT C GENETIC ALGO, P136

[5] SYMBOLIC DESIGN OF COMBINATIONAL AND SEQUENTIAL LOGIC-CIRCUITS IMPLEMENTED BY 2-LEVEL LOGIC MACROS [J].

DEMICHELI, G .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1986, 5 (04) :597-616

[6]

DEO N, 1986, GRAPH THEORY APPLICA

[7]

Garey M. R, 1979, GUIDE THEORY NP COMP

[8]

Goldberg DE, 1989, GENETIC ALGORITHMS S

[9]

HOLLAND JH, 1975, ADAPTATION NATURAL A

[10] BEST-FIRST SEARCH ALGORITHM FOR OPTIMAL PLA FOLDING. [J].

Hwang, Sun Young ;

Dutton, Robert W. ;

Blank, Tom .

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1986, CAD-5 (03) :433-442

← 1 2 →