检索结果-内蒙古大学图书馆

Efficient parallel algorithms for String Comparison 21

学校读者我要写书评

暂无评论

Efficient Parallel Algorithms for String Comparison

50th International Conference on parallel Processing (ICPP)

作者： Mishin, Nikita Berezun, Daniil Tiskin, Alexander St Petersburg State Univ St Petersburg Russia JetBrains Res Prague Czech Republic

ISBN: (纸本)9781450390682

The longest common subsequence (LCS) problem on a pair of strings is a classical problem in string algorithms. Its extension, the semilocal LCS problem, provides a more detailed comparison of the input strings, without any increase in asymptotic running time. Several semi-local LCS algorithms have been proposed previously;however, to the best of our knowledge, none have yet been implemented. In this paper, we explore a new hybrid approach to the semi-local LCS problem. We also propose a novel bit-parallel LCS algorithm. In the experimental part of the paper, we present an implementation of several existing and new parallel LCS algorithms and evaluate their performance.

关键词： string algorithms longest common subsequence semi-local string comparison parallel algorithms divide-and-conquer dynamic programming braid multiplication parallel braid multiplication bitparallel algorithms

parallel algorithms for Multifractal Analysis of River Networks 3rd

学校读者我要写书评

暂无评论

Parallel Algorithms for Multifractal Analysis of River Netwo...

3rd International Conference on Numerical Computations - Theory and algorithms (NUMTA)

作者： Primavera, Leonardo Florio, Emilia Univ Calabria Dipartimento Fis Cubo 31-C I-87036 Arcavacata Di Rende CS Italy Univ Calabria Dipartimento Matemat & Informat Cubo 30-B I-87036 Arcavacata Di Rende CS Italy

ISBN: (纸本)9783030390815

The dynamical properties of many natural phenomena can be related to their support fractal dimension. A relevant example is the connection between flood peaks produced in a river basin, as observed in flood hydrographs, and the multi-fractal spectrum of the river itself, according to the Multifractal Instantaneous Unit Hydrograph (MIUH) theory. Typically, the multifractal analysis of river networks is carried out by sampling large collections of points belonging to the river basin and analyzing the fractal dimensions and the Lipschitz-Holder exponents of singularities through numerical procedures which involve different degrees of accuracy in the assessment of such quantities through different methods (box-counting techniques, the generalized correlation integral method by Pawelzik and Schuster (1987), the fixed-mass algorithms by Badii and Politi (1985), being some relevant examples). However, the higher accuracy in the determination of the fractal dimensions requires considerably higher computational times. For this reason, we recently developed a parallel version of some of the cited multifractal methods described above by using the MPI parallel library, by reaching almost optimal speed-ups in the computations. This will supply a tool for the assessment of the fractal dimensions of river networks (as well as of several other natural phenomena whose embedding dimension is 2 or 3) on massively parallel clusters or multi-core workstations.

关键词： Multifractal dimension River networks parallel algorithms

Efficient parallel algorithms for dynamic closeness- and betweenness centrality

学校读者我要写书评

暂无评论

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2023年第17期35卷

作者： Regunta, Sai Charan Tondomker, Sai Harsh Shukla, Kshitij Kothapalli, Kishore Int Inst Informat Technol Ctr Secur Theory & Algorithm Res Hyderabad Telangana India

Finding the centrality measures of nodes in a graph is a problem of fundamental importance due to various applications from social networks, biological networks, and transportation networks. Given the large size of such graphs, it is natural to use parallelism as a recourse. Several studies show how to compute the various centrality measures of nodes in a graph on parallel architectures, including multi-core systems and GPUs. However, as these graphs evolve and change, it is pertinent to study how to update the centrality measures on changes to the underlying graph. In this article, we show novel parallel algorithms for updating the betweenness- and closeness-centrality values of nodes in a dynamic graph. Our algorithms process a batch of updates in parallel by extending the approach of handling a single update for betweenness- and closeness-centrality. For the latter, we also introduce techniques based on traversals of the block-cut tree of a graph. Besides, our algorithms incorporate mechanisms to exploit the structural properties of graphs for enhanced performance. We implement our algorithms on two parallel architectures: an Intel 24-core CPU and an Nvidia Tesla V100 GPU. To the best of our knowledge, we are the first to show GPU algorithms for the above two problems. In addition, we conduct detailed experiments to study the impact of various parameters associated with our algorithms and their implementation. Our results on a collection of real-world graphs indicate that our algorithms achieve a significant speedup over corresponding state-of-the-art algorithms.

关键词： batch updates betweenness-centrality closeness-centrality CPU dynamic graph algorithms GPU parallel algorithms

Fast parallel algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Blanuša, Jovan Atasu, Kubilay Ienne, Paolo Ecole Polytechnique Fédérale de Lausanne School of Computer and Communication Sciences Switzerland IBM Research Europe - Zurich Zurich Switzerland Ecole Polytechnique Fédérale de Lausanne School of Computer and Communication Sciences LausanneCH-1015 Switzerland

Cycles are one of the fundamental subgraph patterns and being able to enumerate them in graphs enables important applications in a wide variety of fields, including finance, biology, chemistry, and network science. However, to enable cycle enumeration in real-world applications, efficient parallel algorithms are required. In this work, we propose scalable parallelisation of state-of-the-art sequential algorithms for enumerating simple, temporal, and hop-constrained cycles. First, we focus on the simple cycle enumeration problem and parallelise the algorithms by Johnson and by Read and Tarjan in a fine-grained manner. We theoretically show that our resulting fine-grained parallel algorithms are scalable, with the fine-grained parallel Read-Tarjan algorithm being strongly scalable. In contrast, we show that straightforward coarse-grained parallel versions of these simple cycle enumeration algorithms that exploit edge- or vertex-level parallelism are not scalable. Next, we adapt our fine-grained approach to enable the enumeration of cycles under time-window, temporal, and hop constraints. Our evaluation on a cluster with 256 CPU cores that can execute up to 1024 simultaneous threads demonstrates a near-linear scalability of our fine-grained parallel algorithms when enumerating cycles under the aforementioned constraints. On the same cluster, our fine-grained parallel algorithms achieve, on average, one order of magnitude speedup compared to the respective coarse-grained parallel versions of the state-of-the-art algorithms for cycle enumeration. The performance gap between the fine-grained and the coarse-grained parallel algorithms increases as we use more CPU cores. Copyright © 2023, The Authors. All rights reserved.

关键词： parallel algorithms

On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Schmidt, Jonas Schwentick, Thomas Todtenhoefer, Jennifer TU Dortmund University Germany

Previous work on Dynamic Complexity has established that there exist dynamic constant-time parallel algorithms for regular tree languages and context-free languages under label or symbol changes. However, these algorithms were not developed with the goal to minimise work (or, equivalently, the number of processors). In fact, their inspection yields the work bounds O(n2) and O(n7) per change operation, respectively. In this paper, dynamic algorithms for regular tree languages are proposed that generalise the previous algorithms in that they allow unbounded node rank and leaf insertions, while improving the work bound from O(n2) to O(nϵ), for arbitrary ϵ > 0. For context-free languages, algorithms with better work bounds (compared with O(n7)) for restricted classes are proposed: for every ϵ > 0 there are such algorithms for deterministic context-free languages with work bound O(n3+ϵ) and for visibly pushdown languages with work bound O(n2+ϵ). © 2023, CC BY.

关键词： parallel algorithms

Sequential and Shared-Memory parallel algorithms for Partitioned Local Depths

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Devarakonda, Aditya Ballard, Grey Department of Computer Science Wake Forest University United States

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× over a baseline sequential implementation and parallel speedups of up to 19.4× over optimized sequential implementations using up to 32 threads on an Intel multicore *** Codes 68W10 © 2023, CC BY.

关键词： parallel algorithms

Data-parallel algorithms for String Diagrams

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Wilson, Paul Zanasi, Fabio Independent University College London United Kingdom University of Bologna Italy

We give parallel algorithms for string diagrams represented as structured cospans of ACSets. Specifically, we give linear (sequential) and logarithmic (parallel) time algorithms for composition, tensor product, construction of diagrams from arbitrary Σ-terms, and application of functors to diagrams. Our datastructure can represent morphisms of both the free symmetric monoidal category over an arbitrary signature as well as those with a chosen Special Frobenius structure. We show how this additional (hypergraph) structure can be used to map diagrams to diagrams of optics. This leads to a case study in which we define an algorithm for efficiently computing symbolic representations of gradient-based learners based on reverse derivatives. The work we present here is intended to be useful as a general purpose datastructure. Implementation requires only integer arrays and well-known algorithms, and is data-parallel by constuction. We therefore expect it to be applicable to a wide variety of settings, including embedded and parallel hardware and low-level languages. © 2023, CC BY-NC-SA.

关键词： parallel algorithms

High-Performance and Flexible parallel algorithms for Semisort and Related Problems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Dong, Xiaojun Wu, Yunshu Wang, Zhongqi Dhulipala, Laxman Gu, Yan Sun, Yihan University of California Riverside United States University of Maryland College Park United States

Semisort is a fundamental algorithmic primitive widely used in the design and analysis of efficient parallel algorithms. It takes input as an array of records and a function extracting a key per record, and reorders them so that records with equal keys are contiguous. Since many applications only require collecting equal values, but not fully sorting the input, semisort is broadly applicable, e.g., in string algorithms, graph analytics, and geometry processing, among many other domains. However, despite dozens of recent papers that use semisort in their theoretical analysis and the existence of an asymptotically optimal parallel semisort algorithm, most implementations of these parallel algorithms choose to implement semisort by using comparison or integer sorting in practice, due to potential performance issues in existing semisort implementations. In this paper, we revisit the semisort problem, with the goal of achieving a high-performance parallel semisort implementation with a flexible interface. Our approach can easily extend to two related problems, histogram and collect-reduce. Our algorithms achieve strong speedups in practice, and importantly, outperform state-of-the-art parallel sorting and semisorting methods for almost all settings we tested, with varying input sizes, distribution, and key types. We also test two important applications with real-world data, and show that our algorithms improve the performance over existing approaches. We believe that many other parallel algorithm implementations can be accelerated using our results. © 2023, CC BY.

关键词： parallel algorithms

Practical parallel algorithms for Near-Optimal Densest Subgraphs on Massive Graphs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Sukprasert, Pattara Liu, Quanquan C. Dhulipala, Laxman Shun, Julian Databricks San FranciscoCA United States Simons Institute at UC Berkeley BerkeleyCA United States University of Maryland College ParkMD United States MIT CSAIL CambridgeMA United States

The densest subgraph problem has received significant attention, both in theory and in practice, due to its applications in problems such as community detection, social network analysis, and spam detection. Due to the high cost of obtaining exact solutions, much attention has focused on designing approximate densest subgraph algorithms. However, existing approaches are not able to scale to massive graphs with billions of edges. In this paper, we introduce a new framework that combines approximate densest subgraph algorithms with a pruning optimization. We design new parallel variants of the state-of-the-art sequential Greedy++ algorithm, and plug it into our framework in conjunction with a parallel pruning technique based on k-core decomposition to obtain parallel (1+Ε)-approximate densest subgraph algorithms. On a single thread, our algorithms achieve 2.6-34× speedup over Greedy++, and obtain up to 22.37× self-relative parallel speedup on a 30-core machine with two-way hyper-threading. Compared with the state-of-the-art parallel algorithm by Harb et al. [NeurIPS'22], we achieve up to a 114× speedup on the same machine. Finally, against the recent sequential algorithm of Xu et al. [PACMMOD'23], we achieve up to a 25.9× speedup. The scalability of our algorithms enables us to obtain near-optimal density statistics on the hyperlink2012 (with roughly 113 billion edges) and clueweb (with roughly 37 billion edges) graphs for the first time in the literature. Copyright © 2023, The Authors. All rights reserved.

关键词： parallel algorithms