Computational Nanotechnology Issue №4 — 2015

A comparison of MPI and Charm++ parallel programming technologies on the minimum spanning tree problem
( Pp. 18-25)

Mazeev Artem Valerievich Semenov Alexander Sergeevich Frolov Alexander Sergeevich

Mazeev Artem Valerievich inzhener-programmist
JSC SRCECT Semenov Alexander Sergeevich kand. tehn. nauk, nachalnik sektora
JSC SRCECT Frolov Alexander Sergeevich nachalnik otdela
JSC SRCECT

Abstract:

The paper presents implementations of the GHS minimum spanning tree algorithm developed using message passing model (MPI library), message-driven model (Charm++ language), and vertex-centric model in Charm++. The optimized GHS implementations using MPI and Charm++ have approximately the same performance on 32-node cluster, the performance degradation of the implementation in Charm++ vertex-centric model is of 1-2 orders of magnitude.

How to Cite:

Mazeev A.V., Semenov A.S., Frolov A.S., (2015), A COMPARISON OF MPI AND CHARM++ PARALLEL PROGRAMMING TECHNOLOGIES ON THE MINIMUM SPANNING TREE PROBLEM. Computational Nanotechnology, 4 => 18-25.

Reference list:

Message Passing Interface Homepage. URL: http://www.mpi-forum.org (data obrashcheniya: 16.12.2015).
Kale L. Charm : A portable concurrent object oriented system based on C / L. Kale, S. Krishnan // SIGPLAN Not. - 1993. - 28(10). - P. 91-108.
Frolov A.S. Ispol zovanie Charm dlya resheniya grafovykh zadach v masshtabakh ekzaflopsnykh vychisleniy / Frolov A.S., A.S. Semenov // Sovremennye informatsionnye tekhnologii i IT-obrazovanie. - 2015. - Tom 2(№11). - S. 608-614.
McCune R. Thinking Like a Vertex: a Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing / McCune R., Weninger T., Madey G. // ACM Comput. Surv. - 2015. - 48(2).
Wesolowski L. et al. Tram: Optimizing fine-grained communication with topological routing and aggregation of messages // Parallel Processing (ICPP), 2014 43rd International Conference on. - IEEE, 2014. - C. 211-220.
Prim R. C. Shortest connection networks and some generalizations // Bell system technical journal. - 1957. - T. 36. - №. 6. - S. 1389-1401.
Kruskal J. B. On the shortest spanning subtree of a graph and the traveling salesman problem // Proceedings of the American Mathematical society. - 1956. - T. 7. - №. 1. - S. 48-50.
Boruvka O. O jist m probl mu minim lni m (about a certain minimal problem) // Praca Moravske Prirodovedecke Spolecnosti. v3. - 1926. - S. 37-58.
Gallager R. G. A distributed algorithm for minimum-weight spanning trees / Gallager R. G., Humblet P. A., Spira P. M. // ACM Transactions on Programming Languages and systems (TOPLAS). - 1983. - T. 5. - №. 1. - S. 66-77.
Awerbuch B. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems // Proceedings of the nineteenth annual ACM symposium on Theory of computing. - ACM, 1987. - S. 230-240.
Simonov A.S. i dr. Pervoe pokolenie vysokoskorostnoy kommunikatsionnoy seti Angara // Naukoemkie tekhnologii. - 2014. - T. 15, №1. - S. 21-28.
Slutskin A.I. i dr. Razrabotka mezhuzlovoy kommunikatsionnoy seti ES8430 Angara dlya perspektivnykh superkomp yuterov // Uspekhi sovremennoy radioelektroniki. - 2012. - №1. - S. 6-10.
Chakrabarti D. R-MAT: A Recursive Model for Graph Mining / Chakrabarti D., Zhan Y., Faloutsos // SDM. - 2004. - T. 4. - S. 442-446.

Keywords:

graphs, supercomputers, MPI, Charm++, MST, GHS.