[Beowulf] Good demo applications for small, slow cluster

[Peter St. John]

Max,
Remarkable, thanks! I surely agree that in binary, doubling is fast. So you
sort of bypass computing low powers, with an ancient method (?!) of
computing high powers efficiently. Very cool. So, everything is
parallelizable :-)
Peter


On Wed, Aug 21, 2013 at 3:22 PM, Max R. Dechantsreiter <
max at performancejones.com> wrote:

> Hi Peter,
>
>
>  That's interesting, where can I read about "giant-stepping the generator"?
>> The wiki article
>> http://en.wikipedia.org/wiki/**Linear_congruential_generator<http://en.wikipedia.org/wiki/Linear_congruential_generator>doesn't
>> mention distributed processing.
>>
>
> The term "giant-stepping" may not be in general use....
> The idea is to find an efficient way to compute an RNG state
> far ahead of the current one.
>
> For a multiplicative generator like that of the NPB:
>
>         x[k+1] = a * x[k] mod p
>
> (p not necessarily prime), observe that
>
>         x[k+2] = a * x[k+1] mod p = a**2 * x[k] mod p
>
> so
>
>         x[k+m] = (a**m mod p) * x[k] mod p
>
> a**m mod p may be efficiently computed by Russian Peasant:
>
>         http://en.wikipedia.org/wiki/**Ancient_Egyptian_**
> multiplication#Russian_**peasant_multiplication<http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication#Russian_peasant_multiplication>
>
> Then
>
>         x[k+2*m] = (a**m mod p) * x[k+m] mod p
>
> et cetera.  Single-threaded operations fill in the rest.
>
> For LFSR-based generators, the multiplier is a bit matrix,
> so powers of that matrix would need to be computed (also by
> Russian Peasant).
>
> The scheme would be particular to each generation algorithm.
>
> Surprisingly many RNG can be parallelized this way; the big
> advantage over (say) simply giving each computational thread
> private RNG parameters is that with care the results of a
> parallel computation could match those of a serial one.
>
> Regards,
>
> Max
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.beowulf.org/pipermail/beowulf/attachments/20130821/d7886560/attachment.html>