Author: Bruce Moreland
Date: 01:05:10 05/26/00
Go up one level in this thread
On May 26, 2000 at 03:52:48, Tom Kerrigan wrote: >On May 26, 2000 at 03:47:37, Bruce Moreland wrote: > >>On May 26, 2000 at 02:49:55, Tom Kerrigan wrote: >> >>>I've been writing a multithreaded program. I'm running on 1 processor but my >>>program splits into 4 threads. So far, the threads don't communicate in any way, >>>so searches take exactly 4 times as long (not counting some overhead). >>> >>>But this evening I added a shared hash table, and now the threads=4 program is >>>only slightly slower (in terms of NPS and nodes/ply) than the threads=1 program. >>> >>>Is this some sort of mistake? I tried for almost an hour to prove that something >>>flakey is going on, but it seems to really go 4 times faster, even though the >>>threads don't communicate (except for the hash table). The PVs and scores that >>>the programs spit out are exactly the same, and the threads seem to be sharing >>>the work equally. >>> >>>Could this be some sort of side effect from running on 1 processor? >>> >>>Thanks for any comments. >>> >>>-Tom >> >>This is one way of writing a multiprocessor chess program. Rather than having >>the threads run lock-step, you let them do their own thing, and count on the >>transposition table to save you work. >> >>I tried this and the initial cut was much slower than the lock-step version, so >>it would take some enhancing. I think that the Virtual Chess guys did this >>early on, and I think there's someone else who reads this group who tried >>something similar, if he'd like to come out. >> >>bruce > >I will implement the ABDADA algorithm soon; the paper was published in ICCA at >some point. It looks very clever. The basic idea is to use the hash table to >keep track of which program is searching what, in addition to saving work. It's >not completely trivial to implement, but it's relatively simple compared to >other algorithms I've read about. > >-Tom The algorithm that I use assumes that if a move has been searched in a given position, and the score has not failed high, that this node is going to fail low. If the node is sufficiently distant from the leaves, and there are any idle processors, it will use the idle processors to search subsequent moves. There are some nasty tricks. For instance, if I let someone else search some of my moves for me, then I get done before they do, I've either got to sit there doing nothing or make my processor available to someone else. I can't return alpha since alpha might increase. I solve this by having a bunch of spare tasks sitting around doing nothing, and when I'm idle I just allow one of them to make itself available, and then block until my helper tasks get done. When the last one gets done it will understand that there are too many active processes, and it will take itself out of availability and allow me to run without overcommitting processors. Usually. My program ends up running 5 or 6 active tasks a little bit of the time on a 4-processor machine. This doesn't seem to matter much, in fact for a while my best version had 5 running all the time, because I was so inefficient that there was usually a processor idle anyway. You will have a lot of fun making a multiprocessor program. It isn't particularly hard to do, but debugging can be a joy. bruce
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.