Author: Tony Werten
Date: 00:06:46 10/03/01
Go up one level in this thread
On October 02, 2001 at 10:38:02, Robert Hyatt wrote: >On October 02, 2001 at 04:54:13, Bruce Moreland wrote: > >>On October 01, 2001 at 00:36:48, Robert Hyatt wrote: >> >>>On September 30, 2001 at 14:47:21, Bruce Moreland wrote: >>> >>>>On September 29, 2001 at 14:54:03, Robert Hyatt wrote: >>>> >>>>>On September 29, 2001 at 10:41:37, Miguel A. Ballicora wrote: >>>> >>>>>>Super-linear speedups are "probably" impossible but so far I did not see that >>>>>>they are "provably" impossible. I would settle with "They are believed to be >>>>>>impossible". >>>>>> >>>>>>Regards, >>>>>>Miguel >>>>> >>>>> >>>>>They simply _are_ impossible. Unless you believe in perpetual >>>>>motion, infinite compression, a fire that will burn forever, etc. >>>> >>>>Take a human who can move a 200-pound box, but only by scraping it along the >>>>ground. Compute the time it takes him to move 10 such boxes 100 yards. >>>> >>>>Assume that two humans can move a 200-pound box more easily. Can they move a >>>>200-pound box more than twice as fast as one human? Would this violate laws >>>>against perpetual motion? Of course not. It is perfectly valid to consider >>>>working in parallel rather than working serially. The mechanics of the task >>>>might change, resulting in much increased efficiency -- they can lift the box >>>>off the ground. >>> >>> >>>I think that after you think about this example, you will see the flaw. >>>Lifting the box off the ground takes _more_ effort. So the two people are >>>doing _more_ work in a given period of time than two people pushing two boxes >>>at the same time. The ancient Egyptions found that dragging was better than >>>lifting. :) >>> >>> >>> >>>> >>>>Two workers cooperating to perform a task, do not *have* to go less than or >>>>equal to the speed of two workers, each of whom does exactly half of a task that >>>>can be fairly divided in two. >>>> >>>>There exists the opportunity for synergy. >>>> >>>>The argument that the above violates the prohibition against perpetual motion is >>>>fallacious. >>>> >>>>bruce >>> >>> >>>Not after you think about it. If two people work and each of them moves 5 >>>blocks, then they do no more work than the 1 person did moving 10. But they >>>did it in twice the time. If they _lift_ the block _and_ move it, they are >>>doing _more_ work per unit of time. They should have moved the blocks >>>faster one at a time, but they were taking it easy... >>> >>> A computer can't do that. >> >>You can't possibly be arguing that there is nothing that N (N>1) people can't do >>in less than 1/N the time that it takes one person. >> >>I was trying to find an obvious example. If you don't like that one, I'm sure >>there is another one. >> >>bruce > > >If you mean something that takes one person N units of time to do, and two >can do it in less than N/2 units of time, then no, I don't believe it is >possible. The exception is that I have to move a 400 pound box. I can't >move it by myself, probably. So I can't do it at all. Two people can >probably shove it around. > >But I can't think of any thing that one can do, where two can do it twice as >fast, assuming that two don't do more physical work than the one person did. >Otherwise it isn't reasonable, as it would be like comparing two 1ghz processors >to one 800mhz processor. The two 1 gigs should run more than twice as fast. >They are doing more than twice as much work. > >If you can find an example, it would be interesting to analyze it. Either both >do more work than one would do, or else there is a trick involved. IE you have >to simultaneously nail up both ends of a long board. One person has to walk >back and forth multiple times. Two would not. But in that case, the two-person >team eliminated work required of the one person team, _before_ the project even >starts. I don't see any possible analogy applied to alpha/beta search. That was my idea. If you can improve the locality of the search you can have a bigger speedup. fe I have a very expensive evaluation so I hash all kinds of stuff. Searching related moves in parallel can give me a speedup because of entries in these hashtables that in serial would have been replaced. Tony
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.