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

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

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 data sets 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 work efficient solutions aimed at processing large, sparse graphs on modern parallel architectures. In this paper, we introduce graph pruning as a technique that aims to reduce the size of the graph. Certain elements of the graph can be pruned depending on the nature of the computation. Once a solution is obtained for the pruned graph, the solution is extended to the entire graph. We apply the above technique on three fundamental graph algorithms: breadth first search (BFS), Connected Components (CC), and All Pairs Shortest Paths (APSP). To validate our technique, we implement our algorithms on a heterogeneous platform consisting of a multicore CPU and a GPU. On this platform, we achieve an average of 35% improvement compared to state-ofthe-art solutions. Such an improvement has the potential to speed up other applications that rely on these algorithms.

Abstract

Distributed algorithms for computing a maximal independent set of a graph have been very popular in the research community. Starting with the algorithm of Luby dating back to 25 years, several researchers have focused on distributed MIS algorithms for general graphs. with little success. Only recently, M'etevier et al. have proposed an algorithm for MIS in the distributed setting with a round complexity that matches Luby's algorithm asymptotically. However, very little is known about the relative performance of the algorithm of Luby and M'etevier in practice. Such a study can throw light on some aspects of the algorithms that are not brought out by a theoretical analysis. In this paper, we compare implementations of the algorithm of Luby and M'etevier and study their behavior on a class of random graphs and bipartite graphs. Further, we study how varying the probability that a node wishes to join the MIS in the case of Luby's algorithm affects the number of rounds required.

Abstract

The shared whiteboard model for distributed computing is one of the recent interesting models to be proposed (See Becker et al. (SPAA 2012)). In its basic form, this model allows all nodes to write a message of no more than O(log n) bits on a whiteboard that every node can read. However, each node can write at most once. In this model, a variety of problems from graphs are shown to be either possible or impossible. In this paper we extend the work of Becker et al. to allow for nodes to write on the shared whiteboard more than once. However, each node can write at most O(log n) bits at any one instant. Interestingly, in this model, we show that allowing just two rounds of writing on the whiteboard, one can color the vertices of a d-degenerate graph using d+1 colors. Similarly, we show that two rounds suffice to find maximal independent set (MIS), whereas 2-ruling sets can be computed in one round in simultaneous synchronous models. Finally, we show that for finding connected components in a graph, even O(1) rounds is not enough in general. We show that any deterministic algorithm that follows certain rules requires at least Omega(log nlog log n) rounds to find the connected components of an n-vertex graph. At the same time, we show the existence of a O(log n) round algorithm for the same. Thus, our results indicate that the multi-round shared whiteboard model has interesting consequences.

Abstract

We consider the problem of reporting convex hull points in an orthogonal range query in two dimensions. Formally, let $ P $ be a set of $ n $ points in $\mathbb {R}^{2} $. A point lies on the convex hull of a point set $ S $ if it lies on the boundary of the minimum convex polygon formed by $ S $. In this paper, we are interested in finding the points that lie on the boundary of the convex hull of the points in $ P $ that also fall with in an orthogonal range $[x_ {lt}, x_ {rt}]\times {}[y_b, y_t] $. We propose a $ O (n\log^{2} n) $ space data structure that can support reporting points on a convex hull inside an orthogonal range query, in time $ O (\log^{3} n+ h) $. Here $ h $ is the size of the output. This work improves the result of (Brass et al. 2013)\cite {brass} that builds a data structure that uses $ O (n\log^{2} n) $ space and has a $ O (\log^{5} n+ h) $ query time. Additionally, we show that our data structure can be modified slightly to solve other related problems. For instance, for counting the number of points on the convex hull in an orthogonal query rectangle, we propose an $ O (n\log^{2} n) $ space data structure that can be queried upon in $ O (\log^{3} n) $ time. We also propose a $ O (n\log^{2} n) $ space data structure that can compute the $ area $ and $ perimeter $ of the convex hull inside an orthogonal range query in $ O (\log^{3} n $) time.

Abstract

Sorting has been a topic of immense research value since the inception of Computer Science. Hybrid computing on multicore architectures involves computing simultaneously on a tightly coupled heterogeneous collection of devices. In this work, we consider a multicore CPU along with a many core GPU as our experimental hybrid platform. In this work, we present a hybrid comparison based sorting algorithm which utilizes a many-core GPU and a multi-core CPU to perform sorting. The algorithm is broadly based on splitting the input list according to a large number of splitters followed by creating independent sub lists. Sorting the independent sub lists results in sorting the entire original list. On a CPU+GPU platform consisting of an Intel i7 980 and an Nvidia GTX 580, our algorithm achieves a 20% gain over the current best known comparison sort result that was published by Davidson et. al. [In Par 2012]. On the above experimental platform, our results are better by 40% on average over a similar GPU-alone algorithm proposed by Leischner et. al. [IPDPS 2010]. Our results also show that our algorithm and its implementation scale with the size of the input. We also show that such performance gains can be obtained on other hybrid CPU+GPU platforms.

Abstract

This paper initiates formal analysis of a simple, distributed algorithm for community detection on networks. We analyze an algorithm that we call Max-LPA, both in terms of its convergence time and in terms of the “quality” of the communities detected. Max-LPA is an instance of a class of community detection algorithms called label propagation algorithms. As far as we know, most analysis of label propagation algorithms thus far has been empirical in nature and in this paper we seek a theoretical understanding of label propagation algorithms. In our main result, we define a clustered version of Erdös-Rényi random graphs with clusters V 1, V 2, …, V k where the probability p, of an edge connecting nodes within a cluster V i is higher than p′, the probability of an edge connecting nodes in distinct clusters. We show that even with fairly general restrictions on p and p′ ( p=Ω(1n1/4−ϵ) for any ε > 0, p′ = O(p 2), where n is the number of nodes), Max-LPA detects the clusters V 1, V 2, …, V n in just two rounds. Based on this and on empirical results, we conjecture that Max-LPA can correctly and quickly identify communities on clustered Erdös-Rényi graphs even when the clusters are much sparser, i.e., with p=clognn for some c > 1.

Abstract

We consider the planar convex hull range query problem. Let P be a set of points in the plane. We preprocess these points into a data structure such that given an orthogonal range query, we can report the convex hull of the points in the range in O (log2 n+ h) time, where h is the size of the output. The data structure uses O (n log n) space. This improves the previous bound of O (log5 n+ h) time and O (n log2 n) space. Given a range query, it also supports extreme points in a given direction, tangent queries through a given point, and line-hull intersection queries on the points in the range in time O (log2 n) for each orthogonal query and O (log n) time for each additional query on that range. These problems have not been studied before.

Abstract

Sparse matrix-sparse/dense matrix multiplications, spgemm and csrmm, respectively, among other applications find usage in various matrix formulations of graph problems. Considering the difficulties in executing graph problems and the duality between graphs and matrices, computations such as spgemm and csrmm have recently caught the attention of HPC community. These computations pose challenges such as load balancing, irregular nature of the computation, and difficulty in predicting the output size. It is even more challenging when combined with the GPU architectural constraints such as memory accesses, limited shared memory, strict SIMD and thread execution. To address these challenges on a GPU, we evaluate three possible variations of matrix multiplication (Row-Column, Column-Row, Row-Row) and perform suitable optimizations targeted at sparse matrices. Our experiments indicate that the Row-Row formulation, which mostly outperforms the other formulations, is 3.5x faster on average compared to an optimized multi-core implementation in the Intel MKL library. We extend the Row-Row formulation to a CPU+GPU hybrid algorithm that simultaneously utilizes the CPU also. In this direction, we present heuristics to find the right amount of work division between the CPU and the GPU. Our hybrid row-row formulation of the spgemm operation performs 5.5x faster on average when compared to the optimized multi-core implementation in the Intel MKL library. Our experience indicates that it is difficult to identify right amount of work division between the CPU and the GPU. We therefore investigate a subclass of sparse matrices, band matrices, and present an analytical method to identify a good work division when multiplying two band matrices. Our GPU csrmm operation performs 2.5x faster on average when compared to a corresponding implementation in the cusparse library, which outperforms the Intel MKL library implementation.