A parallel simulated annealing algorithm for channel routing on a hypercube multiprocessor

摘要

The algorithm begins with an initial placement of nets in the channel using the number of tracks equal to the density of the channel. Overlapping subnets are permitted at this stage as the annealing process will gradually work to remove the overlaps. Transformations are then repeatedly applied to the channel state by moving nets around the channel in a parallel fashion. By allowing overlap situations and controlling them with appropriate cost function, the algorithm is capable of producing very good results with the advantage of decreased runtime from the parallelism. and can also be applied to extensions of the channel routing problem, such as switchbox routine with obstacle avoidance.