<div dir="ltr">Regarding <div><span style="font-family:arial,sans-serif;font-size:13px">"...There are probably simple algorithms which are</span><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">efficient in a single processor environment, but become egregiously</span><br style="font-family:arial,sans-serif;font-size:13px">
<span style="font-family:arial,sans-serif;font-size:13px">inefficient when distributed..."</span><br></div><div><span style="font-family:arial,sans-serif;font-size:13px">What about the old random number generator: take a 16 bit seed, square it, take the middle 16 bits, and repeat. They'd want a large number in order (so you can repeat an experiment, or a run of a model, with the same "random" numbers), and it's easy to computer sequentially; but if you want a million of them it would be nice to distribute the job, but I don't think you can. But maybe "can't parallelize" isn't the same as "badly inefficient to parallelize".</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">But I'd use something like that (besides the famous example that 9 women can't make a baby in one month) as an algrorithm that has to be done sequentially.</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">Peter</span></div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Aug 21, 2013 at 10:10 AM, Lux, Jim (337C) <span dir="ltr"><<a href="mailto:james.p.lux@jpl.nasa.gov" target="_blank">james.p.lux@jpl.nasa.gov</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Sorts in general.. Good idea.<br>
<br>
Yes, we'll do a distributed computing bubble sort.<br>
<br>
Interesting, though.. There are probably simple algorithms which are<br>
efficient in a single processor environment, but become egregiously<br>
inefficient when distributed.<br>
<br>
Jim<br>
<br>
<br>
<br>
On 8/20/13 12:11 PM, "Max R. Dechantsreiter" <<a href="mailto:max@performancejones.com">max@performancejones.com</a>><br>
wrote:<br>
<div class="HOEnZb"><div class="h5"><br>
>Hi Jim,<br>
><br>
>How about bucket sort?<br>
><br>
>Make N as small as need be for cluster capability.<br>
><br>
>Regards,<br>
><br>
>Max<br>
>---<br>
><br>
><br>
><br>
>On Tue, 20 Aug 2013 <a href="mailto:maxd@performancejones.com">maxd@performancejones.com</a> wrote:<br>
><br>
>> Date: Tue, 20 Aug 2013 00:23:53 +0000<br>
>> From: "Lux, Jim (337C)" <<a href="mailto:james.p.lux@jpl.nasa.gov">james.p.lux@jpl.nasa.gov</a>><br>
>> Subject: [Beowulf] Good demo applications for small, slow cluster<br>
>> To: "<a href="mailto:beowulf@beowulf.org">beowulf@beowulf.org</a>" <<a href="mailto:beowulf@beowulf.org">beowulf@beowulf.org</a>><br>
>> Message-ID:<br>
>>      <F7B6AE13222F1B43B210AA4991836895236966E9@ap-embx-sp40.RES.AD.JPL><br>
>> Content-Type: text/plain; charset="us-ascii"<br>
>><br>
>> I'm looking for some simple demo applications for a small, very slow<br>
>>cluster that would provide a good introduction to using message passing<br>
>>to implement parallelism.<br>
>><br>
>> The processors are quite limited in performance (maybe a  few MFLOP),<br>
>>and they can be arranged in a variety of topologies (shared bus, rings,<br>
>>hypercube) with 3 network interfaces on each node.  The processor to<br>
>>processor link probably runs at about 1 Mbit/second, so sending 1 kByte<br>
>>takes 8 milliseconds<br>
>><br>
>><br>
>> So I'd like some computational problems that can be given as<br>
>>assignments on this toy cluster, and someone can thrash through getting<br>
>>it to work, and in the course of things, understand about things like<br>
>>bus contention, multihop vs single hop paths, distributing data and<br>
>>collecting results, etc.<br>
>><br>
>> There's things like N-body gravity simulations, parallelized FFTs, and<br>
>>so forth.  All of these would run faster in parallel than serially on<br>
>>one node, and the performance should be strongly affected by the<br>
>>interconnect topology.  They also have real-world uses (so, while toys,<br>
>>they are representative of what people really do with clusters)<br>
>><br>
>> Since sending data takes milliseconds, it seems that computational<br>
>>chunks which also take milliseconds is of the right scale.  And, of<br>
>>course, we could always slow down the communication, to look at the<br>
>>effect.<br>
>><br>
>> There's no I/O on the nodes other than some LEDs, which could blink in<br>
>>different colors to indicate what's going on in that node (e.g.<br>
>>communicating, computing, waiting)<br>
>><br>
>> Yes, this could all be done in simulation with virtual machines (and<br>
>>probably cheaper), but it's more visceral and tactile if you're<br>
>>physically connecting and disconnecting cables between nodes, and it's<br>
>>learning about error behaviors and such that's what I'm getting at.<br>
>><br>
>> Kind of like doing biology dissection, physics lab or chem lab for<br>
>>real, as opposed to simulation.  You want the experience of "oops, I<br>
>>connected the cables in the wrong order"<br>
>><br>
>> Jim Lux<br>
>><br>
>_______________________________________________<br>
>Beowulf mailing list, <a href="mailto:Beowulf@beowulf.org">Beowulf@beowulf.org</a> sponsored by Penguin Computing<br>
>To change your subscription (digest mode or unsubscribe) visit<br>
><a href="http://www.beowulf.org/mailman/listinfo/beowulf" target="_blank">http://www.beowulf.org/mailman/listinfo/beowulf</a><br>
<br>
_______________________________________________<br>
Beowulf mailing list, <a href="mailto:Beowulf@beowulf.org">Beowulf@beowulf.org</a> sponsored by Penguin Computing<br>
To change your subscription (digest mode or unsubscribe) visit <a href="http://www.beowulf.org/mailman/listinfo/beowulf" target="_blank">http://www.beowulf.org/mailman/listinfo/beowulf</a><br>
</div></div></blockquote></div><br></div>