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

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Ghaffari, Mohsen Grunau, Christoph Qu, Jiahao MIT Cambridge MA 02139 USA Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450395458

We present the first parallel depth-first search algorithm for undirected graphs that has near-linear work and sublinear depth. Concretely, in any n-node m-edge undirected graph, our algorithm computes a DFS in O(root n) depth and using (O) over tilde (m + n) work. All prior work either required Omega(n) depth, and thus were essentially sequential, or needed a high poly(n) work and thus were far from being work-efficient.

关键词： parallel algorithms depth-first search work-efficient

来源：评论

学校读者我要写书评

暂无评论

An Efficient parallel Sketch-based Algorithm for Mapping Long Reads to Contigs

An Efficient Parallel Sketch-based Algorithm for Mapping Lon...

引用

37th IEEE International parallel and Distributed Processing Symposium (IPDPS)

作者： Rahman, Tazin Bhowmik, Oieswarya Kalyanaraman, Ananth Washington State Univ Pullman WA 99164 USA

ISBN: (纸本)9798350311990

Long read technologies are continuing to evolve at a rapid pace, with the latest of the high fidelity technologies delivering reads over 10Kbp with high accuracy (99.9%). However, there also exist partially constructed assemblies using short read data. Hybrid assembly workflows provide a way to combine the information in both these data sources and generate highly improved and near complete assemblies and genomic scaffolds. In this paper, we address the problem of mapping long reads to contigs (representing prior constructed partial assemblies). This is a many-to-many comparison application. However, brute force comparisons of all pairs is not practical. Therefore, in this paper, we present a parallel, alignment-free sketching-based algorithm that efficiently maps long reads to contigs. More specifically, our approach uses a minimizer-based Jaccard estimator (or JEM), a variant of the classical MinHashing technique, as its sketch. Experimental evaluation shows that our parallel algorithm is highly effective in producing a high quality mapping while improving significantly the time to solution compared to state-of-the-art mapping tools. For instance, for a large genome Betta splendens (approximate to 350Mbp genome) with 429K HiFi long reads and 98K contigs, our JEM approach produces a mapping with 99.31% precision and 96.18% recall, while yielding 7.13x speedup over a state-of-the-art mapper (Mashmap).

关键词： hybrid assembly long read mapping sketching MinHashing parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Invited Paper: On the Cost-Optimal parallel Solution of the Majority Problem

Invited Paper: On the Cost-Optimal Parallel Solution of the ...

引用

37th IEEE International parallel and Distributed Processing Symposium (IPDPS)

作者： Wu, Jie Temple Univ Ctr Networked Comp Philadelphia PA 19122 USA

ISBN: (纸本)9798350311990

The majority problem can be stated as follows: there is a collection of n bank cards that belong to different bank accounts. The only way to "read" these cards is through one or more two-input "equivalence testers". Each tester accepts two cards and outputs "yes" if two input cards correspond to the same bank account or "no" if they do not. The objective of the majority problem is to design a solution that uses the minimum number of tests to determine if more than n/2 cards belong to the same bank account and then find these cards. We first review two sequential solutions, including the Boyer-Moore optimal linear solution (i.e., with a time complexity of O(n)). Then, we introduce an optimal elimination solution together with a special structure to support a cost-optimal parallel solution that solves the problem in O(log n) using O(n/ log n) processors (i.e., testers). That is, this solution matches the optimal sequential solution with O(n) operations.

关键词： Cost-optimal solutions data structure parallel algorithms speedup

来源：评论

学校读者我要写书评

暂无评论

Per Segment Plane Sweep Line Segment Intersection on the GPU

引用

ACM TRANSACTIONS ON SPATIAL algorithms AND SYSTEMS 2025年第2期11卷

作者： Frye, Roger McKenney, Mark Blackburn Coll Comp Sci Carlinville IL 62626 USA Southern Illinois Univ Edwardsville Comp Sci Dept Edwardsville IL USA

Polygon overlay operations are used for various purposes, such as GIS searches and queries, VLSI, and basic geometric operations of intersection, union, and difference. There have been recent research articles presenting algorithms using the GPU to perform line segment intersection for geometric operations. We present two parallel algorithms implemented on the GPU that focus on the active list portion of the traditional serial plane sweep algorithm. The first algorithm uses a single block of threads to simulate the active list data structure in hardware;this algorithm is slow due to GPU thread block size limitations and synchronization points but demonstrates favorable time complexity. The second algorithm uses dynamic parallelism to remove synchronization and scales to utilize available GPU hardware (single GPU). We perform experiments on both synthetic and real-world datasets. The presented results show improvement in execution time with respect to recent algorithms and low memory usage compared to recent algorithms. We achieve speedups of up to 38.8 over the serial sweep line algorithm on real-world data.

关键词： Computational geometry GPU processing parallel algorithms plane sweep algorithm polygon overlay

来源：评论

学校读者我要写书评

暂无评论

parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances 2023

Parallel Breadth-First Search and Exact Shortest Paths and S...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Rozhon, Vaclav Haeupler, Bernhard Martinsson, Anders Grunau, Christoph Zuzic, Goran Swiss Fed Inst Technol Zurich Switzerland CMU Pittsburgh PA 15213 USA

ISBN: (纸本)9781450399135

This paper introduces stronger notions for approximate single-source shortest-path distances and gives simple reductions to compute them from weaker standard notions of approximate distances. Strongly-approximate distances isolate, capture, and address the well-known barriers for using approximate distances algorithmically and their reductions directly address these barriers in a clean and modular manner. The reductions are model-independent and require only log(O(1)) black-box approximate distance computations. They apply equally to parallel, distributed, and semi-streaming settings. Strongly (1 +epsilon)-approximate distances are equivalent to exact distances in a (1 + epsilon)-perturbed graph and approximately satisfy the subtractive triangle inequality. In directed graphs, this is sufficient to reduce even exact distance computation to arbitrary (1 + epsilon)-approximate ones. Overall, this paper simplifies, unifies, and cleans up problemspecific ad-hoc solutions developed in many prior works, e.g., for ball-growing routines in undirected graphs and for computing exact distances in directed graphs. Several algorithmic results for parallel and distributed algorithms - some known, some new - are directly implied by our reductions. Applications of particular interest include the first work-efficient sublinear-depth parallel algorithm for breadth-first search and computing exact single-source shortest paths - both major open problems in parallel computing. Given a source vertex in a directed graph with polynomiallybounded nonnegative integer lengths the algorithm computes an exact shortest path tree in.. log(O(1)) work and n(1/2+o(1)) depth. Previously, no parallel algorithm improving the trivial linear depths of Dijkstra's algorithm without significantly increasing the work was known, even for the case of undirected and unit-length graphs, i.e., for computing a breadth-first-search tree. This result was independently obtained by Fineman and Cao.

关键词： parallel algorithms distributed algorithms bfs shortest path exact distances approximate distances

来源：评论

学校读者我要写书评

暂无评论

Optimal Round and Sample-Size Complexity for Partitioning in parallel Sorting 23

Optimal Round and Sample-Size Complexity for Partitioning in...

引用

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Yang, Wentao Harsh, Vipul Solomonik, Edgar Univ Illinois Dept Comp Sci Urbana IL 61801 USA

ISBN: (纸本)9781450395458

State-of-the-art parallel sorting algorithms for distributed-memory architectures are based on computing a balanced partitioning via sampling and histogramming. By finding samples that partition the sorted keys into evenly-sized chunks, these algorithms minimize the number of communication rounds required. Histogramming (computing positions of samples) guides sampling, enabling a decrease in the overall number of samples collected. We derive lower and upper bounds on the number of sampling/histogramming rounds required to compute a balanced partitioning. We improve on prior results to demonstrate that when using p processors, O(log* p) rounds with O(p/log* p) samples per round suffice. We match that with a lower bound that shows that any algorithm with O(p) samples per round requires at least Omega(log* p) rounds. Additionally, we prove the Omega(p log p) samples lower bound for one round, thus proving that existing one round algorithms: sample sort, AMS sort [2] and HSS [16] have optimal sample size complexity. To derive the lower bound, we propose a hard randomized input distribution and apply classical results from the distribution theory of runs.

关键词： parallel algorithms parallel sorting communication cost communication lower bounds

来源：评论

学校读者我要写书评

暂无评论

A Simple and Efficient parallel Laplacian Solver 23

A Simple and Efficient Parallel Laplacian Solver

引用

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Sachdeva, Sushant Zhao, Yibin Univ Toronto Toronto ON Canada

ISBN: (纸本)9781450395458

A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linear systems in nearly linear time, several algorithms have been designed for the task. Yet, the work of Kyng and Sachdeva (2016) remains the simplest and most practical sequential solver. They presented a solver purely based on random sampling and without graph-theoretic constructions such as low-stretch trees and sparsifiers. In this work, we extend the result of Kyng and Sachdeva to a simple parallel Laplacian solver with O(m log(3) n log log n) or O((m + n log(5) n) log n log log n) work and O(log(2) n log log n) depth using the ideas of block Cholesky factorization from Kyng et al. (2016). Compared to the best known parallel Laplacian solvers that achieve polylogarithmic depth due to Lee et al. (2015), our solver achieves both better depth and, for dense graphs, better work.

关键词： Laplacian Linear Systems parallel algorithms Linear System Solvers

来源：评论

学校读者我要写书评

暂无评论

Quadratic Speedups in parallel Sampling from Determinantal Distributions 23

Quadratic Speedups in Parallel Sampling from Determinantal D...

引用

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Anari, Nima Burgess, Callum Tian, Kevin Thuy-Duong Vuong Stanford Univ Stanford CA 94305 USA Microsoft Res Redmond WA USA

ISBN: (纸本)9781450395458

We study the problem of parallelizing sampling from distributions related to determinants: symmetric, nonsymmetric, and partitionconstrained determinantal point processes, as well as planar perfect matchings. For these distributions, the partition function, a.k.a. the count, can be obtained via matrix determinants, a highly parallelizable computation;Csanky proved it is in NC. However, parallel counting does not automatically translate to parallel sampling, as classic reductions between the two are inherently sequential. We show that a nearly quadratic parallel speedup over sequential sampling can be achieved for all the aforementioned distributions. If the distribution is supported on subsets of size k of a ground set, we show how to approximately produce a sample in (O) over tilde (k(1/2+c)) time with polynomially many processors for any constant c > 0. In the two special cases of symmetric determinantal point processes and planar perfect matchings, our bound improves to (O) over tilde(root k) and we show how to sample exactly in these cases. As our main technical contribution, we fully characterize the limits of batching for the steps of sampling-to-counting reductions. We observe that only O(1) steps can be batched together if we strive for exact sampling, even in the case of nonsymmetric determinantal point processes. However, we show that for approximate sampling, (O) over tilde (k(1/2-c)) steps can be batched together, for any entropically independent distribution, which includes all mentioned classes of determinantal point processes. Entropic independence and related notions have been the source of breakthroughs in Markov chain analysis in recent years, so we expect our framework to prove useful for distributions beyond those studied in this work.

关键词： sampling counting rejection sampling parallel algorithms determinantal point process planar perfect matchings

来源：评论

学校读者我要写书评

暂无评论

Provably-Efficient and Internally-Deterministic parallel Union-Find 23

Provably-Efficient and Internally-Deterministic Parallel Uni...

引用

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Fedorov, Alexander Hashemi, Diba Nadiradze, Giorgi Alistarh, Dan IST Austria Klosterneuburg Austria

ISBN: (纸本)9781450395458

Determining the degree of inherent parallelism in classical sequential algorithms and leveraging it for fast parallel execution is a key topic in parallel computing, and detailed analyses are known for a wide range of classical algorithms. In this paper, we perform the first such analysis for the fundamental Union-Find problem, in which we are given a graph as a sequence of edges, and must maintain its connectivity structure under edge additions. We prove that classic sequential algorithms for this problem are well-parallelizable under reasonable assumptions, addressing a conjecture by [Blelloch, 2017]. More precisely, we show via a new potential argument that, under uniform random edge ordering, parallel union-find operations are unlikely to interfere: T concurrent threads processing the graph in parallel will encounter memory contention O(T-2 center dot log vertical bar V vertical bar center dot log vertical bar E vertical bar) times in expectation, where vertical bar E vertical bar and vertical bar V vertical bar are the number of edges and nodes in the graph, respectively. We leverage this result to design a new parallel Union-Find algorithm that is both internally deterministic, i.e., its results are guaranteed to match those of a sequential execution, but also work-efficient and scalable, as long as the number of threads T is O(vertical bar E vertical bar(1/3-epsilon)), for an arbitrarily small constant epsilon > 0, which holds for most large real-world graphs. We present lower bounds which show that our analysis is close to optimal, and experimental results suggesting that the performance cost of internal determinism is limited.

关键词： union-find parallel algorithms graph algorithms deterministic parallelism

来源：评论

学校读者我要写书评

暂无评论

Decalf: A Directed, Effectful Cost-Aware Logical Framework

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2024年第POPL期8卷 273-301页

作者： Grodin, Harrison Niu, Yue Sterling, Jonathan Harper, Robert Carnegie Mellon Univ Dept Comp Sci 5000 Forbes Ave Pittsburgh PA 15213 USA Univ Cambridge Dept Comp Sci & Technol 15 JJ Thomson Ave Cambridge CB3 0FD England

We present decalf, a directed, effectful cost-aware logical framework for studying quantitative aspects of functional programs with effects. Like calf, the language is based on a formal phase distinction between the extension and the intension of a program, its pure behavior as distinct from its cost measured by an effectful step-counting primitive. The type theory ensures that the behavior is unaffected by the cost accounting. Unlike calf, the present language takes account of effects, such as probabilistic choice and mutable state. This extension requires a reformulation of calf's approach to cost accounting: rather than rely on a "separable" notion of cost, here a cost bound is simply another program. To make this formal, we equip every type with an intrinsic preorder, relaxing the precise cost accounting intrinsic to a program to a looser but nevertheless informative estimate. For example, the cost bound of a probabilistic program is itself a probabilistic program that specifies the distribution of costs. This approach serves as a streamlined alternative to the standard method of isolating a cost recurrence and readily extends to higher-order, effectful programs. The development proceeds by first introducing the decalf type system, which is based on an intrinsic ordering among terms that restricts in the extensional phase to extensional equality, but in the intensional phase reflects an approximation of the cost of a program of interest. This formulation is then applied to a number of illustrative examples, including pure and effectful sorting algorithms, simple probabilistic programs, and higher-order functions. Finally, we justify decalf via a model in the topos of augmented simplicial sets.

关键词： algorithm analysis cost models phase distinction noninterference intensional property behavioral verification equational reasoning modal type theory mechanized proof proof assistants recurrence relations amortized analysis parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：