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
[[Imagem:PageRanks-Example.svg|400px|right]]
 
== Descrição da Aplicação ==
 
Numa rede com n nodos, atribui-se inicialmente o valor de 1/n para cada um. Depois disso, realizamos uma regra de atualização um determinado número k de vezes. A regra de atualização é a seguinte: cada nodo compartilha seu valor atual de PageRank igualmente com todos os nodos que segue, e cada nodo atualiza seu valor para ser a soma das partes que recebeu. A teoria do PageRank diz que até mesmo uma pessoa que clica em links aleatoriamente vai, eventualmente, parar de clicar. A probabilidade, a qualquer passo, que uma pessoa continue clicando é dado por um fator de amortecimento (damping factor) d, que geralmente é configurado para ter o valor 0,85. O fator de amortecimento é subtraído de 1 e o resultado é adicionado ao produto do fator de amortecimento pela soma das partes que o nodo recebeu.
 
<code>
Para cada vértice <math>v</math>:
 
<math>PR(v, 0) = \frac{1}{N}</math>
<math>VA = {v \in V}</math>
 
Para cada iteração <math>t</math>, enquanto <math>|VA| > 0</math>:
VA = {v \in V}
Para cada vértice <math>v \in VA</math>:
 
<math>PR(v, t+1) = \frac{1-d}{N} + d \sum_{u \in M(v)} \frac{PR(u, t)}{L(u)}</math>
Para cada iteração t, enquanto |VA| > 0:
<math>VA = {v \in V : |PR(V, t+1) - PR(V, t)| > MAX_ERR}</math>
 
</code>
Para cada vértice v \in VA:
 
PR(v, t+1) = \frac{1-d}{N} + d \sum_{u \in M(v)} \frac{PR(u, t)}{L(u)}
 
VA = {v \in V : |PR(V, t+1) - PR(V, t)| > MAX_ERR}
 
=== Exemplo de Funcionamento ===
=== Oportunidades de paralelização ===
 
OComo 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 de ranks atualizados.
 
A paralelização pode ser ampliada se os somatórios de ranks forforem divididodivididos. 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 criandofazendo as threads que somamsomarem números aproximados de nodos e; os nodos que tem mais apontadores seriam divididos ementre mais threads, enquanto uma thread pode fazer o somatório para mais de um nodo.
 
=== 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 atual desses nodos junto com o número de nodos para os quais eles apontam ou apenas a divisão dessesentre esses 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 é relativamente baixo.
 
Quando o volume de dados é muito grande, o processamento teria tempo de execução longo e os dados podem não caber noem um só 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 na rede.
 
=== Padrões de comunicação ===
 
É necessário fazer comunicação para sincronizar as linhas de execução de cada threadthreads no final de cada threaditeração 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. Essa sincronização pode ser vista como duas barreiras, em que a primeira espera todos os somatórios terminar e a segunda espera todos os ranks serem 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 em cada iteração seria igual ao número de arestas do grafo, e issoesse pode sobrecarregar a rede, porque ogrande número de mensagens épode muitosobrecarregar grandea rede.
 
=== 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 ==
5

edições