Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Identificação de ciclos em grafos: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição
Sem resumo de edição
Linha 78:
==== Implementação Paralela no Sistema GraphChi ====
 
Considerando que a implementação principal do modelo Pregel da Google possui código fechado, pode ser interessante avaliar uma alternativa ao modelo Pregel. Uma das alternativas é o sistema GraphChi da GraphLab. Esse sistema fornece uma ''engine'' para processamento de grafos, no contexto de dados massivos, em uma única máquina. O sistema apresenta um processamento baseado em disco (memória secundária) para computação eficiente de grafos de grande escala.
Implementação da função Update no sistema do GraphChi
 
Diferentemente do modelo Pregel, GraphChi é uma ''engine'' baseada em memória compartilhada. Em GraphChi, cada vértice e cada aresta armazena um dado. A comunicação entre os vértices durante o processamento paralelo é realizada com base nos dados armazenados pelos vértices e arestas.
 
De maneira semelhante ao modelo Pregel, GraphChi também apresenta uma abordagem centrada nos vértices. A ''engine'' do GraphChi consiste basicamente em uma sequência de iterações, nas quais, para cada vértice é executado uma função de atualização (''update''). Antes de cada iteração a ''engine'' executa uma função chamada ''before_iteration'' e após cada iteração é executada a função ''after_iteration''.
 
A seguir é apresentado uma implementação do algoritmo de detecção de ciclos em grafos por passagem de mensagens usando o sistema do GraphChi. Esta implementação fornece uma abstração semelhante ao modelo Pregel sobre a engine do GraphChi, incluindo a abstração de passagem de mensagens, o que é conveniente para o algoritmo de detecção de ciclos proposto.
 
Todo aplicação do sistema GraphChi deve implementar a classe abstrata GraphChiProgram. A classe GraphChiProgram fornece os métodos públicos apresentados pelo código da classe CycleDetection a seguir.
 
<source lang=cpp>
typedef vid_t VertexDataType;
typedef list<list<vid_t>*>* EdgeDataType;
 
graphchi_engine<VertexDataType, EdgeDataType> *enginePtr;
int countIteration;
size_t finishedVertices;
 
#define activateVertex() finishedVertices--
#define initIteration() finishedVertices = gcontext.nvertices
#define closeIteration() if(finishedVertices==gcontext.nvertices) enginePtr->set_outside_closing(true)
 
class CycleDetection : public GraphChiProgram<VertexDataType, EdgeDataType> {
Linha 104 ⟶ 120:
};
</source>
 
O código a seguir apresenta a implementação do método ''update'' que é equivalente à função COMPUTE do modelo Pregel. O método ''update'' é a implementação principal do algoritmo de detecção de ciclos por passagem de mensagens apresentado anteriormente pelo pseudo-código da função COMPUTE.
 
Basicamente, a implementação consiste em percorrer todas as arestas de entrada, recolhendo todas as "mensagens" recebidas, para poder realizar o processamento nas listas de vértices recebidas. Para cada lista de vértice recebida, é realizado o processamento sobre a lista e, caso necessário, a lista com o novo vértice é encaminhada para as arestas de saída.
 
<source lang=cpp>
Linha 140 ⟶ 160:
}
</source>
 
Os métodos implementados no código a seguir fornecem a implementação necessário no modelo GraphChi para oferecer uma abstração do término de execução da aplicação com base nos vértices estarem ativos ou não, semelhante ao modelo Pregel.
 
<source lang=cpp>
graphchi_engine<VertexDataType, EdgeDataType> *enginePtr;
int countIteration;
size_t finishedVertices;
 
#define activateVertex() finishedVertices--
#define initIteration() finishedVertices = gcontext.nvertices
#define closeIteration() if(finishedVertices==gcontext.nvertices) enginePtr->set_outside_closing(true)
 
void CycleDetection::before_iteration(int iteration, graphchi_context &gcontext) {
Linha 165 ⟶ 180:
 
</source>
 
Os métodos apresentados asseguir apresentam algumas funções úteis para o algoritmo principal e algumas delas auxiliam na abstração de passagem de mensagens. Observe que o método ''outputCycle'' é apenas uma ilustração. Esse método deve receber uma lista contendo os ''ID''s dos vértices que representam um ciclo, e executar alguma computação sobre o ciclo recebido, que melhor convir para a aplicação em questão.
 
<source lang=cpp>