Multicore - how to merge local groups of data found on each core?

Question

I have a large set of scalar values distributed over a 3D mesh (one value per vertex.)

My goal is to show:

• all points in the mesh where the value is greater than a threshold.
• AND group the points that are connected (to simplify the display.)

So my basic solution was:

1. Find the points that pass the threshold test
2. For each point that has not been grouped, create a new group and recursively put all connected points into that group.

This works fine, until I started using a multicore solution:

• The data set has been divided across multiple cores
• Each core knows about boundary points that are shared by other cores.
• I'm using MPI to communicate between cores.

I used my original algorithm to find "local" groups a single core.

My challenge is to merge "local" groups into global groups. The problem gets complicated for a number of reasons: Connected groups can cross many core boundaries. Groups that seem separate on one core can be connected by a group on a second core.

Thanks in advance. Jeff

Answer 1

the threshold test can be carried out locally, so for the sake of simplicity we can eliminate it from the discussion. What you want is to have a distributed algorithm that calculates the connected components in your graph. This paper should be very relevant:

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