Genetic Programming III: Darwinian Invention and Problem
Rolf Drechsler · 1999
One of the major challenges in the field of integrated circuit design is coping with difficult combinatorial optimization problems. Simply finding the minimum length of wire needed to connect a block of transistors is NP-hard. When factoring in a handful of other simultaneous optimization dimensions such as connections to other blocks of components and area minimization, it is easy to see the difficulty facing circuit designers. Since many of the problems encountered do not have polynomial-time solutions, very large scale integration (VLSI) algorithm designers experiment with various optimization techniques such as integer linear programming and simulated annealing. Optimization methods for VLSI computer-aided design (CAD) incorporating evolutionary search began appearing in research articles in the late 1980’s. As the first body of work devoted exclusively to evolutionary algorithms (EA’s) in VLSI CAD, this monograph attempts to fill a noticeable void in the literature. The book is divided into two parts. Part I “Basic Principles” provides an overview of the book and discusses the underlying principles of EA’s and algorithm performance issues. The treatment of EA’s here is cursory at best and concentrates mainly on the classic genetic algorithm. An overview of some aspects of VLSI CAD is also included; however, only the latter phase of the circuit design process is covered, and analog integrated circuit design is not touched upon. The second part entitled “Practice” comprises roughly threequarters of the book and deals with tools and applications. A software tool called the Genetic Algorithm Managing Environment (GAME) is described in one chapter. It provides a flexible environment in which an algorithm designer can easily interface EA’s to VLSI CAD tools to facilitate experimentation and production runs. One of the author’s themes is that problem-specific knowledge is necessary for EA’s to be competitive with other optimization approaches. Support for this argument is provided by the numerous case studies examined in a lengthy chapter concerning applications of EA’s to logic synthesis, mapping, and testing. In logic synthesis, one wishes to implement a Boolean function in hardware while satisfying certain constraints (e.g., power, delay area). A category of logic realization called Fixed Polarity Reed Muller expressions is described. Such expressions are difficult to minimize and an approach is described that uses a hybrid EA (one that incorporates problem-specific heuristics). For large Boolean functions, it is shown that the EA presented can achieve smaller expressions as compared to standard tools, although the EA required more computer time. The section on mapping includes EA applications in partitioning, floorplanning, and placement and routing problems. Partitioning consists of mapping blocks of circuit components to two-dimensional