Cilk++

[Gerd Isenberg]

We may soon use Cilk++ inside Intel's Parallel Studio, see Dr. Dobb's. What is the expert's opinion on using Cilk++ for parallel alpha-beta?

[Dan Andersson]

There is old data if we look at StarTech, *Socrates anc CilkChess performance and papers.

MvH Dan Andersson

[Gian-Carlo Pascutto]

We may soon use Cilk++ inside Intel's Parallel Studio, see Dr. Dobb's. What is the expert's opinion on using Cilk++ for parallel alpha-beta?

The original Cilk was designed for parallelizing alpha-beta, so it should be pretty good.

I had some issues with the structure, iirc there were restrictions such as Cilk functions can only call Cilk functions which made using it a pain.

If those are lifted this could be quite interesting.

[Aaron Becker]

The thing that makes Cilk good for problems like this is its work-stealing scheduler. Since Intel's Threaded Building Blocks also uses a work-stealing scheduler, you might want to take a look there as well. It's a plain C++ library with no language extensions, but the concepts involved are quite similar.

[Rein Halbersma]

The thing that makes Cilk good for problems like this is its work-stealing scheduler. Since Intel's Threaded Building Blocks also uses a work-stealing scheduler, you might want to take a look there as well. It's a plain C++ library with no language extensions, but the concepts involved are quite similar.

One important difference between Cilk en Cilk++ is the "abort" keyword. Cilk++ does not (yet) support this, meaning that you have to wait until all threads have synced at a split point. The old Cilk aborted parallel threads whenever a cutoff was found. In the manual they mention that such speculative computing might be supported in future Cilk++ releases.

[Gerd Isenberg]

The thing that makes Cilk good for problems like this is its work-stealing scheduler. Since Intel's Threaded Building Blocks also uses a work-stealing scheduler, you might want to take a look there as well. It's a plain C++ library with no language extensions, but the concepts involved are quite similar.

One important difference between Cilk en Cilk++ is the "abort" keyword. Cilk++ does not (yet) support this, meaning that you have to wait until all threads have synced at a split point. The old Cilk aborted parallel threads whenever a cutoff was found. In the manual they mention that such speculative computing might be supported in future Cilk++ releases.

Thanks, that seems a problem with Cilk++ so far, "abort" is a must, I guess. Why is it not supported in Cilk++, but was in Cilk more than 10 years ago?

[Zach Wegner]

One important thing to note with Cilk is that it requires copy-make rather than make-unmake. So if you have a lot of incrementally updated data for your board structure this might become a bottleneck.

Generally I prefer to have more control on how the search splits, but this should work pretty well for most people. Certainly better than Toga-style parallel algorithms...

[Don]

One important thing to note with Cilk is that it requires copy-make rather than make-unmake. So if you have a lot of incrementally updated data for your board structure this might become a bottleneck.

Generally I prefer to have more control on how the search splits, but this should work pretty well for most people. Certainly better than Toga-style parallel algorithms...

I have programmed in cilk obviously as cilkchess was designed for this.

Cilk does not "require" copy-make, you can do whatever you want. But you have to copy state anyway to pass work to another processor or thread, right? Presumably you just want to copy state only when work is passed on to another thread.

I suggest that for an advanced program you want to get around the idea of the board being in a single global variable that you update and down-date in place with various stacks that basically serve as journals. As you can see that model is already broken somewhat with parallel programming.

But you can still do it in Cilk if you need/want to. It's more flexible than you think. One way is to simply copy state only when you spawn work. Most of this will be uneccesary because the work may not actually get stolen, but it will still be less copying than actually doing this on every move.

But with Cilk you have access to a process number, let's say it's the thread ID although I don't remember what it's called. So you can tag each state with this and make the state copy only when you know that the state has been stolen by another processor or thread.

[Don]

The thing that makes Cilk good for problems like this is its work-stealing scheduler. Since Intel's Threaded Building Blocks also uses a work-stealing scheduler, you might want to take a look there as well. It's a plain C++ library with no language extensions, but the concepts involved are quite similar.

One important difference between Cilk en Cilk++ is the "abort" keyword. Cilk++ does not (yet) support this, meaning that you have to wait until all threads have synced at a split point. The old Cilk aborted parallel threads whenever a cutoff was found. In the manual they mention that such speculative computing might be supported in future Cilk++ releases.

Thanks, that seems a problem with Cilk++ so far, "abort" is a must, I guess. Why is it not supported in Cilk++, but was in Cilk more than 10 years ago?

That is sad news if it's true. It reduces the power of Cilk substantially and I think makes it inappropriate for alpha beta searching.

It was supported in Cilk more than 10 years ago because Cilk development was driven by computer chess. I don't think that is a consideration currently but I don't know - I have not been involved with Cilk for many years. But still I think it would be an important feature for a language specifically designed for parallel programming.

[Don]

We may soon use Cilk++ inside Intel's Parallel Studio, see Dr. Dobb's. What is the expert's opinion on using Cilk++ for parallel alpha-beta?

The original Cilk was designed for parallelizing alpha-beta, so it should be pretty good.

I had some issues with the structure, iirc there were restrictions such as Cilk functions can only call Cilk functions which made using it a pain.

If those are lifted this could be quite interesting.

Let me clarify what you just said, it is easy to mis-parse. You can call non-cilk functions from cilk, you just cannot call cilk functions from non-cilk functions!