Parallelization of an iterative model

What I have:

An iterative process based on the application of a very simple algebra to represent a rate, with total dependence among any iteration and its predecessor (one input parameter for (n)th iteration is the output parameter from the (n-1)th iteration).

What I want:

Some kind of shift on algebra allowing some level of independence among sequential iterations, this way allowing parallelization.

What I know (or believe to) so far:

There is extensive published literature on parallel iterative methods, but most of them are about classical methods like:

http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2006_725.pdf

But I'm failing to recognize which of them I could "use" to help me with my simple algebra.

Question: Can someone help me pointing literature on the basics of algebra transformation aiming parallelization? (any thoughts on that matter will be very helpful)

The Wikipedia article on Recurrence relations may be a good place to get started. It shows some examples and how to solve them. Ultimately this is going to depend on the algebra of your relationship, it may be something simple, or very complex to parallelize.

It's difficult to answer your question without a more specificity on the algebra you are trying to solve.

If your algebra is simple enough that you can write a closed form expression for f(n) - then obviously making it parallel is fairly trivial - - partition the space 0-n, dispatch to each processor, have each calculate f(n) for those values of n, and then recombine the results.

If f(n) cannot be expressed in a closed form, then you are going to have to find some way to partition the domain of the problem. How you might be able to do this depends on the specifics of the calculation you are trying to perform, and the end objective (e.g. are you looking for convergence of some kind? or is it something else?)

The following paper provides a sophisticated answer to your question, taken at face value.

http://www.loria.fr/~contasss/publications/RR-BCC05.pdf

Part of me suspects though that your actual problem isn't quite this complex.

Let me put it this way: I am assuming that you have a database with values of y1....yn. (and possibly z1....zn, wasn't quite sure about that).

Let's further assume that you can create partitions of this data set, with shards or blocks of index values of n. (e.g. y1...y3, y4...y6, y7...y9 etc.)

If you can write an update formula for how to combine the blocks, then you are basically done. Split the data, send each block to a different processor, then do the math to combine the results of each block. (this could also be done in parallel, if it was time consuming, by allocating one processor to each combination calculation)... In fact, in this case, it would be a fairly straightforward application of Map Reduce

One other thing to keep in mind - - in general, we are assuming that this value converges. If that's the case, you probably don't need to process all of the data you have... only enough until it actually does converge... I bring this up because making the algorithm parallel has a variety of costs... and you may find that the costs of a parallel implementation are greater than the benefits.

• the algebra is: f(x, y, z) = x + (y - x) / (z + 1) where: x - is the modeled rate (typical value between 0 and 1) y - is the contribution of every new record to the learning about the rate (typical value 0 or 1) z - is some kind of convergence/learning speed parameter (typical value any integer between 30 and 900) May 26 '13 at 21:00