Integration of a Local Search Operator into Evolutionary Algorithms for VLSI-Model Partitioning

The application of Evolutionary Algorithms in hierarchical model partitioning for parallel system simulation in VLSI design processes has proven to be successful. Thereby, individuals embody partitions of hardware designs. On the basis of a formal model of parallel cycle simulation a fitness function is chosen combining load balancing and interprocessor communication aspects. As supplement to the concept of superposition we introduce a Local Search Operator to achieve a fast decreasing fitness function during evolution. This operator is based on a modification of a classical iterative partitioning algorithm by Fiduccia-Mattheyses. Results are shown for the partitioning of two real processor models, representing the PowerPC 604 and an IBM S/390 processor