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

IncPregeh an incremental graph parallel computation model

Frontiers of Computer Science 2018年第6期12卷 1076-1089页

作者： Qiang LIU Xiaoshe DONG Heng CHEN Yinfeng WANG School of Electronics and Information Engineering Xi'an Jiaotong UniversityXi'an 710049China Shenzhen Institute of Information Technology Shenzhen 518172China

Large-scale graph computation is often required in a variety of emerging applications such as social network computation and Web services. Such graphs are typically large and frequently updated with minor changes. However, re-computing an entire graph when a few vertices or edges are updated is often prohibitively expensive. To reduce the cost of such updates, this study proposes an incremental graph computation model called IncPregel, which leverages the non-after-effect property of the first-order Markov chain and provides incremental programming abstractions to avoid redundant computation and message communication. This is accomplished by employing an efficient and fine-grained reuse mechanism. We implemented this model on Hama, a popular open source framework based on Pregel, to construct an incremental graph processing system called IncHama. IncHama automatically detects changes in input in order to recognize “changed vertices” and to exchange reusable data by means of shuffling. The evaluation results on large-scale graphs show that, compared with Hama, IncHama is 1.1–2.7 times faster and can reduce communication messages by more than 50% when the incremental edges increase in number from 0.1 to 100k.

关键词： graph computation Pregel cloud computing

来源：评论

学校读者我要写书评

暂无评论

VENUS: A System for Streamlined graph computation on a Single PC

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2016年第8期28卷 2230-2245页

作者： Liu, Qin Cheng, Jiefeng Li, Zhenguo Lui, John C. S. Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China Huawei Noahs Ark Lab Hong Kong Hong Kong Peoples R China

Recent studies show that disk-based graph computation systems on just a single PC can be as highly competitive as cluster-based systems on large-scale problems. Inspired by this remarkable progress, we develop VENUS, a disk-based graph computation system which is able to handle billion-scale graphs efficiently on a commodity PC. VENUS adopts a novel computing architecture that features vertex-centric "streamlined" processing-the graph is sequentially loaded and an update function is executed for each vertex in parallel on the fly. VENUS deliberately avoids loading batch edge data by separating read-only structure data from mutable vertex data on disk, and minimizes random IOs by caching vertex data in the main memory whenever possible. The streamlined processing is realized with efficient sequential scan over massive structure data and fast feeding the update function for a large number of vertices. Extensive evaluation on large real-world and synthetic graphs has demonstrated the efficiency of VENUS. For example, to run the PageRank algorithm on a Twitter graph of 42 million vertices and 1.4 billion edges, Spark needs 8.1 minutes with 50 machines and graphChi spends 13 minutes using high-speed SSD, while VENUS only takes 5 minutes on one machine with an ordinary hard disk.

关键词： graph computation disk-based computing vertex-centric streamlined processing

来源：评论

学校读者我要写书评

暂无评论

An Efficient Framework for Incremental graph computation 15

An Efficient Framework for Incremental Graph Computation

引用

15th IEEE Int Conf on Trust, Security and Privacy in Comp and Commun / 10th IEEE Int Conf on Big Data Science and Engineering / 14th IEEE Int Symposium on Parallel and Distributed Proc with Applicat (IEEE Trustcom/BigDataSE/ISPA)

作者： Liu, Qiang Dong, XiaoShe Chen, Heng Zhu, Zheng Dong Wang, Yinfeng Xi An Jiao Tong Univ Sch Elect & Informat Engn Xian 710049 Peoples R China Shenzhen Inst Informat Technol Shenzhen 518172 Peoples R China

ISBN: (纸本)9781509032051

graph computation has become increasingly popular in emerging applications such as social networks and web graphs. In practice, graph is typically large and frequently updated with small changes. However, traditional graph processing systems process the evolving graph in a batch manner. To accelerate these large-scale graph applications, this paper proposes an efficient message reuse framework for incremental graph computation, called IncTracker. IncTracker automatically detects the input data changes and only processes the "changed" vertices by employing an efficient, fine-grained reuse mechanism. By reusing the intermediate messages and results of previous runs, the proposed framework can efficiently avoid redundant message communication in iterations. We compare the framework with Pregel on several SNAP datasets. The results show that the speedup ranges from 1.10x to 2.26x and the network traffic is significantly reduced when the incremental changes from 0% to 20%.

关键词： graph computation incremental computation message reuse

来源：评论

学校读者我要写书评

暂无评论

PAGE: A Partition Aware Engine for Parallel graph computation

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2015年第2期27卷 518-530页

作者： Shao, Yingxia Cui, Bin Ma, Lin Peking Univ Sch EECS Key Lab High Confidence Software Technol MOE Beijing Peoples R China

graph partition quality affects the overall performance of parallel graph computation systems. The quality of a graph partition is measured by the balance factor and edge cut ratio. A balanced graph partition with small edge cut ratio is generally preferred since it reduces the expensive network communication cost. However, according to an empirical study on Giraph, the performance over well partitioned graph might be even two times worse than simple random partitions. This is because these systems only optimize for the simple partition strategies and cannot efficiently handle the increasing workload of local message processing when a high quality graph partition is used. In this paper, we propose a novel partition aware graph computation engine named PAGE, which equips a new message processor and a dynamic concurrency control model. The new message processor concurrently processes local and remote messages in a unified way. The dynamic model adaptively adjusts the concurrency of the processor based on the online statistics. The experimental evaluation demonstrates the superiority of PAGE over the graph partitions with various qualities.

关键词： graph computation graph partition message processing

来源：评论

学校读者我要写书评

暂无评论

Locality-Aware Vertex Scheduling for GPU-based graph computation 23

Locality-Aware Vertex Scheduling for GPU-based Graph Computa...

引用

23rd IFIP WG 10.5/IEEE International Conference on Very Large Scale Integration (VLSI-SoC)

作者： Park, Hyunsun Ahn, Junwhan Park, Eunhyeok Yoo, Sungjoo Pohang Univ Sci & Technol POSTECH Dept Elect Engn Pohang South Korea Seoul Natl Univ Dept Elect & Comp Engn Seoul 151 South Korea Seoul Natl Univ Dept Comp Sci & Engn Seoul 151 South Korea

ISBN: (纸本)9781467391405

graph computation is becoming more and more popular in machine learning, big data analytics, etc. For such workloads, GPU is considered as an efficient execution platform since graph computation is characterized by massively parallel computation and high demand of memory bandwidth. In our investigation, existing GPU programming methods for graph computation do not fully exploit high memory bandwidth as well as high computing power in GPU. We propose a novel optimization called locality-aware vertex scheduling, which aims at minimizing memory requests by adjusting the order of vertex computations to improve temporal locality of vertex data stored in on-chip caches. Experiments with nine real-world graphs and three graph algorithms on the recent GPU platform show that the proposed method offers a significant speedup (average 46%) over the state-of-the-art graph algorithm implementation on GPUs.

关键词： graph computation GPU data locality vertex scheduling

来源：评论

学校读者我要写书评

暂无评论

graphGen: An FPGA Framework for Vertex-Centric graph computation 22

GraphGen: An FPGA Framework for Vertex-Centric Graph Computa...

引用

22nd IEEE Annual International Symposium on Field-Programmable Custom Computing Machines ((FCCM)

作者： Nurvitadhi, Eriko Weisz, Gabriel Wang, Yu Hurkat, Skand Marie Nguyen Hoe, James C. Martinez, Jose F. Guestrin, Carlos Intel Corp Pittsburgh PA 15213 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Cornell Univ Ithaca NY USA Univ Washington Seattle WA 98195 USA

ISBN: (纸本)9781479951116

Vertex-centric graph computations are widely used in many machine learning and data mining applications that operate on graph data structures. This paper presents graphGen, a vertex-centric framework that targets FPGA for hardware acceleration of graph computations. graphGen accepts a vertex-centric graph specification and automatically compiles it onto an application-specific synthesized graph processor and memory system for the target FPGA platform. We report design case studies using graphGen to implement stereo matching and handwriting recognition graph applications on Terasic DE4 and Xilinx ML605 FPGA boards. Results show up to 14.6x and 2.9x speedups over software on Intel Core i7 CPU for the two applications, respectively.

关键词： graph computation design framework case studies

来源：评论

学校读者我要写书评

暂无评论

Fast Single-phase Fault Location Method Based on Community graph Depth-first Traversal for Distribution Network

引用

CSEE Journal of Power and Energy Systems 2023年第2期9卷 612-622页

作者： Jian Dang Yunjiang Yan Rong Jia Xiaowei Wang Hui Wei Xi’an Key Laboratory of Intelligent Energy Xi’an University of TechnologyShaanxi 710048China

With the increasing complexity of distribution network structures originating from the high penetration of renewable energy and responsive loads,fast and accurate fault location technology for distribution networks is a prerequisite for rapid isolation of faults and restoration of the power *** this paper,a fault location method based on community graph depth-first traversal is proposed for fast location of single-phase ground faults in distribution ***,this paper defines the fault graph weight of the vertices in the distribution network graph model,which can be used to reflect the topology of the vertices and fault points as well as the fluctuation of the vertices’***,the vertices on the graph model are clustered by using an improved parallel louvain method(IPLM).Finally,the community formed by IPLM is used as the smallest unit for depth-first traversal to achieve fast and accurate location of the fault *** paper develops a distribution network graph model of IEEE 33-bus system on the graph database for *** three other methods are selected for comparison with *** test results show that IPLMDF can achieve fast and accurate fault location when half of the nodes in the distribution network are equipped with *** some of the D-PMUs lose time synchronization,it is still possible to locate the fault section,and at the same time,the locating results can be avoided by falling into local optimal solutions.

关键词： Depth-first traversal fault location graph computation single-phase fault

来源：评论

学校读者我要写书评

暂无评论

Edge Repartitioning via Structure-Aware Group Migration

引用

IEEE TRANSACTIONS ON computationAL SOCIAL SYSTEMS 2022年第3期9卷 751-760页

作者： Li, He Yuan, Hang Huang, Jianbin Ma, Xiaoke Cui, Jiangtao Yoo, Jaesoo Xidian Univ Sch Comp Sci & Technol Xian 710126 Peoples R China Chungbuk Natl Univ Dept Informat & Commun Engn Cheongju 361763 South Korea

graph partitioning is a mandatory step in distributed graph computing systems. Some existing systems use edge partitioning methods to partition static graphs. However, the structure of the real-world graphs changes dynamically, which leads to unnecessary vertex replicas and load imbalance, reducing the performance of graph computation. In this article, we focus on improving the lower partitioning quality caused by the dynamics of the graph structure. We propose an edge repartitioning algorithm via structure-aware group migration (SAGM-ER). We define a special structure edge group (EG) consisting of multiple edges, which can reduce vertex replicas by migrating to other partitions. In repartitioning, we search for EGs in parallel by a method based on a structure-aware priority and then migrate EGs to reduce vertex replicas. Compared to the state of the art, SAGM-ER can reduce more vertex replicas. We implement SAGM-ER on Powergraph, which reduces the redundant replicas by 63.33%, thus reducing executing time and communication costs in graph computation by 33.72% and 37.51%, respectively.

关键词： Partitioning algorithms Heuristic algorithms Load management Resource management Spread spectrum communication Social networking (online) Real-time systems Dynamic graph edge group (EG) edge repartitioning graph computation structure-aware priority

来源：评论

学校读者我要写书评

暂无评论

Tianhegraph: Customizing graph Search for graph500 on Tianhe Supercomputer

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2022年第4期33卷 941-951页

作者： Gan, Xinbiao Zhang, Yiming Wang, Ruibo Li, Tiejun Xiao, Tiaojie Zeng, Ruigeng Liu, Jie Lu, Kai Natl Univ Def Technol Changsha 410073 Hunan Peoples R China

As the era of exascale supercomputing is coming, it is vital for next-generation supercomputers to find appropriate applications with high social and economic benefit. In recent years, it has been widely accepted that extremely-large graph computation is a promising killer application for supercomputing. Although Tianhe series supercomputers are leading in the world-wide competition of supercomputing (ranked No. 1 in the Top500 list for six times), previously they had been inefficient in graph computation according to the graph500 list. This is mainly because the previous graph processing system cannot leverage the advanced hardware features of Tianhe supercomputers. To address the problem, in this paper we present our integrated optimizations for improving the graph computation performance on our next-generation Tianhe supercomputing system, mainly including sorting with buffering for heavy vertices, vectorized searching with SVE (Scalable Vector Extension) on matrix2000+ CPUs, and group communication on the proprietary interconnection network. Performance evaluation on a subset of the Tianhe supercomputer (with 512 nodes and 196,608 cores) shows that our customized graph processing system effectively improves the graph search performance and achieves the BFS performance of 2131.98 GTEPS.

关键词： Supercomputers Next generation networking Benchmark testing Hardware Multiprocessor interconnection Image edge detection Performance evaluation graph computation exascale supercomputer matrix2000+ group-based communication graph500 BFS

来源：评论

学校读者我要写书评

暂无评论

graph partitioning strategies: one size does not fit all

引用

JOURNAL OF SUPERCOMPUTING 2022年第17期78卷 19272-19295页

作者： Zhai, Xiaomeng Zhang, Hong Huang, Xu Zhang, Shouhua Hebei Univ Sch Cyber Secur & Comp Qiyi East Rd Baoding 071000 Hebei Peoples R China Univ Oulu Informat Technol & Elect Engn Oulu Finland

As an important part of distributed graph computing, graph partitioning has been widely studied. However, the majority of the existing approaches to distributed graph partitioning barely take into consideration the relationship between the partition strategy and the graph algorithm's characteristics. The current graph partitioning strategies are on the basis of the graph structure, and the performance is diverse as running different graph algorithms. In this paper, considering the characteristics of a graph algorithm, we propose a distributed graph partitioning framework that can decide which partitioning strategy is better based on the program analysis. We also design a triangle-based partitioning strategy which benefits several graph algorithms such as the triangle counting. In addition, to reduce the number of shuffling operations in PageRank algorithm, we redesign the PageRank algorithm which considers the corresponding hash partitioning. The experimental results show that our adaptive graph partitioning framework implemented on graphx surpasses the original one, especially for the triangle counting and PageRank, no matter on real-world graphs or synthetic graphs.

关键词： graph partitioning Triangle counting PageRank graph computation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：