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

53rd International Conference on parallel Processing (ICPP)

作者： Srikanth, Mithinti Singh, Prashant Ramakrishna, G. Indian Inst Technol Tirupati Tirupati Andhra Pradesh India

ISBN: (纸本)9798400717932

This paper introduces the first GPU-based parallel algorithms to solve the fastest path duration (FPD) problem in temporal graphs. Fastest path duration in temporal graphs is a well studied problem that has multiple use cases in information diffusion, epidemic spreading, and route planning in public transportation. Given a temporal graph G in which each edge associates with a departure time and duration time, and a source vertex s, the Fastest Path Duration (FPD) problem is to compute the journey times from s to all the rest of the vertices in G. The existing multi-core algorithm for FPD by Delling et al. exhibits limited parallelism. In general, many parallel algorithms suffer from doing redundant work while pruning certain computations. Our research focuses on multiple algorithmic ways to avoid redundant work and perform pruning of computations effectively. We introduce three novel GPU-based parallel algorithms for FPD, namely Level Order (LO), Multiple Breadth First Search (MBFS), and Local Work-lists (LW) and implement them on a GPU architecture machine. Our algorithms demonstrate an average speedup of approximately 165 times and a maximum speedup of up to 1383 times over the current state-of-the-art algorithms. This paper provides a comprehensive explanation of various algorithm designs, their optimizations for GPUS, and an extensive evaluation of their performance across various temporal graph scenarios.

关键词： Temporal Graph Fastest Path GPU-algorithms massively parallel algorithms Transformed Graph Journey Time

来源：评论

学校读者我要写书评

暂无评论

Cover or Pack: New Upper and Lower Bounds for massively parallel Joins 21

Cover or Pack: New Upper and Lower Bounds for Massively Para...

引用

40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Hu, Xiao Duke Univ Durham NC 27706 USA

ISBN: (纸本)9781450383813

This paper considers the worst-case complexity of multi-round join evaluation in the massively parallel Computation (MPC) model. Unlike the sequential RAM model, in which there is a unified optimal algorithm based on the AGM bound for all join queries, worst-case optimal algorithms have been achieved on a very restrictive class of joins in the MPC model. The only known lower bound is still derived from the AGM bound, in terms of the optimal fractional edge covering number of the query. In this work, we make efforts towards bridging this gap. We design an instance-dependent algorithm for the class of alpha-acyclic join queries. In particular, when the maximum size of input relations is bounded, this complexity has a closed form in terms of the optimal fractional edge covering number of the query, which is worst-case optimal. Beyond acyclic joins, we surprisingly find that the optimal fractional edge covering number does not lead to a tight lower bound. More specifically, we prove for a class of cyclic joins a higher lower bound in terms of the optimal fractional edge packing number of the query, which is matched by existing algorithms, thus optimal. This new result displays a significant distinction for join evaluation, not only between acyclic and cyclic joins, but also between the fine-grained RAM and coarse-grained MPC model.

关键词： query processing massively parallel algorithms worst-case optimal

来源：评论

学校读者我要写书评

暂无评论

Location-Sensitive String Problems in MPC 23

Location-Sensitive String Problems in MPC

引用

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

作者： Gilbert, Jacob Hajiaghayi, MohammadTaghi Saleh, Hamed Seddighin, Saeed Univ Maryland College Pk MD 20742 USA Toyota Technol Inst Chicago Chicago IL USA

ISBN: (纸本)9781450395458

A suffix tree is a trie-like data structure that stores every suffix of an input string of length n. Finding the Suffix Tree of a given string is a well-studied and classic problem. A compressed suffix tree is constructible in O(n) time using the well-known algorithm of McCreight (JACM, 1976) [24]. Suffix trees alongside with hashing are two powerful tools in solving location-sensitive string problems. Many well-studied fundamental string problems such as String Matching, Longest Palindrome Substring (LPS), Longest Common Substring (LCS), and Longest Common Prefix (LCP) queries are location-sensitive and have linear time solutions via reductions to suffix tree. Inspired by suffix trees, we study location-sensitive string problems LCP, LPS, and LCS in the massively parallel Computation (MPC) model. Our algorithms extensively utilize a novel data structure for answering O(n(1+c)) arbitrary LCP queries, called an LCPQ oracle, in O(1) rounds and with (O) over tilde (n(1+epsilon)) total memory. Using our LCPQ oracle we are able to give the first O(1)-round, (O) over tilde (n) total memory algorithm inMPCfor LPS and an O(1)-round LCS solution using (O) over tilde (n(1+epsilon)) total memory, beating previous state-of-the-art techniques for both problems. Furthermore, we give an O(1/epsilon)-round MPC algorithm for constructing suffix arrays and suffix trees utilizing our LCPQ oracle, and demonstrate reductions for LPS and LCS to suffix tree in O(1) rounds of MPC. Finally, we show that in the Adaptive massively parallel Computation (AMPC) model, we can build a fully-functional suffix tree for a given input string in O(1) rounds and with (O) over tilde (n) total memory for any constant epsilon > 0.

关键词： Data Structures massively parallel algorithms Suffix Trees

来源：评论

学校读者我要写书评

暂无评论

Accelerating BWA-MEM Read Mapping on GPUs 23

Accelerating BWA-MEM Read Mapping on GPUs

引用

37th ACM International Conference on Supercomputing (ACM ICS)

作者： Minh Pham Tu, Yicheng Lv, Xiaoyi Univ S Florida Tampa FL 33620 USA Xinjiang Univ Urumqi Peoples R China

ISBN: (纸本)9798400700569

Advancements in Next-Generation Sequencing (NGS) have significantly reduced the cost of generating DNA sequence data and increased the speed of data production. However, such high-throughput data production has increased the need for efficient data analysis programs. One of the most computationally demanding steps in analyzing sequencing data is mapping short reads produced by NGS to a reference DNA sequence, such as a human genome. The mapping program BWA-MEM and its newer version BWA-MEM2, optimized for CPUs, are some of the most popular choices for this task. In this study, we discuss the implementation of BWA-MEM on GPUs. This is a challenging task because many algorithms and data structures in BWA-MEM do not execute efficiently on the GPU architecture. This paper identifies major challenges in developing efficient GPU code on all major stages of the BWA-MEM program, including seeding, seed chaining, Smith-Waterman alignment, memory management, and I/O handling. We conduct comparison experiments against BWA-MEM and BWA-MEM2 running on a 64-thread CPU. The results show that our implementation achieved up to 3.2x speedup over BWA-MEM2 and up to 5.8x over BWA-MEM when using an NVIDIA A40. Using an NVIDIA A6000 and an NVIDIA A100, we achieved a wall-time speedup of up to 3.4x/3.8x over BWA-MEM2 and up to 6.1x/6.8x over BWA-MEM, respectively. In stage-wise comparison, the A40/A6000/A100 GPUs respectively achieved up to 3.7/3.8/4x, 2/2.3/2.5x, and 3.1/5/7.9x speedup on the three major stages of BWA-MEM: seeding and seed chaining, Smith-Waterman, and making SAM output. To the best of our knowledge, this is the first study that attempts to implement the entire BWA-MEM program on GPUs. Source code: https://***/minhhpham/bwa

关键词： NGS alignment GPU massively parallel algorithms BWA

来源：评论

学校读者我要写书评

暂无评论

G-PICS: A Framework for GPU-Based Spatial Indexing and Query Processing

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2022年第3期34卷 1243-1257页

作者： Lewis, Zhila-Nouri Tu, Yi-Cheng Univ S Florida Comp Sci & Engn Tampa FL 33620 USA

Support for efficient spatial data storage and retrieval has become a vital component in almost all spatial database systems. While GPUs have become a mainstream platform for high-throughput data processing in recent years, exploiting the massively parallel processing power of GPUs is non-trivial. Current approaches that parallelize one query at a time have low work efficiency and cannot make good use of GPU resources. On the other hand, many spatial database systems could receive a large number of queries simultaneously. In this paper, we present a comprehensive framework named G-PICS for parallel processing of concurrent spatial queries on GPUs. G-PICS encapsulates efficient parallel algorithms for constructing a variety of spatial trees with different space partitioning methods. G-PICS also provides highly optimized programs for processing major spatial query types, and such programs can be accessed via an API that could be further extended to implement user-defined algorithms. While support for dynamic data inputs is missing in existing work, G-PICS implements efficient parallel algorithms for bulk updates of data. Furthermore, G-PICS is designed to work in a Multi-GPU environment to support datasets beyond the size of a single GPU's global memory. Empirical evaluation of G-PICS shows significant performance improvement over the state-of-the-art GPU and parallel CPU-based spatial query processing systems. In particular, G-PICS achieves double-digit speedup over such systems in tree construction (up to 53X) and query processing (up to 80X).

关键词： Query processing Graphics processing units Spatial databases Indexing parallel processing Computational modeling Spatial indexes Spatial query processing massively parallel algorithms GPU computing

来源：评论

学校读者我要写书评

暂无评论

Faster Segmented Sort on GPUs 29th

Faster Segmented Sort on GPUs

引用

29th International Conference on parallel and Distributed Computing (Euro-Par)

作者： Kobus, Robin Nelgen, Johannes Henkys, Valentin Schmidt, Bertil Johannes Gutenberg Univ Mainz Inst Comp Sci D-55128 Mainz Germany

ISBN: (纸本)9783031396977;9783031396984

Efficient parallel implementations of various sorting algorithms on modern hardware platforms are essential to numerous application areas. In this paper, we first measure the performance of the leading segmented sort implementation on CUDA-enabled GPUs and determine optimal setups using the resulting runtimes. Subsequently, we propose a number of changes that improve efficiency for segments of specific lengths. Furthermore, an alternative key-only version is introduced, that is specifically optimized to just sort keys instead of key-value pairs, which allows for further optimization. Performance is evaluated by comparing runtimes of the original algorithm with our improved version for segments of different lengths resulting in average speedups between 1.26 and 1.35 on four GPUs of different generations (Pascal, Volta, Ampere, Ada Lovelace). Furthermore, comparison to alternative segmented sort implementations from CUB and ModernGPU results in average speedups of at least 2.2 and 2.5, respectively, across all tested architectures. To illustrate how our improved sorting algorithm can be beneficial in a practical application, we have integrated it into the MetaCache-GPU pipeline for metagenomic DNA classification resulting in speedups of up to 25.6% for the sorting step. Code is publicly available at https://***/pararch/faster-segmented-sort-on-gpus.

关键词： GPUs Sorting massively parallel algorithms CUDA Bioinformatics

来源：评论

学校读者我要写书评

暂无评论

Scalable adaptive algorithms for next-generation multiphase flow simulations 37

Scalable adaptive algorithms for next-generation multiphase ...

引用

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

作者： Saurabh, Kumar Ishii, Masado Khanwale, Makrand A. Sundar, Hari Ganapathysubramanian, Baskar Iowa State Univ Dept Mech Engn Ames IA 50011 USA Univ Utah Sch Comp Salt Lake City UT USA Stanford Univ Ctr Turbulence Res Stanford CA USA

ISBN: (纸本)9798350337662

High-fidelity flow simulations are indispensable when analyzing systems exhibiting multiphase flow phenomena. The accuracy of multiphase flow simulations is strongly contingent upon the finest mesh resolution used to represent the fluid-fluid interfaces. However, the increased resolution comes at a higher computational cost. In this work, we propose algorithmic advances that aim to reduce the computational cost without compromising on the physics by selectively detecting key regions of interest (droplets/filaments) that require significantly higher resolution. The framework uses an adaptive octree-based meshing framework that is integrated with PETSc's linear algebra solvers. We demonstrate scaling of the framework up to 114,688 processes on TACC's Frontera. Finally, we deploy the framework to simulate one of the most resolved simulations of primary jet atomization. This simulation - equivalent to 35 trillion grid points on a uniform grid - is 64x larger than current state-of-the-art simulations and provides unprecedented insights into an important flow physics problem with a diverse array of engineering applications.

关键词： multiphase flow simulations octree massively parallel algorithms adaptive mesh

来源：评论

学校读者我要写书评

暂无评论

Highly scalable hybrid domain decomposition method for the solution of huge scalar variational inequalities

引用

NUMERICAL algorithms 2022年第2期91卷 773-801页

作者： Dostal, Zdenek Horak, David Kruzik, Jakub Brzobohaty, Tomas Vlach, Oldrich VSB Tech Univ Ostrava Dept Appl Math 17 Listopadu 15 Ostrava 70833 Czech Republic VSB Tech Univ Ostrava IT4Innovat Natl Supercomp Ctr 17 Listopadu 15 Ostrava 70833 Czech Republic VSB TU Ostrava Dept Appl Math Ostrava Czech Republic Inst Geon ASCR Ostrava Czech Republic

The unpreconditioned hybrid domain decomposition method was recently shown to be a competitive solver for linear elliptic PDE problems discretized by structured grids. Here, we plug H-TFETI-DP (hybrid total finite element tearing and interconnecting dual primal) method into the solution of huge boundary elliptic variational inequalities. We decompose the domain into subdomains that are discretized and then interconnected partly by Lagrange multipliers and partly by edge averages. After eliminating the primal variables, we get a quadratic programming problem with a well-conditioned Hessian and bound and equality constraints that is effectively solvable by specialized algorithms. We prove that the procedure enjoys optimal, i.e., asymptotically linear complexity. The analysis uses recently established bounds on the spectrum of the Schur complements of the clusters interconnected by edge/face averages. The results extend the scope of scalability of massively parallel algorithms for the solution of variational inequalities and show the outstanding efficiency of the H-TFETI-DP coarse grid split between the primal and dual variables.

关键词： Domain decomposition Variational inequality Scalability massively parallel algorithms Hybrid TFETI-DP

来源：评论

学校读者我要写书评

暂无评论

FastFlow: GPU Acceleration of Flow and Depression Routing for Landscape Simulation

引用

COMPUTER GRAPHICS FORUM 2024年第7期43卷

作者： Jain, Aryamaan Kerbl, Bernhard Gain, James Finley, Brandon Cordonnier, Guillaume Univ Cote Azur Inria Nice France TU Wien Vienna Austria Univ Cape Town Cape Town South Africa Univ Lausanne Lausanne Switzerland

Terrain analysis plays an important role in computer graphics, hydrology and geomorphology. In particular, analyzing the path of material flow over a terrain with consideration of local depressions is a precursor to many further tasks in erosion, river formation, and plant ecosystem simulation. For example, fluvial erosion simulation used in terrain modeling computes water discharge to repeatedly locate erosion channels for soil removal and transport. Despite its significance, traditional methods face performance constraints, limiting their broader applicability. In this paper, we propose a novel GPU flow routing algorithm that computes the water discharge in O(log n) iterations for a terrain with n vertices (assuming n processors). We also provide a depression routing algorithm to route the water out of local minima formed by depressions in the terrain, which converges in O(log(2) n) iterations. Our implementation of these algorithms leads to a 5x speedup for flow routing and 34 x to 52 x speedup for depression routing compared to previous work on a 10242 terrain, enabling interactive control of terrain simulation.

关键词： CCS Concepts • Computing methodologies → Shape modeling massively parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

In Situ Visualization With Temporal Caching

引用

COMPUTING IN SCIENCE & ENGINEERING 2021年第3期23卷 25-33页

作者： DeMarle, David E. Bauer, Andrew C. 2200 Mission Coll Blvd Santa Clara CA 95054 USA US Army Engineer Res & Dev Ctr Vicksburg MS 39180 USA

In situ visualization is a technique in which plots and other visual analyses are performed in tandem with numerical simulation processes in order to better utilize HPC machine resources. Especially with unattended exploratory engineering simulation analyses, events may occur during the run, which justify supplemental processing. Sometimes though, when the events do occur, the phenomena of interest includes the physics that precipitated the events and this may be the key insight into understanding the phenomena that is being simulated. In situ temporal caching is the temporary storing of produced data in memory for possible later analysis including time varying visualization. The later analysis and visualization still occurs during the simulation run but not until after the significant events have been detected. In this article, we demonstrate how temporal caching can be used with in-line in situ visualization to reduce simulation run-time while still capturing essential simulation results.

关键词： Computational modeling Data visualization Data models Catalysis Feature extraction Libraries Analytical models massively parallel algorithms Scientific visualization In Situ processing Time Varying Data

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：