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

27th ACM symposium on parallelism in algorithms and Architectures (SPAA)

作者： Ceccarello, Matteo Pietracaprina, Andrea Pucci, Geppino Upfal, Eli Univ Padua Dept Informat Engn Padua Italy Brown Univ Dept Comp Sci Providence RI 02912 USA

ISBN: (纸本)9781450335881

We develop a novel parallel decomposition strategy for un-weighted, undirected graphs, based on growing disjoint connected clusters from batches of centers progressively selected from yet uncovered nodes. With respect to similar previous decompositions, our strategy exercises a tighter control on both the number of clusters and their maximum radius. We present two important applications of our parallel graph decomposition: (1) k-center clustering approximation;and (2) diameter approximation. In both cases, we obtain algorithms which feature a polylogarithmic approximation factor and are amenable to a distributed implementation that is geared for massive (long-diameter) graphs. The total space needed for the computation is linear in the problem size, and the parallel depth is substantially sublinear in the diameter for graphs with low doubling dimension. To the best of our knowledge, ours are the first parallel approximations for these problems which achieve sub-diameter parallel time, for a relevant class of graphs, using only linear space. Besides the theoretical guarantees, our algorithms allow for a very simple implementation on clustered architectures: we report on extensive experiments which demonstrate their effectiveness and efficiency on large graphs as compared to alternative known approaches.

关键词： parallel graph algorithms graph Decomposition k-Center Problem Diameter Approximation MapReduce

来源：评论

学校读者我要写书评

暂无评论

parallel Batch-Dynamic graph Connectivity 19

Parallel Batch-Dynamic Graph Connectivity

引用

31st ACM Symposium on parallelism in algorithms and Architecturess (SPAA)

作者： Acar, Umut A. Anderson, Daniel Blelloch, Guy E. Dhulipala, Laxman Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450361842

In this paper, we study batch parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in the sequential setting. The best sequential algorithm for dynamic connectivity is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves O(1g(2) n) amortized time per edge insertion or deletion, and O(1g n) time per query. We design a parallel batch-dynamic connectivity algorithm that is work-efficient with respect to the HDT algorithm for small batch sizes, and is asymptotically faster when the average batch size is sufficiently large. Given a sequence of batched updates, where A is the average batch size of all deletions, our algorithm achieves O(1g n lg(1 + n/A)) expected amortized work per edge insertion and deletion and O (1g(3) n) depth w.h.p. Our algorithm answers a batch of k connectivity queries in O(k lg(1 + n/ k)) expected work and O(1g n) depth w.h.p. To the best of our knowledge, our algorithm is the first parallel batch-dynamic algorithm for connectivity.

关键词： parallel graph algorithms graph connectivity dynamic graph algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithm-Level Optimizations for Scalable parallel graph Processing

Algorithm-Level Optimizations for Scalable Parallel Graph Pr...

引用

作者： Harshvardhan Texas A&M University

Efficiently processing large graphs is challenging, since parallel graph algorithms suffer from poor scalability and performance due to many factors, including heavy communication and load-imbalance. Furthermore, it is difficult to express graph algorithms, as users need to understand and effectively utilize the underlying execution of the algorithm on the distributed system. The performance of graph algorithms depends not only on the characteristics of the system (such as latency, available RAM, etc.), but also on the characteristics of the input graph (small-world scalefree, mesh, long-diameter, etc.), and characteristics of the algorithm (sparse computation vs. dense communication). The best execution strategy, therefore, often heavily depends on the combination of input graph, system and algorithm. Fine-grained expression exposes maximum parallelism in the algorithm and allows the user to concentrate on a single vertex, making it easier to express parallel graph algorithms. However, this often loses information about the machine, making it difficult to extract performance and scalability from fine-grained algorithms. To address these issues, we present a model for expressing parallel graph algorithms using a fine-grained expression. Our model decouples the algorithm-writer from the underlying details of the system, graph, and execution and tuning of the algorithm. We also present various graph paradigms that optimize the execution of graph algorithms for various types of input graphs and systems. We show our model is general enough to allow graph algorithms to use the various graph paradigms for the best/fastest execution, and demonstrate good performance and scalability for various different graphs, algorithms, and systems to 100,000+ cores.

关键词： graph Processing Distributed Systems graph algorithms High Performance Computing parallel graph algorithms Scalable graph algorithms Distributed graph Processing Systems Large-scale graph Processing Thesis

来源：评论

学校读者我要写书评

暂无评论

DECENTRALIZED LOW-STRETCH TREES VIA LOW DIAMETER graph DECOMPOSITIONS

引用

SIAM JOURNAL ON COMPUTING 2024年第2期53卷 247-286页

作者： Becker, Ruben Emek, Yuval Ghaffari, Mohsen Lenzen, Christoph CaFoscari Univ Venice I-30123 Venice Italy Technion Israel Inst Technol IL-3200003 Haifa Israel MIT Cambridge MA 02139 USA CISPA Helmholtz Ctr Informat Secur Saarland Informat Campus D-66123 Saarbrucken Germany

We study the problem of approximating the distances in an undirected weighted graph G by the distances in trees based on the notion of stretch. Focusing on decentralized models of computation such as the CONGEST, PRAM, and semi-streaming models, our main results are as follows: (1) We develop a simple randomized algorithm that constructs a spanning tree such that the expected stretch of every edge is O(log(3) n), where n is the number of nodes in G. If G is unweighted, then this algorithm can be implemented to run in O(hop(G)) rounds in the CONGEST model, where hop(G) is the hop-diameter of G;thus our algorithm is asymptotically optimal in this case. In the weighted case, the run-time of the algorithm matches the currently best known bound for exact single source shortest path (SSSP) computations, which despite recent progress is still separated from the lower bound of Omega(root n + hop(G)) by polynomial factors. A naive attempt to replace exact SSSP computations with approximate ones in order to improve the complexity in the weighted case encounters a fundamental challenge, as the underlying decomposition technique fails to work under distance approximation. (2) We overcome this obstacle by developing a technique termed blurry ball growing. This technique, in combination with a clever algorithmic idea of Miller, Peng, and Xu (SPAA 2013), allows us to obtain low diameter graph decompositions with small edge cutting probabilities based solely on approximate SSSP computations. (3) Using these decompositions, we in turn obtain metric tree embedding algorithms in the vein of the celebrated work of Bartal (FOCS 1996), whose computational complexity is optimal up to polylogarithmic factors not only in the CONGEST model but also in the PRAM and semi-streaming models. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is "used" only logarithmically many times. This property is of interest for capaci

关键词： distributed graph algorithms parallel graph algorithms (semi-)streaming graph algorithms metric tree embeddings low-stretch trees graph decompositions

来源：评论

学校读者我要写书评

暂无评论

Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2006年第11期66卷 1366-1378页

作者： Bader, David A. Cong, Guojing Georgia Inst Technol Coll Comp Atlanta GA 30332 USA IBM Corp TJ Watson Res Ctr Yorktown Hts NY 10598 USA

Minimum spanning tree (MST) is one of the most studied combinatorial problems with practical applications in VLSI layout, wireless communication, and distributed networks, recent problems in biology and medicine such as cancer detection, medical imaging, and proteomics, and national security and bioterrorism such as detecting the spread of toxins through populations in the case of biological/chemical warfare. Most of the previous attempts for improving the speed of MST using parallel computing are too complicated to implement or perform well only on special graphs with regular structure. In this paper we design and implement four parallel MST algorithms (three variations of Boruvka plus our new approach) for arbitrary sparse graphs that for the first time give speedup when compared with the best sequential algorithm. In fact, our algorithms also solve the minimum spanning forest problem. We provide an experimental study of our algorithms on symmetric multiprocessors such as IBMs pSeries and Sun's Enterprise servers. Our new implementation achieves good speedups over a wide range of input graphs with regular and irregular structures, including the graphs used by previous parallel MST studies. For example, on an arbitrary random graph with 1M vertices and 20M edges, our new approach achieves a speedup of 5 using 8 processors. The source code for these algorithms is freely available from our web site. (C) 2006 Elsevier Inc. All rights reserved.

关键词： parallel graph algorithms connectivity high-performance algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

BFS-4K: An Efficient Implementation of BFS for Kepler GPU Architectures

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2015年第7期26卷 1826-1838页

作者： Busato, Federico Bombieri, Nicola Univ Verona Dept Comp Sci I-37100 Verona Italy

Breadth-first search (BFS) is one of the most common graph traversal algorithms and the building block for a wide range of graph applications. With the advent of graphics processing units (GPUs), several works have been proposed to accelerate graph algorithms and, in particular, BFS on such many-core architectures. Nevertheless, BFS has proven to be an algorithm for which it is hard to obtain better performance from parallelization. Indeed, the proposed solutions take advantage of the massively parallelism of GPUs but they are often asymptotically less efficient than the fastest CPU implementations. This paper presents BFS-4K, a parallel implementation of BFS for GPUs that exploits the more advanced features of GPU-based platforms (i.e., NVIDIA Kepler) and that achieves an asymptotically optimal work complexity. The paper presents different strategies implemented in BFS-4K to deal with the potential workload imbalance and thread divergence caused by any actual graph non-homogeneity. The paper presents the experimental results conducted on several graphs of different size and characteristics to understand how the proposed techniques are applied and combined to obtain the best performance from the parallel BFS visits. Finally, an analysis of the most representative BFS implementations for GPUs at the state of the art and their comparison with BFS-4K are reported to underline the efficiency of the proposed solution.

关键词： parallel graph algorithms CUDA GPU BFS Kepler

来源：评论

学校读者我要写书评

暂无评论

Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components

引用

FORMAL METHODS IN SYSTEM DESIGN 2016年第3期48卷 274-300页

作者： Wijs, Anton Katoen, Joost-Pieter Bosnacki, Dragan Eindhoven Univ Technol Eindhoven Netherlands Rhein Westfal TH Aachen Aachen Germany

This article presents parallel algorithms for component decomposition of graph structures on general purpose graphics processing units (GPUs). In particular, we consider the problem of decomposing sparse graphs into strongly connected components, and decomposing graphs induced by stochastic games (such as Markov decision processes) into maximal end components. These problems are key ingredients of many (probabilistic) model-checking algorithms. We explain the main rationales behind our GPU-algorithms, and show a significant speed-up over the sequential (as well as existing parallel) counterparts in several case studies.

关键词： parallel graph algorithms Strongly connected components Maximal end components Probabilistic model checking Markov decision processes GPU

来源：评论

学校读者我要写书评

暂无评论

FINDING LOWEST COMMON ANCESTORS IN parallel

引用

IEEE TRANSACTIONS ON COMPUTERS 1986年第8期35卷 764-769页

作者： TSIN, YH MEM UNIV NEWFOUNDLAND DEPT COMP SCIST JOHNS A1C 5S7NEWFOUNDLANDCANADA

Two parallel algorithms for finding the lowest common ancestors of a set of vertex pairs Q (the query set) in a directed tree are presented. With all the overheads taken into account, these algorithms take O((n + QI) P log2 n) and O(n2/p + log2n) time, respectively, with p(> 0) processors (n is the size of the tree). These results are better than the best known result in that the first achieves the O(log2 n) time bound with only n + |Q| processors while the second reduces the number of processors used by a factor of log2 n which is optimal for large query sets when 0 < p ≤ n2/log2 n. The computer model we use here is the PRAM which is an SIMD model allowing read but not write conflicts. Our results also imply the following improvements: the processor bound for finding a set of fundamental cycles in an undirected graph is improved by a factor of log2 n and the result is optimal for dense graphs; the implementations of some other sequential and parallel algorithms are also simplified.

关键词： Design and analysis of algorithms PRAM SIMD models fundamental cycles lowest common ancestors parallel computation parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Portable and efficient parallel computing using the BSP model

引用

IEEE TRANSACTIONS ON COMPUTERS 1999年第7期48卷 670-689页

作者： Goudreau, MW Lang, K Rao, SB Suel, T Tsantilas, T NEC US C&C Res Labs Princeton NJ 08540 USA Polytech Univ Brooklyn NY 11201 USA Bear Stearns & Co New York NY 10167 USA

The Bulk-Synchronous parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory. the BSP model has been shown to allow the asymptotically optimal execution of architecture-independent software on a variety of architectures. Our goal in this work is to experimentally examine the practical use of the BSP model on current parallel architectures. We describe the design and implementation of the Green BSP Library, a small library of functions that implement the BSP model, and of several applications that were written for this library. We then discuss the performance of the library and application programs on several parallel architectures. Our results are positive in that we demonstrate efficiency and portability over a range of parallel architectures and show that the BSP cost model is useful for predicting performance trends and estimating execution times.

关键词： BSP minimum spanning tree problem models of parallel computation N-body problem parallel computing parallel graph algorithms shortest path problem

来源：评论

学校读者我要写书评

暂无评论

graph coloring algorithms for multi-core and massively multithreaded architectures

引用

parallel COMPUTING 2012年第10-11期38卷 576-594页

作者： Catalyuerek, Uemit V. Feo, John Gebremedhin, Assefaw H. Halappanavar, Mahantesh Pothen, Alex Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA Pacific NW Natl Lab Richland WA 99352 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA

We explore the interplay between architectures and algorithm design in the context of shared-memory platforms and a specific graph problem of central importance in scientific and high-performance computing, distance-1 graph coloring. We introduce two different kinds of multithreaded heuristic algorithms for the stated. NP-hard, problem. The first algorithm relies on speculation and iteration, and is suitable for any shared-memory system. The second algorithm uses dataflow principles, and is targeted at the non-conventional, massively multithreaded Cray XMT system. We study the performance of the algorithms on the Cray XMT and two multi-core systems, Sun Niagara 2 and Intel Nehalem. Together, the three systems represent a spectrum of multithreading capabilities and memory structure. As testbed, we use synthetically generated large-scale graphs carefully chosen to cover a wide range of input types. The results show that the algorithms have scalable runtime performance and use nearly the same number of colors as the underlying serial algorithm, which in turn is effective in practice. The study provides insight into the design of high performance algorithms for irregular problems on many-core architectures. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Multi-core/multithreaded computing parallel graph algorithms Combinatorial scientific computing graph coloring

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：