25,161
edits
Changes
Created page with "'''Home * Search * Parallel Search * Dynamic Tree Splitting''' FILE:Feeringbury Manor split double trunk tree, Feering Essex England 1.jpg|border|righ..."
'''[[Main Page|Home]] * [[Search]] * [[Parallel Search]] * Dynamic Tree Splitting'''
[[FILE:Feeringbury Manor split double trunk tree, Feering Essex England 1.jpg|border|right|thumb|Splitted tree <ref>A tree with a doubled split trunk on a lawn beside a drive at Feeringbury Manor in the [https://en.wikipedia.org/wiki/Civil_parish civil parish] of [https://en.wikipedia.org/wiki/Feering Feering], [https://en.wikipedia.org/wiki/Braintree_District Braintree], [https://en.wikipedia.org/wiki/Essex Essex], England. [https://commons.wikimedia.org/wiki/File:Feeringbury_Manor_split_double_trunk_tree,_Feering_Essex_England_1.jpg Image] © by [https://commons.wikimedia.org/wiki/User:Acabashi Acabashi], October 02, 2015, [https://creativecommons.org/licenses/by-sa/4.0/deed.en Creative Commons CC BY-SA 4.0], Source: [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref>]]
'''Dynamic Tree Splitting''', (DTS)<br/>
a [https://en.wikipedia.org/wiki/Peer-to-peer peer-to-peer] model of parallelism which divides the [[Search Tree|search tree]] among several processors on a [[Memory#Shared|shared memory]] parallel machine, devised by [[Robert Hyatt]] <ref>[[Robert Hyatt]] ('''1994'''). ''[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm]''</ref> , implemented in [[Cray Blitz]] and tested on a 16 processor [[Cray X-MP#C90|Cray C916/1024]] with 1024 mebiwords of [[Memory|memory]] (8 [https://en.wikipedia.org/wiki/Gibibyte gibibytes]).DTS overcomes one problem of [[Parallel Search#PrincipalVariationSplitting|principle variation splitting]] (PVS) and enhanced principle variation splitting (EPVS) <ref>[[Robert Hyatt]], [[Bruce W. Suter]], [[Harry Nelson]] ('''1989'''). ''A Parallel Alpha-Beta Tree Searching Algorithm''. Parallel Computing, Vol. 10, No. 3.</ref> with bushy trees, that processors assigned to a [[Node|node]] become and stay [https://en.wikipedia.org/wiki/Idle_(CPU) idle] while other processors are still busy on the same node. In DTS, busy processors publish their state of the tree in shared memory for idle processors to examine, to let them decide which (if any) of the busy processors to join, and to inform a busy processor of the chosen expceted [[Node Types#ALL|all-node]] or [[Node Types#PV|pv-node]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=398061&t=38317 Re: "CUT" vs "ALL" nodes] by [[Robert Hyatt]], [[CCC]], March 08, 2011</ref> , dubbed split point. The busy processor with that subtree in progress in turn, then copies the complete tree state with current [[Chess Position|board position]], [[Bound|bounds]], [[Move List|move list]], [[Repetitions#listofkeys|repetition list]] and so forth to a shared memory area, becoming a so called "split block". Owner and helper processors can now extract moves from this shared data to search in parallel <ref>[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm] by [[Robert Hyatt]]</ref> .
=Performance Test=
Rather than to use a group of unrelated chess problems, the CB team took a segment of a real chess game from the [[ACM 1993]] [[ACM 1993#MChessCrayBlitz|M-Chess Pro vs. Cray Blitz]], a sharp [https://en.wikipedia.org/wiki/Vienna_Game Vienna game] aka delayed [https://en.wikipedia.org/wiki/King%27s_Gambit#King.27s_Gambit_Accepted:_2...exf4 kings gambit accepted] after CB was out of book after 1. e4 e5 2. Nc3 Nc6 3. f4 exf4 4. Nf3 g5 5. d4 g4 6. Bc4 gxf3 7. o-o d5 8. exd5 Bg4 9. Qd2, 24 positions in total. The results include two sets of numbers for each test, where a test used either one, two, four, eight or sixteen processors. The numbers are the clock time required for the search (wall clock time) and the number of nodes searched which shows how much extra work is added by using additional processors <ref>[[Robert Hyatt]] ('''1994'''). ''[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm]''</ref> .
==DTS Speedups==
''DTS Cray Blitz speedups on Cray C916/1024 over 24 test positions'' <ref>Table 4 Search Time in Seconds, Table 5 Total Nodes Searched, and Table 6 Parallel Processing Speedup, combined, in [http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm] by [[Robert Hyatt]], and [[Robert Hyatt]] ('''1997'''). ''[http://www.craftychess.com/hyatt/search.html The Dynamic Tree-Splitting Parallel Search Algorithm]''. [[ICGA Journal#20_1|ICCA Journal, Vol. 20, No. 1]]</ref>
{| class="wikitable"
|-
! #proc
! colspan="3" | 1
! colspan="3" | 2
! colspan="3" | 4
! colspan="3" | 8
! colspan="3" | 16
|-
! pos
! sec
! nodes
! speedup
! sec
! nodes
! speedup
! sec
! nodes
! speedup
! sec
! nodes
! speedup
! sec
! nodes
! speedup
|-
! 1
| style="text-align:right;" | 2,830
| style="text-align:right;" | 87,735,974
! 1
| style="text-align:right;" | 1,415
| style="text-align:right;" | 89,052,012
! 2.0
| style="text-align:right;" | 832
| style="text-align:right;" | 105,025,123
! 3.4
| style="text-align:right;" | 435
| style="text-align:right;" | 109,467,495
! 6.5
| style="text-align:right;" | 311
| style="text-align:right;" | 155,514,410
! 9.1
|-
! 2
| style="text-align:right;" | 2,849
| style="text-align:right;" | 88,954,757
! 1
| style="text-align:right;" | 1,424
| style="text-align:right;" | 90,289,077
! 2.0
| style="text-align:right;" | 791
| style="text-align:right;" | 100,568,301
! 3.6
| style="text-align:right;" | 438
| style="text-align:right;" | 110,988,161
! 6.5
| style="text-align:right;" | 274
| style="text-align:right;" | 137,965,406
! 10.4
|-
! 3
| style="text-align:right;" | 3,274
| style="text-align:right;" | 101,302,792
! 1
| style="text-align:right;" | 1,637
| style="text-align:right;" | 102,822,332
! 2.0
| style="text-align:right;" | 884
| style="text-align:right;" | 111,433,074
! 3.7
| style="text-align:right;" | 467
| style="text-align:right;" | 117,366,515
! 7.0
| style="text-align:right;" | 239
| style="text-align:right;" | 119,271,093
! 13.7
|-
! 4
| style="text-align:right;" | 2,308
| style="text-align:right;" | 71,726,853
! 1
| style="text-align:right;" | 1,154
| style="text-align:right;" | 72,802,754
! 2.0
| style="text-align:right;" | 591
| style="text-align:right;" | 74,853,409
! 3.9
| style="text-align:right;" | 349
| style="text-align:right;" | 88,137,085
! 6.6
| style="text-align:right;" | 208
| style="text-align:right;" | 104,230,094
! 11.1
|-
! 5
| style="text-align:right;" | 1,584
| style="text-align:right;" | 49,386,616
! 1
| style="text-align:right;" | 792
| style="text-align:right;" | 50,127,414
! 2.0
| style="text-align:right;" | 440
| style="text-align:right;" | 55,834,316
! 3.6
| style="text-align:right;" | 243
| style="text-align:right;" | 61,619,298
! 6.5
| style="text-align:right;" | 178
| style="text-align:right;" | 89,506,306
! 8.9
|-
! 6
| style="text-align:right;" | 4,294
| style="text-align:right;" | 133,238,718
! 1
| style="text-align:right;" | 2,147
| style="text-align:right;" | 135,237,296
! 2.0
| style="text-align:right;" | 1,160
| style="text-align:right;" | 146,562,594
! 3.7
| style="text-align:right;" | 670
| style="text-align:right;" | 168,838,428
! 6.4
| style="text-align:right;" | 452
| style="text-align:right;" | 226,225,307
! 9.5
|-
! 7
| style="text-align:right;" | 1,888
| style="text-align:right;" | 58,593,747
! 1
| style="text-align:right;" | 993
| style="text-align:right;" | 62,602,792
! 1.9
| style="text-align:right;" | 524
| style="text-align:right;" | 66,243,490
! 3.6
| style="text-align:right;" | 273
| style="text-align:right;" | 68,868,878
! 6.9
| style="text-align:right;" | 187
| style="text-align:right;" | 93,575,946
! 10.1
|-
! 8
| style="text-align:right;" | 7,275
| style="text-align:right;" | 225,906,282
! 1
| style="text-align:right;" | 3,637
| style="text-align:right;" | 229,294,872
! 2.0
| style="text-align:right;" | 1,966
| style="text-align:right;" | 248,496,917
! 3.7
| style="text-align:right;" | 1,039
| style="text-align:right;" | 261,728,552
! 7.0
| style="text-align:right;" | 680
| style="text-align:right;" | 340,548,431
! 10.7
|-
! 9
| style="text-align:right;" | 3,940
| style="text-align:right;" | 122,264,617
! 1
| style="text-align:right;" | 1,970
| style="text-align:right;" | 124,098,584
! 2.0
| style="text-align:right;" | 1,094
| style="text-align:right;" | 138,226,951
! 3.6
| style="text-align:right;" | 635
| style="text-align:right;" | 159,930,005
! 6.2
| style="text-align:right;" | 398
| style="text-align:right;" | 199,204,874
! 9.9
|-
! 10
| style="text-align:right;" | 2,431
| style="text-align:right;" | 75,301,353
! 1
| style="text-align:right;" | 1,215
| style="text-align:right;" | 76,430,872
! 2.0
| style="text-align:right;" | 639
| style="text-align:right;" | 80,651,716
! 3.8
| style="text-align:right;" | 333
| style="text-align:right;" | 83,656,702
! 7.3
| style="text-align:right;" | 187
| style="text-align:right;" | 93,431,597
! 13.0
|-
! 11
| style="text-align:right;" | 3,062
| style="text-align:right;" | 95,321,494
! 1
| style="text-align:right;" | 1,531
| style="text-align:right;" | 96,751,315
! 2.0
| style="text-align:right;" | 827
| style="text-align:right;" | 104,853,646
! 3.7
| style="text-align:right;" | 425
| style="text-align:right;" | 107,369,070
! 7.2
| style="text-align:right;" | 247
| style="text-align:right;" | 123,994,812
! 12.4
|-
! 12
| style="text-align:right;" | 2,518
| style="text-align:right;" | 79,975,416
! 1
| style="text-align:right;" | 1,325
| style="text-align:right;" | 85,447,418
! 1.9
| style="text-align:right;" | 662
| style="text-align:right;" | 85,657,884
! 3.8
| style="text-align:right;" | 364
| style="text-align:right;" | 94,000,085
! 6.9
| style="text-align:right;" | 219
| style="text-align:right;" | 112,174,209
! 11.5
|-
! 13
| style="text-align:right;" | 2,131
| style="text-align:right;" | 66,100,160
! 1
| style="text-align:right;" | 1,121
| style="text-align:right;" | 70,622,802
! 1.9
| style="text-align:right;" | 560
| style="text-align:right;" | 70,796,754
! 3.8
| style="text-align:right;" | 313
| style="text-align:right;" | 78,834,155
! 6.8
| style="text-align:right;" | 192
| style="text-align:right;" | 96,053,649
! 11.1
|-
! 14
| style="text-align:right;" | 1,871
| style="text-align:right;" | 58,099,574
! 1
| style="text-align:right;" | 935
| style="text-align:right;" | 58,971,066
! 2.0
| style="text-align:right;" | 534
| style="text-align:right;" | 67,561,507
! 3.5
| style="text-align:right;" | 296
| style="text-align:right;" | 74,791,668
! 6.3
| style="text-align:right;" | 191
| style="text-align:right;" | 95,627,150
! 9.8
|-
! 15
| style="text-align:right;" | 2,648
| style="text-align:right;" | 84,143,340
! 1
| style="text-align:right;" | 1,324
| style="text-align:right;" | 85,405,488
! 2.0
| style="text-align:right;" | 715
| style="text-align:right;" | 92,557,676
! 3.7
| style="text-align:right;" | 378
| style="text-align:right;" | 97,486,065
! 7.0
| style="text-align:right;" | 243
| style="text-align:right;" | 124,516,703
! 10.9
|-
! 16
| style="text-align:right;" | 2,347
| style="text-align:right;" | 75,738,094
! 1
| style="text-align:right;" | 1,235
| style="text-align:right;" | 80,920,173
! 1.9
| style="text-align:right;" | 601
| style="text-align:right;" | 79,039,499
! 3.9
| style="text-align:right;" | 321
| style="text-align:right;" | 84,141,904
! 7.3
| style="text-align:right;" | 182
| style="text-align:right;" | 94,701,972
! 12.9
|-
! 17
| style="text-align:right;" | 4,884
| style="text-align:right;" | 154,901,225
! 1
| style="text-align:right;" | 2,872
| style="text-align:right;" | 184,970,278
! 1.7
| style="text-align:right;" | 1,878
| style="text-align:right;" | 242,480,013
! 2.6
| style="text-align:right;" | 1,085
| style="text-align:right;" | 279,166,418
! 4.5
| style="text-align:right;" | 814
| style="text-align:right;" | 416,426,105
! 6.0
|-
! 18
| style="text-align:right;" | 646
| style="text-align:right;" | 20,266,629
! 1
| style="text-align:right;" | 358
| style="text-align:right;" | 22,856,254
! 1.8
| style="text-align:right;" | 222
| style="text-align:right;" | 28,443,165
! 2.9
| style="text-align:right;" | 124
| style="text-align:right;" | 31,608,146
! 5.2
| style="text-align:right;" | 84
| style="text-align:right;" | 42,454,639
! 7.7
|-
! 19
| style="text-align:right;" | 2,983
| style="text-align:right;" | 93,858,903
! 1
| style="text-align:right;" | 1,491
| style="text-align:right;" | 95,266,785
! 2.0
| style="text-align:right;" | 785
| style="text-align:right;" | 100,527,830
! 3.8
| style="text-align:right;" | 426
| style="text-align:right;" | 108,742,238
! 7.0
| style="text-align:right;" | 226
| style="text-align:right;" | 114,692,731
! 13.2
|-
! 20
| style="text-align:right;" | 7,473
| style="text-align:right;" | 231,206,390
! 1
| style="text-align:right;" | 3,736
| style="text-align:right;" | 234,674,482
! 2.0
| style="text-align:right;" | 1,916
| style="text-align:right;" | 241,284,621
! 3.9
| style="text-align:right;" | 1,083
| style="text-align:right;" | 271,751,263
! 6.9
| style="text-align:right;" | 530
| style="text-align:right;" | 264,493,531
! 14.1
|-
! 21
| style="text-align:right;" | 3,626
| style="text-align:right;" | 112,457,464
! 1
| style="text-align:right;" | 1,813
| style="text-align:right;" | 114,144,324
! 2.0
| style="text-align:right;" | 906
| style="text-align:right;" | 114,425,474
! 4.0
| style="text-align:right;" | 489
| style="text-align:right;" | 123,247,294
! 7.4
| style="text-align:right;" | 237
| style="text-align:right;" | 118,558,091
! 15.3
|-
! 22
| style="text-align:right;" | 2,560
| style="text-align:right;" | 81,302,340
! 1
| style="text-align:right;" | 1,347
| style="text-align:right;" | 86,865,131
! 1.9
| style="text-align:right;" | 691
| style="text-align:right;" | 89,432,576
! 3.7
| style="text-align:right;" | 412
| style="text-align:right;" | 106,348,704
! 6.2
| style="text-align:right;" | 264
| style="text-align:right;" | 135,196,568
! 9.7
|-
! 23
| style="text-align:right;" | 2,039
| style="text-align:right;" | 63,598,940
! 1
| style="text-align:right;" | 1,019
| style="text-align:right;" | 64,552,923
! 2.0
| style="text-align:right;" | 536
| style="text-align:right;" | 68,117,815
! 3.8
| style="text-align:right;" | 323
| style="text-align:right;" | 81,871,010
! 6.3
| style="text-align:right;" | 206
| style="text-align:right;" | 103,621,303
! 9.9
|-
! 24
| style="text-align:right;" | 2,563
| style="text-align:right;" | 80,413,971
! 1
| style="text-align:right;" | 1,281
| style="text-align:right;" | 81,620,179
! 2.0
| style="text-align:right;" | 657
| style="text-align:right;" | 83,919,196
! 3.9
| style="text-align:right;" | 337
| style="text-align:right;" | 85,810,169
! 7.6
| style="text-align:right;" | 178
| style="text-align:right;" | 90,074,814
! 14.4
|-
! avg
!
!
! 1
!
!
! 2.0
!
!
! 3.7
!
!
! 6.6
!
!
! 11.1
|}
Despite Robert Hyatt mentioned DTS really will only scale as far as a shared memory architecture scales, and any delays (such as those in some architectures that use a [[NUMA|hierarchical memory organization]] with varying delays depending on how far the memory is from the requesting processor) will certainly have an adverse effect on DTS, the published speedups were heavily criticized by [[Vincent Diepeveen]] in 2002 <ref>[https://www.stmintz.com/ccc/index.php?id=249457 DTS article robert hyatt - revealing his bad math] by [[Vincent Diepeveen]], [[CCC]], September 03, 2002</ref> .
==Comparison==
''Average Cray Blitz speedups on Cray C916/1024 over 24 test positions''
{| class="wikitable"
|-
! #Procs<br/>Algorithm
! 1
! 2
! 4
! 8
! 16
|-
! PVS
| style="text-align:right;" | 1.0
| style="text-align:right;" | 1.8
| style="text-align:right;" | 3.0
| style="text-align:right;" | 4.1
| style="text-align:right;" | 4.6
|-
! EPVS
| style="text-align:right;" | 1.0
| style="text-align:right;" | 1.9
| style="text-align:right;" | 3.4
| style="text-align:right;" | 5.4
| style="text-align:right;" | 6.0
|-
! DTS
| style="text-align:right;" | 1.0
| style="text-align:right;" | 2.0
| style="text-align:right;" | 3.7
| style="text-align:right;" | 6.6
| style="text-align:right;" | 11.1
|}
=Recursive DTS=
While searching various subtrees with different [[Ply|ply]] levels from the [[Root|root]] was quite straighforward to implement in [[Cray Blitz|Cray Blitz']] [[Iterative Search|iterative search]] written in [[Fortran]], a [[Recursion|recursive]] [[Negamax]] would have made it much more difficult, since the [[Stack#Hardware|call stack]] is inaccessible to the search code and moving the tree state around would have been more difficult <ref>[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm] by [[Robert Hyatt]]</ref> . A recursive DTS-like algorithm was proposed by [[Peter Österlund]] in 2013 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48752 Recursive DTS-like search algorithm] by [[Peter Österlund]], [[CCC]], July 24, 201</ref> , as implemented in [[Texel]].
=See also=
* [[ABDADA]]
* [[Jamboree]]
* [[Lazy SMP]]
* [[NUMA]]
* [[SMP]]
* [[Young Brothers Wait Concept]]
=Publications=
* [[Robert Hyatt]] ('''1994'''). ''[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm]''.
* [[Robert Hyatt]] ('''1997'''). ''[http://www.craftychess.com/hyatt/search.html The Dynamic Tree-Splitting Parallel Search Algorithm]''. [[ICGA Journal#20_1|ICCA Journal, Vol. 20, No. 1]]
* [[Valavan Manohararajah]] ('''2001'''). ''Parallel Alpha-Beta Search on Shared Memory Multiprocessors''. Masters Thesis, [http://www.top-5000.nl/ps/Parallel%20Alpha-Beta%20Search%20on%20Shared%20Memory%20Multiprocessors.pdf pdf]
* [[David J. Wu]] ('''2015'''). ''Designing a Winning Arimaa Program''. [[ICGA Journal#38_1|ICGA Journal, Vol. 38, No. 1]], [http://icosahedral.net/downloads/djwu2015arimaa_color.pdf pdf] » [[Arimaa]] <ref>[https://www.game-ai-forum.org/viewtopic.php?f=2&t=83 Paper describing "Sharp" the program that won the Arimaa Challenge] by ddyer, [[Computer Chess Forums|Game-AI Forum]], January 14, 2016</ref>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=249457 DTS article robert hyatt - revealing his bad math] by [[Vincent Diepeveen]], [[CCC]], September 03, 2002
: [https://www.stmintz.com/ccc/index.php?id=249651 DTS NUMA] by [[Vincent Diepeveen]], [[CCC]], September 03, 2002 » [[NUMA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=14832 Iterative DTS] by [[Fritz Reul]], [[CCC]], July 02, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=34561 DTS Structure] by [[Edmund Moshammer]], [[CCC]], May 28, 2010 » [[Dynamic Tree Splitting]], [[Iterative Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=34633 DTS-ification of YBWC] by [[Marco Costalba]], [[CCC]], June 01, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=42986 Parallelization questions, ABDADA or DTS?] by [[Benjamin Rosseaux]], [[CCC]], March 23, 2012 » [[ABDADA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48752 Recursive DTS-like search algorithm] by [[Peter Österlund]], [[CCC]], July 24, 2013 » [[Texel]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2378 DTS-like SMP] by [[Vadim Demichev|ThinkingALot]], [[Computer Chess Forums|OpenChess Forum]], July 25, 2013 » [[GullChess|Gull]]
* [http://www.talkchess.com/forum/viewtopic.php?t=55649 Dynamic Tree Splitting] by [[Syed Fahad]], [[CCC]], March 13, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56019 Empirical results with Lazy SMP, YBWC, DTS] by [[Kai Laskos]], [[CCC]], April 16, 2015 » [[Lazy SMP]], [[Young Brothers Wait Concept|YBWC]]
=External Links=
* [http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm] by [[Robert Hyatt]]
* [[Videos#PorcupineTree|Porcupine Tree]] - [https://en.wikipedia.org/wiki/Octane_Twisted Octane Twisted] (2012), recorded at [https://en.wikipedia.org/wiki/Riviera_Theater Riviera Theatre], [https://en.wikipedia.org/wiki/Chicago,_Illinois Chicago], April 30, 2010, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=LR-ikN7K8TM|alignment=left|valignment=top}}
=References=
<references />
'''[[Parallel Search|Up one level]]'''
[[FILE:Feeringbury Manor split double trunk tree, Feering Essex England 1.jpg|border|right|thumb|Splitted tree <ref>A tree with a doubled split trunk on a lawn beside a drive at Feeringbury Manor in the [https://en.wikipedia.org/wiki/Civil_parish civil parish] of [https://en.wikipedia.org/wiki/Feering Feering], [https://en.wikipedia.org/wiki/Braintree_District Braintree], [https://en.wikipedia.org/wiki/Essex Essex], England. [https://commons.wikimedia.org/wiki/File:Feeringbury_Manor_split_double_trunk_tree,_Feering_Essex_England_1.jpg Image] © by [https://commons.wikimedia.org/wiki/User:Acabashi Acabashi], October 02, 2015, [https://creativecommons.org/licenses/by-sa/4.0/deed.en Creative Commons CC BY-SA 4.0], Source: [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref>]]
'''Dynamic Tree Splitting''', (DTS)<br/>
a [https://en.wikipedia.org/wiki/Peer-to-peer peer-to-peer] model of parallelism which divides the [[Search Tree|search tree]] among several processors on a [[Memory#Shared|shared memory]] parallel machine, devised by [[Robert Hyatt]] <ref>[[Robert Hyatt]] ('''1994'''). ''[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm]''</ref> , implemented in [[Cray Blitz]] and tested on a 16 processor [[Cray X-MP#C90|Cray C916/1024]] with 1024 mebiwords of [[Memory|memory]] (8 [https://en.wikipedia.org/wiki/Gibibyte gibibytes]).DTS overcomes one problem of [[Parallel Search#PrincipalVariationSplitting|principle variation splitting]] (PVS) and enhanced principle variation splitting (EPVS) <ref>[[Robert Hyatt]], [[Bruce W. Suter]], [[Harry Nelson]] ('''1989'''). ''A Parallel Alpha-Beta Tree Searching Algorithm''. Parallel Computing, Vol. 10, No. 3.</ref> with bushy trees, that processors assigned to a [[Node|node]] become and stay [https://en.wikipedia.org/wiki/Idle_(CPU) idle] while other processors are still busy on the same node. In DTS, busy processors publish their state of the tree in shared memory for idle processors to examine, to let them decide which (if any) of the busy processors to join, and to inform a busy processor of the chosen expceted [[Node Types#ALL|all-node]] or [[Node Types#PV|pv-node]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=398061&t=38317 Re: "CUT" vs "ALL" nodes] by [[Robert Hyatt]], [[CCC]], March 08, 2011</ref> , dubbed split point. The busy processor with that subtree in progress in turn, then copies the complete tree state with current [[Chess Position|board position]], [[Bound|bounds]], [[Move List|move list]], [[Repetitions#listofkeys|repetition list]] and so forth to a shared memory area, becoming a so called "split block". Owner and helper processors can now extract moves from this shared data to search in parallel <ref>[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm] by [[Robert Hyatt]]</ref> .
=Performance Test=
Rather than to use a group of unrelated chess problems, the CB team took a segment of a real chess game from the [[ACM 1993]] [[ACM 1993#MChessCrayBlitz|M-Chess Pro vs. Cray Blitz]], a sharp [https://en.wikipedia.org/wiki/Vienna_Game Vienna game] aka delayed [https://en.wikipedia.org/wiki/King%27s_Gambit#King.27s_Gambit_Accepted:_2...exf4 kings gambit accepted] after CB was out of book after 1. e4 e5 2. Nc3 Nc6 3. f4 exf4 4. Nf3 g5 5. d4 g4 6. Bc4 gxf3 7. o-o d5 8. exd5 Bg4 9. Qd2, 24 positions in total. The results include two sets of numbers for each test, where a test used either one, two, four, eight or sixteen processors. The numbers are the clock time required for the search (wall clock time) and the number of nodes searched which shows how much extra work is added by using additional processors <ref>[[Robert Hyatt]] ('''1994'''). ''[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm]''</ref> .
==DTS Speedups==
''DTS Cray Blitz speedups on Cray C916/1024 over 24 test positions'' <ref>Table 4 Search Time in Seconds, Table 5 Total Nodes Searched, and Table 6 Parallel Processing Speedup, combined, in [http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm] by [[Robert Hyatt]], and [[Robert Hyatt]] ('''1997'''). ''[http://www.craftychess.com/hyatt/search.html The Dynamic Tree-Splitting Parallel Search Algorithm]''. [[ICGA Journal#20_1|ICCA Journal, Vol. 20, No. 1]]</ref>
{| class="wikitable"
|-
! #proc
! colspan="3" | 1
! colspan="3" | 2
! colspan="3" | 4
! colspan="3" | 8
! colspan="3" | 16
|-
! pos
! sec
! nodes
! speedup
! sec
! nodes
! speedup
! sec
! nodes
! speedup
! sec
! nodes
! speedup
! sec
! nodes
! speedup
|-
! 1
| style="text-align:right;" | 2,830
| style="text-align:right;" | 87,735,974
! 1
| style="text-align:right;" | 1,415
| style="text-align:right;" | 89,052,012
! 2.0
| style="text-align:right;" | 832
| style="text-align:right;" | 105,025,123
! 3.4
| style="text-align:right;" | 435
| style="text-align:right;" | 109,467,495
! 6.5
| style="text-align:right;" | 311
| style="text-align:right;" | 155,514,410
! 9.1
|-
! 2
| style="text-align:right;" | 2,849
| style="text-align:right;" | 88,954,757
! 1
| style="text-align:right;" | 1,424
| style="text-align:right;" | 90,289,077
! 2.0
| style="text-align:right;" | 791
| style="text-align:right;" | 100,568,301
! 3.6
| style="text-align:right;" | 438
| style="text-align:right;" | 110,988,161
! 6.5
| style="text-align:right;" | 274
| style="text-align:right;" | 137,965,406
! 10.4
|-
! 3
| style="text-align:right;" | 3,274
| style="text-align:right;" | 101,302,792
! 1
| style="text-align:right;" | 1,637
| style="text-align:right;" | 102,822,332
! 2.0
| style="text-align:right;" | 884
| style="text-align:right;" | 111,433,074
! 3.7
| style="text-align:right;" | 467
| style="text-align:right;" | 117,366,515
! 7.0
| style="text-align:right;" | 239
| style="text-align:right;" | 119,271,093
! 13.7
|-
! 4
| style="text-align:right;" | 2,308
| style="text-align:right;" | 71,726,853
! 1
| style="text-align:right;" | 1,154
| style="text-align:right;" | 72,802,754
! 2.0
| style="text-align:right;" | 591
| style="text-align:right;" | 74,853,409
! 3.9
| style="text-align:right;" | 349
| style="text-align:right;" | 88,137,085
! 6.6
| style="text-align:right;" | 208
| style="text-align:right;" | 104,230,094
! 11.1
|-
! 5
| style="text-align:right;" | 1,584
| style="text-align:right;" | 49,386,616
! 1
| style="text-align:right;" | 792
| style="text-align:right;" | 50,127,414
! 2.0
| style="text-align:right;" | 440
| style="text-align:right;" | 55,834,316
! 3.6
| style="text-align:right;" | 243
| style="text-align:right;" | 61,619,298
! 6.5
| style="text-align:right;" | 178
| style="text-align:right;" | 89,506,306
! 8.9
|-
! 6
| style="text-align:right;" | 4,294
| style="text-align:right;" | 133,238,718
! 1
| style="text-align:right;" | 2,147
| style="text-align:right;" | 135,237,296
! 2.0
| style="text-align:right;" | 1,160
| style="text-align:right;" | 146,562,594
! 3.7
| style="text-align:right;" | 670
| style="text-align:right;" | 168,838,428
! 6.4
| style="text-align:right;" | 452
| style="text-align:right;" | 226,225,307
! 9.5
|-
! 7
| style="text-align:right;" | 1,888
| style="text-align:right;" | 58,593,747
! 1
| style="text-align:right;" | 993
| style="text-align:right;" | 62,602,792
! 1.9
| style="text-align:right;" | 524
| style="text-align:right;" | 66,243,490
! 3.6
| style="text-align:right;" | 273
| style="text-align:right;" | 68,868,878
! 6.9
| style="text-align:right;" | 187
| style="text-align:right;" | 93,575,946
! 10.1
|-
! 8
| style="text-align:right;" | 7,275
| style="text-align:right;" | 225,906,282
! 1
| style="text-align:right;" | 3,637
| style="text-align:right;" | 229,294,872
! 2.0
| style="text-align:right;" | 1,966
| style="text-align:right;" | 248,496,917
! 3.7
| style="text-align:right;" | 1,039
| style="text-align:right;" | 261,728,552
! 7.0
| style="text-align:right;" | 680
| style="text-align:right;" | 340,548,431
! 10.7
|-
! 9
| style="text-align:right;" | 3,940
| style="text-align:right;" | 122,264,617
! 1
| style="text-align:right;" | 1,970
| style="text-align:right;" | 124,098,584
! 2.0
| style="text-align:right;" | 1,094
| style="text-align:right;" | 138,226,951
! 3.6
| style="text-align:right;" | 635
| style="text-align:right;" | 159,930,005
! 6.2
| style="text-align:right;" | 398
| style="text-align:right;" | 199,204,874
! 9.9
|-
! 10
| style="text-align:right;" | 2,431
| style="text-align:right;" | 75,301,353
! 1
| style="text-align:right;" | 1,215
| style="text-align:right;" | 76,430,872
! 2.0
| style="text-align:right;" | 639
| style="text-align:right;" | 80,651,716
! 3.8
| style="text-align:right;" | 333
| style="text-align:right;" | 83,656,702
! 7.3
| style="text-align:right;" | 187
| style="text-align:right;" | 93,431,597
! 13.0
|-
! 11
| style="text-align:right;" | 3,062
| style="text-align:right;" | 95,321,494
! 1
| style="text-align:right;" | 1,531
| style="text-align:right;" | 96,751,315
! 2.0
| style="text-align:right;" | 827
| style="text-align:right;" | 104,853,646
! 3.7
| style="text-align:right;" | 425
| style="text-align:right;" | 107,369,070
! 7.2
| style="text-align:right;" | 247
| style="text-align:right;" | 123,994,812
! 12.4
|-
! 12
| style="text-align:right;" | 2,518
| style="text-align:right;" | 79,975,416
! 1
| style="text-align:right;" | 1,325
| style="text-align:right;" | 85,447,418
! 1.9
| style="text-align:right;" | 662
| style="text-align:right;" | 85,657,884
! 3.8
| style="text-align:right;" | 364
| style="text-align:right;" | 94,000,085
! 6.9
| style="text-align:right;" | 219
| style="text-align:right;" | 112,174,209
! 11.5
|-
! 13
| style="text-align:right;" | 2,131
| style="text-align:right;" | 66,100,160
! 1
| style="text-align:right;" | 1,121
| style="text-align:right;" | 70,622,802
! 1.9
| style="text-align:right;" | 560
| style="text-align:right;" | 70,796,754
! 3.8
| style="text-align:right;" | 313
| style="text-align:right;" | 78,834,155
! 6.8
| style="text-align:right;" | 192
| style="text-align:right;" | 96,053,649
! 11.1
|-
! 14
| style="text-align:right;" | 1,871
| style="text-align:right;" | 58,099,574
! 1
| style="text-align:right;" | 935
| style="text-align:right;" | 58,971,066
! 2.0
| style="text-align:right;" | 534
| style="text-align:right;" | 67,561,507
! 3.5
| style="text-align:right;" | 296
| style="text-align:right;" | 74,791,668
! 6.3
| style="text-align:right;" | 191
| style="text-align:right;" | 95,627,150
! 9.8
|-
! 15
| style="text-align:right;" | 2,648
| style="text-align:right;" | 84,143,340
! 1
| style="text-align:right;" | 1,324
| style="text-align:right;" | 85,405,488
! 2.0
| style="text-align:right;" | 715
| style="text-align:right;" | 92,557,676
! 3.7
| style="text-align:right;" | 378
| style="text-align:right;" | 97,486,065
! 7.0
| style="text-align:right;" | 243
| style="text-align:right;" | 124,516,703
! 10.9
|-
! 16
| style="text-align:right;" | 2,347
| style="text-align:right;" | 75,738,094
! 1
| style="text-align:right;" | 1,235
| style="text-align:right;" | 80,920,173
! 1.9
| style="text-align:right;" | 601
| style="text-align:right;" | 79,039,499
! 3.9
| style="text-align:right;" | 321
| style="text-align:right;" | 84,141,904
! 7.3
| style="text-align:right;" | 182
| style="text-align:right;" | 94,701,972
! 12.9
|-
! 17
| style="text-align:right;" | 4,884
| style="text-align:right;" | 154,901,225
! 1
| style="text-align:right;" | 2,872
| style="text-align:right;" | 184,970,278
! 1.7
| style="text-align:right;" | 1,878
| style="text-align:right;" | 242,480,013
! 2.6
| style="text-align:right;" | 1,085
| style="text-align:right;" | 279,166,418
! 4.5
| style="text-align:right;" | 814
| style="text-align:right;" | 416,426,105
! 6.0
|-
! 18
| style="text-align:right;" | 646
| style="text-align:right;" | 20,266,629
! 1
| style="text-align:right;" | 358
| style="text-align:right;" | 22,856,254
! 1.8
| style="text-align:right;" | 222
| style="text-align:right;" | 28,443,165
! 2.9
| style="text-align:right;" | 124
| style="text-align:right;" | 31,608,146
! 5.2
| style="text-align:right;" | 84
| style="text-align:right;" | 42,454,639
! 7.7
|-
! 19
| style="text-align:right;" | 2,983
| style="text-align:right;" | 93,858,903
! 1
| style="text-align:right;" | 1,491
| style="text-align:right;" | 95,266,785
! 2.0
| style="text-align:right;" | 785
| style="text-align:right;" | 100,527,830
! 3.8
| style="text-align:right;" | 426
| style="text-align:right;" | 108,742,238
! 7.0
| style="text-align:right;" | 226
| style="text-align:right;" | 114,692,731
! 13.2
|-
! 20
| style="text-align:right;" | 7,473
| style="text-align:right;" | 231,206,390
! 1
| style="text-align:right;" | 3,736
| style="text-align:right;" | 234,674,482
! 2.0
| style="text-align:right;" | 1,916
| style="text-align:right;" | 241,284,621
! 3.9
| style="text-align:right;" | 1,083
| style="text-align:right;" | 271,751,263
! 6.9
| style="text-align:right;" | 530
| style="text-align:right;" | 264,493,531
! 14.1
|-
! 21
| style="text-align:right;" | 3,626
| style="text-align:right;" | 112,457,464
! 1
| style="text-align:right;" | 1,813
| style="text-align:right;" | 114,144,324
! 2.0
| style="text-align:right;" | 906
| style="text-align:right;" | 114,425,474
! 4.0
| style="text-align:right;" | 489
| style="text-align:right;" | 123,247,294
! 7.4
| style="text-align:right;" | 237
| style="text-align:right;" | 118,558,091
! 15.3
|-
! 22
| style="text-align:right;" | 2,560
| style="text-align:right;" | 81,302,340
! 1
| style="text-align:right;" | 1,347
| style="text-align:right;" | 86,865,131
! 1.9
| style="text-align:right;" | 691
| style="text-align:right;" | 89,432,576
! 3.7
| style="text-align:right;" | 412
| style="text-align:right;" | 106,348,704
! 6.2
| style="text-align:right;" | 264
| style="text-align:right;" | 135,196,568
! 9.7
|-
! 23
| style="text-align:right;" | 2,039
| style="text-align:right;" | 63,598,940
! 1
| style="text-align:right;" | 1,019
| style="text-align:right;" | 64,552,923
! 2.0
| style="text-align:right;" | 536
| style="text-align:right;" | 68,117,815
! 3.8
| style="text-align:right;" | 323
| style="text-align:right;" | 81,871,010
! 6.3
| style="text-align:right;" | 206
| style="text-align:right;" | 103,621,303
! 9.9
|-
! 24
| style="text-align:right;" | 2,563
| style="text-align:right;" | 80,413,971
! 1
| style="text-align:right;" | 1,281
| style="text-align:right;" | 81,620,179
! 2.0
| style="text-align:right;" | 657
| style="text-align:right;" | 83,919,196
! 3.9
| style="text-align:right;" | 337
| style="text-align:right;" | 85,810,169
! 7.6
| style="text-align:right;" | 178
| style="text-align:right;" | 90,074,814
! 14.4
|-
! avg
!
!
! 1
!
!
! 2.0
!
!
! 3.7
!
!
! 6.6
!
!
! 11.1
|}
Despite Robert Hyatt mentioned DTS really will only scale as far as a shared memory architecture scales, and any delays (such as those in some architectures that use a [[NUMA|hierarchical memory organization]] with varying delays depending on how far the memory is from the requesting processor) will certainly have an adverse effect on DTS, the published speedups were heavily criticized by [[Vincent Diepeveen]] in 2002 <ref>[https://www.stmintz.com/ccc/index.php?id=249457 DTS article robert hyatt - revealing his bad math] by [[Vincent Diepeveen]], [[CCC]], September 03, 2002</ref> .
==Comparison==
''Average Cray Blitz speedups on Cray C916/1024 over 24 test positions''
{| class="wikitable"
|-
! #Procs<br/>Algorithm
! 1
! 2
! 4
! 8
! 16
|-
! PVS
| style="text-align:right;" | 1.0
| style="text-align:right;" | 1.8
| style="text-align:right;" | 3.0
| style="text-align:right;" | 4.1
| style="text-align:right;" | 4.6
|-
! EPVS
| style="text-align:right;" | 1.0
| style="text-align:right;" | 1.9
| style="text-align:right;" | 3.4
| style="text-align:right;" | 5.4
| style="text-align:right;" | 6.0
|-
! DTS
| style="text-align:right;" | 1.0
| style="text-align:right;" | 2.0
| style="text-align:right;" | 3.7
| style="text-align:right;" | 6.6
| style="text-align:right;" | 11.1
|}
=Recursive DTS=
While searching various subtrees with different [[Ply|ply]] levels from the [[Root|root]] was quite straighforward to implement in [[Cray Blitz|Cray Blitz']] [[Iterative Search|iterative search]] written in [[Fortran]], a [[Recursion|recursive]] [[Negamax]] would have made it much more difficult, since the [[Stack#Hardware|call stack]] is inaccessible to the search code and moving the tree state around would have been more difficult <ref>[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm] by [[Robert Hyatt]]</ref> . A recursive DTS-like algorithm was proposed by [[Peter Österlund]] in 2013 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48752 Recursive DTS-like search algorithm] by [[Peter Österlund]], [[CCC]], July 24, 201</ref> , as implemented in [[Texel]].
=See also=
* [[ABDADA]]
* [[Jamboree]]
* [[Lazy SMP]]
* [[NUMA]]
* [[SMP]]
* [[Young Brothers Wait Concept]]
=Publications=
* [[Robert Hyatt]] ('''1994'''). ''[http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm]''.
* [[Robert Hyatt]] ('''1997'''). ''[http://www.craftychess.com/hyatt/search.html The Dynamic Tree-Splitting Parallel Search Algorithm]''. [[ICGA Journal#20_1|ICCA Journal, Vol. 20, No. 1]]
* [[Valavan Manohararajah]] ('''2001'''). ''Parallel Alpha-Beta Search on Shared Memory Multiprocessors''. Masters Thesis, [http://www.top-5000.nl/ps/Parallel%20Alpha-Beta%20Search%20on%20Shared%20Memory%20Multiprocessors.pdf pdf]
* [[David J. Wu]] ('''2015'''). ''Designing a Winning Arimaa Program''. [[ICGA Journal#38_1|ICGA Journal, Vol. 38, No. 1]], [http://icosahedral.net/downloads/djwu2015arimaa_color.pdf pdf] » [[Arimaa]] <ref>[https://www.game-ai-forum.org/viewtopic.php?f=2&t=83 Paper describing "Sharp" the program that won the Arimaa Challenge] by ddyer, [[Computer Chess Forums|Game-AI Forum]], January 14, 2016</ref>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=249457 DTS article robert hyatt - revealing his bad math] by [[Vincent Diepeveen]], [[CCC]], September 03, 2002
: [https://www.stmintz.com/ccc/index.php?id=249651 DTS NUMA] by [[Vincent Diepeveen]], [[CCC]], September 03, 2002 » [[NUMA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=14832 Iterative DTS] by [[Fritz Reul]], [[CCC]], July 02, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=34561 DTS Structure] by [[Edmund Moshammer]], [[CCC]], May 28, 2010 » [[Dynamic Tree Splitting]], [[Iterative Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=34633 DTS-ification of YBWC] by [[Marco Costalba]], [[CCC]], June 01, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=42986 Parallelization questions, ABDADA or DTS?] by [[Benjamin Rosseaux]], [[CCC]], March 23, 2012 » [[ABDADA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48752 Recursive DTS-like search algorithm] by [[Peter Österlund]], [[CCC]], July 24, 2013 » [[Texel]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2378 DTS-like SMP] by [[Vadim Demichev|ThinkingALot]], [[Computer Chess Forums|OpenChess Forum]], July 25, 2013 » [[GullChess|Gull]]
* [http://www.talkchess.com/forum/viewtopic.php?t=55649 Dynamic Tree Splitting] by [[Syed Fahad]], [[CCC]], March 13, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56019 Empirical results with Lazy SMP, YBWC, DTS] by [[Kai Laskos]], [[CCC]], April 16, 2015 » [[Lazy SMP]], [[Young Brothers Wait Concept|YBWC]]
=External Links=
* [http://www.craftychess.com/hyatt/search.html The DTS high-performance parallel tree search algorithm] by [[Robert Hyatt]]
* [[Videos#PorcupineTree|Porcupine Tree]] - [https://en.wikipedia.org/wiki/Octane_Twisted Octane Twisted] (2012), recorded at [https://en.wikipedia.org/wiki/Riviera_Theater Riviera Theatre], [https://en.wikipedia.org/wiki/Chicago,_Illinois Chicago], April 30, 2010, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=LR-ikN7K8TM|alignment=left|valignment=top}}
=References=
<references />
'''[[Parallel Search|Up one level]]'''
