1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This ia an awfully wide open question... can you give some futher details? $\endgroup$ – vonbrand May 24 '13 at 22:02
4
$\begingroup$

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:

sequential algorithm

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:

Chunked up 4 ways

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.

$\endgroup$
  • $\begingroup$ let me check if I understood... Consider that I have 100 interactions to be evaluated so I can get the most recent version of the modeled rate by this function. Consider I use 10 threads to parallely update it. I set every thread to deal with 10 interactions. Every thread will define its A and its B. Then, when I need to apply the effect of every thread, I just apply every pair of A and B generated by every thread. Right? It would be something like: x100= At10 + Bt10*(At09 + Bt09*(At08 + Bt08*(At07 + Bt07*(At06 + Bt06*(At05 + Bt05*(At04 + Bt04*(At03 + Bt03*(At02 + Bt02*(At01 + Bt01*x0))))))))) $\endgroup$ – Samuel Siqueira May 28 '13 at 17:14
  • $\begingroup$ Yes, that is correct. Hopefully you have 10s of 1000s of interactions, otherwise the overhead of coordinating the threads and doing the final sum is going to swamp your parallelism gains. $\endgroup$ – Wandering Logic May 28 '13 at 20:58
  • $\begingroup$ Thank you very much! It is very intuitive and interesting! $\endgroup$ – Samuel Siqueira May 28 '13 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.