<div>Ssssh. I'm trying to take over Tim's cluster.</div>
<div>peter<br><br> </div>
<div><span class="gmail_quote">On 8/16/07, <b class="gmail_sendername">Jack C</b> <<a href="mailto:jack@crepinc.com">jack@crepinc.com</a>> wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">Peter,<br><br>You can always install MPI on a single host to test your code, even if you don't have a cluster. You can even run multple threads on that single host, it just won;t have the speedup that multiple hosts would.
<br><br>-Jack Carrozzo
<div><span class="e" id="q_11470732d92320d2_1"><br><br>
<div><span class="gmail_quote">On 8/16/07, <b class="gmail_sendername">Peter St. John</b> <<a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:peter.st.john@gmail.com" target="_blank">peter.st.john@gmail.com
</a>> wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid">
<div>Tim,</div>
<div>I thought about this some. I don't have a cluster, but I can program in C; you have a cluster, but don't want to program too much. It's possible we can help each other.</div>
<div> </div>
<div>A toy application I thought of is finding numbers that can written as a sum of two cubes in two different ways (there's a famous story about Ramanujan recognizing the four-digit number of a taxicab as "the smallest number than can be expressed as a sum of two cubes in two distinct ways").
</div>
<div> </div>
<div>So I had this plan. I went to wiki and got the source of an MPI "hello world" application, <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://en.wikipedia.org/wiki/Message_Passing_Interface" target="_blank">
http://en.wikipedia.org/wiki/Message_Passing_Interface </a></div>
<div> </div>
<div>Then I wrote a C program to take a range of numbers, say 1000 to 1999, and find the numbers in that interval that have the taxicab quality (it turns out that's what such numbers are called now!).</div>
<div>Since I don't have the MPI library or a cluster I can't test the integrated thing, so at the moment all I have is the wiki example (which just fills a buffer with "I am node #<whatever>" for later reporting), which presumably is an OK example of MPI, and my own code (which just does arithmetic) which I tested myself. So if you wanted, you could try and integrate these, and see if you can find bigger reults by compiling for 64 bit arithmetic.
</div>
<div> </div>
<div>My program wastes a huge amount of redundant calculation; it's only virtue is to split the memory required among nodes. So it computes x^3 + y^3 for silly huge ranges of x and y, at each node, but only stores results for comparisons in limited ranges which can be split up among nodes.
</div>
<div> </div>
<div>I was disappointed at first because I only got 1729 (which was Ramanujan's number, the smallest), and 4,104:</div>
<div> </div>
<div>C:\PeteStJohn\Experiments\Ramanujan\Debug>ramanujan<br>Deubg: i = 0<br>DEBUG: HIT:<br> 01729 = 12^3 + 1^3,<br> 01729 = 10^3 + 9^3<br>DEBUG: HIT:<br> 04104 = 16^3 + 2^3,<br> 04104 = 15^3 + 9^3<br>Deubg: i = 1000<br>
DEBUG: i = 1588 is too big.<br>Findrama made 2 hits<br>Winner 4104:<br>= 16 + 2<br>= 15 + 9</div>
<div> </div>
<div>but I checked, putting those two numbers, 1729 and 4104, into the Online Encyclopedia of Integer Sequences <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.research.att.com/~njas/sequences/?q=1729%2C+4104&language=english&go=Search" target="_blank">
http://www.research.att.com/~njas/sequences/?q=1729%2C+4104&language=english&go=Search </a>, and that got me the "Taxi Cab Sequence" and the next value is 13,832. My program is naive, using an exhaustive and redundant search, with only 32 bit, so I get stuck when 1588 is too big becaues it's cube is bigger than about 4 billion, the extent of a 32 bit int. Also I didn't take the time even to accommodate the signum bit.
</div>
<div> </div>
<div>I suggest you look at the wiki link. If you want to hack that code (which could be confusing because the address of something in this node's memory may not make sense when passed to some other node, but the MPI library makes some accommodation) let me know and I'll send you my C program, to call from inside that Wiki program.
</div>
<div> </div>
<div>You might start by just running the wiki example, and see if it works and what you have to do to make it work. If that seems like fun then we can try doing math with it.</div>
<div> </div>
<div>I think I'll integrate them myself, but I wouldn't be able to test it directly. If you think this toy project is the kind of thing you could use let me know. Maybe some day you will run my genetic algorithm app, which is not a toy, for me, and I won't need a cluster :-)
</div>
<div> </div>
<div>Well, here. It's not that big a program so I'll just paste it in. Serious software engineers may avert their eyes.</div>
<div> </div>
<div>
<p>// FindRama<br>// Toy parallelizable math application<br>// Pete St.John 8/2007<br>//</p>
<p>#include <stdio.h><br>#include <stdlib.h><br>#include <malloc.h></p>
<p><br>#define BIGGEST 4000000000<br>// sloppy way to deal with 32-bit limitation</p>
<p>struct pair<br>{<br> long x;<br> long y;<br>};<br>// a pair of integers; the sum of their cubes matters to us.</p>
<p>struct winner<br>{<br> long win;<br> struct pair first;<br> struct pair second;<br>};<br>// any pair you want to keep and report, e.g. the largest summand found in the range.</p>
<p>int findrama(int myid, long z1, long z2, struct winner *winnerp);<br>// findrama finds numbers which are sums of cubes in two distince ways, <br>// e.g. 1729 = 12^3 + 1^3 but also = 10^3 + 9^3<br>// "myid" is the hypothetical node number of the MPI instance that would invoke this
<br>// z1 and z2 are the range of numbers to search, e.g. 1729 might be found <br>// between 1000 and 19999;<br>// winner is the "best" result found, which in this example is the largest.</p>
<p><br>int main(int argc, char **argv)<br>{<br> // I'm not doing much in this main. We want to use the wiki MPI example<br> // main to call "findrama" with a range of numbers, perhaps based on myid; e.g.<br>
// node 1 does z = 1 to 1999, node 2 does 2000 to 2999, etc, based on the number<br> // of nodes you have and the largest arithmetic you can do.</p>
<p> int myid;</p>
<p> int hits;</p>
<p> struct winner mywinner;</p>
<p> myid = 0;</p>
<p> hits = findrama(myid, 1, 10000, &mywinner);</p>
<p> printf("Findrama made %d hits\n", hits);</p>
<p> if(hits < 0)<br> {<br> printf("Error, probably malloc error.\n");<br> return 0;<br> }</p>
<p> printf("Winner %d:\n", mywinner.win);<br> printf("= %d, %d\n", mywinner.first.x, mywinner.first.y);<br> printf("= %d, %d\n", mywinner.second.x, mywinner.second.y);</p>
<p> return 0;<br>}</p>
<p>int findrama(int myid, long z1, long z2, struct winner *winnerp)<br>{<br> struct pair *p;<br> long range;<br> long i, j, k;<br> int hits;<br> long bigz, z;<br> long xi, xj;<br> long xsum;</p>
<p> //struct pair newpair;<br> struct winner mywinner;</p>
<p> bigz = 0;</p>
<p> hits = 0;</p>
<p> range = (z2 - z1);<br> p = malloc( range * sizeof(struct pair));<br> //<br> // malloc should return a pointer to a range of allocated memory <br> // large enough for "range" pairs, and pair takes up space for two long integers.
<br> //</p>
<p> if(!p)<br> {<br> fprintf(stderr, "Error: unable to malloc at myid = %d\n", myid);<br> return -1;<br> }<br> // in the zth offset we will store the pair x, y st x^3 + y^3 = z^3<br> // for z in the range from z1 <= z < z2
</p>
<p> // zero out<br> for(i=0; i < range; i++)<br> {<br> p[i].x = 0;<br> p[i].y = 0;</p>
<p> }</p>
<p> //z2cube = z2 * z2 * z2;</p>
<p> for(i = 0; i < z2; i++)<br> {<br> xi = i*i*i;</p>
<p> if(xi > BIGGEST)<br> {<br> printf("DEBUG: i = %d is too big.\n", i);<br> break;<br> }</p>
<p> // debug<br> if(i%1000 == 0)<br> {<br> printf("Deubg: i = %d\n", i);<br> }</p>
<p> for(j = 0; j <= i; j++)<br> {<br> xj = j*j*j;<br> xsum = xi + xj;</p>
<p> if(xsum > z2)<br> {<br> // we've exceeded our range<br> break;<br> }<br> <br> for(k = 0; k< range; k++)<br> {<br> z = z1 + k;</p>
<p> if(z == xsum)<br> {<br> if(p[z].x == 0 && p[z].y == 0)<br> {<br> // found this sum of cubes for the first time<br> p[z].x = i;<br> p[z].y = j;<br> }<br> else<br> {<br>
// we have discovered a number that<br> // can be written as a sum of two cubes<br> // in two distince ways.<br> hits++;</p>
<p> printf("DEBUG: HIT:\n %05d = %d^3 + %d^3,\n %05d = %d^3 + %d^3\n",<br> z, i, j, z, p[z].x, p[z].y<br> );<br> mywinner.win = z;<br> mywinner.first.x = i;<br> mywinner.first.y = j;
<br> mywinner.second.x = p[z].x;<br> mywinner.second.y = p[z].y;<br> }<br> }<br> }<br> }<br> }<br> winnerp->win = mywinner.win; <br> winnerp->first.x = mywinner.first.x;<br> winnerp->first.y =
mywinner.first.y;<br> winnerp->second.x = mywinner.second.x;<br> winnerp->second.y = mywinner.second.y;</p>
<p> </p>
<p> return hits;<br>}</p></div><span>
<div> </div>
<div>Peter</div></span>
<div><span>
<div> </div>
<div><br><br> </div>
<div><span class="gmail_quote">On 8/16/07, <b class="gmail_sendername">Robert G. Brown</b> <<a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:rgb@phy.duke.edu" target="_blank">rgb@phy.duke.edu</a>
> wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid">On Tue, 14 Aug 2007, Tim Simon wrote:<br><br>> I would like to know if there is any open source software that will
<br>> run on a beowulf, which will do something like find prime numbers, or<br>> something simillar. I cant afford a commercial program.<br>><br>> I am guessing that there is not "one size fits all" type thing - what
<br>> fits your beowulf wont fit mine. Is there anything that can be easily<br>> made to fit? I have searched all over the net, and all i can find are<br>> educational or high research type applications. I just would like
<br>> something reasonably simple, (I thought prime numbers but hey,<br>> anything is good).<br><br>Writing your own is good. Hunting for primes is actually something that<br>will parallelize decently simply because the Sieve of Erasthones for a
<br>proposed number N only requires that you try all the primes found up to<br>N/2. Therefore a collection of nodes can contain and share all the<br>primes found up to N-1, and distribute the testing of N, N+2, N+4,<br>N+6... N+M (obviously skipping all even numbers) as long as N+M < 2N.
<br><br>For a small number M of nodes, if you precompute and load all the primes<br>less than M -- trivially done -- then you're in business.<br><br>You will have a few longer term problems. A single processor can sieve
<br>all the unsigned int primes from 0-(2^32-1) out fairly quickly anyway.<br>To go beyond this, you'll need to use symbolic division instead of<br>binary computer arithmetic, I think. You'll also run into<br>storage/memory problems as you start to get a significant number of
<br>primes in your running table.<br><br>But it is a fun problem, for sure. Go for it.<br><br>Beyond that, there are a number of programs people use to play with or<br>demonstrate a beowulf's speedup. The "funnest" is any of the
<br>rubberbandable Mandelbrot set exploration tools parallelized on top of<br>MPI or PVM -- makes nifty graphics. It isn't quite as cool as it used<br>to be because Moore's Law has overwhelmed the computational difficulty
<br>of the task. When I started in this business, it might have taken<br>minutes to compute a rubberbanding down into the MS, depending on where<br>one was (and how deep one had to go on all those pixels to terminate).<br>
Parallelize that on sixty or so nodes and it drops DRAMATICALLY to<br>seconds.<br><br>Now CPUs are so fast that a SINGLE CPU can rubberband down in a second<br>or two, and networks haven't kept pace so that computing the pixels in a
<br>single thread might actually be faster than splitting them. So speedup<br>is a bit less dramatic, but still very cool.<br><br> rgb<br><br>> I am running Red Hat FC4.<br><br>Hmmm, might at least TRY 6 or 7.<br><br>
<br>><br>><br>> Tim<br>> _______________________________________________<br>> Beowulf mailing list, <a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:Beowulf@beowulf.org" target="_blank">
Beowulf@beowulf.org</a><br>> To change your subscription (digest mode or unsubscribe) visit <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.beowulf.org/mailman/listinfo/beowulf" target="_blank">
http://www.beowulf.org/mailman/listinfo/beowulf</a><br>><br><br>--<br>Robert G. Brown <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.phy.duke.edu/~rgb/" target="_blank">
http://www.phy.duke.edu/~rgb/ </a><br>Duke University Dept. of Physics, Box 90305<br>Durham, N.C. 27708-0305<br>Phone: 1-919-660-2567 Fax: 919-660-2525 <a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:email:rgb@phy.duke.edu" target="_blank">
email:rgb@phy.duke.edu</a><br><br><br>_______________________________________________ <br>Beowulf mailing list, <a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:Beowulf@beowulf.org" target="_blank">Beowulf@beowulf.org
</a><br>To change your subscription (digest mode or unsubscribe) visit <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.beowulf.org/mailman/listinfo/beowulf" target="_blank">http://www.beowulf.org/mailman/listinfo/beowulf
</a><br></blockquote></div><br></span></div><br>_______________________________________________<br>Beowulf mailing list, <a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:Beowulf@beowulf.org" target="_blank">
Beowulf@beowulf.org</a><br>To change your subscription (digest mode or unsubscribe) visit <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.beowulf.org/mailman/listinfo/beowulf" target="_blank">http://www.beowulf.org/mailman/listinfo/beowulf
</a><br><br></blockquote></div><br></span></div></blockquote></div><br>