Buffered Steiner trees for difficult instances Conference Paper uri icon


  • 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.

published proceedings

  • Proceedings of the International Symposium on Physical Design

author list (cited authors)

  • Alpert, C. J., Hrkic, M., Hu, J., Kahng, A. B., Lillis, J., Liu, B., ... Villarrubia, P.

complete list of authors

  • Alpert, CJ||Hrkic, M||Hu, J||Kahng, AB||Lillis, J||Liu, B||Quay, ST||Sapatnekar, SS||Sullivan, AJ||Villarrubia, P

publication date

  • January 2001