Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths
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.
Code (0)
등록된 구현이 없습니다.
Tasks
CPUTripletSimilar Papers 제목 키워드 기반
Scaling the Wild: Decentralizing Hogwild!-style Shared-memory SGD
Powered by the simplicity of lock-free asynchrony, Hogwilld! is a go-to approach to parallelize SGD over a shared-memory setting. Despite its popularity and concomitant extensions, such as PASSM+ wherein concurrent proce…
Blockingimage-classificationImage ClassificationHardware-conscious Hash-Joins on GPUs
Traditionally, analytical database engines have used task parallelism provided by modern multi-socket multicore CPUs for scaling query execution. Over the past few years, GPUs have started gaining traction as accelerator…
CPUGPUPipeMare: Asynchronous Pipeline Parallel DNN Training
Pipeline parallelism (PP) when training neural networks enables larger models to be partitioned spatially, leading to both lower network communication and overall higher hardware utilization. Unfortunately, to preserve t…
On Model Parallelization and Scheduling Strategies for Distributed Machine Learning
Distributed machine learning has typically been approached from a data parallel perspective, where big data are partitioned to multiple workers and an algorithm is executed concurrently over different data subsets under …
BIG-bench Machine LearningSchedulingA Partitioned Sparse Variational Gaussian Process for Fast, Distributed Spatial Modeling
The next generation of Department of Energy supercomputers will be capable of exascale computation. For these machines, far more computation will be possible than that which can be saved to disk. As a result, users will …