Multicore - como mesclar grupos locais de dados encontrados em cada núcleo?

Question

I têm um grande conjunto de valores escalares distribuídos sobre uma malha 3D (um valor por vértice.)

Meu objetivo é mostrar:

• todos os pontos da malha onde o valor é maior do que um limite.
• E agrupar os pontos que estão conectados (para simplificar a exibição.)

Assim, a minha solução básica foi:

1. Encontre os pontos que passam o teste de limiar
2. Para cada ponto que não tenha sido agrupados, criar um novo grupo e de forma recursiva colocar todos os pontos conectados nesse grupo.

Esta multa funciona, até que eu comecei a usar uma solução multicore:

• O conjunto de dados foi dividido em vários núcleos
• Cada núcleo sabe sobre pontos de fronteira que são compartilhados por outros núcleos.
• Eu estou usando MPI para a comunicação entre núcleos.

Eu usei o meu algoritmo original para encontrar grupos "locais" um único núcleo.

O meu desafio é unir grupos "locais" em grupos globais. O problema se complica por uma série de razões: grupos conectados pode atravessar muitas fronteiras do núcleo. Grupos que parecem separado em um núcleo pode ser ligado por um grupo em um segundo núcleo.

Obrigado antecipadamente. Jeff

Answer 1

o teste de limiar pode ser realizada localmente, assim, por uma questão de simplicidade, podemos eliminá-lo a partir da discussão. O que você quer é ter um algoritmo distribuído que calcula os componentes conectados em seu gráfico . Este papel deve ser muito relevante:

http://citeseerx.ist.psu.edu /viewdoc/summary?doi=10.1.1.46.1091