sccowan@watmsg.uwaterloo.ca (S. Crispin Cowan) (06/03/90)
csimmons@jewel.oracle.com (Charles Simmons) writes: >I'm curious as to what extent researchers have observed real superlinear >speedups. For example, consider a chess program. On an old-fashioned >single processor architechture, the program will examine multiple >alternatives one at a time. The results of each alternative can trim >the amount of searching required in subsequent alternatives. (The >alpha-beta cutoffs become closer together.) Now we might imagine that >a version of the program written for a parallel machine might be able >to benefit from examining multiple alternatives in parallel. For example, >if one alternative is highly advantageous, it might cause the alpha-beta >cutoff values to get lots closer lots faster. >-- Chuck It's a theorum that (theoretically, anyway) super-linear speedup cannot occur. In practice, it may occur marginally, but this is due to the fact that P processors have: -P times as much cache -P times as many data lines to their local main memory (modulo shared memory) And therefore approximately P times the memory bandwidth. As some may have noticed, high-performance RISC processors are reducing even compute-bound problems to memory BW-bound problems. Not because RISCs are memory pigs, but because they run so fast that they saturate the memory bandwidth. So the major win of multiple processors is becoming the increase in bandwidth to memory. Crispin ---------------------------------------------------------------------- (S.) Crispin Cowan, CS grad student, University of Waterloo Office: DC3548 x3934 Home phone: 570-2517 Post Awful: 60 Overlea Drive, Kitchener, N2M 1T1 UUCP: watmath!watmsg!sccowan Domain: sccowan@watmsg.waterloo.edu "You can have peace. Or you can have freedom. Don't ever count on having both at once." -Lazarus Long "You can't separate peace from freedom because no one can be at peace unless he has his freedom." -Malcolm X
csimmons@jewel.oracle.com (Charles Simmons) (06/04/90)
In article <1990Jun3.145408.2472@watmath.waterloo.edu>, sccowan@watmsg.uwaterloo.ca (S. Crispin Cowan) writes: > From: sccowan@watmsg.uwaterloo.ca (S. Crispin Cowan) > Subject: Re^2: Superlinear Speedup (was Re: Scalability?) > Date: 3 Jun 90 14:54:08 GMT > > csimmons@jewel.oracle.com (Charles Simmons) writes: > > >I'm curious as to what extent researchers have observed real superlinear > >speedups. For example, consider a chess program. On an old-fashioned > >single processor architechture, the program will examine multiple > >alternatives one at a time. The results of each alternative can trim > >the amount of searching required in subsequent alternatives. (The > >alpha-beta cutoffs become closer together.) Now we might imagine that > >a version of the program written for a parallel machine might be able > >to benefit from examining multiple alternatives in parallel. For example, > >if one alternative is highly advantageous, it might cause the alpha-beta > >cutoff values to get lots closer lots faster. > >-- Chuck > > It's a theorum that (theoretically, anyway) super-linear speedup cannot > occur. In practice, it may occur marginally, but this is due to the > fact that P processors have: > -P times as much cache > -P times as many data lines to their local main memory (modulo > shared memory) > And therefore approximately P times the memory bandwidth. > > As some may have noticed, high-performance RISC processors are reducing > even compute-bound problems to memory BW-bound problems. Not because > RISCs are memory pigs, but because they run so fast that they saturate > the memory bandwidth. So the major win of multiple processors is > becoming the increase in bandwidth to memory. > > Crispin Yah... Hopefully obviously, I'm not real interested in the speedup effects caused by having more caches and more main memory bandwidth. Also, obviously, I can simulate any multiprocessor algorithm on a single processor by using time sharing techniques. Clearly, adding the time sharing techniques would cause a certain amount of overhead to occur. So I'm still interested in the question of: To what extent have researchers found algorithms that run much faster when you explore multiple possible solutions at the same time. Thanks, Chuck
davidsen@crdos1.crd.ge.COM (Wm E Davidsen Jr) (06/04/90)
In article <1990Jun3.145408.2472@watmath.waterloo.edu> sccowan@watmsg.uwaterloo.ca (S. Crispin Cowan) writes: | It's a theorum that (theoretically, anyway) super-linear speedup cannot | occur. In practice, it may occur marginally, but this is due to the | fact that P processors have: It fact and in theory there is a certain amount of overhead associated with a multitasking system. This occurs even on an unloaded system. The overhead can be expressed as the sum of the fixed cost (peripheral interrupts, etc) and per-CPU costs (dispatching, some memory management). In a well designed multiprocessor system the % of CPU in overhead goes down as processors are added, since the fixed overhead is being split between several CPUs. This continues as CPUs are added until some other resource runs out, then the performace becomes sublinear again. Typically memory bandwidth runs out, but other resources can become a factor, too. -- bill davidsen (davidsen@crdos1.crd.GE.COM -or- uunet!crdgw1!crdos1!davidsen) "Stupidity, like virtue, is its own reward" -me
henry@utzoo.uucp (Henry Spencer) (06/04/90)
In article <1990Jun3.145408.2472@watmath.waterloo.edu> sccowan@watmsg.uwaterloo.ca (S. Crispin Cowan) writes: >It's a theorum that (theoretically, anyway) super-linear speedup cannot >occur. In practice, it may occur marginally, but this is due to the >fact that P processors have: > -P times as much cache > -P times as many data lines to their local main memory... Don't forget that there can also be superlinear effects as fixed overhead (not proportional to P) is handled by P processors instead of 1. -- As a user I'll take speed over| Henry Spencer at U of Toronto Zoology features any day. -A.Tanenbaum| uunet!attcan!utzoo!henry henry@zoo.toronto.edu