PV split algorithm

Code, algorithms, languages, construction...

PV split algorithm

Postby JacobusOpperman » Mon Apr 27, 2015 1:22 pm

Hi
I have written a small chess engine called Alcatraz in Delphi. Recently I have used the pv split algorithm to optimize it for a duo core computer. The parallel searh performs about 40% worse than the serial search and I obviously don't get the 1.8x improvement reported in the literature. I understand the logic behind the pv split algorithm and my program doesn't crash. The way I understand the pv split algorithm is: you search the leftmost branches of the game tree to the horizon depth until you get the principal variation, with one processor, and from thereon the rest of the game tree is searched in parallel with 2 processors. Is it true that you have to create a new thread for most of the nodes of the game tree? My question is: With so many threads running, is the problem not with Windows that it can't deal effectively with the threads and is there not some trick that you can implement to help Windows deal more effectively with all the threads? I am using Windows Vista.
Jacobus Opperman
JacobusOpperman
 
Posts: 6
Joined: Mon Apr 27, 2015 12:35 pm

Re: PV split algorithm

Postby User923005 » Tue Apr 28, 2015 12:44 am

If you start more threads than you have physical cores, there will be a terrible drop-off in performance.
With hyperthreading, you can start up to the virtual core count, but it is less efficient than if the processor were not in hyperthreading mode.
User923005
 
Posts: 606
Joined: Thu May 19, 2011 1:35 am

Re: PV split algorithm

Postby JacobusOpperman » Tue Apr 28, 2015 7:53 am

Thank you User923005 for your reply.
Yes I think I create too many threads for too little processors - I basically create a new thread for most of the nodes of the game tree - for everywhere that the game tree splits. I now think I must try to implement the PV split algorithm with only two threads - the main thread and a secondary thread and use global variables to communicate between the two threads.
JacobusOpperman
 
Posts: 6
Joined: Mon Apr 27, 2015 12:35 pm


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 2 guests

cron