Switchbox routing by simulated annealing: SAR

A new two-layer switchbox/channel router, SAR, based on the simulated annealing algorithm is presented. The routing region is represented by a matrix, and nets are handled by using a dynamic linked list whose nodes are either net segments or vias. Search in the configuration space is performed by reshaping the layouts of randomly selected nets by making use of Lee-type moves with adaptive parameters, and moves that change layer assignments of net segments. SAR works with no user intervention. It is completely automatic and has no problem dependence. For all benchmark switchbox problems, the success of SAR was at least as good as the other well-known methods in the literature