文档介绍：Large Scale Circuit Placement: Gap and PromiseJason CongUCLA VLSI CAD LAB1Joint work with Chin-Chih Chang, Tim Kong, Michail Romesis, Joseph R. Shinnerl, Min Xie and Xin YuanOutlinenIntroductionnGap Analysis of Existing Placement AlgorithmsnScalable Paradigm – Multilevel PlacementWhy Still Placement ProblemnTrue, it has been studied over 30 years, but …nWe need good solutions more then everuOne of most important steps in IC implementation flowFDirectly defines interconnectsnDifficultuProblem size grows 2X every 18-24 monthsFMoore’s LawuCannot place hierarchically without quality degradationExample of Logic Hierarchy in Final LayoutBy courtesy of IBM (Tony Drumm)Why Still PlacementnTrue, it has been studied over 30 years, but …nWe need good solutions more then everuOne of most important steps in IC implementation flowFDirectly defines interconnectsnDifficultuProblem size grows 2X every 18-24 monthsFMoore’s LawuCannot place hierarchically without quality degradationnWe are not very good at it …OutlinenIntroductionnGap Analysis of Existing Placement AlgorithmsnScalable Paradigm – Multilevel PlacementMotivationnLack of significant progress in wirelengthreductionuRate of reduction is about 5-10% every 2-3 yearsuLatest developments in placement differ mainly in runtimenMost pare only with known heuristicsuUse real design based benchmarksuUse synthetic benchmarksnLittle understanding about the divergence from the optimalPlacement Examples with Known Optimal Wirelength [Chang et al, 2003]nAll the modules are of equal size, and there is no space between rows and adjacent modulesnFor 22-s , connect any two adjacent modules/ 2n n n? ?? ? ??? ?? ? ??? ?? ?nFor each nn- , connect the nnmodules in a rectangular region close to a square, ., the length of each side is close to sqrt(n)nThe wirelength is of each nn- is given bynGiven a (real) listN’ with known opt. WL and match distribution of NPlacement Exam