DOC PREVIEW
Area Fill Generation

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 ThicknessChemical-Mechanical Planarization (CMP) = wafer surface planarization Uneven features cause polishing pad to deformInterlevel-dielectric (ILD) thickness  feature densityInsert 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 RegimeGiven 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 featuresnmijTijFijFTile 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),(ijijUBLBijTRanged CFGP in Fixed-Dissection RegimeGiven 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 requirementsSingle-Tile Integer LP Formulations01pqs01apqijS,site in position (p,q) in tile (i,j)Afeasible AREF in layoutis covered by AREFpqijS,otherwiseotherwiseAREF is chosen AAREFsfeasiblealla1010kplqpqijsFpqseringAREFsallpqascov0pqspqijS,if is occupied by original featurespqseringAREFsallpqpqasncovMinimize:# 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 FormulationsIdeally consider fill compression on entire layout at one timeMultiple-tile compression as a tradeoff 1)1('1)1('''1,,1;1,,0kikipljBjqqpijBjAisF for tilesBARanged Fill CompressionExploit allowed range of fill features for each tileSingle-TileMultiple-Tile 1010kplqijpqijUBsLB 1)1('1)1('''1,,1;1,,0kikipijljBjqqpijBjAiUBsLB for tilesBA7Greedy Speedup ApproachesGreedy Speedup Approach 1 (GS-1) Find the largest AREFs originating from each free sitePick the AREF that fills the maximum number of free sites but does not overfill the tiles if such an AREF existsOtherwise, select the maximum AREF from the largest AREFs, and take one of its sub-AREFs which do not overfill the tilesTime complexity of the algorithm is reduced to O(n3)Motivation of SpeedupStrict greedy heuristic-O(n4) time complexity-Provide good solutions but is impracticalGreedy 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 siteCriteria of an acceptable AREF:-Size is smaller than K  L-Fill maximum free sites but does not overfill the tilesTime complexity of the algorithm is reduced to O(KLn2)GS-1 vs. GS-2Compared 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 optionGS-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-TileGreedy 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-2Performance of GS-1


Area Fill Generation

Download Area Fill Generation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Area Fill Generation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Area Fill Generation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?