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

36th IEEE International parallel and Distributed Processing Symposium (IEEE IPDPS)

作者： Aljundi, Amro Alabsi Akyildiz, Taha Atahan Kaya, Kamer Sabanci Univ Fac Engn & Nat Sci Istanbul Turkey

ISBN: (纸本)9781665481069

graphs provide the ability to extract valuable metrics from the structural properties of the underlying data they represent. One such metric is the Jaccard Weight of an edge, which is the ratio of the number of common neighbors of the edge's endpoints to the union of the endpoints' neighborhood. A naive implementation of Jaccard Weights computation has a complexity that scales with the number of edges in the graph times the square of the maximum degree. Recently, GPU-based parallel algorithms have been proposed for this problem. However, these algorithms cannot overcome the structural variance within a graph, i.e., the sparsity pattern and degree imbalance, which directly translates to unbalanced work distribution across threads. In this work, we propose an optimized GPU-based algorithm with an ML-based work distribution model that mitigates the unbalanced work distribution. Our algorithm is shown to be up to 35x and on average 12x faster than the state of the art in practice while using less memory. In fact, we show that by manually tweaking the load distribution, a state-of-the-art implementation can be 5x faster. In addition, we propose a multi-core, shared-memory algorithm that applies a traditional but effective technique to improve the computation asymptotically and perform comparably to the GPU algorithms. Our code is available at https://***/SU- HPC/Jaccard-ML

关键词： Jaccard Weights parallel graph algorithms GPU work distribution

来源：评论

学校读者我要写书评

暂无评论

Scalable Fine-Grained parallel Cycle Enumeration algorithms 22

Scalable Fine-Grained Parallel Cycle Enumeration Algorithms

引用

34th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Blanusa, Jovan Ienne, Paolo Atasu, Kubilay IBM Res Europe Zurich Switzerland Ecole Polytechn Federale Lausanne EPFL Sch Comp & Commun Sci CH-1015 Lausanne Switzerland

ISBN: (纸本)9781450391467

Enumerating simple cycles has important applications in computational biology, network science, and financial crime analysis. In this work, we focus on parallelising the state-of-the-art simple cycle enumeration algorithms by Johnson and Read-Tarjan along with their applications to temporal graphs. To our knowledge, we are the first ones to parallelise these two algorithms in a fine-grained manner. We are also the first to demonstrate experimentally a linear performance scaling. Such a scaling is made possible by our decomposition of long sequential searches into fine-grained tasks, which are then dynamically scheduled across CPU cores, enabling an optimal load balancing. Furthermore, we show that coarse-grained parallel versions of the Johnson and the Read-Tarjan algorithms that exploit edge- or vertex-level parallelism are not scalable. On a cluster of four multi-core CPUs with 256 physical cores, our fine-grained parallel algorithms are, on average, an order of magnitude faster than their coarse-grained parallel counterparts. The performance gap between the fine-grained and the coarse-grained parallel algorithms widens as we use more CPU cores. When using all 256 CPU cores, our parallel algorithms enumerate temporal cycles, on average, 260x faster than the serial algorithm of Kumar and Calders. Code repository: https://***/IBM/parallel-cycle-enumeration

关键词： Cycle enumeration parallel graph algorithms graph mining

来源：评论

学校读者我要写书评

暂无评论

TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge graphs

引用

Proceedings of the ACM on Management of Data 2023年第3期1卷 1-27页

作者： Laxman Dhulipala Jakub Łącki Jason Lee Vahab Mirrokni UMD & Google Research Bethesda MD USA Google Research New York NY USA

We introduce TeraHAC, a (1+ε)-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing (1+ε)-approximate HAC, which is a novel combination of the nearest-neighbor chain algorithm and the notion of (1+ε)-approximate HAC. Our approach allows us to partition the graph among multiple machines and make significant progress in computing the clustering within each partition before any communication with other partitions is *** evaluate TeraHAC on a number of real-world and synthetic graphs of up to 8 trillion edges. We show that TeraHAC requires over 100x fewer rounds compared to previously known approaches for computing HAC. It is up to 8.3x faster than SCC, the state-of-the-art distributed algorithm for hierarchical clustering, while achieving 1.16x higher quality. In fact, TeraHAC essentially retains the quality of the celebrated HAC algorithm while significantly improving the running time.

关键词： distributed graph algorithms hierarchical agglomerative clustering parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Enabling Exploratory Large Scale graph Analytics through Arkouda

Enabling Exploratory Large Scale Graph Analytics through Ark...

引用

IEEE High Performance Extreme Computing Conference (HPEC)

作者： Du, Zhihui Rodriguez, Oliver Alvarado Bader, David A. New Jersey Inst Technol Dept Data Sci Newark NJ 07102 USA

ISBN: (纸本)9781665423694

Exploratory graph analytics helps maximize the informational value from a graph. However, increasing graph sizes makes it impossible for existing popular exploratory data analysis tools to handle dozens of terabytes or even larger data sets in the memory of a common laptop/personal computer. Arkouda is a framework under early development that brings together the productivity of Python at the user-side with the high performance of Chapel at the server-side. In this paper, we present our initial work on overcoming the memory limit and high-performance computing coding roadblocks for high-level Python users to perform large graph analyses. Based on a simple and succinct graph data structure, a high-level Chapel-based graph algorithm, Breadth-First Search (BFS), is presented to show the scalable and parallel graph algorithm development method in a productive way through Arkouda. The reverse Cuthill-McKee (RCM) algorithm is implemented in Chapel to relabel the vertices of a graph as a preprocessing step to improve the performance of BFS and one low-level BFS algorithm is also developed to compare with the performance of high-level method. Both synthetic graphs and typical graph benchmarks are used to evaluate the performance of the provided graph algorithms. The experimental results show that, based on the proposed high-level algorithm framework, the performance of BFS can be improved significantly and easily by simply selecting suitable Chapel high-level data structures and parallel constructs. Our code is open source and available from GitHub (https://***/Bader-Research/arkouda).

关键词： Exploratory graph analysis parallel graph algorithms Breadth-First Search High-Performance Computing

来源：评论

学校读者我要写书评

暂无评论

SISA: Set-Centric Instruction Set Architecture for graph Mining on Processing-in-Memory Systems 21

SISA: Set-Centric Instruction Set Architecture for Graph Min...

引用

54th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)

作者： Besta, Maciej Kanakagiri, Raghavendra Kwasniewski, Grzegorz Ausavarungnirun, Rachata Beranek, Jakub Kanellopoulos, Konstantinos Janda, Kacper Vonarburg-Shmaria, Zur Gianinazzi, Lukas Stefan, Ioana Gomez-Luna, Juan Copik, Marcin Kapp-Schwoerer, Lukas Di Girolamo, Salvatore Blach, Nils Konieczny, Marek Mutlu, Onur Hoefler, Torsten Swiss Fed Inst Technol Zurich Switzerland IIT Tirupati Tirupati Andhra Pradesh India King Mongkuts Univ Technol North Bangkok Bangkok Thailand Tech Univ Ostrava Ostrava Czech Republic AGH Univ Sci & Technol Lublin Poland

ISBN: (纸本)9781450385572

Simple graph algorithms such as PageRank have been the target of numerous hardware accelerators. Yet, there also exist much more complex graph mining algorithms for problems such as clustering or maximal clique listing. These algorithms are memory-bound and thus could be accelerated by hardware techniques such as Processing-in-Memory (PIM). However, they also come with non-straightforward parallelism and complicated memory access patterns. In this work, we address this problem with a simple yet surprisingly powerful observation: operations on sets of vertices, such as intersection or union, form a large part of many complex graph mining algorithms, and can offer rich and simple parallelism at multiple levels. This observation drives our cross-layer design, in which we (1) expose set operations using a novel programming paradigm, (2) express and execute these operations efficiently with carefully designed set-centric ISA extensions called SISA, and (3) use PIM to accelerate SISA instructions. The key design idea is to alleviate the bandwidth needs of SISA instructions by mapping set operations to two types of PIM: in-DRAM bulk bitwise computing for bitvectors representing high-degree vertices, and near-memory logic layers for integer arrays representing low-degree vertices. Set-centric SISA-enhanced algorithms are efficient and outperform hand-tuned baselines, offering more than 10x speedup over the established Bron-Kerbosch algorithm for listing maximal cliques. We deliver more than 10 SISA set-centric algorithm formulations, illustrating SISA's wide applicability.

关键词： graph Mining graph Pattern Matching graph Learning Clique Mining Clique Listing Clique Enumeration Subgraph Isomorphism parallel graph algorithms Processing In Memory Processing Near Memory graph Accelerators Instruction Set Architecture

来源：评论

学校读者我要写书评

暂无评论

Towards scaling community detection on distributed-memory heterogeneous systems

引用

parallel COMPUTING 2022年 111卷

作者： Gawande, Nitin Ghosh, Sayan Halappanavar, Mahantesh Tumeo, Antonino Kalyanaraman, Ananth Pacific Northwest Natl Lab Richland WA 99352 USA Washington State Univ Pullman WA 99164 USA Intel Corp Santa Clara CA USA PNNL Richland WA USA

In most real-world networks, nodes/vertices tend to be organized into tightly-knit modules known as communities or clusters such that nodes within a community are more likely to be connected or related to one another than they are to the rest of the network. Community detection in a network (graph) is aimed at finding a partitioning of the vertices into communities. The goodness of the partitioning is commonly measured using modularity. Maximizing modularity is an NP-complete problem. In 2008, Blondel et al. introduced a multi-phase, multi-iteration heuristic for modularity maximization called the Louvain method. Owing to its speed and ability to yield high quality communities, the Louvain method continues to be one of the most widely used tools for serial community detection. Distributed multi-GPU systems pose significant challenges and opportunities for efficient execution of parallel applications. graph algorithms, in particular, have been known to be harder to parallelize on such platforms, due to irregular memory accesses, low computation to communication ratios, and load balancing problems that are especially hard to address on multi-GPU systems. In this paper, we present our ongoing work on distributed-memory implementation of Louvain method on heterogeneous systems. We build on our prior work parallelizing the Louvain method for community detection on traditional CPU-only distributed systems without GPUs. Corroborated by an extensive set of experiments on multi-GPU systems, we demonstrate competitive performance to existing distributed-memory CPU-based implementation, up to 3.2x speedup using 16 nodes of OLCF Summit relative to two nodes, and up to 19x speedup relative to the NVIDIA RAPIDS (R) CUgraph (R) implementation on a single NVIDIA V100 GPU from DGX-2 platform, while achieving high quality solutions comparable to the original Louvain method. To the best of our knowledge, this work represents the first effort for community detection on distributed mult

关键词： Distributed community detection Heterogeneous systems Multi-GPU parallel Louvain parallel graph algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel Batch-Dynamic graph Connectivity 19

Parallel Batch-Dynamic Graph Connectivity

引用

31st ACM Symposium on parallelism in algorithms and Architecturess (SPAA)

作者： Acar, Umut A. Anderson, Daniel Blelloch, Guy E. Dhulipala, Laxman Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450361842

In this paper, we study batch parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in the sequential setting. The best sequential algorithm for dynamic connectivity is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves O(1g(2) n) amortized time per edge insertion or deletion, and O(1g n) time per query. We design a parallel batch-dynamic connectivity algorithm that is work-efficient with respect to the HDT algorithm for small batch sizes, and is asymptotically faster when the average batch size is sufficiently large. Given a sequence of batched updates, where A is the average batch size of all deletions, our algorithm achieves O(1g n lg(1 + n/A)) expected amortized work per edge insertion and deletion and O (1g(3) n) depth w.h.p. Our algorithm answers a batch of k connectivity queries in O(k lg(1 + n/ k)) expected work and O(1g n) depth w.h.p. To the best of our knowledge, our algorithm is the first parallel batch-dynamic algorithm for connectivity.

关键词： parallel graph algorithms graph connectivity dynamic graph algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A performance predictor for implementation selection of parallelized static and temporal graph algorithms

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2022年第2期34卷

作者： Rehman, Akif Ahmad, Masab Khan, Omer Univ Connecticut Elect & Comp Engn Storrs CT USA

Task-based execution of graph workloads allows various ordered and unordered implementations, with tasks representing dependencies between graph vertices and edges. This work explores graph algorithms in the context of ordered and unordered task-based implementations, that trade-off work-efficiency with parallelism. The monotonicity of convergent graph solutions is the reason behind the trade-off between work-efficiency and parallelism. This trade-off results in variable performance-based choices within and across different machines (CPUs and GPUs), graph algorithms, implementations (ordered, relaxed, and unordered). Input graphs also augment this choice space, with this work analyzing temporally changing graphs in addition to the static graphs explored by prior works. These algorithmic and architectural choices are first explored in this work, and it is seen that different graph workload-input combinations perform optimally on diverse architectural configurations. The resulting choice space is analyzed and this work represents it in the form of characteristic variables that correlate with each choice space. Using these characteristic variables, this work proposes analytical and neural network models to correlate these choice spaces to find the best performing implementation. The variables and the prediction models proposed in this work are also integrated with a state-of-the-art performance predictor on a multiaccelerator setup, and shows geometric performance gains of 54% on a CPU, 14% on a GPU, and 31.5% in a multiaccelerator setup over baseline implementations without performance prediction.

关键词： ordered algorithms parallel graph algorithms temporal graphs unordered algorithms

来源：评论

学校读者我要写书评

暂无评论

GOSH: Embedding Big graphs on Small Hardware 20

GOSH: Embedding Big Graphs on Small Hardware

引用

49th International Conference on parallel Processing (ICPP)

作者： Akyildiz, Taha Atahan Aljundi, Amro Alabsi Kaya, Kamer Sabanci Univ Istanbul Turkey

ISBN: (纸本)9781450388160

In graph embedding, the connectivity information of a graph is used to represent each vertex as a point in a d-dimensional space. Unlike the original, irregular structural information, such a representation can be used for a multitude of machine learning tasks. Although the process is extremely useful in practice, it is indeed expensive and unfortunately, the graphs are becoming larger and harder to embed. Attempts at scaling up the process to larger graphs have been successful but often at a steep price in hardware requirements. We present Gosh, an approach for embedding graphs of arbitrary sizes on a single GPU with minimum constraints. Gosh utilizes a novel graph coarsening approach to compress the graph and minimize the work required for embedding, delivering high-quality embeddings at a fraction of the time compared to the state-of-the-art. In addition to this, it incorporates a decomposition schema that enables any arbitrarily large graph to be embedded using a single GPU with minimum constraints on the memory size. With these techniques, Gosh is able to embed a graph with over 65 million vertices and 1.8 billion edges in less than an hour on a single GPU and obtains a 93% AUCROC for link-prediction which can be increased to 95% by running the tool for 80 minutes.

关键词： graph embedding GPU parallel graph algorithms graph coarsening link prediction

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：