Geodesic
Distributed algorithm for distributed data lattice mapping on multidimensional multicomputer in the luna fragmented programming system
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 2, pp. 63-76 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Distributed algorithm with local interactions Patch is presented in the paper. Patch is intended for data distribution and dynamic load balancing in the LuNA fragmented programming system. LuNA system is used for creation of parallel implementations of large-scale numerical models for distributed memory systems. Execution of a fragmented program is controlled by LuNA run-time system, which uses different data and computation distribution algorithms to enable efficient use of resources and minimize total execution time of the program. Patch algorithm, developed to be used in the LuNA system, enables distribution of multidimensional data meshes on a multidimensional lattice of computational nodes of a supercomputer. The algorithm uses mapping of data to multidimensional lattice of cells (coordinates), which in their turn are mapped to computational nodes. That mapping makes it possible to account for data dependencies and preserve data locality during dynamic load balancing. Patch algorithm was compared with another LuNA data distribution algorithm Rope, fragmented realisation of a real numerical problem was used for experiments. Experiments showed that Patch algorithm provides a general reduction in total computational volume and distances, as compared to Rope algorithm.
Keywords: distributed algorithms, data distribution, dynamic load balancing, fragmented programming technology, LuNA fragmented programming system. 
@article{VYURV_2018_7_2_a4,
     author = {G. A. Schukin},
     title = {Distributed algorithm for distributed data lattice mapping on multidimensional multicomputer in the luna fragmented programming system},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {63--76},
     year = {2018},
     volume = {7},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a4/}
}
TY  - JOUR
AU  - G. A. Schukin
TI  - Distributed algorithm for distributed data lattice mapping on multidimensional multicomputer in the luna fragmented programming system
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2018
SP  - 63
EP  - 76
VL  - 7
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a4/
LA  - ru
ID  - VYURV_2018_7_2_a4
ER  - 
%0 Journal Article
%A G. A. Schukin
%T Distributed algorithm for distributed data lattice mapping on multidimensional multicomputer in the luna fragmented programming system
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2018
%P 63-76
%V 7
%N 2
%U http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a4/
%G ru
%F VYURV_2018_7_2_a4
G. A. Schukin. Distributed algorithm for distributed data lattice mapping on multidimensional multicomputer in the luna fragmented programming system. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 2, pp. 63-76. http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a4/

[1] V. E. Malyshkin, V. A. Perepelkin, G. A. Schukin, “Scalable Distributed Data Allocation in LuNA Fragmented Programming System”, J. Supercomputing, 73:2 (2017), 726-732 | DOI

[2] V. E. Malyshkin, V. A. Perepelkin, G. A. Schukin, “Distributed Algorithm of Data Allocation in the Fragmented Programming System LuNA”, PaCT 2015, 13th International Conference on Parallel Computing Technologies (August 31 – September 4, 2015, Petrozavodsk), v. 9251, Springer, LNCS, 2015, 80–85 | DOI

[3] V. E. Malyshkin, V. A. Perepelkin, “LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem”, PaCT 2011, 11th International Conference on Parallel Computing Technologies (September 19–23, 2011, Kazan), v. 6873, Springer, LNCS, 2011, 53–61 | DOI

[4] V. E. Malyshkin, V. A. Perepelkin, “Optimization Methods of Parallel Execution of Numerical Programs in the LuNA Fragmented Programming System”, J. Supercomputing, 61:1 (2012), 235–248 | DOI

[5] V. E. Malyshkin, V. A. Perepelkin, “The PIC Implementation in LuNA System of Fragmented Programming”, J. Supercomputing, 2014. Vol, 69:1 (2014), 89–97 | DOI

[6] M. A. Kraeva, V. E. Malyshkin, “Assembly Technology for Parallel Realization of Numerical Models on MIMD-Multicomputers”, J. Future Generation Computer Systems, 17:6 (2001), 755–765 | DOI

[7] A. Gonzalez-Escribano, Y. Torres, J. Fresno, D. R. Llanos, “An Extensible System for Multilevel Automatic Data Partition and Mapping”, J. IEEE Transactions on Parallel and Distributed Systems, 2014. Vol, 25:5 (2014), 1145–1154 | DOI

[8] B. L. Chamberlain, S. J. Deitz, D. Iten, S.-E. Choi, “User-Defined Distributions and Layouts in Chapel: Philosophy and Framework”, HotPar’10, 2nd USENIX conference on Hot topics in Parallelism yr 2010, USENIX Association, Berkeley, CA, USA, 12–12

[9] G. Bikshandi, J. Guo., D. Hoeflinger, G. Almasi, B. B. Fraguela, M. J. Garzaran, D. Padua, C. von Praun, “Programming for Parallelism and Locality with Hierarchically Tiled Arrays”, PPoPP ’06, 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming yr 2006, ACM New York, NY, USA, 48–57 | DOI

[10] P. Furtado, P. Baumann, “Storage of Multidimensional Arrays Based on Arbitrary Tiling”, 15th International Conference on Data Engineering, IEEE, 1999, 480–489 | DOI

[11] C. Begau, G. Sutmann, “Adaptive Dynamic Load-balancing with Irregular Domain Decomposition for Particle Simulations”, J. Computer Physics Communications, 190 (2015), 51–61 | DOI

[12] J. L. Fattebert, D. F. Richards, J. N. Glosli, “Dynamic Load Balancing Algorithm for Molecular Dynamics Based on Voronoi Cells Domain Decompositions”, J. Computer Physics Communications, 183:12 (2012), 2608–2615 | DOI

[13] Y. Deng, R. F. Peierls, C. Rivera, “An Adaptive Load Balancing Method for Parallel Molecular Dynamics Simulations”, J. of Computational Physics, 161:1 (2000), 250–263 | DOI

[14] F. Fleissner, P. Eberhard, “Parallel Load-balanced Simulation for Short-range Interaction Particle Methods with Hierarchical Particle Grouping Based on Orthogonal Recursive Bisection”, Int. J. for Numerical Methods in Engineering, 74:4 (2008), 531-553 | DOI

[15] R. Hayashi, S. Horiguchi, “Efficiency of Dynamic Load Balancing Based on Permanent Cells for Parallel Molecular Dynamics Simulation”, IPDPS 2000, 14th International Parallel and Distributed Processing Symposium, IEEE, 2000, 85–92 | DOI

[16] Rope and Patch algorithms demonstration web–page, } {\tt http://ssd.sscc.ru/en/algorithms