Conference Agenda

Global routing in VLSI design involves connecting chip objects with wires through rectilinear Steiner trees, subject to various constraints and optimization goals.

It aims for a solution close to a feasible (detailed) routing while relaxing design rule constraints.

Traditionally, global routing is modeled as a Steiner tree packing problem in a 3D grid graph subject to capacities on the edges. In this model, all objects are mapped to nodes of this coarse grid graph, neglecting the fact that connections to the detailed pin shapes need to be made.

An alternative approach, first introduced by Hähnle and Saccardi, uses uniform rhomboidal tiles to cover the chip area and assigns each tile a capacity for metal object area. Here, too, the global routing problem is a Steiner tree packing problem, but with no wire or pin position restrictions and considering tile area capacities instead of edge capacities. Wire space utilization is measured according to the intersection length with the rhomboidal tiles.

We extend the model of Hähnle and Saccardi by introducing continuous costs for vias (segments that connect consecutive layers of a chip) and we provide a polyhedral description of rectilinear graphs with a fixed structure and their rhomboidal usages.

Using this description, we derive a proof that minimum cost Steiner trees, rather than paths, lie on the rhomboidal Hanan grid.

Further, we extend goal-oriented path search techniques to the rhomboidal model.

The competitiveness of this continuous routing approach is demonstrated by comparing detailed routing results to an industrial traditional global router.

We consider a special case of the set cover problem which we call the Preselected Path Multi-Cover problem. In this problem, we are given a graph with demands on the vertices as well as a family of paths with capacities and cost. Our goal is finding a minimum-cost multisubset of these paths that cover the demands of of all vertices. It is known that this problem is APX-hard even on trees.We consider the problem on graphs that become trees if a constant number of edges is removed. The minimum number of edges we need to remove to turn a graph into a forest is called the cyclomatic number. We give a 5-approximation algorithm for Preselected Path Multi-Cover on graphs with bounded cyclomatic number. Furthermore, we give a 5log(k)-approximation algorithm, where k is the cyclomatic number, with a runtime independent of k. For the latter algorithm, we modify the greedy algorithm for Set Multicover so it can deal with having convex instead of linear costs on singlet sets only. This modified greedy algorithm may be of independent interest.