Locality estimation of parallel algorithm for distributed memory computers
https://doi.org/10.29235/1561-8323-2020-64-6-647-656
Abstract
Locality is an algorithm characteristic describing a usage level of fast access memory. For example, in case of distributed memory computers we focus on memory of each computational node. To achieve the high performance of algorithm implementation one should choose the best possible locality option. Studying the parallel algorithm locality is to estimate the number and volume of data communications. In this work, we formulate and prove the statements for computers with distributed memory that allow us to estimate the asymptotic volume of data communication operations. These estimation results are useful while comparing alternative versions of parallel algorithms during data communication cost analysis.
About the Authors
N. A. Likhoded
Belarusian State University
Belarus
Belarus
Likhoded Nikolai A. – D. Sc. (Physics and Mathematics), Professor.
4, Nezavisimosti Ave., 220030, Minsk
A. A. Tolstsikau
Belarusian State University
Belarus
Belarus
Tolstsikau Aliaksei A. – Senior lecturer
4, Nezavisimosti Ave., 220030, Minsk
References
1. Voevodin Vl. V., Voevodin Vad. V. The fortunate locality of supercomputers. Otkrytye sistemy = Open Systems, 2013, no. 9, pp. 12–15 (in Russian).
2. Xue J., Cai W. Time-minimal tiling when rise is larger than zero. Parallel Computing, 2002, vol. 28, no. 6, pp. 915–939. https://doi.org/10.1016/s0167-8191(02)00098-4
3. Dathathri R., Mullapudi R. T., Bondhugula U. Compiling affine loop nests for a dynamic scheduling runtime on shared and distributed memory. ACM Transactions on Parallel Computing (TOPC), 2016, vol. 3, no. 2, p. 1–28. https://doi.org/10.1145/2948975
4. Voevodin V. V., Voevodin Vl. V. Parallel Computing. Saint Petersburg, 2002. 608 p. (in Russian).
5. Adutskevich E. V., Likhoded N. A. A consistent generation of pipeline parallelism and distribution of operations and data among processors. Programming and Computer Software, 2006, vol. 32, no. 3, pp. 166–176. https://doi.org/10.1134/s0361768806030078
6. Bondhugula U., Baskaran M., Krishnamoorthy S., Ramanujam J., Rountev A., Sadayappan P. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. Lecture notes in computer science, 2008, no. 4959, pp. 132–146. https://doi.org/10.1007/978-3-540-78791-4_9
7. Likhoded N. A. Sufficient conditions for the determination and use of data in the same granular parallel computation process. Computational Mathematics and Mathematical Physics, 2014, vol. 54, no. 8, pp. 1316–1326. https://doi.org/10.1134/s0965542514080077
8. Likhoded N. A., Paliashchuk M. A. Method of ranking tiles size parameters of parallel algorithm. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2015, vol. 59, no. 4, pp. 25– 33 (in Russian).
9. Gergel V. P., Strongin R. G. Introduction to parallel computing for multiprocessor systems. Nizhny Novgorod, 2003. 184 p. (in Russian).
10. Likhoded N. A., Tolstikov A. A. Parallel sequences of grain computations. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2010, vol. 54, no. 4, pp. 36–41 (in Russian).
11. Bakhanovich S. V., Likhoded N. A., Mandrik P. A. Improvement of locality of parallel algorithms of the numerical solutions of the two-dimensional quasilinear parabolic equation. Discrete and Continuous Models and Applied Computational Science, 2014, no. 2, pp. 211–215 (in Russian).
Review
Views: 618
Email this article 