Disclaimer: If you're not into parallelization (on clusters), this question is probably not interesting to you and probably not worth a read.
TL;DR: I search for a communication model (preferably compatible with
MPI) that efficiently assures that each data line is processed once. Read the next paragraph as well to know what I mean by data line.
Consider the following problem: An algorithm takes a data line (in my case, an array of integers with fixed size) and produces various data lines which then need to be processed by the same algorithm. Each unique data line only needs to be processed once, since the outcome is purely deterministic. The set of unique data lines is finite, so after a finite number of recursive calls of this algorithm it produces the whole set. The goal is to find this set.
I've already implemented the algorithm and I've also implemented a parallelization. Obviously, since we need to process each unique data line, at each time all currently unprocessed data lines may be processed by different processors in parallel.
On the other hand, parallelization introduces the problem of keeping the different processors from doing redundant work.
A trivial implementation would send data lines to processors, collect all results and distribute again. This may be inefficient since the (possibly large) result lists have to be merged before any further work may be done. If all lists are returned around the same time, the master is overwhelmed by the sheer amount of data while all slaves idle until all merging is done.
My (as far as I think, improved) communication model is still basically Master-Slave:
This is what the Master does:
Distribute initial chunk of data lines to slaves While there is at least one active slave for each active slave Request data line if slave doesn't have a data line set slave inactive, break else if the data line was previously processed break endif if there is an inactive slave send the data line to inactive slave and mark that slave as active send the sending slave a notification to not process the data line else notify the slave to process the data line it just sent endif endif endfor endwhile
Each slave does this:
while true wait for request if data line available send it wait for master to say if the line should be processed here process if necessary go back to beginning else notify master wait for master to send a data line process the received line go back to beginning endif
The slave manages its own local list of processed and unprocessed data lines. For each request, one element of the unprocessed ones is moved to the processed ones. Only unique entries among both lists are stored.
In conclusion: Only the master knows about the full set of processed lines. a slave processes a data line if and only if the master says that it wasn't previously processed. The Master doesn't know about the results for each data line until it has requested all available lines from each slave.
As far as I can think, this model of communicating the list of processed data lines is pretty efficient, but I'm new to the world of parallelization, especially in the world of parallelization on a cluster.
What are other ways of efficiently communicating data lines among several processors to assure that each data line is processed exactly once?
This question is basically not bound to the combination of
MPI, though any answer reflecting the way the Message Passing Interface works are greatly appreciated.