Modelos paralelos atuais para computação

30

Os anos 80 deram origem aos modelos de computação paralela PRAM e BSP . Parece que o apogeu de ambos os modelos ocorreu no final dos anos 80 e início dos anos 90.

Essas áreas ainda estão ativas em termos de pesquisa de algoritmos paralelos? Existem modelos mais novos e sofisticados para computação paralela? Os modelos gerais ainda estão em voga ou os pesquisadores estão tentando se especializar em GPGPU ou computação baseada em nuvem?

Nicholas Mancuso
fonte

Respostas:

19

Existem vários modelos flutuando, mas alguns dos mais destacados são:

  1. Os modelos MUD e Mapreduce que tratam principalmente da captura da estrutura MapReduce, mas geralmente podem ser vistos como modelos de computação distribuídos em paralelo
  2. Os vários modelos multicore que foram propostos (mas de maneira alguma ainda são o padrão)

No mês passado, houve uma oficina na DIMACS sobre este tópico: ler os resumos fornecerá mais dicas.

Suresh Venkat
fonte
O workshop do DIMACs é brilhante! Obrigado.
Nicholas Mancuso
3
Houve um workshop anterior em 2009, umiacs.umd.edu/conferences/tmc2009, que me pareceu ser mais aguçado do que o recente DIMACs. Leslie Valiant introduziu o modelo Multi-BSP lá (discutido em mais detalhes no workshop deste ano), e Phil Gibbons, da Intel, apresentou uma provocadora teoria da conversa : adormecido na mudança para muitos núcleos que vale a pena examinar. Para mim, o workshop DIMACs estava muito focado no MapReduce, que o Google não usa mais para criar seu índice da web.
András Salamon
isso é verdade. Eu tinha esquecido o anterior.
Suresh Venkat
22

Peço desculpas antecipadamente pelo formato de postagem do blog da minha resposta. Não pude evitar fazer uma pequena visão geral do mundo da computação paralela.

É possível categorizar modelos de programação paralela em aproximadamente duas categorias: modelos de fluxo de controle e fluxo de dados.

Os modelos de fluxo de controle tentam fazer o paralelismo funcionar dentro do contexto de um programa de controle explícito, basicamente todos os computadores programáveis ​​atualmente. O problema fundamental que está sendo enfrentado é que essa "arquitetura de Von Neumann" não foi projetada para execução paralela, mas para cálculos seqüenciais eficientes. O paralelismo nesse contexto é obtido pela duplicação de partes dos módulos básicos (memória, controle, aritmética).

A duplicação apenas da aritmética fornece instruções SIMD, todas as ALUs compartilham o mesmo contador de programas (PC) e, portanto, sempre executam a mesma operação em paralelo, embora com dados diferentes.

A duplicação da ALU e do PC, mas mantendo o seqüenciador de instruções dentro da unidade de controle, oferece execução fora de ordem (OoO) que gera algum paralelismo de pipeline. Nesta categoria, você também tem as Técnicas de Palavra Muito Longa (VLWI) e de previsão de ramificação. Você raramente vê essa categoria no nível do software.

Ir um pouco mais longe é duplicar todo o 'núcleo', mas mantendo a memória compartilhada, esses são os processadores multicore atuais que fornecem paralelismo de tarefas (ou threads). Compartilhar memória nesse contexto oferece problemas de concorrência muito, muito difíceis e sutis . Os cálculos paralelos no multicore atual estão, assim, girando completamente em torno de problemas de sincronização / simultaneidade, o cuidadoso equilíbrio de desempenho (sem sincronização) e a semântica desejada (semântica de execução sequencial totalmente sincronizada). Exemplos disso é a PRAM ou mais popular atualmente nos Cilk ofshoots, como fork / join ( IntelTBB , Java.Utils.Concurrency) Os modelos CSP e Actor são modelos de simultaneidade, mas, como mencionado acima, simultaneidade e paralelismo ficam embaçados em um ambiente de memória compartilhada. nb paralelismo é para desempenho, simultaneidade para manter a semântica correta.

A duplicação de memória também oferece computadores em rede que são programados com o MPI e seus tipos, ou apenas arquiteturas não-Von Neumann estranhas, como os processadores de rede em um chip (processador em nuvem, Transputer, Tilera). Modelos de memória como UMA ou NUMA tentam manter a ilusão de memória compartilhada e podem existir no nível de software ou hardware. O MPI mantém o paralelismo no nível do programa e se comunica apenas através da passagem de mensagens. A passagem de mensagens também é usada no nível do hardware para comunicação e simultaneidade (Transputer).

A segunda categoria são modelos de fluxo de dados . Estes foram projetados no início da era do computador como uma maneira de escrever e executar cálculos paralelos, evitando o design de Von Neumann. Estes caíram na moda (para computação paralela) nos anos 80, após o desempenho sequencial ter aumentado exponencialmente. No entanto, muitos sistemas de programação paralela, como o Google MapReduce, o Dryad da Microsoft ou o Concurrent Collections da Intel, são de fato modelos computacionais de fluxo de dados. Em algum momento, eles representam os cálculos como um gráfico e o usam para orientar a execução.

Ao especificar partes dos modelos, você obtém diferentes categorias e semânticas para o modelo de fluxo de dados. A que você restringe a forma do gráfico: DAG (CnC, Dríade), árvore (mapreduce), dígrafo? Há semântica estrita de sincronização ( Luster, programação reativa]? Você proíbe a recursão para poder ter um agendamento estático (StreaMIT) ou fornece uma potência mais expressiva ao ter um agendador dinâmico (Intel CnC)? Existe um limite no número de bordas de entrada ou saída? A semântica de disparo permite disparar o nó quando um subconjunto dos dados recebidos está disponível? São fluxos de arestas de dados (processamento de fluxo) ou tokens de dados únicos (atribuição única estática / dinâmica). Para trabalhos relacionados, você pode começar analisando o trabalho de pesquisa de fluxo de dados de pessoas como Arvind, K. Kavi, j. Sharp, W. Ackerman, R. Jagannathan, etc.

Edit: Por uma questão de integridade. Gostaria de salientar também há paralelos orientado a redução e orientada para o padrão modelos. Para as estratégias de redução, você tem amplamente redução de gráfico e redução de cadeia. Haskell basicamente usa a redução de gráficos, que é uma estratégia muito eficiente em um sistema seqüencial de memória compartilhada. A duplicação de redução de cadeia funciona, mas possui uma propriedade de memória privada que a torna mais adequada para ser implicitamente paralelizada. Os modelos controlados por padrão são as linguagens lógicas paralelas, como o prólogo simultâneo. O modelo Actor também é um modelo orientado a padrões, mas com características de memória privada.

PS. Uso amplamente o termo 'modelo', cobrindo máquinas abstratas para fins formais e de programação.

Carne
fonte
Não entendo como o mapreduce forma uma árvore. Você poderia explicar?
precisa
@Riko Jacob, digamos que você mapeie '+' para (1 2 3 4), conceitualmente isso cria uma árvore de aplicativos com '+' em cada nó e cada número como folhas. reduzir (ou dobrar se você é de haskel) recolherá cada nó com os dados de seus filhos.
Beef
K2,2
Se você não levar em consideração a criação do gráfico em si (por exemplo, mapeando a, b para os pares chave / vale), duas árvores farão a redução, com um pouco de boa vontade :) Talvez seja mais um gráfico conectado em k ou em rede como você disse. Você está certo de que é um pouco mais geral do que uma simples árvore. Eu estava tentando fazer uma distinção com estruturas de fluxo de dados mais gerais do DAG.
Carne
8

Para arquiteturas de transmissão de mensagens, um modelo bastante semelhante ao BSP, mas mais fácil de lidar e com a análise de desempenho próxima ao que você realmente obtém em uma máquina real, é certamente o CGM ou o Multicomputador de Granulação Grossa. Foi proposto por Frank Dehne, e você encontrará muitos artigos interessantes apresentando algoritmos desenvolvidos neste contexto.

O CGM se encaixa em arquiteturas de granulação grossa assumindo processadores p, cada um com memória local O (n / p) e o tamanho da entrada n muito maior (ordens de magnitude separadas) que p, ou seja, p≪n. Portanto, o modelo mapeia muito melhor do que outros nas arquiteturas atuais; foi estudado extensivamente. O modelo baseia-se nas seguintes suposições: (i) os algoritmos executam as chamadas super-etapas, que consistem em uma fase de computação local e uma fase de comunicação entre processadores com sincronização de barreira intermediária, (ii) todos os processadores p têm acesso a Memória local O (n / p), (iii) em cada super etapa, um processador pode enviar e receber no máximo elementos O (n / p) e (iv) a rede de comunicação entre os processadores pode ser arbitrária. Nesse modelo, um algoritmo é avaliado pelo tempo de computação e número de rodadas de comunicação. Embora o modelo seja simples, ele fornece uma previsão razoável do desempenho real dos algoritmos paralelos; de fato, algoritmos paralelos para CGMs geralmente têm uma análise de complexidade teórica muito próxima dos tempos reais determinados experimentalmente ao implementá-los e compará-los.

Massimo Cafaro
fonte
4

A memória externa paralela (PEM) é uma combinação natural de uma máquina de memória compartilhada no estilo PRAM com o modelo de memória externa. Ele se concentra nas implicações de caches particulares.

Riko Jacob
fonte
4

Pelo que sei, os modelos BSP e LogP são usados ​​hoje em dia para algoritmos distribuídos. Além disso, desde a computação em GPU, a PRAM se tornou novamente popular, no entanto, deve-se incluir as hierarquias de memória na análise. Você pode verificar o modelo UPMH (hierarquia de memória paralela uniforme) que complementa perfeitamente a PRAM.

B. Alpern, L. Carter, E. Feig e T. Selker. O modelo uniforme de hierarquia de memória da computação. Algorithmica, 12: 72-109, 1994. 10.1007 / BF01185206.

Bowen Alpern, Larry Carter e Jeanne Ferrante. Modelando computadores paralelos como hierarquias de memória. In In Proc. Modelos de programação para computadores massivamente paralelos, páginas 116–123. IEEE Computer Society Press, 1993.

Também para a computação GPU, houve uma proposta para um modelo teórico de computação; o modelo K:

Gabriele Capannini, Fabrizio Silvestri e Ranieri Baraglia. Modelo K: um novo modelo computacional para processadores de fluxo. Em Anais da 12ª Conferência Internacional IEEE de 2010 sobre Computação e Comunicações de Alto Desempenho, HPCC '10, páginas 239-246, Washington, DC, EUA, 2010. IEEE Computer Society.

Por fim, eu vi autômatos celulares (CA) modelados como computadores paralelos; pessoalmente, acho que esse é um tópico de pesquisa muito interessante. Quem sabe no futuro os processadores serão feitos dessa maneira, como pequenos espaços de computação. Eu não tenho uma referência sólida para isso, você pode procurar na web.

labotsirc
fonte
3

Programas puramente funcionais permitem a execução paralela de expressões independentes. Portanto, eu os contaria como modelos paralelos de computação.

Riko Jacob
fonte
Não existe um modelo de custo específico associado à programação funcional, portanto isso não responde à pergunta. Veja cstheory.stackexchange.com/questions/376/…
Charles Stewart
2
O mecanismo de avaliação para essas linguagens baseadas no cálculo lambda é a redução, que na verdade não tem um mapeamento direto para o hardware real. É por isso que Haskell ainda precisa introduzir construções paralelas explícitas como 'par'. referência: csg.csail.mit.edu/projects/languages/ph.shtml
Beef
3

Eu prefiro a abordagem de Bader-Jaja (consulte a seção 2.1). Você modela a complexidade como um problema de passagem de mensagens. Para cada mensagem enviada, existe uma variável de latência para iniciar a comunicação e uma variável de largura de banda.

tumptump

Chad Brewbaker
fonte
-3

você menciona especificamente a computação em nuvem. em poucos anos, houve intensa inovação nessa área com a nuvem de computação elástica da Amazon, o mecanismo de aplicativos do google e várias ferramentas e seus "modelos" de processamento paralelo conceitual associados.

ferramentas de código aberto especiais incluem os bancos de dados Mapreduce , Apache Hadoop e NoSQL do Google, que estão surgindo como novos padrões fortes e amplamente adaptados nas "melhores práticas" e "padrões de design" do algoritmo de paralelização. também o memcacheD está sendo cada vez mais usado como um banco de dados distribuído na memória. um exemplo disso está em uso no Facebook, descrito em um artigo recente [1].

[1] Muitos dos principais armazenamentos de valores-chave de Berezecki et al.

vzn
fonte
novamente. Peço modelos ou computação paralela. Não ferramentas. O MapReduce é um desses modelos. No entanto, o Hadoop e o NoSQL não são. O Hadoop é uma reificação baseada em java do MapReduce. O NoSQL é um modelo para key-stores relaxados, pelo que posso dizer.
Nicholas Mancuso
O MapReduce começou como uma ferramenta e passou para um modelo através do uso / adoção generalizada. mesmo com os outros. O Hadoop não é idêntico ao MapReduce, mas talvez semelhante. sim, acho que fiquei impressionado com a resposta do voto de Suresh que incluía o MapReduce ... as pessoas parecem não se importar muito com, ou preferem não discutir, os pacotes de software reais neste site ... não importa o quão amplamente usado .. mesmo considerando que eles inspiram / fazem crosspollinate / drive sólida teoria posterior como o MapReduce fez ... my bad = (
vzn 31/12/12
2
O ponto é que você não está respondendo à pergunta. a política por aqui é que sugestões tangencialmente relacionadas à pergunta não são respostas aceitáveis. se você não gostar desta política, poderá optar por não participar. se você tivesse idéias reais sobre como modelar um sistema paralelo no mundo real, que seria mais sobre o tema (embora ainda não uma resposta para a pergunta feita)
Sasho Nikolov
-3

outro ângulo sobre isso. é certo que isso poderia ser considerado um tanto obscuro ou marginal por alguns, mas há algum trabalho em paralelizar, de uma maneira geral, algoritmos probabilísticos, que se afirma serem algo naturalmente adequados ao paralelismo.

veja, por exemplo, Computações Probabilísticas Paralelas em um Cluster de Estações de Trabalho Radenski, Vann, Norris:

Algoritmos probabilísticos são métodos aproximados computacionalmente intensivos para resolver problemas intratáveis. Os algoritmos probabilísticos são excelentes candidatos para cálculos de cluster porque exigem pouca comunicação e sincronização. É possível especificar uma estrutura de controle paralelo comum como um algoritmo genérico para cálculos probabilísticos de cluster. Um algoritmo paralelo genérico pode ser colado com algoritmos sequenciais específicos do domínio, a fim de derivar soluções paralelas aproximadas para diferentes problemas intratáveis. Neste artigo, propomos um algoritmo genérico para cálculos probabilísticos em um cluster de estações de trabalho. Utilizamos esse algoritmo genérico para derivar algoritmos paralelos específicos para dois problemas discretos de otimização: o problema da mochila e o problema do vendedor ambulante.

caso não esteja claro, a "estrutura de controle paralelo comum como um algoritmo genérico" referida juntamente com o cálculo probabilístico e a conversão geral é o "modelo".

pode-se argumentar que a computação probabilística não é estritamente clássica ou Turing completa. observe que há algum trabalho em vincular o clássico à computação probabilística também especificamente em um contexto paralelo, por exemplo

Raciocínio sobre programas paralelos probabilísticos de Rao:

O uso da randomização no design e análise de algoritmos promete algoritmos simples e eficientes para problemas difíceis, alguns dos quais podem não ter uma solução determinística. Esse ganho em simplicidade, eficiência e solvabilidade resulta em uma troca da noção tradicional de correção absoluta de algoritmos para uma noção mais quantitativa: correção com probabilidade entre 0 e 1. A adição da noção de paralelismo à já não intuitiva A idéia de randomização torna o raciocínio sobre programas paralelos probabilísticos ainda mais tortuoso e difícil. Neste artigo, abordaremos o problema de especificar e derivar propriedades de programas paralelos probabilísticos que se mantêm deterministicamente ou com probabilidade 1.

é claro que a computação QM é muito semelhante à computação probabilística (uma boa referência que enfatiza que essa é a visão de One Quantity Complexity of Quantum Computing da Fortnow ) e há algumas dicas de que essas abordagens podem ser estendidas por lá, por exemplo, no trabalho em simulação QM paralela.

vzn
fonte
-6

isso será considerado controverso por alguns, e mesmo os proponentes desse ângulo terão que admitir isso nos estágios iniciais da pesquisa, mas basicamente a computação quântica parece ter muitas conexões com o paralelismo e a computação paralela. as referências estão agora dispersas, mas um tema emergente pode ser visto por um determinado pesquisador.

talvez a melhor conexão seja com o algoritmo de busca de Grovers, que recentemente se mostrou mais geral no sentido de ser usado para acelerar a maioria dos problemas completos de NP em geral [5]. O algoritmo de Grovers parece ter uma forte analogia / conexão com algoritmos de pesquisa de banco de dados paralelos. os melhores algoritmos seriais clássicos não podem atingir o mesmo desempenho, mas pelo menos uma autoridade argumentou recentemente que as abordagens de QM para pesquisa na verdade não superam os algoritmos clássicos paralelos. [1]

evidências adicionais são esquemas que examinam explicitamente o paralelismo na pesquisa quântica, por exemplo [2]. também foram propostos simuladores quânticos baseados em processamento paralelo / distribuído [3] [4] e porque o esquema se encaixa bem e leva a simulações eficientes e tratáveis ​​(30 qubits são simulados na ref [3]), essa conversão certamente não é apenas uma coincidência e indica uma ponte mais profunda entre a computação clássica paralela e a computação QM, mas provavelmente até agora descoberta.

[1] A pesquisa quântica é prática? por Viamontes et al

[2] Pesquisa quântica exata por esquemas de discriminação unitária paralela por Wu / Dian.

[3] Simulador paralelo de uso geral para computação quântica de Niwa, Matsumoto, Imai.

[4] computação quântica distribuída eficiente por Beals et al 2012

[5] Resolvendo problemas completos de NP com pesquisa quântica realizada por Furer 2008

vzn
fonte
@ vnz, isso parece ser, na melhor das hipóteses, uma mistura aleatória de conceitos quânticos. Pesquisar no Google "quantum paralelo" e listar os resultados aqui não tem utilidade para mim e para outras pessoas que estão lendo isso. Eu acho que seria melhor para a comunidade realmente responder às respostas com as quais você se sente confortável e com conhecimento, em vez de apenas fazer uma corrida louca por pontos de reputação. É não-construtivo e possivelmente dissimulado pensar na computação quântica como pesquisa paralela. A computação quântica tem, para usar sua descrição, "fortes analogias / conexões" com pesquisa probabilística, não paralela.
Nicholas Mancuso
Eu não sei o que o dogma é ensinado nas salas de aula, mas se alguém lá fora realmente tem uma REFERÊNCIA em vez de meras afirmações sem fundamento que indicam por que não há validade para uma correspondência até agora descoberta de QM realizando computação clássica paralela ... ISTO. A computação QM retorna respostas precisas, por exemplo, fatoração costeira, caso contrário, não é um sistema de computação real ..... também existem outras maneiras além das que eu esboço para demonstrar que a computação QM deve ser equivalente à computação clássica paralela em algum sentido ... talvez desde que não está em um livro, deve estar errado hein !!
vzn
Há todo um curso gratuito sobre computação quântica aqui: coursera.org, que pode esclarecer as coisas para você.
Nicholas Mancuso
ps como para "hodgepodge" ... tente realmente LER OS REFS .. ou talvez apenas deslizando-os no seu caso wink =)
vzn 31/07/12
11
(6.) Sua referência. [5] descreve maneiras pelas quais o algoritmo de Grover pode ser estendido, novamente sem abordar o paralelismo que você procura na computação quântica. Em resumo: sua interpretação de que existem conexões entre computação quântica e paralela parece derivar da interpretação de muitos mundos da QM. Embora não seja obscuro, também não é incontroverso e certamente não nos permite descrever produtivamente a computação quântica como "computação em paralelo", exceto na medida em que não vemos essas computações ... o que não é um argumento forte para a presença deles.
Niel de Beaudrap 25/03