Heterogeneous systems present exciting new opportunities for graph and Machine Learning applications. This paper presents a novel approach for the All-pairs Shortest Path (APSP) computation using a heterogeneous CPU-F...
详细信息
ISBN:
(纸本)9781665494663
Heterogeneous systems present exciting new opportunities for graph and Machine Learning applications. This paper presents a novel approach for the All-pairs Shortest Path (APSP) computation using a heterogeneous CPU-FPGA Accelerator system. It is based on a recursive variant of Kleene's APSP algorithm. Carefully re-engineering the algorithm to exploit parallelism in both the Floyd-Warshall algorithm and the general Kleene algorithm to perform Floyd-Warshall and Matrix-Multiply on the FPGA while the CPU efficiently balances the communication and computation between the kernels, improves state-of-the-art performance on FPGAs for APSP, while achieving near-GPU levels of performance, with less power and hardware resources, and outperforms the CPU-only solution by over 137x for a 8192x8192 problem size. When adjusted for power draw differences in process nodes, it also surpasses the GPU implementation in terms of performance per Watt by over 13%.
作者：
Mao, XiaoMIT
Dept Elect Engn & Comp Sci Cambridge MA 02139 USA
The (unweighted) tree edit distance problem for n node trees asks to compute a measure of dissimilarity between two rooted trees with node labels. The current best algorithm from more than a decade ago runs in O(n(3))...
详细信息
ISBN:
(纸本)9781665420556
The (unweighted) tree edit distance problem for n node trees asks to compute a measure of dissimilarity between two rooted trees with node labels. The current best algorithm from more than a decade ago runs in O(n(3)) time [Demaine, Mozes, Rossman, and Weimann, ICALP 2007]. The same paper also showed that O(n(3)) is the best possible running time for any algorithm using the so-called decomposition strategy, which underlies almost all the known algorithms for this problem. These algorithms would also work for the weighted tree edit distance problem, which cannot be solved in truly sub-cubic time under the APSP conjecture [Bringmann, Gawrychowski, Mozes, and Weimann, SODA 2018]. In this paper, we break the cubic barrier by showing an O(n(2.9546)) time algorithm for the unweighted tree edit distance problem. We consider an equivalent maximization problem and use a dynamic programming scheme involving matrices with many special properties. By using a decomposition scheme as well as several combinatorial techniques, we reduce tree edit distance to the max-plus product of bounded-difference matrices, which can be solved in truly sub-cubic time [Bringmann, Grandoni, Saha, and Vassilevska Williams, FOCS 2016].
Many real-world applications operate on dynamic graphs that undergo rapid changes in their topological structure over time. However, it is challenging to design dynamic algorithms that are capable of supporting such g...
详细信息
ISBN:
(纸本)9781450392495
Many real-world applications operate on dynamic graphs that undergo rapid changes in their topological structure over time. However, it is challenging to design dynamic algorithms that are capable of supporting such graph changes efficiently. To circumvent the challenge, we propose a batch-dynamic framework for answering distance queries, which combines offline labelling and online searching to leverage the advantages from both sides - accelerating query processing through a partial distance labelling that is of limited size but provides a good approximation to bound online searches. We devise batch-dynamic algorithms to dynamize a distance labelling efficiently in order to reflect batch updates on the underlying graph. In addition to providing theoretical analysis for the correctness, labelling minimality, and computational complexity, we have conducted experiments on 14 real-world networks to empirically verify the efficiency and scalability of the proposed algorithms.
The graphBLAS are building blocks for constructing graph algorithms as linear algebra. They are defined mathematically with the goal that they would eventually map onto a variety of programming languages. Today they e...
详细信息
ISBN:
(纸本)9781665497473
The graphBLAS are building blocks for constructing graph algorithms as linear algebra. They are defined mathematically with the goal that they would eventually map onto a variety of programming languages. Today they exist in C, C++, Python, MATLAB (R), and Julia. In this paper, we describe the graphBLAS for the Go programming language. A particularly interesting aspect of this work is that using the concurrency features of the Go language, we aim to build a runtime system that uses the graphBLAS nonblocking mode by default.
Triangle Counting (TC) is a basic graph mining problem with numerous applications. However, the large size of real-world graphs has a severe effect on TC performance. This paper studies the TC algorithm from the persp...
详细信息
ISBN:
(纸本)9781450392044
Triangle Counting (TC) is a basic graph mining problem with numerous applications. However, the large size of real-world graphs has a severe effect on TC performance. This paper studies the TC algorithm from the perspective of memory utilization. We investigate the implications of the skewed degree distribution of real-world graphs on TC and make novel observations on how memory locality is negatively affected. Based on this, we introduce the LOTUS algorithm as a structure-aware TC that optimizes locality. The evaluation on 14 real-world graphs with up to 162 billion edges and on 3 different processor architectures of up to 128 cores shows that Lotus is 2.2-5.5x faster than previous works.
We show that some natural problems that are XNLP-hard (hence W[t]-hard for all t) when parameterized by pathwidth or treewidth, become FPT when parameterized by stable gonality, a novel graph parameter based on optima...
详细信息
ISBN:
(数字)9783031159145
ISBN:
(纸本)9783031159145;9783031159138
We show that some natural problems that are XNLP-hard (hence W[t]-hard for all t) when parameterized by pathwidth or treewidth, become FPT when parameterized by stable gonality, a novel graph parameter based on optimal maps from graphs to trees. The problems we consider are classical flow and orientation problems, such as UNDIRECTED FLOW WITH LOWER BOUNDS, MINIMUM MAXIMUM OUTDEGREE, and capacitated optimization problems such as CAPACITATED (RED-BLUE) DOMINATING SET. Our hardness claims beat existing results. The FPT algorithms use a new parameter "treebreadth", associated to a weighted tree partition, as well as DP and ILP.
We introduce the Structure-Aware Parallel Counting (SAPCo) Sort algorithm that optimizes performance of degree-ordering, a key operation in graph analytics. SAPCo leverages the skewed degree distribution to accelerate...
详细信息
ISBN:
(纸本)9781665459549
We introduce the Structure-Aware Parallel Counting (SAPCo) Sort algorithm that optimizes performance of degree-ordering, a key operation in graph analytics. SAPCo leverages the skewed degree distribution to accelerate sorting. The evaluation for graphs of up to 3.6 billion vertices shows that SAPCo sort is, on average, 1.7-33.5 times faster than state-of-the-art sorting algorithms such as counting sort, radix sort, and sample sort.
A subset M subset of E of edges of a graph G = (V, E) is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called a uniquely restricted matching if, G[V (M)], the subgraph of G...
详细信息
A subset M subset of E of edges of a graph G = (V, E) is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called a uniquely restricted matching if, G[V (M)], the subgraph of G induced by the set of M-saturated vertices of G contains exactly one perfect matching. A uniquely restricted matching M is maximal if M is not properly contained in any uniquely restricted matching of G. Given a graph G, the MIN-MAX-UR MATCHING problem asks to find a maximal uniquely restricted matching in G of minimum cardinality and DECIDE-MIN-MAX-UR MATCHING problem, the decision version of this problem takes a graph G and an integer k and asks whether G admits a maximal uniquely restricted matching of cardinality at most k. It is known that the DECIDE-MIN-MAX-UR MATCHING problem is NP-complete. In this paper, we strengthen this result by proving that the DECIDE-MIN-MAX-UR MATCHING problem remains NP-complete for chordal bipartite graphs, star-convex bipartite graphs, chordal graphs, and doubly chordal graphs. On the positive side, we prove that the MIN-MAX-UR MATCHING problem is polynomial time solvable for bipartite distance-hereditary graphs and linear time solvable for bipartite permutation graphs, proper interval graphs, and threshold graphs. Finally, we prove that the MIN-MAX-UR MATCHING problem is APX-complete for graphs with maximum degree 4. (C) 2021 Elsevier B.V. All rights reserved.
Given a graph, a sparsification is a smaller graph which approximates or preserves some property of the original graph. Well-known sparsifications include but are not limited to spanning trees (preserving connectivity...
详细信息
Given a graph, a sparsification is a smaller graph which approximates or preserves some property of the original graph. Well-known sparsifications include but are not limited to spanning trees (preserving connectivity), Steiner trees and forests (preserving connectivity between certain vertices or vertex pairs), spanners and emulators (preserving distances up to given error), distance preservers, cut and spectral sparsifiers, and variants of these. Sparsifications have application in many network design problems including multimedia and electrical power distribution, multicast routing, motion planning, computing approximate all-pairs shortest paths, computational biology, and graph visualization. We first develop several theoretical results involving additive spanners in weighted graphs. An additive +β spanner is a subgraph which preserves distances in the original graph up to +β additive error; such spanners were largely only studied in unweighted graphs. By generalizing an initialization technique and neighborhood lemma, additive spanners in weighted graphs can be constructed with nearly the same size bounds as in unweighted graphs. We then develop a similar neighborhood lemma to construct lightweight additive spanners which aim to minimize total edge weight instead of number of edges. One persistent issue in the above sparsifications involves the underlying graph itself: important vertices (such as traffic hubs in a transportation network, or influential users in a social network) are essentially indistinguishable from less important vertices. We then consider multi-priority generalizations of the above problems where vertices possess different priority, level, or Quality of Service (QoS) requirements, in which higher-priority vertices require higher-quality connections between them. We mainly study this generalization applied to the Steiner tree and node-weighted Steiner tree problems, but this notion can be extended to other sparsifications including spanners.
We develop a systematic way of constructing S-Ricci flat graphs which are not Abelian Cayley via graph bundle with explicit examples. For this purpose, we prove that, with some natural constrains, a non-trivial graph ...
详细信息
暂无评论