Abstract
In this paper, we propose a runtime method for determining optimal delay insertion to avoid network contention in any communication pattern on a switching topology. The idea for finding an optimum solution is to deploy an arrival-consumption model that is able to independently estimate the occurrence of contention on sender processes. This independent estimation allows processes to calculate the optimal delay for each destination when processing send operations. The proposed method assumes that messages are transferred through a single network switch by an eager protocol. The experimental results on a 64-node cluster show that the maximum speedup over existing methods reached 10 times for an imbalanced case where the numbers of send operations and message sizes differ among processes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chen, Y., Griffith, R., Liu, J., Katz, R.H., Joseph, A.D.: Understanding TCP incast throughput collapse in datacenter networks. In: Proceedings of the 1st ACM Workshop Research on Enterprise Networking (WREN), pp. 73–82 (2009)
Demmel, J., Hoemmen, M., Mohiyuddin, M., Yelick, K.: Avoiding communication in sparse matrix computations. In: Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2008)
Gabriel, E., et al.: Open MPI: goals, concept, and design of a next generation MPI implementation. In: Kranzlmüller, D., Kacsuk, P., Dongarra, J. (eds.) EuroPVM/MPI 2004. LNCS, vol. 3241, pp. 97–104. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30218-6_19
Ino, F., Fujimoto, N., Hagihara, K.: LogGPS: a parallel computational model for synchronization analysis. In: Proceedings of the 8th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 133–142 (2001)
Karwande, A., Yuan, X., Lowenthal, D.K.: CC-MPI: a compiled communication capable MPI prototype for ethernet switched clusters. In: Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 95–106 (2003)
Kwak, B.J., Song, N.O., Miller, L.E.: Performance analysis of exponential backoff. IEEE/ACM Trans. Netw. 13(2), 343–355 (2005)
Message Passing Interface Forum: MPI: A Message-Passing Interface Standard Version 4.0 (2021). https://www.mpi-forum.org/docs/mpi-4.0/mpi40-report.pdf
Okuyama, T., et al.: Accelerating ODE-based simulation of general and heterogeneous biophysical models using a GPU. IEEE Trans. Parallel Distrib. Syst. 25(8), 1966–1975 (2014)
Shen, J., Ino, F., Farrés, A., Hanzich, M.: A data-centric directive-based framework to accelerate out-of-core stencil computation on a GPU. IEICE Trans. Inf. Syst. E103-D(12), 2421–2434 (2020)
Thakur, R., Rabenseifner, R., Gropp, W.: Optimization of collective communication operations in MPICH. Int. J. High Perform. Comput. Appl. 19(1), 49–66 (2005)
Wonnacott, D.G., Strout, M.M.: On the scalability of loop tiling techniques. In: Proceedings of the 3rd International Workshop Polyhedral Compilation Techniques (IMPACT), pp. 3–11 (2013)
Acknowledgment
This study was supported in part by the Japan Society for the Promotion of Science KAKENHI Grant Numbers JP22K11972 and JP20K21794. The authors would like to thank the anonymous reviewers for helpful comments to improve their paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Yamada, H., Okita, M., Ino, F. (2023). Accelerating Imbalanced Many-to-Many Communication with Systematic Delay Insertion. In: Takizawa, H., Shen, H., Hanawa, T., Hyuk Park, J., Tian, H., Egawa, R. (eds) Parallel and Distributed Computing, Applications and Technologies. PDCAT 2022. Lecture Notes in Computer Science, vol 13798. Springer, Cham. https://doi.org/10.1007/978-3-031-29927-8_33
Download citation
DOI: https://doi.org/10.1007/978-3-031-29927-8_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-29926-1
Online ISBN: 978-3-031-29927-8
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science