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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Study of power supply restoration in distribution networks based on graph computation 6

Study of power supply restoration in distribution networks b...

引用

6th IEEE International Conference on Automation, Electronics and Electrical Engineering, AUTEEE 2023

作者： Yang, Jie Tianjin University of Technology Tianjin China

ISBN: (纸本)9798350305623

In order to solve the troubles caused by the complex and variable topology of distribution networks and the change of load demand on the power supply restoration of distribution networks, the article proposes a correlation analysis method based on graph computation for power supply restoration of distribution networks, which provides a new idea for the operation and maintenance of distribution networks. A graph model of distribution network, which is highly consistent with the topology of distribution network, is constructed, and the power supply restoration strategy is optimized by applying graph computation, and finally verified by simulation in IEEE33 system. The results show that the model can comprehensively utilize the outage area to repeat the primary transfer and secondary transfer to restore the power supply, and at the same time determine the optimal restoration strategy according to the restoration objectives, which can make the power supply reach the restoration effect quickly and efficiently compared with other methods. © 2023 IEEE.

关键词： distribution network graph computation power restoration topology

来源：评论

学校读者我要写书评

暂无评论

Automating Vectorized Distributed graph computation

引用

Proceedings of the ACM on Management of Data 2024年第6期2卷 1-27页

作者： Wenyue Zhao Yang Cao Peter Buneman Jia Li Nikos Ntarmos University of Edinburgh Edinburgh UK Edinburgh Research Center Central Software Institute Huawei Edinburgh UK

Multi-instance graph algorithms interleave the evaluation of multiple instances of the same algorithm with different inputs over the same graph. They have been shown to be significantly faster than traditional serial and batch evaluation, by sharing computation across instances. However, writing correct multi-instance algorithms is challenging; and in this work, we describe AutoMI, a framework for automatically converting vertex-centric graph algorithms into their vectorized multi-instance versions. We also develop an algebraic characterization of algorithms that can benefit best from multi-instance computation with simpler and faster streamlined vectorization. This allows users to decide when to use such optimization and instruct AutoMI to make the best use of SIMD vectorization. Using 6 real-life graphs, we show that AutoMI-converted multi-instance algorithms are 9.6 to 29.5 times faster than serial evaluation, 7.1 to 26.4 times faster than batch evaluation, and are even 2.6 to 4.6 times faster than existing highly optimized handcrafted multi-instance algorithms without vectorization.

关键词： algebraic characterization auto vectorization graph computation simd vectorization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Parallelizing Sequential graph computations 17

Parallelizing Sequential Graph Computations

引用

ACM International Conference on Management of Data

作者： Fan, Wenfei Xu, Jingbo Wu, Yinghui Yu, Wenyuan Jiang, Jiaxin Zheng, Zeyu Zhang, Bohan Cao, Yang Tian, Chao Univ Edinburgh Edinburgh Midlothian Scotland Beihang Univ Beijing Peoples R China Washington State Univ Pullman WA 99164 USA Hong Kong Baptist Univ Kowloon Peoples R China Peking Univ Beijing Peoples R China

ISBN: (纸本)9781450341974

This paper presents GRAPE, a parallel system for graph computations. GRAPE differs from prior systems in its ability to parallelize existing sequential graph algorithms as a whole. Underlying GRAPE are a simple programming model and a principled approach, based on partial evaluation and incremental computation. We show that sequential graph algorithms can be "plugged into" GRAPE with minor changes, and get parallelized. As long as the sequential algorithms are correct, their GRAPE parallelization guarantees to terminate with correct answers under a monotonic condition. 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-ofthe-art graph systems, using real-life and synthetic graphs.

关键词： Parallel model graph computation partial evaluation incremental evaluation scalability

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Efficient computation of distance labeling for decremental updates in large dynamic graphs

引用

WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS 2017年第5期20卷 915-937页

作者： Qin, Yongrui Sheng, Quan Z. Falkner, Nickolas J. G. Yao, Lina Parkinson, Simon Univ Huddersfield Sch Comp & Engn Huddersfield W Yorkshire England Univ Adelaide Sch Comp Sci Adelaide SA Australia Univ New South Wales Sch Comp Sci & Engn Sydney NSW Australia

Since today's real-world graphs, such as social network graphs, are evolving all the time, it is of great importance to perform graph computations and analysis in these dynamic graphs. Due to the fact that many applications such as social network link analysis with the existence of inactive users need to handle failed links or nodes, decremental computation and maintenance for graphs is considered a challenging problem. Shortest path computation is one of the most fundamental operations for managing and analyzing large graphs. A number of indexing methods have been proposed to answer distance queries in static graphs. Unfortunately, there is little work on answering such queries for dynamic graphs. In this paper, we focus on the problem of computing the shortest path distance in dynamic graphs, particularly on decremental updates (i.e., edge deletions). We propose maintenance algorithms based on distance labeling, which can handle decremental updates efficiently. By exploiting properties of distance labeling in original graphs, we are able to efficiently maintain distance labeling for new graphs. We experimentally evaluate our algorithms using eleven real-world large graphs and confirm the effectiveness and efficiency of our approach. More specifically, our method can speed up index re-computation by up to an order of magnitude compared with the state-of-the-art method, Pruned Landmark Labeling (PLL).

关键词： Shortest path graph computation Distance labeling Dynamic graph

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：