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

Distributed graph Diameter Approximation

algorithms 2020年第9期13卷 216页

作者： Ceccarello, Matteo Pietracaprina, Andrea Pucci, Geppino Upfal, Eli Free Univ Bozen Fac Comp Sci I-39100 Bolzano Italy Univ Padua Dept Informat Engn I-35131 Padua Italy Brown Univ Dept Comp Sci Providence RI 02912 USA

We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into disjoint clusters of bounded radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee;most importantly, for a large family of graphs, it features a round complexity asymptotically smaller than the one exhibited by a natural approximation algorithm based on the state-of-the-art Delta-stepping SSSP algorithm, which is its only practical, linear-space competitor in the distributed setting. We complement our theoretical findings with a proof-of-concept experimental analysis on large benchmark graphs, which suggests that our algorithm may attain substantial improvements in terms of running time compared to the aforementioned competitor, while featuring, in practice, a similar approximation ratio.

关键词： graph analytics parallel graph algorithms weighted graph decomposition weighted diameter approximation MapReduce

来源：评论

学校读者我要写书评

暂无评论

A Brief Survey of algorithms, Architectures, and Challenges toward Extreme-scale graph Analytics 22

A Brief Survey of Algorithms, Architectures, and Challenges ...

引用

22nd Design, Automation and Test in Europe Conference and Exhibition (DATE)

作者： Kalyanaraman, Ananth Pande, Partha Pratim Washington State Univ Sch EECS Pullman WA 99164 USA

ISBN: (纸本)9783981926323

The notion of networks is inherent in the structure, function and behavior of the natural and engineered world that surround us. Consequently, graph models and methods have assumed a prominent role to play in this modern era of Big Data, and are taking a center stage in the discovery pipelines of various data-driven scientific domains. In this paper, we present a brief review of the state-of-the-art in parallel graph analytics, particularly focusing on iterative graph algorithms and their implementation on modern day multicore/manycore architectures. The class of iterative graph algorithms covers a broad class of graph operations of varying complexities, from simpler routines such as Breadth-First Search (BFS), to polynomially-solvable problems such as shortest path computations, to NP-Hard problems such as community detection and graph coloring. We cover a set of common algorithmic abstractions used in implementing such iterative graph algorithms, state the challenges around parallelization on contemporary parallel platforms (including commodity multicores and emerging manycore platforms), and describe a set of approaches that have led to efficient implementations. We also report on advances in manycore architectural frameworks that have found application in parallel graph analytics. We conclude the paper identifying potential research directions, opportunities, and challenges that lay ahead in the path toward enabling graph analytics at exascale.

关键词： parallel graph algorithms parallel architectures irregular applications extreme-scale computing

来源：评论

学校读者我要写书评

暂无评论

Low-Latency graph Streaming using Compressed Purely-Functional Trees 2019

Low-Latency Graph Streaming using Compressed Purely-Function...

引用

40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) part of ACM's Federated Computing Research Conference (FCRC)

作者： Dhulipala, Laxman Blelloch, Guy E. Shun, Julian Carnegie Mellon Univ Pittsburgh PA 15213 USA MIT CSAIL Cambridge MA 02139 USA

ISBN: (纸本)9781450367127

There has been a growing interest in the graph-streaming setting where a continuous stream of graph updates is mixed with graph queries. In principle, purely-functional trees are an ideal fit for this setting as they enable safe parallelism, lightweight snapshots, and strict serializability for queries. However, directly using them for graph processing leads to significant space overhead and poor cache locality. This paper presents C-trees, a compressed purely-functional search tree data structure that significantly improves on the space usage and locality of purely-functional trees. We design theoretically-efficient and practical algorithms for performing batch updates to C-trees, and also show that we can store massive dynamic real-world graphs using only a few bytes per edge, thereby achieving space usage close to that of the best static graph processing frameworks. To study the applicability of our data structure, we designed Aspen, a graph-streaming framework that extends the interface of Ligra with operations for updating graphs. We show that Aspen is faster than two state-of-the-art graph-streaming systems, Stinger and LLAMA, while requiring less memory, and is competitive in performance with the state-of-the-art static graph frameworks, Galois, GAP, and Ligra+. With Aspen, we are able to efficiently process the largest publicly-available graph with over two hundred billion edges in the graph-streaming setting using a single commodity multicore server with 1TB of memory.

关键词： streaming graph processing purely-functional data structures parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Substream-Centric Maximum Matchings on FPGA 19

Substream-Centric Maximum Matchings on FPGA

引用

ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA)

作者： Besta, Maciej Fischer, Marc Ben-Nun, Tal Licht, Johannes De Fine Hoefler, Torsten Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

ISBN: (纸本)9781450361378

Developing high-performance and energy-efficient algorithms for maximum matchings is becoming increasingly important in social network analysis, computational sciences, scheduling, and others. In this work, we propose the first maximum matching algorithm designed for FPGAs;it is energy-efficient and has provable guarantees on accuracy, performance, and storage utilization. To achieve this, we forego popular graph processing paradigms, such as vertex-centric programming, that often entail large communication costs. Instead, we propose a substream-centric approach, in which the input stream of data is divided into substreams processed independently to enable more parallelism while lowering communication costs. We base our work on the theory of streaming graph algorithms and analyze 14 models and 28 algorithms. We use this analysis to provide theoretical underpinning that matches the physical constraints of FPGA platforms. Our algorithm delivers high performance (more than 4x speedup over tuned parallel CPU variants), low memory, high accuracy, and effective usage of FPGA resources. The substream-centric approach could easily be extended to other algorithms to offer low-power and high-performance graph processing on FPGAs.

关键词： matching graph streaming parallel graph algorithms maximum matching fpga

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Optimizing graph algorithms in Asymmetric Multicore Processors

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2018年第11期37卷 2673-2684页

作者： Krishna, Jyothi V. S. Nasre, Rupesh Indian Inst Technol Madras Dept Comp Sci & Engn Madras 600036 Tamil Nadu India

Asymmetric multicore processors (AMP) fall under a special subcategory of modern-day heterogeneous multicore architectures with different participating core types executing a common instruction set architecture. The innate asymmetry in the performance of different cores in AMPs poses interesting challenges. Irregular workloads, such as graph algorithms, intensify these challenges as the parallel workloads in these algorithms cannot be precisely characterized at compile time. In this paper, we propose a framework named scheduler for irregular AMPs, which optimizes the efficiency of the given AMP system for a given algorithm-graph pair by optimizing the graph representation and using a predictor to find the optimal configurations to run the algorithm-graph pair. The optimization is performed in two stages: 1) finding an optimal graph representation and 2) finding an optimal hardware configuration to run the input algorithm-graph pair. We have tested the efficiency of our system on five different graph algorithms over eight real-world and synthetic graphs. On an average, we see 42.82% improvement in energy delay product over the base case.

关键词： Asymmetric multicore processors (AMP) parallel graph algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

parallel Algorithm for Incremental Betweenness Centrality on Large graphs

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2018年第3期29卷 659-672页

作者： Jamour, Fuad Skiadopoulos, Spiros Kalnis, Panos KAUST Thuwal 23955 Saudi Arabia Univ Peloponnese Tripoli 22100 Greece

Betweenness centrality quantifies the importance of nodes in a graph in many applications, including network analysis, community detection and identification of influential users. Typically, graphs in such applications evolve over time. Thus, the computation of betweenness centrality should be performed incrementally. This is challenging because updating even a single edge may trigger the computation of all-pairs shortest paths in the entire graph. Existing approaches cannot scale to large graphs: they either require excessive memory (i.e., quadratic to the size of the input graph) or perform unnecessary computations rendering them prohibitively slow. We propose iCENTRAL;a novel incremental algorithm for computing betweenness centrality in evolving graphs. We decompose the graph into biconnected components and prove that processing can be localized within the affected components. iCENTRAL is the first algorithm to support incremental betweeness centrality computation within a graph component. This is done efficiently, in linear space;consequently, iCENTRAL scales to large graphs. We demonstrate with real datasets that the serial implementation of iCENTRAL is up to 3.7 times faster than existing serial methods. Our parallel implementation that scales to large graphs, is an order of magnitude faster than the state-of-the-art parallel algorithm, while using an order of magnitude less computational resources.

关键词： Betweenness centrality dynamic graph algorithms parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Log(graph): A Near-Optimal High-Performance graph Representation 18

Log(Graph): A Near-Optimal High-Performance Graph Representa...

引用

27th IEEE/ACM/IFIP International Conference on parallel Architectures and Compilation Techniques (PACT)

作者： Besta, Maciej Stanojevic, Dimitri Zivic, Tijana Singh, Jagpreet Hoerold, Maurice Hoefler, Torsten Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

ISBN: (纸本)9781450359863

Today's graphs used in domains such as machine learning or social network analysis may contain hundreds of billions of edges. Yet, they are not necessarily stored efficiently, and standard graph representations such as adjacency lists waste a significant number of bits while graph compression schemes such as Webgraph often require time-consuming decompression. To address this, we propose Log(graph): a graph representation that combines high compression ratios with very low-overhead decompression to enable cheaper and faster graph processing. The key idea is to encode a graph so that the parts of the representation approach or match the respective storage lower bounds. We call our approach "graph logarithmization" because these bounds are usually logarithmic. Our high-performance Log(graph) implementation based on modern bitwise operations and state-of-the-art succinct data structures achieves high compression ratios as well as performance. For example, compared to the tuned graph Algorithm Processing Benchmark Suite (GAPBS), it reduces graph sizes by 20-35% while matching GAPBS' performance or even delivering speedups due to reducing amounts of transferred data. It approaches the compression ratio of the established Webgraph compression library while enabling speedups of up to more than 2x. Log(graph) can improve the design of various graph processing engines or libraries on single NUMA nodes as well as distributed-memory systems.

关键词： graph compression graph representation graph layout parallel graph algorithms ILP succinct data structures

来源：评论

学校读者我要写书评

暂无评论

An Empirical Comparison of k-Shortest Simple Path algorithms on Multicores 18

An Empirical Comparison of <i>k</i>-Shortest Simple Path Alg...

引用

47th International Conference on parallel Processing (ICPP)

作者： Ajwani, Deepak Duriakova, Erika Hurley, Neil Meyer, Ulrich Schickedanz, Alexander Nokia Bell Labs Dublin Ireland Univ Coll Dublin Sch Comp Sci Insight Ctr Data Analyt Dublin Ireland Goethe Univ Frankfurt Germany

ISBN: (纸本)9781450365109

We consider the loop less k-shortest path (KSP) problem. Although this problem has been studied in the sequential setting for at least the last two decades, no good parallel implementations are known. In this paper, we provide (i) a first systematic empirical comparison of various KSP algorithms and heuristic optimisations, (ii) carefully engineer various parallel implementations of these sequential algorithms and (iii) perform an extensive study of these parallel implementations on a range of graph classes and multicore architectures to determine the best algorithm and parallelization strategy for different graph classes. We find that even though the worst-case complexity of the best undirected KSP algorithm O (k (m + n log n)) is significantly better than that of the popular and considerably simpler directed KSP algorithm O(kn(m + n log n)), the two algorithms are fairly competitive in terms of their empirical performance on small diameter graphs. Furthermore, we show that a few simple optimisations help to bridge the gap between these KSP algorithms even more. However, on moderate to large diameter graphs, the undirected KSP algorithm is considerably faster than the directed algorithms, both in sequential and parallel settings. In terms of the parallelisation strategy, simply replacing the shortest path subroutine by parallel A-stepping algorithm can provide a good speed-up for many KSP algorithms on random graphs. In contrast, for graphs with skewed degree distribution, a more complex strategy of parallelizing the different deviations and then parallelizing the shortest path computation inside the deviations with the remaining threads, provides a better performance.

关键词： Algorithm Engineering parallel k-Shortest Path parallel graph algorithms parallel Single Source Shortest Path

来源：评论

学校读者我要写书评

暂无评论

A Shared-Memory Algorithm for Updating Single-Source Shortest Paths in Large Weighted Dynamic Networks 25

A Shared-Memory Algorithm for Updating Single-Source Shortes...

引用

25th IEEE International Conference on High Performance Computing, Data and Analytics (HiPC)

作者： Srinivasan, Sriram Riazi, Sara Norris, Boyana Das, Sajal K. Bhowmick, Sanjukta Univ Nebraska Omaha NE 68106 USA Univ Oregon Eugene OR 97403 USA Missouri Univ Sci & Technol Rolla MO 65409 USA Univ North Texas Denton TX 76203 USA

ISBN: (纸本)9781538683866

Computing the single-source shortest path (SSSP) is one of the fundamental graph algorithms, and is used in many applications. Here, we focus on computing SSSP on large dynamic graphs, i.e. graphs whose structure evolves with time. We posit that instead of recomputing the SSSP for each set of changes on the dynamic graphs, it is more efficient to update the results based only on the region of change. To this end, we present a novel two step shared-memory algorithm for updating SSSP on weighted large-scale graphs. The key idea of our algorithm is to identify changes, such as vertex/edge addition and deletion, that affect the shortest path computations and update only the parts of the graphs affected by the change. We provide the proof of correctness of our proposed algorithm. Our experiments on real and synthetic networks demonstrate that our algorithm is as much as 4X faster compared to computing SSSP with Galois, a state-of-the-art parallel graph analysis software for shared memory architectures. We also demonstrate how increasing the asynchrony can lead to even faster updates. To the best of our knowledge, this is one of the first practical parallel algorithms for updating networks on shared-memory systems, that is also scalable to large networks.

关键词： dynamic networks parallel graph algorithms single-source shortest path

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：