Implementation of a parallel genetic algorithm for floorplan optimization on IBM SP2

Author

Foo, Han Yang ; Song, Jianjian ; Zhuang, Wenjun ; Esbensen, Henrik ; Kuh, Ernest S.

Author_Institution

Supercomput. Res. Center, Nat. Univ. of Singapore, Singapore

fYear

1997

fDate

28 Apr-2 May 1997

Firstpage

456

Lastpage

459

Abstract

A Multi-Selection-Multi-Evolution (MSME) scheme for parallelizing a genetic algorithm for floorplan optimization is presented and its implementation with MPI and its experimental results are discussed. Our experimental results on a 16 node IBM SP2 scaleable parallel computer have shown that the scheme is effective in improving performance of floorplanning over that of a sequential implementation. The parallel version could obtain better results with more than 90% of probability. Given 1000 second wall clock time, our parallel program could reduce both chip area and maximum path delay by more than 8% with 8 processors and 12% with 12 processors. Parallel computing can also speed up the evolution process so that there could be higher probability of obtaining a better solution within a given time interval

Keywords

IBM computers; VLSI; circuit layout CAD; genetic algorithms; parallel algorithms; parallel machines; 16 node IBM SP2 scaleable parallel computer; IBM SP2; MPI; MSME scheme; Multi-Selection-Multi-Evolution scheme; VLSI chip design; experimental results; floorplan optimization; parallel computing; parallel genetic algorithm; parallel version; wall clock time; Concurrent computing; Costs; Delay effects; Genetic algorithms; Genetic mutations; Libraries; Parallel processing; Routing; Space exploration; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

High Performance Computing on the Information Superhighway, 1997. HPC Asia '97

Conference_Location

Seoul

Print_ISBN

0-8186-7901-8

Type

conf

DOI

10.1109/HPC.1997.592190

Filename

592190