aloha!
i have a few stupid multithreading questions, since i have a dual core machine now and am starting to get interested...
i seem to have learned that you should have no global variables (except for stuff that you want to share). i also seem to have learned that static variables won't work properly. then there are some things that i don't quite understand about shared data: i would expect that you want to share the hashtable among threads that search the same root position. if this is the case, then i would also expect that you should not access the hashtable simultaneously with multiple threads, because something bad could happen. so i used EnterCriticalSection() and LeaveCriticalSection around my hashtable lookup code, and while that worked, it made my checkers program (i know, i know, the game is solved!) 10 times slower (only when searching two threads parallel, when searching one thread it got slower too, but much less so). so i looked at crafty's source code and could find no attempt to restrict access to the hashtable.
finally, some questions:
does access to the hashtable have to be restricted to one thread? if not, why not?
are the windows functions EnterCriticalSection etc. much slower than the assembly code i saw in crafty's source code?
is there anything (paper, website etc) that describes some fundamentals of multi-threades game playing programs? i found a thread which said that the thesis by valavan manohararajah was a good starting point, so i read it - but i don't think it's a good starting point at all
no pseudocode for the actual splitting operations, no discussion of sharing stuff etc. is there anything else, preferably on a lower level?
cheers
martin
multithreading questions
Moderators: hgm, Rebel, chrisw
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: multithreading questions
Hello Martin!
For pawn hash tables and material hash tables, I use separate tables for each thread.
Tord
Because locking and unlocking are very expensive operations (as you have already noticed yourself), and because the hash table is so big that the probability of two threads writing to the same entry simultaneously is very small. What I (and, I think, most other programmers) do is to let all threads access the hash table freely without any locking, but to always check the hash move for legality before playing it. In theory, I will sometimes still get incorrect hash table cutoffs, but in practice this happens so rarely that it has zero impact on playing strength.Martin Fierz wrote:finally, some questions:
does access to the hashtable have to be restricted to one thread? if not, why not?
For pawn hash tables and material hash tables, I use separate tables for each thread.
I don't know (I don't run Windows), but I doubt that they are sufficiently fast to make locking of the main hash table feasible.are the windows functions EnterCriticalSection etc. much slower than the assembly code i saw in crafty's source code?
Unfortunately, I am not aware of any better starting point than Valavan's thesis. If you want to look at some actual code, I have a lobotomized version of Glaurung 1 named Viper which is supposed to illustrate YBW in simple and straightforward code. It is still too complicated and poorly commented, but perhaps it can still be helpful.is there anything (paper, website etc) that describes some fundamentals of multi-threades game playing programs? i found a thread which said that the thesis by valavan manohararajah was a good starting point, so i read it - but i don't think it's a good starting point at all
no pseudocode for the actual splitting operations, no discussion of sharing stuff etc. is there anything else, preferably on a lower level?
Tord
Re: multithreading questions
Crafty uses a lockless hashing which is discribed on Prof. Hyatt's website.
http://www.cis.uab.edu/hyatt/hashing.html
Maybe this helps to understand what Crafty does. Unfortunately, I didn't have the time yet to read it...
http://www.cis.uab.edu/hyatt/hashing.html
Maybe this helps to understand what Crafty does. Unfortunately, I didn't have the time yet to read it...
-
- Posts: 27822
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: multithreading questions
Well, the idea of lockless hashing is very simple, and based on the philosophy that you don't care so much if a hash entry gets lost, as long as it produces a recognizably invalid hash entry rather than an erroneous one that might send your engine off track.
To this end you XOR all independently stored words of the hash entry together, and store it in stead of the word containing the signature. On probing you have to recover the signature (and whatever other data there might be in this word) by repeating the XOR operation, before you can compare it with your hash key.
If not all words belong to the same entry, (because two threads messed it up by simultaneously trying to store something in the same entry, or one is replacing it while you were reading), you won't recover the original signature word through the XORing, and thus will discard the corrupted entry as a miss.
To this end you XOR all independently stored words of the hash entry together, and store it in stead of the word containing the signature. On probing you have to recover the signature (and whatever other data there might be in this word) by repeating the XOR operation, before you can compare it with your hash key.
If not all words belong to the same entry, (because two threads messed it up by simultaneously trying to store something in the same entry, or one is replacing it while you were reading), you won't recover the original signature word through the XORing, and thus will discard the corrupted entry as a miss.
Re: multithreading questions
That's only partially true. The truth is most chess programs have a lot of globals, mine included. However, most of them don't get modified at all during the search, so I don't worry about them. What you really want to avoid is having a global variable that is written to by multiple threads without using some sort of locking mechanism (mutex, semaphore, etc) to ensure there are no race conditions.Martin Fierz wrote:aloha!
i seem to have learned that you should have no global variables (except for stuff that you want to share).
Here's a classic race condition:
Code: Select all
while (flag==1) {}
flag=1;
<some critical section of code>
flag=0;
You can safely access the hash table in multiple threads, you just have to be careful to do so in a thread safe way. You could use locking mechanisms, or you could just ignore the problem. If you ignore the problem, you run the serious risk of fetching corrupt hash data. But, if you can handle that, it may be a better approach than locking, which can get to be expensive. (Not 10x though!)Martin Fierz wrote: i also seem to have learned that static variables won't work properly. then there are some things that i don't quite understand about shared data: i would expect that you want to share the hashtable among threads that search the same root position. if this is the case, then i would also expect that you should not access the hashtable simultaneously with multiple threads, because something bad could happen.
I recommend you read Hyatt's paper on "Lockless Hashing" from here:
http://www.cis.uab.edu/hyatt/pubs.html .
I have implemented it in Prophet, it's not too bad.
Martin Fierz wrote: so i used EnterCriticalSection() and LeaveCriticalSection around my hashtable lookup code, and while that worked, it made my checkers program (i know, i know, the game is solved!) 10 times slower (only when searching two threads parallel, when searching one thread it got slower too, but much less so). so i looked at crafty's source code and could find no attempt to restrict access to the hashtable.
finally, some questions:
does access to the hashtable have to be restricted to one thread? if not, why not?
are the windows functions EnterCriticalSection etc. much slower than the assembly code i saw in crafty's source code?
is there anything (paper, website etc) that describes some fundamentals of multi-threades game playing programs? i found a thread which said that the thesis by valavan manohararajah was a good starting point, so i read it - but i don't think it's a good starting point at all
no pseudocode for the actual splitting operations, no discussion of sharing stuff etc. is there anything else, preferably on a lower level?
cheers
martin
-
- Posts: 287
- Joined: Sat Mar 11, 2006 3:19 am
- Location: Atlanta, GA
Re: multithreading questions
Yes much slower (atleast 3x slower on my P4) because Critical selection does a spin-wait first then does a slow OS call to block. Crafty's spinning assembly locks are also a tad-bit slower when there is high contention because it does an interlocked exchange first then tests. Here's what I'm using in Buzz:Martin Fierz wrote:are the windows functions EnterCriticalSection etc. much slower than the assembly code i saw in crafty's source code?
Code: Select all
#ifndef INLINE
#ifdef _MSC_VER
#define INLINE __forceinline
#elif defined(__GNUC__)
#define INLINE __inline__ __attribute__((always_inline))
#else
#define INLINE inline
#endif
#endif
#if defined(__GNUC__)
typedef volatile int SpinLock[1];
typedef volatile int* const SpinLock_P;
static INLINE int volatile LockedExchange(SpinLock_P Target, const int Value)
{
int ret = Value;
__asm__
(
"xchgl %[ret], %[Target]"
: [ret] "+r" (ret)
: [Target] "m" (*Target)
: "memory"
);
return ret;
}
#elif defined(_MSC_VER)
typedef volatile long SpinLock[1];
typedef volatile long* const SpinLock_P;
#include <intrin.h>
#pragma intrinsic (_InterlockedExchange)
#define LockedExchange(Target,Value) _InterlockedExchange(Target,Value)
#else
#error Unspported Compiler
#endif
#define IsLocked(s) ((s)[0])
#define SetLocked(s,boolean) ((s)[0]=(boolean))
#define ResetSpinLock(s) SetLocked(s,0)
static INLINE void volatile Release(SpinLock_P s) {SetLocked(s,0);}
static INLINE int volatile TryLock(SpinLock_P s) {return !(IsLocked(s) || LockedExchange(s,1));}
static INLINE void volatile Lock(SpinLock_P s) {while(IsLocked(s) || LockedExchange(s,1));}
http://www.intel.com/cd/ids/developer/a ... 333935.htm
In my opinion, this is the best starting place:is there anything (paper, website etc) that describes some fundamentals of multi-threades game playing programs? i found a thread which said that the thesis by valavan manohararajah was a good starting point, so i read it - but i don't think it's a good starting point at all
http://www.netlib.org/utk/lsi/pcwLSI/text/node351.html
It's slow and boring but for this I read up online on Windows API and POSIX Threads API.no pseudocode for the actual splitting operations, no discussion of sharing stuff etc. is there anything else, preferably on a lower level?
Good luck with your parallel engine.cheers
martin
-
- Posts: 1221
- Joined: Wed Mar 08, 2006 8:28 pm
- Location: Florida, USA
Re: multithreading questions
Martin,
I haven't written a multi-threaded chess program but I have thought of the issue you raise.
This is how I am planning to tackle the problem. Whenever a thread wants to probe or write to a hash entry it first increments a integer (call it "lock") which is part of the hash table entry. The thread then tests to see if lock = 1. If it is true it proceeds to use (i.e. read or write) the hash entry. After it is finished with the hash entry the thread decrements the lock flag. If on initially testing lock, it is > 1 it knows that the entry is being used by another thread and acts accordingly.
Regards,
Steve
I haven't written a multi-threaded chess program but I have thought of the issue you raise.
This is how I am planning to tackle the problem. Whenever a thread wants to probe or write to a hash entry it first increments a integer (call it "lock") which is part of the hash table entry. The thread then tests to see if lock = 1. If it is true it proceeds to use (i.e. read or write) the hash entry. After it is finished with the hash entry the thread decrements the lock flag. If on initially testing lock, it is > 1 it knows that the entry is being used by another thread and acts accordingly.
Regards,
Steve
-
- Posts: 892
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
Re: multithreading questions
Integer flag decrement is not thread safe. If you make it safe it will be very slow.
-
- Posts: 1221
- Joined: Wed Mar 08, 2006 8:28 pm
- Location: Florida, USA
Re: multithreading questions
Aleks,
Steve
I don't know that much about multi-core programming so I'm sure you're right. Nevertheless could you expand upon this? How is it not safe? What would happen if you implemented a raw integer decrement?Aleks Peshkov wrote:Integer flag decrement is not thread safe. If you make it safe it will be very slow.
Steve
-
- Posts: 27822
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: multithreading questions
I also never have done any multi-core programming, but what would be wrong in simply using the inc/dec instruction with a lock prefix (or using xchg, which is always locked)? Being only a single instruction, that cannot be disastrously slow, can it?Aleks Peshkov wrote:Integer flag decrement is not thread safe. If you make it safe it will be very slow.