Title :
A constructive genetic algorithm for gate matrix layout problems
Author :
De Oliveira, Alexandre C M ; Lorena, Luiz A N
Author_Institution :
Departamento de Informatica, Univ. Fed. do Maranhao, Sao Luis, MA, Brazil
fDate :
8/1/2002 12:00:00 AM
Abstract :
This paper describes an application of a Constructive Genetic Algorithm (CGA) to the gate matrix layout problem (GMLP). The GMLP happens in very large scale integration design and can be described as a problem of assigning a set of circuit nodes (gates) in an optimal sequence, such that the layout area is minimized, as a consequence of optimizing the number of tracks necessary to cover the gates interconnection. The CGA has a number of new features compared to a traditional genetic algorithm. These include a population of dynamic size composed of schemata and structures and the possibility of using heuristics in structure representation and in the fitness function definitions. The application of CGA to GMLP uses a 2-Opt-like heuristic to define the fitness functions and the mutation operator. Computational tests are presented using available instances taken from the literature.
Keywords :
VLSI; binary decision diagrams; circuit layout CAD; circuit optimisation; genetic algorithms; integrated circuit layout; logic CAD; logic gates; minimisation of switching nets; 2-Opt-like heuristic; CGA; GMLP; circuit nodes; computational tests; constructive genetic algorithm; dynamic size; fitness function definitions; gate matrix layout problems; heuristics; layout area; mutation operator; optimal sequence; schemata; structure representation; very large scale integration design; Algorithm design and analysis; Costs; Design optimization; Genetic algorithms; Genetic mutations; Integrated circuit interconnections; Programmable logic arrays; Testing; Very large scale integration; Wire;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2002.800454
