Parallelizing a serial algorithm

Question

Hej folks,

I am working on porting a Text mining/Natural language application from single-core to a Map-Reduce style system. One of the steps involves a while loop similar to this:

Queue<Element>;

while (!queue.empty()) {
    Element e = queue.next();
    Set<Element> result = calculateResultSet(e);

    if (!result.empty()) {
        queue.addAll(result);
    }
}

Each iteration depends on the result of the one before (kind of). There is no way of determining the number of iterations this loop will have to perform.

Is there a way of parallelizing a serial algorithm such as this one? I am trying to think of a feedback mechanism, that is able to provide its own input, but how would one go about parallelizing it?

Thanks for any help/remarks

Answer 1

Maybe you could split calculateResultSet into several different functions that operate on the entire set. This way, you could give all the functions the entire set and have each function perform a separate operation. Once all functions have completed, you can then feed all the results to another function to create the final output. This would allow you to send the data to different nodes, perform an operation, and finally gather the results using a distributed architecture.

You could also look into the notion of sharing. A classic example is the fibonacci sequence where xn is dependent on xn-1 and xn-2. Here is an example of a parallelized version using OpenMP: http://myxman.org/dp/node/182