Author: Robert Hyatt
Date: 12:09:57 09/26/01
Go up one level in this thread
On September 26, 2001 at 14:23:43, Bruce Moreland wrote: >On September 25, 2001 at 22:49:10, Robert Hyatt wrote: > >>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. > >What it would mean, assuming that such a thing existed, is that parallel >algorithm, when expressed serially, would be better than the serial one. Correct... > >The only law that this would have to violate is the law that says that people >aren't stupid, and this is broken continuously. > >It is possible that someone could be randomly hacking and improve their own >underlying chess program algorithm by making it parallel. Certainly. But then the next step would be to repair the serial algorithm to make it more efficient and fix it. IE alpha/beta is an _inherently_ sequential algorithm, by its very definition and nature. If a parallel implementation is more efficient than the sequential one, then by definition, something is definitely broken in the sequential one. > >>>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... > >Is this constantly monitored? If you were fiddling around and this happened, >how would you detect it? I run such tests all the time. I have a simple script that will run the same position with 1, 2, 3 and 4 processors. I have found that to be a great way to excise parallel search bugs that I introduce without knowing I have done so. When I did my Ph.D. thesis, I ran so many 1, 2, 4, 8 and 16 processor tests it was not funny. Taking the 24 kopec positions, and using one line for each position, to record just the search time and nodes required to search the position to a fixed depth, I had over two _boxes_ (read reams, or 500 sheets per box) of paper with results. That translates into 66 lines per page, times 1000 pages, or 66,000 lines of output. I always saw the "occasional" super- linear speedup on a single test position out of 24 here and there. I _never_ saw any consistent super-linear speedups that were not bugs. IE I had a broken move generator that could screw up (due to something in shared memory) and not generate a complete set of moves, which would speed the search up signficantly but wrongly. I would erroneously stop (abort) some parallel search branches and not complete the work that I had thought was really going to be completed. And in each case, I found and excised the bug that caused the better-than-expected speedup. For my final dissertation report, those 1000+ pages had _no_ anomalies of any kind with regard to super-linear speedups. They did contain exactly _one_ test result where the search took hugely longer with 16 cpus than it did with one. > >I don't think that I am saying anything threatening. There is a lot of random >junk playing chess. It might be possible that if you write more random junk >that does a parallel search on top of the first random junk, everything might >get better. I wouldn't disagree there. IE when Schaeffer first parallelized the very old program "tinker belle" by Ken Thompson, the parallel speedup was very good. But then when he compared that program to his, its branching factor was much worse, and the search depth was far less for the same period of time. meaning that a bad program might be improved more than a good program when doing things in parallel. But the problem remains... the bad program _can_ be made a lot better while still running serially. And reporting a 4.5 speedup with 2 cpus on a lousy program is not exactly impressive, IMHO. Particularly knowing how alpha/beta works and how serial it is by nature. > >If Vincent is saying that "everyone" is getting speedups of greater than 2X on >two processors, I don't believe that, but the proof is in the proof. Without >it, this just sounds like a rumor, and I'm not interested in investigating it. > >bruce Vincent has been claiming that for his for a long time. He has now added Deep Fritz to that "pot". Someone with deep fritz and a dual CPU can run some test positions and confirm or disprove that pretty quickly... I posted my data earlier this morning. I'm a bit surprised at the 1.9x for 2 cpus. But not nearly as surprised nor concerned I would be if it was 2.5X. The 3.5X is pretty much in line with what I have been getting for a year or more now, since the last parallel algorithm changes I made... I still see numbers < 3X on occasion. On rare occasions I see numbers > 4X. But the average is always <4X for me.
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.