ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Is there such a thing as branchless move generation?
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
John Hamlen



Joined: 18 Feb 2012
Posts: 25
Location: United Kingdom
PostPost subject: Re: Is there such a thing as branchless move generation?    Posted: Sat Jun 09, 2012 2:43 pm Reply to topic Reply with quote
Daniel Shawul wrote:
Listen to Sven. You are getting wrong advice here. I don't know if you just want to write a 100% branchless code or write a real chess engine ,but that is the least of your concerns. Say I give you a 100% branchless code, then what? The threads are going to execute different search threads anyway. 0x88 requires piece lists too, have you thought about where you are going to store those and the generated moves. This is just a bad advice sorry. Try bitboards (kogge-stone or not) doesn't really matter but atleast you won't spend your time optimizing something you don't need later. You are not going to do any real SIMD instruction on them. Plus there is no requirement that the code be branchless (even if it is possible). Warps don't just sit idle like cpus do when a branchless code is encountered. Other warps are scheduled for execution thus you can get your occupancy higher this way.


Hi Daniel. Really pleased to see you chipping in as, from looking at other posts on the forum - you and Srdja Matovic are actively coding chess on GPUs. Was hoping that you and/or Srdja would join.

I must say say that I'm still very pleased with Edmund's (and everyone else's) advice but probably need to explain a bit more background so you know where I'm coming from and also to answer your questions in the process. I posted a longer, question before this one but deleted it because it was just too big a brain dump of all the questions in my head for anyone to have a realistic chance of answering ... so no-one did Smile. This branchless movegen query was just one of them!

Daniel Shawul wrote:

I don't know if you just want to write a 100% branchless code or write a real chess engine ,but that is the least of your concerns.

Yes and yes. I'm looking to run branchless code on the GPU to run monte-carlo simulations (which is why I'm so pleased you've joined the thread!) and - if successful and promising, I'll write a chess engine to run on the host CPU(s).

Daniel Shawul wrote:

Say I give you a 100% branchless code, then what? The threads are going to execute different search threads anyway.

I definitely don't want anyone to give me any branchless code, especially not you because I'd that your code is going to be rather elegent as you've already been coding in this MC/chess/GPU space for a while. Nothing worse than seeing really good code and then trying to clear it out of your mind and do your own thing Sad. The search threads and all intelligence will be on the host.

Daniel Shawul wrote:

0x88 requires piece lists too, have you thought about where you are going to store those and the generated moves.

Only need to store one movelist per core, or just one move if I can figure out how to generate one random move, rather than generate all moves and pick one from the list. So hoping that it/they will fit in register/local/L1 (?) (Still learning about how GPU memory models work.

Daniel Shawul wrote:

Try bitboards (kogge-stone or not) doesn't really matter but atleast you won't spend your time optimizing something you don't need later. You are not going to do any real SIMD instruction on them.

Plan at the moment is to forget about the host search for the moment and just see if I can write and optimise a MC simulation engine that will run on a GPU. So the idea is indeed to see if I can run fully SIMD and keep all units occupied until the final gather operation. Re: bitboards. My ancient chess program (Woodpusher) uses these, so they are within my comfort zone but, even though things seem to have moved on a lot in this space, they still appear to rely rather a lot on big table lookups which - from what I've learned so far about GPU computing - seems to be a real no-no as far as performance is concerned because of the huge latency of global memory access. So I was very happy to get the following response from my old friend Gerd:
Gerd Isenberg wrote:
Direction-wise move generation can be done almost branchless without any lookups but pure SIMD register computation with fill algorithms aka Kogge-Stone for sliding piece attacks.


However, it's not immediately obvious to me how the Koggie-Stone methods work and how I can map them to branchless code. I feel that I need to walk before I run, so Edmund's post was very welcome! I haven't written a line of chess code since 1997 (Woodpusher) or a line of Monte-Carlo simulation code since 2004 (DumbGo), so 0x88 appears to be a nice introduction back into the world of coding, and I can see how it maps easily to a pure, branchless SIMD model. If I can get that running, I can then use that as a stepping stone (pardon the pun) to Koggie-Stone. What do you think.

Many thanks,
John
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
Is there such a thing as branchless move generation? John Hamlen Thu Jun 07, 2012 7:50 pm
      Re: Is there such a thing as branchless move generation? Gerd Isenberg Thu Jun 07, 2012 8:44 pm
            Re: Is there such a thing as branchless move generation? John Hamlen Thu Jun 07, 2012 10:18 pm
      Re: Is there such a thing as branchless move generation? Edmund Moshammer Thu Jun 07, 2012 10:57 pm
            Re: Is there such a thing as branchless move generation? John Hamlen Fri Jun 08, 2012 8:21 am
                  Re: Is there such a thing as branchless move generation? Sven Schüle Fri Jun 08, 2012 9:21 am
                        Re: Is there such a thing as branchless move generation? John Hamlen Fri Jun 08, 2012 10:31 am
                              Re: Is there such a thing as branchless move generation? Edmund Moshammer Fri Jun 08, 2012 10:41 am
                                    Re: Is there such a thing as branchless move generation? John Hamlen Sat Jun 09, 2012 1:17 pm
                              Re: Is there such a thing as branchless move generation? Daniel Shawul Fri Jun 08, 2012 11:12 am
                                    Re: Is there such a thing as branchless move generation? Edmund Moshammer Fri Jun 08, 2012 11:18 am
                                          Re: Is there such a thing as branchless move generation? Daniel Shawul Fri Jun 08, 2012 3:39 pm
                                                Re: Is there such a thing as branchless move generation? Vincent Diepeveen Sat Jun 16, 2012 9:07 am
                                                      Re: Is there such a thing as branchless move generation? Daniel Shawul Sat Jun 16, 2012 11:27 am
                                                            Re: Is there such a thing as branchless move generation? Vincent Diepeveen Sat Jun 16, 2012 11:35 am
                                    Re: Is there such a thing as branchless move generation? John Hamlen Sat Jun 09, 2012 2:43 pm
                                          Re: Is there such a thing as branchless move generation? Daniel Shawul Sat Jun 09, 2012 6:02 pm
                                                Re: Is there such a thing as branchless move generation? John Hamlen Sun Jun 10, 2012 2:21 pm
                                                      Re: Is there such a thing as branchless move generation? Daniel Shawul Sun Jun 10, 2012 6:33 pm
                                                            Re: Is there such a thing as branchless move generation? Daniel Shawul Sun Jun 10, 2012 7:16 pm
                                                                  Re: Is there such a thing as branchless move generation? Edmund Moshammer Sun Jun 10, 2012 9:24 pm
                                                                        Re: Is there such a thing as branchless move generation? Daniel Shawul Sun Jun 10, 2012 9:54 pm
                                                                  Re: Is there such a thing as branchless move generation? John Hamlen Sun Jun 10, 2012 10:14 pm
                                                                        Re: Is there such a thing as branchless move generation? Daniel Shawul Mon Jun 11, 2012 12:49 am
                                                                              Re: Is there such a thing as branchless move generation? John Hamlen Mon Jun 11, 2012 12:43 pm
                                                                                    Re: Is there such a thing as branchless move generation? Daniel Shawul Mon Jun 11, 2012 2:41 pm
                                                                                          Re: Is there such a thing as branchless move generation? John Hamlen Mon Jun 11, 2012 10:12 pm
                                                                                          Re: Is there such a thing as branchless move generation? Daniel Shawul Mon Jun 11, 2012 11:12 pm
                                                                                          Re: Is there such a thing as branchless move generation? John Hamlen Mon Jun 11, 2012 11:41 pm
                                                                        Re: Is there such a thing as branchless move generation? Vincent Diepeveen Sat Jun 16, 2012 9:56 am
                                                            Re: Is there such a thing as branchless move generation? John Hamlen Sun Jun 10, 2012 10:58 pm
                                          Re: Is there such a thing as branchless move generation? Gerd Isenberg Sat Jun 09, 2012 7:48 pm
                                                Re: Is there such a thing as branchless move generation? John Hamlen Sun Jun 10, 2012 5:28 pm
            Re: Is there such a thing as branchless move generation? Edmund Moshammer Fri Jun 08, 2012 10:32 am
                  Re: Is there such a thing as branchless move generation? John Hamlen Sat Jun 09, 2012 2:57 pm
                  Re: Is there such a thing as branchless move generation? Vincent Diepeveen Sat Jun 16, 2012 8:57 am
      Re: Zeta CL uses Magic Bitboards Srdja Matovic Mon Jun 11, 2012 2:53 pm
            Re: Zeta CL uses Magic Bitboards Gerd Isenberg Mon Jun 11, 2012 8:55 pm
                  Re: Zeta CL uses Magic Bitboards Srdja Matovic Mon Jun 11, 2012 9:35 pm
                        Re: Zeta CL uses Magic Bitboards Daniel Shawul Mon Jun 11, 2012 11:26 pm
                              Re: Zeta CL uses Magic Bitboards Srdja Matovic Tue Jun 12, 2012 1:16 am
                              Re: Zeta CL uses Magic Bitboards Gerd Isenberg Tue Jun 12, 2012 6:58 am
                                    Re: Zeta CL uses Magic Bitboards Daniel Shawul Tue Jun 12, 2012 1:46 pm
                                          Re: Zeta CL uses Magic Bitboards Srdja Matovic Tue Jun 12, 2012 2:35 pm
                                                Re: Zeta CL uses Magic Bitboards Daniel Shawul Tue Jun 12, 2012 4:37 pm
                                                      Re: Zeta CL uses Magic Bitboards Vincent Diepeveen Sat Jun 16, 2012 8:46 am
                                                            Re: Zeta CL uses Magic Bitboards Daniel Shawul Sat Jun 16, 2012 11:17 am
                                                                  Re: Zeta CL uses Magic Bitboards Vincent Diepeveen Sat Jun 16, 2012 11:30 am
                                                                        Re: Zeta CL uses Magic Bitboards Daniel Shawul Sat Jun 16, 2012 1:56 pm
                                                                              Re: Zeta CL uses Magic Bitboards Vincent Diepeveen Sat Jun 16, 2012 2:51 pm
                  Re: Zeta CL uses Magic Bitboards vs Kogge-Stone Srdja Matovic Tue Jun 12, 2012 1:05 am
                        Re: Zeta CL uses Magic Bitboards vs Kogge-Stone Gerd Isenberg Tue Jun 12, 2012 6:31 am
            Re: Zeta CL uses Magic Bitboards John Hamlen Mon Jun 11, 2012 10:35 pm
                  Re: Zeta CL uses Magic Bitboards Daniel Shawul Mon Jun 11, 2012 11:00 pm
      Re: Is there such a thing as branchless move generation? Vincent Diepeveen Sat Jun 16, 2012 8:40 am
      Re: Is there such a thing as branchless move generation? Vincent Diepeveen Sat Jun 16, 2012 9:23 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads