A parallel genetic algorithm for performance-driven VLSI routing

Author

Lienig, Jens

Author_Institution

Tanner Res. Inc., Pasadena, CA, USA

Volume

1

Issue

1

fYear

1997

fDate

4/1/1997 12:00:00 AM

Firstpage

29

Lastpage

39

Abstract

This paper presents a novel approach to solve the VLSI (very large scale integration) channel and switchbox routing problems. The approach is based on a parallel genetic algorithm (PGA) that runs on a distributed network of workstations. The algorithm optimizes both physical constraints (length of nets, number of vias) and crosstalk (delay due to coupled capacitance). The parallel approach is shown to consistently perform better than a sequential genetic algorithm when applied to these routing problems. An extensive investigation of the parameters of the algorithm yields routing results that are qualitatively better or as good as the best published results. In addition, the algorithm is able to significantly reduce the occurrence of crosstalk

Keywords

VLSI; circuit layout CAD; crosstalk; delays; genetic algorithms; integrated circuit layout; network routing; parallel algorithms; coupled capacitance; crosstalk; parallel genetic algorithm; performance-driven VLSI routing; physical constraints; switchbox routing problems; Capacitance; Concurrent computing; Crosstalk; Delay; Electronics packaging; Genetic algorithms; Integrated circuit interconnections; Routing; Very large scale integration; Workstations;

fLanguage

English

Journal_Title

Evolutionary Computation, IEEE Transactions on

Publisher

ieee

ISSN

1089-778X

Type

jour

DOI

10.1109/4235.585890

Filename

585890