The diameter of a graph is a fundamental topological parameter that provides valuable insight needed in multiple areas of graph analytics. The traditional approach to computing the diameter is solving the all-pairs shortest-paths problem (APSP). Since APSP has a time complexity that is at least quadratic in the size of the graph, it is impractical for large graphs. As a remedy, leading algorithms use Breadth-First Search (BFS) combined with various optimizations to limit the number of BFS calls required to find the diameter. We present a new algorithm called F-Diam for quickly computing the exact diameter of large graphs. It includes new techniques such as Winnowing to greatly reduce the number of BFS calls. Our parallel CPU implementation of F-Diam is faster than the state of the art on all tested inputs, often by orders of magnitude.

Computing a maximal independent set (MIS) of a graph is an important problem in many scientific applications.Several parallel algorithms exist to perform this computation quickly.Though the state-of-the-art GPU implementation is very efficient, it cannot process graphs that do not fit in the global memory of a single GPU.We propose MG-MIS, a multi-GPU algorithm that addresses this problem.It distributes the computation across the GPUs in a compute node and uses novel techniques to minimize inter-GPU communication.Our results show that, for graphs that require more than 32 GB memory, MG-MIS outperforms the state-of-the-art single-GPU code with UVM by a geometric mean of 17.73× on a system with 4 V100 GPUs, each with 32 GB global memory.For another set of graphs that require more than 12 GB memory, MG-MIS outperforms the same single-GPU code by 22.88× on a system with 2 RTX 3080 GPUs, each with a global memory of 12 GB.On average, the size of the MIS computed by MG-MIS is 2.6% smaller than that produced by the state-of-the-art single-GPU code.

Computing maximum matchings in bipartite graphs is an important problem with applications in domains such as resource allocation, chemical analysis, and bioinformatics. The leading algorithms for this computation follow an augmenting-path-based approach. Since they involve traversing and propagating information along long paths, it is challenging to extract large amounts of parallelism from them. Moreover, the synchronization requirement is high as the threads must maintain vertex-disjoint paths. We present a novel GPU algorithm called ECL-MM that exposes more parallelism, minimizes synchronization, and reduces path overlaps. It includes a new parallel algorithm for quickly finding an initial maximal matching for starting the augmenting-path computation. Our results from an RTX-4090 GPU show that ECL-MM outperforms the fastest prior multicore CPU code by a factor of 4.5 and the fastest prior GPU code by a factor of$\mathbf{1. 6 3}$.

Summary The surge in data sizes in fluid processing applications necessitates partitioning the data into clusters and studying their representatives instead of studying each voxel data point. In addition, the dynamic nature of these data poses further challenges. Under such circumstances, it becomes essential to develop an approach that can handle the delta data with minimal updates to the underlying data structure, without processing the complete data from scratch on every update. However, this poses synchronization challenges in parallelization. In this article, we propose SLCoDD (single‐linkage clustering of dynamic data), a geometric distance based dynamic clustering and its multi‐core parallelization using OpenMP. To improve efficiency, SLCoDD exploits geometric properties of the bounding squares. We illustrate trade‐offs in various ways of performing point additions to clusters, point deletions, and their batched versions. Using a suite of large inputs, we demonstrate the effectiveness of SLCoDD. SLCoDD's fully dynamic version achieves a substantial geomean speedup of over the static parallel version and of over the dynamic sequential version.