Parallelization of an iterative function application

Question

What I have

An iterative process based on the application of a very simple function 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). Specifically,

$\qquad f(x, y, z) = x + \frac{y - x}{z + 1}$

with $x$ the modeled rate (typical value between 0 and 1), $y$ the contribution of every new record to the learning about the rate (typical value 0 or 1) and $z$ some kind of convergence/learning speed parameter (typical value any integer between 30 and 900). While $y$ and $z$ are constant, $x$ would be the result of the previous calculation.

What I want

Some kind of manipulation of the function that allows some level of independence among sequential iterations, thus 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 Map-Reduce for Machine Learning on Multicore by Chu et al.

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

Can someone help me pointing literature on the basics of function transformation aiming towards parallelization? Any thoughts on that matter will be very helpful.

Answer 1

A good starting point is the Wikipedia article on Prefix Sums. A particularly good source is Guy Blelloch's article about Prefix Sums.

The idea is this: if you have an associative operator (e.g., "+"), you can turn a long dependent chain of those operators into a tree that is more balanced.

For the example you gave, $f(x,y,z) = x + (y-x)/(z+1)$ we can actually generalize to an entire class of problems. $$ \begin{array}{rcl} x_{i+1} & = & x_i + (y_{i+1}-x_i)/(z_{i+1}+1) \\ & = & \frac{y_{i+1}}{z_{i+1}+1} + \frac{x_i (z_{i+1}+1) - x_i}{z_{i+1}+1} \\ & = & \frac{y_{i+1}}{z_{i+1}+1} + \frac{z_{i+1}}{z_{i+1}+1} x_i \\ & = & a_{i+1} + b_{i+1} x_i\mathrm{,} \end{array} $$ where the $a_i$ and $b_i$ can be calculated completely in parallel. So the calculation looks like:

Ok. So let's look at a few iterations starting at $x_i$ through $x_{i+3}$: $$ \begin{array}{rcl} x_{i+2} & = & a_{i+2} + b_{i+2} x_{i+1} \\ & = & a_{i+2} + b_{i+2} (a_{i+1} + b_{i+1} x_i) \\ & = & (a_{i+2} + a_{i+1} b_{i+2}) + b_{i+2}b_{i+1} x_i \\ x_{i+3} & = & a_{i+3} + b_{i+3} x_{i+2} \\ & = & a_{i+3} + b_{i+3} (a_{i+2} + a_{i+1} b_{i+2} + b_{i+2}b_{i+1}x_i)\\ & = & (a_{i+3} + a_{i+2}b_{i+3} + a_{i+1}b_{i+3}b_{i+2}) + b_{i+3}b_{i+2}b_{i+1}x_i\\ & = & A_{i+1,i+3} + B_{i+1,i+3}x_i \end{array} $$

and so on. The interesting thing is that we can calculate $x_{i+k}$ as $A_{i+1,i+k} + B_{i+1,i+k}x_i,$ where large chunks of computation can be summed up independently in the $A_{i+k}$ and the $B_{i+k},$ without knowing $x_{i+1}, \cdots, x_{i+k-1}.$

Now let's chunk up the work of calculating the $x_i$'s. Here's what it might look like if we divided the calculation up into 4 equal parts and put each part on a different thread:

So each thread works completely independently to calculate the $A_i$ and $B_i$. Then we have a final (sequential) phase where we calculate $x_{n/4}, x_{2n/4}, x_{3n/4},$ and $x_n$.

As Guy Blelloch's article shows, you can actually calculate all the partial sums with one last step, if you need them.