Tese da computação paralela

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na teoria da complexidade computacional, a tese da computação paralela é uma hipótese que afirma que o tempo é utilizado por uma máquina paralela (razoável) e é polinomialmente relacionada com o espaço utilizado por uma máquina seqüencial. A tese de computação paralela foi estabelecido por Chandra e Larry Stockmeyer em 1976[1] (ver Referências).

Em outras palavras, é um modelo computacional que permite cálculos em ramificação e executados em paralelo sem limites, uma linguagem formal que é decidível sob o modelo usando não mais que t(n) passos para as entradas de comprimento n é decidível por uma máquina no modelo desramificação usando não mais que t(n)^k unidade de armazenamento para alguma constante k. Da mesma forma, se uma máquina no modelo de desramificação decide uma linguagem utilizando não mais do que s(n) armazenamento, uma máquina no modelo paralelo pode decidir a linguagem em não mais do que s(n)^k passos para alguma constante k.

A tese de computação paralela não é uma declaração formal rigorosa, uma vez que não define claramente o que constitui um modelo aceitável paralelo. A máquina paralela deve ser suficientemente poderosa para emular a máquina seqüencial em tempo polinomial relacionadas com o espaço seqüencial; compare máquina de Turing, máquina de Turing não-determinística, e máquina de Turing alternada. Em 1983, N. Blum[2] introduziu um modelo em que a tese não se sustenta. No entanto, o modelo permite 2^{2^{O(T(n))}} processos de computação paralela após T(n) passos. (Veja notação Grande-O.) Em 1986, Parberry[3] sugeriu uma forma mais "razoável" que seria 2^{O(T(n))} ou 2^{T(n)^{O(1)}}, em defesa da tese. Em 1982, Goldschlager[4] propôs um modelo que é suficientemente universal para emular todas os modelos paralelos "razoáveis", que aderem à tese. Chandra e Stockmeyer originalmente formalizaram e provaram resultados relacionadas com a tese para máquinas Turing determinísticas e alternadas, que é de onde se originou a tese.

Referências

  1. * Chandra, A.K. and Stockmeyer, L.J., 'Alternation,' Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.
  2. * Blum, N., "A note on the 'parallel computation thesis'," Inf. Proc. Lett., volume 17, pp. 203-205, 1983.
  3. * Parberry, I., 'Parallel speedup of sequential machines: a defense of parallel computation thesis,' ACM SIGACT News, Volume 18, Issue 1, pp. 54-67, 1986.
  4. * Goldschlager, Leslie M., 'A Universal Interconnection Pattern for Parallel Computers,' Journal of the ACM, Volume 29, Issue 3, pp. 1073-1086, 1982.