Open AccessVM BASED EVALUATION OF THE SCALABLE PARALLEL MINIMUM SPANNING TREE ALGORITHM FOR PGAS MODEL
Author(s) -
V. Bejanyan,
Hrachya Astsatryan
Publication year - 2021
Publication title -
9th international conference "distributed computing and grid technologies in science and education"
Language(s) - English
Resource type - Conference proceedings
DOI - 10.54546/mlit.2021.75.94.001
Subject(s) - computer science , scalability , asynchronous communication , locality , parallel computing , distributed memory , distributed computing , bulk synchronous parallel , graph , partitioned global address space , server , spanning tree , minimum spanning tree , message passing , shared memory , theoretical computer science , parallel algorithm , algorithm , operating system , computer network , mathematics , philosophy , linguistics , combinatorics
The minimum spanning tree problem has influential importance in computer science, networkanalysis, and engineering. However, the sequential algorithms become unable to process the givenproblem as the volume of the data representing graph instances overgrowing. Instead, the highperformance computational resources pursue to simulate large-scale graph instances in a distributedmanner. Generally, the standard shared or distributed memory models like OpenMP and MessagePassing Interface are applied to address the parallelization. Nevertheless, as an emerging alternative,the Partitioned Global Address Space model communicates in the form of asynchronous remoteprocedure calls to access distributed-shared memory, positively affecting the performance usingoverlapping communications and locality-aware structures. The paper presents a modification of theKruskal algorithm for MST problems based on performance and energy-efficiency evaluation relyingon emerging technologies. The algorithm evaluation shows great scalability within the server up to 16vCPU and between the physical servers coupled with a connected weighted graph using differentvertices, edges, and densities.