Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!columbia!rutgers!husc6!think!bradley From: bradley@think.uucp (Bradley Kuszmaul) Newsgroups: comp.arch Subject: Re: chewing up mips with graphics Message-ID: <5793@think.UUCP> Date: Thu, 25-Jun-87 10:15:07 EDT Article-I.D.: think.5793 Posted: Thu Jun 25 10:15:07 1987 Date-Received: Sat, 27-Jun-87 01:25:52 EDT References: <8270@amdahl.amdahl.com> <359@rocky2.UUCP> Sender: news@think.UUCP Reply-To: bradley@godot.think.com.UUCP (Bradley Kuszmaul) Organization: Thinking Machines Corporation, Cambridge, MA Lines: 68 In article <337@astroatc.UUCP> johnw@astroatc.UUCP (John F. Wardale) writes: >This may be true, but for most "real" problems, some well know >person determined that the average code spends 90% of its time >executing 10% of its code. > >This and other related studys show that a large fraction of >problems that have no, or very limited parrallelism. Actually, I interpret the 90%-10% rule as indicating that there might be a lot of parallelism in problems. Since 90% of the time is spent executing a very small amount of code, it seems likely that there is a lot of data involved. It is also likely that the dependencies between data are something smaller than "completely connected", and so it is likely that different parts of the data can be processed in parallel. Now, I am the first to admit that everything I just said has a lot of "maybes" and "likelys" in it, and while I personally believe that in fact there is a lot of parallelism lying around, I would not expect you to believe it based on such a weak argument. My feeling is that the lesson to be learned here is not "There is X amount of parallelism lying around in current applications". The lesson is "Rules of thumb, such as Amdahl's Law, don't have much to say about parallel computing". >A couple mounths ago there was some discussion of somebody's >challenge (with a moderate cash prize) .... As I recall, you had >to speed up a general problem (not limited to HIS problem set, but >he could reject anything that was "embarrisingly parrallel" [like >the 100 compiles example]) by a factor of 100, and you could use >as many processors as you wanted. Did anyone save any of these? >Has anyone won the prize yet? As far as I know, no one has seriously tried to solve the Karp problem. I think it is only a matter of time. The problem is that in order to even have a chance at solving the Karp problem, you have to have at least 100 processors in your parallel machine (otherwise no way are you going to get a factor of 100 speedup). Most of the machines which have <1000 processors in them (e.g. BBN butterfly or Intel IPSC) have relatively slow communciations networks, and thus find it difficult not to lose a factor of 10 due to that sort of inefficiency. If we assume (handwave handwave) that parallel computing carrys come constant performance cost (say a factor of 10) then we need at least 1000 processors. There are very few machines with >1000 processors in them, most of them are not quite general purpose enough to solve the problem. Company plug: The Connection Machine, which has 64000 processors in it, probably has the best chance of solving the Karp problem, but it seems a little unfair to compare 64000 one bit processors to a single one bit processor (for a performance improvement of 64000) or to compare a 64000 processor Connection Machine to a Cray (which is made out of much more expensive technology). My feeling is that the Karp problem should have been phrased as "compare your parallel machine with a single processor serial machine made out of about the same amount of hardware" (or perhaps the same cost?). This would pit a Connection Machine against about a third of a Cray 1, or perhaps a couple of Vax 8800's or a high end IBM mainframe. There are several applications for which the Connection Machine which can beat those machines by an order of magnitude. One can imagine that there are some applications for which the Connection Machine is not well suited, but, aside from simulating a network of Cray computers, I can't think of any :-) -Bradley Bradley C. Kuszmaul, Thinking Machines Corporation, Cambridge, MA bradley@think.com bradley@think.uucp (i.e. seismo!think!bradleWit