View Full Document

12 views

Unformatted text preview:

Supported by Cadence Design Systems Inc NSF the Packard Foundation and State of Georgia s Yamacraw Initiative Area Fill Generation With Inherent Data Volume Reduction Yu Chen Andrew B Kahng Gabriel Robins Alexander Zelikovsky and Yuhong Zheng UCLA UCSD UVA GSU http vlsicad ucsd edu 1 CMP and Interlevel Dielectric Thickness Chemical Mechanical Planarization CMP wafer surface planarization Uneven features cause polishing pad to deform Features Post CMP ILD thickness Interlevel dielectric ILD thickness feature density Insert dummy features to decrease variation Area fill features Post CMP ILD thickness 2 Fill 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 layout Filled layout with area Filled layout features in 9features AREFs with 82 area 3 Fill Compression in Fixed Dissection Regime Fixed CFGP in Fixed Dissection Regime Ranged CFGP in Fixed Dissection Regime nn tiles Given m Given aa design designrule correct rule correctlayout layoutconsisting consistingofof m tiles the the site arrays for each tile and fill requirement Fij for each tile site arrays for each tile and fill requirement range LBij UBij for create the minimum number of AREFs to represent area fill each tile such create minimum number of AREFsFijto represent features thatthe each tile Tij contains exactly area fill area fill features such that each tile Tij contains a number of area features fill features in the range LBij UBij windows Original layout in Gridwith the tile fill with feature size e g Tile original features Satisfy fixed ranged fill requirement requirement 56 fixed dissection regime e g fill features 50 60 fill features with minimum with minimum number of AREFs number of e g AREFs 4 AREFs e g 3 AREFs tile 4 Linear Programming Based Methods Main idea Find minimum AREFs in free sites for given fill requirements Single Tile Integer LP Formulations Sij pq site in position p q in tile i j s pq 1 Sij pq is covered by AREF 0 otherwise Minimize A feasible AREF in layout 1 a 0 AREF A is chosen otherwise a all feasible AREFs k 1 l 1 Fij s pq covered slack sites given fill features p 0 q 0 n pq s pq a all sites covered by AREF are filled all AREFs cov ering s pq s pq a only the sites covered by AREF can be filled all AREFs cov ering s pq s pq 0 if Sij pq is occupied by original features 5 Compressible 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 i 1 k 1 j 1 l 1 Fij p i k s i 0 A 1 j 1 B 1 p q for A B tiles q j B Ranged Fill Compression Exploit allowed range of fill features for each tile Single Tile k 1 LBij p 0 l 1 s pq UBij q 0 Multiple Tile i 1 k 1 j 1 l 1 LBij s p i k p q UBij i 0 A 1 j 1 B 1 for A B tiles q j B 6 Greedy Speedup Approaches 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 AREFs 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 7 Greedy 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 option 8 Experiments Greedy Speedup Approaches Compression Ratios GS 1 vs GS 2 GS 1 Ranged Single Tile GS 2 Ranged Single Tile GS 1 Ranged Multiple Tile GS 2 Ranged Multiple Tile C o m p re s s io n R a tio 35 30 25 20 15 10 5 0 Testcases 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 tile 9 Experiments Greedy Speedup Approaches GS 2 achieves better tradeoff between performance and runtime GS 2 is much faster than GS 1 with only small quality degradation 10 Comparison of fill compression methods Run time of the fillfill compression Performance of the compressionmethods methods Fixed Fill Fill ILP ILP Fixed Fixed Fill Fill GS 1 GS 1 Fixed Fixed Fill Fill GS 2 GS 2 Fixed Ranged Fill ILP Ranged Fill ILP Ranged Ranged Fill Fill GS 1 GS 1 Ranged RangedFill Fill GS 2 GS 2 100000 7000 6000 10000 R uo nf A tRiEmF se 5000 1000 4000 3000 100 2000 1000 10 0 T2 80K 4 1500 T3 80K 4 1500 T4 12K 4 200 1 T1 80K 4 1500 T1 80K 4 1500 T2 80K 4 1500 T3 80K 4 1500 TestcasesT4 12K 4 200 T5 12K 4 200 T5 12K 4 200 T6 12K 4 200 T6 12K 4 200 Test cases Performance of GS 1 is very close to optimal ILP method GS 1 is more efficient in run time than ILP method 11 Conclusions Future Works Contributions New compressed fill strategies with AREF to reduce data volume Linear programming based methods Greedy based optimization methods Future Works Improve compression ratios and scalability Exploit new standard layout format Open Artwork System Interchange Standard OASIS Compressible fill generation problem with underlying layout hierarchy 12 Thank You 13


Access the best Study Guides, Lecture Notes and Practice Exams

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 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?