Parallel computation thesis

Parallel computation thesis

In computational complexity theory, the parallel computation thesis is a hypothesis which states that the time used by a (reasonable) parallel machine is polynomially related to the space used by a sequential machine. The parallel computation thesis was set forth by Chandra and Stockmeyer in 1976 (see References).

In other words, for a computational model which allows computations to branch and run in parallel without bound, a formal language which is decidable under the model using no more than t(n) steps for inputs of length "n" is decidable by a machine in the unbranching model using no more than t(n)^k units of storage for some constant "k". Similarly, if a machine in the unbranching model decides a language using no more than s(n) storage, a machine in the parallel model can decide the language in no more than s(n)^k steps for some constant "k".

The parallel computation thesis is not a rigorous formal statement, as it does not clearly define what constitutes an acceptable parallel model. A parallel machine must be sufficiently powerful to emulate the sequential machine in time polynomially related to the sequential space; compare Turing machine, non-deterministic Turing machine, and alternating Turing machine. N. Blum (1983) has introduced a model for which the thesis does not hold. However, the model allows 2^{2^{O(T(n)) parallel threads of computation after T(n) steps. (See Big O notation.) Parberry (1986) suggested a more "reasonable" bound would be 2^{O(T(n))} or 2^{T(n)^{O(1), in defense of the thesis. Goldschlager (1982) has proposed a model which is sufficiently universal to emulate all "reasonable" parallel models, which adheres to the thesis. Chandra and Stockmeyer originally formalized and proved results related to the thesis for deterministic and alternating Turing machines, which is where the thesis originated.

References

* Blum, N., "A note on the 'parallel computation thesis'," "Inf. Proc. Lett.", volume 17, pp. 203-205, 1983.
* [http://portal.acm.org/citation.cfm?id=322243&coll=Portal&dl=ACM&CFID=60283170&CFTOKEN=44928981 Chandra, A.K. and Stockmeyer, L.J., 'Alternation,'] "Journal of the ACM", Volume 28, Issue 1, pp. 114-133, 1981.
* [http://portal.acm.org/citation.cfm?id=322353&coll=Portal&dl=ACM&CFID=60284798&CFTOKEN=73324856 Goldschlager, Leslie M., 'A Universal Interconnection Pattern for Parallel Computers,'] "Journal of the ACM", Volume 29, Issue 3, pp. 1073-1086, 1982.
* [http://portal.acm.org/citation.cfm?id=8317&coll=Portal&dl=ACM&CFID=60284798&CFTOKEN=73324856 Parberry, I., 'Parallel speedup of sequential machines: a defense of parallel computation thesis,'] "ACM SIGACT News", Volume 18, Issue 1, pp. 54-67, 1986.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Parallel computing — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing …   Wikipedia

  • History of the Church–Turing thesis — This article is an extension of the history of the Church–Turing thesis. The debate and discovery of the meaning of computation and recursion has been long and contentious. This article provides detail of that debate and discovery from Peano s… …   Wikipedia

  • History of the Church-Turing thesis — This article is an extension of the history of the Church Turing thesis.The debate and discovery of the meaning of computation and recursion has been long and contentious. This article provides detail of that debate and discovery from Peano s… …   Wikipedia

  • Indeterminacy in concurrent computation — is concerned with the effects of indeterminacy in concurrent computation. Computation is an area in which indeterminacy is becoming increasingly important because of the massive increase in concurrency due to networking and the advent of… …   Wikipedia

  • Evolutionary computation — For the journal, see Evolutionary Computation (journal). In computer science, evolutionary computation is a subfield of artificial intelligence (more particularly computational intelligence) that involves combinatorial optimization problems.… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • Alternating Turing machine — In computational complexity theory, an alternating Turing machine (ATM) is a non deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co NP.… …   Wikipedia

  • Actor model — In computer science, the Actor model is a mathematical model of concurrent computation that treats actors as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”