undefined | Better HN

0 pointsot14y ago0 comments

Cilk is definitely more than syntactic sugar.

How would you implement work-stealing in pure C?

0 comments

3 comments · 1 top-level

lukesandberg14y ago· 2 in thread

I've done it. You need hardware support to do it without locks. Here is a paper describing an implementation using CAS http://www.cse.chalmers.se/~tsigas/papers/JPDC-Lock-free-ski...

in order to do work stealing in general you just need to organize your computations into tasks. Having a language that supports closures (or a similar thing) makes it easier, but it is not neccesary because you can just use function pointers to define tasks (and some kind of struct to pass args)

marshray14y ago

That is awesome.

I've been using g++-4.6 lately and with the new lambdas I'm migrating more and more to this async task application model.

One point that seems frequently understated with the lamentations about the absence of a true double-pointer-sized DCAS is that on machines with a 64 bit CAS (e.g. x86 and x64) you could still implement something useful CAS on pairs of 32-bit handles.

2^32 concurrent work items "ought to be enough for anybody", right? :-) Well, it might be useful to those of us with less than 100 GB of RAM.

lukesandberg14y ago

Luckily these days people are designing algorithms/data structures that don't rely on DCAS :) So you can actually implement them on real hardware

1 more reply

j / k navigate · click thread line to collapse