UCLA

In this thesis we present several Linear Programming (LP) based pin assignment algorithms for silicon interposer based 2.5D dielet integration with different purposes. In the first part of the dissertation we present three different formulations of the pin assignment problem: 1) Integer Linear Programming based (ILP formulation), 2) ILP based with LP relaxation (Relaxed-ILP formulation), and 3) LP based modeling (LP formulation). ILP based modeling employees the use of integer assignment matrices, which comply with the nature of pin assignment problem where only discrete locations are available to pins. However, due to NP-hard nature of ILP problems, complexity and run time of ILP formulation is not scalable and pin assignment can be accomplished only for designs with limited size. Relaxed-ILP formulation can reduce the run time significantly and can scale to larger designs. While solutions generated with LP relaxation are usually not valid pin assignments, we apply a rounding heuristic to legalize the solution. Finally the LP formulation with rounding heuristic can further reduce the complexity of the problem and make the run time more scalable. Since I/O power consumption for each die is a major overhead of 2.5D integration, in the second part of the thesis we present a framework for optimizing the energy-per-bit required by I/O cells to drive the interconnects between different dies. We use RC wire model to simulate power and latency of interconnects, and use 2pi model to simulate wire performance in presence of wire coupling and ground bouncing. We model the energy required for each link as a function of the required link speed and wire length and modify LP formulation accordingly. We compare our model with Cadence Innovus and show that we can achieve lower power overhead. In the third part of the thesis we propose a model for multi-floorplan pin assignment (MFPA). We perform pin assignment without the knowledge of floorplan such that the block under consideration can be reused in multiple designs and avoid potential routing hotspot or wire congestion. Also we show that such MFPA flow can effectively reduce the worst case and average interconnect length across a set of random floorplans.