Tree Structures and Algorithms for Physical Design

ABSTRACT

Tree structures and algorithms provide a fundamental and powerful data abstraction and methods for computer science and operations research. In particular, they enable significant advancement of IC physical design techniques and design optimization. For the last half century, Prof. T. C. Hu has areas in computer science, including network flows, integer programming, shortest paths, binary trees, global routing, etc. In this article, we select and summarize three important and interesting tree-related topics (ancestor trees, column generation, and alphabetical trees) in the highlights of Prof. T. C. Hu's contributions to physical design.

References

1. C. Albrecht, "Provably Good Global Routing by A New Approximation Algorithm for Multicommodity Flow", Proc. ISPD, 2000, pp. 19--25.
2. F. Alvelos and J. M. V. de Carvalho, "An Extended Model and a Column Generation Algorithm for the Planar Multicommodity Flow Problem", Networks 50(1) (2007), pp. 3--16.
3. W. Ben-Ameur and J. Neto, "Acceleration of Cutting-Plane and Column Generation Algorithms: Applications to Network Design", Networks 49(1) (2007), pp. 3--17.
4. R. C. Carden, J. Li and C. K. Cheng, "A Global Router with a Theoretical Bound on the Optimal Solution", IEEE Trans. on CAD 15(2) (1996), pp. 208--216.
5. Y. C. Chang, Y.-W. Chang, G. M. Wu and S. W. Wu, "B*-Trees: A New Representation for Non-Slicing Floorplans", Proc. DAC, 2000, pp. 458--463.
6. S.-J. Chen and C. K. Cheng, "Tutorial on VLSI Partitioning", VLSI Design 11(3) (2000), pp. 175--218.
7. C. K. Cheng, "The Optimal Partitioning of Networks", Networks 22(3) (1992), pp. 297--315.
8. C. K. Cheng and T. C. Hu, "Ancestor Tree for Arbitrary Multi-Terminal Cut Functions", Annals of Operations Research 33(3) (1991), pp. 199--213.
9. C. K. Cheng and T. C. Hu, "Maximum Concurrent Flows and Minimum Ratio Cuts", Algorithmica 8(1) (1992), pp. 233--249.
10. C. Contardo, J.-F. Cordeau and B. Gendron, "An Exact Algorithm Based on Cut-and-Column Generation for the Capacitated Location-Routing Problem", INFORMS Journal on Computing 26(1) (2014), pp. 88--102.
11. L. R. Ford and D. R. Fulkerson, "Maximal Flow through a Network", Canadian Journal of Mathematics 8(3) (1956), pp. 399--404.
12. V. Gabrel, A. Knippel and M. Minoux, "Exact Solution of Multicommodity Network Optimization Problems with General Step Cost Functions", Operations Research Letters 25(1) (1999), pp. 15--23.
13. E. N. Gilbert and E. F. Moore, "Variable Length Binary Encodings", Bell System Technical Journal 38 (1959), pp. 933--968.
14. R. E. Gomory and T. C. Hu, "Multi-Terminal Network Flows", Journal of SIAM 9(4) (1961), pp. 551--570.
15. J. Gondzio, P. González-Brevis and P. Munari, "New Developments in the Primal-Dual Column Generation Technique", European Journal of Operational Research 224(1) (2013), pp. 41--51.
16. J. Gondzio, P. González-Brevis and P. Munari, "Large-Scale Optimization with the Primal-Dual Column Generation Method", Mathematical Programming Computation 8(1) (2016), pp. 47--82.
17. P.-N. Guo, T. Takahashi, C. K. Cheng and T. Yoshimura, "Floorplanning Using a Tree Representation", IEEE Trans. on CAD 20(2) (2001), pp. 281--289.
18. J. Hu and S. S. Sapatnekar, "A Survey on Multi-Net Global Routing for Integrated Circuits", Integration, the VLSI Journal 31(1) (2001), pp. 1--49.
19. T. C. Hu, "Multi-Commodity Network Flows", Operations Research 11(3) (1963), pp. 344--360.
20. T. C. Hu and A. B. Kahng, Linear and Integer Programming Made Easy, Springer, 2016.
21. T. C. Hu and M. T. Shing, "A Decomposition Algorithm for Circuit Routing", Mathematical Programming Study 24 (1985), pp. 87--103.
22. T. C. Hu and M. T. Shing, Combinatorial Algorithms, 2nd Ed., Dover Publications, 2002.
23. T. C. Hu and A. C. Tucker, "Optimal Computer Search Trees and Variable-Length Alphabetical Codes", Journal of SIAM 21(4) 1971, pp.514--532.
24. J. Huang, X. L. Hong, C. K. Cheng and E. S. Kuh, "An Efficient Timing-Driven Global Routing Algorithm", Proc. DAC, 1993, pp. 596--600.
25. J. Janacek, M. Kohani, M. Koniorczyk and P. Marton, "Optimization of Periodic Crew Schedules with Application of Column Generation Method", Transportation Research Part C: Emerging Technologies 83 (2017), pp. 165--178.
26. G.-W. Jeong, K. Lee, S. Park and K. Park, "A Branch-and-Price Algorithm for the Steiner Tree Packing Problem", Computers & Operations Research 29(3) (2002), pp. 221--241.
27. D. G. Jørgensen and M. Meyling, "A Branch-and-Price Algorithm for Switch-Box Routing", Networks 40(1) (2002), pp. 13--26.
28. A. B. Kahng, J. Lienig, I. L. Markov and J. Hu, VLSI Physical Design: From Graph Partitioning to Timing Closure, Springer, 2011.
29. D. E. Knuth, "Optimum Binary Search Trees", Acta Informatica 1 (1971), pp. 14--25.
30. M. E. Kuo and C. K. Cheng, "A Network Flow Approach for Hierarchical Tree Partitioning", Proc. DAC, 1997, pp. 512--517.
31. G. Laporte, "The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms", European Journal of Operational Research 59(3) (1992), pp. 345--358.
32. L.-T. Liu, M.-T. Kuo, C. K. Cheng and T. C. Hu, "A Replication Cut for Two-Way Partitioning", IEEE Trans. on CAD 14(5) (1995), pp. 623--630.
33. J. Liu, S. Zhou, H. Zhu and C. K. Cheng, "An Algorithmic Approach for Generic Parallel Adders", Proc. ICCAD, 2003, pp. 734--740.
34. M. E. Lubbecke and J. Desrosiers, "Selected Topics in Column Generation", Operations Research 53(6) (2005), pp. 1007--1023.
35. T. Nishi and T. Izuno, "Column Generation Heuristics for Ship Routing and Scheduling Problems in Crude Oil Transportation with Split Deliveries", Computers & Chemical Engineering 60 (2014), pp. 329--338.
36. M. Pedram and H. Vaishnav, "Technology Decomposition Using Optimal Alphabetic Trees", Proc. ECDA, 1993, pp. 573--577.
37. D. Potthoff, D. Huisman and G. Desaulniers, "Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling", Transportation Science 44 (2010), pp. 493--505.
38. H. Vaishnav and M. Pedram, "Alphabetic Trees - Theory and Applications in Layout-Driven Logic Synthesis", IEEE Trans. on CAD 42(2) (2002), pp. 219--223.
39. A. Vittal and M. Marek-Sadowska, "Minimal Delay Interconnect Design Using Alphabetic Trees", Proc. DAC, 1994, pp. 392--396.
40. T. H. Wu, A. Davoodi and J. T. Linderoth, "GRIP: Global Routing via Integer Programming", IEEE Trans. on CAD 30(1) (2011), pp. 72--84.
41. B. Yao, H. Chen, C. K. Cheng and R. Graham, "Floorplan Representations: Complexity and Connections", ACM Trans. on DAES 8(1) (2003), pp. 55--80.
42. E. F. Y. Young, C. C. N. Chu and Z. C. Shen, "Twin Binary Sequences: A Nonredundant Representation for General Nonslicing Floorplan", IEEE Trans. on CAD 22(4) (2003), pp. 457--469.
43. Y. Zhu, J. Liu, H. Zhu and C. K. Cheng, "Timing-Power Optimization for Mixed-Radix Ling Adders by Integer Linear Programming", Proc. ASP-DAC, 2008, pp. 131--137.
44. Brief Biography of Dr. Te Chiang Hu, The Institute for Operations Research and the Management Sciences, http://www.informs.org/Explore/History-of-O.R.-Excellence/Biographical-Profiles/Hu-Te-Chiang/.
45. Column Generation and Dantzig-Wolfe Decomposition, Group for Research in Decision Analysis (GERAD), http://www.science4all.org/article/column-generation/.
46. Duality Theory in LP, http://www.slideshare.net/jyothimonc/duality-in-linear-programming/.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

• Mathematics of computing

• Theory of computation

  • Theory and algorithms for application domains