A Novel Parallel Genetic Algorithm for the Graph Coloring Problem in VLSI Channel Routing

With the increasing popularization of very large scale integrated (VLSI) chips, the improvement of their performance and the reduction of their cost have become two of the most important problems. In this paper, a novel Parallel Genetic Algorithm (PGA) is successfully applied to the graph coloring problem (GCP) in VLSI channel routing problem (CRP). Five topological structures of parallel models are discussed and compared in detail. Finally, one theorem has been proposed to evaluate the parallel performance based on a large amount of experiments. By using the theorem, we could easily modify the parameters to get the better results. The purpose of the research is to promote the performance of VLSI channel routing and the parallel computing. Also, some ideas for quantity analysis of parallel computing are put forward.