Abstract
Wire bonding is the most popular method to connect signals between dies in System- in-Package (SiP) design nowadays. Pad assignment, which assigns inter-die signals to die pads so as to facilitate wire bonding, is an important physical design problem for SiP design because the quality of a pad assignment solution a ects both the cost and performance of a SiP design. In this thesis, we study a pad assignment problem, which prohibits the generation of illegal crossings and aims to minimize the total signal wire- length, for die-stacking SiP design. We rst consider a variety of special cases and present a minimum-cost maximum- ow based approach to optimally solve them in polynomial time. We then describe an approach, which uses a modi ed left edge algorithm and an integer linear programming technique, to solve the general case. Encouraging experimen- tal results are shown to support our approaches. To the best of our knowledge, our work is the rst one which addresses a pad assignment problem for die-stacking SiP design and gives promising solutions.