Распределенный алгоритм отображения распределенных многомерных данных на многомерный мультикомпьютер в системе фрагментированного программирования Luna
Автор: Щукин Георгий Анатольевич
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 2 т.7, 2018 года.
Бесплатный доступ
В статье рассматривается распределенный алгоритм с локальными взаимодействиями Patch, предназначенный для управления распределением данных и динамической балансировки нагрузки в системе фрагментированного программирования LuNA. Система LuNA используется для упрощения создания параллельных реализаций крупномасштабных численных моделей для распределенных вычислительных систем. Фрагментированная программа в системе LuNA выполняется под управлением исполнительной системы, которая использует различные алгоритмы распределения данных и вычислений для обеспечения эффективного (в плане времени исполнения и потребления ресурсов) исполнения программы. Разработанный для использования в системе LuNA распределенный алгоритм Patch предназначен для случая распределения многомерных сеток данных на многомерной решетке вычислительных узлов. Алгоритм использует отображение данных на многомерную решетку ячеек (координат), которые затем распределяются между вычислительными узлами мультикомпьютера. Такое отображение позволяет алгоритму учитывать зависимости между данными и сохранять локальность данных при динамической балансировке нагрузки. Тестирование алгоритма Patch на фрагментированной реализации реальной вычислительной задачи показало его преимущество над использовавшимся ранее в системе LuNA алгоритме Rope, в виде уменьшения суммарного объема и дальности коммуникаций между вычислительными узлами в ходе исполнения программы.
Распределенные алгоритмы, распределение данных, динамическая балансировка нагрузки, технология фрагментированного программирования, система фрагментированного программирования luna
Короткий адрес: https://sciup.org/147160645
IDR: 147160645 | DOI: 10.14529/cmse180205
Список литературы Распределенный алгоритм отображения распределенных многомерных данных на многомерный мультикомпьютер в системе фрагментированного программирования Luna
- Malyshkin V.E., Perepelkin V.A., Schukin G.A. Scalable Distributed Data Allocation in LuNA Fragmented Programming System//J. Supercomputing, 2017. Vol. 73, No. 2. P. 726-732 DOI: 10.1007/s11227-016-1781-0
- Malyshkin V.E., Perepelkin V.A., Schukin G.A. 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, Russia. Springer, LNCS, 2015. Vol. 9251. P. 80-85 DOI: 10.1007/978-3-319-21909-7_8
- Malyshkin V.E., Perepelkin V.A. 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, Russia. Springer, LNCS, 2011. Vol. 6873. P. 53-61 DOI: 10.1007/978-3-642-23178-0_5
- Malyshkin V.E., Perepelkin V.A. Optimization Methods of Parallel Execution of Numerical Programs in the LuNA Fragmented Programming System//J. Supercomputing, 2012. Vol. 61, No. 1. P. 235-248 DOI: 10.1007/s11227-011-0649-6
- Malyshkin V.E., Perepelkin V.A. The PIC Implementation in LuNA System of Fragmented Programming//J. Supercomputing, 2014. Vol. 69, No. 1. P. 89-97 DOI: 10.1007/s11227-014-1216-8
- Kraeva M.A., Malyshkin V.E. Assembly Technology for Parallel Realization of Numerical Models on MIMD-Multicomputers//J. Future Generation Computer Systems, 2001. Vol. 17, No. 6. P. 755-765 DOI: 10.1016/S0167-739X(00)00058-3
- Gonzalez-Escribano A., Torres Y., Fresno J., Llanos D.R. An Extensible System for Multilevel Automatic Data Partition and Mapping//J. IEEE Transactions on Parallel and Distributed Systems, 2014. Vol. 25, No. 5. P. 1145-1154 DOI: 10.1109/TPDS.2013.83
- Chamberlain B.L., Deitz S.J., Iten D., Choi S.-E. User-Defined Distributions and Layouts in Chapel: Philosophy and Framework//HotPar’10, 2nd USENIX conference on Hot topics in Parallelism. USENIX Association, Berkeley, CA, USA, 2010. P. 12-12.
- Bikshandi G., Guo J., Hoeflinger D., Almasi G., Fraguela B.B., Garzar´an M.J., Padua D., von Praun C. Programming for Parallelism and Locality with Hierarchically Tiled Arrays//PPoPP ’06, 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM New York, NY, USA, 2006. P. 48-57 DOI: 10.1145/1122971.1122981
- Furtado P., Baumann P. Storage of Multidimensional Arrays Based on Arbitrary Tiling//15th International Conference on Data Engineering. IEEE, 1999. P. 480-489 DOI: 10.1109/ICDE.1999.754964
- Begau C., Sutmann G. Adaptive Dynamic Load-balancing with Irregular Domain Decomposition for Particle Simulations//J. Computer Physics Communications, 2015. Vol. 190. P. 51-61 DOI: 10.1016/j.cpc.2015.01.009
- Fattebert J.-L., Richards D.F., Glosli J.N. Dynamic Load Balancing Algorithm for Molecular Dynamics Based on Voronoi Cells Domain Decompositions//J. Computer Physics Communications, 2012. Vol. 183, No. 12. P. 2608-2615 DOI: 10.1016/j.cpc.2012.07.013
- Deng Y., Peierls R.F., Rivera C. An Adaptive Load Balancing Method for Parallel Molecular Dynamics Simulations//J. of Computational Physics, 2000. Vol. 161, No. 1. P. 250-263 DOI: 10.1006/jcph.2000.6501
- Fleissner F., Eberhard P. 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, 2008. Vol. 74, No. 4. P. 531-553 DOI: 10.1002/nme.2184
- Hayashi R., Horiguchi S.: 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. P. 85-92 DOI: 10.1109/IPDPS.2000.845968
- Веб-страница с демонстрацией работы алгоритмов Rope и Patch. URL: http://ssd.sscc.ru/en/algorithms (дата обращения: 01.02.2018)
