A estrutura do MapReduce é um tipo de BSP?

11

É preciso chamar a estrutura mapReduce de um tipo de estrutura de programação paralela síncrona em massa sem retenção de memória local nos processadores entre as sincronizações? Caso contrário, qual modelo de programação paralela encapsula com mais precisão a estrutura mapReduce?

Jeff Kubina
fonte
1
essa é uma boa pergunta!
Suresh Venkat
obrigado Suresh, o que você acha, concorda?
Jeff Kubina
Escolha difícil escolher a melhor resposta, pois acho que todas elas me ajudaram a obter mais conhecimento sobre mapreduce e como os outros a veem. escolhi a resposta de Sasho, pois me levou a um artigo que aborda a minha pergunta da melhor forma. obrigado a todos.
Jeff Kubina

Respostas:

11

Na seção 2 de http://arxiv.org/abs/1101.1902 , os autores definem um modelo de MapReduce que é intencionalmente estruturado como o BSP. Eles também provam teoremas de simulação. Pode ser um bom lugar para começar.

Sasho Nikolov
fonte
5

Sim, minha opinião é que o MapReduce clássico é um modelo BSP (e, portanto, tem suas limitações inerentes ao máximo desempenho paralelo possível que pode ser alcançado). No entanto, o trabalho mais recente do MapReduce parece estar focado em noções mais frouxas de sincronização, o que tiraria esse "MapReduce generalizado" da estrutura estrita do BSP. Em particular, se alguém replicar alguns dados, a estrutura de sincronização poderá ser relaxada, gerando ganhos de desempenho.

Veja, por exemplo, o trabalho de Foto Afrati e Jeff Ullman: Otimizando junções em um ambiente de redução de mapa , EDBT 2010. ( pré-impressão )

András Salamon
fonte
2

Como no MapReduce existe um gráfico simples e estruturado subjacente à computação, isso pode ser classificado como um modelo de fluxo de dados.

Massimo Cafaro
fonte
Concordo que o MapReduce tem a mesma estratégia de computação que uma máquina de fluxo de dados com tags. A linguagem Pig do Yahoo até cria uma linguagem de fluxo de dados sobre o MapReduce.
Beef