Efficient GPU Implementations to Compute the Diameter of a Graph The FloydWarshall algorithm is a wellknown algorithm to compute the distance of all pairs of nodes of a graph. The Blocked FloydWarshall algorithm, a variant of the FloydWarshall has been proposed to accelerate the FloydWarshall algorithm by means of a GPU architecture. The previously published GPU implementations for the Blocked FloydWarshall algorithm perform many separated kernel calls for costly barrier synchronization. The main contribution of this paper is to present a more sophisticated implementation of the Blocked FloydWarshall algorithm, which performs no barrier synchronization and invokes only one kernel call. Experimental results using NVIDIA Tesla V100 show that our implementation is 1.021.09 times faster than the previously published one. Our implementation with SIMD functions also runs 1.222.02 times faster than it. Furthermore, we propose efficient GPU implementations to execute the Blocked FloydWarshall algorithm for many graphs at the same time. From the experimental results, our implementation is 1.021.46 times faster than an extended implementation of previous one.

Heterogeneous 2Phase Method for Strongly Connected Components Detection and Classification of Graphs Different sequential and parallel methods exist for decomposing a directed graph into its Strongly Connected Components (SCCs). To speed up the execution for very large graphs, Graphics Processing Units (GPUs) have been used. The realworld graphs have smallworld property with a single giant SCC and many smallsized SCCs. For such graphs, twophase methods have been used with different parallelism strategies, both on CPU and GPU in the previous research. Our research indicates that the existing methods have great variance in their performances for different types of graphs. This research classifies the graphs on the basis of which method works best for them after analyzing their properties. Such classification ensures applying the best SCC detection method in case the type of the input graph is known. We have also developed a new method that has consistently better performance for all types of graphs. This method can be used when the type of the input graph is not known or it doesnu0027t fit into the classification. In this method, the first phase is run on the GPU whereas the second phase is run on the CPU using either sequential or multithreaded routine.