A parallel Steiner heuristic for wirelength estimation of large net populations

Rajeev Jayaraman, Rob A. Rutenbar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers
PublisherPubl by IEEE
Pages344-347
Number of pages4
ISBN (Print)0818621575
StatePublished - Dec 1 1992
Event1991 IEEE International Conference on Computer-Aided Design - ICCAD-91 - Santa Clara, CA, USA
Duration: Nov 11 1991Nov 14 1991

Publication series

Name1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers

Other

Other1991 IEEE International Conference on Computer-Aided Design - ICCAD-91
CitySanta Clara, CA, USA
Period11/11/9111/14/91

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'A parallel Steiner heuristic for wirelength estimation of large net populations'. Together they form a unique fingerprint.

  • Cite this

    Jayaraman, R., & Rutenbar, R. A. (1992). A parallel Steiner heuristic for wirelength estimation of large net populations. In 1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers (pp. 344-347). (1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers). Publ by IEEE.