Bibliotecas paralelas de memória compartilhada baseadas em tarefas na Scientific Computing

10

Nos últimos anos, surgiram várias bibliotecas / projetos de software que oferecem uma forma ou outra de paralelismo de memória compartilhada de uso geral orientado a dados.

A idéia principal é que, em vez de escrever um código explicitamente encadeado, os programadores implementam seus algoritmos como tarefas interdependentes, que são agendadas dinamicamente por um middleware de uso geral em uma máquina de memória compartilhada.

Exemplos dessas bibliotecas são:

  • QUARK : Originalmente projetado para a biblioteca de álgebra linear paralela MAGMA , parece ter sido usado também para um método multipolar rápido paralelo .

  • Cilk : Originalmente, um projeto baseado no MIT, agora suportado pela Intel, implementado como extensões de linguagem / compilador para C, usado no software de xadrez para computador Cilkchess e experimentalmente em FFTW .

  • Superescalar SMP : desenvolvido no Barcelona Supercomputing Center, semelhante ao Cilk em muitos aspectos, com base em #pragmaextensões.

  • StarPU : "codelets" baseados em bibliotecas semelhantes, que podem ser compilados e agendados em várias arquiteturas diferentes, incluindo GPUs.

  • Tarefas do OpenMP: A partir da versão 3.0, o OpenMP introduziu "tarefas" que podem ser agendadas de forma assíncrona (consulte a Seção 2.7 da especificação).

  • Blocos de construção de encadeamento da Intel : usa classes C ++ para criar e iniciar tarefas assíncronas, consulte a Seção 11 do Tutorial.

  • OpenCL : Suporta paralelismo baseado em tarefas em múltiplos núcleos.

Embora exista muita literatura descrevendo o trabalho interno dessas extensões de bibliotecas / linguagem e sua aplicação a problemas específicos, encontrei apenas poucos exemplos deles sendo utilizados na prática em aplicativos de computação científica.

Então, aqui está a pergunta: alguém sabe de códigos de computação científica usando alguma dessas bibliotecas / extensões de linguagem, ou similar, para paralelismo de memória compartilhada?

Pedro
fonte
Você está procurando paralelismo baseado em tarefas? Existe uma razão para você ter ignorado o OpenCL e o Intel TBB? Eu tenho que admitir que não posso dizer exatamente o que você está procurando aqui.
Aron Ahmadia 13/09/12
11
@AronAhmadia: Ignorância, principalmente ... :) Adicionei TBB e OpenCL à lista, mas a pergunta ainda é a mesma: estes, ou seja, seus componentes baseados em tarefas, foram usados ​​em qualquer parte significativa do software para fins científicos? Informática?
Pedro
Como nos sentimos em transformar essa pergunta e suas respostas em um wiki da comunidade versus tentar expandi-la ainda mais?
Aron Ahmadia 14/09/12
@AronAhmadia: Estou um pouco preocupado que, se eu deixar o formato da pergunta, isso rapidamente se degenerar em longas discussões sobre as vantagens / desvantagens da programação baseada em tarefas e / ou de memória compartilhada em geral. No entanto, eu seria a favor de trocá-lo depois de obter mais algumas respostas.
Pedro
O título não é apropriado. Esta pergunta é sobre paralelismo de tarefas, não memória compartilhada.
23413 Jeff Jeff

Respostas:

8

deal.II usa os Threading Building Blocks em toda a biblioteca e, em geral, estamos razoavelmente felizes com isso. Examinamos algumas alternativas, em particular o OpenMP, já que todo mundo parece estar usando isso para códigos mais simples, mas os encontrou ausentes. Em particular, o OpenMP tem a enorme desvantagem de que seu modelo de tarefa não permite que você identifique uma tarefa iniciada e, consequentemente, é difícil acessar o estado de uma tarefa (por exemplo, aguardar a conclusão) ou retornar valores de funções executadas em uma tarefa separada. O OpenMP é principalmente bom para paralelizar os loops mais internos, mas você obtém eficiência paralela paralelizando os loops mais complexos e externos , e o OpenMP não é a ferramenta para isso, enquanto o TBB é razoavelmente bom para isso.

Wolfgang Bangerth
fonte
Obrigado por apontar isso, eu não tinha olhado para o acordo.II! Existe alguma publicação ou documentação em que o uso do acordo.II do TBB é descrito em detalhes?
Pedro
Nenhuma publicação, mas isso pode ajudar: dealii.org/developer/doxygen/deal.II/group__threads.html
Wolfgang Bangerth
4

Na minha opinião, esses sistemas foram relativamente mal-sucedidos devido principalmente aos seguintes motivos.

  • A perspectiva ingênua de que a computação paralela é paralelizar a computação (por exemplo, flops) mais do que expor a localização da memória e remover pontos de sincronização. Embora alguns problemas, como algoritmos de matriz densa, ainda sejam limitados por FP, isso só ocorre após uma análise cuidadosa do subsistema de memória e a maioria dos kernels computacionais (especialmente no mundo PDE) são mais sensíveis à memória. As filas de trabalho tendem a trocar a localidade da memória para obter um melhor equilíbrio ingênuo de flops e mais operações de memória atômica (devido à sincronização através da fila).
  • Confiança na super decomposição para balanceamento dinâmico de carga à custa de forte escalabilidade. As tarefas geralmente têm dependências de dados sobrepostas (valores fantasmas). À medida que o tamanho do interior diminui, a proporção fantasma / interior aumenta. Mesmo quando isso não implica trabalho redundante, implica aumento do movimento da memória. Reduções significativas nos requisitos de largura de banda da memória podem ser obtidas por abordagens como a pré-busca cooperativa, pela qual vários encadeamentos compartilham um cache L1 ou L2 pela pré-busca de software para o vizinho (o que implicitamente mantém o grupo de encadeamentos aproximadamente coerente). Isso é exatamente o oposto da super decomposição.
  • Desempenho imprevisível, principalmente devido aos problemas de memória acima.
  • Falta de componentes compatíveis com a biblioteca. Isso pode ser resumido como não tendo um análogo de um MPI_Commque permita que diferentes bibliotecas executem operações avançadas sem colidir, além de passar o contexto entre bibliotecas e recuperar os atributos necessários. A abstração fornecida pelo "comunicador" é importante para a composição da biblioteca, independentemente de a memória compartilhada ou distribuída ser usada.
Jed Brown
fonte
Posso estar entendendo mal a sua resposta, mas o primeiro ponto é exatamente o oposto do que Buttari, Kurzak, Dongarra e outros mostraram com o MAGMA, uma biblioteca de memória compartilhada baseada em tarefas para álgebra linear densa ... Além disso, em seu segundo ponto você se refere a dados sobrepostos, ou seja, valores fantasmas e a relação superfície / volume, mas esses são um retardo dos esquemas de decomposição do domínio da memória distribuída. Eu mesmo trabalho com esses métodos para códigos baseados em partículas e obtenho um desempenho muito melhor do que as implementações paralelas baseadas em MPI.
Pedro
De qualquer forma, a pergunta era diferente ... Você conhece algum projeto de software de computação científica que use essas abordagens?
Pedro
1. Existem alguns projetos usando esses sistemas, mas não acho que a abordagem possa ser considerada "bem-sucedida". 2. As dependências ainda estão sobrepostas na memória compartilhada. Veja como o tcmalloc ou o kernel do Linux torna os threads mais independentes para evitar gargalos, como a sincronização por meio de átomos. O espaço de endereço compartilhado não implica que você deva operar como se tivesse memória uniforme ou que considere atômicos baratos.
Jed Brown
3. Não sei qual "comparação justa" você pretende citar, mas o PLASMA recebe apenas cerca de 25% da FPU de pico (por exemplo, slide 5 de hpcgarage.org/cscads2012/Luszczek-UTK-PowerTools.pdf ) que seria publicamente ruim para a mesma operação na memória distribuída, onde pelo menos 70% do pico seria esperado. Álgebra linear densa é um caso vinculado à FPU que citei especificamente como uma possível exceção, mas apesar dos enormes tamanhos de matriz, o PLASMA está obviamente longe de ser vinculado à FPU.
precisa
Pedro, mais física tem um componente de longo alcance, de modo que as partículas estão acoplados com uma actualização que está sujeita ao efeito de superfície-para-solume acima (PPPM, partícula vórtice, etc)
Matt Knepley