Buffered Steiner trees for difficult instances

C. J. Alpert, M. Hrkic, J. Hu, A. B. Kahng, J. Lillis, B. Liu, S. T. Quay, S. S. Sapatnekar, A. J. Sullivan, P. Villarrubia

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

26 Scopus citations

Abstract

Buffer insertion has become an increasingly critical optimization in high performance design. The problem of finding a delay-optimal buffered Steiner tree has been an active area of research, and excellent solutions exist for most instances. However, current approaches fail to adequately solve a particular class of real-world "difficult" instances which are characterized by a large number of sinks, variations in sink criticalities, and varying polarity requirements. We propose a new Steiner tree construction called C-Tree for these instance types. When combined with van Ginneken style buffer insertion, C-Tree achieves higher quality solutions with fewer resources compared to traditional approaches.

Original languageEnglish (US)
Title of host publicationProceedings of the International Symposium on Physical Design
Pages4-9
Number of pages6
StatePublished - Jan 1 2001
Event2001 International Symposium on Physical Design - Sonoma, CA, United States
Duration: Apr 1 2001Apr 4 2001

Other

Other2001 International Symposium on Physical Design
CountryUnited States
CitySonoma, CA
Period4/1/014/4/01

Cite this