Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths

Aditya Devarakonda, Grey Ballard

Abstract

In this work, we design, analyze, and optimize sequential and shared-memory parallel algorithms for partitioned local depths (PaLD). Given a set of data points and pairwise distances, PaLD is a method for identifying strength of pairwise relationships based on relative distances, enabling the identification of strong ties within dense and sparse communities even if their sizes and within-community absolute distances vary greatly. We design two algorithmic variants that perform community structure analysis through triplet comparisons of pairwise distances. We present theoretical analyses of computation and communication costs and prove that the sequential algorithms are communication optimal, up to constant factors. We introduce performance optimization strategies that yield sequential speedups of up to $29\times$ over a baseline sequential implementation and parallel speedups of up to $19.4\times$ over optimized sequential implementations using up to $32$ threads on an Intel multicore CPU.

Introduction

Identifying communities in data—groups of points that are more "related" to each other than to the rest of the set—is a fundamental task in data science. Most popular methods, like $k$-nearest neighbors (KNN) or DBSCAN, require users to tune sensitive parameters such as the value of $k$ or a distance threshold $\epsilon$. Partitioned Local Depths (PaLD) offers a parameter-free alternative that uses relative distances to calculate "cohesion" between points. This allows it to find strong ties in both very dense and very sparse clusters simultaneously.

However, PaLD is computationally expensive, with an arithmetic complexity of $O(n^3)$. This means doubling the number of data points increases the work by eightfold, making the analysis of moderately sized datasets (e.g., 20,000 points) prohibitively slow without significant optimization. This paper addresses these bottlenecks by applying high-performance computing (HPC) techniques to scale PaLD for large-scale relationship networks.

Algorithmic Design and Optimization

The researchers proposed two main algorithmic variants: the Pairwise approach and the Triplet approach. The Pairwise approach iterates over every pair of points and scans all other points to calculate local focus, offering regular data access patterns. The Triplet approach iterates over unique sets of three points, exploiting symmetry to reduce the total number of operations, though it results in more complex memory access.

The relationship between Distance (D), Local Focus (U), and Cohesion (C) matrices in the PaLD algorithm.

To achieve high performance, several low-level optimizations were implemented:

  1. Cache Blocking: Borrowing from General Matrix Multiply (GEMM) optimization, data is "blocked" to keep small chunks of the distance and cohesion matrices in the CPU's fast cache memory.
  2. Branch Avoidance: Standard PaLD involves many if-else statements. By replacing these with mathematical masks and Fused Multiply-Add (FMA) instructions, the authors avoided expensive branch mispredictions, effectively trading logic for "cheaper" math.
  3. Parallelization: Using OpenMP for shared-memory systems and adding NUMA-aware optimizations ensures that threads process data physically close to them in hardware.
The Cohesion (C) matrix structure illustrating the symmetry exploited by the Triplet algorithm.

Performance Evaluation

The algorithms were evaluated using synthetic data, Shakespeare's sonnets (semantic analysis), and large-scale collaboration networks from the SNAP repository.

The results demonstrate massive performance gains:

  • Sequential Speedup: The optimized sequential code was up to $29\times$ faster than a naive implementation.
  • Parallel Scaling: On a 32-thread Intel multicore CPU, the parallel versions achieved an additional $19.4\times$ speedup over the optimized sequential code.
  • Real-World Impact: For the ca-CondMat dataset (23,133 nodes), computation time dropped from 31 minutes to just 92 seconds.
  • Efficiency: The optimized algorithms reached nearly 28% of the theoretical peak GFLOPS of the hardware, a high mark for non-linear algebra workloads.

Conclusion

While this work significantly advances the scalability of PaLD on single-node systems, future work is needed to extend these methods to distributed-memory environments (MPI) for truly massive datasets. Additionally, while the Triplet algorithm is faster sequentially, its irregular memory dependencies present challenges for parallel scaling across multiple CPU sockets. Despite these constraints, the current optimizations make parameter-free community detection feasible for datasets with tens of thousands of points in near real-time.

Summary updated

Abstract

In this work, we design, analyze, and optimize sequential and shared-memory parallel algorithms for partitioned local depths (PaLD). Given a set of data points and pairwise distances, PaLD is a method for identifying strength of pairwise relationships based on relative distances, enabling the identification of strong ties within dense and sparse communities even if their sizes and within-community absolute distances vary greatly. We design two algorithmic variants that perform community structure analysis through triplet comparisons of pairwise distances. We present theoretical analyses of computation and communication costs and prove that the sequential algorithms are communication optimal, up to constant factors. We introduce performance optimization strategies that yield sequential speedups of up to $29\times$ over a baseline sequential implementation and parallel speedups of up to $19.4\times$ over optimized sequential implementations using up to $32$ threads on an Intel multicore CPU.
BibTeX
@misc{devarakonda2023sequential,
  author = {Aditya Devarakonda and Grey Ballard},
  title = {{Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths}},
  year = {2023},
  eprint = {2307.16652},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.16652},
}
Figure