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

parallel graph processing on Modern Multi-Core Servers: New Findings and Remaining Challenges 24

Parallel Graph Processing on Modern Multi-Core Servers: New ...

24th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS)

作者： Eisenman, Assaf Cherkasova, Ludmila Magalhaes, Guilherme Cai, Qiong Katti, Sachin Stanford Univ Stanford CA 94305 USA Hewlett Packard Labs Palo Alto CA 94304 USA Hewlett Packard Enterprise Palo Alto CA USA

ISBN: (纸本)9781509034321

Big Data analytics and new problems in social networks, computational biology, and web connectivity led to a renewed research interest in graph processing. Due to "irregularity" of graph computations, efficient parallel graph processing faces a set of software and hardware challenges debated in literature. In this paper(1), by utilizing hardware performance counters, we characterize system bottlenecks, resource usage, and the efficiency of popular graph applications on the modern commodity hardware. We analyze selected graph applications ( implemented in the Galois framework) on a variety of graph datasets: both scale-free graphs and meshes. Our profiling shows that with an increased number of cores the analyzed graph applications achieve a good speedup, which is highly correlated with utilized memory bandwidth. Contrary to traditional past stereotypes, we find that graph applications significantly benefit from hardware prefetchers. Moreover, the use of transparent huge pages ( THP) exhibits a "double win" impact: 1) THP significantly decrease the TLB misses and page walk durations, and 2) THP boost the hardware prefetchers' performance. These insights shed light to understand the performance of emerging systems with large memories. Our profiling framework reports hardware counter values over time. It reveals the danger of using averages for a bottleneck and resource usage analysis: many applications have a time-varying behavior and stretch the usage of system resources to their peak. We discuss the new insights and remaining challenges for guiding the design of future hardware and software components for efficient graph processing.

关键词： Bottlenecks Hardware performance counters Hardware prefetchers parallel graph processing Performance analysis Profiling Scalability THP

来源：评论

学校读者我要写书评

暂无评论

parallel graph processing: Prejudice and State of the Art 16

Parallel Graph Processing: Prejudice and State of the Art

引用

7th ACM/SPEC International Conference on Performance Engineering (ICPE)

作者： Eisenman, Assaf Cherkasova, Ludmila Magalhaes, Guilherme Cai, Qiong Faraboschi, Paolo Katti, Sachin Stanford Univ Stanford CA 94305 USA Hewlett Packard Labs Palo Alto CA 94304 USA Hewlett Packard Enterprise Palo Alto CA USA

ISBN: (纸本)9781450340809

Large graph processing has attracted much renewed attention due to its increased importance for a social network analysis. The efficient parallel graph processing faces a set of software and hardware issues, discussed in literature. The main cause of these challenges is the "irregularity" of graph computations and related difficulties in efficient parallelization of graph processing. Unbalanced computations, caused by uneven data partitioning, can affect application scalability. Moreover, the issue of poor data locality is another major concern, that makes the graph processing applications memory-bound. In this paper(1), we aim to profile how large, parallel graph applications (based on Galois framework) utilize modern systems, in particular, memory subsystem. We found that modern graph processing frameworks executed on the latest Intel multicore systems (a single node server) exhibit a good data locality and achieve a good speedup with an increased number of cores, contrary to traditional past stereotypes. The application processing speedup is highly correlated with utilized memory bandwidth. At the same time, our measurements show that the memory bandwidth is not a bottleneck, and the analyzed graph applications are memory-latency bound. These new insights can help us in matching the resource demands of the graph processing applications to future system design parameters.

关键词： parallel graph processing benchmarking profiling hardware performance counters

来源：评论

学校读者我要写书评

暂无评论

Enabling application-aware flexible graph partition mechanism for parallel graph processing systems

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2017年第6期29卷

作者： Dong, Fang Zhang, Junxue Luo, Junzhou Shen, Dian Jin, Jiahui Southeast Univ Sch Comp Sci & Engn Nanjing Jiangsu Peoples R China

With the emerging of the large-scale graph data, Pregel-like graph parallel processing systems have been an essential tool to efficiently process the graph data. The first step to use the Pregel-like systems is to partition the graph into multiple blocks and distribute them on multiple machines. The partition strategy plays a significant role in determining the performance because a good partition could both ensure load balance and optimize network communication overhead, and vice versa. However, existing partition strategies fail to meet the requirements because they suffer from the following drawbacks: (1) they ignore the application features and (2) they ignore the multi-application feature in productive environment. To overcome those drawbacks, we proposed the superblock partition strategy, which utilizes the atomic blocks generated by pre-processing of the original graph and could be constructed and re-constructed dynamically according to the submitted applications in real time. The hash-based and clustering-based pre-partition methods are covered in details. The application feature extraction method and heuristic superblock partition algorithm are proposed to construct the superblocks. Experimental results show that the superblock partition strategy could boost the graph processing performance and its partition efficiency also outperforms the hash-based and topology optimal partition strategy. Copyright (C) 2016 John Wiley & Sons, Ltd.

关键词： parallel graph processing graph partition application aware fast and flexible

来源：评论

学校读者我要写书评

暂无评论

Enabling application-aware flexible graph partition mechanism for parallel graph processing systems

Enabling application-aware flexible graph partition mechanis...

引用

3rd International Conference on Advanced Cloud and Big Data (CBD)

作者： Dong, Fang Zhang, Junxue Luo, Junzhou Shen, Dian Jin, Jiahui Southeast Univ Sch Comp Sci & Engn Nanjing Jiangsu Peoples R China

关键词： parallel graph processing graph partition application aware fast and flexible

来源：评论

学校读者我要写书评

暂无评论

DFA-G: A Unified Programming Model for Vertex-centric parallel graph processing 16

DFA-G: A Unified Programming Model for Vertex-centric Parall...

引用

16th IEEE International Conference on Data Mining (ICDM)

作者： Suo, Bo Su, Jing Chen, Qun Li, Zhanhuai Pan, Wei Northwestern Polytech Univ Sch Comp Sci & Engn Xian Peoples R China

ISBN: (纸本)9781509059102

Many systems have been built for vertex-centric parallel graph processing. Based on the Bulk Synchronous parallel (BSP) model, they execute user-defined operations at vertices iteratively and exchange information between vertices by messages. Even though the native BSP systems (e.g. Pregel and Giraph) execute the operations on vertices synchronously within an iteration, many other platforms (e.g. Grace, Blogel and graphHP) have proposed asynchronous execution for improved efficiency. However, they also bring about an undesirable side effect: a program designed for synchronous platforms may not run properly on asynchronous platforms. In this demo, we present DFA-G (Deterministic Finite Automaton for graph processing), a unified programming model for vertex-centric parallel graph processing. Built on DFA, DFA-G expresses the computation at a vertex as a process of message-driven state transition. A program modeled after DFA-G can run properly on both synchronous and asynchronous platforms. We demonstrate how to build DFA-G models using a graphical user interface and also how to automatically translate them into BSP programs.

关键词： Deterministic Finite Automaton parallel graph processing Programming Model

来源：评论

学校读者我要写书评

暂无评论

A Performance and Recommendation System for parallel graph processing Implementations: Work-In-Progress 19

A Performance and Recommendation System for Parallel Graph P...

引用

10th ACM/SPEC International Conference on Performance Engineering (ICPE)

作者： Pollard, Samuel D. Srinivasan, Sudharshan Norris, Boyana Univ Oregon Eugene OR 97403 USA

ISBN: (纸本)9781450362863

There are nearly one hundred parallel and distributed graph processing packages. Selecting the best package for a given problem is difficult;some packages require GPUs, some are optimized for distributed or shared memory, and some require proprietary compilers or perform better on different hardware. Furthermore, performance may vary wildly depending on the graph itself. This complexity makes selecting the optimal implementation manually infeasible. We develop an approach to predict the performance of parallel graph processing using both regression models and binary classification by labeling configurations as either well-performing or not. We demonstrate our approach on six graph processing packages: graphMat, the graph500, the graph Algorithm Platform Benchmark Suite, graphBIG, Galois, and Powergraph and on four algorithms: PageRank, single-source shortest paths, triangle counting, and breadth first search. Given a graph, our method can estimate execution time or suggest an implementation and thread count expected to perform well. Our method correctly identifies well-performing configurations in 97% of test cases.

关键词： parallel graph processing Performance Engineering Performance Analysis Recommender System Classification Regression

来源：评论

学校读者我要写书评

暂无评论

Allok: a machine learning approach for efficient graph execution on CPU-GPU clusters

引用

JOURNAL OF SUPERCOMPUTING 2024年第13期80卷 18838-18865页

作者： Moori, Marcelo Koji Rocha, Hiago Mayk G. de A. Lorenzon, Arthur F. Beck, Antonio Carlos S. Univ Fed Rio Grande do Sul Inst Informat Porto Alegre Brazil

The unprecedented increase in interconnected data has driven the development of efficient graph analytics for extensive data analysis, resulting in improvements across various domains. Prior work has focused on optimizing graph execution for both CPUs and GPUs while overlooking the scalability of graph applications and the selection of an ideal architecture. Thus, we propose Allok, a flexible graph processing framework that aids in selecting the optimal processing architecture (CPU or GPU) for a batch of graph applications while also optimizing number of threads on CPUs. Allok relies solely on high-level graph features to make decisions without the need for further application execution. Our experiments on an HPC system with 4 CPUs and 3 GPUs running 5 algorithms over 25 input graphs show that Allok reduces application execution time by an average of 67.26x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\times$$\end{document} and reduces energy consumption and energy-delay product by an average of 18.06x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\times$$\end{document} and 1237.96x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\times$$\end{document}, respectively.

关键词： graph analytics parallel graph processing graph's features GPU CPU

来源：评论

学校读者我要写书评

暂无评论

parallelizing maximal clique and k-plex enumeration over graph data

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2017年 106卷 79-91页

作者： Wang, Zhuo Chen, Qun Hou, Boyi Suo, Bo Li, Zhanhuai Pan, Wei Ives, Zachary G. Northwestern Polytech Univ Sch Comp Sci & Engn Xian 710072 Peoples R China Univ Penn Comp & Informat Sci Dept Philadelphia PA 19104 USA

In a wide variety of emerging data-intensive applications, such as social network analysis, Web document clustering, entity resolution, and detection of consistently co-expressed genes in systems biology, the detection of dense subgraphs cliques and k-plex is an essential component. Unfortunately, these problems are NP-Complete and thus computationally intensive at scale hence there is a need to come up with techniques for distributing the computation across multiple machines such that the computation, which is too time-consuming on a single machine, can be efficiently performed on a machine cluster given that it is large enough. In this paper, we first propose a new approach for maximal clique and k-plex enumeration, which identifies dense subgraphs by binary graph partitioning. Given a connected graph G = (V, E), it has a space complexity of O(|E|) and a time complexity of O(|E|mu(G)), where mu(G) represents the number of different cliques (k-plexes) existing in G. It recursively divides a graph until each task is sufficiently small to be processed in parallel. We then develop parallel solutions and demonstrate how graph partitioning can enable effective load balancing. Finally, we evaluate the performance of the proposed approach on real and synthetic graph data and show that it performs considerably better than existing approaches in both centralized and parallel settings. In the parallel setting, it can achieve the speedups of up to 10x over existing approaches on large graphs. Our parallel algorithms are primarily implemented and evaluated on MapReduce, a popular shared-nothing parallel framework, but can easily generalize to other shared nothing or shared-memory parallel frameworks. The work presented in this paper is an extension of our preliminary work on the approach of binary graph partitioning for maximal clique enumeration. In this work, we extend the proposed approach to handle maximal k-plex detection as well. (C) 2017 Elsevier Inc. All rights reserve

关键词： Maximal clique enumeration Maximal k-plex enumeration parallel graph processing MapReduce

来源：评论

学校读者我要写书评

暂无评论

Theoretically Efficient parallel graph Algorithms Can Be Fast and Scalable

引用

ACM TRANSACTIONS ON parallel COMPUTING 2021年第1期8卷 1–70页

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

There has been significant recent interest in parallel graph processing due to the need to quickly analyze the large graphs available today. Many graph codes have been designed for distributed memory or external memory. However, today even the largest publicly-available real-world graph (the Hyperlink Web graph with over 3.5 billion vertices and 128 billion edges) can fit in the memory of a single commodity multicore server. Nevertheless, most experimental work in the literature report results on much smaller graphs, and the ones for the Hyperlink graph use distributed or external memory. Therefore, it is natural to ask whether we can efficiently solve a broad class of graph problems on this graph in memory. This paper shows that theoretically-efficient parallel graph algorithms can scale to the largest publicly available graphs using a single machine with a terabyte of RAM, processing them in minutes. We give implementations of theoretically-efficient parallel algorithms for 20 important graph problems. We also present the interfaces, optimizations, and graph processing techniques that we used in our implementations, which were crucial in enabling us to process these large graphs quickly. We show that the running times of our implementations outperform existing state-of-the-art implementations on the largest real-world graphs. For many of the problems that we consider, this is the first time they have been solved on graphs at this scale. We have made the implementations developed in this work publicly-available as the graph Based Benchmark Suite (GBBS).

关键词： parallel graph algorithms parallel graph processing

来源：评论

学校读者我要写书评

暂无评论

Diversified Top-k Querying in Knowledge graphs 4th

Diversified Top-k Querying in Knowledge Graphs

引用

Joint International Conference on Web and Big Data : Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM)

作者： Guo, Xintong Gao, Hong An, Yinan Zou, Zhaonian Harbin Inst Technol Harbin Peoples R China

ISBN: (纸本)9783030602581;9783030602598

The existing literatures of the query processing on knowledge graphs focus on an exhaustive enumeration of all matches, which is time-consuming. Users are often interested in diversified top-k matches, rather than the entire match set. Motivated by these, this paper formalizes the diversified top-k querying (DTQ) problem in the context of RDF/SPARQL and proposes a diversification function to balance importance and diversity. We first prove that the decision problem of DTQ is NP-complete, and give a baseline algorithm with an approximation ratio of 2. Secondly, an index-based algorithm with the early termination property is proposed. The index is adept in parallel diversified top-k selection in multicore architectures. Using real-world and synthetic data, we experimentally verify that our algorithms are efficient and effective in computing meaningful diversified top-k matches.

关键词： Diversified top-k query RDF/SPARQL parallel graph processing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：