Efficient Via Shifting Algorithms in Channel Compaction

We consider in this paper the problem of shifting vias to obtain more compactable channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let v_c, w_cbe the number of grid points on column c that are occupied by vias, horizontal wires in S, respectively. We define the expected height of columns c in S to be h_c = Av_c + Bw_c + C, where A, B, C are some design rule dependent constants. A column in S is said to be a critical column if it has maximum expected height among all columns in S. Let H_s= max_ch_cbe the expected height of the critical column(s) of S. H_sis an estimation of the height of S after compaction. We show that the problem of shifting vias to minimize H_scan be solved optimally in polynomial time.