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