Implementation of a parallel genetic algorithm for floorplanoptimization on IBM SP2

摘要

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