Abstract

Parallel graph algorithms continue to attract a lot of research attention given their applications to several fields of sciences and engineering. Efficient design and implementation of graph algorithms on modern manycore accelerators has to however contend with a host of challenges including not being able to reach full memory system throughput and irregularity. Of late, focusing on real-world graphs, researchers are addressing these challenges by using decomposition and preprocessing techniques guided by the structural properties of such graphs. In this direction, we present a new GPU algorithm for obtaining an ear decomposition of a graph. Our implementation of the proposed algorithm on an NVidia Tesla K40c improves the state-of-the-art by a factor of 2.3x on average on a collection of real-world and synthetic graphs. The improved performance of our algorithm is due to our proposed characterization that identifies edges of the graph as redundant for the purposes of an ear decomposition. We then study an application of the ear decomposition of a graph in computing the betweenness-centrality values of nodes in the graph. We use an ear decomposition of the input graph to systematically remove nodes of degree two. The actual computation of betweenness-centrality is done on the remaining nodes and the results are extended to nodes removed in the previous step. We show that this approach improves the state-of-the-art for computing betweenness-centrality on an NVidia K40c GPU by a factor of 1.9x on average over a collection of real-world graphs.

Abstract

Graph algorithms play a prominent role in several fields of sciences and engineering. Notable among them are graph traversal, finding the connected components of a graph, and computing shortest paths. There are several efficient implementations of the above problems on a variety of modern multiprocessor architectures. It can be noticed in recent times that the size of the graphs that correspond to real world datasets has been increasing. Parallelism offers only a limited succor to this situation as current parallel architectures have severe short-comings when deployed for most graph algorithms. At the same time, these graphs are also getting very sparse in nature. This calls for particular solution strategies aimed at processing large, sparse graphs on modern parallel architectures.

Abstract

Multiplying two sparse matrices, denoted spmm, is a fundamental operation in linear algebra with several applications. Hence, efficient and scalable implementation of spmm has been a topic of immense research. Recent efforts are aimed at implementations on GPUs, multicore architectures, FPGAs, and such emerging computational platforms. Owing to the highly irregular nature of spmm, it is observed that GPUs and CPUs can offer comparable performance. In this paper, we study CPU+GPU heterogeneous algorithms for spmm where the matrices exhibit a scale-free nature. Focusing on such matrices, we propose an algorithm that multiplies two sparse matrices exhibiting scale-free nature on a CPU+GPU heterogeneous platform. Our experiments on a wide variety of real-world matrices from standard datasets show an average of 25% improvement over the best possible algorithm on a CPU+GPU heterogeneous platform. We show that our approach is both architecture-aware, and workload-aware.

Abstract

In this work we show that given a set S of n points with coordinates on an n × n grid, we can construct data structures for (i) reporting and (ii) counting the maximal points in an axes-parallel query rectangle in sub-logarithmic time. We assume our model of computation to be the word RAM with size of each word being log n bits.

Abstract

We present output sensitive techniques for the generalized reporting versions of the planar range maxima problem and the planar range convex hull problem. Our solutions are in the pointer machine model, for orthogonal range queries on a static point set. We solve the planar range maxima problem for two-sided, three-sided and four-sided queries. We achieve a query time of O(logn + c) using O(n) space for the two-sided case, where n denotes the number of stored points and c the number of colors reported. For the three-sided case, we achieve query time O(log2 n + clogn) using O(n) space while for four-sided queries we answer queries in O(log3 n + clog2 n) using O(nlogn) space. For the planar range convex hull problem, we provide a solution that answers queries in O(log2 n + clogn) time, using O(nlog2 n) space.

Abstract

In this work, we consider the problem of finding the closest pair (in L 1 metric) of points in an orthogonal query rectangle. Given a set of n static points on a U× U grid, we preprocess these points into a data structure of size O (m f (m) log 2 m) that can be queried in time O ((g (m)+ log log m) log 3 m), for m= O (n log U) and (i) f (m)= O (1) and g (m)= O (log ε m);(ii) f (m)= O (log log m) and g (m)= O (log log m);(iii) f (m)= O (log ε m) and g (m)= O (1). Here ε: 0< ε< 1 is a small but arbitrary constant.

Abstract

A t-ruling set of a graph G=(V, E) is a vertex-subset S⊆ V that is independent and satisfies the property that every vertex v∈ V is at a distance of at most t hops from some vertex in S. A maximal independent set (MIS) is a 1-ruling set. Extending results from Kothapalli et al.(FSTTCS 2012) this note presents a randomized algorithm for computing, with high probability, a t-ruling set in O (t⋅ log 1/(t-1) n) rounds for 2< t≤√(log log n) and in (O (√(log log n))) rounds for t>√(log log n).

Abstract

Range searching is a primal problem in computational geometry with applications to database systems, mobile computing, geographical information systems, and the like. Defined simply, the problem is to preprocess a given a set of points in a d-dimensional space so that the points that lie inside an orthogonal query rectangle can be efficiently reported. Many practical applications of range trees require one to process a massive amount of points and a massive number of queries. In this context, we propose an efficient parallel implementation of range trees on manycore architectures such as GPUs. We extend our implementation to query processing. While queries can be batched together to exploit interquery parallelism, we also utilize intra-query parallelism. This inter- and intra-query parallelism greatly reduces the per query latency thereby increasing the throughput. On an input of 1 M points in a 2-dimensional space, our implementation on a single Nvidia GTX 580 GPU for constructing a range tree shows an improvement of 12X over a 12-threaded CPU implementation. We also achieve an average throughput of 10 M queries per second for answering 4 M queries on a range tree containing 1 M points on a Nvidia GTX 580 GPU. We extend our implementation to an application where we seek to report the set of maximal points in a given orthogonal query rectangle.

Abstract

Multiplying a sparse matrix with a vector, denoted spmv, is a fundamental operation in linear algebra with several applications. Hence, efficient and scalable implementation of spmv has been a topic of immense research. Recent efforts are aimed at implementations on GPUs, multicore architectures, and such emerging computational platforms. Owing to the highly irregular nature of spmv, it is observed that GPUs and CPUs can offer comparable performance.

Abstract

GPUs with their massive Single Instruction Multiple Data (SIMD) capability have become attractive for scientific computation. The Kirchhoff-Helmholtz Transform (KHT) is a two dimensional integral commonly used in numerical reconstruction of the object from its experimentally measured diffraction pattern (called hologram). We explore the evaluation of KHT using GPU at various levels of optimisation. These optimisations are of two types:(a) algorithmic: exploiting the symmetries inherent in KHT, and (b) programmatic: optimizations that are specific to the GPU architecture like the lookup tables, scheduling of read/writes. From the numerical experiments, we report the speedup for each level of optimisation.