Network-oblivious algorithms

DOI10.1145/2812804zbMATH Open1426.68091arXiv1404.3318OpenAlexW2314666169MaRDI QIDQ3177760FDOQ3177760

Authors: Gianfranco Bilardi, Andrea Pietracaprina, Geppino Pucci, Michele Scquizzato, Francesco Silvestri 

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: A framework is proposed for the design and analysis of emph{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 BSP 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.

Full work available at URL: https://arxiv.org/abs/1404.3318

Recommendations

• Oblivious algorithms for multicores and networks of processors
• scientific article; zbMATH DE number 2011837
• Parallel algorithms for routing in nonblocking networks
• An optimal time bound for oblivious routing
• Tight bounds for oblivious routing in the hypercube

zbMATH Keywords

communicationparallel algorithmsmodels of computationoblivious algorithmsnetwork locality

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Networks and circuits as models of computation; circuit complexity (68Q06)

Cited In (4)

• Optimal oblivious reconfigurable networks
• Pseudorandomness for network algorithms
• Automatic Methods for Hiding Latency in Parallel and Distributed Computation
• Oblivious algorithms for multicores and networks of processors

This page was built for publication: Network-oblivious algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177760)