GR-PA: A cost pre-allocation model for global routing

This work presents methods to identify and treat circuit areas that have high overflow and interconnect demand, during global routing step. In that way, two cost pre-allocation techniques are presented: the first is applied during the pre-routing congestion estimation step of the global routing flow; the second technique will act during the iterative routing phase, where the the congestion is updated on each routing round and the congestion hot spots can be identified. Since the congestion hot spots are identified, a cost calibration step is executed using the proposed congestion look-ahead techniques. The focus of these algorithms is to speed up the convergence of the global routing solution while trying to reduce the side effects in wire length. Our experiments shows a speed up of up to 1.357x with 1.39% of maximum increase in wirelength when compared to the reference implementation for the ISPD 2008 benchmarks.