Author: Robert Hyatt
Date: 18:23:38 11/10/02
Go up one level in this thread
On November 10, 2002 at 12:28:46, Gian-Carlo Pascutto wrote: >On November 09, 2002 at 23:03:07, Robert Hyatt wrote: > >>I don't have my dissertation handy, but PVS got better than 1.3 for everyone >>that ever tried it and published results in the JICCA. IE if I just split at >>the root only, the first version of Cray Blitz got > 1.3 on average using two >>cpus in 1983 at the WCCC. In fact, 1.5 was a good average. Unfortunately, >>four processors barely improved that so that I took Monty Newborn's ande Murray >>Campbell's suggestion and implemented the PVS algorithm. If you do it right, >>there is no reason it won't produce reasonable speedups for 2, but with all >>processors locked together at any specific node, going beyond 2 hurts, >>especially in the endgame. >> >>I'll locate and report my original 2-cpu and 4-cpu PVS numbers when I get to >>the office, they are in my dissertation. > >I suspect the data may be outdated. PVS wants situations where you can >split so all moves take roughly the same amount of work, or at the very >least situations where one move does *not* take more time then all other >combined. > >Nowadays most programs use nullmove heavily, and have a lot of extensions. >If you add in forward pruning and selective searches, the situation gets even >worse. However, back to Cray Blitz. I used PVS in 1984. I don't _think_ that I added null-move until 1986 or so. But in 1984 we were doing lots of extensions, from in-check, to recapture, to passed-pawn-push, to one-legal-move, and so forth. So the trees (sub-trees) were already dynamically variable in size. As far as null-move, remember it only made a 3.0 vs 3.1 difference when we ran those tests for Vincent a month or two back... > >I found that when using PVS I had trouble keeping 2 cpus busy, because >I always ended up with one move that took way more time to search than >the others. If your loading factor (load you can place on both cpus) >is < 1.5, then you are never going to get a good speedup, so I had to >drop PVS. That is solvable. I reported on an ehancement to PVS that I simply called EPVS that solved this problem. When one processor goes idle, stop the other, go two plies deeper into the tree and search there in parallel as you now have something useful to search. > >Your EPVS presents a solution for this, but when I considered how to >implement it in my program, I decided that it would have about the >same complexity as doing a simplified DTS implementation, where the >latter had much better guarantees to generate a good speedup. So I >chose that route. > >-- >GCP DTS is certainly far better for many reasons. But one advantage it had over the others is that the processors were not "locked together". While I don't use DTS today in Crafty, because the recursive search makes it unbearably complicated to implement, my current search still has this characteristic that you hardly _ever_ find a processor doing nothing.
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.