Author: Uri Blass
Date: 14:18:04 09/26/01
Go up one level in this thread
On September 26, 2001 at 15:09:57, Robert Hyatt wrote: >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 have a lot of positions based on my correspndence games when Deep Fritz changed it's mind after a long time. If somebody is interested in getting them and comparing the time that Deep Fritz needs to change it's mind with one processor with the time that it needs to get to the same consequence with 2 processors then I can send the positions by email. I cannot check it because I have only one processor and inspite of the claim that it is possible to change the number of threads in one processor I cannot increase the parameter of number of threads in Deep Fritz on one processor(the computer simply tells me 1 that I cannot change). I think the interesting test is not to test the time that the program needs to finish some depth but to test the time that it needs to find moves (my experience is that Deep fritz changes it's mind often for positional reasons at long time control) Uri
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.