Diferenças entre edições de "Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Avaliação do algoritmo PageRank"

sem resumo de edição
(Criou nova página com '== Descrição da Aplicação == === Denominação === Algoritmo PageRank. === Contexto === A busca de informação não é uma tarefa trivial. A área da recuperaç...')
 
=== Denominação ===
 
Algoritmo [[:w:PageRank|PageRank]].
 
=== Contexto ===
 
Há ainda tentativas de implementação do algoritmo em placas gráficas (GPUs), que são arquiteturas fortemente paralelas e com enorme poder de processamento. Apesar de eficientes, a maioria dessas abordagens fica limitada pela memória local limitada, então para aplicações práticas de alto porte, é necessária uma estratégia auxiliar.
 
== Projeto ==
 
=== Oportunidades de paralelização ===
 
O cálculo do rank de um nodo em uma iteração depende do rank na iteração anterior dos nodos que apontam para este nodo. Assim, este passo de calcular o novo rank pode ser executado paralelamente para cada nodo.
 
O valor do rank anterior não pode ser mudado enquanto esse passo é executado e isso pode ser evitado. Ao terminar esse passo, é necessário sincronizar as linhas de execução para que a próxima iteração leia valores atualizados.
 
A paralelização pode ser ampliada se os somatórios de ranks for dividido. A lista de nodos apontadores seria dividida e o rank parcial seria calculado separadamente, já que soma em ordem diferente tem o mesmo resultado. Entretanto isso cria uma etapa adicional para combinar os resultados parciais.
 
Entretanto essa oportunidade paralelização não garante balanceamento de carga entre cada thread, porque enquanto um nodo pode ser apontado por apenas um nodo, outro pode ser apontado por inúmeros. O balanceamento pode ser melhorado criando threads que somam números aproximados de nodos e os nodos que tem mais apontadores seriam divididos em mais threads.
 
=== Padrões de acesso aos dados ===
 
Cada nodo tem como dados o cojunto de nodos para o qual ele aponta e o valor de page rank atual. É necessário que o nodo em cada iteração veja um grafo invertido, que tenha a lista de nodos que apontam para ele. E ele precisará saber o valor do rank desses nodos junto com o número de nodos para os quais eles apontam ou apenas a divisão desses dois valores.
 
Quando um algoritmo paralelo executa no mesmo computador, as threads podem ter memória compartilhada e isso permite que cada thread leia todas as informações que precisar sobre o grafo e o custo disso é baixo.
 
Quando o volume de dados é muito grande o processamento teria tempo de execução longo e os dados podem não caber no disco rígido. A solução seria fazer processamento é distribuído. Isso requer que cada computador do cluster receba os dados necessários dos nodos que ele precisará e ao final de cada iteração o nodo precisará saber o novo valor de rank de cada nodo que ele precisa e isso gera muitas mensagens de comunicação.
 
=== Padrões de comunicação ===
 
É necessário fazer comunicação para sincronizar as linhas de execução de cada thread no final de cada thread para que o novo valor de rank seja atualizado no momento certo para não prejudicar as outras threads que ainda estejam executando e também para começar a próxima iteração lendo valores de rank atualizados.
 
Em processamento distribuído, o novo valor de rank deve ser enviado para todas as threads que usarão esse valor na próxima iteração. Assim, o número de mensagens trocadas na rede seria igual ao número de arestas do grafo e isso pode sobrecarregar a rede, porque o número de mensagens é muito grande.
 
=== Linha do tempo integrada ===
Quando há uma thread por nodo, cada thread processa de maneira independente sua lista de apontadores e no final é necessário esperar todas as outras threads terminar para poder atualizar o rank do nodo e receber novos valores de rank. Além da comunicação para sincronização, em implementação distribuída, é necessário comunicação para enviar e receber valores do rank calculados durante a iteração.
 
 
== Desenvolvimento ==
 
=== Hadoop ===
 
A implementação do PageRank usando Hadoop executa um número de iterações definido como argumento do programa. Cada iteração tem uma fase de “map” e “reduce”, além das fases de leitura de dados da iteração anterior e escrita para o próxima iteração. O programa começa lendo um arquivo de entrada contendo o grafo e carrega os dados do grafo no Hadoop.
 
O “damping factor” é um argumento opcional do programa. O valor padrão é 0.85 e para desativar basta definir o valor como 1.0.
 
==== Estratégias de paralelização ====
 
A etapa “map” é executada paralelamente para cada dado. Ela tem como entrada a chave sendo o identificador do nodo e como valor o rank atual do nó. Cada nodo passa no “map” uma vez e tem como saída cada nodo apontado por ele e o valor de rank dividido pelo número de nodos apontados.
 
A etapa “reduce” tem como entrada a chave sendo o identificador do nodo e uma lista de valores de rank/número de nodos apontados já calculados na etapa anterior. Essa etapa vai somar os valores dessa lista e retornar o novo valor de rank para o nodo identificado pela chave.
 
Como foi falado, essa estratégia não garante balanceamento de carga na etapa “reduce”, porque o tempo de execução para nodos com mais apontadores seria mais longo por ter mais valores no iterador para somar.
 
==== Estratégias de armazenamento ====
 
Ao terminar uma iteração os dados são salvos no sistema de arquivos virtual distribuído do Hadoop (HDFS) para serem lidos no início da próxima iteração.
 
==== Estratégias de comunicação ====
 
A gerência da execução é feita pela função principal do programa que inicia cada iteração de map-reduce. Assim, o Hadoop é encarregado de criar as threads e dividir a carga, sincronizar e transportar dados nas etapas map e reduce, e escrever a saída da iteração.
 
=== GraphLab ===
 
 
== Implementação ==
 
=== Plataformas e ferramentas ===
 
=== Integração de plataformas e ferramentas ===
 
=== Detalhes de implementação ===
 
== Avaliação ==
 
=== Carga de trabalho ===
 
=== Avaliação experimental ===
 
=== Análise de resultados ===
 
=== Análise Crítica ===
5

edições