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

Performance, Portability and Productivity in HPC (P3HPC)

作者： Yuuichi Asahi Thomas Padioleau Guillaume Latu Julien Bigot Virginie Grandgirard Kevin Obrejan CCSE Japan Atomic Energy Agency Chiba Japan Université Paris-Saclay UVSQ CNRS CEA Maison de la Simulation Gif-sur-Yvette France DES/IRESNE/DEC CEA St.Paul-lez-Durance France IRFM CEA St.Paul-lez-Durance France

ISBN: (纸本)9781665460224

This paper presents the performance portable implementation of a kinetic plasma simulation code with C++ parallel algorithm to run across multiple CPUs and GPUs. Relying on the language standard parallelism stdpar and proposed language standard multi-dimensional array support mdspan, we demonstrate that a performance portable implementation is possible without harming the readability and productivity. We obtain a good overall performance for a mini-application in the range of 20 % to the Kokkos version on Intel Icelake, NVIDIA V100, and A100 GPUs. Our conclusion is that stdpar can be a good candidate to develop a performance portable and productive code targeting the Exascale era platform, assuming this approach will be available on AMD and/or Intel GPUs in the future.

关键词： Productivity Plasma simulation Codes Conferences C++ languages Kinetic theory parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

GPU-Accelerated Batch-Dynamic Subgraph Matching

GPU-Accelerated Batch-Dynamic Subgraph Matching

引用

International Conference on Data Engineering

作者： Linshan Qiu Lu Chen Hailiang Jie Xiangyu Ke Yunjun Gao Yang Liu Zetao Zhang Zhejiang University Hangzhou China Huawei Chengdu China

ISBN: (数字)9798350317152

ISBN: (纸本)9798350317169

Subgraph matching has garnered increasing attention for its diverse real-world applications. Given the dynamic nature of real-world graphs, addressing evolving scenarios with-out incurring prohibitive overheads has been a focus of research. However, existing approaches for dynamic subgraph matching often proceed serially, retrieving incremental matches for each updated edge individually. This approach falls short when handling batch data updates, leading to a decrease in system throughput. Leveraging the parallel processing power of GPUs, which can execute a massive number of cores simultaneously, has been widely recognized for performance acceleration in various domains. Surprisingly, systematic exploration of subgraph matching in the context of batch-dynamic graphs, particularly on a GPU platform, remains untouched. In this paper, we bridge this gap by introducing an efficient framework, GAMMA (GPU-Accelerated Batch-Dynamic Subgraph Matching). Our approach features a DFS-based warp-centric batch-dynamic subgraph matching algorithm. To ensure load balance in the DFS-based search, we propose warp-level work stealing via shared memory. Additionally, we introduce coalesced search to reduce redundant computations. Comprehensive experiments demonstrate the superior performance of GAMMA. Compared to state-of-the-art algorithms, GAMMA showcases a performance improvement up to hundreds of times.

关键词： Bridges Systematics Graphics processing units Throughput Data engineering Vehicle dynamics parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal Preprocessing for Answering On-Line Product Queries

arXiv

引用

arXiv 2024年

作者： Alon, Noga Schieber, Baruch Department of Mathematics School of Mathematical Sciences Tel Aviv University Tel Aviv69978 Israel Department of Computer Science School of Mathematical Sciences Tel Aviv University Tel Aviv69978 Israel

We examine the amount of preprocessing needed for answering certain on-line queries as fast as possible. We start with the following basic problem. Suppose we are given a semigroup (S, ◦). Let s1, . . ., sn be elements of S. We want to answer on-line queries of the form, "What is the product si◦si+1◦ · · · ◦sj−1◦sj?" for any given 1 ≤ i ≤ j ≤ n. We show that a preprocessing of Θ(nλ(k, n)) time and space is both necessary and sufficient to answer each such query in at most k steps, for any fixed k. The function λ(k, ·) is the inverse of a certain function at the ⌊k/2⌋-th level of the primitive recursive hierarchy. In case linear preprocessing is desired, we show that one can answer each such query in O(α(n)) steps and that this is best possible. The function α(n) is the inverse Ackermann function. We also consider the following extended problem. Let T be a tree with an element of S associated with each of its vertices. We want to answer on-line queries of the form, "What is the product of the elements associated with the vertices along the path from u to v?" for any pair of vertices u and v in T. We derive results that are similar to the above, for the preprocessing needed for answering such queries. All our sequential preprocessing algorithms can be parallelized efficiently to give optimal parallel algorithms which run in O(log n) time on a CREW PRAM. These parallel algorithms are optimal in both running time and total number of operations. Our algorithms, especially for the semigroup of the real numbers with the minimum or maximum operations, have various applications in certain graph algorithms, in the utilization of communication networks and in Database retrieval. © 2024, CC BY.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and parallel Applications

Deterministic Low-Diameter Decompositions for Weighted Graph...

引用

Annual IEEE Symposium on Foundations of Computer Science

作者： Václav Rozhoň Michael Elkin Christoph Grunau Bernhard Haeupler ETH Zurich Ben-Gurion University of the Negev ETH Zurich & Carnegie Mellon University

ISBN: (数字)9781665455190

ISBN: (纸本)9781665455206

This paper presents new deterministic and distributed low-diameter decomposition algorithms for weighted graphs. In particular, we show that if one can efficiently compute approximate distances in a parallel or a distributed setting, one can also efficiently compute low-diameter decompositions. This consequently implies solutions to many fundamental distance based problems using a polylogarithmic number of approximate distance *** low-diameter decomposition generalizes and extends the line of work starting from [RG20] to weighted graphs in a very model-independent manner. Moreover, our clustering results have additional useful properties, including strong-diameter guarantees, separation properties, restricting cluster centers to specified terminals, and more. Applications include:–The first near-linear work and polylogarithmic depth randomized and deterministic parallel algorithm for low-stretch spanning trees (LSST) with polylogarithmic stretch. Previously, the best parallel LSST algorithm required $m.n^{o(1)}$ work and $n^{o(1)}$ depth and was inherently randomized. No deterministic LSST algorithm with truly sub-quadratic work and sub-linear depth was known.–The first near-linear work and polylogarithmic depth deterministic algorithm for computing an $\ell_algorithms-$embedding into polylogarithmic dimensional space with polylogarithmic distortion. The best prior deterministic algorithms for $\ell_algorithms$-embeddings either require large polynomial work or are inherently *** when we apply our techniques to the classical problem of computing a ball-carving with strong-diameter $O(\log^{2}n)$ in an unweighted graph, our new clustering algorithm still leads to an improvement in round complexity from $O(\log^{10}n)$ rounds [CG21] to $O(\log^{4}n)$.

关键词： Computer science Computational modeling Clustering algorithms Distortion Approximation algorithms Complexity theory parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

MST in Incremental Graphs Through Tree Contractions

MST in Incremental Graphs Through Tree Contractions

引用

IEEE Conference on High Performance Extreme Computing (HPEC)

作者： Akanksha Dwivedi Sameer Sharma Dip Sankar Banerjee Department of Computer Science and Engineering Indian Institute of Technology Jodhpur India

ISBN: (数字)9798350387131

ISBN: (纸本)9798350387148

Dynamic graphs, characterized by rapid changes in their topological structure through adding or deleting edges or vertices, pose significant challenges for algorithm design. This paper presents a parallel algorithm for dynamic graphs in a batched setting. We employ a popular tree contraction mechanism to create a hierarchical representation of the input graph that allows the identification of localized areas that further enable maintaining a critical graph primitive such as the minimum spanning tree (MST) without requiring re-computation from scratch. We perform experiments to demonstrate the application of our algorithm in real-world graphs where batch-dynamic algorithms on large trees are essential for incremental updates. We show experimental validations on GPUs where our proposed technique can provide up to 3.43x speedup over equivalent parallel implementations on shared memory CPUs. Additionally, our methods can provide up to 4.23x speedup over conventional parallel computation from scratch.

关键词： Heuristic algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Enumeration of Large Maximal k-Plexes

arXiv

引用

arXiv 2024年

作者： Cheng, Qihao Yan, Da Wu, Tianhao Yuan, Lyuheng Cheng, Ji Huang, Zhongyi Zhou, Yang Tsinghua University China Indiana University Bloomington United States HKUST Hong Kong Auburn University United States

Finding cohesive subgraphs in a large graph has many important applications, such as community detection and biological network analysis. Clique is often a too strict cohesive structure since communities or biological modules rarely form as cliques for various reasons such as data noise. Therefore, k-plex is introduced as a popular clique relaxation, which is a graph where every vertex is adjacent to all but at most k vertices. In this paper, we propose a fast branch-and-bound algorithm as well as its task-based parallel version to enumerate all maximal kplexes with at least q vertices. Our algorithm adopts an effective search space partitioning approach that provides a lower time complexity, a new pivot vertex selection method that reduces candidate vertex size, an effective upper-bounding technique to prune useless branches, and three novel pruning techniques by vertex pairs. Our parallel algorithm uses a timeout mechanism to eliminate straggler tasks, and maximizes cache locality while ensuring load balancing. Extensive experiments show that compared with the state-of-the-art algorithms, our sequential and parallel algorithms enumerate large maximal k-plexes with up to 5× and 18.9× speedup, respectively. Ablation results also demonstrate that our pruning techniques bring up to 7× speedup compared with our basic algorithm. Our code is released at https://***/chengqihao/Maximal-kPlex. © 2024, CC BY.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS

arXiv

引用

arXiv 2024年

作者： Koo, Jaehyun MIT United States

We present an O(1)-round fully-scalable deterministic massively parallel algorithm for computing the min-plus matrix multiplication of unit-Monge matrices. We use this to derive a O(log n)-round fully-scalable massively parallel algorithm for solving the exact longest increasing subsequence (LIS) problem. For a fully-scalable MPC regime, this result substantially improves the previously known algorithm of O(log4 n)-round complexity, and matches the best algorithm for computing the (1 + ǫ)-approximation of LIS. © 2024, CC BY.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Enhancing Text Summarization through parallelization: A TF-IDF Algorithm Approach

Enhancing Text Summarization through Parallelization: A TF-I...

引用

Intelligent Cyber Physical Systems and Internet of Things (ICoICI), International Conference on

作者： Diwesh Chaurasia Prof. Vimala Devi K Mudit Bhatta School of Computer Science and Engineering Vellore Institute of Technology Vellore Tamil Nadu India

ISBN: (数字)9798331540661

ISBN: (纸本)9798331540678

Text parallelization is a crucial aspect of natural language processing, aiming to enhance the efficiency of information retrieval and analysis. This project focuses on leveraging the Term Frequency-Inverse Document Frequency (TF-IDF) algorithm to achieve text parallelization. TF-IDF is a widely used technique for information retrieval and document similarity measurement. In this study, we propose a novel approach that harnesses the TF-IDF algorithm to identify and parallelize relevant sections of text, thereby improving the speed and scalability of text processing tasks. We present a comprehensive analysis of the proposed method, evaluating its effectiveness in comparison to traditional approaches. Our results demonstrate the potential of TF-IDF-based text parallelization in optimizing information extraction processes. This research contributes to the ongoing efforts in advancing text processing techniques, particularly in the context of large-scale document analysis.

关键词： Machine learning algorithms Scalability Transfer learning Text summarization Information retrieval Transformers Natural language processing Internet of Things parallel algorithms Text processing

来源：评论

学校读者我要写书评

暂无评论

Constant-Memory Graph Coarsening

Constant-Memory Graph Coarsening

引用

IEEE Conference on High Performance Extreme Computing (HPEC)

作者： George M. Slota Christopher Brissette Rensselaer Polytechnic Institute

ISBN: (数字)9798350387131

ISBN: (纸本)9798350387148

Graph coarsening is an important step for many multi-level algorithms, most notably graph partitioning. However, such methods often utilize an iterative approach, where a new coarser graph representation is explicitly constructed and retained in memory at each level of coarsening. These overheads can be prohibitive for processing massive datasets or in constrained-memory environments like GPUs. We develop a data structure (CM-Graph) for representing coarsened graphs, which can be used with any adjacency-based graph representation. The CM-Graph data structure uses a constant amount of memory, regardless of the desired level of coarsening. In addition, CMGraph does not require modification to the existing graph representation, it offers a several-fold memory savings in practice, and it can even accelerate graph coarsening, due to not having to explicitly construct coarser graph structures. We further describe efficient GPU parallelizations of the CM-Graph subroutines for adjacency access, which can also be utilized in most arbitrary graph computations without modification.

关键词： Memory management Graphics processing units Data structures Partitioning algorithms Computational efficiency Iterative methods parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

An Adaptive Asynchronous Approach for the Single-Source Shortest Paths Problem

An Adaptive Asynchronous Approach for the Single-Source Shor...

引用

High Performance Computing, Networking, Storage and Analysis, SC-W: Workshops of the International Conference for

作者： Ritvik Rao Kavitha Chandrasekar Laxmikant Kale University of Illinois Urbana IL USA

ISBN: (数字)9798350355543

ISBN: (纸本)9798350355550

Large-scale graphs with billions and trillions of vertices and edges require efficient parallel algorithms for common graph problems, one of which is single-source shortest paths (SSSP). Bulk-synchronous parallel algorithms such as ∆-stepping experience large synchronization costs at the scale of many nodes, so asynchronous approaches are needed for scalability. However, asynchronous approaches are susceptible to wasteful, speculative execution. We introduce ACIC, a highly asynchronous approach modulated by continuous concurrent introspection and adaptation. Using message-driven concurrent reductions and broadcasts, task-based scheduling, and an adaptive aggregation library, we explore techniques such as evolving windows and generation and prioritized flow of optimal updates, or edge relaxations, aimed at reducing speculative loss without constraining parallelism. Our results, while preliminary, demonstrate the promise of these ideas, with the potential to impact a wider class of graph algorithms.

关键词： Shortest path problem Costs Scalability High performance computing Conferences Libraries Synchronization parallel algorithms Optimization Monitoring

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：