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

Distributed graph Computation Meets Machine Learning

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2020年第7期31卷 1588-1604页

作者： Xiao, Wencong Xue, Jilong Miao, Youshan Li, Zhen Chen, Cheng Wu, Ming Li, Wei Zhou, Lidong Alibaba Grp Hangzhou 311121 Peoples R China Microsoft Res Beijing 100080 Peoples R China Google Mountain View CA 94043 USA ByteDance Beijing 100089 Peoples R China Conflux Fdn Singapore 48619 Singapore Beihang Univ State Key Lab Software Dev Environm Beijing 100083 Peoples R China

TuX(2) is a new distributed graph engine that bridges graph computation and distributed machine learning. TuX(2) inherits the benefits of elegant graph computation model, efficient graph layout, and balanced parallelism to scale to billion-edge graphs, while extended and optimized for distributed machine learning to support heterogeneity in data model, Stale Synchronous Parallel in scheduling, and a new Mini-batch, Exchange, GlobalSync, and Apply (MEGA) model for programming. TuX(2) further introduces a hybrid vertex-cut graph optimization and supports various consistency models in fault tolerance for machine learning. We have developed a set of representative distributed machine learning algorithms in TuX(2), covering both supervised and unsupervised learning. Compared to the implementations on distributed machine learning platforms, writing those algorithms in TuX(2) takes only about 25 percent of the code: our graph computation model hides the detailed management of data layout, partitioning, and parallelism from developers. The extensive evaluation of TuX(2), using large datasets with up to 64 billion of edges, shows that TuX(2) outperforms Powergraph/PowerLyra, the state-of-the-art distributed graph engines, by an order of magnitude, while beating two state-of-the-art distributed machine learning systems by at least 60 percent.

关键词： graph computing distributed machine learning heterogeneity stale synchronous parallel MEGA model

来源：评论

学校读者我要写书评

暂无评论

A Shortest Path Finding Time-Based Accelerator Core With Built-in Gravity Control and Buffer Zone for Smooth 3-D Navigation

引用

IEEE SOLID-STATE CIRCUITS LETTERS 2020年 3卷 66-69页

作者： Everson, Luke R. Song, Jeehwan Sapatnekar, Sachin S. Kim, Chris H. Univ Minnesota Elect & Comp Engn Dept Minneapolis MN 55455 USA

A mixed-signal time-based 65-nm application specific integrated circuit is developed for solving shortest-path problems in 3-D. Previous path planning ASICs have been restricted to 2-D maps due to computational complexity or physical architecture limitations. Our time-based, asynchronous, one-shot architecture has been coupled with a novel dual axis interleaving strategy to solve the multidimensional shortest path problem in a simple, energy efficient manner. Additional features include circuit-based solutions for obstacle blockage avoidance and gravity. The efficacy of the proposed ASIC is evaluated on a drone navigation application, 3-D Voronoi diagrams, and a physical optics experiment. The chip is twice as energy efficient as prior 2-D work while containing 5x more vertices and 7.5x additional edge connections.

关键词： A* algorithm graph computing graphs single-source shortest path time-domain computing time-to-digital converter

来源：评论

学校读者我要写书评

暂无评论

MG-Hybrid: A Strongly Connected Components Detection Algorithm Using Multiple GPUs 52

MG-Hybrid: A Strongly Connected Components Detection Algorit...

引用

IEEE International Symposium on Circuits and Systems (ISCAS)

作者： Hou, Junteng Wang, Shupeng Wu, Guangjun Ma, Bingnan Si, Chengxiang Jia, Siyu Chinese Acad Sci Inst Informat Engn Beijing Peoples R China Univ Chinese Acad Sci Sch Cyber Secur Beijing Peoples R China Coordinat Ctr China Natl Comp Network Emergency Response Tech Team Beijing Peoples R China

ISBN: (纸本)9781728133201

Detection of strongly connected component (SCC) on the GPU has become a fundamental operation to accelerate graph computing. Existing SCC detection methods on multiple GPUs introduce massive unnecessary data transformation between multiple GPUs. In this paper, we propose a novel distributed SCC detection approach using multiple GPUs plus CPU. Our approach includes three key ideas: (1) segmentation and labeling over large-scale datasets;(2) collecting and merging the segmented SCCs;and (3) running tasks assignment over multiples GPUs and CPU. We implement our approach under a hybrid distributed architecture with multiple GPUs plus CPU. Our approach can achieve device-level optimization and can be compatible with the state-of-the-art algorithms. We conduct extensive theoretical and experimental analysis to demonstrate efficiency and accuracy of our approach. The experimental results expose that our approach can achieves 11.2x, 1.2x, 1.2x speedup for SCC detection using NVIDIA K80 compared with Tarjan's, FB-Trim, and FB-Hybrid algorithms respectively.

关键词： graph computing strongly connected components detection multiple GPUs heterogeneous algorithm hybrid scheme

来源：评论

学校读者我要写书评

暂无评论

Power Grid Modeling and Topology Analysis Based on graph Database Conforming with CIM/E 4th

Power Grid Modeling and Topology Analysis Based on Graph Dat...

引用

4th International Forum on Smart Grid Protection and Control (Purple Mountain Forum)

作者： Huang, Hua Gao, Zonghe Dai, Jiangpeng Wang, Yi Shan, Xin Zhai, Mingyu Liu, Guangyi Wang, Wei NARI Grp Corp Nanjing 211106 Peoples R China NARI Technol Co Ltd Nanjing 211106 Peoples R China State Key Lab Smart Grid Protect & Control Nanjing 211106 Peoples R China Global Energy Interconnect Res Inst North Amer San Jose CA 95134 USA

ISBN: (纸本)9789811397837;9789811397820

The power system is becoming larger and larger, and the operation is more frequent, which puts higher requirements on the real-time performance of analysis and calculation. The graph database is a new type of database that originated from the parallel processing of massive data in the Internet. The data model can visually express the topology of the grid and easily realize parallel traversal query. Firstly, the characteristics of graph database are introduced from the aspects of data model and data query, and the potential advantages of applying it to large-scale power system analysis and calculation are analyzed. Secondly, the design method of power system modeling is presented for satisfying the guidelines of integrity, consistency and efficiency conforming with CIM/E standard. Finally, a parallel power network topology analysis algorithm is implemented based on the graph database model for a provincial grid. The calculation results of the actual large-scale provincial power grid show that the proposed method can significantly improve the topology search efficiency.

关键词： graph database graph computing Power grid modeling Network topology CIM/E

来源：评论

学校读者我要写书评

暂无评论

Online Prediction for Transmission Cascading Outages Induced by Ultrafast PEV Charging

引用

IEEE TRANSACTIONS ON TRANSPORTATION ELECTRIFICATION 2019年第4期5卷 1124-1133页

作者： Mao, Daijiafan Yuan, Chen Gao, Ziran Wang, Jiankang Zhao, Ruili Global Energy Interconnect Res Inst North Amer San Jose CA 95134 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Calif Independent Syst Operator Folsom CA 95630 USA

With the development of charging technologies, the auto industry has envisioned the ability to recharge plug-in electric vehicles (PEV) at speeds comparable to traditional gas refueling. These ultrafast charging stations (UFCSs) could exert disruptive influences on the power grid. This article proposes a graph-computing-based cascading failure evolution (G-CFE) analysis to predict potential cascading failures induced by UFCS on power transmission systems. Fundamentally different from the existing cascading analysis tools, which are based on dc power flow or require a long-computation time, the proposed method greatly improves accuracy by using ac power flow, while guaranteeing the analyzing speed with graph parallel computing techniques. In addition, G-CFE can accurately capture the stochastic PEV charging patterns with Monte-Carlo simulation. Finally, G-CFE can be easily scaled to various network configurations through a graph-based scheme. The proposed method is validated on a provincial transmission system in China.

关键词： Power grids Power system faults Power system protection Stochastic processes State of charge Load modeling Failure analysis Cascading failure graph computing impact assessment plug-in electric vehicle ultrafast charging station (UFCS)

来源：评论

学校读者我要写书评

暂无评论

KnightKing: A Fast Distributed graph Random Walk Engine 19

KnightKing: A Fast Distributed Graph Random Walk Engine

引用

27th ACM Symposium on Operating Systems Principles (SOSP)

作者： Yang, Ke Zhang, MingXing Chen, Kang Ma, Xiaosong Bai, Yang Jiang, Yong Tsinghua Univ Beijing Natl Res Ctr Informat Sci & Technol BNRis Dept Comp Sci & Technol Beijing Peoples R China Tsinghua Univ Res Inst Shenzhen Peoples R China Sangfor Technol Inc Shenzhen Peoples R China Hamad Bin Khalifa Univ Qatar Comp Res Inst Ar Rayyan Qatar 4Paradigm Co Ltd Beijing Peoples R China

ISBN: (纸本)9781450368735

Random walk on graphs has recently gained immense popularity as a tool for graph data analytics and machine learning. Currently, random walk algorithms are developed as individual implementations and suffer significant performance and scalability problems, especially with the dynamic nature of sophisticated walk strategies. We present KnightKing, the first general-purpose, distributed graph random walk engine. To address the unique interaction between a static graph and many dynamic walkers, it adopts an intuitive walker-centric computation model. The corresponding programming model allows users to easily specify existing or new random walk algorithms, facilitated by a new unified edge transition probability definition that applies across popular known algorithms. With KnightKing, these diverse algorithms benefit from its common distributed random walk execution engine, centered around an innovative rejection-based sampling mechanism that dramatically reduces the cost of higher-order random walk algorithms. Our evaluation confirms that KnightKing brings up to 4 orders of magnitude improvement in executing algorithms that currently can only be afforded with approximation solutions on large graphs.

关键词： graph computing random walk rejection sampling

来源：评论

学校读者我要写书评

暂无评论

LOSC: Efficient Out-of-Core graph Processing with Locality-optimized Subgraph Construction 19

LOSC: Efficient Out-of-Core Graph Processing with Locality-o...

引用

IEEE/ACM International Symposium on Quality of Service (IWQoS)

作者： Xu, Xianghao Wang, Fang Jiang, Hong Cheng, Yongli Hua, Yu Feng, Dan Zhang, Yongxuan Huazhong Univ Sci & Technol Wuhan Natl Lab Optoelect Wuhan Hubei Peoples R China Univ Texas Arlington Dept Comp Sci & Engn Arlington TX 76019 USA FuZhou Univ Coll Math & Comp Sci Fuzhou Fujian Peoples R China Shenzhen Huazhong Univ Sci & Technol Res Inst Shenzhen Peoples R China

ISBN: (数字)9781450367783

ISBN: (纸本)9781450367783

Big data applications increasingly rely on the analysis of large graphs. In recent years, a number of out-of-core graph processing systems have been proposed to process graphs with billions of edges on just one commodity computer, by efficiently using the secondary storage (e.g., hard disk, SSD). On the other hand, the vertex-centric computing model is extensively used in graph processing thanks to its good applicability and expressiveness. Unfortunately, when implementing vertex-centric model for out-of-core graph processing, the large number of random memory accesses required to construct subgraphs lead to a serious performance bottleneck that substantially weakens cache access locality and thus leads to very long waiting time experienced by users for the computing results. In this paper, we propose an efficient out-of-core graph processing system, LOSC, to substantially reduce the overhead of subgraph construction without sacrificing the underlying vertex-centric computing model. LOSC proposes a locality-optimized subgraph construction scheme that significantly improves the in-memory data access locality of the subgraph construction phase. Furthermore, LOSC adopts a compact edge storage format and a lightweight replication of vertices to reduce I/O traffic and improve computation efficiency. Extensive evaluation results show that LOSC is respectively 6.9x and 3.5x faster than graphChi and Gridgraph, two state-of-the-art out-of-core systems.

关键词： graph computing out-of-core subgraph construction

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient computing With Time-Based Digital Circuits

Energy Efficient Computing With Time-Based Digital Circuits

引用

作者： Luke Everson University of Minnesota

学位级别：博士

Advancements in semiconductor technology have given the world economical, abundant, and reliable computing resources which have enabled countless breakthroughs in science, medicine, and agriculture which have improved the lives of many. Due to physics, the rate of these advancements is slowing, while the demand for the increasing computing horsepower ever grows. Novel computer architectures that leverage the foundation of conventional systems must become mainstream to continue providing the improved hardware required by engineers, scientists, and governments to innovate. This thesis provides a path forward by introducing multiple time-based computing architectures for a diverse range of applications. Simply put, time-based computing encodes the output of the computation in the time it takes to generate the result. Conventional systems encode this information in voltages across multiple signals; the performance of these systems is tightly coupled to improvements in semiconductor technology. Time-based computing elegantly uses the simplest of components from conventional systems to efficiently compute complex results. Two time-based neuromorphic computing platforms, based on a ring oscillator and a digital delay line, are described. An analog-to-digital converter is designed in the time domain using a beat frequency circuit which is used to record brain activity. A novel path planning architecture, with designs for 2D and 3D routes, is implemented in the time domain. Finally, a machine learning application using time domain inputs enables improved performance of heart rate prediction, biometric identification, and introduces a new method for using machine learning to predict temporal signal sequences. As these innovative architectures are presented, it will become clear the way forward will be increasingly enabled with time-based designs.

关键词： circuit design digital circuits graph computing machine learning time-domain vlsi

来源：评论

学校读者我要写书评

暂无评论

Query-Sensitive graph Partitioner for Pattern Matching Applications

引用

IEEE ACCESS 2019年 7卷 184668-184675页

作者： Lu, Li Hua, Bei Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230027 Peoples R China

Searching and mining in large graphs is critical to a variety of applications, at the core of which is the pattern matching activity. The scalable processing of large graphs requires careful distribution of graphs across clusters. graph partitioning is the technique that divides a big graph into several non-overlapped subgraphs and assigns each subgraph to a compute node. Traditional workload agnostic partitioners aim to minimize the number of inter-partition edges using only graph topology, which, however, may not obtain the best solution if the workload exhibits skew. Some workload-aware partitioners choose to mine information from a specific workload and use it to minimize the number of inter-partition traversals during execution;however, their methods are not suitable for pattern matching applications. In this work, we propose a querysensitive graph partitioner that aims to improve existing partitioning for a given pattern matching workload. The partitioner takes any initial partitioning as a starting point and iteratively adjusts it by exchanging chosen clusters across partitions, heuristically reducing the probability of inter-partition traversals. We determine a few implementation-irrelative factors that may increase the traversal probability of an edge and quantify them into a calculable indicator with information from query patterns and graph topology. Then, we propose an efficient algorithm to calculate the indicator and implement a graph repartitioner by combining the indicator with a greedy cluster-exchanging mechanism. Finally, we generate a large heterogeneous labeled graph with real-world data crawled from the Netease Music website and evaluate the partitioning quality of our repartitioner with a few meaningful query patterns of common topologies including line, loop and branching. Compared with a hash-based partitioning, our system can reduce the inter-partition traversals by at least 70%. Compared with the state-of-the-art graph partitioner Metis, o

关键词： graph computing graph partitioning pattern match workload mining

来源：评论

学校读者我要写书评

暂无评论

Accelerating breadth-first graph search on a single server by dynamic edge trimming

引用

JOURNAL OF PARALLEL AND DISTRIBUTED computing 2018年 120卷 383-394页

作者： Zhang, Guangyan Cheng, Shuhan Shu, Jiwu Hu, Qingda Zheng, Weimin Tsinghua Univ Dept Comp Sci & Technol Beijing Peoples R China

Breadth-first graph search (a.k.a., BFS) is one of the typical in-memory computing models with complicated and frequent memory accesses. Existing single-server graph computing systems fail to take advantage of access pattern of BFS for performance optimization, hence suffering from a lot of extra memory latencies due to accessing no longer useful data elements of a big graph as well as wasting plenty of computing resources for processing them. In this article, we propose FastBFS, a new approach that accelerates breadth-first graph search on a single server by leverage of the access pattern during iterating over a big graph. First, FastBFS uses an edge-centric graph processing model to obtain the high bandwidth of sequential memory and/or disk access without expensive data preprocessing. Second, with a dynamic and asynchronous trimming mechanism, FastBFS can efficiently reduce the size of a big graph by eliminating useless edges in parallel with the computation. Third, FastBFS schedules I/O streams efficiently and can attain greater parallelism if an additional disk is available. We implement FastBFS by modifying the X-Stream system developed by EPFL. Our experimental results show that FastBFS can attain speedups of up to 7.9x and 10.4x in the computing speed compared with X-stream and graphChi respectively. With an additional disk, the performance can be further improved. (C) 2017 Elsevier Inc. All rights reserved.

关键词： graph computing In-memory computing I/O optimization BFS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：