Network-Oblivious Algorithms
Lists
Only you see this
Abstract
A framework is proposed for the design and analysis of network-oblivious algorithms, namely algorithms that can run unchanged, yet efficiently, on a variety of machines characterized by different degrees of parallelism and communication capabilities. The framework prescribes that a network-oblivious algorithm be specified on a parallel model of computation where the only parameter is the problem’s input size, and then evaluated on a model with two parameters, capturing parallelism granularity and communication latency. It is shown that for a wide class of network-oblivious algorithms, optimality in the latter model implies optimality in the decomposable bulk synchronous parallel model, which is known to effectively describe a wide and significant class of parallel platforms. The proposed framework can be regarded as an attempt to port the notion of obliviousness, well established in the context of cache hierarchies, to the realm of parallel computation. Its effectiveness is illustrated by providing optimal network-oblivious algorithms for a number of key problems. Some limitations of the oblivious approach are also discussed.
BibTeX
@article{bilardi2016network,
author = {Gianfranco Bilardi and Andrea Pietracaprina and Geppino Pucci and Michele Scquizzato and Francesco Silvestri},
title = {{Network-Oblivious Algorithms}},
journal = {J. ACM},
year = {2016},
doi = {10.1145/2812804},
}| Efficient Resource Oblivious Algorithms for Multicores | arXiv · 2011 |
| Architecture Independent Analysis of Parallel Programs | International Conference on Computational Science · 2001 |
| Locality | arXiv · 2019 |
| Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication | arXiv · 2019 |
| Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers | arXiv · 2017 |
| Parallelepipeds obtaining HBL lower bounds | arXiv · 2016 |