MILP-Based Efficient Routing Method with Restricted Route Structure for 2-Layer Ball Grid Array Packages

Yoichi TOMIOKA  Yoshiaki KURATA  Yukihide KOHIRA  Atsushi TAKAHASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.12   pp.2998-3006
Publication Date: 2009/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.2998
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Physical Level Desing
ball grid array,  monotonic,  nearest via assignment,  package routing,  radiate,  

Full Text: PDF>>
Buy this Article

In this paper, we propose a routing method for 2-layer ball grid array packages that generates a routing pattern satisfying a design rule. In our proposed method, the routing structure on each layer is restricted while keeping most of feasible patterns to efficiently obtain a feasible routing pattern. A routing pattern that satisfies the design rule is formulated as a mixed integer linear programming. In experiments with seven data, we obtain a routing pattern such that satisfies the design rule within a practical time by using a mixed integer linear programming solver.