Author: Robert Hyatt
Date: 08:20:21 10/07/01
Go up one level in this thread
On October 07, 2001 at 09:52:37, Miguel A. Ballicora wrote: >On October 05, 2001 at 15:12:40, Robert Hyatt wrote: > >>>>for the addition of a second processor, for this comparison to be reasonable. >>>>That is a common flaw in many reported parallel speedups. IE the Waycool guys >>>>at CalTech added another processor _and_ another block of memory. And they >>>>didn't separate the gain from the additional processor from the gain from the >>>>additional hash table size... >>> >>>Wait just a second! you are not doubling the resources then?? then you >>>do not duplicate the worker, you give him another brain but not double arms >>>and legs. Ok. >>>Anyway, this means that if you double all the resources you admit >>>that a super linear speed up is possible (please see level (1) >>>in my other post)? yes or no? Let's agree in the question first. >>> >>>Miguel >> >>NO one disagrees on that. We are talking about two processors vs one processor, >>_everything_ else is the same. In the case of cpus, sure you get 8 registers on >>one intel cpu, 16 on another. you get one cache on one cpu, two on a dual. >>You get one TLB on one, two on a dual. But that is all. Those don't have any >>influence on the _algorithm_. But more memory definitely does. Just take >>any program and run it with a 4M hash table, then an 8M hash table. you will >>see the difference even though you use only a one-processor machine. > >This is extremely unfair. You are not doubling everything, you just double >part of the hardware, how can you want me to even reach 2.0? >The second CPU should be able to use another stack, for instance, so it needs >more memory. >Anyway, let's go step by step. You admit that if you double ALL the resources it >is possible to have a superlinear speedup? yes or no? Re-ask the question. If you double all the resources _but_ the number of processors you _might_ get a super-linear speedup there. The hash table is a significant contributor to speed. So if you double the size of memory, the serial algorithm will run faster. Are you going to compare your parallel algorithm with 2x the memory to the serial algorithm with 2x the memory? If so, then _no_. There will be no super-linear speedup. If you are going to compare your parallel algorithm with 2x the memory to the serial algorithm with 1x the memory, then yes, you might get more than 2x the speed. But only +part+ of it is attributable to the parallel search. > >[snii] > >>So that is the "context" for any valid super-linear speedup discussion. It is >>not about trying to fabricate an algorithm or test case that runs out of >>hardware resources on the single but not on the dual. IE there are plenty of >>machines with 32 general registers. And they won't suffer like the intel >>processors do with only 8. And then there are the crays with hundreds of >>registers... > >We are talking about a superlinear speed up in a given real machine, not >a theoretical one with infinite registers, infinite memory etc. >You are denying the possibility to have linear speedups even on intel >and AMD machines where the resources are limited. Bringing up the Cray >is irrelevant. But first, please, answer my above question to we >discuss about the same things. We obviously are _not_ discussing the same thing. First, when you add a cpu, that is _all_ you can add. Otherwise the science in the result is suspect because if you change more than one thing in the experiment at a time, you can not attribute changes in the result to changes in the experiment accurately. That is no good. Second, the number of registers is irrelevant for alpha/beta discussions. Our data won't fit into a set of 8, nor a set of 32 registers. But if _that_ is the main constraint to performance, then using two processors doubles the number of registers. Is the speedup a result of the additional processors? Or would a single-cpu with 2x the registers be a better comparison? _nobody_ in parallel programming research does such comparisons. That is part of the "science" involved. IE we don't spend all our time trying to find special cases where a super-linear speedup seems to happen. We spend all our time analyzing _why_ when we do see a super-linear speedup, because we _know_ that means that for that example, there is a better serial algorithm than what we are using. Sometimes the super-linear speedup is serendipity... random move ordering effect. Sometimes it is just a poor serial algorithm. And a few end up in the "hardware artifact" column. Which is where your examples all belong. You are essentially asking "can someone use two hammers to drive a pair of screws faster than when they use one crowbar?" The right question would be "Can someone use two of the best nailguns available and drive two nails more than twice as fast as someone using one of the best nailguns available?" Basically, super-linear is an artifact that points out a flaw in the experiment. Either a bad serial algorithm. Some quirk in the hardware that would not be present on different hardware. Etc. For alpha/beta, the hardware is irrelevant except for memory size...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.