X-architecture placement based on effective wire models

ABSTRACT

In this paper, we derive the X-half-perimeter wirelength (XHPWL) model for X-architecture placement and explore the effects of three different wire models on X-architecture placement, including the Manhattan-half-perimeter wirelength (MHPWL) model, the XHPWL model, and the X-Steiner wirelength (XStWL) model. For min-cut partitioning placement, we propose a generalized net-weighting method that can exactly model the wirelength after partitioning by the net weight. The net-weighting method is general and can be incorporated into any wire models such as the XHPWL and XStWL models. For analytical placement, we smooth the XHPWL function using log-sum-exp functions to facilitate analytical placement. Our study shows that both the XHPWL model and the XStWL model can reduce the X wirelength. In particular, our results reveal the effectiveness of the X architecture on wirelength reduction during placement and thus the importance of the study on the X-placement algorithms, which is different from the results given in the previous work that the X-architecture placement might not improve the X-routing wirelength over the Manhattan-architecture placement.

References

1. S. N. Adya, M. C. Yildiz, I. L. Markov, P. G. Villarrubia, P. N. Parakh, and P. H. Madden. Benchmarking for large-scale placement and beyond. IEEE Trans. Computer-Aided Design, 23(4):472--487, 2004.
2. A. R. Agnihotri, S. Ono, and P. H. Madden. Recursive bisection placement: Feng Shui 5.0 implementation details. In Proceedings of ACM International Symposium on Physical Design, pages 230--232, San Francisco, CA, Apr. 2005.
3. C. J. Alpert, J.-H. Huang, and A. B. Kahng. Multilevel circuit partitioning. IEEE Trans. Computer-Aided Design, 17(8):655--667, Aug. 1998.
4. Z. Cao, T. Jing, Y. Hu, Y. Shi, X. Hong, X. Hu, and G. Yan. DraXRouter: global routing in X-architecture with dynamic resource assignment. In Proceedings of IEEE/ACM Asia South Pacific Design Automation Conference, pages 618--623, Yokohama, Japan, Jan. 2006.
5. T. Chan, J. Cong, J. Shinnerl, K. Sze, and M. Xie. mPL6: Enhanced multilevel mixed-size placement. In Proceedings of ACM International Symposium on Physical Design, pages 212--214, San Jose, CA, Apr. 2006.
6. T. Chan, J. Cong, and K. Sze. Multilevel generalized force-directed method for circuit placement. In Proceedings of ACM International Symposium on Physical Design, pages 185--192, San Francisco, CA, Apr. 2005.
7. H. Chen, C.-K. Cheng, A. B. Kahng, I. Mandoiu, and Q. Wang. Estimation of wirelength reduction for λ-geometry vs. Manhattan placement and routing. In Proceedings of System Level Interconnect Prediction Workshop, pages 71--76, Monterey, CA, Apr. 2003.
8. T.-C. Chen, Y.-W. Chang, and S.-C. Lin. IMF: Interconnect-driven multilevel floorplanning for large-scale building-module designs. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 159--164, San Jose, CA, Nov. 2005.
9. T.-C. Chen, T.-C. Hsu, Z.-W. Jiang, and Y.-W. Chang. NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs. In Proceedings of ACM International Symposium on Physical Design, pages 236--238, San Francisco, CA, Apr. 2005.
10. T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, and Y.-W. Chang. A high-quality mixed-size analytical placer considering preplaced blocks and density constraints. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, San Jose, CA, Nov. 2006.
11. H. Eisenmann and F. M. Johannes. Generic global placement and floorplanning. In Proceedings of ACM/IEEE Design Automation Conference, pages 269--274, June 1998.
12. C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Proceedings of ACM/IEEE Design Automation Conference, pages 175--181, 1982.
13. T.-Y. Ho, C.-F. Chang, Y.-W. Chang, and S.-J. Chen. Multilevel full-chip routing for the X-based architecture. In Proceedings of ACM/IEEE Design Automation Conference, pages 597--602, Anaheim, CA, June 2005.
14. A. B. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. IEEE Trans. Computer-Aided Design, 24(5), May 2005.
15. A. B. Kahng and Q. Wang. A faster implementation of APlace. In Proceedings of ACM International Symposium on Physical Design, pages 218--220, San Jose, CA, Apr. 2006.
16. G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. In Proceedings of ACM/IEEE Design Automation Conference, pages 343--348, New Orleans, LA, June 1999.
17. B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49:291--307, Feb. 1970.
18. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. Gordian: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. Computer-Aided Design, 10(3):356--365, 1991.
19. W. C. Naylor, R. Donelly, and L. Sha. US patent 6,301,693: Non-linear optimization system and method for wire length and dealy optimization for an automatic electric circuit placer. 2001.
20. S. Ono, S. Tilak, and P. H. Madden. Bisection based placement for the X architecture. In Proceedings of IEEE/ACM Asia South Pacific Design Automation Conference, Yokohama, Japan, Jan. 2007 (to appear).
21. J. Roy, D. Papa, A. Ng, and I. Markov. Satisfying whitespace requirements in top-down placement. In Proceedings of ACM International Symposium on Physical Design, pages 206--208, San Jose, CA, Apr. 2006.
22. J. A. Roy, J. F. Lu, and I. L. Markov. Seeing the forest and the trees: Steiner wirelength optimization in placement. In Proceedings of ACM International Symposium on Physical Design, San Francisco, CA, Apr. 2005.
23. N. Selvakkumaran and G. Karypis. Theto - a fast and high-quality paritioning driven global placer. Technical Report 03-46, Dept of Computer Science and Engineering, Univeristy of Minnesota, Nov. 2003.
24. N. Selvakkumaran and G. Karypis. Theto - a fast and high-quality paritioning driven placement tool. Technical Report 04-40, Dept of Computer Science and Engineering, Univeristy of Minnesota, Oct. 2004.
25. T. Taghavi, X. Yang, B.-K. Choi, M. Wang, and M. Sarrafzadeh. Dragon2006: Blockage-aware congestion-controlling mixed-size placer. In Proceedings of ACM International Symposium on Physical Design, pages 209--211, San Jose, CA, Apr. 2006.
26. S. L. Teig. The X architecture: not your father's diagonal wiring. In Proceedings of System Level Interconnect Prediction Workshop, pages 33--38, San Diego, CA, Apr. 2002.
27. S. L. Teig and J. L. Ganley. US patent 6,848,091: Partitioning placement method and apparatus. 2002.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing