Author: Robert Hyatt
Date: 19:49:10 09/25/01
Go up one level in this thread
On September 25, 2001 at 18:36:57, Bruce Moreland wrote: >On September 25, 2001 at 10:29:56, Robert Hyatt wrote: > >>I don't see this as a problem. The issue still remains, "can you do something >>parallel that executes more than 2x faster than what you do serially?" If the >>answer is "yes" then there is something basically wrong with your serial >>algorithm... > >If I make a minor change to my program, the same search might take half as long, >or twice as long, or whatever. > >If I run a given search serially, with a particular version, it takes X time. > >If I run the same search with a two-processor parallel version, it might take >1/2X time, or 1/4X time, or X time, or even >X time. I believe this happens for >the same reason that when I make a minor change to my serial version, I get >different search times. > >If I could consistently get less than 1/2X time with two processors, that'd be >something to be happy about, and it would also raise some serious questions, >obviously. > >But I don't think it is necessarily true that this would violate the laws of >physics. Actually it does. Because if you can do > 2.0 with 2 processors _consistently_ then you can do > 1.0 with one. By using the simple time-slicing approach that everyone knows about. If the "synergism" works for two processes on two cpus, it will work for two processes on one cpu in exactly the same way. Which means the two-process algorithm is _better_ than the one-process algorithm. And if it can be done with two processes on one cpu, then it is trivial to prove that it can be done with one process that alternates between searching two different paths one node at a time. > >If the two halves of the problem were absolutely independent, then of course, >you'd have a 2X speedup at best. > >Since there is interaction between the two threads, it is not necessarily true >that you can have at most a 2X speedup. It is possible to construct a >hypothetical case where one thread helps the other to over-achieve, and perhaps >there are problem domains where these hypothetical cases would be the rule, >rather than the exception. > >Chess programs are deeply flawed from the start, so I'd believe that anything >might be *seen*. Whether it's seen for a reason, or due to random chance, I >don't know. > >But I don't think that people who argue for super-scalar speedups are >necessarily arguing in favor of perpetual motion machines. > >bruce My conclusion is based on the fact that for 25 years we have been seeing parallel search programs. Mine. Many others. And in _every_ case, we have not seen any super-linear speedups on a consistent basis. On the occasional problem, of course they happen. But not on a consistent basis. In light of that, _one_ program isn't going to convince me that suddenly it is possible...
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.