Parallelization Strategies for the Detailed Routing Step

Abstract:
Since processor speeds have plateaued in recent years, other avenues need to be explored to speed up Electronic Design Automation (EDA) applications in order to keep pace with the growing complexity of VLSI designs. The ubiquity of multicore processors makes parallelization an obvious approach for achieving further performance improvements. However, fully realizing the potential provided by many-core systems requires the algorithms to be carefully designed to avoid bottlenecks. The detailed routing step can take a lot of time and therefore is a good candidate for performance improvements. However, the necessity of generating legal routing results makes it challenging to scale to lots of processing cores due to the necessary communication overhead. This paper gives an overview on different approaches to the problem. Furthermore, we identify the core problems of different approaches.