ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

info about zappa on 512 cores ?
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Daniel Shawul



Joined: 14 Mar 2006
Posts: 2187
Location: Ethiopia
PostPost subject: Re: transposition tables    Posted: Sat Jun 30, 2012 12:40 am Reply to topic Reply with quote
syzygy wrote:
Daniel Shawul wrote:
Give N small hash tables of the same size with K entries, how do you hash a position with zobrist hash hash_key ? Assume the small hash tables are physically separate (on different processor if you will).

If I understand you correctly, the N small hash tables form one large hash table. Each position maps to exactly one entry (or bucket) in this large hash table.

If N = 2^n and K = 2^k, then the large hash table has 2^(n+k) entries (or buckets), so you use n+k bits of the hash key to find this entry of the (fictitious) large hash table. n of those bits determine which of the N small hash tables you use for this position, the other k bits determine the entry within this small hash table.

If N is not a power of two, you could e.g. use the lower k bits to determine the entry (or bucket) within the small hashtable, and take ((hash_key >> k) % N) to find the small hash table.

If K is not a power of two either, you can take (hash_key % K) and ((hash_key / K) % N).

I thought about that but the number of processors is usually not a power of 2. It turns out distributed hash tables have much more important use in web caching and has been researched well. The key elements are decentralization, fault tolerance, and scalability. So I can not make assumptions on the total size of the hash table entries being a power of 2. A client could disconnect at any time and the hash table should keep on working with the remaing tables. When you take these facts into consideration , the method with division and modulo is OK. So each small hash table of equal size with 2^k entries and all N clients total = N * 2^k.
Code:

processor = hash_key % N
hash_key = hash_key / N   /* I think a shift to the right could replace the division here but N is dynamic */
entry = hash_key & (2^k - 1)

_________________
https://sites.google.com/site/dshawul/
https://github.com/dshawul
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
Display posts from previous:   
Subject Author Date/Time
info about zappa on 512 cores ? Daniel Shawul Sat Jun 23, 2012 2:05 pm
      numa scaling Daniel Shawul Sun Jun 24, 2012 10:20 am
            Re: numa scaling Robert Hyatt Sun Jun 24, 2012 5:01 pm
                  Re: numa scaling Daniel Shawul Sun Jun 24, 2012 5:41 pm
                        Re: numa scaling Robert Hyatt Mon Jun 25, 2012 12:37 am
                              Re: numa scaling Daniel Shawul Mon Jun 25, 2012 1:23 am
                                    Re: numa scaling Robert Hyatt Mon Jun 25, 2012 10:05 am
                                          Re: numa scaling Daniel Shawul Mon Jun 25, 2012 4:00 pm
                                                Re: numa scaling Daniel Shawul Mon Jun 25, 2012 5:21 pm
                                                Re: numa scaling Daniel Shawul Mon Jun 25, 2012 8:09 pm
                                                      Re: numa scaling Robert Hyatt Mon Jun 25, 2012 8:38 pm
                                                            Re: numa scaling Daniel Shawul Mon Jun 25, 2012 8:53 pm
                                                                  Re: numa scaling Robert Hyatt Mon Jun 25, 2012 9:17 pm
                                                                        Re: numa scaling Daniel Shawul Mon Jun 25, 2012 9:46 pm
                                                                              Re: numa scaling Robert Hyatt Tue Jun 26, 2012 3:34 am
                                                                                    Re: numa scaling Daniel Shawul Tue Jun 26, 2012 11:06 am
                                                      Re: numa scaling Daniel Shawul Tue Jun 26, 2012 12:55 am
            transposition tables Daniel Shawul Sun Jun 24, 2012 5:53 pm
                  Re: transposition tables Daniel Shawul Wed Jun 27, 2012 11:17 pm
                        Re: transposition tables Ronald de Man Fri Jun 29, 2012 11:47 pm
                              Re: transposition tables Daniel Shawul Sat Jun 30, 2012 12:40 am
      Re: info about zappa on 512 cores ? Vincent Diepeveen Fri Jun 29, 2012 11:07 pm
            Re: info about zappa on 512 cores ? Daniel Shawul Sat Jun 30, 2012 12:32 am
                  Re: info about zappa on 512 cores ? Daniel Shawul Sat Jun 30, 2012 10:50 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads