Author: Gian-Carlo Pascutto
Date: 11:53:40 08/18/03
Go up one level in this thread
On August 18, 2003 at 13:35:00, Sune Fischer wrote: >Don't give him any good ideas, he is your rival! :) > >So your perspective please, on scale from 1 to 10, how hard is it to implement >and "debug", or is it a one time deal, life is peacy, no worries from there on? > >I'm mainly concerned about non thread safe libraries, could be nasty, or what? Probably 11 or 12. I had a fair amount of programming experience before I did it, but this was by and far the hardest thing I have ever done. For starters, there's the issue of getting the thing running parallel. You probably didn't consider parallelism when designing your engine. I guess nobody does except if they've already written one once. So, expect messyness. Non-thread-safe libs shouldn't be an issue. (I don't use libs except for the C library so I wouldn't really know, but I assume that whatever the ones you need do is not something that is critical to the search itself, in which case you can limit their use to a master thread) So, you've got the thing running in parallel. Of course it's totally buggy, but you don't notice that yet. Now you need some kind of algorithm. The ICGA has approximately 2 or 3 articles about parallel algorithms. You can throw the ones about ABDADA, PVS and EPVS in the trash. They promise nice numbers. They work like horsecrap (or a cold shower, if you went to effort to try them. Do a test with Amy first and save disappointment later). The only interesting one is the one about DTS from Robert. If you read it, you're in for another unpleasant surprise. He doesn't describe the algorithm in nearly enough detail to be useful, in fact many important things are missing. Not only that, but there's some nice things in there, like the fact that it only works for nonrecursive search algorithms (aka Stone Age Programming). But what is useful to you is that it is a general description of how a good parallel algorithm could work and the things you'll encounter. Now, get a pencil and paper. Or a whiteboard. Think very very hard about how you want to divide up the tree, what datastructures you will need, and what messy things you can encounter. Make your own algorithm. Try a first implementation. Oops, you forgot a datastructure or you can't handle something you need to be able to handle. Back to the whiteboard. Lather, rinse, repeat. Now, you're done, and you try the first testrun. It crashes before finishing ply 1. Second cold shower: your usual debugging methods are useless now and you are *soo* screwed because it's impossible to reproduce anything (that's nondeterminism for you). Think about a way to debug stuff. Spend time writing the new debug routines. Spend much more time studying large logs for what went wrong. Fix bug. Lather, rinse, repeat. At some point, it works reasonable enough that you can do your first speedup measurements. If your algorithm was reasonable enough, this will already be something decent (e.g. >1.5). Think about improvements. Implement. Crash. Test. Test. Test. Test. Crash. Debug. Test. DOESN'T THAT SOUND LIKE A LOT OF FUN???? Once things are running reasonable enough, I didn't have much problems with parallelism, in the sense that you do have to take it into account when adding stuff to your search, but once you've been to the above, it'll look easy in comparison. I generally ignore all parallel stuff until I know something works well anyway. There's no reason to bother with parallel effects until you know it works, and most stuff I try doesn't work. So no problems there. In Leiden, Frans Morsch said 'Implementing a parallel search takes a year'. I think that's slightly exaggerated, but he programs in assembler, so it won't have been too far off. If you wonder why I bothered to go parallel, I had three consecutive months where I could work fulltime round-the-clock on the engine. I think quite a bit of the above gets much harder when it has the be done in a few hours each evening. So I went ahead with it. I don't regret it, but I wouldn't want to go back either. -- GCP
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.