Abstract
Routability has become very challenging with designs scaling down. Recently, many placement tools adopt routing congestion estimators (RCEs) to guide their algorithms, and designers can adopt RCEs to judge whether their designs are routable in the early design stage. Thus, industry desires a fast and accurate RCE to reduce the design cost and speed up time-to-market. Typically, RCEs can be categorized into two types, the probability-based and the global-routing-based (GR-based) methods. Because GR-based RCEs are more accurate than probability-based RCEs in congestion estimation, integrating GR-based RCEs into placers has become a trend. However, GR-based RCEs are much slower than probability-based RCEs, that becomes a critical issue when GR-based RCEs are iteratively launched by placers. To accelerate GR-based RCEs, this thesis presents a resource-based parallel strategy (RPS) to partition a global routing problem into several independent sub-problems, and these sub-problems can be concurrently solved by multiple threads. The concept of RPS is to first duplicate the routing graph to several copies, and dispatches the routing resource and nets from the original routing graph to each duplicated graph. After that, the routing problem in each duplicated graph can be solved concurrently. Finally, the routing results in duplicated graphs are merged together to form a final routing result in the original graph. Compared to the traditional region-based parallel strategy, RPS can better handle the situations when many nets have bounding boxes overlapping with each other and a net crosses multiple regions. However, how to dispatch routing resource and nets to each duplicated graph is a challenging problem. If the nets and routing resource are not dispatched properly, the quality of routing results degrades and the computation effort of each thread may be unbalanced. This thesis presents resource allocation, net dispatching, and routing effort balancing methods to even the routing effort of each thread. Experimental results reveal that an existing GR-based RCE with the proposed RPS can averagely achieve 3.4X speedup with four threads.