具有网络排序优化的成对间距约束封装布线.pdf

1、Paired-Spacing-Constrained Package Routing with Net Ordering OptimizationPresenter:Ying-Jie JiangAdvisor:Shao-Yun Fang12OutlineIntroductionAlgorithm FlowNet Ordering DeterminationTile and Network Graph ConstructionMCMF-based Global Routing DerivationExperimental ResultsConclusion3Introduction4Introd

2、uctionPaired-spacing constraint is one of the most important constraints in advanced package technologyA net may require different spacing depending on the nets it is adjacent toThere can be at most 2 spacing rules for netsIt is important to establish different spacing rules for different bump netsE

3、nsure signal integrity Minimize crosstalk5Example of Pair SpacingIf we apply post-refinement or a pessimistic spacing ruleResult in suboptimal solution:Normal Net Bump:Critical Spacing:Normal Spacing:Critical Net Bump:Ball:Spacing Violation(a)(b)(c)(d)6Design RulesNon-crossing ConstraintTwo nets can

4、not be routed across each otherRouting Direction ConstraintRouted in four kinds of orientationVertical,horizontal,45,and 135Routing Angle ConstraintReversed 45 turn is not allowedPaired Spacing ConstraintFor normal(non-critical)nets,keep at least a distance from other netsFor critical nets,keep at l

5、east a distance from other nets7Problem FormulationGivenA chip set,a normal bump set,a critical bump set,and a ball grid array(BGA)Wire width Spacing rules for normal bumps and critical bumpsOutputConnect all bumps to ballsMinimized wirelengthWithout any design rule violationFor better readability a

6、nd more concise explanationsOnly consider two spacing constraints in our workCritical spacing rule,normal spacing rule.The proposed algorithm can be trivially extended to general problem instancesArbitrary spacing value can be set between each pair of adjacent nets.8Algorithm Flow9Algorithm Overview