Re:Google's Introduction to Parallel Programming and MapReduce
by defen on Sunday October 23, 2011 @04:58PM
(#3147236)
[1 1; 1 0]^n = [Fn+1 Fn; Fn Fn-1]
So you could rewrite n as a sum of m powers of 2 (just write it in binary), then for each "1" there, send it to a separate processor to compute [1 1; 1 0]^k using exponentiation by squaring (where k is the corresponding power of 2). Your reduce step multiplies the resulting matrices together.
Note: this is just the first thing that comes to mind, I have no idea if this is what you were thinking of, or if it's even a good idea.
Re:Google's Introduction to Parallel Programming and MapReduce
by SamReidHughes on Sunday October 23, 2011 @06:28PM
(#3147481)
Since computing [1 1; 1 0]^(2k) where k is a power of 2 would involve computing [1 1; 1 0]^k first, you'll end up reproducing the exact same work on all your machines, and you might as well just use the one.
Edit: to be clear, I don't mean the obvious but useless trick where you can compute F(n-1) and F(n-2) recursively in parallel, which is just redoing most of the work. I mean a way to model the problem as operations on data-parallel vectors.