25,161
edits
Changes
no edit summary
''see Main page: [[Shared Hash Table]]''
This technique is a very simple approach to [[SMP]]. The implementation requires little more than starting additional processors. Processors are simply fed the root position at the beginning of the search, and each searches the same tree with the only communication being the [[Transposition Table|transposition table]]. 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 speedup is then based on how many nodes the main processor is able to skip from transposition table entries. Many programs used this if a "quick and dirty" approach to SMP is needed. It had the reputation of little speedup on a mere 2 processors, and to scale quite badly after this.
<span id="Lazy"></span>
==Lazy SMP==
'''1983'''
* [[Raphael Finkel]], [[John Philip Fishburn]] ('''1983'''). ''Improved Speedup Bounds for Parallel Alpha-Beta Search''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 5, No. 1, pp. 89 - 92
* [[Clyde Kruskal]] ('''1983'''). ''[httphttps://ieeexplore.ieee.org/xpldocument/freeabs_all.jsp1676138?arnumber=1676138 Searching, Merging, and Sorting in Parallel Computation]''. [[IEEE#TOC|IEEE Transactions on Computers]], Vol. C-32, No 10
* [[Gary Lindstrom]] ('''1983'''). ''The Key Node Method: A Highly-Parallel Alpha-Beta Algorithm''. Technical Report UUCCS 83-101, [https://en.wikipedia.org/wiki/University_of_Utah University of Utah], [http://content.lib.utah.edu/utils/getfile/collection/uspace/id/3706/filename/image pdf]
'''1984'''
* [[Lionel Moser]] ('''1984'''). ''An Experiment in Distributed Game Tree Searching'', M.Sc. thesis, [[University of Waterloo]] <ref>[[Jonathan Schaeffer]] ('''1985'''). ''[[Lionel Moser]]: An Experiment in Distributed Game Tree Searching.'' [[ICGA Journal#8_2|ICCA Journal, Vol. 8, No. 2]] (Review)</ref> <ref>[httphttps://www.cs.uwaterloo.ca/~alopez-o/divulge/chimp.html An Introduction to Computer Chess] by [http://www.cs.uwaterloo.ca/~alopez-o/ [Alejandro López-Ortiz]], 1993</ref>
==1985 ...==
* [[Tony Marsland]], [[Fred Popowich]] ('''1985'''). ''Parallel Game-Tree Search.'' [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 7, No. 4, pp. 442-452. [http://webdocs.cs.ualberta.ca/~tony/OldPapers/parallel.pdf 1984 pdf] (Draft)
* [[Baruch Awerbuch]] ('''1985'''). ''[http://www.sciencedirect.com/science/article/pii/0020019085900833 A New Distributed Depth-First Search Algorithm]''. [https://en.wikipedia.org/wiki/Information_Processing_Letters Information Processing Letters], Vol. 20, No. 3
* [[Monroe Newborn]] ('''1985'''). ''A Parallel Search Chess Program''. Proceedings of the ACM Annual Conference, pp. 272-277. Denver, Co.
* [[Clyde Kruskal]], [https://en.wikipedia.org/wiki/Alan_Weiss_%28mathematician%29 [Mathematician#AWeiss|Alan Weiss]] ('''1985'''). ''Allocating Independent Subtasks on Parallel Processors''. [https://en.wikipedia.org/wiki/IEEE_Transactions_on_Software_Engineering [IEEE#SE|IEEE Transactions on Software Engineering]], Vol. 11, No. 10
* [http://www.informatik.uni-trier.de/~ley/pers/hd/l/Leifker:Daniel_B=.html Daniel B. Leifker], [[Laveen Kanal|Laveen N. Kanal]] ('''1985'''). ''[http://dl.acm.org/citation.cfm?id=1623687 A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees]''. [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai85.html#LeifkerK85 IJCAI'85] » [[SSS* and Dual*]]
'''1986'''
==1990 ...==
* [[Rainer Feldmann]], [[Peter Mysliwietz]], [[Burkhard Monien]] ('''1991''') ''A Fully Distributed Chess Program''. [[Advances in Computer Chess 6]], [http://www.top-5000.nl/ps/A%20fully%20distribuited%20chess%20program.pdf pdf]
* [[Clyde Kruskal]], [[Mathematician#LRudolph|Larry Rudolph]], [[Mathematician#MSnir|Marc Snir]] ('''1990'''). ''[https://www.sciencedirect.com/science/article/pii/030439759090192K A Complexity Theory of Efficient Parallel Algorithms]''. [https://en.wikipedia.org/wiki/Theoretical_Computer_Science_%28journal%29 Theoretical Computer Science], Vol. 71
* [[Clyde Kruskal]], [[Mathematician#LRudolph|Larry Rudolph]], [[Mathematician#MSnir|Marc Snir]] ('''1990'''). ''[https://link.springer.com/article/10.1007/BF01840376 Efficient Parallel Algorithms for Graph Problems]''. [https://en.wikipedia.org/wiki/Algorithmica Algorithmica], Vol. 5, No. 1
'''1992'''
* [[Jaleh Rezaie]], [[Raphael Finkel]] ('''1992'''). ''[https://www.researchgate.net/publication/2813087_A_comparison_of_some_parallel_game-tree_search_algorithms_Revised_version A comparison of some parallel game-tree search algorithms]''. [https://en.wikipedia.org/wiki/University_of_Kentucky University of Kentucky]
* [http://www.talkchess.com/forum/viewtopic.php?t=58946 Parallel Search to Fixed Depth] by [[Brian Richardson]], [[CCC]], January 17, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=58950 Threads test incl. Komodo 9.3] by [[Andreas Strangmüller]], [[CCC]], January 17, 2016 » [[Komodo]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59389 Lazy SMP - how it works] by [[Kalyankumar Ramaseshan]], [[CCC]], February 29, 2016 » [[Lazy SMP]]
* [http://talkchess.com/forum/viewtopic.php?t=59745 Crafty SMP measurement] by [[Robert Hyatt]], [[CCC]], April 04, 2016 » [[Crafty]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60271 parallel search speed measurement] by [[Robert Hyatt]], [[CCC]], May 24, 2016
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69481 Simplest way to implement quick and dirty lazy smp] by [[Tom King]], [[CCC]], January 04, 2019
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71115 OpenMP for chess programming] by BeyondCritics, [[CCC]], June 27, 2019
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71739 Multithreaded noob question] by [[Michael Sherwin]], [[CCC]], September 06, 2019
=External Links=
