HISTÓRICO, MOTIVAÇÃO E CENÁRIO
• Grande quantidade de dados criou uma
necessidade de maior poder computacional;
• Impossibilidade de aumentar a capacidade
de processamento de um único processador.
Solução: paralelização!
HISTÓRICO, MOTIVAÇÃO E CENÁRIO
Gráfico 1, obtido
com dados de [6]
HISTÓRICO, MOTIVAÇÃO E CENÁRIO
Na Google®, as paralelizações nos algoritmos
eram feitas caso a caso.
Em cada caso, problemas comuns a todas as
paralelizações tinham de ser resolvidos.
Como fazer um modelo de paralelizações que
não necessite de novas implementações para
cada caso?
CONCEITO: PARALELIZAÇÃO
Paralelizar um algoritmo é executar partes
diferentes
dele
em
unidades
de
processamento diferentes e obter um menor
tempo de execução.
CONCEITO: PARALELIZAÇÃO
Figura 2 – A paralelização de um processamento
CONCEITO: PARALELIZAÇÃO
PROBLEMAS:
• Como
designar
processamento
aos
processadores?
• Como garantir exclusão mútua onde for
necessário?
• Como fazer o algoritmo paralelo ter os
mesmos resultados do original?
SINCRONIZAÇÃO!
CONCEITO: COMPUTAÇÃO DISTRIBUÍDA
• Sistema Paralelo: computador com diversos
processadores que compartilham áreas da
memória e discos.
• Sistema distribuído: diversos computadores
ligados em rede, capazes de executar
algoritmos paralelos. Chamado também de
cluster. Cada processador de um cluster é
chamado de nó.
O MODELO MAPREDUCE
Abstração que permite que o usuário seja isolado da
camada de paralelização. [1]
A paralelização depende da implementação do
modelo MapReduce.
Na implementação que devem estar garantidas as
propriedades
do
sistema
(integridade,
disponibilidade, controle de acesso, não-repúdio,
confidencialidade, autenticação e privacidade).
MAPREDUCE: VISÃO DO USUÁRIO
• Usuário programa duas funções:
• map(chave, valor) -> (chaveInt , valorInt)
• reduce(chaveInt, valoresInt) -> (saídas)
MAP(CHAVE, VALOR)
A função map(chave, valor) recebe como
parâmetro de entrada um par (chave, valor) e
emite na saída um par (chave intermediária,
valor intermediário).
REDUCE(CHAVEINT, VALORESINT)
A função reduce recebe o conjunto de valores
intermediários valoresInt (saídas da função
map) que estão associados à mesma chave
intermediária chaveInt e emite como saída os
valores finais na saída para a mesma chave.
A IMPLEMENTAÇÃO DO MAPREDUCE
• Diversas implementações são possíveis:
• Cenários
diferentes
demandam
implementações diferentes.
A IMPLEMENTAÇÃO DA GOOGLE®
• Características dos cluster’s disponíveis:
• Dispositivos de rede e processamento
comuns (x86 dual-core, discos IDE);
• Cluster com centenas ou milhares de nós.
• Sistema de arquivos distribuído próprio, o
GFS [5]
A IMPLEMENTAÇÃO DA GOOGLE® (2)
Usuário implementa as funções map e
reduce e chama uma função MapReduce
dentro do próprio programa
• A implementação fragmenta o arquivo de
entrada do usuário (64 MB/parte)
• As funções map e reduce são copiadas para
os nós do cluster
• Mestre X trabalhadores
•
A IMPLEMENTAÇÃO DA GOOGLE® (3)
• O mestre: tarefas a trabalhadores ociosos.
• Trabalhadores
mappers
recebem
um
fragmento do arquivo de entrada cada,
extraem uma chave e valor dele e chamam a
função map.
• Pares intermediários ficam guardados na
memória
• Escritos em disco periodicamente
• Mestre toma nota dos locais dos pares
intermediários.
A IMPLEMENTAÇÃO DA GOOGLE® (4)
• O mestre designa um nó para a tarefa de
reduce com os locais dos valores
intermediários da sua chave.
• O nó de redução lê todos os valores
intermediários relacionados àquela chave
intermediária e chama a função reduce, que
é executada e escreve em um arquivo de
saída o resultado final da execução.
• Implementação retorna ao programa do
usuário
A IMPLEMENTAÇÃO DA GOOGLE® (5)
Figura 3 – Esquema da implementação da Google®
HADOOP
• Uma implementação de código aberto do
modelo MapReduce [4]
• Utiliza interfaces Java® para o programador
implementar as funções map e reduce.
• Muito parecido com a implementação da
Google ®, mas é flexível com relação às
máquinas em que roda.
AMBIENTES OPORTUNÍSTICOS
• Ciclos ociosos de máquinas podem ser
usados
para
executar
tarefas
de
map/reduce.
• Projeto MOON[7]
• Recursos
disponíveis
por
curtíssimos
períodos de tempo
TRABALHOS FUTUROS
• Implementação simplificada de MapReduce
• Ambientes oportunísticos como serviço:
• Como garantir um bom serviço?
• Executar código de interesse nas máquinas
de usuários de aplicativos web.
REFERÊNCIAS
[1] DEAN, Jeffrey; GHEMAWAT, Sanjay. MapReduce: Simplied Data
Processing on Large Clusters. Communications of the ACM, v. 51,
n. 1, p. 107-113, jan. 2008. Disponível em:
<http://static.googleusercontent.com/external_content/untruste
d_dlcp/research.google.com/pt-BR//archive/mapreduceosdi04.pdf>. Acesso em: 23 maio 2012.
[2] LÄMMEL, Ralf. Google's MapReduce Programming Model Revisited. Science of Computer Programming, v.70, n. 1, p. 1-30,
jan. 2008. Disponível em:
<http://web.cs.wpi.edu/~cs3013/a11/Papers/Lammel_MapRed
uce_Revisited.pdf>. Acesso em: 23 maio 2012.
REFERÊNCIAS (2)
[3] VENKATESH, Kirpal A.; NEELAMEGAM, K.; REVATHY, R. Usando
MapReduce e balanceamento de carga em nuvens, out. 2010.
Disponível em:
<http://www.ibm.com/developerworks/br/java/library/clmapreduce/#N1010A>. Acesso em: 24 abr. 2012.
[4] HADOOP. Hadoop 1.0.2 documentation. Disponível em:
<http://hadoop.apache.org/common/docs/current/index.html>.
Acesso em: 24 abr. 2012.
[5] GHEMAWAT, Sanjay; GOBIOFF, Howard; LEUNG, Shun-Tak. The
Google File System.ACM SIGOPS Operating Systems Review SOSP '03, v. 37, n.5, p. 29-43, dez. 2003. Disponível em:
<http://www.cs.brown.edu/courses/cs295-11/2006/gfs.pdf>.
Acesso em: 23 maio 2012.
REFERÊNCIAS (3)
[6] INTEL. Microprocessor Quick Reference Guide. Disponível em:
<http://www.intel.com/pressroom/kits/quickrefyr.htm>. Acesso
em: 23 maio 2012.
[7] Heshan Lin; ARCHULETA, Jeremy; Xiaosong Ma; Wu-chun Feng;
Zhe Zhang; GARDNER, Mark. MOON: MapReduce On
Opportunistic eNvironments. Proceedings of the 19th ACM
International Symposium on High Performance Distributed
Computing - ACM HPDC '10, p. 95-106, 2010. Disponível em:
<http://eprints.cs.vt.edu/archive/00001089/01/moon.pdf>.
Acesso em: 24 maio 2012.