A parallel Steiner heuristic for wirelength estimation of large net populations

The authors discuss techniques to produce Steiner trees for a large population of nets, e.g., 1000 to 5000 nets, in parallel. This problem arises in iterative-improvement layout strategies that perturb not just a single placed object, but a few thousand objects simultaneously. Such strategies are the focus of work on mapping large placement problems onto massively parallel computers. The authors present a new heuristic that computes Steiner trees for an arbitrary number of nets, each with an arbitrary number of terminals, in essentially constant time given sufficient data-parallel machine resources and a constant distribution of net sizes. Experiments on a Connection Machine demonstrate that it is possible to create good Steiner trees for a few thousand nets in a few hundred milliseconds.