In the era of big data and cloud computing, large amounts of data are generated from user applications and need to be processed in the datacenter. Dataparallel computing frameworks, such as Apache Spark, are widely used to perform such data processing at scale. Specifically, Spark leverages distributed memory to cache the intermediate results, represented as Resilient Distributed Datasets (RDDs). This gives Spark an advantage over other parallel frameworks for implementations of iterative machine learning and data mining algorithms, by avoiding repeated computation or hard disk accesses to retrieve RDDs. By default, caching decisions are left at the programmer’s discretion, and the LRU policy is used for evicting RDDs when the cache is full. However, when the objective is to minimize total work, LRU is woefully inadequate, leading to arbitrarily suboptimal caching decisions. In this paper, we design an algorithm for multistage big data processing platforms to adaptively determine and cache the most valuable intermediate datasets that can be reused in the future. Our solution automates the decision of which RDDs to cache: this amounts to identifying nodes in a direct acyclic graph (DAG) representing computations whose outputs should persist in the memory. Our experiment results show that our proposed cachemore »
Fast Stencil Computations using Fast Fourier Transforms
Stencil computations are widely used to simulate the change of state of physical systems across a multidimensional grid over multiple timesteps. The stateoftheart techniques in this area fall into three groups: cacheaware tiled looping algorithms, cacheoblivious divideandconquer trapezoidal algorithms, and Krylov subspace methods.
In this paper, we present two efficient parallel algorithms for performing linear stencil computations. Current direct solvers in this domain are computationally inefficient, and Krylov methods require manual labor and mathematical training. We solve these problems for linear stencils by using DFT preconditioning on a Krylov method to achieve a direct solver which is both fast and general. Indeed, while all currently available algorithms for solving general linear stencils perform Θ(NT) work, where N is the size of the spatial grid and T is the number of timesteps, our algorithms perform o(NT) work.
To the best of our knowledge, we give the first algorithms that use fast Fourier transforms to compute final grid data by evolving the initial data for many timesteps at once. Our algorithms handle both periodic and aperiodic boundary conditions, and achieve polynomially better performance bounds (i.e., computational complexity and parallel runtime) than all other existing solutions.
Initial experimental results show that implementations of our algorithms that more »
 Publication Date:
 NSFPAR ID:
 10298518
 Journal Name:
 Annual ACM Symposium on Parallelism in Algorithms and Architectures
 ISSN:
 15486109
 Sponsoring Org:
 National Science Foundation
More Like this


In this paper we describe a new parallel algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint k. This algorithm achieves the optimal 11/e approximation guarantee and is orders of magnitude faster than the stateoftheart on a variety of experiments over realworld data sets. Following recent work by Balkanski & Singer (2018a), there has been a great deal of research on algorithms whose theoretical parallel runtime is exponentially faster than algorithms used for sub modular maximization over the past 40 years. However, while these new algorithms are fast in terms of asymptotic worstcase guarantees, it is computationally infeasible to use them in practice even on small data sets because the number of rounds and queries they require depend on large constants and highdegree polynomials in terms of precision and confidence. The design principles behind the FAST algorithm we present here are a significant departure from those of recent theoretically fast algorithms. Rather than optimize for asymptotic theoretical guarantees, the design of FAST introduces several new techniques that achieve remarkable practical and theoretical parallel runtimes. The approximation guarantee obtained by FAST is arbitrarily close to 11/e, and its asymptotic parallel runtime (adaptivity) ismore »

Counting the frequency of subgraphs in large networks is a classic research question that reveals the underlying substructures of these networks for important applications. However, subgraph counting is a challenging problem, even for subgraph sizes as small as five, due to the combinatorial explosion in the number of possible occurrences. This article focuses on the fivecycle, which is an important special case of fivevertex subgraph counting and one of the most difficult to count efficiently. We design two new parallel fivecycle counting algorithms and prove that they are work efficient and achieve polylogarithmic span. Both algorithms are based on computing low outdegree orientations, which enables the efficient computation of directed twopaths and threepaths, and the algorithms differ in the ways in which they use this orientation to eliminate doublecounting. Additionally, we present new parallel algorithms for obtaining unbiased estimates of fivecycle counts using graph sparsification. We develop fast multicore implementations of the algorithms and propose a work scheduling optimization to improve their performance. Our experiments on a variety of realworld graphs using a 36core machine with twoway hyperthreading show that our best exact parallel algorithm achieves 10–46× selfrelative speedup, outperforms our serial benchmarks by 10–32×, and outperforms the previous stateoftheartmore »

The Sylvester equation offers a powerful and unifying primitive for a variety of important graph mining tasks, including network alignment, graph kernel, node similarity, subgraph matching, etc. A major bottleneck of Sylvester equation lies in its high computational complexity. Despite tremendous effort, stateoftheart methods still require a complexity that is at least \em quadratic in the number of nodes of graphs, even with approximations. In this paper, we propose a family of Krylov subspace based algorithms (\fasten) to speed up and scale up the computation of Sylvester equation for graph mining. The key idea of the proposed methods is to project the original equivalent linear system onto a Kronecker Krylov subspace. We further exploit (1) the implicit representation of the solution matrix as well as the associated computation, and (2) the decomposition of the original Sylvester equation into a set of intercorrelated Sylvester equations of smaller size. The proposed algorithms bear two distinctive features. First, they provide the \em exact solutions without any approximation error. Second, they significantly reduce the time and space complexity for solving Sylvester equation, with two of the proposed algorithms having a \em linear complexity in both time and space. Experimental evaluations on a diverse setmore »

Purpose The purpose of this paper is as follows: to significantly reduce the computation time (by a factor of 1,000 and more) compared to known numerical techniques for realworld problems with complex interfaces; and to simplify the solution by using trivial unfitted Cartesian meshes (no need in complicated mesh generators for complex geometry). Design/methodology/approach This study extends the recently developed optimal local truncation error method (OLTEM) for the Poisson equation with constant coefficients to a much more general case of discontinuous coefficients that can be applied to domains with different material properties (e.g. different inclusions, multimaterial structural components, etc.). This study develops OLTEM using compact 9point and 25point stencils that are similar to those for linear and quadratic finite elements. In contrast to finite elements and other known numerical techniques for interface problems with conformed and unfitted meshes, OLTEM with 9point and 25point stencils and unfitted Cartesian meshes provides the 3rd and 11th order of accuracy for irregular interfaces, respectively; i.e. a huge increase in accuracy by eight orders for the new 'quadratic' elements compared to known techniques at similar computational costs. There are no unknowns on interfaces between different materials; the structure of the global discrete system is themore »