A depth-first-search controlled gridless incremental routing algorithm for VLSI circuits

In the engineering change order (ECO) process, engineers make changes to VLSI circuits after their layouts are completed in order to correct electrical problems or design errors. As far as routing is concerned, in order to capitalize on the enormous resources and time already spent on routing the circuit, and to meet time-to-market requirements, it is desirable to re-route only the ECO-affected portion of the circuit, while minimizing any routing changes in the larger unaffected part of the circuit in order to preserve its electrical properties. In this paper, we develop a novel algorithm to find incremental routing solutions using a gridless framework for VLSI circuits that require variable width and variable spacing on interconnects. The basic idea in our algorithm is to route the new or ECO-modified nets by minimally re-arranging, if necessary, some portions of some existing nets using a novel DFS controlled process that does not allow the perturbed existing nets´ lengths and topologies to change beyond pre-set limits. With these constraints, it explores a number of low-cost ways of re-routing the portions of these nets within the available routing resources (2 metal layers only). Experimental results show that within the above constraints our incremental router succeeds in routing more than 98% of ECO-generated nets, and also that its failure rate is 5 to 12 and 2.4 to 9 times less than that of previous incremental routing techniques standard (Std) and Rip-up&Reroute (R&R), respectively. It is also able to route most of the wide nets using a reasonable number of vias and with near-minimal net lengths.