An Approach to Estimate the Locality of Grained Computation Processes Organized to a Two-Dimensional Structure
DOI:
https://doi.org/10.14529/cmse210303Keywords:
parallel computing, distributed memory parallel computer, data communication reduction, fractional step methodAbstract
Implementing algorithms for distributed memory computers, one should pay attention to locality, a computational property of the algorithm that reflects the usage of fast access memory, that plays an important role in achieving high performance. For computing systems with distributed memory the local memory of each node is considered fast. Usually the parallel algorithms have better locality if it has a smaller total size of communication data and a better structure of communication operations. In this work, a new parallel algorithm for the numerical solution of a three-dimensional linear heat equation is constructed on the basis of a splitting method with weights. The algorithm is specified for distributed memory computers, combines pipeline and natural parallelism, and uses a 2D process structure. For the case of 1D process structure it was shown that usage of a pipeline parallelism instead of part of natural parallelism reduces the total size of communication operations. The proposed 2D algorithm generalizes the known 1D algorithm. The usage of two-dimensional structures allows to reduce the total volume of communication operations and to reduce idle time of a pipeline. Therefore, the 2D algorithm has better locality compared to the 1D process structure. The computational experiments on a distributed computing sytem have shown the advantage of a new parallel algorithm. Proposed method can be used to obtain and to examine parallel algorithms for other schemes of the fractional step method. Additionally, the implemented splitting scheme algorithm shows an approach to obtain asymptotic estimation of the communication volume, presented method operates with granular (the macrooperation level) parallel computing processes organized logically into a two-dimensional structure. The estimations can be used to compare communication cost for alternative versions of parallel algorithms. The approach is developed on the basis of early result that allows to obtain asymptotic estimations of the communication operations volume of computational processes organized in a one-dimensional structure.
References
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. P. 166–176.
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. RUDN Journal of Mathematics, Information Sciences and Physics. 2014. No. 2. P. 211–215. (in Russian)
Voevodin V.V., Voevodin Vl.V. Parallel Computing. St. Petersburg, BKhV-Petersburg Publ., 2002. 608 p. (in Russian)
Voevodin Vl.V., Voevodin Vad.V. The fortunate locality of supercomputers Open Systems. 2013. No. 9. P. 12–15. (in Russian)
Gergel V.P., Strongin R.G. Introduction to parallel computing for multiprocessor systems. Nizhny Novgorod, Lobachevsky State University of Nizhny Novgorod, 2003. 184 p. (in Russian)
Koleshko S.B., Popov F.D. Mechanics of Liquids and Gases. Difference schemes. Tutorial. St. Petersburg, SPbGTU Publ., 2001. 72 p. (in Russian)
Korneev B.A., Levchenko V.D. Effective solving of three-dimensional gas dynamics problems with the Runge-Kutta discontinuous Galerkin method. Comput. Math. and Math. Phys. 2016. Vol. 56. P. 460–469. DOI: 10.1134/S0965542516030118.
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. P. 1316–1326. (in Russian) DOI: 10.1134/s0965542514080077.
Likhoded N.A., Bakhanovich S.V., Zherelo A.V. Obtaining affine transformations to improve the locality of loop nests. Programming and Computer Software. 2005. Vol. 31, no. 5. P. 270–281. (in Russian) DOI: 10.1007/s11086-005-0036-2.
Likhoded N.A., Poleshchuk M.A. Tiled parallel 2D computational processes. Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series. 2018. Vol. 54, no. 4. P. 417–426. (in Russian) DOI: 10.29235/1561-2430-2018-54-4-417-426.
Likhoded N.A., Tolstsikau А.А. Locality estimation of parallel algorithm for distributed memory computers. Proceedings of the National Academy of Sciences of Belarus. 2020. Vol. 64, no. 6. P. 647–656. (in Russian) DOI: 10.29235/1561-8323-2020-64-6-647-656.
Likhoded N.A., Tolstsikau A.A. Parallel sequences of grain computations. Proceedings of the National Academy of Sciences of Belarus. 2010. Vol. 54, no. 4. P. 36–41. (in Russian)
Tolstsikau A.A., Likhoded N.A. Algorithm partition correctness while organizing grained parallel computing processes. International Congress on Computer Science: Information Systems and Technologies (CSIST'2011) (Minsk, Belarus, October 31 – November 3, 2011). Minsk, Belarusian State University, 2011. Vol. 2. P. 122–126. (in Russian)
Tolstsikau A.A., Likhoded N.A. Parallel algorithm implementing split method for a distributed memory computer. Parallel Computational Technologies (PCT 2020) (Perm, Russia, March 31 – April 2, 2020). Short papers and posters. Chelyabinsk, Publishing of the South Ural State University, 2020. P. 287–297. (in Russian)
Yanenko N.N. The method of fractional steps for solving multi-dimensional problems of mathematical physics. Novosibirsk, Science, 1967. 196 p. (in Russian)
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. Vol. 4959. Springer, 2008. P. 132–146. DOI: 10.1007/978-3-540-78791-4_9.
Buluc A., Gilberta J.R., Budak C. Solving path problems on the GPU. Parallel Computing. 2010. Vol. 36, no. 5–6. P. 241–253. DOI: 10.1016/j.parco.2009.12.002.
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. DOI: 10.1145/2948975.
Lim A.W., Lam M.S. Maximizing parallelism and minimizing synchronization with affine partitions. Parallel Computing. 1998. Vol. 24, no. 3–4. P. 445–475. DOI: 10.1016/S0167-8191(98)00021-0.
Xue J. Loop tiling for parallelism. Springer Science & Business Media, 2000. 256 p. DOI: 10.1007/978-1-4615-4337-4.
Zhao J., Cohen A. Flextended tiles: a flexible extension of overlapped tiles for polyhedral compilation. ACM Transactions on Architecture and Code Optimization. 2019. Vol. 16, no. 4, article 47. DOI: 10.1145/3369382.
Zhao J., Di P. Optimizing the Memory Hierarchy by Compositing Automatic Transformations on Computations and Data. 53rd IEEE/ACM International Symposium on Microarchitecture (MICRO 2020) (Athens, Greece, October 17–21, 2020). IEEE, 2020. P. 427–441. DOI: 10.1109/micro50266.2020.00044.
