From: ptkwt@...1.aracnet.com (Phil Tomson) Date: 2002-01-25T13:15:49+09:00 Subject: Re: looking for an example problem to demonstrate TaskMaster In article , Bob Hutchison wrote: >On 1/24/02 5:36 PM, "Phil Tomson" wrote: > >> In article , >> Dave Thomas wrote: >>> ptkwt@shell1.aracnet.com (Phil Tomson) writes: >>> >>>> I'm looking for suggestions here... >>> >>> The good ol' Mandelbrot calculation? >>> >> Actually, now that I think about it doing the Mandelbrot on several >> machines and then sending back all the data points to the central 'server' >> would require too much information transfer vs compute time. >> > >The obvious: To demonstrate this kind of thing you want a problem that is >easily partitioned into chunks to be solved, chunks that take more compute >time than communications time, and chunks whose results are easily >assembled. However, if you can find a problem that is non-linearly dependent >on its size you have an additional advantage you can use to offset the >communications problem (the sub-problems are smaller so compute faster, >sometimes much faster). Also, what are you trying to demonstrate? that >TaskMaster works, or to show its potential? It might be nice to have >something useful too. The goal would be to not only show its potential, but also to show how to use it. I've already got it working in a fairly complex test system to test a logic synthesis tool. There are thousands of testcases that get run. A test case gets synthesized to structural VHDL (logic gates) and then simulated (some flows are more complex, but that's basically what happens). Each testcase takes anywhere from 2minutes to about an hour - so its a perfect application for TestMaster. The amount of computation done is much greater than the amount of data sent back afterwards (it only sends back a pass/fail status and some totals. I can't really use this application for a demo because 1) It's too complex for a demo 2) It's pretty large 3) It's done for a company. > >I'm not sure any of these ideas are suitable, but they might trigger a >thought. > >Years ago I was involved in something like this. The intention was to use >multiple machines to ray-trace complex scenes (3D graphics). This worked >wonderfully. The Mandelbrot might be a similar problem and so suitable, but >I don't know much about the problem. Can the problem be partitioned on the >top level, or is it a tree-like thing? (If it is tree like you might be able >to run the problem until there are as many leaves as there are processors >and then distribute the sub-problems). If all the sub-problems are the same >size and there are many of them and they are easy to compute then this won't >demonstrate anything good. And you are going to have to display the results >of a graphical application, which may be difficult. > >You might be able to show sorting work faster. Use a bubble sort, something >that is seriously dependent on the length of the list, split the list into >pieces (one for each processor) distribute and sort, then merge the sorted >sub-lists upon their return. Any sorting algorithm should work, but some >will demonstrate better. Unfortunately, this is a really abstract kind of >demo -- it won't impress anyone but people who can understand how to use it >(i.e. you are simply proving it works, not necessarily informing people of >the possibilities) This might be a good demo application. It's pretty simple. > >We used the same basic framework that controlled the rendering to control a >distributed compilation process (shoved source code around the network, each >node compiled then returned the object code). Try re-compiling ruby, see >what happens (compilers are much faster now than they were, so things won't >be so dramatic as they used to be). However, running unit tests are as slow >now as they ever were, or it seems that way. Could you distribute Ruby's >unit tests? Could you build TaskMaster into Runit or Lapidary? > I thought about applying it to Rubicon (Ruby's own set of unit tests) but they only take a couple of minutes to run on one machine, so I'm not sure it would be compelling. Now if there were about a thousand more testcases, it might be a very good demo. I'm wondering if gcc might have a testsuite - that might be a good demo if it's big enough. I do know that Icarus Verilog (an open source Verilog simulator - Verilog is an HDL[Hardware Description Language]) has some sort of testsuite and in fact Icarus does call gcc (Verilog gets converted to C) and then executes the resulting binary; adding more nodes to distribute testcases to should speed it up significantly. >Encryption/decryption might be similar to the distributed compilation demo. > That's an idea too, but to be honest I don't know much about the topic. Phil