Accueil / flux-publications / On the parallel computation thesis

On the parallel computation thesis

FacebookTwitter

Nachum Dershowitz, Eugenia Falkovich-Derzhavetz, "On the parallel computation thesis", in Logic Journal of IGPL, Oxford University Press, 2016.

Abstract

We develop a generic programming language for parallel algorithms, one that works for all data structures and control structures. We show that any parallel algorithm satisfying intuitively-appealing postulates can be modelled by a collection of cells, each of which is an abstract state machine, augmented with the ability to spawn new cells. The cells all run the same algorithm and communicate via a shared global memory. Using a formal definition of what makes such an algorithm effective, we prove the validity of the Parallel Computation Thesis, according to which all reasonable parallel models of computation have roughly equivalent running times.

Full text (PDF on Oxfordjournals.org)

Machine Learning Tools for Historical Documents
01 octobre 2015 - 30 juin 2016
30 juin 2016
485
Nachum Dershowitz
4153
2016
Époque contemporaine (1789-...)
Monde ou sans région
Nachum Dershowitz et al.