A Length Matching Routing Algorithm for Set-Pair Routing Problem


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.12   pp.2565-2571
Publication Date: 2015/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.2565
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Physical Level Design
set-pair routing,  interposer,  PCB,  routing algorithm,  

Full Text: PDF>>
Buy this Article

In the routing design of interposer and etc., the combination of a pin pair to be connected by wire is often flexible, and the reductions of the total wire length and the length difference are pursued to keep the circuit performance. Even though the total wire length can be minimized by finding a minimum cost maximum flow in set pair routing problems, the length difference is often large, and the reduction of it is not easy. In this paper, an algorithm that reduces the length difference while keeping the total wire length small is proposed. In the proposed algorithm, an initial routing first obtained by a minimum cost maximum flow. Then it is modified to reduce the maximum length while keeping the minimum total wire length, and a connection of the minimum length is detoured to reduce the length difference. The effectiveness of the proposed algorithm is confirmed by experiments.