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

26th ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC)

作者： Besta, Maciej Podstawski, Michal Groner, Linus Solomonik, Edgar Hoefler, Torsten Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Perform Grp Katowice Katowice Poland Katowice Inst Informat Technol Katowice Poland Univ Illinois Dept Comp Sci Champaign IL USA

ISBN: (纸本)9781450346993

We reduce the cost of communication and synchronization in graph processing by analyzing the fastest way to process graphs: pushing the updates to a shared state or pulling the updates to a private state. We investigate the applicability of this push-pull dichotomy to various algorithms and its impact on complexity, performance, and the amount of used locks, atomics, and reads/writes. We consider 11 graph algorithms, 3 programming models, 2 graph abstractions, and various families of graphs. The conducted analysis illustrates surprising differences between push and pull variants of different algorithms in performance, speed of convergence, and code complexity;the insights are backed up by performance data from hardware counters. We use these findings to illustrate which variant is faster for each algorithm and to develop generic strategies that enable even higher speedups. Our insights can be used to accelerate graph processing engines or libraries on both massively-parallel shared-memory machines as well as distributed-memory systems. Site: haps://***/Research/Parallel _Programming/PushPull

关键词： graph computations

来源：评论

学校读者我要写书评

暂无评论

Parallelizing Sequential graph computations

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2018年第4期43卷 18-18页

作者： Fan, Wenfei Yu, Wenyuan Xu, Jingbo Zhou, Jingren Luo, Xiaojian Yin, Qiang Lu, Ping Cao, Yang Xu, Ruiqi Univ Edinburgh 10 Crichton St Edinburgh EH8 9AB Midlothian Scotland Beihang Univ 37 Xue Yuan Rd Beijing 100191 Peoples R China Shenzhen Inst Comp Sci Shenzhen Peoples R China Alibaba Grp 969 West Wen Yi Rd Hangzhou 311121 Zhejiang Peoples R China Beihang Univ BDBC 37 Xue Yuan Rd Beijing 100191 Peoples R China

This article presents GRAPE, a parallel (graph) under bar (E) under bar ngine for graph computations. GRAPE differs from prior systems in its ability to parallelize existing sequential graph algorithms as a whole, without the need for recasting the entire algorithm into a new model. Underlying GRAPE are a simple programming model and a principled approach based on fixpoint computation that starts with partial evaluation and uses an incremental function as the intermediate consequence operator. We show that users can devise existing sequential graph algorithms with minor additions, and GRAPE parallelizes the computation. Under a monotonic condition, the GRAPE parallelization guarantees to converge at correct answers as long as the sequential algorithms are correct. Moreover, we show that algorithms in MapReduce, BSP, and PRAM can be optimally simulated on GRAPE. In addition to the ease of programming, we experimentally verify that GRAPE achieves comparable performance to the state-of-the-art graph systems using real-life and synthetic graphs.

关键词： graph computations parallel graph query engines parallelizing sequential algorithms convergence simulation

来源：评论

学校读者我要写书评

暂无评论

PARALLEL NESTED DISSECTION FOR PATH ALGEBRA computations

引用

OPERATIONS RESEARCH LETTERS 1986年第4期5卷 177-184页

作者： PAN, V REIF, J HARVARD UNIV AIKEN COMPUTAT LABCAMBRIDGEMA 02138

This paper extends the authors' parallel nested dissection algorithm of [13] originally devised for solving sparse linear systems. We present a class of new applications of the nested dissection method, this time to path algebra computations (in both cases of single source and all pair paths), where the path algebra problem is defined by a symmetric matrix A whose associated graph G with n vertices is planar. We substantially improve the known algorithms for path algebra problems of that general class; this has further applications to maximum flow and minimum cut problems in an undirected planar network and to the feasibility testing of a multicommodity flow in a planar network.

关键词： graph computations path algebras parallel algorithms network flow

来源：评论

学校读者我要写书评

暂无评论

Response to "Scale Up or Scale Out for graph Processing"

引用

IEEE INTERNET COMPUTING 2018年第5期22卷 18-24页

作者： Salihoglu, Semih Ozsu, M. Tamer Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada

In this article, the authors provide their views on whether organizations should scale up or scale out their graph computations. This question was explored in a previous installment of this column by Jimmy Lin, where ... 详细信息

关键词： graph Theory Mathematics Computing graph computations graph Processing Internet Distributed Computing Random Access Memory Multicore Processing graphics Internet graph Analytics Multicore Distributed Software RAM Distributed Cluster

来源：评论

学校读者我要写书评

暂无评论

From "Think Like a Vertex" to "Think Like a graph"

引用

PROCEEDINGS OF THE VLDB ENDOWMENT 2013年第3期7卷 193-204页

作者： Tian, Yuanyuan Balmin, Andrey Corsten, Severin Andreas Tatikonda, Shirish McPherson, John IBM Almaden Res Ctr Yorktown Hts NY 10598 USA GraphSQL Redwood City CA 94065 USA IBM Deutschland GmbH Berlin Germany

To meet the challenge of processing rapidly growing graph and network data created by modern applications, a number of distributed graph processing systems have emerged, such as Pregel and graphLab. All these systems divide input graphs into partitions, and employ a "think like a vertex" programming model to support iterative graph computation. This vertex-centric model is easy to program and has been proved useful for many graph algorithms. However, this model hides the partitioning information from the users, thus prevents many algorithm-specific optimizations. This often results in longer execution time due to excessive network messages (e.g. in Pregel) or heavy scheduling overhead to ensure data consistency (e.g. in graphLab). To address this limitation, we propose a new "think like a graph" programming paradigm. Under this graph-centric model, the partition structure is opened up to the users, and can be utilized so that communication within a partition can bypass the heavy message passing or scheduling machinery. We implemented this model in a new system, called Giraph++, based on Apache Giraph, an open source implementation of Pregel. We explore the applicability of the graph-centric model to three categories of graph algorithms, and demonstrate its flexibility and superior performance, especially on well-partitioned data. For example, on a web graph with 118 million vertices and 855 million edges, the graph-centric version of connected component detection algorithm runs 63X faster and uses 204X fewer network messages than its vertex- centric counterpart.

关键词： graph theory Iterative methods Machinery Message passing Open source software Open systems Scheduling Connected component graph algorithms graph computations Modern applications Open source implementation Partition structures Programming models Programming paradigms

来源：评论

学校读者我要写书评

暂无评论

High-performance graph Analytics on Manycore Processors 29

High-performance Graph Analytics on Manycore Processors

引用

29th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Slota, George M. Rajamanickam, Sivasankaran Madduri, Kamesh Penn State Univ Comp Sci & Engn University Pk PA 16802 USA Sandia Natl Labs Scalable Algorithms Dept Albuquerque NM 87185 USA

ISBN: (纸本)9781479986484

The divergence in the computer architecture landscape has resulted in different architectures being considered mainstream at the same time. For application and algorithm developers, a dilemma arises when one must focus on using underlying architectural features to extract the best performance on each of these architectures, while writing portable code at the same time. We focus on this problem with graph analytics as our target application domain. In this paper, we present an abstraction-based methodology for performance-portable graph algorithm design on manycore architectures. We demonstrate our approach by systematically optimizing algorithms for the problems of breadth-first search, color propagation, and strongly connected components. We use Kokkos, a manycore library and programming model, for prototyping our algorithms. Our portable implementation of the strongly connected components algorithm on the NVIDIA Tesla K40M is up to 3.25x faster than a state-of-the-art parallel CPU implementation on a dual-socket Sandy Bridge compute node.

关键词： graph computations BFS color propagation GPU parallel performance portability

来源：评论

学校读者我要写书评

暂无评论

Performance Portability of an SpMV Kernel Across Scientific Computing and Data Science Applications

Performance Portability of an SpMV Kernel Across Scientific ...

引用

IEEE High Performance Extreme Computing Conference (HPEC)

作者： Olivier, Stephen L. Ellingwood, Nathan D. Berry, Jonathan Dunlavy, Daniel M. Sandia Natl Labs POB 5800 Albuquerque NM 87185 USA

ISBN: (纸本)9781665423694

Both the data science and scientific computing communities are embracing GPU acceleration for their most demanding workloads. For scientific computing applications, the massive volume of code and diversity of hardware platforms at supercomputing centers has motivated a strong effort toward performance portability. This property of a program, denoting its ability to perform well on multiple architectures and varied datasets, is heavily dependent on the choice of parallel programming model and which features of the programming model are used. In this paper, we evaluate performance portability in the context of a data science workload in contrast to a scientific computing workload, evaluating the same sparse matrix kernel on both. Among our implementations of the kernel in different performance-portable programming models, we find that many struggle to consistently achieve performance improvements using the GPU compared to simple one-line OpenMP parallelization on high-end multicore CPUs. We show one that does, and its performance approaches and sometimes even matches that of vendor-provided GPU math libraries.

关键词： performance portability SpMV sparse matrix operations graph computations

来源：评论

学校读者我要写书评

暂无评论

Trigram-based algorithms for OCR result correction 9

Trigram-based algorithms for OCR result correction

引用

9th International Conference on Machine Vision (ICMV)

作者： Bulatov, Konstantin Manzhikov, Temudzhin Slavin, Oleg Faradjev, Igor Janiszewski, Igor Russian Acad Sci Fed Res Ctr Comp Sci & Control Inst Syst Anal Moscow Russia Moscow Inst Phys & Technol Moscow Russia

ISBN: (纸本)9781510611320

In this paper we consider a task of improving optical character recognition (OCR) results of document fields on low-quality and average-quality images using N-gram models. Cyrillic fields of Russian Federation internal passport are analyzed as an example. Two approaches are presented: the first one is based on hypothesis of dependence of a symbol from two adjacent symbols and the second is based on calculation of marginal distributions and Bayesian networks computation. A comparison of the algorithms and experimental results within a real document OCR system are presented, it's showed that the document field OCR accuracy can be improved by more than 6% for low-quality images.

关键词： OCR N-gram trigram trigram weight marginal distribution graph computations

来源：评论

学校读者我要写书评

暂无评论

Towards a Science of Parallel Programming 10

Towards a Science of Parallel Programming

引用

19th International Conference on Parallel Architectures and Compilation Techniques

作者： Pingali, Keshav Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

How do we give parallel programming a more scientific foundation? In this talk, I will discuss the approach we are taking in the Galois project.

ISBN: (纸本)9781450301787

How do we give parallel programming a more scientific foundation? In this talk, I will discuss the approach we are taking in the Galois project.

关键词： Irregular algorithms graph computations Operator Formulation of Algorithms Amorphous Data-parallelism Optimistic Parallelization Multicore processors

来源：评论

学校读者我要写书评

暂无评论

Adaptive Asynchronous Parallelization of graph Algorithms 18

Adaptive Asynchronous Parallelization of Graph Algorithms

引用

44th ACM SIGMOD International Conference on Management of Data

作者： Fan, Wenfei Lu, Ping Luo, Xiaojian Xu, Jingbo Yin, Qiang Yu, Wenyuan Xu, Ruiqi Univ Edinburgh Edinburgh Midlothian Scotland Beihang Univ BDBC Beijing Peoples R China 7 Bridges Ltd Cambridge MA 02129 USA

ISBN: (纸本)9781450317436

This paper proposes an Adaptive Asynchronous Parallel (AAP) model for graph computations. As opposed to Bulk Synchronous Parallel (BSP) and Asynchronous Parallel (AP) models, AAP reduces both stragglers and stale computations by dynamically adjusting relative progress of workers. We show that BSP, AP and Stale Synchronous Parallel model (SSP) are special cases of AAP. Better yet, AAP optimizes parallel processing by adaptively switching among these models at different stages of a single execution. Moreover, employing the programming model of GRAPE, AAP aims to parallelize existing sequential algorithms based on fixpoint computation with partial and incremental evaluation. Under a monotone condition, AAP guarantees to converge at correct answers if the sequential algorithms are correct. Furthermore, we show that AAP can optimally simulate MapReduce, PRAM, BSP, AP and SSP. Using real-life and synthetic graphs, we experimentally verify that AAP outperforms BSP, AP and SSP for a variety of graph computations.

关键词： parallel model parallelization graph computations Church-Rosser

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：