Selective sequential trunk locking of single-trunk Steiner trees in global routing

This thesis presents a new algorithm for the global routing of M3-layer single-trunk Steiner trees. The new algorithm, called selective sequential trunk locking (SSTL), works by selecting a trunk from a set of trunks, then locking the trunk in place. The remainder of the trunks in the set are adjusted according to their relationships to the locked trunk. An input file provides the selection criteria along with the chip and circuit layout information. SSTL is compared to a divide and conquer algorithm, which works by recursively dividing the area the trunks exist in then moving trunks from more highly congested areas to less highly congested areas. When the size of an area is at or below a threshold size, an attempt is made to lock down all trunks in the area. The experimental results show that, although the divide and conquer algorithm has some advantages over SSTL, SSTL wins in the most important area SSTL will lock down all trunks in the chip under a wider variety of conditions than divide and conquer.