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

High-performance parallel frequent subgraph discovery

JOURNAL OF SUPERCOMPUTING 2015年第7期71卷 2412-2432页

作者： Shahrivari, Saeed Jalili, Saeed TMU Dept Comp Engn Tehran Iran

Discovery of frequent subgraphs of an input network is one of the most important facilities for mining and analyzing complex networks. The most accurate solution to frequent subgraph discovery is to enumerate all subgraphs of size k and then count the frequency of each isomorphic class. However, the process is much time consuming because the number of subgraphs grows exponentially with the growth of the input network, or by increasing the size of the subgraphs. Also, there is no known polynomial-time algorithm for subgraph isomorphism detection, and this issue makes the problem harder. Hence, the available solutions can just mine small input networks and small subgraph sizes. A parallel and load-balanced solution named Subdigger is proposed which is faster and more efficient compared to available solutions. Subdigger efficiently executes on current multicore and multiprocessor machines, and incorporates a fast heuristic with a high-performance concurrent data structure which significantly accelerates detection and counting of isomorphic subgraphs. Subdigger can also handle large networks and subgraph sizes using external memory and external sorting. We performed several experiments using real-world input networks. Compared to the available solutions, Subdigger can extract frequent subgraphs much faster and the performance scales almost linearly using additional processor cores. The experimental results show that Subdigger can be more than 100 times faster than other solutions on a 4-core Intel i7 machine. Besides performance, Subdigger can process larger subgraphs using external memory while other tools crash due to memory limitation.

关键词： parallel frequent subgraph discovery Multicore processing parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A scalable, parallel algorithm for maximal clique enumeration

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2009年第4期69卷 417-428页

作者： Schmidt, Matthew C. Samatova, Nagiza F. Thomas, Kevin Park, Byung-Hoon N Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA Oak Ridge Natl Lab Comp Sci & Math Div Oak Ridge TN 37831 USA

The problem of maximal clique enumeration (MCE) is to enumerate all of the maximal cliques in a graph. Once enumerated, maximal cliques are widely used to solve problems in areas such as 3-D protein structure alignment, genome mapping, gene expression analysis, and detection of social hierarchies. Even the most efficient serial MCE algorithms require large amounts of time to enumerate the maximal cliques in networks arising from these problems that contain hundreds, thousands, or larger numbers of vertices. The previous attempts to provide practical solutions to the MCE problem through parallel implementation have had limited success, largely due to a number of challenges inherent to the nature of the MCE combinatorial search space. On the one hand, NICE algorithms often create a backtracking search tree that has a highly irregular and hard-or-impossible to predict structure;therefore, almost any static decomposition of the search tree by parallel processors results in highly unbalanced processor execution times. On the other hand, the data-intensive nature of the MCE problem often makes naive dynamic load distribution strategies that require extensive data movement prohibitively expensive. As a result, good scaling of the overall execution time of parallel MCE algorithms has been reported for only up to a couple hundred processors. In this paper, we propose a parallel, scalable, and memory-efficient MCE algorithm for distributed and/or shared memory high performance computing architectures, whose runtime scales linearly for thousands of processors on real-world application graphs with hundreds and thousands of nodes. Its scalability and efficiency are attributed to the proposed: (a) representation of the search tree decomposition to enable parallelization;(b) parallel depth-first backtracking search to both constrain the search space and minimize memory requirement: (c) least stringent synchronization to minimize data movement;and (d) on-demand work stealing intell

关键词： Maximal clique enumeration parallel graph algorithms High-performance computing Dynamic load balancing Biological networks Cray XT

来源：评论

学校读者我要写书评

暂无评论

Optimizing graph algorithms in Asymmetric Multicore Processors

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2018年第11期37卷 2673-2684页

作者： Krishna, Jyothi V. S. Nasre, Rupesh Indian Inst Technol Madras Dept Comp Sci & Engn Madras 600036 Tamil Nadu India

Asymmetric multicore processors (AMP) fall under a special subcategory of modern-day heterogeneous multicore architectures with different participating core types executing a common instruction set architecture. The innate asymmetry in the performance of different cores in AMPs poses interesting challenges. Irregular workloads, such as graph algorithms, intensify these challenges as the parallel workloads in these algorithms cannot be precisely characterized at compile time. In this paper, we propose a framework named scheduler for irregular AMPs, which optimizes the efficiency of the given AMP system for a given algorithm-graph pair by optimizing the graph representation and using a predictor to find the optimal configurations to run the algorithm-graph pair. The optimization is performed in two stages: 1) finding an optimal graph representation and 2) finding an optimal hardware configuration to run the input algorithm-graph pair. We have tested the efficiency of our system on five different graph algorithms over eight real-world and synthetic graphs. On an average, we see 42.82% improvement in energy delay product over the base case.

关键词： Asymmetric multicore processors (AMP) parallel graph algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

An Efficient GPU Implementation of Inclusion-Based Pointer Analysis

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2016年第2期27卷 353-366页

作者： Su, Yu Ye, Ding Xue, Jingling Liao, Xiang-Ke UNSW Sch Comp Sci & Engn Programming Language & Compilers Grp Sydney NSW Australia Natl Univ Def Technol Sch Comp Sci Changsha Hunan Peoples R China

We present an efficient GPU implementation of Andersen's whole-program inclusion-based pointer analysis, a fundamental analysis on which many others are based, including optimising compilers, bug detection and security analyses. Andersen's algorithm makes extensive modifications to the graph that represents the pointer-manipulating statements in a program. These modifications are highly irregular, input-dependent and statically unpredictable, making it much more challenging to balance such graph workloads across a multitude of GPU cores than those dealt with by traditional graph algorithms such as DFS and BFS. To parallelise Andersen's analysis efficiently on GPUs, we introduce an imbalance-aware workload partitioning scheme that divides its workload dynamically among the concurrent warps, initially in a warp-centric manner (during the coarsegrain stage) but later switches to a task-pool-based model when a workload imbalance is detected (during the fine-grain stage). We improve further its performance by using an adaptive group propagation scheme to reduce some redundant traversals. For a set of 14 C benchmarks evaluated, our parallel implementation of Andersen's analysis achieves a significant speedup of 46 percent on average over the state-of-the art on an NVIDIA Tesla K20c GPU.

关键词： parallel graph algorithms GPGPU pointer analysis compilers

来源：评论

学校读者我要写书评

暂无评论

A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPS)

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2005年第9期65卷 994-1006页

作者： Bader, DA Cong, GJ Georgia Inst Technol Coll Comp Atlanta GA 30332 USA IBM Corp TJ Watson Res Ctr Yorktown Hts NY USA

The ability to provide uniform shared-memory access to a significant number of processors in a single SMP node brings us much closer to the ideal PRAM parallel computer. Many PRAM algorithms can be adapted to SMPs with few modifications. Yet there are few studies that deal with the implementation and performance issues of running PRAM-style algorithms on SMPs. Our study in this paper focuses on implementing parallel spanning tree algorithms on SMPs. Spanning tree is an important problem in the sense that it is the building block for many other parallel graph algorithms and also because it is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and fast PRAM algorithms, but these irregular problems often have no known efficient parallel implementations. Experimental studies have been conducted on related problems (minimum spanning tree and connected components) using parallel computers, but only achieved reasonable speedup on regular graph topologies that can be implicitly partitioned with good locality features or on very dense graphs with limited numbers of vertices. In this paper we present a new randomized algorithm and implementation with superior performance that for the first time achieves parallel speedup on arbitrary graphs (both regular and irregular topologies) when compared with the best sequential implementation for finding a spanning tree. This new algorithm uses several techniques to give an expected running time that scales linearly with the number p of processors for suitably large inputs (n > p(2)). As the spanning tree problem is notoriously hard for any parallel implementation to achieve reasonable speedup, our study may shed new light on implementing PRAM algorithms for shared-memory parallel computers. The main results of this paper are 1. A new and practical spanning tree algorithm for symmetric multiprocessors that exhibits parallel speedups on graphs with regular and irr

关键词： parallel graph algorithms connectivity shared memory high-performance algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

IMPLEMENTING RECURRENT BACK-PROPAGATION ON THE CONNECTION MACHINE

引用

NEURAL NETWORKS 1989年第4期2卷 295-314页

作者： DEPRIT, E Naval Research Laboratory USA

The recurrent back-propagation algorithm for neural networks has been implemented on the Connection Machine, a massively parallel processor. Two fundamentally different graph architectures underlying the nets were tested: one based on arcs, the other on nodes. Confirming the predominance of communication over computation, performance measurements underscore the necessity to make connections the basic unit of representation. Comparisons between these graph algorithms lead to important conclusions concerning the parallel implementation of neural nets in both software and hardware.

关键词： Neural networks Recurrent back-propagation Continuous mapping Associative memory parallel processing Massively parallel processor parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel Algorithm for Incremental Betweenness Centrality on Large graphs

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2018年第3期29卷 659-672页

作者： Jamour, Fuad Skiadopoulos, Spiros Kalnis, Panos KAUST Thuwal 23955 Saudi Arabia Univ Peloponnese Tripoli 22100 Greece

Betweenness centrality quantifies the importance of nodes in a graph in many applications, including network analysis, community detection and identification of influential users. Typically, graphs in such applications evolve over time. Thus, the computation of betweenness centrality should be performed incrementally. This is challenging because updating even a single edge may trigger the computation of all-pairs shortest paths in the entire graph. Existing approaches cannot scale to large graphs: they either require excessive memory (i.e., quadratic to the size of the input graph) or perform unnecessary computations rendering them prohibitively slow. We propose iCENTRAL;a novel incremental algorithm for computing betweenness centrality in evolving graphs. We decompose the graph into biconnected components and prove that processing can be localized within the affected components. iCENTRAL is the first algorithm to support incremental betweeness centrality computation within a graph component. This is done efficiently, in linear space;consequently, iCENTRAL scales to large graphs. We demonstrate with real datasets that the serial implementation of iCENTRAL is up to 3.7 times faster than existing serial methods. Our parallel implementation that scales to large graphs, is an order of magnitude faster than the state-of-the-art parallel algorithm, while using an order of magnitude less computational resources.

关键词： Betweenness centrality dynamic graph algorithms parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A new augmentation based algorithm for extracting maximal chordal subgraphs

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2015年 76卷 132-144页

作者： Bhowmick, Sanjukta Chen, Tzu-Yi Halappanavar, Mahantesh Univ Nebraska Omaha NE 68182 USA Pomona Coll Claremont CA 91711 USA Pacific NW Natl Lab Richland WA 99352 USA

A graph is chordal if every cycle of length greater than three contains an edge between non-adjacent vertices. Chordal graphs are of interest both theoretically, since they admit polynomial time solutions to a range of NP-hard graph problems, and practically, since they arise in many applications including sparse linear algebra, computer vision, and computational biology. A maximal chordal subgraph is a chordal subgraph that is not a proper subgraph of any other chordal subgraph. Existing algorithms for computing maximal chordal subgraphs depend on dynamically ordering the vertices, which is an inherently sequential process and therefore limits the algorithms' parallelizability. In this paper we explore techniques to develop a scalable parallel algorithm for extracting a maximal chordal subgraph. We demonstrate that an earlier attempt at developing a parallel algorithm may induce a non-optimal vertex ordering and is therefore not guaranteed to terminate with a maximal chordal subgraph. We then give a new algorithm that first computes and then repeatedly augments a spanning chordal subgraph. After proving that the algorithm terminates with a maximal chordal subgraph, we then demonstrate that this algorithm is more amenable to parallelization and that the parallel version also terminates with a maximal chordal subgraph. That said, the complexity of the new algorithm is higher than that of the previous parallel algorithm, although the earlier algorithm computes a chordal subgraph which is not guaranteed to be maximal. We experimented with our augmentation-based algorithm on both synthetic and real-world graphs. We provide scalability results and also explore the effect of different choices for the initial spanning chordal subgraph on both the running time and on the number of edges in the maximal chordal subgraph. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Maximal chordal subgraphs parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A memory efficient maximal clique enumeration method for sparse graphs with a parallel implementation

引用

parallel COMPUTING 2019年第Sep.期87卷 46-59页

作者： Yu, Ting Liu, Mengchi Wuhan Univ Sch Comp Sci Wuhan Hubei Peoples R China South China Normal Univ Sch Comp Sci Guangzhou 510631 Guangdong Peoples R China

Maximal clique enumeration (MCE) is a widely studied problem that plays a crucial role in structure mining of undirected graphs. The increasing scale of real-world graphs has brought the challenges of high memory cost and high CPU workload to the problem. In this paper, we propose a memory efficient method named CMC-bit for MCE on sparse graphs. It reduces the memory cost via minimizing the candidate cliques and representing them by the data structure bitset. It generates an appropriate order for the vertex set according to two optimized principles to reduce the CPU cost. We further design a partition-based CMC-bit algorithm with a one-side extending strategy to solve the memory-limited problem. We parallelize the CMC-bit algorithm based on MapReduce with a range-based partition strategy to make an optimal trade-off between the shuffling workload of graph decomposition and load balance in the Reduce phase. We conduct extensive experiments on 30 real-world datasets. The results demonstrate that both the CMC-bit algorithm and its parallel implementation significantly outperform the respective state-of-the-art algorithms in speed. We also show that the parallel CMC-bit algorithm achieves good performance on the scalability with respect to both the reducer number and the CPU number. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Maximal clique enumeration graph algorithms MapReduce parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

MR-search: massively parallel heuristic search

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2013年第1期25卷 40-54页

作者： Schuett, Thorsten Reinefeld, Alexander Maier, Robert Zuse Inst Berlin D-14195 Berlin Germany

MR-Search is a framework for massively parallel heuristic search. Based on the MapReduce paradigm, it efficiently utilizes all available resources: processors, memories, and disks. MR-Search uses OpenMP on shared memory systems, Message Passing Interface on clusters with distributed memory, and a combination of both on clusters with multi-core processors. Large graphs that do not fit into the main memory can be efficiently processed with an out-of-core variant. We implemented two node expansion strategies in MR-Search: breadth-first frontier search and breadth-first iterative deepening A*. With breadth-first frontier search, we computed large and powerful table-driven heuristics, so-called pattern databases that exceed the main memory capacity. These pattern databases were then used to solve random instances of the 24-puzzle with breadth-first iterative deepening A* on systems with up to 4093 processor cores. MR-Search is conceptually simple. It takes care of data partitioning, process scheduling, out-of-core data merging, communication, and synchronization. Application developers benefit from the parallel computational capacity without having the burden of implementing parallel application code. Copyright (c)?2011 John Wiley & Sons, Ltd.

关键词： heuristic search parallel graph algorithms scalable algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：