Slashdot Mirror
Export Controls on Beowulf?
Gary Franczyk writes, "The United States government has tightly controlled the export of "supercomputers" to certain other nations (i.e., China, Pakistan, India, etc.) for quite some time. Sun has had to deal with this numerous times when selling their equipment. How will the U.S. government handle the fact that now anyone with access to large numbers of PCs can create a "super-computer" cluster? I'm sure that the government is using Beowulf to do nuclear simulations right now... Who says that other nations cannot do the same? " Interesting thought. I'm not aware of any export controls on Beowulf, but with the U.S.'s views on cryptography, how will it be before such draconian views extend to any powerful computing technology? Is it even possible for the U.S. to restrict Beowulf in any way?
They haven't stopped the Socialist Open Source movement, so how could they stop the Socialst Supercomputer movement?
If the people demand Linux-based supercomputers, then dammit, they will have them.
You can bet your nexct IPO on it, pal.
Yep, that should keep the cat in the bag. It worked for cryptography, after all. Them furriners don't have kryptography, 'cause of our export controls.
Oh, well.....
See what I've been reading.
Well, the feeling I get when I read all those export restriction stories is that it applies only to hardware. If software would be included in the export control I'm afraid TCP/IP could be classified as do-not-export-to-some-countries software? :>. Anyways, I've always thought this supercomputer export laws to be pretty silly, what if the countries would just lease supercomputer time in the US, no need to export any hardware!
J.
Apple advertised its G4 range a while back as being too powerful to export to unstable countries because the US government classified it as a munition.
Off the record, however, Apple staff here in the UK told me that the USG didn't specifically restrict the G4, as there were other, more powerful systems that were already available on the general market that were more suited to tinkering with things beyond man's ken and other dictatorish type things.
I'm assuming they were referring to things like Beowulf and various other Unix machines.
IMHO the restrictions applied to older machines, back when men wore plaid and a gigaflop meant not having to say you were sorry...
Golf; a good walk spoiled. -Mark Twain
In cases such as this, it may be worth exercising caution: nothing to do with the usual conspiracy theory, but what if these simple minded government/secret service types hadn't actually thought of the Beowulf as being a supercomputer?
Anyway, that was just hypothetical, we all know that if China or Russia wanted to use Beowulf software against the US's wishes, they would do and there'd be nothing that could be done about it.
Ripping an new rectum in the fabric of spacetime.
It came to your mind nobody thinked about it yet?
Now all the foreign H-bomb developers will hurry up and download cluster software, fast.
I bet the drain will be closed in a few days.
I'm with the Technical University Munich, and the Leibniz Supercomputing Center next door is getting a new Big Box in March, which will then be the most powerful computer in Europe. The peak transfer rate between its nosed is 10 GIGABytes per second, IIRC. At the moment, thay're still installing the cooling units (the thing will consume about 600 Kilowatts!).
The illegal we do immediately. The unconstitutional takes a little longer.
--Henry Kissinger
THey could slap an export restriction on the technology, but that isn't going to have a huge effect.
Ironically enough though although the US isn't allowed to produce any new weapons they are spending billions on making the ones they have more devestating...
Or they could do what they usually do and invade any small countries and attempt to put illegal puppet governments in place...
Go figure the fairness in that...
Working for the (other) man
They can pass any law they want. But it won't work. Apart from limiting more than, say, exporting 64 processors to a single country per year, it cannot be done. Even limiting the number of purchases allowed per customer (which would make resellers overseas very, very mad) would not stop the government.
If anyone can come up with a way to make this work, please, let me know (and don't let the government know, heh... you know they'd implement it)
(oh geez.. getting bad mental images of laws requiring all exportable US chips to have a proximity sensor in them... )
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
What is a Beowulf cluster?
If Google really cared they would fix Android Chrome to reflow text, instead of discriminating
You can buy a pc anywhere right? You can get the code anywhere right? You can install it anywhere right? You can service it anywhere from anywhere right? What's the problem?
how will it be before such draconian views extend to any powerful computing technology
You mean "powerful computing technology" such as the Playstation 2? If the U.S. govt can restrict it in any way, they probably will.
Not that it is likely to make much of a difference by now. Just as anyone who wants DeCSS can get it, anyone who wants Beowulf would probably be able to get it. There are no border checks on the Internet.
~~~~~~~~~
auntfloyd
Assuming that say Iraq won't be able to buy a pile of Alphas, or K7's if they so wish is utter bullshit. The US may ofcourse choose not to export such computers to those countries, but what is to stop some person from buying the vary same boxes in some other country and shipping them to Iraq then ?
It's not as if all countries have export-regulations equally silly as the US.
Im sure that the government is using Beowulf to do nuclear simulations right now... Who says that other nations cannot do the same?
There was a story on Slashdot a couple of months or so ago, and it said that since India couldn't get hold of an "official" supercomputer to do nuclear weapons -related calculations, they built their own cluster from consumer-grade PCs. (I think it was Beowulf)
I think the logic behind export restrictions is a bit faulty. The fact is, if you can't get something out-of-the-box from the shelf, you have to be creative and go round that obstacle. And often the creativity which you are forced to use gets you solutions that surpass the existing ones.
I wouldn't be surprised if Libya, North Korea, Sudan, Syria or some other nation in this weeks list of USA's Most Hated had come up with for example their own clever cryptography algorithms.
1999.. Alpha 750Mhz 21264 CPU..
2000.. AMD 1000Mhz CPU..
2001.. Intel 1500Mhz CPU..
2002.. Sun 1500Mhz UltraSparc5 CPU..
There's no stopping them. Perhaps we should start rating supercomputers as any computer or cluster that can handle a teraflop? These are the days when your Dreamcast is even considered a supercomputer. Will governement ever learn to keep up with the times?
- EraseMe
I guess you haven't been hanging around Slashdot long enough. This came up and was resolved nearly two years ago.
--
Here is the result of your Slashdot Purity Test.
Linux MAPI Server!
http://www.openone.com/software/MailOne/
(Exchange Migration HOWTO coming soon)
US government controls are becoming looser because of this kind of thing. There is no use in limiting US companies when equivalent technology is sitting on the web. OTOH: The Beowulf cluster is not an optimal architecture for every kind of problem.
sed 's/commun/terror/g' mccarthy > bush; sed 's/terror/saddam/g' bush > bush_wacked
Surely it would be easier to get a non-US supercomputer.
Maybe most fast CPU's are made in countries that are friendly to the US and have similar controls and export rules, but surely these rules would be pointless if there is a single country without these rules that can make fast computers.
Alternatively just do some serious overclocking. Just how fast can you make an only just about legal CPU go?
Name 1 - 1 task - that requires a supercomputer that can't be broken down into nodes well. Cracking crypto? Analysing radio signals? Doing nuclear tests? Running a genetic algorithm or ann extremely advanced neural net (not aware of any that take supercomputer speeds, but hey..).
I, scanning my mind, cannot come up with a single task that cannot be implemented in a way that will lose almost no speed when made as a beowulf.
Can you?
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
That way any non nt cluster will crack any code in the same time as an individual wintel machine.... Of course all this needs to be sponsored....
Personally, I dont see the big deal if we restrict exports of high technology to Russia or China. We should sell out our "edge" (generally speaking) so SUN can make a few bux? Id rather sleep at nite knowing that we arent supplying our enemies with the technology they'd use to oppose us in the Global arena. (And if you think they're friends now, go read a paper) Theres not much we can do except economic blackmail to keep other countres from selling the equipment to them. American companies and the economy are doing well enough that we dont have to sell to our enemies.
I assume the restriction defines 'potentially evil hardware' in terms of processing power, thus allowing the software to be exported without restriction. And since every node is a not-too powerful separate computing entity, the restriction can't be applied to the nodes either.
So what can the government do? I can see three scenarios:
1. No change, export of traditional supercomputers still controlled, beowulfs unrestricted.
2. The ineffective export control lessened since beowulfs circumvent the restriction anyway, and the restriction was kind of stupid in the first place.
3. The export rules get kludged in some ugly way to encompass clusters of computers. More pain, less fun for all involved parties.
Oh, and imagine a MetaBeowulf cluster of those things! (Ah, the comment you all had been waiting for!)
Barcelona, Belgium, Japan, Cambridge Uni (the n hundred year version), Italy and Korea are just some of the places running Beowolf clusters. Its already out there, stop the shipping from the US of PCs and the software and it will be picked up from one of these places outside the US.
:-), Windows and Sunny Delight.
Ma: Where is the horse ?
Pa: She's bolted.
Ma: Well you'd better bolt the door now.
Things the US should stop exporting: McDonalds (eat British, eat Burger King
An Eye for an Eye will make the whole world blind - Gandhi
Oh-my-gawd even the Germans have one.
threadeds blog
We're talking about processing units that are orders of magnitude beyond what a typical workstation can do, not processing units that are several percent beyond what a typical workstation can do.
-- Erich
Slashdot reader since 1997
It's the kind of machine with negative latency.
Before you hit "Enter" the answer is already on the screen.
[]'s Carlos Cardoso - Becoming a brazilian ProBlogger, typo by typo
All the U.S. Government is trying to do is put on a big front and show...which allows them to crack down arbitrarily and forcefully on any entity (business or individual) who they see as a threat to their interests. The government sells more dangerous toys to foreign governments than ANYBODY. They're more interested in running the show than actually protecting world peace, so don't let them fool you.
I used to think they were just damn fools, now I realize they're EVIL damn fools.
What'dya mean there's no BLINK tag!?
Did you even read my posting? I said that supercomputers are also just a collection of nodes. The difference is in the infrastructure.
I, scanning my mind, cannot come up with a single task that cannot be implemented in a way that will lose almost no speed when made as a beowulf.
The you have no knowledge whatsoever of the kind of work being done on real supercomputers. Which is mostly simulations, i.e. solving differential equations. When I talked to the guy at the supercomputing center who showed us around, he said that on average, they managed to use twenty percent of their computers' potential computing power because the problems don't scale well to many nodes. This would be considerably lower on a Beowulf due to its slower network and no real compiler support.
There are alos tasks (again simulations) that cannot be parallelized at all.
The illegal we do immediately. The unconstitutional takes a little longer.
--Henry Kissinger
well, you named a big one: simulating nuclear tests. these and weather simulations really do need supercomputers. they involve millions (billions?) of particles interacting with each other. this requires the massive memory and interprocessor bandwidth that only supercomputers have. sorry, but no beowulf cluster can even come close.
"onward!" cried the copper man, little knowing brass corrupts...
OK, we all know that the US government owns the world, and that what it says goes, right?
But, how exactly would it prevent Beowulf ending up in the hands of 'unsavoury' regimes?
When, for example, AMD is manufacturing Athlons in Germany, and the code for Beowulf must be mirrored all over the world already, what does the US govt expect to be able to do?
If they wanted to resrict large quantities of CPU's making it to these regimes, it would have to ban US chip manufacturers from building fabs abroad (not terribly feasible, legally). Even if they managed that, there would be nothing to stop foreign firms manufacturing chips.
Then what would they do about the mirrored versions of the code? Shut down every Linux related FTP site in the world 'just-in-case'?
This smells far too much like paranoia, and fuss over nothing, it ain't gonna happen, so why worry about it?
--
Listening for the sound of the coming rain...
Yes, and the easter bunny visits my house and leaves golden eggs on my porch.
Try the following: ""The United States government has enacted legislation that attempts to tightly control the export of "supercomputers" to certain other nations (i.e., China, Pakistan, India, etc.)". Even then you mislead people, simply because of the word "export". The vast majority of the required parts are not made in the US. (Is there a single necessary part where all possible components that could be used are manufactured in the U.S.?)
To keep a product like that in the hands of the U.S. only would require the creating corporation agreeing to do the following.
- Keeping all manufacturing in the U.S. at U.S. wages.
- Refusing to patent the technology.
- Keeping a very expensive security lid on the entire facility.
- Not releasing any details that would allow anyone with the resources of China to come up with an equivilent technology
Yeah. Right.In a way, it seems silly to refuse to sell certain nations supercomputers when we still hire their citizens to work on our supercomputers...
-----
No Zen is good zen
However, most nuclear tests these days seem to be for shows of strength (France and the India/Pakistan tests spring to mind), so it is actually more dangerous, in my view, to develop and test nuclear technology using supercomputers, than to develop and test them in "the open", since open testing is a good deterent to other countries.
Perhaps there should be a clause in the GPL, that GPL'd software can't be used to bring about armageddon. OK, that won't work since: a) it violates the Open Source Definition, and b) Emacs would have to be removed from all sites;) - but at least require any nuclear technology developed under Linux be released GPL, maybe have nuke.soureforge.net. This would actually be cool, perhaps VA Linux could fund tests of the open-source nukes on some random place (off the top of my head - Redmond?), if an angry penguin running at you at 100mph is scary, what'll an angry penguin with a nuclear warhead be like?
Sorry about the incoherence of the above post, it's been a long day (and it's only half-way through as well)
--
hi all, i don't think that it should be restricted. the change in the crypto law's long overdue. too bad they didn't realise it until recently. i'm not in the US and it's nice to seee htat i can browse the web with a 128 bit enabled browser now. sure, you can create powerful stuff with clustering. berwulf is so cool!! but let's face it, the cold war's over man. stupid crypto laws just make everyone feel crappy ...
10 GBytes/s end-to-end between two processing units is quite unlikely, given high-end processors typically employed in supercomputers (like UltraSparc, Alpha,
The bisection bandwidth might be 10 GByte/s, though. And _that_ is hardly suprising - you can get Ethernet switches with 30Gbit/s backbone bandwidth for less then $20k these days
The main difference between GBit Ethernet and tightly coupled network interfaces is the latency, i.e. the time it takes to send a message accross. Fractions of a microsecond for supercomputers, tens of microseconds for Ethernet.
</soapbox>
You'll probably find the story in the Slashdot archives. People were mirroring the Red Hat CD and the Beowulf archives on every part of the globe, within an hour of the story breaking on this site. (I'm not joking! If there's any "wild exageration" it is more likely that of one of an hour being far longer than it actually took.)
About two, maybe three, weeks later, the Beowulf site was back up and running. Almost certainly monitored, though. This was definitely munitions, according to someone with the clout to push a NASA site around.
IIRC, though, Beowulf is really not much more than some finer tuning for the network drivers, PVM, MPI, and some freebie cluster management software. Most of the tuning was for the 2.0.x kernels and has since been incorporated into the main tree. PVM and MPI are freely downloadable, and there are later versions than on the Beowulf site. There are also lots of cluster management packages around, now, as well. Beowulf, IMHO, has ceased to be the specific patches/bundle released by AMES, and has become any collection of boxes, configured to act as a single, multi-node, supercomputer.
And, yes, export of supercomputers is VERY restricted. Apple can't export any G3-based computers (though whether anyone in the rest of the world is upset by this is anyone's guess), and it's unlikely that newer-generation processors from other companies will qualify for export, either.
(Personally, I suspect an overclocked, supercooled SMP K7 board would exceed the limits by quite a substantial margin.)
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
First of all, learn to turn bold off when posting in html once you're done with the boldfaced segment ;)
Secondly, is the server only solving 1 differential equation? If so, what is this equation, "the universe works like.. ? If there are 10,000 equations being solved, they can be panned out to 10,000 nodes ("computers" if you're going to complain about my arbitrary use of the term "node").
Third, there is nothing about a differential equation that cannot be paralellized. Even if each equation was dependant on the previous one, with no branching (highly doubtful) the algorithm to solve differential equations itself can be broken down. Its been a while since I took differential equations, but I don't recall an incredible need for a completely linear approach to solve them.
Anyone know more about differential equations to back or refute this case?
- Rei
P.S. : "no real compiler support" - what are you talking about?
P.P.S. : Is your "big box" costing more than 20% more than an equivalent beowulf? I'd be willing to bet it costs more than 10 times more. Thus, your 20% number (which seems kind of odd to me in the first place, I suspect poor code that wasn't designed to be distributed in the first place) falls apart.
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
We've already open-sourced all the nuclear bomb making info. Hazel O'Leary released that right off the bat. To make a sixties type weapon, an abacus has all the needed power.
The research for making biological warfare materiels is now out in the open. We sell glass lined stainless steel to whoever wants it.
We've allowed anyone to purchase the best Sun and SGI boxes, no questions asked.
Let the Clinton Admin get upset about clustering tech, it won't matter. The TurboLinux stuff comes from overseas anyway.
Yeah, you're right, nuclear tests can't be done on beowulfs... wait a minute! Oh no, all of our government's nuclear simulations that they are currently conducting on beowulfs are impossible! Ahh, run for your lives ;) hehehehee
:) Particle simulations are a great thing to distribute. You can give each node a "region" to process, with some common data accessable over the network. Each one processes their region, loading it into memory requesting data outside its region whenever it is nessisary for its calculations. Once its calculations are done, the common data region is re-submitted to the common data. I know this is a vast oversimplification, but this is how I would design a distributed particle system.
Seriously
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Let's go through this real quick:
That's all there is to it, as far as I know. I should add that many "Freedonias", during the cold war, used the exact same procedures to illegally acquire hardware they were not allowed to buy... There are even tales of the (old) USSR acquiring Cray machines, when these were the "crown jewels" of US computing. Commodity hardware has just made this 100 times more simple...
The right to offend is far more important than the right not to be offended. (Rowan Atkinson)
Apple can't export any G3-based computers (though whether anyone in the rest of the world is upset by this is anyone's guess)
:)
Gee whiz, in that case the iMac that has sat in my desk since October 1998 is just a figment of my imagination, right? I've been dreaming about it all along, eh?
Apple is forbidden to directly export one specific model: the G4/500MHz, which exceeds 1 GFlops and is therefore subject to "supercomputer" regulation. But iMacs, iBooks, "big" G3s and more recently "big" G4s can be found all around the world, including here in Brazil. (Okay, so they're all priced like supercomputers... but that's not the issue
To the editors: your English is as bad as your Perl. Please go back to grade school.
Thats the beauty of Linux and Friends: :)
It is open (like open in can of worms
Prohibiting Beowulf export would be
like giving orders that the wind has to quit
blowing around.
You could do it but things wouldn't change too
much. That's another reason why I love Open
Sources and the people behind this effort.
Hint: The Electronic Frontier Foundation is engaged in
fighting to defend your personal rights
and your freedom on the Net. If you feel
that what they do is in your interest, then isn`t
it time for you too to support them?
Put your money where your mouth is (and interests are)
and join the The Electronic Frontier Foundation.
It costs only 35 bucks/year (students even
cheaper, 10 $ I think).
I did it and I'm a proud EFF member now. When they
sent me my membership certificate, I was
ashamed to find out that there are less then 9000 members
so far. Shouldn't there be hundreds of
thousends of members instead?
Take your girl/boy friend one time per year and
stay at home (show her/him your new Linux box)
instead going to the Sushi parlor. You spare
the bucks for the EFF and you'll have a lot of fun.
You can be the first of those new members. Don't delay.
Browse their web site NOW
No, I should learn to use that preview feature.
Secondly, is the server only solving 1 differential equation? If so, what is this equation, "the universe works like.. ? If there are 10,000 equations being solved, they can be panned out to 10,000 nodes ("computers" if you're going to complain about my arbitrary use of the term "node"). Third, there is nothing about a differential equation that cannot be paralellized.
To be honest, I myself know very little about differential equations. It's definitely not one equation, but interdependent systems of equations. Anyway, someone whos writing his master thesis on the stuff told me that hes doing simulations (of some sort of circuity) that can't be parallelized.
P.S. : "no real compiler support" - what are you talking about?
Ideally, you have a compiler that takes care of using all the nodes and distributing the code. If you have to hand-code all that, it just takes too long and is error-prone (debugging distributed code is a really/i> ugly task). Something like High Performance Fortran.
P.P.S. : Is your "big box" costing more than 20% more than an equivalent beowulf? I'd be willing to bet it costs more than 10 times more. The point is that there is no "equivalent" Beowulf! It's designed to solve problems that a cluster of workstations simply isn't fit for.
Thus, your 20% number (which seems kind of odd to me in the first place, I suspect poor code that wasn't designed to be distributed in the first place)
No, it's code that simply cannot parallelized with 100% efficiency.
And your question about the cost seem like you didn't understand what I wanted to say. These supercomputers spend 80% of their CPU cycles doing nothing because they work on problems which can't be parallelized perfectly. With a Beowulf cluster, the percentage would be higher, and it would keep increasing with the size of the cluster, so that it simply is not possible to build a Beowulf cluster that would solve the same problem faster.
The illegal we do immediately. The unconstitutional takes a little longer.
--Henry Kissinger
Where exactly are these nuclear simulations being run on Beowulfs? We aren't doing it in Los Alamos' X Division and I don't know anyone at Livermore's A or B Divisions doing it...could it be that you don't know what you're talking about?
Jim, speaking for himself.
Learn to spell: nickel, missile, lose, solely, amendment, speech, kernel, probably, ridiculous, deity, hierarchy, versus
There is a mailing list full of people who know what they're talking about with regard to this topic. Subscribe with info from www.beowulf.org for these sorts of questions. Don't trust these comments because they're mostly from clueless slashdot users who misuse the Beowulf name and have no idea about any of this. Hell, somebody is posting links to the extreme linux CD... do NOT buy the Extreme Linux CD if you are trying to get a real cluster together - it is an outdated POS
While it might be true that the supercomputers efficiency to deal with applications specifically written cannot be argued about, it is also true on teh same count that the excellent refurbishing of the old machines into high performance Beowulf clusters has meant that the power of having superior and faster processor power has gone from the hands of the few who could afford it to teh hands of thousands who need this power and afford it as well..
..
Dont get me wrong here. its nothe average home user who would like to go and build a 200 processor beowulf cluster.. but more the universities and institutions who have been wronged by the US government from buying these so-called munitions for legitimate computing purposes..
from a technical standpoint, the argument that beowulf clusters simply cannot stand up to the computing power of supercomputers can be accepted to an extent and thats the way it will be for sometime..
as mentioned elsewhere.. its true that languages like c/c++ are not the best for parallel computing but more high perf fortran because of its native supportin the form of parallel lbs for faster computations.. so there are other considerations for evaluating the perf of supercomputers v beowulf cluster..
my 2 cents
- ramas opines !!
Guys guys guys, Do you really think that if there would be export restrictions on Beowulf-like systems' source code that would stop (blacklisted countries) from obtaining such source? and besides, even if they don't have it already (which they do) why can't they write their own? after all, they've got the skills the power the money and will do to do, nothing will stop them, not even a funny thing such as export restrictions on source code. Beowulf-like systems are not something new, nowdays, many people know of such because of the Internet and mostly Linux, such systems have existed and had been running for ages, all over the world. This discussion is rather pointless.
No Task Cannot Be Distributed.
Here's the basic structure of an algorithm that builds on its previous results
while (TRUE)
{
a=Func(a);
}
This cannot be broken down. However, unless Func is also structured like this, it can be broken down. Now, what could you accomplish if func is structured like this? Nothing, it would have to be calling subfunctions that actually do something, as demonstrated below.
while (TRUE)
{
a=Func(a);
}
void *Func(void *a)
{
long i;
for (i=0; iloop_size; i++)
{
a=Func2(a);
}
return a;
}
etc. You can do as many layers of this as you'd like, but eventually you have to get to a function that does something.
void *Func2(void *a)
{
long i;
for (i=0; i100; i++)
((char *)a)[i]=((char *)a)[i]+1;
return a;
}
This last example can be broken down into
void *Func2(void *a, int thread)
{
int i;
for (i=thread*5; ithread*5+20; i++)
{
((char *)a)[i]=((char *)a)[i]+1;
}
return a;
}
(this example uses 5 threads, accessing a common memory segment).
As I was saying, any task (please correct me if I've made an error in my thinking here) can be broken down into multiple threads. The efficiency of these threads, now, comes into question, but with the price of supercomputers, a 100fold loss in speed in a beowulf is often justified. And you'll only get a 100fold loss of speed on something like, perhaps, calculating a bunch of random numbers (seed builds on the previous one) - where the innermost function has an extremely low latency. Not a very common thing in real-world calculations.
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
You seem to have this misguided preconception that beowulfs have exponential speed loss. This is horribly untrue. Lets say you have a system like seti@home distributed. You're sending data once every *day* on a certain box across the network. Even with 86,400 nodes, you're down to a batch request/submission once a second.
Once a second!!!!!!
Learn to think clearly. beowulfs do *NOT* lose speed exponentially. Period. End of case. Do you understand?
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Motorola has been getting around export controls by shipping at least 1 Sun E10000 to China in pieces which is classified as a supercomputer. I heard this through the grape_vine from someone that works at Motorola.
While the Beowulf patches come out of NASA, there's a whole bunch of stuff out there which isn't written in the US at all. For example, the best session clustering technology for Linux is MOSIX which is put out by Hebrew University in Isreal. To my knowledge this isn't export restricted at all, and is released as a set of patches against the main kernel tree. Anyone with basic System Administration skills could set up a Mosix cluster pretty quickly.
e ms.html">Yahoo Batch Queuing Page" for a short list of many popular packages.
If you're less interested in interactive clustering and need computational load balancing instead, there's a whole slew of batch queuing packages available from GNU QUEUE to the many derivatives of NQS out there. Here's the a href="http://www.cmpharm.ucsf.edu/~srp/batch/syst
I don't think the US government could stop any nation from purchasing commodity hardware manufactured from around the world, installing a basic Linux or BSD distribution, and setting up a batch queue or other type of basic cluster. Never mind that a sufficiently serious government could just up and write their own... in my department at BBN (Speech and Natural Language Processing) we use an internally written batch manager which is surprisingly simple... all written in C.
AVALON
Oh, of course, I know nothing about what I'm talking about. Beowulfs are never used for particle system simulations. Especially at Los Alamos (read - SARCASM). Apparently you don't know what you're talking about. Go to hotbot.com, search for beowulf and particle. The second site on the list has hundreds of beowulfs listed, of which I'd bet half of them are used for physics research using particle systems of various kinds.
Please, before you post uneducated drivel and attack me, please pay attention.
- Rei
P.S - Have you ever worked on distributed code before? Hmm... guess who, in this thread, has...
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
All the restrictions in the world cannot alter the intent of another nation. If you treat someone (or a nation) with suspicion, interpret their every move as hostile, and generally bully their citizens, is it surprising that negative attitudes form? Now that the Cold War is over, perhaps a more enlightened foreign policy could be forged based on a more consistent set of principles?
In my mind, the export of "munitions" like Beowulf pales in comparison with past doctrine now being slowly exposed such as military training given to the Indonesian special forces which rebounded badly in the Timor Separation. Certain Latin American countries have no particular appreciation of the US "aid" that they received in the past either (Panama, Niguargua, Columbio, Haitii, etc).
The steadiest water stream can erode the strongest rock. A consistent message of rule by law, respect for human and property rights, and civil society will do more in the long-term in altering societial values than bombing the living daylights out of people whenever they step over a dimly perceived line. By watching TV, the Chinese have gained respect for western police reading people's rights when arrested (not a common occurance for a society slowly emerging from fuedal warlord times). By consistently demonstrating the virtues of a open society, with the free exchange of ideas, even when that could put us in a perceived position of vulnerability (with a decent armored cluebat hidden out of sight just in case), moral authority can be maintained. Even though many people do not share RMS views, they do respect his passion for sticking to his principles. Leadership, especially in the global setting, should be more setting an example, not trying to blugeon or bully people into following your lead blindly. When a giant, walk softly and bend down to listen sounds like a good analogy to get along with normals.
The Beowulf example is like trying to stick a finger in a dam when the whole ediface is changing, about as useless as patenting the click when everyone is moving on beyond the mouse. Similar technology exists in Isreal and could be duplicated given enough time. Given the basics of enough food (a recent Nobel winner proved that most starvation resulted from bad distribution systems, rather than absolute lack of food) and some decent shelter, the average citizen from other countries are much more interested in sitting down and knocking back a few beers than in the posturing antics of self-opinioned leaders on a media crusade. And ultimately it is the average citizen that benefits from openess when they can vote with their feet.
If they can afford to build a Beowulf then ship them the CDs and invite them to join the GNU revolution.
LL
end to all this surprise? Every story like this on /. is always, "Whoa, look. So and so is providing linux drivers." At what point are we going to stop being suprised and expect linux drivers in the same way we expect Windows drivers? Just a question ...
It will kick Beowulf's ass. Those guys may as well give up and go home right now. You know why ?
Because WOLFPACK is a MICROSOFT TECHNOLOGY. - Game over Beowulf guys....
Erm, that is: Avalon (I misread an 'l' as a '1')
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
One thing to distinguish the Playstation 2 and a beowulf cluster is that the playstation 2 is hardware and beowulf is, more or less, an idea. The analogy that I've read in earlier posts that seems right to me is to compare restriction of beowulf clusters to encryption. The way I see it:
Avalon (You can tell I don't do web work, heh... forgot the http)
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
This is not the case with other problems. With those, you need high-bandwidth, low-latency communication between the nodes, and that is something you simply don't get out of Ethernet, which, actually does have exponential speed losses when the network comes close to saturation.
The illegal we do immediately. The unconstitutional takes a little longer.
--Henry Kissinger
Between a computer and other devices like a SonyPlaystation 2, Which if I read the specs in the trade pubs correctly has roughly the same floating point performance of an SGI Iris Indigo. But I can't imagine the govt attempting to restrict a Japanese company's ability to export.
That's right. I worked on an university project that dealt with a N-body simulation. We had implemented the solution using the C library MPI, which does message passing around the nodes. The task was to reduce the passed messages. The same code ran on a 26 node Cray supercomputer and on my 2 node home (not beowulf) linux cluster. That was real scaling code ;-)
"Is it friday yet?"
If you look at the latest list of the world's fastest supercomputers, you'll notice that govt. labs have most of them. And those are just the one that are declassified. I don't think that U.S. weapons labs buy cheap Beowulf clusters when they have tax dollars to spend.
I do research in astronomy and astrophysics, and Beowulf clusters are common throughout my field. Many international collaborations happen on the same cluster, so it's too late for export restrictions. And are we supposed to take all those Beowulf HOWTOs off the web?
Let's put export restrictions on our politicians -- no more expensive trips to Africa, China, and wherever else their daughters want to go.
You saw (I hope) my post above where I broke down the steps in converting a linear process into a (basic) distributed one.
Please present a realistic code sample that will accomplish something useful and yet not scale well over a network. Be forewarned that, as a general rule, the more complex the task (AKA things that apply to the real world) the better it breaks down into a distributed environment, as a general rule.
Theoretical, pointless mathmatical calculations (*dons asbestos suit to protect self from math majors*) may be simple enough and few enough in number in the inner loop to prevent a beowulf from getting that 100x better performance ratio it needs to beat out a supercomputer... but a real world, useful task? I honestly doubt it.
Once again, I request a code sample that shows something useful being accomplished that can't be broken down.
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
I was going to look you up on the net, yet your bio shows almost no info. In fact, the only thing I found useful in your bio was your web page... which doesn't work (broken link). I'd fix that :)
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
should there be export controls on my bowls so that grits cannot be so easily imported to my pants? good lord i should hope not. thank you.
I bet we could make a Beowulf cluster out of these!
Huh? We're already talking about Beowulf? Dammit.
According to my japanese society teacher, there is only 1 thing made in the US that is recognised as high quality around the world (most things made in the US are seen as rather poor quality, especially in japan). That thing is blue jeans ;)
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
That's very nice, they're accessing read/write a common memory segment. Now, pray tell, how is this accomplished on a Beowulf efficiently?
As it happens, you've conveniently chosen something that's embarrassingly parallel anyway (no dependencies between elements not belonging to the same node, and no sequential component such as sequential I/O). I could put a node on Earth and a node on Mars and get perfect speedup in that situation. Think about something like finite element analysis with nearest neighbor interactions, or FFT, or n-body simulations (in order of increasing difficulty to scale well on most architectures).
And no, not every task can be broken down into multiple threads. As an example, consider decrypting a stream (where you know the key, you're not trying to break it or anything) that was encrypted with output feedback (simple electronic codebook encryption, where there's no dependence on prior state, is pretty easy to break with traditional cryptanalysis). You have to know the entire previous state of the message stream to decrypt the next block. That cannot be parallelized by any technique that I'm familiar with.
Beowulf is nothing more than a bunch of PCs, connected via medium speed (100mbps to 1gbps) networking, running one or more of a couple particular software packages. Both pvm and mpich
have been readily available, to the whole world, for a long time. MOSIX has also been available for a long time (though not on Linux)
In short, you can't restrict Beowulf because there's very little there to restrict. For example, mpich based parallel programs can very easily be recomiled on FreeBSD, and the performance is better. (yes, FreeBSD does have better networking. See http://www.cs.duke.edu/ari/trapeze/ip/ for some real benchmarks.)
Besides, MPI is a documented protocol, so even if implementations were banned, it shouldn't be that hard to re-implement from the protocol descriptions.
ERROR: Null
Clustering far predates Beowulf or Linux; at the University of Toronto, we've been doing clustering work for years, and some of it has been successfully commercialized, e.g. LSF. The techniques are fairly straightforward, and there's no real way to keep any particular country from building a compute cluster. Of course, a cluster is not a supercomputer: as Henry Spencer once put it, you can get a lot more work out of a couple of stout oxen than a hundred chickens.
Many problems do not parallelize well. For instance, to my admittedly limited knowledge no parallel version of the fast Fourier transform algorithm (which serves as the backbone of many spectral and pseudospectral codes) is known which does not require a prohibitive amount of interprocessor communications.
At the risk of being overly pedestrian, let me try tackling your differential equations question: Communications latency issues can crop up even if you have just a single equation to solve. Let's imagine, for the sake of discussion, that you wish to understand the propagation of heat on a metal plate, and you have a differential equation that describes the process. Conceptually, you might imagine solving this problem on a parallel computer by breaking the metal plate into a bunch of smaller regions, and asking each processor to compute heat flow on an individual region, as in the following, where a plate is broken into 9 regions:
OOO
OOO
OOO
You can see that every region borders other regions, and herein lies the difficulty: To compute how heat propagates in any one region, say the top left corner, you have to have information from each of the neighboring regions. (In the case of the top-left corner, it'd be the center-left and top-center domains). In solving differential equations, this information is called the "boundary conditions." Each time step would require sending a considerable amount of information among the processors in order to handle the boundary conditions. To use a real-world analogy, if communication latency is high, then many of the processors will end up waiting for the information they need, much like workers in a bureaucracy that has an inefficient internal mail service. In "real" supercomputers you pay big bucks for fast communications, and problems that are communications-intensive will naturally perform better on these machines than on Beowulf or Appleseed clusters. Alternatively, problems whose algorithms require few messages to be passed among processors (many Monte Carlo algorithms have this feature) may run very efficiently on a Beowulf or Appleseed cluster, where communications latency is high.
Parallel computing seems to be largely an exercise in economics. Any parallel algorithm with a nonzero number of messages to be passed will necessarily run at something less than 100% efficiency. Just how far below 100% depends on the nature of the algorithm and the machine/cluster it is running on.
To add fuel to the inferno.
One of the typical advantages of a "real" super computer is it contains one or more vector processors. Something a typical PC lacks.
Does that mean a vector processor can not be obtained? No. I know a group computational chemist's in the US that is trying to build a cluster out of sony play stations.
Why? It's is not because they don't have super computer time, they do. It is because they have excellent vector processors and are networkable.
The biggest problem they have is not all the code is yet parallelized. A typical run takes 2 to 10 days at NCSA.
So restrict the toys and we will all be safe!
To_lazy_to_set_up_an_account
exerpt from Category 4 - Computers
b. "Digital computers" having a "composite theoretical performance" ("CTP") exceeding 2,000 million theoretical operations per second (Mtops);
c. "Electronic assemblies" specially designed or modified to be capable of enhancing performance by aggregation of "computing elements" ("CEs") so that the "CTP" of the aggregation exceeds the limit in b.;
How the US Government thinks it could ever enforce this with Beowulf is beyond me...
1. Why on Earth would a supercomputer be working on a stream???
Thats a rather silly example. I'm still looking for a realistic example of a situation a supercomputer would be working on (something relevant, not just generating a bunch of random numbers or something) that cannot be easily paralellized.
2. My example was actually a horrible example for paralellization, because the inner loop was about as simple as it could be. My point (as is stressed in later posts) is that any real-world application will have a much more complicated inner loop - and, thus, a slower inner loop - and, thus, work far, far better as a distributed system.
Noone here seems to grasp this simple concept. Its pathetic.
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Chinese Space Agency That is.
t ml
http://www.turbolinux.com/solutions/customers.h
--- Nothing To See Here ---
Wow, someone who knows what they're talking about :) I applaud you for bringing some intellectual discussion into this thread.
As I hope you pay attention to this thread, as you know what you are talking about, would not, the larger the calculations being done, the less the % latency (don't really know how to phrase this - see below)
Lets take your 9-piece metal plate example. Now, picture there being 1 4 particles per piece. Every particle is therefore a border particle, and may need to communicate on every cycle with at least 1 neighbor (100%). Now, lets make them 9 particle plates. The central particles will never communicate with the outside, but the outside ones still may. Thats about 91% of the particles needing to communicate. Now, lets try 10,000 particle (100x100) plates. Now we have 396 particles on each edge, and 9,604 particles on the inside - about 4%.
Now, of course, increasing the number of particles slows down the problem - but it also makes the simulation more accurate. And, what many people here don't seem to grasp, is that increasing the number of particles, as in this case, makes the beowulf system more efficient, compared to a single supercomputer.
If I am misinterperiting any part of this problem, for example of the conductivity of the plates is described by an equation and not discrete points, or something like that, please let me know (I don't know what the math is like on something like that)
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Well, an FFT's inner loop (butterfly) is pretty simple, something like 10 arithmetic ops if I remember. Higher radix helps, and there are other tricks to reduce the number of communication steps (address reordering), but it's still doing a lot of communication.
Also, answer my question about N-body problems.
I agree that the kinds of problems a supercomputing would be working on are usually very parallel. That doesn't mean that they're computationally easy to parallelize, particularly with limited communication bandwidth. If they require access to a shared resource (at least if it's update access), or the communication needs are heavy, it's going to be very hard to parallelize efficiently on a Beowulf-type cluster. That's where you need the massive bandwidth that a Starfire or SP or Connection Machine offers.
(And yes, I have programmed, from the inside, a Connection Machine. Worked for them for over 7 years, in fact, and spent most of that time tuning the FFT and suchlike. Even with a really good ratio of bandwidth to computation power, it still took a lot of work to get good performance even from a lowly FFT or matrix multiplication. And even though complete applications usually do FFT's and matrix multiplications in parallel, rather than one large one across the entire dataset, they usually have even more communication taking place than the core routines do.)
Name 1 - 1 task - that requires a supercomputer that can't be broken down into nodes well
Sure, I can name several. Just some examples: Weather simulation. Ocean simulation. Molecular simulations. Simulation of astronomical bodies. All of which are very real problems.
In short, any problem which is not trivially parallel will get a much poorer speedup on a NOW (network of workstations) versus a real supercomputer. Many of the problems above will generate many MB/s of data per processor (60 - 200 MB/s is not uncommon).
What you fail to realize is that many problems run for many iterations, and for each iteration you need to distribute the global dataset to all worker nodes. Take the Barnes-Hut program, for example. In that program, each node get a set of close-by astral bodies (stars and planets), and calculates their new positions for the next time step. To do that you need the positions of all other stars. For the next time step, you need to a) collect the calculated positions from all worker nodes, and b) distribute them back for the next iteration. When trying to run that on a NOW, you will very soon find that doubling the size of the cluster will not give any speedup at all, since they will spend most of the time chatting with each other on the network. On a supercomputer, you can run many more worker nodes before this happens.
I am not incredibly familiar with FFT's, but isn't their main purpose image enhancing? If so, what is the highest resolution image that people deal with? Perhaps some satelite pictures? I'd suspect that the most intense use, CPU-wise of FFT's is video enhancement. But video is a large collection of single frames - and thus very paralellizable.
However, that is a good example to bring up. A very very large frame FFT may currently be better done with a supercomputer - until Moore's law catches up (I don't know if people will keep finding a use for better and better resolution for some things... certain groups such as NASA might need consistantly increasing resolution)
(btw, if FFT's aren't primarily used for image enhancement, I apologize. my pain point in bringing it back up is that in any complex process, all it takes is one single step that can be paralellized efficiently to make a beowulf worthwhile - and then you gain a huge money/performance ratio.)
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
As I recall, this question circulated on slashdot sometime last year. I don't remember the details, but I do remember that everyone was concerned about whether or not Beowulf would be classified as munitions. It seems to me that this question has already been resolved, hence the great preponderance of beowulf outside the US.
So long, and thanks for all the Phish
I want a beowulf cluster of those beowulf clusters. -Saddam Hussien
> Ideally, you have a compiler that takes care of using all the nodes and distributing the code.
> If you have to hand-code all that, it just takes too long and is error-prone (debugging
> distributed code is a really ugly task). Something like High Performance Fortran.
Are you aware that there are HPF compilers for Linux being used in Beowulf clusters?
Check out:
VastHPF
PGHPF
There are other commercial products, plus some educational type compilers.
- Darren
--
-- Fnord.
I heard an interesting story whilst in my previous job.
;-)
Basically, my company was doing a project based in Russia, but the export restrictions meant the hardware couldn't be shipped at that time. However, it was known that in x years (or whatever), that the level of h/w would be allowed.
In preparation, the manuals and similar material were sent over to the Russians for their analysis.
By the time the hardware was allowed, they were pretty much all experts... powering on the computers, and immediately writing software on them. They had studied the literature thoroughly, even performing simulations with pen and paper.
Nifty.
If they were to ban it (which they won't),
what's to stop non-US people developing something similar?
Humility? Self doubt?
Really!
I'm out of my tree just now but please feel free to leave a banana.
Don't you think it would be worse with Republicanos? Shit they were the ones that fucked every small country in the world by attempting to stop the communist(supplying weapons to everyone, promoting civil wars, etc..)
If you take a look at the hype on www.beowulf.org shutdown, and Important Beowulf notice stories. Now, I know there was great debate over what *really* happened, but one of the possibilities that was a concern was exactly what you are asking about..
-- I'm the root of all that's evil, but you can call me cookie..
This sounds like a DCoERA (distributed circumvention of export restrictions attack). Now it's an attack! So it can fall under anti-terrorist rules! Bye bye geneva conventions and constitutional rights (the local US retailers to foreign nations)! 3... 2... 1... detonate... BOOOOMMM!!! (warehouse crumbles).... This is the ATF, you're all under arrest! Come out with your hands up!
Lets take your 9-piece metal plate example. Now, picture there being 1 4 particles per piece. Every particle is therefore a border particle, and may need to communicate on every cycle with at least 1 neighbor (100%). Now, lets make them 9 particle plates. The central particles will never communicate with the outside, but the outside ones still may. Thats about 91% of the particles needing to communicate. Now, lets try 10,000 particle (100x100) plates. Now we have 396 particles on each edge, and 9,604 particles on the inside - about 4%. Now, of course, increasing the number of particles slows down the problem - but it also makes the simulation more accurate. And, what many people here don't seem to grasp, is that increasing the number of particles, as in this case, makes the beowulf system more efficient, compared to a single supercomputer.
it seems to me, that what you're proposing is essentially taking the piece of sheet metal and breaking it down into 90,000 regions instead of 9. if you don't increase the number of nodes, i don't see what you're accomplishing by doing that (i'm assuming that the equations' accuracy is independent of the computation method -- read: 1 particle and 500 particles will yield the same result, one just might take more time). if you do increase the number of nodes, then you're increasing the number of messages that need to be passed between them, not reducing it. in your example above, where you increase the message traffic (making latency that much more of an issue), how can you argue that a beowulf system is more efficient? cost-wise, it obviously depends on the problem. computationally, i don't think a beowulf system would ever be more efficient (node for node).
of course, if i'm missing something obvious, please point it out.
"onward!" cried the copper man, little knowing brass corrupts...
Now, I'm CERTAINLY no expert on the subject, but I must beg to differ. Weather simulation *CAN* be broken out to run on a distributed machine, which is proven by the fact that several government entities have awarded contracts to build them to just such machines!
I also believe that perhaps you are unfamiliar with a good cubic beowulf setup. Typically, each machine would have 4 Gigbits of bandwidth to transfer data, i.e., 4 Gigbit ethernet cards, no more then 2 hops from any given machine. Using this method, transfering the datasets is fairly trivial. Granted, *THIS METHOD DOESN'T SCALE AS WELL* if you use the same programming techniques as those one would use on a supercomputer scale. However, this can be overcome if you take this into consideration, aka, clusters of 9 cluster machines. Each machine would really only be talking to one of 9 machines, with the cluster controller talking with the other controllers. It's just a different way of looking at the problem.
-- I'm the root of all that's evil, but you can call me cookie..
Yeah, baby, deny the bastards that feeling of a warm goo trickling down your pants.
I spoke to Michael Reagan on the air about this very subject about 8 months ago. Some people (like mike) just don't get it. What Mike was talking about was the Clinton administrations easing of computer export restrictions to countries like China.
The Genie is out of the bottle. Beowulf, actually allows one to build faster computers for LESS money. If you buy a "million dollar" super-computer and you spend a million dollars on nodes for a Beowulf cluster, typically the Beowulf if going to be capable of doing the work faster.
I'm not too worried about China getting nuclear technology through eased export restrictions, I'm worried about well funded terrorist groups getting access to nukes, Bin Laden's boys or that death cult in Japan are far scarier to me than China.
LK
"Hi. This is my friend, Jack Shit, and you don't know him." - Lord Kano
What people keep trying to tell you, and you keep refusing to hear, is that it is not just a question of whether a problem can be "paralellized" to a single step. If each node has to wait for information from other nodes before it can perform its next "paralellized" step, and you have slow communication between nodes (such as Ethernet) then your node is going to spend most of its time synchronizing, and very little of its time doing something useful.
Wow, someone who knows what they're talking about....
:)
I deceive people well.
If I understand correctly, you are describing how a "surface-to-volume" ratio goes up as the volume elements get larger, thus allowing individual processors to spend more time crunching numbers and less time waiting for boundary data. This is indeed true, and this is precisely the kind of balancing act one has to perform to compute efficiently in parallel. As you've demonstrated, the same algorithms may be more efficient on some machines than on others, but based on my (albeit limited) experience in computational physics, optimization almost always seems to boil down to how one reduces the number of messages that have to be passed in order to perform the task. This seems to be the single most important factor in the scalability of numerical calculations (how much speedup is gained by increasing the number of processors).
Disclaimer: While I have some experience in parallel computing, I am by no means an expert in this field, and I suggest you read some of the other excellent posts in this thread to hear from the real experts.
When India was denied crays, it went and developed a parallel processing supercomputer called param, made of ultrasparc 1's. In fact they made some money off this, by selling this to russia and others. Right now there are a couple of companies in india whose whole business model is building beowulfs and selling them to anyone who asks. Controls my ass. It's like chinese emperors trying to keep silk-making a secret. Don't people ever learn?
How would you turn that into a parallel algorithm? You can't simply run n threads in parallel, because now the results of each stage of computation depend on previous results. If you did simply run n-threads, you'd get different results.
This is the basic problem with non-trivial algorithms - the results of a later part of the algorithm depend on results of a earlier part of the algorithm. So you can't run the later part until the earlier part has completed.
This is what people are talking about when they talk about FFTs or n-body simulation. In both those cases, although there may be parts of the algorithm that can be performed in parallel, the overhead of communicating the results to the other nodes may outweigh that, and the actual work of the algorithm involves repeating the same step over and over again, where the next step cannot be started until the previous step has been completed. That's why parallel computers do not always offer the speed benefits that one might think they do.
Will
> Please present a realistic code sample that
h tml) studied this problem because it is a critical component in the computation of Ewald lattice sums for Molecular Dynamics simulations.
a w/Amdahls.html) s p) and then come back here when you have a little more appreciation for the scope and problems associated with high performance computing and beowulf's
> will accomplish something useful and yet not
> scale well over a network.
A 256x256x256 3D FFT. It *can* be parallelized, but on a beowulf with fast ether, this problem will not scale beyond 4-8 processors in general.
As for being "real world", this type of processing is used in many applications. Our research group at Duke (http://www.ee.duke.edu/Research/SciComp/SciComp.
Another example is an algorithm such as the fast multipole method for N-body problems. The algorithm itself is O(N), but because of the tree structure of the algorithm (involving a global sum) the algorithm will *never* scale better than O(log N) on N processors. The research codes that I have written demonstrate a speedup of about 26 on 32 nodes, which is considered very good. The relative speedup drops the more processors you add.
Final example: the "shallow water" portion of the current weather forcasting models. It doesn't scale well at all due to data dependancies.
> Once again, I request a code sample that shows
> something useful being accomplished that can't
> be broken down.
It's not a matter of "can't be broken down". It's a matter of scalability. Take, for example, the 3D FFT mentioned above. On paper, the algorithm is easy to write in a parallel form. However, the overhead of the communications phase of the processing (which grows as O(P)) limits the efficiency of the algorithm. Once you go beyond about 8 processors, it actually takes *more* time to compute the result.
You can run this on the biggest cluster farm you can find and the problem won't go any faster. More advanced network hardware, such a Myrinet, helps, but only so much.
Some reading suggestions:
Do you understand Amdahl's Law and it's implications? (http://www.scl.ameslab.gov/Publications/AmdahlsL
I would also suggest that you go and read the relavent sections of Hennessy and Patterson's "Computer Architecture: A Quantitative Approach". (http://www.mkp.com/books_catalog/1-55860-329-8.a
Be aware that even the hardcore beowulf community realizes the limitations of the cluster-computing model.
> Be forewarned that, as a general rule, the more
> complex the task (AKA things that apply to the
> real world) the better it breaks down into a
> distributed environment, as a general rule.
Be forwarned that, as a general rule, making gross generalizations in the field of high performance computing often leads to very wrong conclusions.
Regards,
Dr. Bill Rankin
wrankin@ee.duke.edu
Now someone is controlling the export of the colors on the /. pages.
An example: (I didn't do this code, but I watched a presentation on it)
Consider a simulation of a space with many particles, which create and are affected by electromagnetic fields. This problem can be easily broken down by breaking the space into N different spaces (like the heat-propagation problem presented above), where N is the number of processors. For each time step, large arrays of field and particle location data must be passed between the processors, in order for them to compute the force and motion values for the next time step. This communication is far from trivial. In fact, it takes up a large majority of the total simulation time!
With a problem like this (and this type of particle problem is very common), a Beowulf cluster will perform very poorly next to, say, a Cray T3E, which has MUCH faster communication time, and has optimizations such as hardware-implemention for certain MPI routines.
Your argument above about increasing the number of particles is misguided. Yes, by adding more particles, the *percentage* of communications might go down in some cases. But the total number/size of the communications is still increasing. If the size of simulations that scientists want to do are limited by bandwidth, then they are going to want to get a machine(s) with better bandwidth, not increase the simulation size to make it run longer!!
The primary advantage of Beowulf clusters is low price (which you've pointed out, even if it is a little skewed). However, to claim that a similar sized Beowulf cluster can keep up with a T3E or IBM SP is not even close to accurate for these kinds of real world computations. The high prices for these machines are being paid for this extra memory and communication bandwidth because it actually makes a huge difference in their simulations.
Dude, you have crossed WAY over the line into "true believer"-hood. You just can't admit that there could be ANY computing task for which Linux isn't the optimal solution. Get a grip.
Sorry to burst your bubble guys, the world does NOT revolve around the USA. Europe is not some small country over the water.
US products are subject to US laws. 128-bit encryption, supercomputers, ICBMs, you name it, are not subject to US laws IF THEY'RE NOT DEVELOPED IN THE USofA!
Beowulf was developed on the net. 99.95% of it is raw Linux, developed by one L.T. and cronies from all over the globe.
This discussion is not entirely redundant, because this issue has to be addressed for US-only OSS projects, but it does not apply to Beowulf. The US does not have juristiction to impose regulations on its "export". Possibly downloading it from a US-based website may come under US law, but not from a local mirror.
Sorry again to bring you down to earth, but America is one country amongst many, whatever your media may tell you.
Steve.
Author, Shell Scripting : Expert Re
I am a bit surprised by the question... Isn't Linux, and Beowulf created by people all over the world. Europe and the US in partocular, but how coul dthe US stop the export of a product which is not a 100% American technology? Is Beowulf 100% American, does anyone know? I thought it was not...
I don't consider N-body particle simulations to be "nuclear simulations." Being at Los Alamos, I consider "nuclear simulations" to be weapons modeling. If that's a difference in terminology, my apologies. I will stand by this statement: no Beowulf clusters are used at Los Alamos for nuclear weapons modeling, nor to the best of my knowledge at Lawrence Livermore.
/. userprefs to reflect the fact that I took that down.
As for whether I have ever worked on distributed code, that'd be a "yes".
As for the broken home page, yeah, I should probably change my
Learn to spell: nickel, missile, lose, solely, amendment, speech, kernel, probably, ridiculous, deity, hierarchy, versus
That's exactly wrong. The point of Amdahl's Law is that all it takes is one sequential step to ruin the ability of an application to scale well. Amdahl was not a proponent of parallel computing; he liked big mainframes, and came up with his "law" to demonstrate that fast single processors were the way to go, not parallelism. I don't agree with his position (about parallel vs. sequential in general), but absent issues such as memory contention it's basically a pretty firm rule.
Also, Amdahl's Law sets a hard upper limit on parallelism. The ultimate speedup constraint imposed by the number of processors and the fraction of sequential work only applies in otherwise perfect conditions -- the communication cost is zero, and there is no inter-processor contention. These can be true in some circumstances (an embarrassingly parallel app on a pure MPP). A Beowulf cluster qualifies as a true MPP. Very few interesting apps truly qualify as embarrassingly parallel. Communication on a Beowulf cluster with anything less than a high quality gigabit switch (or better) is definitely not close to free.
Just because video consists of a stream of images doesn't mean that the images are independent images. I presume that good video (as opposed to photographic) image techniques rely heavily on correlation between frames
*sigh*
Please listen.
Minds work better when open, not only source.
*waits a minute to let that sink in*
*still waiting*
Ok... lets try this again.
I'd like you to think: What have I said, repeatedly, about the inner loops of the majority of calculations?
I've said that the inner loops generally have, or could be made to have, very slow calculations.
Now, if the calculations on a given piece of data take a long time, what does this say about how much the network is taxed?
The more intensive the calculations in the inner loop, the less the network is taxed. Nost real world applications (as demonstrated in my (lower?) message) can be adjusted so as to increase the amount of inner loop calculations in some way or another.
Now, take another look at what I said above, about FFTs of video.
From what it appears, FFT requires an entire image to transform. Ok, so we define this level to be the level at which a single machine runs. Then, we pass out frames to each of the other nodes - each node has a frame. The node can sit there for a week processing that frame. But, if you have 1000 nodes, thats 1000 frames a week. A 100mbs network undoubtably can handle the passing of 1000 frames 2-ways in a week. Now, how does this compare to a mainframe? Well, you'd need a mainframe that ran 1000 times faster than each of these PC nodes. Just using single cpu, 500 mhz intel nodes, you *would* need (in equivalent mhz) 500 ghz in a single machine. A 500 ghz machine is *far* more than 1000 500 mhz intel machines (overclocked celerons, single cpu, just board, chip, power supply, ram, and ethernet perhaps 200-250$ each, 200-250k$ total, compared to many million for a single machine.
Do you follow this?
I don't want to have to explain it again. I just hope you understand what is being said.
Open minds work wonders. Please listen.
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Process A (linear) is done on Process B (linear) is done on Process C (parallel) is done on Process D(linear).
This breaks to:
For each node:
Process A(linear) is done on Process B (linear) is done on a certain part of Process C (paralell) is done on Process D(linear).
Amdahl's law is incorrect.
As I stated, a single paralell task allows the system to be parallelized. From working on threaded genetic algorithms, I know this to be true (only 1 part of the algorithm (all cells can be run at once) is paralell; the majority of it must be done linearly).
Ok, lets say all frames in a video need N neighbor frames. Then we start in chunks of frames. Node 0 has frames 0->N in memory and is working on them. Node 1 has frames N+1->2*N in memory and is working on them. Etc. You stagger the starting points of each node (I.e. node 0 may start on frame 0, node 1 may start on frame N+N/2, etc) so they need data from other batches at different times, staggering network load.
Once again.
I sign.
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Well, what you've done is change it so it is harder to parallelize. You've done what I said earlier, wherein it is now along the lines of calculating a series of random numbers, and throwing out the results.
;) ) it can be paralellized down to basic operations, but as I said, they are small operations, which work poorly as a distributed effort.
:P
;)
Real world calculations don't work this way. Real world calculations work the way my example showed (albeit, with much more complex inner loops).
*sigh* But... since you insist on me paralellizing this (getting sick of typing that word
PLEASE. if you're reading this, no more pointless examples. Give real world examples, like the person who gave the example of a FFT. Anyone can have a computer sit and chuck out worthless data that doesn't paralellize well
Each node has a starting, blank copy of a[] on it. Each node is running in a for loop, using a mutex to keep them in sync (I don't know how mutexes work over a distributed system... I'd assume they work the same as in a threaded system). Node 0 calculates a[i-1]+a[i+1]+3. Node 1 calculates ((a[i-1]+1)**2)%100. By this time, Node 0 is done with its calculations, and node 1 can just read in the data to store, unlocking node 0's mutex, and reaching a new mutex when it is done setting the data. Node 0 then reads in node 1's address and stores the data, and unlocks node1's mutex, and they both continue again. You'd probbly only gain, with this particular example, if you had smp connection speeds, or at least gigabit. Well... actually, best speed increase would be done with 2 very old systems, as the math calculations would cost more... and a couple of cheap 100 mbs ethernet cards with a direct connection. If you had 2 386's working at this, there could be a speed increase (save the slow node, node 1, 5 add/subtracts and 2 memory ref's, in exchange for 2 packet sends on node 1's part.. )
Another thing you could do is give this to a math major for a bit to look at and rewrite a bit for you so its more easily paralellizable. Trying to do that makes my head spin, but some people like that sort of stuff
Once again, this is a jury-rigged example. The real world doesn't work like this. Also, we're looking at just 1 step. In all likelyhood, there is a much better step to paralellize than this.
I conclude with: pointless examples return pointless results, but yes, anything that is more than 1 operation can be paralellized (not nessisarily at a better cost than sending the data around, however, if it is a jury-rigged problem)
- Rei (getting tired)
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Actually, there are border checks on the Internet. Take a look at the PRC and its efforts at countrywide censorship. Just like physical world border posts/checks, their system isn't 100% reliable but the people that they catch/make an example of are quite effective so far. It's a completely open question of whether this model is going to work over the medium term (3-5 years) but right now, it's doing its job, keeping the communist party in power in the PRC. B-(
DB
I'm not going to rewrite it. ;)
Read the note below. He did a good job of summarizing it for me.
My fingers are getting sore.
Good thing my boss doesn't mind me slacking
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
I never commented on linux. This discussion is about beowulfs, and their efficiency for massive computing tasks.
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Of course, I know you'll do neither. :P
If you don't believe that Beowulf's are supercomputers, please do the following test:
1. Come to the United States, and live here permanently.
2. Build, say, an 8-node Beowulf, using, say, some 750+ MHz K7's or Pentiums. Get everything working, including all the configurations, switches, etc.
3. Now take your non-supercomputer, and ship it to either Iraq, Libya, or China.
4. Post your results here, and send a copy to the BXA.
5. Let us know what happens.
Of course, not one single person of the old farts school of supercomputing will do this. Not a single one.
Instead, they'll all sit back in their rocking chairs, and complain about how all these killer micros aren't real supercomputers.
Go ahead - prove me wrong. I dare ya! ROFL.
Have you noticed a pattern? Everyone who joins this discussion patiently tries to explain to you the problem with your argument. You accuse them of not being open-minded.
Not a single person has backed up your ridiculous argument that every problem can be set up in such a way that a single node could spend hours or days crunching without having to look at a shared resource, or the result of another nod's computations. (Does that tell you something? Like, maybe you are wrong?) (No one is saying that problems like that don't exist by the way, they are just saying that all problems are not of that form.)
You asked for a single example of a problem that was not embarrassingly parallel (which is what your examples have been). You were given weather modeling, nuclear modeling, and a score of other examples that I'm not going to bother looking up.
*As an aside, my particular favorite was the example about the heated metal surface divided into nine areas. Do you remember? It was the one where you suggested subdividing the areas, to "create parallelism", when in fact you would actually be making the communication between node problem exponentially worse, since each of the new nodes would need to communicate with its nearest neighbor. *
Don't you see the pattern? People who do this for a living are posting and telling you time after time that the communication time between nodes would leave your CPUs idling for 90+% of the time in problems with interrelated data. And most problems being run on super computers have interrelated data... that's why they are being run on super computers, not clusters.
Do you really think that you are so much smatter and more open minded than the rest of the world that you are the only one who would have noticed if super computers were obsolete?
I don't know why I am posting again, as I said, people who do this for a living have tried without success to explain this to you. I am just a student who happens to be studying this, this semester. I am sure you won't listen to me; I must be closed minded and stupid. Please proceed to write a reply with as many *sigh*s in it as you see fit.
Big deal.
I hate to tell you, but the number of people who go buy off-the-shelf stuff and don't do their own QA tests is mindboggling! Most commercial PC's shave corners on the components. Cheap RAM is one common area.
Give me an OC'd system with top notch components over a non-OC'd system with cheap components anyday.
Heh - even the best of the super's can screw up at the bit-level. You DO have error-checking built into your algorythms, don't you?
Heh. I didn't think so. This is one area where most researchers fall down on. Given that they are living off taxpayer dollars, perhaps they should be fired as well?
That's great! Maybe next you can work on a program that can determine if all other programs halt. Having seen you work today, I'm sure it won't take more than an hour or two. You have stopped making my head hurt, and have started to make me laugh.
I am not qualified to comment on the details of the algorithms you mentioned, as there were no details given that explain them, nor could I find an explanation on your still-under-construction site. I will have to trust you that there is no way to distribute them efficiently, for now.
Odd that you would send me that link about Amdahl's Law. Seing as your point was that Amdahl's law is correct and that link says that it is incorrect. As the link states, it assumes that there is no corrolation between the number of processors and the amount of work done by each processor, which is patently silly. As was mentioned in a previous post, Amdahl was a major mainframe enthusiast, and seems to have had a biased viewpoint, as well as not conducted tests himself like the people at the link you sent did.
Also, not to seem ungrateful for the reference, but to order a book for the sake of a debate which would be over long before this page is long gone except in distant slashdot histories is kind of pointless, except to help me learn more about the subject, which I can (and have) from many spots on the net.
I do understand a good bit about distributed computing. I do not understand the details of your specific algorithms you mention, or their implications, or the other ways to calculate them, etc, so i will have to trust your groups work.
Good luck to you and your group, Dr. Rankin.
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Mot is an AMERICAN company you yella fuckhead.
Beowulf's can be restricted. And the last time I checked, they still were.
Unless you've put together a fully configured and operational Beowulf, and shipped it to a restricted country, without any flak from the Fed's, you can't say that they can't be restricted.
I do know what you mean, but I also note that even supplying the parts for a supercomputer can land you in jail (and in fact I believe this has already happened to some people).
So does the previous problem: "modeling of a universe" scale or do you have to break the problem up into 10 smaller universes if you had 10 controllers?
The difference between this and the heat distribution problem is that all particles act on each other. Thus, it is a totally different problem and we structure it different.
.80 cents/meg (haven't checked pricewatch in a while - is that reasonable?) thats 38,550 / nodes particles per dollar. We'll assume that a Xs mhz supercomputer with no ram for Ps$ has a speed of N Xi mhz systems for Pi$ each. We'll also assume the ram in the supercomputer is equal cost as the PC ram (doubtful). We'll put a total cap on the amount of money at Ps$+Pram$*Particles/38550, where Pram is the price of ram. Which gives the better performance?
8 550-N*Pi$=0; / Particles $ /Particles)=N
.8 $/meg. Supercomputer at 10 million$, 100ghz. 100 million particles.
If you modify the cluster for this problem so that you have enough ram in each node to store the entire problem being worked on, then network traffic only needs to be updated at the end of each calculation. I'd need to know the number of particles and how much ram each takes up to know whether or not this would be feasable. If we assume each uses a double precision floating point number (8 bytes? its been a long time..) for its x, y and z coordinates, and another for its velocity, and an short for what type of particle it is (there's probably more things that are stored, but we're doing a generalized particle system and I don't know any specific details), thats 34 bytes per particle. We'll assume we've got some semi-comptent programmers who use structs and not objects for the particles so we have the otpion to guarantee that there is no extra overhead apart from the pointers. Given ram costs of
We then get a system of equations:
Supercomputer=Xs
Beowulf=N*Xi
(Ps$+Pram$*Particles/38550)-Pram$*Particles*N/3
Ps$-N*Pi$=(N-1)*Pram$*Particles/38550
(Ps$-N*Pi$)*38550/Pram$/Particles+1=N
Ps$*38550/Pram$/Particles+1=N+N*Pi$*38550/Pram$
(Ps$*38550/Pram$/Particles+1)/(1+Pi$*38550/Pram
Now, what does this mean?
Well, it is an equation that needs to be optimized, given several discrete values of Pi$ and its associated Xi. Lets try out some sample data.
Assuming: 500$ nodes at 1000 mhz each (smp). ram at
The optimal beowulf came out at 5Thz. - a 50x performance increase.
(I may have made math errors - correct any errors you find) (I'm not as perfect as I sound sometimes *grin*).
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
The problem is that each particle's position needs to be sent to all the other nodes for them to do their calculations. So taking your assumption that each particle takes 34 bytes and assuming the simulation has a million particles in it, you need to send at least 34 MB of data through the network after each calculation. So assuming the calculation takes a while, say 10,000 clock cycles (on a 500Mhz machine) then you need to do 50,000 updates a second. This comes out to about 1,700,000 MB/s of bandwidth. Even if the calculation takes 1,000,000 clocks, you still need at least 17GB/s bandwidth. A beowulf cluster may have a 1 Gb/s bandwidth over gigabit ether but that leaves you short by a factor of 136.
Using a beowulf for the example above means you can only do 30 calculations per second even though you could theoretically do 500 to 50,000 depending on the amount of clocks the calculation takes.
Now suppose you had a supercomputer that had a bandwidth of 10GB/s (gigabyte/s). Then you could do about 300 calculations per second even if your processors were running at 300MHZ instead of 500MHz. In cases like this, the I/O bandwidth determines how fast the simulation will go and a beowulf cluster would not be better.
"When you sit with a nice girl for two hours, it seems like two minutes. When you sit on a hot stove for two minutes, it
I don't think you understand that for a lot of the algorithms that break things up into cells, the accuracy comes from the size of the cell NOT the number of particles in the cell. In other words, having 90,000 particles inside the cell is the same as having 1. It simply doesn't make a difference.
"When you sit with a nice girl for two hours, it seems like two minutes. When you sit on a hot stove for two minutes, it
Sun has shipped over 500 workstations to China that have disappeared into their defense industry complex to develope better nukes and such. Why did Clinton do this, can you say Johnny Haong. I just read this in a book called Red Dragon Rising. China is on the move to at least reclaim Taiwan after a civil war that ended 50 years ago. And the Clinton Administration refuses to acknowledge Taiwan's sovereignity, however Congress has passed resolutions that does. A little off topic but thought some might be interested.
If voting were effective, it would be illegal by now.
There is nothing a rogue state can do if they don't have suitable PEOPLE to setup and maintain supercomputers. And of course more people are needed to do the programming (a computer can't give you the answer if you don't know how to ASK the question), study the results, etc.
Attempts to restrict software of any kind are misguided and a waste of time/money. At the very least a rogue state can send someone over to US then 1)download the necessary programs, 2) upload the files back to their own ftp or burns some CDs and send them back via snail mail or whatever.
If you want my respect, give it first...
If you don't want my respect, expect mine before you give it.
...at least in New York City.
Aaargh, I hate people with deaf eyes, I really do.
1) Not everyone has disagreed with me.
2) I never once claimed that every problem can be broken down to a embarassingly paralell situation, so please quit putting words into my mouth. My original argument, and the one I;m sticking with, is that every program can be paralellized; whether or not its more efficient is questionable, but on real world phenomina, it generally is more efficient.
3) Ah, how ironic. You picked the examples which *do* break down easily. (did you skip over the posts by *other people* which mentioned beowulf clusters being built for weather prediction and particle simulation?). You didn't mention the ones wherein the real problem lies, the ones presented by the dr. in an earlier post (sorry, I don't recall your name), which are things such as FFTs. Which I do not have enough knowledge in the subject to discuss. I do, however, have enough knowledge in the subject of basic particle simulations wherin particles interact with each other to discuss paralellism, so please open your ears to my, and other people's posts.
4. Once agiain, your sticking words in my mouth is getting incredibly annoying. Please stop it, Now. I never claimed that mainframes are obsolete, I never claimed that people who do this for a living don't know what they're talking about. I'm trying to get a simple point across that most physical simulations can be broken down into smaller parts - at the part of the algorithm (which generally exists) which is most paralellizable.
I shall not respond to you again. You seem to be lacking a few brain cells where it matters, to have completely missed over everything that has been said to get here and flame me with inaccurate material.
- Rei (the Irate)
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Its not surprising that you post as a Coward. If I talked such utter drivel with no backing, I wouldn't want anyone to know it came from my mouth
- Rei (the downright bitchy)
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Ok. Lets say we're analysing heat flow on a 1 foot by 1 foot piece of metal. We break it into 9 particles - they're each 3 by 3 inch squares. Now lets break it into 144 particles - they're each 1 by 1 inch squares. By increasing the number of particles, you correspondingly decrease the size of the cell. I figured this would be intuitive to any reader and would not need further explanation.
BTW, I have worked on this before (well, something similar). For a graphics project I did an overly elaborate average yearly climate determination system (cut some corners on the algorithms, yes - not to paralellize - it was linear - but due to time constraints) for landscape modeling; I am fully aware of how increasing the particle resolution increases the accuracy (I did both air and ocean current heat distribution, among other things). And the code was very easily paralelizable; however, the landscape was designed to be plugged into a game, and I don't think enough gamers have beowulfs, for example, to make it worth it *grin*
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
But at *every* iteration, each node has to see if any particles from any of its neighbor nodes will interact with any of its particles. In effect, every node must know about possible interactions with every other node at every iteration, so it defeats the purpose of parallelization. This is known as an n-body problem. It's virtually impossible to parallelize, unless you're willing to accept approximate results and rely on probabilities of interactions.
Ah, but if you have enough memory for each node (as was in my calculations) to sto re the entire contents of memory, it only gets updated at the end of each cycle (preferably with broadcast packets so all nodes can update at once). Thats the data on 100,000,000*34=3.4 billion bytes being sent across the network at the end of calculations. With 100mbs, thats, what, 12mBs? Near 5 minutes to update all of the data (with gigabit, of course, much faster).
;) ). Anyways... as you can clearly see, the time in each node dwarfs the data transfer time. Also, I think my optimal number of nodes came up to be near 5,000 for my sample problem... although I certainly wouldn't want to be trying to maintain a system like that.
Now, as I interperited the problem, it is O(N^2) - each particle interacting with each other one. We're talking about O(N^2) - N particles on each node affected by 100 million particles each. Even if we assume 100us for a single pair of particles calculations on each node, and 100 nodes (N=1 million particles), that comes down to... hmm, 317 years per node? Ok, I'm assuming that either a) it isn't O(N^2) or b) they generally use far less than 100 million particles, (for now
My guess is there is a non O(N^2) approach out there.. but anyways. You get the point. Bandwidth is not an issue if each system keeps a local copy, which was, as you'll note, described in my algorithm and my cost calculations.
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
To be honest, I myself know very little about differential equations. It's definitely not one equation, but interdependent systems of equations. Anyway, someone whos writing his master thesis on the stuff told me that hes doing simulations (of some sort of circuity) that can't be parallelized.
I'm a numerical analyst, but not a specialist in differential equations and, by the standards of numerical analysts blissfully ignorant of such things. But I can say a bit more than has been said. First of all, nuclear simulations probably center on one 3 dimensional non-linear partial differential equation (PDE). Circuit simulation would be a set of coupled ordinary (linear or non-linear) differential equations. For the former, you iterate using something like Newton's method to get a sequence of linear PDEs each equation depending on the previous solution. These solutions eventually converge on the true solution of the nonlinear PDE. To handle the linear subproblems you discretize each linear problem, either using finite elements or finite differences, and get a huge linear system of equations. This is what is slow: solving a huge linear system of equations in parallel. (Those of you who took linear algebra in university should try to think of how to parallelize the inversion of a huger 1,000,000x1,000,000 matrix; that's essentially what you need to do---and the sizes I quote are almost certainly a vast underestimate). Of course, these can be "decoupled" into lower order linear systems of equations which could be farmed out to individual nodes, but the decoupling process itself is computationally intensive and not given to an easy or efficient parallel implementation. Consequently, most people use an iterative method for the linearized systems as well. These work using matrix vector multiplication as a core operation. Matrix/vector multiplication CAN be parallelized nicely, but once you've done the multiply there has to be communication between nodes before the next iteration. This can slow things down. When your systems of equations are really huge you're shuffling around a lot of data and this communication overhead really makes you want to start looking at supercomputers that do better at communication between nodes. With some of these sorts of problems they are already pushing the limits of what can be done with a supercomputer with fast communication between nodes. I don't know how much slower a large Beowulf cluster would be, but communication IS going to hurt you to some extent.
I'm not aware of circuit simulation problems of this level of difficulty, but I wouldn't assume they don't exist. What the poster you quote seems to have missed is that many problems are not ordinary differential equations and PDEs can sometimes require a very fine discretization over 3 dimensional space. This results in solving linear systems of equations with variables corresponding to every discretization point; the systems end up involving many millions of coupled variables. Unfortunately the only mathematical methods we have for these types of problems require fairly regular communication between nodes. I hope this isn't gibberish to those who haven't done much math. Two key points: Huge amount of data; complicated mathematical problem involving said data that has to be broken down into nested stages, each requiring communication after completion. BTW, that was a rather good post. I just wanted to elaborate on exactly why differential equations are hard.
Indeed. Maybe the person you are responding to would care to give us sample code of a parallel FFT instead of a cooked up embarassingly parallel code segment. I would also like to see a code for solving a finite element discretization of a 3-d PDE. If he can really parallelize any practical, real-world problem he can become very rich; and personally I'd love to see such a huge scientific advancement come out of a slashdot discussion.
(The anonymous coward who unwisely attempted to give a thumbnail sketch of how non-linear PDEs are actually solved and why communication between nodes matters).
This is wrong. The problem in the example can't
be broken down into these "particles" you propose
(and from which you extract your efficiency figures).
The point of the example was that each region/node
has to wait *entirely* on communicating with
adjacent regions between states. It's not "calculate
the 9,996 particles in this region;we'll get the 4 border
particles when we are done". The calculation of the *whole* region
can't be done until information about the condition
of the edge arrives. This problem doesn't break up
well at all; the communication between nodes will
be a huge issue.
point having been made available previously.
That's an unsupported assertion that seems to based on ignorance of many "real world" calculations. Maybe the calculations you are interested in are embarassingly parallel, but in fact real world calculations often don't work this way. You've been given many examples that are drawn from common supercomputer applications. If I could find a short FFT code on the web I'd post it and let you take a stab at parallelizing it. Or a finite element code. Why don't you try one from Numerical Recipes or netlib.org? It would shut up your critics and bring you glory and wealth.
Seti@Home is a terrible example, when the real
issue is nuclear weapons modeling, etc. There's little to
no dependency between nodes with Seti@Home. Nuclear
weapons modelling is all *about* dependency when
you try to distribute it.
It's been pointed out to you twenty times in this
thread, but you seem to be willfully missing the point.
Your examples are all situations where discrete
problems can be solved on individual nodes, with no
great need to know the results found on other nodes (Seti,
other brute force cracking projects). As soon as
the computation on one node depends to any extent
on the results found on other nodes, however, the
cluster starts losing ground to the supercomputer, simply
because of communcation costs and the associated cpu waiting times.
But, even though the equations don't express a direct linkage with anything other than neighboring particles, they "communicate" indirectly with the outside through a chain of other particles. Taking this into account is necessary to get reasonable accuracy in the solution (pick up a numerical analysis text that covers partial differential equations) and this leads to a fairly complicated set of linear equations that requires a fair bit of interprocessor communication to solve.
My business partner notes that a Beowulf would be a typically Chinese way to solve the problem of not having a supercomputer, and given this, it is likely that they are using them already. The US thinks of military problems from the standpoint of unlimited resources, while China thinks of them in terms of what they can coax out of what they already have access to. Why use a multimillion dollar machine that you have to execute extreme skullduggery to get when you can rustle up a large amount of cheap machines locally and give it a go from there? To give you an idea, the Chinese already invented a method of disabling satellites that involves setting a relatively weak laser onto a readily available telescope tracking system normally used in astronomy. No Pentagon-level funding involved to make this device...
What we call folk wisdom is often no more than a kind of expedient stupidity.-Edward Abbey
According to Sony specs, Sony Playstation 2 qualifies as a Supercomputer too, since it does exceed 1GFlop limit.
Some time ago there was some talking about this here on Slashdot, but it seems it didn't lead anywere. Anyone has more news? Did they lift this really stupid limitation like they did with encryption?
Ciao, Rob!
AniToolBox! An Open Source animation program!
You have some misconceptions about supercomputers. Even though I love Linux as much as the next guy, let me attempt to clarify for you: not all problems can be solved with a cluster of Linux boxxes. Here's a real simple explanation for why we still need big iron computers: even though there is a large class of problems that are computational-bound (and can thus be solved nicely by a cheap cluster), there is an equally large number of problems that are bound by communication, and thus the max speed of the system is roughly equal to 1/latency of the connection. After you hit this maximum speed, throwing any more linux boxes after the problem will not increase the speed of your calculation. You're maxxed out. And when you're doing simulations that need to be done *quickly*, there's only one way to go: machines like Blue Horizon here at UCSD's SDSC that are capable of tasks that *no amount of PCs in a cluster* can solve in equal amounts of time, simply due to the interconnect. Remember, if all a Supercomputer was was its CPUs, then Blue Horizon would be nothing more than 1000 Macintoshes running AIX. Cheers, Bill K
Here's a code block that cannot be parallelized well with a beowulf cluster. And before you ask, it's LU decomposition (solving a series of equations), which *real* computer scientists have a tendancy to do instead of focusing on embarassingly parallel applications:
FYI -- this will parallelize on an ideal (CREW PRAM) machine which is probably what you learned on at that substandard university of your's. Ideally it goes from an O(N^3) algo to O(N) but in real life (i.e. not that dreamland you live in) you get nowhere close to it. If you can make this run in O(N) time, you are a friggin genius. Of course, I don't expect for you to reply to this, because you can't parallelize it WELL with a beowulf cluster.
Here, I'll even make it easier for you. Use the
LU decomposition routine found in SCALAPACK (which is written by people who actually understandt the problem, not you), go run it on your Beowulf cluster, and see if you can get linear speedup past 32 processors.
http://www.math.uu.nl/people/bisselin/
If you can do that, I'll send you 5 dollars.
Bill K.
UCSD
bkerney@hotmail.com
But if you want a lot of little pecks everywhere in the farmyard the chickens win ... It can be as simple as looking at the problem in a slightly different way.
threadeds blog
You break the problem up, and solve parts of it. *Then* figure out the parts that inter-relate.
In the case of the above, you also need to take into consideration that you could simply have the math equations needed sent to the cluster, with one primary machine just putting it all together. Example:
10 to the 10th can be thrown accross 5 machines, calculating 10 to the second. This a very simplistic example, and in real life, wouldn;t work quite right, but in the case of very math intensive applications, some of the equations *can* scale to that extent. It is also able to be processed in parallel, simply becouse you can be working on several equations at the same time.
-- I'm the root of all that's evil, but you can call me cookie..
Ah, but that was the point - that their communication *is* indirect. Here, let me give you a sample to make it a bit clearer.
;)
You have a plate, with heat distributed in integral amounts as follows:
1 3 2 3 5 9 9 6
2 3 3 3 4 6 9 9
2 3 2 2 2 2 6 9
2 1 1 0 1 3 5 9
1 2 0 0 0 1 2 4
0 2 1 1 3 4 4 4
1 3 3 4 5 6 5 5
3 5 7 8 8 7 4 5
Now, if we have a single machine run across all of the data, it has a temporary buffer and it determines how hot each particle will be at the end of the cycle and stores the result in that buffer. When the cycle is over, that buffer is copied over the original data, and a new cycle begins.
Now, breaking this up into 4 machines, we have:
1 3 2 3 5 9 9 6
2 3 3 3 4 6 9 9
2 3 2 2 2 2 6 9
2 1 1 0 1 3 5 9
1 2 0 0 0 1 2 4
0 2 1 1 3 4 4 4
1 3 3 4 5 6 5 5
3 5 7 8 8 7 4 5
With this setup, each quadrant has its own temporary buffer. Each one then averages its data and stores its results into its temporary buffer. However, the border parts (for example, in the bottom right buffer, the top (0 1 2 4) and the left (0 3 5 8) need data from the other quadrants (0 1 4 8) and (1 3 5 9) to get a proper average. (you can also adjust this to have the particles interact with a wider range of particles, but that doesn't effect the big O of the calculation. And, as before, when the cycle is done, each machine copies their temporary buffer into the original. As you can see, the only network traffic is in a) keeping the machines in sync, which is very minor, and b) transferring border data, which, as I showed in the earlier note, decreases with the number of particles.
The "indirect" heat transfer comes automaticly from this algorithm - now that the border particles have absorbed/lost heat from/to their neighbors, the particles next to the border particles will be warmer or cooler, respectively. You follow?
If it is *really* needed, I will code up a sample for you. But I'd rather spend my free time on my genetic algorithms currently
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Ah, food for thought ; ) my mind is getting well fed (and I needed to do something while I wait for my current program to decide to crash so I can track down the bugs ; ) )
I really wish you hadn't posted anonymously - you deserve recognition for your input.
Ok, so the big problem seems to be an efficient way to paralellize solving a system of equations. I've been going over the process on paper, and this is what I came up with.
we'll assume a system of equations, set up in a matrix where each variable's multiplier is in order, and the last column is a constant value.
1) sort the equations into an order wherein the first variable is nonzero in the first equation, the second varaible is nonzero in the second equation, etc. Row 0, column 0 is set to 0.
2) We'll use the part of memory which held the first equation to store the result of solving for the first variable. Divide each variable's multiplier by the negation of the first variable's multiplier.
3) On to the second equation - substitute the result from the first equation in. This means adding to all multipliers what was in the row above, times that variable's multiplier in the current row.
4) Then we repeat step 2. However, once we have solved for the second variable, we need to go through the first equation's spot in memory and repeat step 3 on it, using the second row's multipliers.
5) On to equation 3. We substitute equations 1 and 2 in as we did in step 3. Then, we do step 4, except on the first 2 rows. And so on with each new equation.
Now, the question is: how to paralellize this?
We can't paralellize each row, as each row depends on the result of the previous row. However, we can paralellize what occurs in each row. Imagine splitting the matrix amongst nodes so that column X goes to node X%NumNodes. Now lets go over the steps.
1) As before. This would be best done before dividing it up amongst nodes.
2) Node 0 broadcasts the negation of its multiplier. All other nodes pick this up and divide by it on each of their members in the first row. Node 0 then sets column 0 to 0.
3) All nodes wait for all others to complete. They all set themselves to work on the second equation. Row 1,column 0 is broadcast. All the values from Row 0 are multiplied times that, and added to the second row. This completes the substitution. Then row 1, column 1 is solved as in step 2.
4) this continues on, as was shown above.
You see, each node doesn't need any data from horizontal nodes except the current multiplier, which is almost no traffic.
Swap space nearing full... gotta post now. Send comments to spurius@earthling.net. Bye! I hope this works
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
As I demonstrated in another note, the N-body problem can be solved without massive bandwidth consumption, if you give each node enough ram to store the entire problem, not just the particles it is working on. I did some basic cost calculations, and a distributed system still came out notably (50x better).
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Bill, thank you for your polite post (a lot of people, when someone disagrees with them, get rather angry). First of all, I'd like to once again disperse the myth that Beowulf is Linux. Beowulf is an clustering organisational structure where there is no server; all nodes sync themselves up, and store their own or all of the data on them at once. It is operating system independant. However, reading posts at slashdot one would think that only Linux can support beowulfs. This is untrue. You can make a beowulf out of anything that supports message passing.
:)
Secondly, my point was not to demean mainframes and say that all of their tasks should be done on beowulfs. My point is that many tasks which are being done on mainframes need not be, with some rethinking of the problem. That is why I have been trying to get people to throw problems at me - I love paralellizing code, and making the implementation cheaper. If I can make code that would normally require a mainframe run just as well on a beowulf, its a pretty good feeling. Thus, once again, I encourage you to throw an algorithm that you have a mainframe at SDSC running at me - either on slashdot, or to my email (spurius@earthling.net). I'd love to take a whack at it
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Get a hold of yourself. First of all, you're claiming "Your examplex are all situations where discrete problems can be solved on individual nodes". And, yet, the problems I am solving are the ones that are being thrown at me, saying that they don't paralellize well (FFT's, N-body problems, differential equations, etc). So.. how again is it that I am rigging my sample data, when it is given to me by people who disagree with me?
Please think clearly.
- Rei
"99 dead duelists of Dios on the wall. 99 dead duelists of Dios! Take one's ring, pass it around..."
Arrgh. Rei: "You have a plate, with heat distributed in integral amounts as follows: [...] Now, if we have a single machine run across all of the data, it has a temporary buffer and it determines how hot each particle will be at the end of the cycle and stores the result in that buffer. Now, breaking this up into 4 machines, we have: [...] With this setup, each quadrant has its own temporary buffer. Each one then averages its data and stores its results into its temporary buffer. However, the border parts (for example, in the bottom right buffer, the top (0 1 2 4) and the left (0 3 5 8) need data from the other quadrants (0 1 4 8) and (1 3 5 9) to get a proper average." Ok. Let's stop here. You're right. Those border parts DO need data from the other quadrants. BUT, and what you're missing here, is that everything else in that quadrant is reliant on those border values. You see what I mean? You have a 4x4 matrix, and each entry is reliant on it's neighbor for it's value. You can't do any calculations until all the entries are known, and that means waiting for edge data. -josh
Now that's half baked and likely coming from someone who's not got as much experience with overclocking and has been reading the crap Intel dishes out. Not to be offensive to someone who's actually supporting my beliefs but if you've got an overclocked Celeron that's cooled properly you aren't going to burn it out. Of my 7 systems, including 2 dual Celerons only one isn't overclcoked. In my past I've overclocked nearly every system I've owned including old 80286 and 8088 systems. Of all of those only ONE CPU has ever burned out - it was a defective boxed Celeron 366 that fried after just 4 hours of operation - I'm convinced it would've died just as quickly at normal speeds. One of my systems uses an old cachless Celeron 266 that's been running 448 24X7 since the day I bought it over a year ago with poor cooling and bumped voltage - it's ROCK stable even running WIN98! I wish this myth of CPUs burning out more quickly due to overclocking owuld just die. Perhaps the CPU won't last 40years and might only last 30 - boohoo, I can deal. The fastest single CPU system I'm running is a watercooled Celeron 366 that's run as high as 620+mhz. It's most stable in the 590 range though as the water is tough to keep chilled enough for 600+ speeds. At 590 I've not had to change the water in a week - it's getting scuzzy (lo). Not bad for a $60 CPU eh? Can't wait to get hold of a K7 or a PIII 500! BLKMGK morejunk4me@hotmail.com