Performance and Memory-Efficient Parallel Computing Framework for RSMT Construction

  • N. R. LathaEmail author
  • G. R. Prasad
Conference paper
Part of the Advances in Intelligent Systems and Computing book series (AISC, volume 1119)


Constructing fast and efficient Rectilinear Steiner Minimal Tree (RSMT) for modern VLSI circuit is a major issue in VLSI physical design (PD). Further, minimizing runtime and wire length is the most desired objective. The existing FLUTE-based VLSI routing model induces memory and I/O overhead. To overcome these research challenges, this paper presents a Memory-Efficient RSMT (MERSMT) construction that addresses the memory overhead problem that exists in larger nets. Further, the runtime of RSMT construction is reduced using High-Performance Computing (HPC) environment such as CPU and GPU. In order to get good trade-offs between memory efficiency and I/O efficiency, this paper presents a Performance and Memory Constraint Parallel Computation (PMCPC) algorithm. Experiments are conducted on ISPD 98 benchmarks and attained good results in terms of wire length, memory utilization, and processing time (i.e., runtime) when compared with standard VLSI routing design.


Graphical processing unit High-performance computing Multicore environment Parallel computing framework RSMT VLSI 


  1. 1.
    Chang, C.-Y., Tseng, I.-L.: A parallel algorithm for constructing obstacle-avoiding rectilinear Steiner minimal trees on multi-core systems. (2012)Google Scholar
  2. 2.
    Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826–834 (1977)MathSciNetCrossRefGoogle Scholar
  3. 3.
    Chu, C.: FLUTE: fast lookup table based wirelength estimation technique. In Proceedings IEEE/ACM International Conference on Computer-Aided Design, pp. 696–701 (2004)Google Scholar
  4. 4.
    Chu, C., Wong, Y.-C.: Fast and accurate rectilinear Steiner minimal tree algorithm for VLSI design. In: Proceedings International Symposisum on Physical Design, pp. 28–35 (2005)Google Scholar
  5. 5.
    Chu, C., Wong, Y.-C.: FLUTE: fast lookup table based rectilinear steiner minimal tree algorithm for VLSI design. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 27(1), 70–83 (2008)CrossRefGoogle Scholar
  6. 6.
    Wong, Y.-C., Chris, C.: A scalable and accurate rectilinear Steiner minimal tree algorithm. In: IEEE International Symposium on VLSI Design, Automation and Test, 2008 (VLSI-DAT 2008), IEEE (2008)Google Scholar
  7. 7.
    Ajwani, G., Chu, C., Mak, W.K.: FOARS: FLUTE based obstacle-avoiding rectilinear Steiner tree construction. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 30(2), 194–204 (2011)CrossRefGoogle Scholar
  8. 8.
    Huang, T., Young, E.F.Y.: An exact algorithm for the construction of rectilinear Steiner minimum trees among complex obstacles. In: Proceedings DAC (2011)Google Scholar
  9. 9.
    Hao, Z., Yea, D.-y., Guo, W.-z.: A heuristic for constructing a rectilinear Steiner tree by reusing routing resources over obstacles. 55, 162–175 (2016)Google Scholar
  10. 10.
    Saha, P.P., Saha, S., Samanta, T.: An efficient intersection avoiding rectilinear routing technique in VLSI. In: 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI), pp. 559–562, Mysore (2013)Google Scholar
  11. 11.
    Chow, W.-K., Li, L., Young, E.F.Y., Sham, C.-W.: Obstacle-avoiding rectilinear Steiner tree construction in sequential and parallel approach. Integr. VLSI J. 47, 105–114 (2014).
  12. 12.
    Wang, R.-Y., Pai, C.-C., Wang, J.-J., Wen, H.-T., Pai, Y.-C., Chang, Y.-W., Li, J., Jiang, J.-H.: Efficient multi-layer obstacle-avoiding region-to-region rectilinear Steiner tree construction. 1–6 (2018)Google Scholar
  13. 13.
    Bader, DA., Kanade, V., Madduri, K.: SWARM: a parallel programming framework for multicore processorsGoogle Scholar
  14. 14.
    Cai, Y., Deng, C., Zhou, Q., Yao, H., Niu, F., Sze, C.N.: Obstacle-avoiding and slew-constrained clock tree synthesis with efficient buffer insertion. In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 23, no. 1, pp. 142–155 (2015)Google Scholar
  15. 15.
    Liu, C.H., Lin, C.X., Chen, I.C., Lee, D.T., Wang, T.C.: Efficient multilayer obstacle-avoiding rectilinear steiner tree construction based on geometric reduction. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 33(12), 1928–1941 (2014)CrossRefGoogle Scholar
  16. 16.
    Held, S., Spirkl, S.T.: A fast algorithm for rectilinear Steiner trees with length restrictions on obstacles. In: Proceedings of the 2014 on International symposium on physical design, pp. 37–44, ACM, (2014)Google Scholar
  17. 17.
    Panda, S.K., Panda, D.C. (2018) Developing high-performance AVM based VLSI computing systems: a study. In: Pattnaik, P., Rautaray, S., Das, H., Nayak, J. (eds.) Progress in Computing, Analytics and Networking. Advances in Intelligent Systems and Computing, vol. 710. Springer, SingaporeGoogle Scholar
  18. 18.
    Latha, N.R., Prasad, G.R.: Wirelength and memory optimized rectilinear Steiner minimum tree routing. 1493–1497 (2017).
  19. 19.
    Ma, K., Zhou, Q., Cai, Y., Zhang, C., Qi, Z.: A Steiner tree construction method for flexibility and congestion optimization. In: 2013 International Conference on Communications, Circuits and Systems (ICCCAS), pp. 519–523, Chengdu (2013)Google Scholar
  20. 20.
    Wu, T.H., Davoodi, A., Linderoth, J.T.: GRIP: global routing via integer programming. IEEE Trans. Comput. Aided Des. Integr. Circ Syst. 30(1), 72–84 (2011)CrossRefGoogle Scholar
  21. 21.
    Pan, M., Xu, Y., Zhang, Y., Chu, C.: FastRoute: an efficient and high-quality global router. VLSI Des. 2012, 608362 (2012)MathSciNetCrossRefGoogle Scholar
  22. 22.
    Umair F. Siddiqi, Sadiq M. Sait, and Yoichi Shiraishi, “A Game Theory-Based Heuristic for the Two-Dimensional VLSI Global Routing Problem,” Journal Of Circuits Systems And Computers, vol. 24, no. 6, 2015Google Scholar
  23. 23.
    Siddiqi, Umair F., Sait, Sadiq M.: A game theory based post-processing method to enhance VLSI global routers. IEEE Access 5, 1328–1339 (2017)CrossRefGoogle Scholar
  24. 24.
    Momeni, A., Mistry, P., Kaeli, D.: A parallel clustering algorithm for placement. In: Fifteenth International Symposium on Quality Electronic Design, pp. 349–356, Santa Clara, CA (2014)Google Scholar
  25. 25.
    Wang, M., Li, Z.: A spatial and temporal locality-aware adaptive cache design with network optimization for tiled many-core architectures. In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 25, no. 9, pp. 2419–2433 (2017)Google Scholar
  26. 26.
    He, S., Wang, Y., Sun, X., Xu, C.: Using minmax-memory claims to improve in-memory workflow computations in the cloud. In: IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 4, pp. 1202–1214 (2017)Google Scholar
  27. 27.
    Song, J., Li, Q., Ma, S.: Toward bounds on parallel execution times of task graphs on multicores with memory constraints. IEEE Access 7 (2019)Google Scholar

Copyright information

© Springer Nature Singapore Pte Ltd. 2020

Authors and Affiliations

  1. 1.Department of CSEB.M.S. College of EngineeringBangaloreIndia

Personalised recommendations