A stochastic parallel algorithm and its applications to VLSI layout

There are some problems that can be reduced to combinatorial optimization in VLSI layout. Using traditional methods, it could not escape from local extrema and often could not find valid solutions. We use a stochastic parallel algorithm to obtain valid and optimal result, through formalizing VLSI layout problems, choosing appropriate annealing schedule and parameters. The algorithm we used has low time and space complexity, high parallelism, and it is easy to be implemented using VLSI circuits. The results we obtained show the effectiveness and universality of the algorithm.<>