A programação funcional e arquitetura multicore

StackOverflow https://stackoverflow.com/questions/181284

Pergunta

Eu li em algum lugar que a programação funcional é adequado para tirar proveito da tendência de multi-core no cálculo. Eu realmente não começa a idéia. Está relacionado com o cálculo lambda e von Neumann arquitetura?

Foi útil?

Solução

minimiza programação funcional ou efeitos colaterais elimina e, portanto, é mais adequado para programação distribuída. isto é, processamento com vários núcleos.

Em outras palavras, muitas peças do quebra-cabeça pode ser resolvido de forma independente em núcleos separados, simultaneamente, sem ter que se preocupar com uma operação que afeta outro quase tanto como você faria em outros estilos de programação.

Outras dicas

Uma das coisas mais difíceis de lidar com processamento paralelo está travando estruturas de dados para evitar a corrupção. Se dois tópicos foram a se transformar uma estrutura de dados de uma só vez, sem tê-lo bloqueado perfeitamente, qualquer coisa a partir de dados inválidos para um impasse poderia resultar.

Em contraste, linguagens de programação funcional tendem a enfatizar os dados imutáveis. Qualquer estado é mantido separado da lógica, e uma vez que uma estrutura de dados é criado, ele não pode ser modificado. A necessidade para o bloqueio é grandemente reduzida.

Outra vantagem é que alguns processos que parallelize muito facilmente, como iteração, são abstraídas para funções. Em C ++, você pode ter um loop que executa um processamento de dados sobre cada item em uma lista. Mas o compilador não tem como saber se essas operações podem ser executados com segurança em paralelo - talvez o resultado de um depende do que antes dela. Quando uma função como map() ou reduce() é usado, o compilador pode saber que não há nenhuma dependência entre as chamadas. Vários itens podem assim ser processadas ao mesmo tempo.

Eu li em algum lugar que a programação funcional é adequado para tirar proveito da tendência de multi-core em computação ... Eu realmente não começa a idéia. Está relacionado com o cálculo lambda e von Neumann arquitetura?

O argumento por trás da crença de que você citou é que os controles de programação efeitos colaterais puramente funcionais, que torna muito mais fácil e mais seguro para introduzir paralelismo e, portanto, que as linguagens de programação puramente funcional deve ser vantajoso no contexto de múltiplos núcleos computadores.

Infelizmente, essa crença foi muito tempo desde refutada por várias razões:

  • O desempenho absoluto dos dados puramente funcionais estruturas é pobre . Então programação puramente funcional é um grande passo inicial na direção errada no contexto de desempenho (que é o único propósito de programação paralela).

  • estruturas de dados puramente funcional escalar mal porque eles enfatizam recursos compartilhados, incluindo o alocador / GC e largura de banda de memória principal. Então paralelizados programas puramente funcionais, muitas vezes obter speedups pobres, como o número de núcleos aumenta.

  • programação puramente funcional torna desempenho imprevisível. Tão real programas puramente funcionais, muitas vezes ver o desempenho degradação quando paralelizado porque granularidade é efetivamente aleatória.

Por exemplo, o bastardized duas linhas quicksort frequentemente citada pela comunidade Haskell tipicamente é executado milhares de vezes mais lento do que um verdadeiro in-place quicksort escrito em uma linguagem mais convencional como F #. Além disso, embora você pode facilmente paralelizar o programa elegante Haskell, é improvável que você vê qualquer melhoria de desempenho que seja porque todas as cópias desnecessárias faz um único núcleo saturar toda a largura de banda da memória principal de uma máquina multicore, tornando paralelismo inútil. Na verdade, ninguém jamais conseguiu escrever qualquer tipo de tipo paralelo genérica em Haskell que é performance competitiva. Os tipos state-of-the-art fornecidos pela biblioteca padrão de Haskell são tipicamente centenas de vezes mais lento do que as alternativas convencionais.

No entanto, a definição mais comum de programação funcional como um estilo que enfatiza o uso de funções de primeira classe faz realmente vir a ser muito útil no contexto da programação multicore porque este paradigma é ideal para programas paralelos de factoring. Por exemplo, veja a nova função de ordem superior Parallel.For do namespace System.Threading.Tasks no .NET 4.

Quando não há efeitos colaterais a ordem de avaliação não importa. Em seguida, é possível avaliar expressões em paralelo.

O argumento básico é que é difícil de paralelizar automaticamente linguagens como C / C ++ / etc porque funções pode definir variáveis ??globais. Considere duas chamadas de função: 

a = foo(b, c);
d = bar(e, f);

Apesar de foo e bar não têm argumentos em comum e um não dependem do código de retorno do outro, eles ainda podem ter dependências porque foo pode definir uma variável global (ou outro efeito colateral) que bar depende.

As linguagens funcionais garantir que foo e bar são independentes: não há globals, e sem efeitos colaterais. Portanto foo e bar pode ser executado com segurança em diferentes núcleos, automaticamente, sem a intervenção do programador.

Todas as respostas acima ir para a ideia-chave que "armazenamento mutável não compartilhada" é um factor-chave para executar peças de um programa em paralelo. Realmente não resolver o problema igualmente difícil de encontrar coisas para executar em paralelo. Mas as expressões típicas mais claros de funcionalidade em linguagens funcionais não torná-lo teoricamente mais fácil extrair o paralelismo de uma expressão seqüencial.

Na prática, acho que o "armazenamento não compartilhado mutável" propriedade de línguas com base na coleta de lixo e copiar-on-mudança semântica torná-los mais fácil adicionar tópicos a. O melhor exemplo é provavelmente Erlang, a semântica que combina quase-funcionais com tópicos explícitas.

Este é um pouco de uma pergunta vaga. Um privilégio de CPUs multi-core é que você pode executar um programa funcional e deixá-lo ligar afastado em série sem se preocupar com a afectar qualquer computação em curso que tem a ver com outras funções da máquina está a realizar.

A diferença entre um servidor multi-U e uma CPU multi-core em um servidor ou PC é a economia de velocidade que você ganha por tê-lo no mesmo BUS, permitindo uma melhor e mais rápido de comunicação para os núcleos.

edit: eu provavelmente deveria qualificar este post dizendo que na maior parte do script que eu faço, com ou sem vários núcleos, eu raramente vejo um problema em obter os meus dados através de paralelização hackish, tais como a execução de vários pequenos scripts ao mesmo tempo em meu script, então eu não estou retardado por coisas como esperar por URLs para carregar e quais não.

double edit: Além disso, uma grande quantidade de linguagens de programação funcional tiveram bifurcada variantes paralelas ao longo de décadas. Estes utilizar melhor computação paralela com alguma melhora a velocidade, mas eles nunca realmente pegou.

A omissão de qualquer / termos científicos a razão técnica é porque o programa funcional não compartilhar dados. Os dados são copiados e transferidos entre as funções, dados assim não há como compartilhados no aplicativo.

E dados compartilhados é o que faz com que metade das dores de cabeça com multithreading.

Não afiliado a StackOverflow
scroll top