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

29th acm SIGPLAN annual symposium on Principles and Practice of parallel Programming (PPoPP)

作者： Dong, Xiaojun Dhulipala, Laxman Gu, Yan Sun, Yihan UC Riverside Riverside CA 92521 USA Univ Maryland Baltimore MD USA

ISBN: (纸本)9798400704352

Integer sorting is a fundamental problem in computer science. This paper studies parallel integer sort both in theory and in practice. In theory, we show tighter bounds for a class of existing practical integer sort algorithms, which provides a solid theoretical foundation for their widespread usage in practice and strong performance. In practice, we design a new integer sorting algorithm, DovetailSort, that is theoreticallyefficient and has good practical performance. In particular, DovetailSort overcomes a common challenge in existing parallel integer sorting algorithms, which is the difficulty of detecting and taking advantage of duplicate keys. The key insight in DovetailSort is to combine algorithmic ideas from both integer- and comparison-sorting algorithms. In our experiments, DovetailSort achieves competitive or better performance than existing state-of-the-art parallel integer and comparison sorting algorithms on various synthetic and real-world datasets.

关键词： Integer Sort Radix Sort parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

POSTER: Minimizing speculation overhead in a parallel recognizer for regular texts 30

POSTER: Minimizing speculation overhead in a parallel recogn...

引用

30th symposium on Principles and Practice of parallel Programming

作者： Borsotti, Angelo Breveglieri, Luca Morzenti, Angelo Reghizzi, Stefano Crespi Politecn Milan Milan Italy CNR IEIIT Milan Italy

ISBN: (纸本)9798400714436

Speculative data-parallel algorithms for language recognition have been widely experimented for various types of finite-state automata (FA), deterministic (DFA) and nondeterministic (NFA), often derived from regular expressions (RE). Such an algorithm cuts the input string into chunks, independently recognizes each chunk in parallel by means of identical FAs, and at last joins the chunk results and checks the overall consistency. In chunk recognition, it is necessary to speculatively start the FAs in any state, thus causing an overhead that reduces the speedup over a serial algorithm. The existing data-parallel DFA-based recognizers suffer from an excessive number of starting states, and the NFA-based ones suffer from the number of nondeterministic transitions. Our data-parallel algorithm is based on the new FA type called reduced-interface DFA (RI-DFA), which minimizes the speculation overhead without incurring in the penalty of nondeterministic transitions or of impractically enlarged DFA machines. The algorithm is theoretically efficient, because it combines the state-reduction of an NFA with the speed of deterministic transitions, thus improving on both DFA-based and NFA-based existing implementations. The practical applicability of the RI-DFA approach is confirmed by a quantitative comparison of the number of starting states for a large public benchmark of complex FAs. On multi-core computing architectures, the RI-DFA recognizer is considerably faster than the NFA-based one on all benchmarks, while it matches the DFA-based one on some benchmarks and performs much better on some others. The extra time needed to construct RI-DFA vs DFA is moderate and is compatible with a practical use. The full paper with all details is in [4]. © 2025 Copyright held by the owner/author(s).

关键词： regular language recognition data-parallel recognition algorithm minimal speculation speedup onmulti-core architecture multi-entry DFA reduced-interface DFA

来源：评论

学校读者我要写书评

暂无评论

SPAA 2023 - Proceedings of the 35th acm symposium on parallelism in algorithms and architectures

SPAA 2023 - Proceedings of the 35th ACM Symposium on Paralle...

引用

35th acm symposium on parallelism in algorithms and architectures, SPAA 2023

ISBN: (纸本)9781450395458

The proceedings contain 47 papers. The topics discussed include: Quancurrent: a concurrent quantiles sketch;an efficient scheduler for task-parallel interactive applications;efficient synchronization-light work stealing;balanced allocations in batches: the tower of two choices;massively parallel tree embeddings for high dimensional spaces;deterministic massively parallel symmetry breaking for sparse graphs;an associativity threshold phenomenon in set-associative caches;increment - and - freeze: every cache, everywhere, all of the time;multidimensional approximate agreement with asynchronous fallback;a tight characterization of fast failover routing: resiliency to two link failures is possible;releasing memory with optimistic access: a hybrid approach to memory reclamation and allocation in lock-free programs;transactional composition of nonblocking data structures;applying hazard pointers to more concurrent data structures;and nearly optimal parallel algorithms for longest increasing subsequence.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Nearly Work-Efficient parallel DFS in Undirected Graphs 23

Nearly Work-Efficient Parallel DFS in Undirected Graphs

引用

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

来源：评论

学校读者我要写书评

暂无评论

parallel Minimum Cuts in O(m log² n) Work and Low Depth

引用

acm TRANSACTIONS ON parallel COMPUTING 2023年第4期10卷 1-28页

作者： Anderson, Daniel Blelloch, Guy E. Carnegie Mellon Univ 5000 Forbes Ave Pittsburgh PA 15213 USA

We present a randomized O(m log(2) n) work, O( polylogn) depth parallel algorithm for minimum cut. This algorithm matches thework bounds of a recent sequential algorithm by Gawrychowski, Mozes, andWeimann [ICALP'20], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA'18], which performs O(m log(4) n) work in O(polylogn) depth. Our algorithm makes use of three components that might be of independent interest. First, we design a parallel data structure that efficiently supports batched mixed queries and updates on trees. It generalizes and improves thework bounds of a previous data structure of Geissmann and Gianinazzi and iswork efficient with respect to the best sequential algorithm. Second, we design a parallel algorithm for approximate minimum cut that improves on previous results by Karger and Motwani. We use this algorithm to give a work-efficient procedure to produce a tree packing, as in Karger's sequential algorithm for minimum cuts. Last, we design an efficient parallel algorithm for solving the minimum 2-respecting cut problem.

关键词： Minimum cut parallel algorithms graph algorithms dynamic trees

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Scalable, Programmable and Dense: The HammerBlade Open-Source RISC-V Manycore 51

Scalable, Programmable and Dense: The HammerBlade Open-Sourc...

引用

acm/IEEE 51st annual International symposium on Computer Architecture (ISCA)

作者： Jung, Dai Cheol Ruttenberg, Max Gao, Paul Davidson, Scott Petrisko, Daniel Li, Kangli Kamath, Aditya K. Cheng, Lin Xie, Shaolin Pan, Peitian Zhao, Zhongyuan Yue, Zichao Veluri, Bandhav Muralitharan, Sripathi Sampson, Adrian Lumsdaine, Andrew Zhang, Zhiru Batten, Christopher Oskin, Mark Richmond, Dustin Taylor, Michael Bedford Univ Washington Seattle WA 98195 USA Cornell Univ Ithaca NY USA PNNL Richland WA USA Univ Calif Santa Cruz Santa Cruz CA USA

ISBN: (纸本)9798350326598;9798350326581

Existing tiled manycore architectures propose to convert abundant silicon resources into general-purpose parallel processors with unmatched computational density and programmability. However, as we approach 100K cores in one chip, conventional manycore architectures struggle to navigate three key axes: scalability, programmability, and density. Many manycores sacrifice programmability for density;or scalability for programmability. In this paper, we explore HammerBlade, which simultaneously achieves scalability, programmability and density. HammerBlade is a fully open-source RISC-V manycore architecture, which has been silicon-validated with a 2048-core ASIC implementation using a 14/16nm process. We evaluate the system using a suite of parallel benchmarks that captures a broad spectrum of computation and communication patterns.

关键词： manycore architecture parallel programming open-source hardware RISC-V

来源：评论

学校读者我要写书评

暂无评论

Improving Tridiagonalization Performance on GPU architectures 25

Improving Tridiagonalization Performance on GPU Architecture...

引用

30th symposium on Principles and Practice of parallel Programming

作者： Wang, Hansheng Duan, Zhekai Zhao, Zitian Wu, Siqi Zheng, Saiqi Li, Qiao Jiang, Xu Zhang, Shaoshuai Univ Elect Sci & Technol China Chengdu Peoples R China Univ Edinburgh Edinburgh Midlothian Scotland Xian Jiaotong Liverpool Univ Xian Peoples R China

ISBN: (纸本)9798400714436

Tridiagonalization, which is a key step in symmetric eigenvalue decomposition (EVD), aims to convert a symmetric matrix to a tridiagonal form. In Nvidia's cuSOLVER library, the FP64 precision tridiagonalization process only reach 2.1 TFLOPs out of 67 TFLOPs on H100 GPU, and it consumes a significant portion of the elapsed time in the entire EVD process, accounting for over 97%. Thus, improving the tridiagonalization performance is crucial on accelerating EVD. In this paper, we analyze the reasons behind the suboptimal performance of tridiagonalization on GPU architectures, and we propose a new double blocking band reduction algorithm along with an implementation of GPU-based bulge chasing to improve the tridiagonalization performance. Through experimental evaluation, the proposed FP64 precision tridiagonalization method yields up to 19.6 TFLOPs which is 9.3x and 5.2x faster compared cuSOVLER and MAGMA, respectively.

关键词： Eigenvalue Decomposition GPGPU Numerical Linear Algebra HPC Matrix Computation

来源：评论

学校读者我要写书评

暂无评论

Work-Efficient parallel Derandomization II: Optimal Concentrations via Bootstrapping 2024

Work-Efficient Parallel Derandomization II: Optimal Concentr...

引用

56th annual acm symposium on Theory of Computing (STOC)

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

ISBN: (纸本)9798400703836

In this paper, we present an efficient parallel derandomization method for randomized algorithms that rely on concentrations such as the Chernoff bound. This settles a classic problem in parallel derandomization, which dates back to the 1980s. Concretely, consider the set balancing problem where m sets of size at most B are given in a ground set of size n, and we should partition the ground set into two parts such that each set is split evenly up to a small additive (discrepancy) bound. A random partition achieves a discrepancy of O (root s log m) in each set, by Chernoff bound. We give a deterministic parallel algorithm that matches this bound, using near-linear work (O) over tilde (m + n + Sigma(m)(i=1) vertical bar S-i vertical bar and polylogarithmic depth poly(log (mn)). The previous results were weaker in discrepancy and/or work bounds: Motwani, Naor, and Naor [FOCS'89] and Berger and Rompel [FOCS'89] achieve discrepancy BY center dot $ (p B log <) with work <(O)over tilde> (m + n + Sigma(m)(i=1) vertical bar S-i vertical bar)center dot m(Theta(1/epsilon)) and polylogarithmic depth;the discrepancy was optimized to O (root s log m) in later work, e.g. by Harris [Algorithmica'19], but the work bound remained prohibitively high at (O) over tilde (m(4)n(3)). Notice that these would require a large polynomial number of processors to even match the near-linear runtime of the sequential algorithm. Ghaffari, Grunau, and Rozhon [FOCS'23] achieve discrepancy s/poly(log(nm)) + O(root s log m) with near-linear work and polylogarithmic-depth. Notice that this discrepancy is nearly quadratically larger than the desired bound and barely sublinear with respect to the trivial bound of s. Our method is different from prior work. It can be viewed as a novel bootstrapping mechanism that uses crude partitioning algorithms as a subroutine and sharpens their discrepancy to the optimal bound. In particular, we solve the problem recursively, by using the crude partition in each iterat

关键词： parallel algorithms Derandomization

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: A parallel Architecture for Dynamic Approximate Membership 23

Brief Announcement: A Parallel Architecture for Dynamic Appr...

引用

35th acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Even, Guy Domingues, Gabriel Marques Toutian, Parham Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9781450395458

We present the first parallel architecture for a dynamic approximate membership data-structure (i.e., a filter) that supports insertions, deletions, and approximate membership queries. Our architecture borrows techniques from PRAM emulation to obtain a parallel filter based on two levels of fingerprint-dictionaries. A key component in the architecture is a special-purpose wide-word processor we designed to support operations over small dictionaries. We implemented this architecture on an FPGA running at 100MHz. The implementation stores up to 1.44 million keys, has a false-positive rate less than 0.3%, receives batches 16 of operations per cycle, preserves sequential order, and runs with a stable throughput of over a billion operations per second with respect to several benchmarks.

关键词： data structures Bloom filter PRAM

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：