peskin@caip.rutgers.edu (R. L. Peskin) (03/28/88)
The recently announced results from Sandia are very impressive, but I am confused. Part of my problem stems from having to read about this significant advance in the NY Times rather than from a more technically informative source. The Times only told of the claimed speedup, the winning of the "prize", and something about howq they made the problem bigger rather than smaller. No mention of what problem was solved. Linear speed up with number of processors is not a new result. Well over a year ago we showed an ABC flow (Beltrami fluid flow) result that exhibited speedup of 99% of 128 running on a 128 node NCUBE. The problem parallelized well (obviously) and actually ran at 1.75 times faster than the same problem on a single processor Cray XMP. Similar results were reported by U. of Michigan (if my memory serves me) also on an NCUBE. So there has to more to the Sandia result than just speedup proportional to the number of processors (they have a 1024 node NCUBE). What is it? Are there results application domain independant? That would be a real advance, but improbable. Parallel computing (on distributed systems, at least) is much like the old analog computing. The name of the game there was reconfiguring the machine (using a patch-board) to best represent the physical aspect of the problem. In parallel computing we have a similar need to decompose the problem domain by appropriate use of interprocessor messaging and localized computation. I feel this is very problem domain specific. (It is also a difficult area requiring knowledge of the application as well as computing per se.) Real gains will come as general principles evolve that point to methods to optimize the many choices in domain decomposition. Has Sandia come up with such principles? If so, will they let the rest of us in on it? The "press" has been overwhelming on this one (I even saw it reported in a NJ "shopping" weekly.) But the technical community (who were not able to attend the meeting where this was reported) seem to be in the dark. (I will admit to hearing about this directly from John Gustafson during a phone conversation, but there was not time to explore it fully.) How about it Sandia; can you let us know some facts via a message to this bboard? --dick peskin
grunwald@uunet.uu.net (03/30/88)
I've read the paper & basically, there's nothing that wonderful about what they did (no slight intended to the folks at Sandia). They took a parallel algorithm, did a good implementation, measured the results and analysed them. The reason they're getting the press instead of similar efforts at Rutgers, etc is that they had a 1024 processor system. This allows them to show real speedup of 1020, where you can do 128 at best. Now, you might say ``So? They've got money and we don't'' -- and you'd be right. However, this was the requirement of the Karp Challange. Real Speedup on Real Hardware. So basically, they've shown that Amdahls law, while true, isn't so limiting for certain problems, and that speedup in the 1000's is possible.
grob@cmcl2.NYU.EDU (Lori S. Grob) (04/05/88)
There is a paper by Ron Cytron of IBM Research that was at the ICPP a few
years ago, that presents an analysis of performance with respect to the
size of a task and the processor allocation for that task. It is theoretical
and does not claim to be for all topologies but in light of this discussion
I thought that the folks who did not know about it might be interested.
Within the constraints of the problem as discussed in the paper it gives
the formula for figuring out the "breakeven point" for adding processors to
a problem. ie. The point beyond which it will cost more to throw more
processors at the problem then you will get help from those processors.
The paper applies the formula to a DOALL loop and to a vector sum reduction.
I think it was the 85 or 86 ICPP conference.
Lori S. Grob (NYU Ultracomputer Project)
grob@nyu.arpa
{mcvax!seismo,floyd,harpo,ihnp4,...}!cmcl2!grob [That's c-m-c-ELL-2]
Courant Institute (NYU), 251 Mercer St., NYC 10012, 212-998-3350