25,161
edits
Changes
Created page with "'''Home * Programming * Data * Hash Table * Shared Hash Table''' FILE:An illustration of the dining philosophers problem.png|border|right|thumb|Di..."
'''[[Main Page|Home]] * [[Programming]] * [[Data]] * [[Hash Table]] * Shared Hash Table'''
[[FILE:An illustration of the dining philosophers problem.png|border|right|thumb|Dining philosophers problem <ref>[https://en.wikipedia.org/wiki/Dining_philosophers_problem Dining philosophers problem from Wikipedia]</ref> ]]
'''Shared Hash Table''',<br/>
a Hash table or [[Transposition Table|Transposition table]] which is accessed by various [[Process|processes]] or [[Thread|threads]] simultaneously, running on [https://en.wikipedia.org/wiki/Multiprocessing multiple processors] or [https://en.wikipedia.org/wiki/Multi-core_processor processor cores]. Shared hash tables are most often implemented as dynamically allocated [[Memory|memory]] treated as global [[Array|array]]. Due to [https://en.wikipedia.org/wiki/Memory_protection memory protection] between processes, they require an [https://en.wikipedia.org/wiki/Application_programming_interface Application programming interface] provided by the [https://en.wikipedia.org/wiki/Operating_system operating system] to allocate [https://en.wikipedia.org/wiki/Shared_memory shared memory]. Threads may share global memory from the process they are belonging to.
=Parallel Search=
Almost all [[Parallel Search|parallel search]] algorithms on [[SMP]]- or [[NUMA]] systems profit from probing hash entries written by other instances of the search, in its most simple form by instances of a sequential search algorithm which simultaneously search the same root position. The gains come from the effect of nondeterminism. Each processor will finish the various subtrees in varying amounts of time, and as the search continues, these effects grow making the search trees diverge. The [https://en.wikipedia.org/wiki/Speedup speedup] is then based on how many nodes the main processor is able to skip from transposition table entries. It had the reputation of little speedup on a mere 2 processors, and to scale quite badly after this. However, the [[Nodes per second|NPS]] scaling is nearly perfect.
==ABDADA==
''see Main page: [[ABDADA]]''
[[ABDADA]], Alpha-Bêta Distribué avec Droit d'Anesse (Distributed Alpha-Beta Search with Eldest Son Right) is a loosely synchronized, distributed search algorithm by [[Jean-Christophe Weill]] <ref>[[Jean-Christophe Weill]] ('''1996'''). ''The ABDADA Distributed Minimax Search Agorithm''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped postscript]</ref> . It is based on the [[Shared Hash Table]], and adds the number of processors searching this node inside the hash-table entry for better utilization - considering the [[Young Brothers Wait Concept]].
==Lazy SMP==
''see Main page: [[Lazy SMP]]''
Recent improvements by [[Dan Homan]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013</ref>, [[Martin Sedlak]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55188 Lazy SMP in Cheng] by [[Martin Sedlak]], [[CCC]], February 02, 2015</ref> and others on '''Lazy''' SMP indicate that the algorithm scales quite well up to 8 cores and beyond <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55170&start=11 Re: A new chess engine : m8 (comming not so soon)] by [[Peter Österlund]], [[CCC]], February 01, 2015</ref>.
=Concurrent Access=
Due to its size, i.e. 16 or more bytes, writing and reading hash entries are none [https://en.wikipedia.org/wiki/Linearizability atomic] and require multiple write- and read-cycles. It may and will happen that [https://en.wikipedia.org/wiki/Concurrency_%28computer_science%29 concurrent] writes and reads at the same table address and almost same time results in corrupt data retrieved that causes significant problems to the search. [https://en.wikipedia.org/wiki/Interrupt Interrupts] may occur between accesses, and there are further nondeterministic issues involved <ref>[https://en.wikipedia.org/wiki/Memory_disambiguation Memory disambiguation from Wikipedia]</ref> which may cause one thread to read two or more atomic data items, which were written by different threads, searching different positions with the same hash-index due to [[Transposition Table#IndexCollisions|type-2]] errors.
==Locks==
One common solution to avoid such errors is [https://en.wikipedia.org/wiki/Synchronization_%28computer_science%29 synchronization] using [https://en.wikipedia.org/wiki/Lock_%28computer_science%29 atomic locks], and to implement a [https://en.wikipedia.org/wiki/Critical_section critical section] or [https://en.wikipedia.org/wiki/Mutual_exclusion mutual exclusion].
===Cilkchess===
As an example, [[Cilkchess]] used [[Cilk|Cilk's]] support for atomicity <ref>[[Don Dailey]], [[Charles Leiserson|Charles E. Leiserson]] ('''2001'''). ''Using Cilk to Write Multiprocessor Chess Programs''. [[Advances in Computer Games 9]], [http://supertech.csail.mit.edu/papers/icca99.pdf pdf], 5 Other parallel programming issues, Cilk support for atomicity, pp. 17-18</ref>. It uses one lock per hash entry:
<pre>
typedef struct
{
Cilk_lockvar lock;
U64 key;
U64 data;
} ttentry;
ttentry hashtable[TABLESIZE];
void ttinit ( ) {
for (int i = 0; i < TABLESIZE; ++i)
Cilk_lock_init( hashtable[i].lock);
}
void update_entry ( ttentry *e, U64 key, U64 data ) {
Cilk_lock (e->lock); /* begin critical section */
e->key = key;
e->data = data;
...
Cilk_unlock (e->lock); /* end critical section */
}
</pre>
===Granularity===
An important property of a lock is its [https://en.wikipedia.org/wiki/Lock_%28computer_science%29#Granularity granularity], which is a measure of the amount of data the lock is protecting. In general, choosing a coarse granularity (a small number of locks, each protecting a large segment of data) results in less lock overhead when a single process is accessing the protected data, but worse performance when multiple processes are running concurrently. This is because of increased lock contention. The more coarse the lock, the higher the likelihood that the lock will stop an unrelated process from proceeding, i.e. in the extreme case, one lock for the whole table. Conversely, using a fine granularity (a larger number of locks, each protecting a fairly small amount of data), like in the Cilkchess sample above, increases the overhead of the locks themselves but reduces lock contention. For a huge transposition table with millions of fairly small entries locks incur a significant performance penalty on many architectures.
<span id="Lockless"></span>
==Lock-less==
===Xor===
[[Robert Hyatt]] and [[Tim Mann]] proposed a lock-less transposition table implementation <ref>[[Robert Hyatt]], [[Tim Mann]] ('''2002'''). ''[http://www.craftychess.com/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]]</ref> for 128 bit entries with two atomic [[Quad Word|quad words]], one qword for storing the key or signature, the 64-bit [[Zobrist Hashing|Zobrist-]] or [[BCH Hashing|BCH-key]] of the position, and one qword for the other information stored, [[Hash Move|move]], [[Score|score]], [[Depth|draft]] and that like (data). Rather than to store two disjoint items, the key is stored [[General Setwise Operations#ExclusiveOr|xored]] with data, while data is stored additionally as usual. According to Robert Hyatt, the original idea came from [[Harry Nelson]] somewhere in 1990-1992 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=531603&t=49099 Re: Lockless hash: Thank you Bob Hyatt!] by [[Robert Hyatt]], [[CCC]], August 26, 2013</ref>.
<pre>
index = key % TABLESIZE;
hashtable[index].key = key ^ data;
hashtable[index].data = data;
</pre>
Since the retrieving position requires the same key for a probing hit, the stored key xored by the retrieved key must match the stored data.
<pre>
index = key % TABLESIZE;
if (( hashtable[index].key ^ hashtable[index].data) == key )
{
/* entry matches key */
}
</pre>
If key and data were written simultaneously by different search instances with different keys, the error will usually yield in a mismatch of the comparison, except the rare but inherent [[Transposition Table#KeyCollisions|Key collisions]] or type-1 errors <ref>[[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.craftychess.com/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]</ref>. As pointed out by [[Harm Geert Muller]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=393348&t=37976 Re: lockless hashing] by [[Harm Geert Muller|H.G.Muller]], [[CCC]], February 07, 2011</ref>, the XOR technique might be applied for any size.
===Checksum===
For a lock-less shared Hash table with (much) larger entry sizes such as the [[Pawn Hash Table]], one may store an additional [https://en.wikipedia.org/wiki/Checksum checksum] of the data, to likely detect errors after retrieving, and to safe the consistence of an entry.
===SSE2===
[[x86]] and [[x86-64]] [[SSE2]] 128-bit read/write instructions might in practice [https://en.wikipedia.org/wiki/Linearizability atomic], but they are not guaranteed even if properly aligned <ref>[https://groups.google.com/d/msg/lock-free/hXtlgYrJj7M/j5mTHsaWYo0J Re: Effectively atomic read of 16 bytes on x86_64 without cmpxchg16b?] by [http://stackoverflow.com/users/5597/anthony-williams Anthony Williams], [https://groups.google.com/forum/#!forum/lock-free groups.google.lock-free], February 08, 2012</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46346&start=44 Re: Speaking of the hash table] by [[Ronald de Man]], [[CCC]], December 10, 2012</ref>. If the processor implements a 16-byte store instruction internally as 2 8-byte stores in the store pipeline, it's perfectly possible for another processor to "steal" the cache line in between the two stores <ref>[http://stackoverflow.com/questions/7646018/sse-instructions-single-memory-access SSE instructions: single memory access] by Atom, [http://de.wikipedia.org/wiki/Stack_Overflow_%28Website%29 Stack overflow], October 04, 2011</ref>. However, [[Intel]] states any locked instruction (either the XCHG instruction or another read-modify-write instruction with a [https://en.wikipedia.org/wiki/Fetch-and-add#x86_implementation LOCK prefix]) appears to execute as an indivisible and uninterruptible sequence of load(s) followed by store(s) regardless of alignment <ref>[http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3a-part-1-manual.html Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3A], section 8.2.3.1.</ref> <ref> [https://en.wikipedia.org/wiki/Fetch-and-add Fetch-and-add from Wikipedia]</ref>.
=Allocation=
Multiple threads inside one process can share its [https://en.wikipedia.org/wiki/Global_variable global variables] or heap. Processes require special [https://en.wikipedia.org/wiki/Application_programming_interface API] calls to create shared memory and to pass a handle to other processes around for [https://en.wikipedia.org/wiki/Inter-process_communication interprocess communication]. [https://en.wikipedia.org/wiki/POSIX POSIX] provides a standardized API for using shared memory <ref>[http://pubs.opengroup.org/onlinepubs/007908799/xsh/shm_open.html shm_open], [https://en.wikipedia.org/wiki/Single_UNIX_Specification#1997:_Single_UNIX_Specification_version_2 The Single UNIX Specification version 2], Copyright © 1997 [https://en.wikipedia.org/wiki/The_Open_Group The Open Group]</ref> . [[Linux]] kernel builds since 2.6 offer /dev/shm as shared memory in the form of a [https://en.wikipedia.org/wiki/RAM_disk RAM disk].
=See also=
* [[ABDADA]]
* [[AVX]]
* [[Cilk]]
* [[Lazy SMP]]
* [[Linux]]
* [[Memory]]
* [[Parallel Search]]
* [[SMP Engines]]
* [[SSE2]]
* [[Transposition Table]]
* [[Unix]]
* [[Windows]]
* [[XOP]]
=Publications=
<ref>[http://www.research.ibm.com/people/m/michael/pubs.htm Maged Michael - Selected Publications]</ref>
==1980 ...==
* [[Clyde Kruskal]], [http://necsi.edu/faculty/rudolph.html Larry Rudolph], [http://cs.illinois.edu/people/faculty/marc-snir Marc Snir] ('''1988'''). ''Efficient Synchronization on Multiprocessors with Shared Memory''. [[ACM#TOPLAS|ACM TOPLAS]], Vol. 10
* [[Henri Bal]] ('''1989'''). ''[http://dare.ubvu.vu.nl/handle/1871/12760?mode=full&submit_simple=Show+full+item+record The shared data-object model as a paradigm for programming distributed systems]''. Ph.D. thesis, [https://en.wikipedia.org/wiki/Vrije_Universiteit Vrije Universiteit]
==1990 ...==
* [http://www.cs.brown.edu/~mph/ Maurice Herlihy] ('''1991'''). ''Wait-free synchronization''. [https://en.wikipedia.org/wiki/ACM_Transactions_on_Programming_Languages_and_Systems ACM Transactions on Programming Languages and Systems] Vol. 13 No. 1, [http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf pdf]
* [[Vincent David]] ('''1993'''). ''[http://cat.inist.fr/?aModele=afficheN&cpsidt=161774 Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint. Etude et application au Minimax]'' = Parallel algorithm for heuristic tree searching and real-time reasoning. Study and application to the Minimax, Ph.D. Thesis, [https://en.wikipedia.org/wiki/%C3%89cole_nationale_sup%C3%A9rieure_de_l%27a%C3%A9ronautique_et_de_l%27espace École nationale supérieure de l'aéronautique et de l'espace], [https://en.wikipedia.org/wiki/Toulouse Toulouse], [https://en.wikipedia.org/wiki/France France]
: '''Abstract''': ''The method of parallelization is based on a suppression of control between the search processes, in favor of a speculative parallelism and full sharing of information achieved through a physically distributed but virtually shared memory. The contribution of our approach for real-time distributed systems and fault-tolerant is evaluated through experimental results''.
* [http://www.research.ibm.com/people/m/michael/ Maged M. Michael], [http://www.cs.rochester.edu/%7Escott/ Michael L. Scott] ('''1995'''). ''Implementation of Atomic Primitives on Distributed Shared Memory Multiprocessors''. [http://www-2.cs.cmu.edu/%7Escandal/conf/pro-HPCA-950122.txt HPCA'95], [http://www.research.ibm.com/people/m/michael/hpca-1995.pdf pdf]
* [[Paul Lu]] ('''1997'''). ''Aurora: Scoped Behaviour for Per-Context Optimized Distributed Data Sharing''. 11th International Parallel Processing Symposium (IPPS) <ref>[http://webdocs.cs.ualberta.ca/~paullu/Aurora/aurora.html The Aurora Distributed Shared Data System]</ref>
* [[John Romein]], [[Aske Plaat]], [[Henri Bal]], [[Jonathan Schaeffer]] ('''1999'''). ''Transposition Table Driven Work Scheduling in Distributed Search''. [[AAAI|AAAI-99]], [https://www.aaai.org/Papers/AAAI/1999/AAAI99-103.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57343&start=5 Re: scorpio can run on 8192 cores] by [[Daniel Shawul]], [[CCC]], August 29, 2015</ref> <ref>[https://en.wikipedia.org/wiki/Transposition-driven_scheduling Transposition-driven scheduling - Wikipedia]</ref>
==2000 ...==
* [[Paul Lu]] ('''2000'''). ''[http://webdocs.cs.ualberta.ca/~paullu/PhDThesis/thesis.html Scoped Behaviour for Optimized Distributed Data Sharing]''. Ph.D. thesis, [[University of Toronto]]
* [[Valavan Manohararajah]] ('''2001''') ''Parallel Alpha-Beta Search on Shared Memory Multiprocessors''. Masters Thesis, [http://www.valavan.net/mthesis.pdf pdf]
* [[John Romein]], [[Henri Bal]], [[Jonathan Schaeffer]], [[Aske Plaat]] ('''2002'''). ''A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search''. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459. [http://www.cs.vu.nl/~bal/Papers/tds.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47700 Transposition driven scheduling] by [[Daniel Shawul]], [[CCC]], April 04, 2013</ref>
* [http://www.research.ibm.com/people/m/michael/ Maged M. Michael] ('''2002'''). ''High Performance Dynamic Lock-Free Hash Tables and List-Based Sets''. [https://en.wikipedia.org/wiki/Thomas_J._Watson_Research_Center IBM Thomas J. Watson Research Center], [http://www.research.ibm.com/people/m/michael/spaa-2002.pdf pdf]
* [[Robert Hyatt]], [[Tim Mann]] ('''2002'''). ''[http://www.craftychess.com/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]]
* [http://www.fi.muni.cz/%7Exbarnat/ Jiří Barnat], [http://www.behindkde.org/node/625 Petr Ročkai] ('''2007'''). ''Shared Hash Tables in Parallel Model Checking''. Faculty of Informatics, [https://en.wikipedia.org/wiki/Masaryk_University Masaryk University], [https://en.wikipedia.org/wiki/Brno Brno], [https://en.wikipedia.org/wiki/Czech_Republic Czech Republic], PDMC 2007, Preliminary Version as [http://anna.fi.muni.cz/papers/src/public/168699cd5787307ee3c8c1a509327e6f.pdf pdf]
* [http://www.cs.rice.edu/%7Evs3/home/Vivek_Sarkar.html Vivek Sarkar] ('''2008'''). ''Shared-Memory Parallel Programming with OpenMP''. [https://en.wikipedia.org/wiki/Rice_University Rice University], [http://www.cs.rice.edu/%7Evs3/comp422/lecture-notes/comp422-lec7-s08-v1.pdf slides as pdf]
* [http://offcode.fi/ Jouni Leppäjärvi] ('''2008'''). ''A pragmatic, historically oriented survey on the universality of synchronization primitives''. [http://www.oamk.fi/~joleppaj/personal/jleppaja_gradu_080511.pdf pdf]
==2010 ...==
* [http://www.vf.utwente.nl/%7Elaarman/ Alfons Laarman], [http://wwwhome.ewi.utwente.nl/%7Evdpol/ Jaco van de Pol], [http://wwwhome.cs.utwente.nl/%7Emichaelw/ Michael Weber] ('''2010'''). ''[http://doc.utwente.nl/73119/ Boosting Multi-Core Reachability Performance with Shared Hash Tables]''. Formal Methods and Tools, [https://en.wikipedia.org/wiki/University_of_Twente University of Twente], [https://en.wikipedia.org/wiki/Netherlands The Netherlands], [http://fmcad10.iaik.tugraz.at/Papers/papers/12Session11/033Laarman.pdf pdf]
* [http://www.cs.rice.edu/%7Ejohnmc/ John Mellor-Crummey] ('''2011'''). ''Shared-memory Parallel Programming with Cilk''. [https://en.wikipedia.org/wiki/Rice_University Rice University], [http://www.clear.rice.edu/comp422/lecture-notes/comp422-2011-Lecture4-Cilk.pdf slides as pdf] » [[Cilk]]
* [http://stackoverflow.com/users/5597/anthony-williams Anthony Williams] ('''2012'''). ''[http://www.cplusplusconcurrencyinaction.com/ C++ Concurrency in Action: Practical Multithreading]''. <ref>[http://scottmeyers.blogspot.co.uk/2012/04/information-on-c11-memory-model.html Information on the C++11 Memory Model] by [https://en.wikipedia.org/wiki/Scott_Meyers Scott Meyers], April 24, 2012</ref>
=Forum Posts=
==1997 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/Wl7A-v-gWYQ/QLuvAp0l4_gJ Parallel searching] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], March 22, 1997 » [[KnightCap]]
* [https://www.stmintz.com/ccc/index.php?id=41708 CilkChess question for Don] by [[Robert Hyatt]], [[CCC]], January 31, 1999 » [[CilkChess]]
==2000 ...==
* [https://groups.google.com/group/comp.lang.asm.x86/browse_frm/thread/ab55c5d57a3a1fd1 Re: Atomic write of 64 bits] by [[Frans Morsch]], [https://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], September 25, 2000
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=15662 multithreading questions] by [[Martin Fierz]], [[CCC]], August 08, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=19446 If making an SMP engine, do NOT use processes] by [[Zach Wegner]], [[CCC]], February 07, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=22398 threads vs processes] by [[Robert Hyatt]], [[CCC]], July 16, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=22799 threads vs processes again] by [[Robert Hyatt]], [[CCC]], August 05, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=26208 SMP hashing problem] by [[Robert Hyatt]], [[CCC]], January 24, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=26223 Interlock clusters] by [[Steven Edwards]], [[CCC]], January 25, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=37976 lockless hashing] by [[Daniel Shawul]], [[CCC]], February 07, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38411 On parallelization] by [[Onno Garms]], [[CCC]], March 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=42833 cache alignment of tt] by [[Daniel Shawul]], [[CCC]], March 11, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46346 Speaking of the hash table] by [[Ed Schroder]], [[CCC]], December 09, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46597 Lazy SMP] by [[Julien Marcel]], [[CCC]], December 27, 2012 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013
* [http://www.open-chess.org/viewtopic.php?f=5&t=2262 Multi-threaded memory access] by [[Vadim Demichev|ThinkingALot]], [[Computer Chess Forums|OpenChess Forum]], February 10, 2013 » [[Memory]], [[Thread]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47455 Lazy SMP, part 3] by [[Dan Homan|Daniel Homan]], [[CCC]], March 09, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47568 Shared hash table smp result] by [[Daniel Shawul]], [[CCC]], March 21, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47700 Transposition driven scheduling] by [[Daniel Shawul]], [[CCC]], April 04, 2013 <ref>[[John Romein]], [[Henri Bal]], [[Jonathan Schaeffer]], [[Aske Plaat]] ('''2002'''). ''A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search''. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459. [http://www.cs.vu.nl/~bal/Papers/tds.pdf pdf]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Dan Homan]], [[CCC]], July 03, 2013 » [[EXchess#LazySMP|Lazy SMP]] in [[EXChess]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49099 Lockless hash: Thank you Bob Hyatt!] by [[Julien Marcel]], [[CCC]], August 25, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50388 How could a compiler break the lockless hashing method?] by [[Rein Halbersma]], [[CCC]], December 08, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=51755 Parallel Search with Transposition Table] by [[Daylen Yang]], [[CCC]], March 27, 2014 » [[Parallel Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54666 Two hash functions for distributed transposition table] by [[Daniel Shawul]], [[CCC]], December 16, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55188 Lazy SMP in Cheng] by [[Martin Sedlak]], [[CCC]], February 02, 2015 » [[Cheng]]
* [http://www.talkchess.com/forum/viewtopic.php?t=55970 Trying to improve lazy smp] by [[Daniel José Queraltó]], [[CCC]], April 11, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57572 lazy smp questions] by Lucas Braesch, [[CCC]], September 09, 2015 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57634 atomic TT] by Lucas Braesch, [[CCC]], September 13, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58645 lazy smp questions] by [[Marco Belli]], [[CCC]], December 21, 2015 » [[Lazy SMP]]
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=58830 NUMA 101] by [[Robert Hyatt]], [[CCC]], January 07, 2016 » [[NUMA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59389 Lazy SMP - how it works] by Kalyankumar Ramaseshan, [[CCC]], February 29, 2016 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60122 lockless hashing] by Lucas Braesch, [[CCC]], May 10, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61472 What do you do with NUMA?] by [[Matthew Lai]], [[CCC]], September 19, 2016 » [[NUMA]]
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=65134 Question about parallel search and race conditions] by [[Michael Sherwin]], [[CCC]], September 11, 2017 » [[Parallel Search]]
=External Links=
==Shared Memory==
{{Shared Memory}}
==Cache==
{{Cache}}
==Concurrency and Synchronization==
{{Synchronization}}
==Distributed memory==
* [https://en.wikipedia.org/wiki/Distributed_memory Distributed memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Distributed_hash_table Distributed hash table from Wikipedia]
: [https://en.wikipedia.org/wiki/Koorde Koorde] based on [https://en.wikipedia.org/wiki/Chord_%28peer-to-peer%29 Chord] and [[De Bruijn sequence]]
* [https://en.wikipedia.org/wiki/Transposition-driven_scheduling Transposition-driven scheduling - Wikipedia]
* [http://webdocs.cs.ualberta.ca/~paullu/Aurora/aurora.html The Aurora Distributed Shared Data System] by [[Paul Lu]]
==Misc==
* [https://en.wikipedia.org/wiki/Cilk Cilk from Wikipedia] » [[Cilk]]
* [http://supertech.csail.mit.edu/cilk/ The Cilk Project] from [[Massachusetts Institute of Technology|MIT]]
* [https://en.wikipedia.org/wiki/Fetch-and-add Fetch-and-add from Wikipedia]
* [https://en.wikipedia.org/wiki/Intel_Cilk_Plus Intel Cilk Plus from Wikipedia]
* [https://en.wikipedia.org/wiki/XMTC XMTC from Wikipedia]
* [[Videos#IanCarr|Ian Carr]] with [https://en.wikipedia.org/wiki/Nucleus_%28band%29 Nucleus] - Solar Plexus 1971, feat. [[Videos#KarlJenkins|Karl Jenkins]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=gHwuo1eGouw|alignment=left|valignment=top}}
=References=
<references />
'''[[Hash Table|Up one Level]]'''
[[FILE:An illustration of the dining philosophers problem.png|border|right|thumb|Dining philosophers problem <ref>[https://en.wikipedia.org/wiki/Dining_philosophers_problem Dining philosophers problem from Wikipedia]</ref> ]]
'''Shared Hash Table''',<br/>
a Hash table or [[Transposition Table|Transposition table]] which is accessed by various [[Process|processes]] or [[Thread|threads]] simultaneously, running on [https://en.wikipedia.org/wiki/Multiprocessing multiple processors] or [https://en.wikipedia.org/wiki/Multi-core_processor processor cores]. Shared hash tables are most often implemented as dynamically allocated [[Memory|memory]] treated as global [[Array|array]]. Due to [https://en.wikipedia.org/wiki/Memory_protection memory protection] between processes, they require an [https://en.wikipedia.org/wiki/Application_programming_interface Application programming interface] provided by the [https://en.wikipedia.org/wiki/Operating_system operating system] to allocate [https://en.wikipedia.org/wiki/Shared_memory shared memory]. Threads may share global memory from the process they are belonging to.
=Parallel Search=
Almost all [[Parallel Search|parallel search]] algorithms on [[SMP]]- or [[NUMA]] systems profit from probing hash entries written by other instances of the search, in its most simple form by instances of a sequential search algorithm which simultaneously search the same root position. The gains come from the effect of nondeterminism. Each processor will finish the various subtrees in varying amounts of time, and as the search continues, these effects grow making the search trees diverge. The [https://en.wikipedia.org/wiki/Speedup speedup] is then based on how many nodes the main processor is able to skip from transposition table entries. It had the reputation of little speedup on a mere 2 processors, and to scale quite badly after this. However, the [[Nodes per second|NPS]] scaling is nearly perfect.
==ABDADA==
''see Main page: [[ABDADA]]''
[[ABDADA]], Alpha-Bêta Distribué avec Droit d'Anesse (Distributed Alpha-Beta Search with Eldest Son Right) is a loosely synchronized, distributed search algorithm by [[Jean-Christophe Weill]] <ref>[[Jean-Christophe Weill]] ('''1996'''). ''The ABDADA Distributed Minimax Search Agorithm''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped postscript]</ref> . It is based on the [[Shared Hash Table]], and adds the number of processors searching this node inside the hash-table entry for better utilization - considering the [[Young Brothers Wait Concept]].
==Lazy SMP==
''see Main page: [[Lazy SMP]]''
Recent improvements by [[Dan Homan]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013</ref>, [[Martin Sedlak]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55188 Lazy SMP in Cheng] by [[Martin Sedlak]], [[CCC]], February 02, 2015</ref> and others on '''Lazy''' SMP indicate that the algorithm scales quite well up to 8 cores and beyond <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55170&start=11 Re: A new chess engine : m8 (comming not so soon)] by [[Peter Österlund]], [[CCC]], February 01, 2015</ref>.
=Concurrent Access=
Due to its size, i.e. 16 or more bytes, writing and reading hash entries are none [https://en.wikipedia.org/wiki/Linearizability atomic] and require multiple write- and read-cycles. It may and will happen that [https://en.wikipedia.org/wiki/Concurrency_%28computer_science%29 concurrent] writes and reads at the same table address and almost same time results in corrupt data retrieved that causes significant problems to the search. [https://en.wikipedia.org/wiki/Interrupt Interrupts] may occur between accesses, and there are further nondeterministic issues involved <ref>[https://en.wikipedia.org/wiki/Memory_disambiguation Memory disambiguation from Wikipedia]</ref> which may cause one thread to read two or more atomic data items, which were written by different threads, searching different positions with the same hash-index due to [[Transposition Table#IndexCollisions|type-2]] errors.
==Locks==
One common solution to avoid such errors is [https://en.wikipedia.org/wiki/Synchronization_%28computer_science%29 synchronization] using [https://en.wikipedia.org/wiki/Lock_%28computer_science%29 atomic locks], and to implement a [https://en.wikipedia.org/wiki/Critical_section critical section] or [https://en.wikipedia.org/wiki/Mutual_exclusion mutual exclusion].
===Cilkchess===
As an example, [[Cilkchess]] used [[Cilk|Cilk's]] support for atomicity <ref>[[Don Dailey]], [[Charles Leiserson|Charles E. Leiserson]] ('''2001'''). ''Using Cilk to Write Multiprocessor Chess Programs''. [[Advances in Computer Games 9]], [http://supertech.csail.mit.edu/papers/icca99.pdf pdf], 5 Other parallel programming issues, Cilk support for atomicity, pp. 17-18</ref>. It uses one lock per hash entry:
<pre>
typedef struct
{
Cilk_lockvar lock;
U64 key;
U64 data;
} ttentry;
ttentry hashtable[TABLESIZE];
void ttinit ( ) {
for (int i = 0; i < TABLESIZE; ++i)
Cilk_lock_init( hashtable[i].lock);
}
void update_entry ( ttentry *e, U64 key, U64 data ) {
Cilk_lock (e->lock); /* begin critical section */
e->key = key;
e->data = data;
...
Cilk_unlock (e->lock); /* end critical section */
}
</pre>
===Granularity===
An important property of a lock is its [https://en.wikipedia.org/wiki/Lock_%28computer_science%29#Granularity granularity], which is a measure of the amount of data the lock is protecting. In general, choosing a coarse granularity (a small number of locks, each protecting a large segment of data) results in less lock overhead when a single process is accessing the protected data, but worse performance when multiple processes are running concurrently. This is because of increased lock contention. The more coarse the lock, the higher the likelihood that the lock will stop an unrelated process from proceeding, i.e. in the extreme case, one lock for the whole table. Conversely, using a fine granularity (a larger number of locks, each protecting a fairly small amount of data), like in the Cilkchess sample above, increases the overhead of the locks themselves but reduces lock contention. For a huge transposition table with millions of fairly small entries locks incur a significant performance penalty on many architectures.
<span id="Lockless"></span>
==Lock-less==
===Xor===
[[Robert Hyatt]] and [[Tim Mann]] proposed a lock-less transposition table implementation <ref>[[Robert Hyatt]], [[Tim Mann]] ('''2002'''). ''[http://www.craftychess.com/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]]</ref> for 128 bit entries with two atomic [[Quad Word|quad words]], one qword for storing the key or signature, the 64-bit [[Zobrist Hashing|Zobrist-]] or [[BCH Hashing|BCH-key]] of the position, and one qword for the other information stored, [[Hash Move|move]], [[Score|score]], [[Depth|draft]] and that like (data). Rather than to store two disjoint items, the key is stored [[General Setwise Operations#ExclusiveOr|xored]] with data, while data is stored additionally as usual. According to Robert Hyatt, the original idea came from [[Harry Nelson]] somewhere in 1990-1992 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=531603&t=49099 Re: Lockless hash: Thank you Bob Hyatt!] by [[Robert Hyatt]], [[CCC]], August 26, 2013</ref>.
<pre>
index = key % TABLESIZE;
hashtable[index].key = key ^ data;
hashtable[index].data = data;
</pre>
Since the retrieving position requires the same key for a probing hit, the stored key xored by the retrieved key must match the stored data.
<pre>
index = key % TABLESIZE;
if (( hashtable[index].key ^ hashtable[index].data) == key )
{
/* entry matches key */
}
</pre>
If key and data were written simultaneously by different search instances with different keys, the error will usually yield in a mismatch of the comparison, except the rare but inherent [[Transposition Table#KeyCollisions|Key collisions]] or type-1 errors <ref>[[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.craftychess.com/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]</ref>. As pointed out by [[Harm Geert Muller]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=393348&t=37976 Re: lockless hashing] by [[Harm Geert Muller|H.G.Muller]], [[CCC]], February 07, 2011</ref>, the XOR technique might be applied for any size.
===Checksum===
For a lock-less shared Hash table with (much) larger entry sizes such as the [[Pawn Hash Table]], one may store an additional [https://en.wikipedia.org/wiki/Checksum checksum] of the data, to likely detect errors after retrieving, and to safe the consistence of an entry.
===SSE2===
[[x86]] and [[x86-64]] [[SSE2]] 128-bit read/write instructions might in practice [https://en.wikipedia.org/wiki/Linearizability atomic], but they are not guaranteed even if properly aligned <ref>[https://groups.google.com/d/msg/lock-free/hXtlgYrJj7M/j5mTHsaWYo0J Re: Effectively atomic read of 16 bytes on x86_64 without cmpxchg16b?] by [http://stackoverflow.com/users/5597/anthony-williams Anthony Williams], [https://groups.google.com/forum/#!forum/lock-free groups.google.lock-free], February 08, 2012</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46346&start=44 Re: Speaking of the hash table] by [[Ronald de Man]], [[CCC]], December 10, 2012</ref>. If the processor implements a 16-byte store instruction internally as 2 8-byte stores in the store pipeline, it's perfectly possible for another processor to "steal" the cache line in between the two stores <ref>[http://stackoverflow.com/questions/7646018/sse-instructions-single-memory-access SSE instructions: single memory access] by Atom, [http://de.wikipedia.org/wiki/Stack_Overflow_%28Website%29 Stack overflow], October 04, 2011</ref>. However, [[Intel]] states any locked instruction (either the XCHG instruction or another read-modify-write instruction with a [https://en.wikipedia.org/wiki/Fetch-and-add#x86_implementation LOCK prefix]) appears to execute as an indivisible and uninterruptible sequence of load(s) followed by store(s) regardless of alignment <ref>[http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3a-part-1-manual.html Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3A], section 8.2.3.1.</ref> <ref> [https://en.wikipedia.org/wiki/Fetch-and-add Fetch-and-add from Wikipedia]</ref>.
=Allocation=
Multiple threads inside one process can share its [https://en.wikipedia.org/wiki/Global_variable global variables] or heap. Processes require special [https://en.wikipedia.org/wiki/Application_programming_interface API] calls to create shared memory and to pass a handle to other processes around for [https://en.wikipedia.org/wiki/Inter-process_communication interprocess communication]. [https://en.wikipedia.org/wiki/POSIX POSIX] provides a standardized API for using shared memory <ref>[http://pubs.opengroup.org/onlinepubs/007908799/xsh/shm_open.html shm_open], [https://en.wikipedia.org/wiki/Single_UNIX_Specification#1997:_Single_UNIX_Specification_version_2 The Single UNIX Specification version 2], Copyright © 1997 [https://en.wikipedia.org/wiki/The_Open_Group The Open Group]</ref> . [[Linux]] kernel builds since 2.6 offer /dev/shm as shared memory in the form of a [https://en.wikipedia.org/wiki/RAM_disk RAM disk].
=See also=
* [[ABDADA]]
* [[AVX]]
* [[Cilk]]
* [[Lazy SMP]]
* [[Linux]]
* [[Memory]]
* [[Parallel Search]]
* [[SMP Engines]]
* [[SSE2]]
* [[Transposition Table]]
* [[Unix]]
* [[Windows]]
* [[XOP]]
=Publications=
<ref>[http://www.research.ibm.com/people/m/michael/pubs.htm Maged Michael - Selected Publications]</ref>
==1980 ...==
* [[Clyde Kruskal]], [http://necsi.edu/faculty/rudolph.html Larry Rudolph], [http://cs.illinois.edu/people/faculty/marc-snir Marc Snir] ('''1988'''). ''Efficient Synchronization on Multiprocessors with Shared Memory''. [[ACM#TOPLAS|ACM TOPLAS]], Vol. 10
* [[Henri Bal]] ('''1989'''). ''[http://dare.ubvu.vu.nl/handle/1871/12760?mode=full&submit_simple=Show+full+item+record The shared data-object model as a paradigm for programming distributed systems]''. Ph.D. thesis, [https://en.wikipedia.org/wiki/Vrije_Universiteit Vrije Universiteit]
==1990 ...==
* [http://www.cs.brown.edu/~mph/ Maurice Herlihy] ('''1991'''). ''Wait-free synchronization''. [https://en.wikipedia.org/wiki/ACM_Transactions_on_Programming_Languages_and_Systems ACM Transactions on Programming Languages and Systems] Vol. 13 No. 1, [http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf pdf]
* [[Vincent David]] ('''1993'''). ''[http://cat.inist.fr/?aModele=afficheN&cpsidt=161774 Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint. Etude et application au Minimax]'' = Parallel algorithm for heuristic tree searching and real-time reasoning. Study and application to the Minimax, Ph.D. Thesis, [https://en.wikipedia.org/wiki/%C3%89cole_nationale_sup%C3%A9rieure_de_l%27a%C3%A9ronautique_et_de_l%27espace École nationale supérieure de l'aéronautique et de l'espace], [https://en.wikipedia.org/wiki/Toulouse Toulouse], [https://en.wikipedia.org/wiki/France France]
: '''Abstract''': ''The method of parallelization is based on a suppression of control between the search processes, in favor of a speculative parallelism and full sharing of information achieved through a physically distributed but virtually shared memory. The contribution of our approach for real-time distributed systems and fault-tolerant is evaluated through experimental results''.
* [http://www.research.ibm.com/people/m/michael/ Maged M. Michael], [http://www.cs.rochester.edu/%7Escott/ Michael L. Scott] ('''1995'''). ''Implementation of Atomic Primitives on Distributed Shared Memory Multiprocessors''. [http://www-2.cs.cmu.edu/%7Escandal/conf/pro-HPCA-950122.txt HPCA'95], [http://www.research.ibm.com/people/m/michael/hpca-1995.pdf pdf]
* [[Paul Lu]] ('''1997'''). ''Aurora: Scoped Behaviour for Per-Context Optimized Distributed Data Sharing''. 11th International Parallel Processing Symposium (IPPS) <ref>[http://webdocs.cs.ualberta.ca/~paullu/Aurora/aurora.html The Aurora Distributed Shared Data System]</ref>
* [[John Romein]], [[Aske Plaat]], [[Henri Bal]], [[Jonathan Schaeffer]] ('''1999'''). ''Transposition Table Driven Work Scheduling in Distributed Search''. [[AAAI|AAAI-99]], [https://www.aaai.org/Papers/AAAI/1999/AAAI99-103.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57343&start=5 Re: scorpio can run on 8192 cores] by [[Daniel Shawul]], [[CCC]], August 29, 2015</ref> <ref>[https://en.wikipedia.org/wiki/Transposition-driven_scheduling Transposition-driven scheduling - Wikipedia]</ref>
==2000 ...==
* [[Paul Lu]] ('''2000'''). ''[http://webdocs.cs.ualberta.ca/~paullu/PhDThesis/thesis.html Scoped Behaviour for Optimized Distributed Data Sharing]''. Ph.D. thesis, [[University of Toronto]]
* [[Valavan Manohararajah]] ('''2001''') ''Parallel Alpha-Beta Search on Shared Memory Multiprocessors''. Masters Thesis, [http://www.valavan.net/mthesis.pdf pdf]
* [[John Romein]], [[Henri Bal]], [[Jonathan Schaeffer]], [[Aske Plaat]] ('''2002'''). ''A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search''. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459. [http://www.cs.vu.nl/~bal/Papers/tds.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47700 Transposition driven scheduling] by [[Daniel Shawul]], [[CCC]], April 04, 2013</ref>
* [http://www.research.ibm.com/people/m/michael/ Maged M. Michael] ('''2002'''). ''High Performance Dynamic Lock-Free Hash Tables and List-Based Sets''. [https://en.wikipedia.org/wiki/Thomas_J._Watson_Research_Center IBM Thomas J. Watson Research Center], [http://www.research.ibm.com/people/m/michael/spaa-2002.pdf pdf]
* [[Robert Hyatt]], [[Tim Mann]] ('''2002'''). ''[http://www.craftychess.com/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]]
* [http://www.fi.muni.cz/%7Exbarnat/ Jiří Barnat], [http://www.behindkde.org/node/625 Petr Ročkai] ('''2007'''). ''Shared Hash Tables in Parallel Model Checking''. Faculty of Informatics, [https://en.wikipedia.org/wiki/Masaryk_University Masaryk University], [https://en.wikipedia.org/wiki/Brno Brno], [https://en.wikipedia.org/wiki/Czech_Republic Czech Republic], PDMC 2007, Preliminary Version as [http://anna.fi.muni.cz/papers/src/public/168699cd5787307ee3c8c1a509327e6f.pdf pdf]
* [http://www.cs.rice.edu/%7Evs3/home/Vivek_Sarkar.html Vivek Sarkar] ('''2008'''). ''Shared-Memory Parallel Programming with OpenMP''. [https://en.wikipedia.org/wiki/Rice_University Rice University], [http://www.cs.rice.edu/%7Evs3/comp422/lecture-notes/comp422-lec7-s08-v1.pdf slides as pdf]
* [http://offcode.fi/ Jouni Leppäjärvi] ('''2008'''). ''A pragmatic, historically oriented survey on the universality of synchronization primitives''. [http://www.oamk.fi/~joleppaj/personal/jleppaja_gradu_080511.pdf pdf]
==2010 ...==
* [http://www.vf.utwente.nl/%7Elaarman/ Alfons Laarman], [http://wwwhome.ewi.utwente.nl/%7Evdpol/ Jaco van de Pol], [http://wwwhome.cs.utwente.nl/%7Emichaelw/ Michael Weber] ('''2010'''). ''[http://doc.utwente.nl/73119/ Boosting Multi-Core Reachability Performance with Shared Hash Tables]''. Formal Methods and Tools, [https://en.wikipedia.org/wiki/University_of_Twente University of Twente], [https://en.wikipedia.org/wiki/Netherlands The Netherlands], [http://fmcad10.iaik.tugraz.at/Papers/papers/12Session11/033Laarman.pdf pdf]
* [http://www.cs.rice.edu/%7Ejohnmc/ John Mellor-Crummey] ('''2011'''). ''Shared-memory Parallel Programming with Cilk''. [https://en.wikipedia.org/wiki/Rice_University Rice University], [http://www.clear.rice.edu/comp422/lecture-notes/comp422-2011-Lecture4-Cilk.pdf slides as pdf] » [[Cilk]]
* [http://stackoverflow.com/users/5597/anthony-williams Anthony Williams] ('''2012'''). ''[http://www.cplusplusconcurrencyinaction.com/ C++ Concurrency in Action: Practical Multithreading]''. <ref>[http://scottmeyers.blogspot.co.uk/2012/04/information-on-c11-memory-model.html Information on the C++11 Memory Model] by [https://en.wikipedia.org/wiki/Scott_Meyers Scott Meyers], April 24, 2012</ref>
=Forum Posts=
==1997 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/Wl7A-v-gWYQ/QLuvAp0l4_gJ Parallel searching] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], March 22, 1997 » [[KnightCap]]
* [https://www.stmintz.com/ccc/index.php?id=41708 CilkChess question for Don] by [[Robert Hyatt]], [[CCC]], January 31, 1999 » [[CilkChess]]
==2000 ...==
* [https://groups.google.com/group/comp.lang.asm.x86/browse_frm/thread/ab55c5d57a3a1fd1 Re: Atomic write of 64 bits] by [[Frans Morsch]], [https://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], September 25, 2000
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=15662 multithreading questions] by [[Martin Fierz]], [[CCC]], August 08, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=19446 If making an SMP engine, do NOT use processes] by [[Zach Wegner]], [[CCC]], February 07, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=22398 threads vs processes] by [[Robert Hyatt]], [[CCC]], July 16, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=22799 threads vs processes again] by [[Robert Hyatt]], [[CCC]], August 05, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=26208 SMP hashing problem] by [[Robert Hyatt]], [[CCC]], January 24, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=26223 Interlock clusters] by [[Steven Edwards]], [[CCC]], January 25, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=37976 lockless hashing] by [[Daniel Shawul]], [[CCC]], February 07, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38411 On parallelization] by [[Onno Garms]], [[CCC]], March 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=42833 cache alignment of tt] by [[Daniel Shawul]], [[CCC]], March 11, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46346 Speaking of the hash table] by [[Ed Schroder]], [[CCC]], December 09, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46597 Lazy SMP] by [[Julien Marcel]], [[CCC]], December 27, 2012 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013
* [http://www.open-chess.org/viewtopic.php?f=5&t=2262 Multi-threaded memory access] by [[Vadim Demichev|ThinkingALot]], [[Computer Chess Forums|OpenChess Forum]], February 10, 2013 » [[Memory]], [[Thread]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47455 Lazy SMP, part 3] by [[Dan Homan|Daniel Homan]], [[CCC]], March 09, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47568 Shared hash table smp result] by [[Daniel Shawul]], [[CCC]], March 21, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47700 Transposition driven scheduling] by [[Daniel Shawul]], [[CCC]], April 04, 2013 <ref>[[John Romein]], [[Henri Bal]], [[Jonathan Schaeffer]], [[Aske Plaat]] ('''2002'''). ''A Performance Analysis of Transposition-Table-Driven Scheduling in Distributed Search''. IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 5, pp. 447–459. [http://www.cs.vu.nl/~bal/Papers/tds.pdf pdf]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Dan Homan]], [[CCC]], July 03, 2013 » [[EXchess#LazySMP|Lazy SMP]] in [[EXChess]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49099 Lockless hash: Thank you Bob Hyatt!] by [[Julien Marcel]], [[CCC]], August 25, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50388 How could a compiler break the lockless hashing method?] by [[Rein Halbersma]], [[CCC]], December 08, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=51755 Parallel Search with Transposition Table] by [[Daylen Yang]], [[CCC]], March 27, 2014 » [[Parallel Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54666 Two hash functions for distributed transposition table] by [[Daniel Shawul]], [[CCC]], December 16, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55188 Lazy SMP in Cheng] by [[Martin Sedlak]], [[CCC]], February 02, 2015 » [[Cheng]]
* [http://www.talkchess.com/forum/viewtopic.php?t=55970 Trying to improve lazy smp] by [[Daniel José Queraltó]], [[CCC]], April 11, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57572 lazy smp questions] by Lucas Braesch, [[CCC]], September 09, 2015 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57634 atomic TT] by Lucas Braesch, [[CCC]], September 13, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58645 lazy smp questions] by [[Marco Belli]], [[CCC]], December 21, 2015 » [[Lazy SMP]]
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=58830 NUMA 101] by [[Robert Hyatt]], [[CCC]], January 07, 2016 » [[NUMA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59389 Lazy SMP - how it works] by Kalyankumar Ramaseshan, [[CCC]], February 29, 2016 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60122 lockless hashing] by Lucas Braesch, [[CCC]], May 10, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61472 What do you do with NUMA?] by [[Matthew Lai]], [[CCC]], September 19, 2016 » [[NUMA]]
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=65134 Question about parallel search and race conditions] by [[Michael Sherwin]], [[CCC]], September 11, 2017 » [[Parallel Search]]
=External Links=
==Shared Memory==
{{Shared Memory}}
==Cache==
{{Cache}}
==Concurrency and Synchronization==
{{Synchronization}}
==Distributed memory==
* [https://en.wikipedia.org/wiki/Distributed_memory Distributed memory from Wikipedia]
* [https://en.wikipedia.org/wiki/Distributed_hash_table Distributed hash table from Wikipedia]
: [https://en.wikipedia.org/wiki/Koorde Koorde] based on [https://en.wikipedia.org/wiki/Chord_%28peer-to-peer%29 Chord] and [[De Bruijn sequence]]
* [https://en.wikipedia.org/wiki/Transposition-driven_scheduling Transposition-driven scheduling - Wikipedia]
* [http://webdocs.cs.ualberta.ca/~paullu/Aurora/aurora.html The Aurora Distributed Shared Data System] by [[Paul Lu]]
==Misc==
* [https://en.wikipedia.org/wiki/Cilk Cilk from Wikipedia] » [[Cilk]]
* [http://supertech.csail.mit.edu/cilk/ The Cilk Project] from [[Massachusetts Institute of Technology|MIT]]
* [https://en.wikipedia.org/wiki/Fetch-and-add Fetch-and-add from Wikipedia]
* [https://en.wikipedia.org/wiki/Intel_Cilk_Plus Intel Cilk Plus from Wikipedia]
* [https://en.wikipedia.org/wiki/XMTC XMTC from Wikipedia]
* [[Videos#IanCarr|Ian Carr]] with [https://en.wikipedia.org/wiki/Nucleus_%28band%29 Nucleus] - Solar Plexus 1971, feat. [[Videos#KarlJenkins|Karl Jenkins]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=gHwuo1eGouw|alignment=left|valignment=top}}
=References=
<references />
'''[[Hash Table|Up one Level]]'''
