An official website of the United States government
The suffix array is a fundamental data structure to support string analysis efficiently. It took about 26 years for the sequential suffix array construction algorithm to achieve O(n) time complexity and inplace sorting. In this paper, we develop the DLPI (D Limited Parallel Induce) algorithm, the first O( n p ) time parallel suffix array construction algorithm. The basic idea of DLPI includes two aspects: dividing the O(n) size problem into p reduced sub-problems with size O( n/p ) so we can handle them on p processors in parallel; developing an efficient parallel induce sorting method to achieve correct order for all the reduced sub-problems. The complete algorithm description is given to show the implementation method of the proposed idea. The time and space complexity analysis and proof are also given to show the correctness and efficiency of the proposed algorithm. The proposed DLPI algorithm can handle large strings with scalable performance.
more »
« less
Parallelization of Plane Sweep Based Voronoi Construction with Compiler Directives
Voronoi diagram construction is a common and fundamental problem in computational geometry and spatial computing. Numerous sequential and parallel algorithms for Voronoi diagram construction exists in literature. This paper presents a multi-threaded approach where we augment an existing sequential implementation of Fortune’s planesweep algorithm with compiler directives. The novelty of our fine-grained parallel algorithm lies in exploiting the concurrency available at each event point encountered during the algorithm. On the Intel Xeon E5 CPU, our shared-memory parallelization with OpenMP achieves around 2x speedup compared to the sequential implementation using datasets containing 2k-128k sites.
more »
« less
- Award ID(s):
- 1756000
- PAR ID:
- 10104471
- Date Published:
- Journal Name:
- 2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC)
- Page Range / eLocation ID:
- 908 to 911
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Computing strongly connected components (SCC) is among the most fundamental problems in graph analytics. Given the large size of today's real-world graphs, parallel SCC implementation is increasingly important. SCC is challenging in the parallel setting and is particularly hard on large-diameter graphs. Many existing parallel SCC implementations can be even slower than Tarjan's sequential algorithm on large-diameter graphs. To tackle this challenge, we propose an efficient parallel SCC implementation using a new parallel reachability approach. Our solution is based on a novel idea referred to as vertical granularity control (VGC). It breaks the synchronization barriers to increase parallelism and hide scheduling overhead. To use VGC in our SCC algorithm, we also design an efficient data structure called the parallel hash bag. It uses parallel dynamic resizing to avoid redundant work in maintaining frontiers (vertices processed in a round). We implement the parallel SCC algorithm by Blelloch et al. (J. ACM, 2020) using our new parallel reachability approach. We compare our implementation to the state-of-the-art systems, including GBBS, iSpan, Multi-step, and our highly optimized Tarjan's (sequential) algorithm, on 18 graphs, including social, web, k-NN, and lattice graphs. On a machine with 96 cores, our implementation is the fastest on 16 out of 18 graphs. On average (geometric means) over all graphs, our SCC is 6.0× faster than the best previous parallel code (GBBS), 12.8× faster than Tarjan's sequential algorithms, and 2.7× faster than the best existing implementation on each graph. We believe that our techniques are of independent interest. We also apply our parallel hash bag and VGC scheme to other graph problems, including connectivity and least-element lists (LE-lists). Our implementations improve the performance of the state-of-the-art parallel implementations for these two problems.more » « less
-
Nucleus decompositions have been shown to be a useful tool for finding dense subgraphs. The coreness value of a clique represents its density based on the number of other cliques it is adjacent to. One useful output of nucleus decomposition is to generate a hierarchy among dense subgraphs at different resolutions. However, existing parallel algorithms for nucleus decomposition do not generate this hierarchy, and only compute the coreness values. This paper presents a scalable parallel algorithm for hierarchy construction, with practical optimizations, such as interleaving the coreness computation with hierarchy construction and using a concurrent union-find data structure in an innovative way to generate the hierarchy. We also introduce a parallel approximation algorithm for nucleus decomposition, which achieves much lower span in theory and better performance in practice. We prove strong theoretical bounds on the work and span (parallel time) of our algorithms. On a 30-core machine with two-way hyper-threading, our parallel hierarchy construction algorithm achieves up to a 58.84x speedup over the state-of-the-art sequential hierarchy construction algorithm by Sariyuce et al. and up to a 30.96x self-relative parallel speedup. On the same machine, our approximation algorithm achieves a 3.3x speedup over our exact algorithm, while generating coreness estimates with a multiplicative error of 1.33x on average.more » « less
-
Buchin, Kevin and (Ed.)We show how a filtration of Delaunay complexes can be used to approximate the persistence diagram of the distance to a point set in ℝ^d. Whereas the full Delaunay complex can be used to compute this persistence diagram exactly, it may have size O(n^⌈d/2⌉). In contrast, our construction uses only O(n) simplices. The central idea is to connect Delaunay complexes on progressively denser subsamples by considering the flips in an incremental construction as simplices in d+1 dimensions. This approach leads to a very simple and straightforward proof of correctness in geometric terms, because the final filtration is dual to a (d+1)-dimensional Voronoi construction similar to the standard Delaunay filtration. We also, show how this complex can be efficiently constructed.more » « less
-
This paper introduces a new unified particle-based formulation for resamplings with specific patterns from original point clouds. Given the input point clouds, the proposed Lp-Gaussian kernel function is defined to simulate the inter-particle energy and force to form the isotropic/adaptive/anisotropic hexagonal and quadrilateral sampling patterns. Then, the particle-based optimization can be easily formulated and computed in parallel scheme with the high-efficiency and the fast convergence, without any control of particle population. Finally, based on the optimized particle distribution, the high-quality surface meshes are reconstructed by computing the restricted Voronoi diagram and its dual mesh with the parallel implementation. The experimental results are demonstrated by using extensive examples and evaluation criteria as well as compared with the state-of-the-art in the point cloud resampling and reconstruction.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/COMPSAC.2019.00136
