VLSI Physical Design AutomationLinear Programming ApproachMixed Integer Linear ProgramProblem FormulationNon-overlapping ConstraintsInteger VariablesFormulationFormulation with Hard BlocksFormulation with Soft BlocksSlide 10Another way to linearizeSolving Linear ProgramComplexitySuccessive AugmentationFloorplan RepresentationsGeneral Floorplanning by Simulated Annealing: Sequence-Pair RepresentationSequence-Pair vs. Polish ExpressionSequence PairPositive Locus and Negative LocusSequence-PairGeometric Info of Sequence-PairFrom Sequence-Pair to a PlacementFrom Sequence-Pair to PlacementSequence Pair (SP)Sequence PairExampleFloorplan RealizationSlide 28Slide 29Constraint GraphsMovesPros and Cons of SPQuestionsSummary of Floorplanning01/14/191VLSI Physical Design AutomationProf. David [email protected]: ACES 5.434Lecture 8. Floorplanning (2)201/14/19Linear Programming Approach ““An Analytical Approach to Floorplan Design and An Analytical Approach to Floorplan Design and Optimization”, Sutanthavibul, Shragowitz and Rosen, Optimization”, Sutanthavibul, Shragowitz and Rosen, IEEE Transaction on CAD, 10:761-769, June 1991.IEEE Transaction on CAD, 10:761-769, June 1991.301/14/19Mixed Integer Linear Program•A mathematical program such that:–The objective is a linear function.–All constraints are linear functions.–Some variables are real numbers and some are integers, i.e., “mixed integer”.•It is almost like a linear program, except that some variables are integers.•Can you think of which variables may be integer?401/14/19Problem Formulation•Minimize the packing area:–Assume that one dimension W is fixed.–Minimize the other dimension Y.•Need to have constraints so that blocks do not overlap.•Associate each block Bi with 4 variables:–xi and yi: coordinates of its lower left corner.–wi and hi: width and height.WY501/14/19Non-overlapping Constraints For two non-overlapping blocks Bi and Bj, at least one of the following four linear constraints must be satisfied:jijijijiB above is B if (4)or B below is B if (3)or B ofright the tois B if (2)or B ofleft the tois B if (1)jjijiijjijiiyhyyhyxwxxwxBiBj(xi, yi)(xj, yj)hihjwiwj601/14/19Integer Variables•Use integer (0 or 1) variables xij and yij: xij=0 and yij =0 if (1) is true. xij=0 and yij =1 if (2) is true. xij=1 and yij =0 if (3) is true. xij=1 and yij =1 if (4) is true.•Let W and H be upper bounds on the total width and height. Non-overlapping constraints:)2( )(4')1( )(3')1( )(2')( )(1'ijijjjiijijjiiijijjjiijijjiiyxHyhyyxHyhyyxWxwxyxWxwx701/14/19FormulationnjiynjixnjiyxHyhynjiyxHyhynjiyxWxwxnjiyxWxwxniYhy,yniWwx,xYi ji jijijjjiijijjiii jijjjii jijjiiiiiiii1 1or 01 1or 01 )2(1 )1(1 )1(1 )(1 0 1 0 s.t. Min.801/14/19Formulation with Hard Blocks If the blocks can be rotated, use a 0-1 integer variable zuse a 0-1 integer variable zii for each for each block Bblock Bii s.t. z s.t. zi i = 0 if B= 0 if Bii is in the original orientation and z is in the original orientation and zi i = 1 if B= 1 if Bii is is rotated 90rotated 90o o ..njiynjixnjiyxHyhzwzynjiyxHyhzwzynjiyxWxwzhzxnjiyxWxwzhzxniYhzwzy,yniWwzhzx,xYijijijijjjjjjiijijjiiiiiijijjjjjjiijijjiiiiiiiiiiiiiiiii1 1or 01 1or 01 )2()1(1 )1()1(1 )1()1(1 )()1(1 )1(0 1 )1(0 s.t. Min.901/14/19Formulation with Soft Blocks•If Bi is a soft block, wihi=Ai. But this constraint is quadratic!•Linearized by taking the first two terms of the Taylor expression of hi=Ai/wi at wimax (max. width of block Bi). hi =himin+i(wimax-wi)where himin =Ai/wimax and i=Ai/wimax21001/14/19Formulation with Soft Blocks•If BIf Bii is soft and B is soft and Bjj is hard: is hard:•If both BIf both Bii and B and Bjj are soft: are soft:)2( (4))1()( (3))1( (2))( (1)ijijjjiijijjimaxiiminiiijijjjiijijjiiyxHyhyyxHywwhyyxWxwxyxWxwx)2()( (4))1()( (3))1( (2))( (1)ijijjjmaxjjminjiijijjimaxiiminiiijijjjiijijjiiyxHywwhyyxHywwhyyxWxwxyxWxwx1101/14/19Another way to linearize1201/14/19Solving Linear Program•Linear Programming (LP) can be solved by classical optimization techniques in polynomial time.•Mixed Integer LP (MILP) is NP-Complete. –The run time of the best known algorithm is exponential to the number of variables and equations1301/14/19Complexity•For a problem with n blocks, and for the simplest case, i.e., all blocks are hard:–2n continuous variables (xi, yi)–2n(n-1) +n integer variables (xij, yij, zi)–4n2-2n linear constraints•Practically, this method can only solve small size problems.1401/14/19Successive Augmentation A classical greedy approach to keep the problem size small: repeatedly pick a small subset of blocks to formulate a MILP, solve it together with the previously picked blocks with fixed locations and shapes:YPartial SolutionNext subset1501/14/19Floorplan Representations•Slicing–Normalized Polish Expression: Wong & Liu [DAC-86]•Mosaic (and General)–Corner Block List (CBL): Hong et al. [ICCAD-00]–Q-Sequence: Sakanushi & Kajitani [APCCAS-00]–Twin Binary Sequence (TBS): Young, Chu, Shen [ISPD-02]•General–Polar graphs: Ohtsuki et al. [ICCST-70]–Sequence pair: Murata et al. [ ICCAD-95]–Bounded Slicing Grid (BSG): Nakatake [ICCAD-96]–Transitive Closure Graph (TCG): Lin & Chang [DAC-01]•Compacted–O-tree: Guo et al. [DAC-99]–B*-tree: Chang et al. [DAC-00]01/14/1916General Floorplanning by Simulated Annealing:Sequence-Pair RepresentationGeneral Floorplanning by Simulated Annealing:Sequence-Pair RepresentationMurata, Fujiyoshi, Nakatake, Kajitani,Murata, Fujiyoshi, Nakatake, Kajitani,““VLSI Module Placement based on VLSI Module Placement based on Rectangle-Packing by the Sequence-PairRectangle-Packing by the Sequence-Pair””,,TCAD, 15:1518-1524, December 1996.TCAD, 15:1518-1524, December 1996.1701/14/19Sequence-Pair vs. Polish Expression•Sequence-Pair is a succinct representation of