Berger, Martin:
ISBN 9783862470389

Bicriteria Optimization in Electronic Design Automation. Placement Algorithms for 2.5D System-in-Package Integration # Pb., 214 S., 65 Abb., davon 10 in Farbe; 31 Tab.

SCHLAGWORTE:
Operations Research
Electronic Design Automation
Placement Problems
Rectangular Packing
Multicriteria Optimization
Approximation Algorithms

This thesis presents efficient placement algorithms for the automation of 2.5D System-in-Package (SiP) design. SiP design automation is a new branch of electronic design automation (EDA) and currently lacks adequate placement algorithms. 2.5D SiP integration aims for miniaturization of microelectronic systems that are integrated on vertically stacked substrates. The placement of the electronic components on the substrates is a bicriteria optimization problem in which an area and a wirelength objective are optimized concurrently. To enable design automation of 2.5D SiP, we require efficient placement algorithms that approximate Pareto optimal solutions. Therefore, we provide an algorithmic fundament for this important real-world application in EDA.
The contribution of this thesis is threefold: we cope with a real-wold application, develop efficient optimization algorithms and challenge NP-hard combinatorial optimization problems.
On the application side, this thesis contributes to the stepwise generalization of an academic optimization problem to a real-world problem. The real-world placement problem is successively approached by starting with two simplified rectangular packing problems that regard an area objective. Then we shift to a placement problem optimized with respect to a wirelength objective. Finally we consider the bicriteria placement problem which models the real-world situation. The four problems with different abstraction levels are modeled as combinatorial optimization problems. The optimization problems are solved with efficient heuristics, exact mixed integer programming and constraint programming methods. Additionally, we develop design constraints for SiP integration that restrict the placement of components of functional units.
On the algorithmic side, this thesis proposes state-of-the-art exact methods and efficient heuristics. The exact methods can only solve small problem instances to optimality. However, all heuristics that are proposed in this thesis solve real-world instances within a desired runtime and provide solutions with a guaranteed optimality gap. For the rectangular packing problem with and without orthogonal orientations, a mixed integer program and a constraint program are proposed. Also an efficient heuristic that constructs a solution by applying simple packing operations is developed. It yields solutions within 5% of optimality for all considered problem instances. Group constraint formulations for functional units and algorithms for handling these constraints are studied. For the placement problem with net objective we propose a bottom-up algorithm to derive a lower bound for the net objective. An improvement heuristic generates solutions whose net objective values differ at most 5% from optimal solutions for the real-world SiP instances. For the bicriteria placement problem we develop a heuristic that approximates the Pareto set and yields lexicographic minima that are within 5% of optimality for our real-world instances.
On the mathematical side, this thesis thoroughly studies four optimization problems and analyzes the proposed optimization algorithms. We show several structural properties of four optimization problems: the disjunctive nature of the non-overlapping constraints, a lower bound for the half perimeter objective, the full-dimensionality of the polyhedron of the feasible set of the rectangular packing problem, the NP-hardness of the placement problem with net objective, and characteristics of the Pareto set of the bicriteria placement problem. We also prove that the mixed integer program and the constraint program for the rectangular packing problem use the same ideas embedded in their own inference methods: inequalities of the mixed integer program restrict the feasible set in the same way as the propagation algorithms of the constraint program; and the lower bound obtained by the linear relaxation of the mixed integer program equals the lower bound obtained by the constraint program. Consequently, we derive that no hybrid method of these two programs can improve any of them. Furthermore, we show that the constructive heuristic for the rectangular packing problem with orthogonal orientations can have no approximation factor better than 11/10. However, we prove that a slightly modified heuristic applied to slightly modified problem instances yields an approximation factor of 3. For specific problem instances, the approximation factor can be improved to 2.

	^