Buffer insertion is a fundamental technology for very large scale integration interconnect optimization. This work presents the repeater insertion with adaptive tree adjustment (RIATA) heuristic that directly extends van Ginneken’s classic algorithm to handle blockages in the layout. Given a Steiner tree containing a Steiner point that overlaps a blockage, a local adjustment is made to the tree topology that enables additional buffer insertion candidates to be considered. This adjustment adapts to the demand on buffer insertion and is incurred only when it facilitates the maximal slack solution. RIATA can be combined with any performance-driven Steiner tree algorithm and permits various solution search schemes to achieve different solution quality and runtime tradeoffs. Experiments on several large nets confirms that high-quality solutions can be obtained through this technique with greater efficiency than simultaneous approaches.
Paper Location
ACM Portal
Citation
[1] J. Hu, C. Alpert, S. Quay, and G. Gandham, "Buffer insertion with adaptive blockage avoidance," Proceedings of the 2002 international symposium on Physical design, ACM, 2002, p. 97.
Positive
- Strong problem formulation, with use of set theory/graph theory.
- Long-winded and thorough algorithm description
- Figures 3 and 4 are outstanding figures to represent the ideas presented.
- Good experimental results!
Negative
- Fails to justify why their routing tree can be a represented as a binary tree.
- Presentation of their algorithm is mathematically rigorous, but obscures how the algorithm itself works.
No comments:
Post a Comment