YBWC implementation questions

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Patrice Duhamel
Posts: 133
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

YBWC implementation questions

Post by Patrice Duhamel » Sat Aug 26, 2017 9:02 am

I am trying to add the YBWC in my engine, and I have a problem with data structures.

I have a global lockless hash table, killers, history and pawn hash table will be declared for each threads, but I don't understand how many elements I need to allocate for board positions, moves lists, pv, and repetitions.

Looking at Viper source code, I see that each thread have an array with a maximum number of split points, but I am not sure to understand why in the split_point_t structure, position_t, search_stack_t, move_stack_t are declared for each threads ?
Is it possible to allocate less elements ?

jdart
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: YBWC implementation questions

Post by jdart » Sun Aug 27, 2017 4:10 pm

You are going to need a fair number of data structures.

Each searching thread has its own stack that maintains move history.

Each searching thread also has a split point stack. This is used to keep track of the places within that thread's execution where a split has occurred. One reason you need this is the rule that a thread that has spawned child threads but is now idle, because its own work has completed, can only be allocated again to help complete work that its own child threads have started.

I have implemented this but I am not sure my code is a model of clarity. It has some comments that might be helpful though:

https://github.com/jdart1/arasan-chess.

--Jon

Patrice Duhamel
Posts: 133
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

Re: YBWC implementation questions

Post by Patrice Duhamel » Sun Aug 27, 2017 6:16 pm

jdart wrote: Each searching thread has its own stack that maintains move history.
I need only one stack for move history by thread, or one stack for move history at each new thread assigned to a split point ?
jdart wrote: I have implemented this but I am not sure my code is a model of clarity. It has some comments that might be helpful though:
https://github.com/jdart1/arasan-chess.
Thanks, I will try to look at Arasan source code.

jdart
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: YBWC implementation questions

Post by jdart » Sun Aug 27, 2017 9:44 pm

I need only one stack for move history by thread, or one stack for move history at each new thread assigned to a split point ?
I have a Search class, one per thread. That contains the stack.

--Jon

Patrice Duhamel
Posts: 133
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

Re: YBWC implementation questions

Post by Patrice Duhamel » Mon Aug 28, 2017 4:39 pm

jdart wrote: I have a Search class, one per thread. That contains the stack.
Sorry I didn't explain my problem very well.

In Arasan, before calling your searchSMP() function, you allocate a NodeInfo array (in the thread stack memory).
If I want to allocate all data for the NodeInfo arrays outside of the thread idle loop, at the start of the program (in the heap),
how many elements I will need ?

Is it possible in a search that all threads are working and have all created their maximum number of split points ?

jdart
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: YBWC implementation questions

Post by jdart » Mon Aug 28, 2017 10:48 pm

you allocate a NodeInfo array (in the thread stack memory)
You want it in the thread stack memory, because of the "first touch" rule (the first access to the memory causes the page to be allocated in the memory local to the thread that is accessing it). In a NUMA system locality is important.

Re your other question: I think it is rare that the split stack is full. But if this worries you can always increase the size.

--Jon

Patrice Duhamel
Posts: 133
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

Re: YBWC implementation questions

Post by Patrice Duhamel » Tue Aug 29, 2017 4:40 pm

jdart wrote: You want it in the thread stack memory, because of the "first touch" rule (the first access to the memory causes the page to be allocated in the memory local to the thread that is accessing it). In a NUMA system locality is important.
Thanks for your help.

I will use the thread stack memory.

Post Reply