Area Fill Generation With Inherent Data Volume ReductionCMP and Interlevel Dielectric ThicknessFill Compression ProblemFill Compression in Fixed-Dissection RegimeLinear Programming Based MethodsCompressible Fill Generation with AREFGreedy Speedup ApproachesGreedy Speedup Approaches (cont’d)Experiments: Greedy Speedup ApproachesExperiments: Greedy Speedup ApproachesComparison of fill compression methodsConclusions & Future WorksSlide 131Area Fill Generation With Inherent Data Volume ReductionYu Chen, Andrew B. Kahng, Gabriel Robins, Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky and Yuhong ZhengAlexander Zelikovsky and Yuhong Zheng(UCLA, UCSD, UVA, GSU)(UCLA, UCSD, UVA, GSU)http://vlsicad.ucsd.edu/http://vlsicad.ucsd.edu/Supported by Cadence Design Systems, Inc.,Supported by Cadence Design Systems, Inc.,NSF, the Packard Foundation, and NSF, the Packard Foundation, and State of Georgia’s Yamacraw InitiativeState of Georgia’s Yamacraw Initiative2CMP and Interlevel Dielectric ThicknessChemical-Mechanical Planarization (CMP) = wafer surface planarization Uneven features cause polishing pad to deformInterlevel-dielectric (ILD) thickness feature densityInsert dummy features to decrease variationPost-CMP ILD thicknessFeaturesArea fillfeaturesPost-CMP ILD thickness3Fill Compression Problem Compressible Fill Generation Problem (CFGP) Given a design rule-correct layout, create the minimum number of GDSII AREFs to represent area fill features such that the window density variation is within the given bounds (L,U)Original layoutFilled layout with 82 area featuresFilled layout with area features in 9 AREFs4Fill Compression in Fixed-Dissection RegimeOriginal layout infixed-dissection regimewindowstileTile with original featuresGrid the tile with feature size Satisfy fixed fill requirement (e.g., 56fill features) with minimum number of AREFs (e.g., 4 AREFs) Fixed CFGP in Fixed-Dissection RegimeGiven a design rule-correct layout consisting of tiles, the site arrays for each tile, and fill requirement for each tile, create the minimum number of AREFs to represent area fill features such that each tile contains exactly area fill featuresnmijTijFijFTile with original featuresGrid the tile with feature size Satisfy ranged fill requirement (e.g., 50 ~ 60 fill features) with minimum number of AREFs (e.g., 3 AREFs) ),(iji jUBLBnm),(ijijUBLBijTRanged CFGP in Fixed-Dissection RegimeGiven a design rule-correct layout consisting of tiles, the site arrays for each tile, and fill requirement range for each tile, create the minimum number of AREFs to represent area fill features such that each tile contains a number of area fill features in the range5Linear Programming Based Methods Main idea: Find minimum #AREFs in free sites for given fill requirementsSingle-Tile Integer LP Formulations01pqs01apqijS,site in position (p,q) in tile (i,j)Afeasible AREF in layoutis covered by AREFpqijS,otherwiseotherwiseAREF is chosen AAREFsfeasiblealla1010kplqpqijsFpqseringAREFsallpqascov0pqspqijS,if is occupied by original featurespqseringAREFsallpqpqasncovMinimize:# covered slack sites = given # fill featuresall sites covered by AREF are filledonly the sites covered by AREF can be filled6Compressible Fill Generation with AREF Multiple-Tile Integer LP FormulationsIdeally consider fill compression on entire layout at one timeMultiple-tile compression as a tradeoff 1)1('1)1('''1,,1;1,,0kikipljBjqqpijBjAisF for tilesBARanged Fill CompressionExploit allowed range of fill features for each tileSingle-TileMultiple-Tile 1010kplqijpqijUBsLB 1)1('1)1('''1,,1;1,,0kikipijljBjqqpijBjAiUBsLB for tilesBA7Greedy Speedup ApproachesGreedy Speedup Approach 1 (GS-1) Find the largest AREFs originating from each free sitePick the AREF that fills the maximum number of free sites but does not overfill the tiles if such an AREF existsOtherwise, select the maximum AREF from the largest AREFs, and take one of its sub-AREFs which do not overfill the tilesTime complexity of the algorithm is reduced to O(n3)Motivation of SpeedupStrict greedy heuristic-O(n4) time complexity-Provide good solutions but is impracticalGreedy speedup schemes-Trade-off between time complexity and compression performance-Pick acceptable AREFs instead of maximal AREFs8Greedy Speedup Approaches (cont’d)Greedy Speedup Approach 2 (GS-2)Pick the acceptable AREFs originating from each free siteCriteria of an acceptable AREF:-Size is smaller than K L-Fill maximum free sites but does not overfill the tilesTime complexity of the algorithm is reduced to O(KLn2)GS-1 vs. GS-2Compared to GS-1, GS-2 achieves better tradeoff between compression results and time complexity. While K·L << n, GS-2 results are just ~4% worse but ~39× faster than GS-1 based on our experiments.GS-1 cannot guarantee better behavior with multiple-tile option than with single-tile option because the sets of the largest AREFs are different for the single-tile option and the multiple-tile optionGS-2 does guarantee better behavior with multiple-tile option9Experiments: Greedy Speedup Approaches Compression Ratios: GS-1 vs. GS-205101520253035TestcasesC o m p re s s io n R a tioGS-1 Ranged Single-Tile GS-2 Ranged Single-Tile GS-1 Ranged Multiple-Tile GS-2 Ranged Multiple-TileGreedy approach can achieves very large compression ratios, especially when the fill features are small GS-1 gets better results for single-tile than for multiple-tile GS-2 results are always better for multiple-tile than for single-tile10Experiments: Greedy Speedup Approaches GS-2 achieves better tradeoff between performance and runtime GS-2 is much faster than GS-1, with only small quality degradation11Comparison of fill compression methodsPerformance of the fill compression methods01000200030004000500060007000T1/80K/4/1500 T2/80K/4/1500 T3/80K/4/1500 T4/12K/4/200 T5/12K/4/200 T6/12K/4/200Testcases# o f A R E F sFixed Fill: ILP Fixed Fill: GS-1 Fixed Fill: GS-2 Ranged Fill: ILP Ranged Fill: GS-1 Ranged Fill: GS-2Performance of GS-1
or
We will never post anything without your permission.
Don't have an account? Sign up