Limites à computação paralela

Estou curioso, em um sentido amplo, sobre o que é conhecido sobre algoritmos de paralelização em P. Encontrei o seguinte artigo da Wikipedia sobre o assunto:

http://en.wikipedia.org/wiki/NC_%28complexity%29

O artigo contém a seguinte frase:

Não se sabe se NC = P, mas a maioria dos pesquisadores suspeita que isso seja falso, o que significa que provavelmente existem alguns problemas tratáveis ​​que são "inerentemente sequenciais" e não podem ser significativamente acelerados usando o paralelismo

Isso soa razoável? Existem casos conhecidos em que um problema em P não pode ser acelerado usando paralelismo?

Nem se sabe se NC = P, mas problemas com P-completos parecem ser inerentemente difíceis de paralelizar. Isso inclui Programação Linear e Horn-SAT. (Por outro lado, os problemas na NC parecem razoavelmente fáceis de paralelizar.)

Veja a pergunta Problemas entre NC e P: Quantos foram resolvidos nesta lista? para material de referência (incluindo links para um livro clássico que agora está disponível para download gratuito) e mais discussões sobre problemas que estão em P, mas que não são conhecidos por serem paralelamente agradáveis.

Veja a pergunta Teorema de Ladner Generalizado para a estrutura das classes de complexidade entre NC e P. Resumidamente, se elas diferem, existem infinitas classes de complexidade estritamente entre NC e P.

Veja a pergunta NC = P consequências? para uma boa demonstração de Ryan Williams de que é possível ampliar colapsos na hierarquia de classes de complexidade em P em colapsos talvez mais improváveis, como PSPACE = EXP .

Vale ressaltar que uma consequência do Horn-SAT ser P-complete, e os links acima, é que não parece possível paralelizar consultas SQL gerais em bancos de dados, a menos que também possamos reescrever qualquer computação em larga escala para usar apenas uma quantidade razoável de armazenamento. Essa é uma discrepância intrigante - acho bastante incontroverso afirmar que há limites para a compactação , mas muitas vezes vejo artigos que parecem construídos com a suposição de que é possível paralelizar qualquer consulta ao banco de dados.

Bem, se houvesse casos conhecidos, poderíamos separar P e NC. Mas existem muitos problemas conhecidos por estarem completos P (isto é, sob reduções do espaço de log) e apresentam o mesmo tipo de barreiras para mostrar P = NC que os problemas completos de NP fazem para P = NP. Entre eles, incluem programação linear e correspondência (e fluxos máximos em geral).

Ketan Mulmuley provou um resultado que separou P e uma forma fraca de NC (sem operações de bit) em 1994. Em certo sentido, seu programa atual para P vs NP decola de onde parou ( de uma maneira muito frouxa ).

O livro ' Limites da computação paralela ' tem mais sobre isso.

Respondi à pergunta semelhante: Existem problemas / algoritmos famosos na computação científica que não podem ser acelerados por paralelização no site da Ciência da Computação ? Deixe-me citar aqui, porque oferece uma perspectiva prática sobre uma instância muito concreta de um problema assim:

O método (famoso) de marcha rápida para resolver a equação de Eikonal não pode ser acelerado pela paralelização. Existem outros métodos (por exemplo, métodos de varredura rápida) para resolver a equação Eikonal que são mais passíveis de paralelização, mas mesmo aqui o potencial para aceleração (paralela) é limitado.

O problema com a equação de Eikonal é que o fluxo de informações depende da própria solução. Em termos gerais, a informação flui ao longo das características (isto é, raios de luz na óptica), mas as características dependem da própria solução. E o fluxo de informações para a equação Eikonal discretizada é ainda pior, exigindo aproximações adicionais (como implicitamente presentes em métodos de varredura rápida) se qualquer aceleração paralela for desejada.

Para ver as dificuldades da paralelização, imagine um belo labirinto como em alguns exemplos na página de Sethian . O número de células no caminho mais curto através do labirinto (provavelmente) é um limite inferior para o número mínimo de etapas / iterações de qualquer algoritmo (paralelo) que resolve o problema correspondente.

(Eu escrevo "(provavelmente) é", porque limites mais baixos são notoriamente difíceis de provar e geralmente exigem algumas suposições razoáveis ​​sobre as operações usadas por um algoritmo).