Planning for Local Net Congestion in Global Routing∗

Local nets are a major contributing factor to mismatch be-tween the global routing (GR) and detailed routing (DR) stages. A local net has all its terminals inside one global cell (gcell) and is traditionally ignored during global rout-ing. This work offers two contributions in order to estimate and manage the local nets at the GR stage. First, a proce-dure is given to generate gcells of non-uniform size in order to reduce the number of local nets and thus the cumulative error associated with ignoring or approximating them. Sec-ond, we approximate the resource usage of local nets at the GR stage by introducing a capacity for each gcell in the GR graph. With these two complementary approaches, we offer a mathematical model for the congestion-aware GR problem that captures local congestion with non-uniform gcells along with other complicating factors of modern designs including variable wire sizes, routing blockages, and virtual pins. A practical routing procedure is presented based on the math-ematical model that can solve large industry instances. This procedure is integrated with the CGRIP congestion analy-sis tool. In the experiments, we evaluate our techniques in planning for local nets during GR while accounting for other sources of congestion using the ISPD11 benchmarks