Accurate Heterogeneous Communication Models and a Software Tool for Their Efficient Estimation

Abstract

In this paper, we analyze the restrictions of traditional communication performance models that affect the accuracy of analytical prediction of the execution time of collective communication operations on homogeneous and heterogeneous clusters. In particular, we show that the constant and variable contributions of processors and the network are not fully separated in these models. Full separation of the contributions that have different natures and arise from different sources would lead to more intuitive and accurate models, but the parameters of such models cannot be estimated from only the point-to-point experiments, which are usually used for traditional models. The paper presents such an intuitive and accurate point-to-point model and describes a set of communication experiments sufficient for estimation of its parameters. It also presents an implementation of the new model in the form of a software tool that automates the estimation of both this model and heterogeneous extensions of traditional communication performance models. We conclude with a presentation of experimental results demonstrating that the elaborated model much more accurately predicts the execution time of different algorithms of collective operations than traditional models.

Keywords

heterogeneous cluster communication performance model message-passing interface communication model estimation

Get full access to this article

View all access options for this article.

References

Alexandrov, A. , Ionescu, M. , Schauser, K. and Scheiman, C. ( 1997). LogGP: incorporating long messages into the LogP model for parallel computation. J. Parallel Distrib. Comput. 44(1): 71-79.

Bai, J. and Perron, P. ( 2003). Computation and analysis of multiple structural change models, J. Appl. Econometrics 18(1): 1-22.

Bhat, P. , Prasanna, V. , and Raghavendra, C. ( 2003). Efficient collective communication in distributed heterogeneous systems, J. Parallel and Distributed Computing, 63: 251-263.

Chan, E. , Heimlich, M. , Purakayastha, A. , Geijn, R. van de ( 2004). On optimizing collective communication. In Proc. Of Cluster 2004, pp. 145-155, IEEE Computer Society.

Culler, D. , Karp, R. , Patterson, D. , Sahay, A. , Schauser, K. , Santos, E. , Subramonian, R. and Eicken, T. von. ( 1993). LogP: towards a realistic model of parallel computation . In Proceedings of PPoPP 1993, ACM, pp. 1-12.

Galassi, M. , Davies, J. , Theiler, J. , Gough, B. , Jungman, G. , Alken, P. , Booth, M. and Rossi, F. ( 2009). GNU Scientific Library Reference Manual. Bristol: Network Theory Limited.

Hatta, J. and Shibusawa, S. ( 2000). Scheduling algorithms for efficient gather operations in distributed heterogeneous systems. In Proc. of WPP 2000, pp. 173-180. Los Alamitos, CA: IEEE Computer Society.

Hockney, R. ( 1994). The communication challenge for MPP: Intel Paragon and Meiko CS-2. Parallel Comput. 20(3): 389-398.

Kielmann, T. , Bal, H. and Verstoep, K. ( 2000). Fast measurement of LogP parameters for message passing platforms. In Proceedings of IPDPS 2000. Springer, pp.1176-1183.

10.

Lastovetsky A. , Mkwawa I. and O’Flynn M. ( 2006). An accurate communication model of a heterogeneous cluster based on a switch-enabled ethernet network. In proceedings of ICPADS 2006, IEEE Computer Society, vol. 2, pp.15-20.

11.

Lastovetsky, A. , O’Flynn, M. and Rychkov, V. ( 2007). Optimization of collective communications in HeteroMPI . In Proceedings of EuroPVM/MPI 2007. Springer, pp. 135-143.

12.

Lastovetsky, A. , O’Flynn, M. and Rychkov, V. ( 2008). MPIBlib: benchmarking MPI communications for parallel computing on homogeneous and heterogeneous clusters. In Proceedings of EuroPVM/MPI 2008. Springer, pp. 227-238.

13.

Lastovetsky, A. and O’Flynn, M. ( 2007). A Performance Model of Many-to-One Collective Communications for Parallel Computing. In proc. of IPDPS 2007 , IEEE.

14.

Lastovetsky, A. and Rychkov, V. ( 2007). Building the communication performance model of heterogeneous clusters based on a switched network. In Proceedings of Cluster 2007. IEEE, pp. 568-575.

15.

Lastovetsky, A. and Rychkov, V. ( 2009). Accurate and efficient estimation of parameters of heterogeneous communication performance models. Int. J. High Perform. Comput. Appl. 23: 123-139.

16.

Lastovetsky, A. , Rychkov, V. and O’Flynn, M. ( 2009). Revisiting communication performance models for computational clusters. In Proceedings of IPDPS 2009. IEEE.

17.

Pjesivac-Grbovic, J. , Angskun, T. , Bosilca, G. , Fagg, G. , Gabriel, E. and Dongarra, J. ( 2007). Performance analysis of MPI collective operations. Cluster Comput. 10(2): 127-143.

18.

Thakur, R. , Rabenseifner, R. , and Gropp, W. ( 2005). Optimization of collective communication operations in MPICH, Int. J. High Performance Computing Applications, 19: 49-66.

19.

Zeileis, A. , Leisch, F. , Hornik, K. and Kleiber, C. ( 2002). Strucchange: an R package for testing for structural change in linear regression models. J. Stat. Software 7(2): 1-38.