The minimum spanning tree problem has influential importance in computer science, network analysis, and engineering. However, the sequential algorithms become unable to process the given problem as the volume of the data representing graph instances overgrowing. Instead, the highperformance computational resources pursue to simulate large-scale graph instances in a distributed manner. Generally, the standard shared or distributed memory models like OpenMP and Message Passing Interface are applied to address the parallelization. Nevertheless, as an emerging alternative, the Partitioned Global Address Space model communicates in the form of asynchronous remote procedure calls to access distributed-shared memory, positively affecting the performance using overlapping communications and locality-aware structures. The paper presents a modification of the Kruskal algorithm for MST problems based on performance and energy-efficiency evaluation relying on emerging technologies. The algorithm evaluation shows great scalability within the server up to 16 vCPU and between the physical servers coupled with a connected weighted graph using different vertices, edges, and densities.
Large scale graph analysis has tremendous importance in network science, social network
analysis, and many other fields. However, due to limitations of memory and computational
performance of a single physical server, large scale graph problems often tend to be solved on
HighPerformance Computational (HPC) clusters. The parallel programming models may address this
challenge, such as Message Passing Interface (MPI) or OpenMP for distributed memory and shared
memory systems [
Several parallel minimum spanning tree (MST) algorithms are available using traditional or emerging
parallel programming models [
In Section 2, the methodology of the experiments and algorithms are presented. Then, the experimental results are discussed in Section 3, while the conclusion is presented in Section 4.
The graph analysis, HPC communication middleware, PGAS, and HPC over cloud framework (see figure 1) are the layers of the suggested methodology for parallel implementation of MST algorithm for large graphs.
The HPC over cloud layer depends on the IaaS (Infrastructure as a Service) cloud service of
the Armenian hybrid research computing platform [
The distributed objects provided by UPCXX have been implemented for graph algorithms to store structures necessary for inter-rank communication, such as edge lists. The graph data structures are stored in processes private memory in consecutive memory locations to avoid the overhead caused by RPC. It is assumed that G=(V, E) is a connected graph with distinct edge weights and a unique MST. Besides, it is required unique id assigned to each graph vertex. A slightly modified adjacency list stores the graph data structure internally. Instead of keeping pointers to the neighbors, each vertex stores list of unique ids of the neighbors. Such id is then used to retrieve the pointer to that neighbor from the vertex store. Vertices are distributed among all the computation nodes in a vector to store vertex id as key and private pointer as a value. Such distribution provides more significant locality and better performance for memory operations because computation with each vertex is done on the vertex's node to which the vertex has an affinity.
The graph generation and MST simulations are evaluated for the experiments. The complexity of the graph generation algorithm depends on the sizes of the vertices and the percentage of graph connectivity input parameters. The suggested graph generation algorithm is divided into three phases. Instance size am32.2xmedium am16.2xmicro am32.2xlarge am16.small am32.4xlarge 16 32 16 32 16 32 16 32 16 32 1 1 2 2 4 4 8 8 16 16 First, the core of the graph is generated to ensure that the graph will remain connected at later stages. Secondly, the algorithm starts to generate edges inside the current connected component by uniformly choosing vertices. And at the final third phase, various connected components assigned to different processes or machines are connected by randomly adding edges between vertices inside different connected components and adding an edge between them.
The experiments have been carried out with a fixed number of vertices and increasing densities, enabling to benchmark both graph generation and MST algorithm for sparse and dense graphs incrementally. Both algorithms have been evaluated using VMs with different configurations (see table 1).
Figure 2 presents the behavior of the suggested graph generation algorithm delivering great runtime for the one and two vCPUs cases. However, in later cases, communication and synchronization costs are getting higher during the third phase. The high cost incurred by the third phase is caused by repeatedly accessing the memory of other processes.
Figure 3 shows the behavior of the presented MST algorithm. The algorithm delivers high scalability over 16 share memory vCPUs, which is mainly achieved by localizing computations and reducing communication only to transfer the small portion of the MST between processes of ranks and overlapping the communication. For example, running on the experimental setup described in table 1, the shared memory algorithm achieves runtime equal to 2.46 seconds for 0.5 million edges with 1 vCPU while for 16 vCPUs runtimes are equal to 0.73 seconds, which means that even for small graph instances the algorithm has scalability over multiple processes. Therefore, the speed up for 16 vCPUs is 3.36 times. At the same time, on the graph with 27.5 million edges, the runtime of the algorithm is 78.73 seconds for one vCPU, while for 16 vCPUs runtimes are nearly equal to 9.18 seconds for each process and speed up is equal to 8.6 times.
After each step of the merging process, half of the computational nodes are done with their work, and hence memory related to the MST algorithm execution is freed to save space in a global heap. The overview of the utilization of the memory and vCPU are presented in Table 2. Feature
Figure 4 presents the behavior of the suggested graph generation algorithm for VMs over two physical servers. The algorithm delivers great runtime for the one node benchmark with nearly identical two the shared memory case with execution time. However, in a two-node case, runtime increases because of communication and synchronization costs.
The algorithm achieves a great scalability over two VMs even though communication and synchronization costs in a distributed case are much higher than shared memory vCPUs. For example, running on the experimental setup described in table 1, the distributed memory algorithm achieves runtime equal to 2.72 seconds for 0.5 million edges with 1 VM while for 2 VMs runtimes are equal to 1.17 seconds, which is higher than for the shared memory case because of additional costs incurred by inter-node communication. The speed up is equal to 2.42 times. Simultaneously, on the graph with 20 million edges, the runtime of the algorithm is 91.28 seconds for 1 VM, while for 2 VMs runtimes are nearly equal to 44.53 seconds for VM and speed is equal to 2 times.
VM 1
The article presents a distributed algorithm for finding MST in a PGAS model. The suggested algorithm is a modification of Kruskal's algorithm. An in-depth evaluation of the proposed MST performance has been performed in the cloud on a connected weighted graph with different vertices, edges, and densities modeling sparse and dense graphs. The experimental results show that the algorithm has high scalability over 16 threads for MST problem in a shared memory setup. However, random graph generation time tends to increase due to communication and synchronization costs incurred by multiprocessing. During the distributed run, MST has again shown high scalability over two VMs where communication and synchronization costs are much higher compared to the shared memory case, even for small graphs instances. Still, graph generation's run-time and scalability have suffered due to irregular access patterns at the third phase of the graph generation algorithm.
It is planned to study and develop algorithms for distributed large graphs in the PGAS model
considering chunk-sizes, communication costs and network optimizations [
The paper is supported by the European Union's Horizon 2020 research infrastructures programme under grant agreement No 857645, project NI4OS Europe (National Initiatives for Open Science in Europe).