A Theoretical Study on Wire Length Estimation Algorithms for Placement with Opaque Blocks

How to estimate the shortest routing length when certain blocks are considered as routing obstacles is becoming an essential problem for block placement because HPWL, is no longer valid in this case. Although this problem is well studied in computational geometry (Mitchell, 2000), the research results are neither well-known to the CAD community nor presented in a way easy for CAD researchers to ultilize their establishment. With the help of some recent notions in block placement, this paper interprets the research result in Atallah and Chen (1991) and de Rezende et al. (1985), which gives the best algorithm for this problem as we know, in a way more concise and more friendly to CAD researchers. Besides, we also tailor its algorithm to VLSI CAD application. As the result, we present a method that estimates the shortest obstacle-avoiding routing length in 0(M² + N) time for a placement with M blocks and N 2-pin nets.