[Nomen-dev] Cilk as continuations
Brought to you by:
bhurt
|
From: Brian H. <bh...@sp...> - 2002-04-23 16:00:23
|
Another postcard from the deep weeds.
Continuations are a deep idea. Quickie introduction to continuations as I
understand them. When, in C, we call a function, the program passes in,
in addition to the arguments the function itself needs, also a return
address and stack frame address to return *to*. OK, generally the stack
frame on return is calculated from the current stack frame, but we can
consider it implicitly passed in. When the function exits, it gotos that
return address and return stack frame (conceptually).
The returning function doesn't have to return from whence it came. It can
return to an entirely different point. Actually, often times C compilers
will do this. In GCC, for example, if you have code like:
void bar(void) {
...
}
void foo(...) {
...
bar();
}
Gcc will produce code like:
.globl bar
bar:
...
ret
.globl foo
foo:
...
jmp bar
I.e. it'll thread the calls and eliminate the unnessecary call/return
pair.
Continuations just make this obvious and visible to the programmer.
Instead of the return address being implicit and dealt with by the
program, they are passed in explicitly.
Cilk is just a specific use of continuations. The act of spawning a
thread in Cilk is just putting two continuations on the runnable stack at
the same time. Since a continuation includes both the location to start
executing and the environment (stack frame) to execute within, the
differing continuations can be moved from one thread to the next with
little trouble. This is what Cilk does.
Cilk gaurentees a certain relationship between cilk-threads. When thread
A spawns thread B, thread B starts executing immediately. What if,
instead, we look at it the following way: we now have two runnable
continuations, A and B, and the scheduler picks between them. This would
allow the introduction of "third source" runnable continuations into the
environment.
This is what I was hinting at earlier. The "thread" to handle the user
clicking on the cancel button is just onther continuation to be executed.
So now we have three runnable continuations- compute threads A and B, and
user interface handler thread C. If thread schedule points happen often
enough, this is sufficient.
So the question is, how to make sure thread schedule points happen often
enough? Every function call is too often, especially as all non-local
variable accesses are implicitly function calls to accessors. Some larger
chunk is necessary.
Another idea I've been playing with: lock recovery codelets. Basically,
every lock is "breakable". When the run time environment gets a lock, it
passes in a pointer to a codelet to run when the lock is broken.
Basically, add transactions to the language, with commit and rollback.
I'd have to think about how this would work.
Brian
|