ACM Transactions on Parallel Computing

Massively parallel systems, such as Graphics Processing Units (GPUs), play an increasingly crucial role in today’s data-intensive computing. The unique challenges associated with developing system software for massively parallel hardware to support numerous parallel threads efficiently are of paramount importance. One such challenge is the design of a dynamic memory allocator to allocate memory at runtime. Traditionally, memory allocators have relied on maintaining a global data structure, such as a queue of free pages. However, in the context of massively parallel systems, accessing such global data structures can quickly become a bottleneck even with multiple queues in place. This paper presents a novel approach to dynamic memory allocation that eliminates the need for a centralized data structure. Our proposed approach revolves around letting threads employ random search procedures to locate free pages. Through mathematical proofs and extensive experiments, we demonstrate that the basic random search design achieves lower latency than the best-known existing solution, Ouroboros, in most situations. Furthermore, we develop more advanced techniques and algorithms to tackle the challenge of warp divergence and further enhance performance when free memory is limited. Building upon these advancements, our mathematical proofs and experimental results affirm that these advanced designs can yield an order of magnitude improvement over the basic design and consistently outperform the state-of-the-art by up to two orders of magnitude. To illustrate the practical implications of our work, we integrate our memory management techniques into two GPU algorithms: a hash join and a group-by. Both case studies provide compelling evidence of our approach’s pronounced performance gains.

Minh Pham

Yongke Yuan

Hao Li

Chengcheng Mou

Yicheng Tu

Zichen Xu

Jinghan Meng

Dynamic Buffer Management in Massively Parallel Systems: The Power of Randomness

大规模并行系统中的动态缓冲区管理：随机性的力量

Clustering is a fundamental task in machine learning. One of the most successful and broadly used algorithms is DBSCAN, a density-based clustering algorithm. DBSCAN requires ϵ-nearest neighbor graphs of the input dataset, which are computed with range-search algorithms and spatial data structures like KD-trees. Despite many efforts to design scalable implementations for DBSCAN, existing work is limited to low-dimensional datasets, as constructing ϵ-nearest neighbor graphs can be expensive in high-dimensions. This paper introduces a modified DBSCAN, using k -nearest neighbor ( k NN) graphs to improve efficiency. We outline conditions for k NN-DBSCAN to match DBSCAN’s results and present a parallel implementation using OpenMP and MPI for shared and distributed memory systems. Testing on datasets up to 32 dimensions, we achieve remarkable scalability. Our implementation clusters one billion 3D points in under one second on 28K cores at TACC’s Frontera system. In a larger run, we cluster 65 billion points in 20 dimensions in under 40 seconds using 114,688 cores. Our method is up to 37 × faster than state-of-the-art parallel DBSCAN on a 20-dimensional dataset with 4 million points. Code is available at https://github.com/ut-padas/knndbscan.

Youguang Chen

William Ruys

George Biros

KNN-DBSCAN: a DBSCAN in high dimensions

KNN-DBSCAN：一种高维DBSCAN

Data sketches are approximate succinct summaries of long data streams. They are widely used for processing massive amounts of data and answering statistical queries about it. Existing libraries producing sketches are very fast, but do not allow parallelism for creating sketches using multiple threads or querying them while they are being built. We present a generic approach to parallelising data sketches efficiently and allowing them to be queried in real time, while bounding the error that such parallelism introduces. Utilising relaxed semantics and the notion of strong linearisability, we prove our algorithm’s correctness and analyse the error it induces in some specific sketches. Our implementation achieves high scalability while keeping the error small. We have contributed one of our concurrent sketches to the open-source data sketches library.

Arik Rinberg

Alexander Spiegelman

Edward Bortnikov

Eshcar Hillel

Idit Keidar

Lee Rhodes

Hadar Serviansky

Fast Concurrent Data Sketches

快速并发数据草图

Locking has been a predominant technique depended upon for achieving thread synchronization and ensuring correctness in multi-threaded applications. It has been established that the concurrent applications working with hierarchical data witness significant benefits due to multi-granularity locking (MGL) techniques compared to either fine- or coarse-grained locking. The de facto MGL technique used in hierarchical databases is intention locks , which uses a traversal-based protocol for hierarchical locking. A recent MGL implementation, dominator-based locking (DomLock), exploits interval numbering to balance the locking cost and concurrency and outperforms intention locks for non-tree-structured hierarchies. We observe, however, that depending upon the hierarchy structure and the interval numbering, DomLock pessimistically declares subhierarchies to be locked when in reality they are not. This increases the waiting time of locks and, in turn, reduces concurrency. To address this issue, we present Multi-Interval DomLock (MID), a new technique to improve the degree of concurrency of interval-based hierarchical locking. By adding additional intervals for each node, MID helps in reducing the unnecessary lock rejections due to false-positive lock status of sub-hierarchies. Unleashing the hidden opportunities to exploit more concurrency allows the parallel threads to finish their operations quickly, leading to notable performance improvement. We also show that with sufficient number of intervals, MID can avoid all the lock rejections due to false-positive lock status of nodes. MID is general and can be applied to any arbitrary hierarchy of trees, Directed Acyclic Graphs (DAGs) , and cycles. It also works with dynamic hierarchies wherein the hierarchical structure undergoes updates. We illustrate the effectiveness of MID using STMBench7 and, with extensive experimental evaluation, show that it leads to significant throughput improvement (up to 141%, average 106%) over DomLock.

M. A. Anju

Rupesh Nasre

Multi-Interval DomLock: Toward Improving Concurrency in Hierarchies

多区间DomLock：面向提升层次结构中的并发性

Detecting strongly connected components (SCCs) in a directed graph is crucial for understanding the structure of graphs. Most real-world graphs have one large SCC that contains the majority of the vertices as well as many small SCCs whose sizes are reversely proportional to the frequency of their occurrences. For both types of SCCs, current approaches that rely on depth first search (DFS) or breadth first search (BFS) face the challenges of both strict synchronization requirements and high computation cost. In this article, we advocate a new paradigm of identifying SCCs with simple spanning trees since SCC detection requires only the knowledge of connectivity among the vertices. We have developed a prototype called i S pan , which consists of parallel, relaxed synchronization construction of spanning trees for detecting large and small SCCs combined with fast trims for small SCCs. We further scale i S pan to the distributed memory system by applying different distribution strategies to the data and task parallel jobs. Not limited, we also extend i S pan to the GPU architecture. The evaluations show that i S pan is able to significantly outperform current state-of-the-art DFS- and BFS-based methods by an average 18× and 4×, respectively.

Yuede Ji

Hang Liu

Yang Hu

H. Howie Huang

<scp>i</scp> <scp>S</scp> <scp>pan</scp> : Parallel Identification of Strongly Connected Components with Spanning Trees

<scp>i</scp> <scp>S</scp> <scp>pan</scp>：基于生成树的强连通分量并行识别

The Longest Common Subsequence (LCS) problem is a well-known and studied problem in computer science and bioinformatics. It consists in finding the longest subsequence that is common to two or more given sequences. In this paper, we address the problem of finding all LCS for the Sequential Substring Constrained-LCS (SSCLCS) problem, called the Multiple SSCLCS problem. To solve this problem, we first propose a dominant point-based sequential algorithm, designed on a new Leveled Direct Acyclic Graph (DAG) that gives the correct evaluation order of subproblems to avoid redundancy due to overlap. Depending on whether the constraints may overlap or not, it requires O ( S | Σ | K + 1 + r + n | Σ |) and O ( S | Σ | K + 1 + n | Σ |) time with \(O(Max\_level+n|\Sigma |) \) space. S is the number of partial SSCLCS in a node, K is the number of DAG levels, n is the length of sequences, r is the total length of constraints, \(Max\_level \) is the number of nodes in the largest level of the DAG, and | Σ | is the length of the alphabet. Then, we derive a coarse-grained multicomputer parallel solution requiring \(O\left(\frac{S|\Sigma |^{K+1}+r+n|\Sigma |}{p}\right) \) and \(O\left(\frac{S|\Sigma |^{K+1}+n|\Sigma |}{p}\right) \) execution time, \(O(Max\_level+n|\Sigma |) \) memory space and O ( K ) communication rounds. p is the number of processors. Experimental results showed that the parallel algorithm is respectively 14.43 × and 19.19 × faster than the sequential algorithm on 32 and 64 processors.

Hermann Bogning Tepiele

Vianney Kengne Tchendji

Mathias Akong Onabid

Jean Frédéric Myoupo

Armel Nkonjoh Ngomade

Dominant point-based sequential and parallel algorithms for the multiple sequential substring constrained-LCS problem

基于支配点的多重序列子串约束最长公共子序列问题的顺序和并行算法

We provide a mathematically proven parallelization scheme for particle methods on distributed-memory computer systems. Particle methods are a versatile and widely used class of algorithms for computer simulations and numerical predictions in various applications, ranging from continuum fluid dynamics to discrete granular flows and molecular dynamics simulations. Particle methods naturally lend themselves to implementation on parallel computing systems. So far, however, a mathematical proof of correctness and equivalence to sequential implementations was only available for shared-memory parallelism. Here, we leverage a formal definition of the algorithmic class of particle methods to provide a proven parallelization scheme for distributed-memory computers. We prove that thus parallelized particle methods on distributed-memory computers are formally equivalent to their sequential counterpart for a well-defined class of particle methods, and we provide analytical expressions for the speed-up and scalability bounds of this class of algorithms in function of their parameters. The parallelization scheme analyzed here is the basis of many real-world software designs for parallel particle methods. The present analysis is, therefore, of direct relevance to existing and new parallel implementations of particle methods and places them on solid theoretical grounds, rationalizing best practices and providing useful scalability and speedup bounds for benchmarking.

Johannes Pahlke

Ivo Sbalzarini

Proven Distributed Memory Parallelization of Particle Methods

粒子方法的分布式内存并行化验证

In this paper, we explore the acceleration of tensor product operations in finite element methods, leveraging the computational power of the NVIDIA A100 GPU Tensor Cores. We provide an accessible overview of the necessary mathematical background and discuss our implementation strategies. Our study focuses on two common programming approaches for NVIDIA Tensor Cores: the C++ Warp Matrix Functions in nvcuda::wmma and the inline Parallel Thread Execution (PTX) instructions mma.sync.aligned . A significant focus is placed on the adoption of the versatile inline PTX instructions combined with a conflict-free shared memory access pattern, a key to unlocking superior performance. When benchmarked against traditional CUDA Cores, our approach yields a remarkable 2.3-fold increase in double precision performance, achieving 8 TFLOPS/s—45% of the theoretical maximum. Furthermore, in half-precision computations, numerical experiments demonstrate a fourfold enhancement in solving the Poisson equation using the flexible GMRES (FGMRES) method, preconditioned by a multigrid method in 3D. This is achieved while maintaining the same discretization error as observed in double precision computations. These results highlight the considerable benefits of using Tensor Cores for finite element operators with tensor products, achieving an optimal balance between computational speed and precision.

Cu Cui

Acceleration of Tensor-Product Operations with Tensor Cores

张量核心加速张量积运算

短名	ACM Trans. Parallel Comput.
Journal Impact	0.78
国际分区	COMPUTER SCIENCE, THEORY & METHODS(Q3)

ISSN	2329-4949, 2329-4957
h-index	22

涉及主题	计算机科学操作系统数学程序设计语言工程类并行计算算法组合数学分布式计算计算机网络理论计算机科学离散数学物理数据库经济数学分析电信
出版信息	出版商: Association for Computing Machinery (ACM)，出版周期: ，期刊类型: journal，开源期刊: 否
基本数据	创刊年份: 2014，原创研究文献占比: 100.00%，自引率:0.00%， Gold OA占比: 7.02%

ACM Transactions on Parallel Computing

期刊引文格式

有 1 位以上作者的期刊

有 2 位作者的期刊

有 3 位作者的期刊

有 5 位以上作者的期刊

书籍引用格式

学位论文引用格式

网页引用格式

专利引用格式

手工熬夜修改参考文献？研飞自动匹配期刊，一键轻松成稿，支持 Word/WPS

投稿经验分享

Dynamic Buffer Management in Massively Parallel Systems: The Power of Randomness

KNN-DBSCAN: a DBSCAN in high dimensions

Fast Concurrent Data Sketches

Multi-Interval DomLock: Toward Improving Concurrency in Hierarchies

i S pan : Parallel Identification of Strongly Connected Components with Spanning Trees

Dynamic Buffer Management in Massively Parallel Systems: The Power of Randomness

KNN-DBSCAN: a DBSCAN in high dimensions

Dominant point-based sequential and parallel algorithms for the multiple sequential substring constrained-LCS problem

Proven Distributed Memory Parallelization of Particle Methods

Acceleration of Tensor-Product Operations with Tensor Cores