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

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

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

ISBN: (纸本)9798400704161

Dynamic trees are a well-studied and fundamental building block of dynamic graph algorithms dating back to the seminal work of Sleator and Tarjan [STOC'81, (1981), pp. 114-122]. The problem is to maintain a tree subject to online edge insertions and deletions while answering queries about the tree, such as the heaviest weight on a path, etc. In the parallel batch-dynamic setting, the goal is to process batches of edge updates work efficiently in low (polylog n) span. Two work-efficient algorithms are known: batch-parallel Euler Tour Trees by Tseng et al. [ALENEX'19, (2019), pp. 92-106] and parallel Rake-Compress (RC) Trees by Acar et al. [ESA'20, (2020), pp. 2:1-2:23]. Both however are randomized and work efficient in expectation. Several downstream results that use these data structures (and indeed to the best of our knowledge, all known workefficient parallel batch-dynamic graph algorithms) are therefore also randomized. In this work, we give the first deterministic work-efficient solution to the problem. Our algorithm maintains a parallel RC-Tree on n vertices subject to batches of k edge updates deterministically in worst-case O(k log(1 + n/k)) work and O(log n log log k) span on the Common-CRCW PRAM. We also show how to improve the span of the randomized algorithm from O(log n log* n) to O(log n). Lastly, as a result of our new deterministic algorithm, we also derandomize several downstream results that make use of parallel batch-dynamic dynamic trees, previously for which the only efficient solutions were randomized.

关键词： dynamic trees parallel graph algorithms batch-dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable Fine-Grained parallel Cycle Enumeration algorithms 22

Scalable Fine-Grained Parallel Cycle Enumeration Algorithms

引用

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

作者： Blanusa, Jovan Ienne, Paolo Atasu, Kubilay IBM Res Europe Zurich Switzerland Ecole Polytechn Federale Lausanne EPFL Sch Comp & Commun Sci CH-1015 Lausanne Switzerland

ISBN: (纸本)9781450391467

Enumerating simple cycles has important applications in computational biology, network science, and financial crime analysis. In this work, we focus on parallelising the state-of-the-art simple cycle enumeration algorithms by Johnson and Read-Tarjan along with their applications to temporal graphs. To our knowledge, we are the first ones to parallelise these two algorithms in a fine-grained manner. We are also the first to demonstrate experimentally a linear performance scaling. Such a scaling is made possible by our decomposition of long sequential searches into fine-grained tasks, which are then dynamically scheduled across CPU cores, enabling an optimal load balancing. Furthermore, we show that coarse-grained parallel versions of the Johnson and the Read-Tarjan algorithms that exploit edge- or vertex-level parallelism are not scalable. On a cluster of four multi-core CPUs with 256 physical cores, our fine-grained parallel algorithms are, on average, an order of magnitude faster than their coarse-grained parallel counterparts. The performance gap between the fine-grained and the coarse-grained parallel algorithms widens as we use more CPU cores. When using all 256 CPU cores, our parallel algorithms enumerate temporal cycles, on average, 260x faster than the serial algorithm of Kumar and Calders. Code repository: https://***/IBM/parallel-cycle-enumeration

关键词： Cycle enumeration parallel graph algorithms graph mining

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for maximal matching based on depth first search

引用

parallel algorithms and Applications 1995年第3-4期5卷 161-164页

作者： Datta, Alak K. Sen, Ranjan K. Department of Mathematics Indian Institute of Technology Kharagpur 721302 India Department of Computer Science and Engineering Indian Institute of Technology Kharagpur 721302 India

We present a new parallel algorithm for finding a maximal matching of a graph. The time required by our algorithm is O(TD(n)log n) and the number of processors used is PD(n), where TD(n) and PD(n) are the time and num... 详细信息

We present a new parallel algorithm for finding a maximal matching of a graph. The time required by our algorithm is O(T_D(n)log n) and the number of processors used is P_D(n), where T_D(n) and P_D(n) are the time and number of processors needed for a Depth First Search (DFS) of the graph. © 1995, Taylor & Francis Group, LLC. All rights reserved.

关键词： Depth-first-search Interval graphs Matching parallel graph algorithms Planar graphs Vertex cover

来源：评论

学校读者我要写书评

暂无评论

The Performance Evaluation of the Java Implementation of graph500 11th

The Performance Evaluation of the Java Implementation of Gra...

引用

11th International Conference on parallel Processing and Applied Mathematics (PPAM)

作者： Ryczkowska, Magdalena Nowicki, Marek Bala, Piotr Nicolaus Copernicus Univ Fac Math & Comp Sci Chopina 12-18 PL-87100 Torun Poland Univ Warsaw Interdisciplinary Ctr Math & Computat Modeling Pawinskiego 5a PL-02106 Warsaw Poland

ISBN: (纸本)9783319321523;9783319321516

graph-based computations are used in many applications. Increasing size of analyzed data and its complexity make graph analysis a challenging task. In this paper we present performance evaluation of Java implementation of graph500 benchmark. It has been developed with the help of the PCJ (parallel Computations in Java) library for parallel and distributed computations in Java. PCJ is based on a PGAS (Partitioned Global Address Space) programming paradigm, where all communication details such as threads or network programming are hidden. In this paper, we present Java implementation details of first and second kernel from graph500 benchmark. The results are compared with the existing MPI implementations of graph500 benchmark, showing good scalability of PCJ library.

关键词： High performance computing graph processing PGAS parallel and distributed computation Performance evaluation parallel graph algorithms Java

来源：评论

学校读者我要写书评

暂无评论

AM++: A Generalized Active Message Framework 10

AM++: A Generalized Active Message Framework

引用

19th International Conference on parallel Architectures and Compilation Techniques

作者： Willcock, Jeremiah J. Hoefler, Torsten Edmonds, Nicholas G. Lumsdaine, Andrew Indiana Univ Bloomington IN 47401 USA

ISBN: (纸本)9781450301787

Active messages have proven to be an effective approach for certain communication problems in high performance computing. Many MPI implementations, as well as runtimes for Partitioned Global Address Space languages, use active messages in their low-level transport layers. However, most active message frameworks have low-level programming interfaces that require significant programming effort to use directly in applications and that also prevent optimization opportunities. In this paper we present AM++, a new user-level library for active messages based on generic programming techniques. Our library allows message handlers to be run in an explicit loop that can be optimized and vectorized by the compiler and that can also be executed in parallel on multicore architectures. Runtime optimizations, such as message combining and filtering, are also provided by the library, removing the need to implement that functionality at the application level. Evaluation of AM++ with distributed-memory graph algorithms shows the usability benefits provided by these library features, as well as their performance advantages.

关键词： Active Messages parallel graph algorithms parallel Programming Interfaces

来源：评论

学校读者我要写书评

暂无评论

Batch Updates of Distributed Streaming graphs using Linear Algebra

Batch Updates of Distributed Streaming Graphs using Linear A...

引用

2024 Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC Workshops 2024

作者： Hassani, Elaheh Hussain, Md Taufique Azad, Ariful Indiana University Dept. of Intelligent Systems Engineering BloomingtonIN United States

ISBN: (纸本)9798350355543

We develop a distributed-memory parallel algorithm for performing batch updates on streaming graphs, where vertices and edges are continuously added or removed. Our algorithm leverages distributed sparse matrices as the core data structures, utilizing equivalent sparse matrix operations to execute graph updates. By reducing unnecessary communication among processes and employing shared-memory parallelism, we accelerate updates of distributed graphs. Additionally, we maintain a balanced load in the output matrix by permuting the resultant matrix during the update process. We demonstrate that our streaming update algorithm is at least 25 times faster than alternative linear-algebraic methods and scales linearly up to 4,096 cores (32 nodes) on a Cray EX supercomputer. © 2024 IEEE.

关键词： batch graph updates distributed-memory algorithms parallel computing parallel graph algorithms scalability in graph processing sparse matrices streaming graphs

来源：评论

学校读者我要写书评

暂无评论

SCCMulti: An Improved parallel Strongly Connected Components Algorithm

SCCMulti: An Improved Parallel Strongly Connected Components...

引用

作者： Tomkins, Daniel Smith, Timmie Amato, Nancy M. Rauchwerger, Lawrence Parasol Laboratory Department of Computer Science and Engineering Texas A and M University United States

来源：评论

学校读者我要写书评

暂无评论

TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge graphs

引用

Proceedings of the ACM on Management of Data 2023年第3期1卷 1-27页

作者： Laxman Dhulipala Jakub Łącki Jason Lee Vahab Mirrokni UMD & Google Research Bethesda MD USA Google Research New York NY USA

We introduce TeraHAC, a (1+ε)-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing (1+ε)-approximate HAC, which is a novel combination of the nearest-neighbor chain algorithm and the notion of (1+ε)-approximate HAC. Our approach allows us to partition the graph among multiple machines and make significant progress in computing the clustering within each partition before any communication with other partitions is *** evaluate TeraHAC on a number of real-world and synthetic graphs of up to 8 trillion edges. We show that TeraHAC requires over 100x fewer rounds compared to previously known approaches for computing HAC. It is up to 8.3x faster than SCC, the state-of-the-art distributed algorithm for hierarchical clustering, while achieving 1.16x higher quality. In fact, TeraHAC essentially retains the quality of the celebrated HAC algorithm while significantly improving the running time.

关键词： distributed graph algorithms hierarchical agglomerative clustering parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

IMPROVED parallel ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH

引用

parallel algorithms and Applications 2000年第4期14卷 321-327页

作者： Alak Kumar Datta[a] Ranjan Kumar Sen - Present address: IBM Poughkeepsie USA[b] [a] Department of Computer Science and Technology Bengal Engineering College (DU) Howrah West Bengal India [b] Department of Computer Science Hampton University Hampton VA USA

Computation of maximal matching of a graph based on Depth First Search tree computation was introduced by Datta and Sen (parallel algorithms and Applications,5, 1995, 161-164). They showed that the approach gives efficient parallel algorithms for maximal matching for graphs for which DFS tree can be efficiently computed. They also presented a parallel scheme to compute a maximal matching in O(T(n) log n) time using O(P(n)) number of processors, where T(n) and P(n) are the time and the number of processors required to compute DFS tree of a graph in parallel. We present here, an improved technique to compute maximal matching in parallel based on DFS tree computation. The algorithm takes O(T(n)) time and O(P(n)) processors.

关键词： parallel graph algorithms Depth first search tree Matching parallel graph algorithms Depth first search tree Matching

来源：评论

学校读者我要写书评

暂无评论

Towards scaling community detection on distributed-memory heterogeneous systems

引用

parallel COMPUTING 2022年 111卷

作者： Gawande, Nitin Ghosh, Sayan Halappanavar, Mahantesh Tumeo, Antonino Kalyanaraman, Ananth Pacific Northwest Natl Lab Richland WA 99352 USA Washington State Univ Pullman WA 99164 USA Intel Corp Santa Clara CA USA PNNL Richland WA USA

In most real-world networks, nodes/vertices tend to be organized into tightly-knit modules known as communities or clusters such that nodes within a community are more likely to be connected or related to one another than they are to the rest of the network. Community detection in a network (graph) is aimed at finding a partitioning of the vertices into communities. The goodness of the partitioning is commonly measured using modularity. Maximizing modularity is an NP-complete problem. In 2008, Blondel et al. introduced a multi-phase, multi-iteration heuristic for modularity maximization called the Louvain method. Owing to its speed and ability to yield high quality communities, the Louvain method continues to be one of the most widely used tools for serial community detection. Distributed multi-GPU systems pose significant challenges and opportunities for efficient execution of parallel applications. graph algorithms, in particular, have been known to be harder to parallelize on such platforms, due to irregular memory accesses, low computation to communication ratios, and load balancing problems that are especially hard to address on multi-GPU systems. In this paper, we present our ongoing work on distributed-memory implementation of Louvain method on heterogeneous systems. We build on our prior work parallelizing the Louvain method for community detection on traditional CPU-only distributed systems without GPUs. Corroborated by an extensive set of experiments on multi-GPU systems, we demonstrate competitive performance to existing distributed-memory CPU-based implementation, up to 3.2x speedup using 16 nodes of OLCF Summit relative to two nodes, and up to 19x speedup relative to the NVIDIA RAPIDS (R) CUgraph (R) implementation on a single NVIDIA V100 GPU from DGX-2 platform, while achieving high quality solutions comparable to the original Louvain method. To the best of our knowledge, this work represents the first effort for community detection on distributed mult

关键词： Distributed community detection Heterogeneous systems Multi-GPU parallel Louvain parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：