25,161
edits
Changes
no edit summary
=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 secondSecond|NPS]] scaling is nearly perfect.
==ABDADA==
''see Main page: [[Lazy SMP]]''
Recent improvements by [[Dan Daniel 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=
* [[Memory]]
* [[Parallel Search]]
* [[SSE2]]
* [[Transposition Table]]
<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 [Mathematician#LRudolph|Larry Rudolph]], [http://cs.illinois.edu/people/faculty/marc-snir [Mathematician#MSnir|Marc Snir]] ('''1988'''). ''[https://dl.acm.org/citation.cfm?id=48024 Efficient Synchronization on Multiprocessors with Shared Memory]''. [[ACM#TOPLAS|ACM TOPLAS]], Vol. 10, No. 4
* [[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.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>
* [https://dblp.uni-trier.de/pers/hd/m/Maier:Tobias Tobias Maier], [[Peter Sanders]], [https://dblp.uni-trier.de/pers/hd/d/Dementiev:Roman Roman Dementiev] ('''2016'''). ''Concurrent Hash Tables: Fast and General?(!)''. [https://arxiv.org/abs/1601.04017 arXiv:1601.04017]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=26223 Interlock clusters] by [[Steven Edwards]], [[CCC]], January 25, 2009
==2010 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=34606 Crafty Transpostion Table Question] by [[Eric Stock]], [[CCC]], May 30, 2010 » [[Crafty]], [[#Lockless|Lockless Hashing]]
* [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=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 Daniel Homan]], [[CCC]], July 03, 2013 » [[EXchess#LazySMP|Lazy SMP]] in [[EXChessEXchess]]
* [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
'''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]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70586 Prefetch and Threading] by [[Dennis Sceviour]], [[CCC]], April 25, 2019 » [[Thread]], [[Transposition Table]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72684 RMO - Randomized Move Order - yet another Lazy SMP derivate] by [[Srdja Matovic]], [[CCC]], December 30, 2019
==2020 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72932 hash collisions] by [[Jon Dart]], [[CCC]], January 28, 2020 » [[Transposition Table#KeyCollisions|Key Collisions]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76483 Transposition table and multithreaded search] by [[Niels Abildskov]], [[CCC]], February 03, 2021
=External Links=
* [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 sequenceSequence]]
* [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]]
* [https://en.wikipedia.org/wiki/Intel_Cilk_Plus Intel Cilk Plus from Wikipedia]
* [https://en.wikipedia.org/wiki/XMTC XMTC from Wikipedia]
* [[Videos#IanCarr:Category:Ian Carr|Ian Carr]] with [[:Category:Nucleus|Nucleus]] - [https://en.wikipedia.org/wiki/Nucleus_%28band%29 Nucleus] - (band)#Discography Solar Plexus 1971], feat. [[Videos#KarlJenkins:Category:Karl Jenkins|Karl Jenkins]], [[:Category:Jeff Clyne|Jeff Clyne]] and [[:Category:John Marshall|John Marshall]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=gHwuo1eGouw|alignment=left|valignment=top}}
'''[[Hash Table|Up one Level]]'''
[[Category:Nucleus]]
[[Category:Ian Carr]]
[[Category:Karl Jenkins]]
[[Category:John Marshall]]
[[Category:Jeff Clyne]]
