Author |
Topic: Usage of 2, 4, 8 cores? (Read 6936 times) |
|
arimaa_master
Forum Guru
Arimaa player #2010
Gender: 
Posts: 358
|
 |
Usage of 2, 4, 8 cores?
« on: Mar 12th, 2008, 6:19am » |
 Quote  Modify
|
I wonder If the bot_bomb (or others) is capable of using more than one core? I am asking coz I know that it is known issue in computer chess where engines usually come out in two different versions.
The question is in place especially due to running computer championship on dual core (intel core 2 duo).
I suspect that without optimalization for 2+ cores usage every bot is using only one core (or two cores at 50 percent etc.)
Thus it seems useless to have dual core (or quad next year) for this tournament coz it will not gain any more from it.
But I understand that the usefullness is high afterwards (coz after the replacement of main server - it will for sure make full use of all cores).
|
| « Last Edit: Mar 12th, 2008, 6:21am by arimaa_master » |
 IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #1 on: Mar 12th, 2008, 11:06am » |
Quote Modify
|
As far as I know none of the current bots use any form of parallel search.
Janzert
|
|
IP Logged |
|
|
|
arimaa_master
Forum Guru
Arimaa player #2010
Gender:
Posts: 358
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #2 on: Mar 12th, 2008, 3:06pm » |
Quote Modify
|
Thx for the Answer, that Is exactly what I thought.
So parallel search would help very much (if it gains 1.7x speedup, so
it will be 2.89x faster at quad).
I guess the same situation is in 32 bit versus 64 bit.
Isn´t time to use some sort of bitbases to significantly improve bot's play?
|
|
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #3 on: Mar 12th, 2008, 3:43pm » |
Quote Modify
|
on Mar 12th, 2008, 3:06pm, arimaa_master wrote:Thx for the Answer, that Is exactly what I thought.
So parallel search would help very much (if it gains 1.7x speedup, so
it will be 2.89x faster at quad).
|
|
Due to the large branching factor I don't think the added complexity of a multithreaded bot is worth it. It would be the same as having a longer thinking time, and some postal games by bots have shown(If I remember correctly) that the extra time doesn't help very much.
Maybe an obsenely high number of processor(cluster?) could make a difference.
on Mar 12th, 2008, 3:06pm, arimaa_master wrote:
I guess the same situation is in 32 bit versus 64 bit.
|
|
I tested this a while ago, and yes, it is a totally free spees boost. The results and discussions are in: http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display ;num=1129496970;start=15
|
|
IP Logged |
|
|
|
arimaa_master
Forum Guru
Arimaa player #2010
Gender:
Posts: 358
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #4 on: Mar 13th, 2008, 5:33am » |
Quote Modify
|
on Mar 12th, 2008, 3:43pm, nbarriga wrote:
Due to the large branching factor I don't think the added complexity of a multithreaded bot is worth it. It would be the same as having a longer thinking time, and some postal games by bots have shown(If I remember correctly) that the extra time doesn't help very much.
Maybe an obsenely high number of processor(cluster?) could make a difference.
I tested this a while ago, and yes, it is a totally free spees boost. The results and discussions are in: http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display ;num=1129496970;start=15 |
|
Yeah it will be useful then to put paralell bot in some sort of supercomputer and see how much improvement in real play it will show.
And thx for that link to 32bit x 64bit. I didn´t know about it (mainly because this thread started before I joined to the arimaa community  ).
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #5 on: Sep 21st, 2008, 9:36pm » |
Quote Modify
|
I don't know why I didn't notice this thread when it was active, but I asked the same question of Fritz a few weeks ago. He was surprised that Gnobot does not utilize multiple cores, and was pretty certain that bomb does. Jeff also mentioned that clueless does.
The reason I raised the topic was that like arimaa_master, I think it is going to be increasingly important to the bot championship (and eventually the challenge).
One afternoon I tried to parallelize Gnobot. Unfortunately I have much to learn, because while it utilized both cores, it actually slowed down. I was going parallel at the leaf nodes (in the evaluation function), but it seems I need to do it higher up the tree.
Does anyone know an easily implemented parallel search algorithm? Even better, would anyone care to parallelize Don Dailey's sample bot?
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #6 on: Sep 21st, 2008, 9:52pm » |
Quote Modify
|
This is something I'm wanting to get into opfor as well. Last week I took a quick look around the internet for information. While I didn't come up with anything really great the chess programming wiki seems to have a fairly good overview of current common techniques at least.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #7 on: Sep 22nd, 2008, 8:20am » |
Quote Modify
|
Thanks for the link, Janzert. I'm wondering whether sharing a hash table, which can be a huge issue is some applications, is a non-issue here.
Now that I think about it, I don't know how folks deal with running out of hash table space in the first place. Obviously the number of nodes searched is going to exceed the number of hash table slots available at some point. My naive thought was that, since we can't save everything anyway, it doesn't make sense to probe or chain: when there is a collision one should simply overwrite the older information. Is that what people do?
|
| « Last Edit: Sep 22nd, 2008, 8:49am by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #8 on: Sep 22nd, 2008, 10:32am » |
Quote Modify
|
Yes, the number of table entries is almost always quite a bit smaller than the number of nodes actually searched. In order to verify that the information in an entry actually corresponds to the given position being looked up a 64 bit hash is usually used. When storing a position that collides with another position's entry there are a number of different strategies to decide which entry to keep. The most common strategies are always replace, replace if the new entry has been searched to a greater depth or some combination of the two (two separate tables one using each of the above is generally considered one of the best methods).
As far as the hash table use in parallel search in particular in an SMP shared memory computing model (as opposed to say a cluster where the memory access between nodes is orders of magnitude slower then the memory on the node) typically one shared main hash table is used. How access to the table is shared though varies.
The slowest but safest approach is to have a processor lock an entry before reading or writing to it. This prevents one processor from reading data that is in the midst of being written by another processor. But it can be very slow to get a lock even when not needing to wait for another processor to release it.
Another approach is to use "lockless hashing" developed by Robert Hyatt. This takes advantage of certain memory writes and reads being atomic operations in order to catch if the data read is corrupt.
The approach that seems to be gaining the most favor currently though, is to simply almost ignore the problem. Basically just write and read the entries as if there was no parallel access occurring. The reason for the "almost" qualifier though is that before actually using certain parts of the entry it has to be verified that it is actually valid for the current position. Normally this just consists of checking that the stored bestmove is in fact a legal move. The primary downside is that occasionally an incorrect score will be returned from a hash hit, this turns out to not be a problem in practice though. Hyatt and Cozzie did a study showing that getting incorrect data even as much as 1 in every 10000 hash probes is unlikely to cause a problem.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #9 on: Sep 22nd, 2008, 7:41pm » |
Quote Modify
|
Thanks for the clear explanation, Janzert. You are generous and patient.
It finally sunk in with me that there are two types of collisions, the rare collisions when two different positions have the same key, and the common collisions when two different keys want to occupy the same space in memory. The common one is no problem, if you can detect a corrupt read, or do hashing with no locks. (Actually, I had already heard of non-blocking hash tables, although I didn't quite get the point.)
It's clever to detect the collision of identical keys via a legal move check, but for the ones that get through, I'm surprised that using the wrong information isn't more catastrophic.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #10 on: Sep 22nd, 2008, 11:23pm » |
Quote Modify
|
Hmm, actually I wasn't completely clear. There are really 3 types of collisions in what I mentioned.
First up is the situation where two different positions hash to the same 64 bit value. This type of collision is of course very rare, barring bugs or improper hash method. In fact they are rare enough that trying to deal with or detect them is usually simply ignored. The next collision type is when two different positions want to occupy the same slot (or entry) in the hash table. Since the space available in the hash table is usually smaller than the number of positions examined in a search these collisions are a common occurance and one of the methods I mentioned in the first paragraph of my last post are used to deal with them. These first two collision types are inherent in normal hash table operation (whether used in parallel or not).
The third collision type doesn't really have anything to do with hash tables in particular and everything to do with parallel use of the data. Since in general there is no guarantee that another processor won't overwrite the data you are trying to read (or write) while you are in the middle of doing it you have to either prevent concurrent access (locks), detect it (lockless hashing) or be able to deal with any corrupt data you get.
And yes it is pretty amazing how resilient alpha-beta search is when simply given the corrupt data. The results given in the Hyatt, Cozzie paper are certainly something I would never have expected.
Janzert
p.s. I should qualify that all of my comments here are meant to apply to hash tables as used by in game search programs not the general computer science hash table (or hash map) data structure. While they have much the same basic operation there are significant differences. Not the least of which is they are generally meant to expand and hold whatever data is put in them, not 'arbitrarily' decide which pieces to throw away that won't fit. 
|
| « Last Edit: Sep 22nd, 2008, 11:31pm by Janzert » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #11 on: Sep 23rd, 2008, 7:05am » |
Quote Modify
|
on Sep 22nd, 2008, 11:23pm, Janzert wrote:| The third collision type doesn't really have anything to do with hash tables in particular and everything to do with parallel use of the data. Since in general there is no guarantee that another processor won't overwrite the data you are trying to read (or write) while you are in the middle of doing it you have to either prevent concurrent access (locks), detect it (lockless hashing) or be able to deal with any corrupt data you get. |
|
Maybe I am not understanding, but this third type of collision seems like a subset of two different keys wanting the same space in memory. If instead a read thread and a write thread have the same key, the write thread is presumably writing the same data that the read thread is trying to read, so it doesn't matter whether the reader or writer goes first.
Now if the keys are different, and the reading thread has "verified" that the memory space has the correct key, but reads a wrong value for that key because a different thread has over-written the value belonging to a different key, this behaves like a key collision, right? The two different values didn't actually have the same key, but to the reader it appears they did. So dealing with it in the same way as a key collision makes sense, no?
Perhaps I don't get what is happening at a low level, and what corrupt data means in this context.
Thanks again for explaining.
|
| « Last Edit: Sep 23rd, 2008, 7:08am by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #12 on: Sep 23rd, 2008, 3:49pm » |
Quote Modify
|
Hmm, I hadn't thought of it in that way before but you are correct the effects of key collisions and access collisions are very similar. Thinking about it for a bit I think the results from access collisions are a superset of the results from key collisions. The difference being that the result from a key collision will always be a valid entry just data for the wrong position. Results from an access collision can be essentially any random combination of words from two or more separate position entries (although the most likely occurrence is for the first part to be one entry and the last another with the split at some random word). So yes looking at the effects of both are going to be pretty much the same in any one instance. The differences come when looking at what situations they occur in and how to prevent them from happening.
Key collisions can't actually be prevented but they can be made to occur as infrequently as desired (at the cost of larger hash key size). Access collisions can of course be prevented (locks) or detected (lockless hashing) if desired.
A key collision will occur between two essentially random positions but will always occur for those two positions. An access collision will occur at basically random times between random positions. It's because of this that I think key collisions would cause a larger problem in a search than access collisions (i.e. consistently getting the wrong answer for one specific position out of a thousand is probably worse than getting the wrong answer randomly one time out of a thousand).
Janzert
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #13 on: Sep 23rd, 2008, 4:10pm » |
Quote Modify
|
on Sep 23rd, 2008, 7:05am, Fritzlein wrote:
Maybe I am not understanding, but this third type of collision seems like a subset of two different keys wanting the same space in memory. If instead a read thread and a write thread have the same key, the write thread is presumably writing the same data that the read thread is trying to read, so it doesn't matter whether the reader or writer goes first. |
|
I don't really understand Janzert's answer, so I'll have a quick shot at this comment. When the key is the same, it's not necessarily writing the same data that the read thread is trying to read. For example, you may have searched the same position to a different depth, and want to record the new deeper evaluation.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Usage of 2, 4, 8 cores?
« Reply #14 on: Sep 23rd, 2008, 5:12pm » |
Quote Modify
|
Oops thanks 99of9, I forgot to explain that part explicitly. Maybe expanding your example out step by step will make the it clearer what exactly can happen.
Say we have a program running with multiple threads and a shared hash table with no locking. Amazingly the computer it's running on uses regular english alpha-numerics as its internal storage and has a word size of a single letter. The hash table currently has an entry for position A that looks like this:
Code:Hash key |depth|score|best step
positionA|00007|+0120|Ca5n |
|
Thread 1 is about to search position A to a depth of 8 and wants to check the hash table to make sure this hasn't already been done or barring that if there was any previous search to a lesser depth what the best step to try first is.
Thread 2 has just finished a search on position A to a depth of 8 and is ready to write the results back to the hash table.
As luck would have it Thread 2 starts writing first, the entry it is writing looks like this:
Code:Hash key |depth|score|best step
positionA|00008|-0010|Ca5s |
|
Unfortunately after having written 2/3rds of the entry Thread 1 reads the entire entry. The entry Thread 1 sees is this:
Code:Hash key |depth|score|best step
positionA|00008|-0120|Ca5n |
|
Oops, Thread 1 will now not search position A but simply return that its score is -120, a score that it has never actually had.
Hopefully that helps clear up some of the mechanics of what can happen.
Janzert
|
| « Last Edit: Sep 23rd, 2008, 5:12pm by Janzert » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print