Re: [Nomen-dev] Cilk

[Brian H. <bh...@sp...>]

On Thu, 11 Apr 2002, Denis wrote:

> > 1) Their response to data race conditions is the same as the old joke
> > "Doctor, it hurts when I do this!"  "Well, don't do that, then!"  
> 
> Yes, their lock system is not very integrated. Do you think it 
> can't be further improved?

Within the framework of cilk, not signifigantly.  Within Nomen, 
definately.

> 
> >
> > 2) Their model of multithreading doesn't provide real 
> > asynchronicity, or any sort of latency bounding.  
> 
> I agree totally with the above paragraph. What you want to do with 
> this kind of multithreading is computation.

Yes.  I am mildly surprised this language isn't more widely used for
numerical programming.  I mean, being able to scale a computation
effectively to hundreds of processors, and still run on a single processor
system with only a tiny performance hit over optimal single-processor
performance, all with the same binary!  And it has a very small learning
curve for any programmer who already knows C.  And there is a beta version
that parallelizes the problem over a distributed network (Beowulf
cluster), which for some inexplicable reason is abandonware.

> Can't we get rid of old-school threads? 

That's what I'm batting around.  I really dislike all the current 
"solutions".

Actually, there are two levels to this.  In one sense, the answer is an 
unequivicable "no".  Threads are a model of SMP computation in the same 
way that C pointer arithmetic is a model of CPU address computation.  This 
is how things work on a low level.  Note that Cilk uses POSIX threads.

However, the fact that the underlying system uses these semantics doesn't 
mean we have to export them- just like Java did away with C's concept of 
pointer arithmetic.  The question then becomes what model do we present to 
the programmer?



> Maybe using constraint 
> programming... I knew of a language that had constraint programming 
> right but I can't find its name again. You could define 
> function-like structures containing a list of affectations, and at 
> each iteration the value of left-hand sides was updated. You used 
> "pre" to get the value of last iteration.
> 
> Something like:
> 
> fun fib(n)
> 	f0 = 1
> 	f1 = 1
> 	i = pre i + 1 | 1
> 	f = (if i = 0 then f0) | (if i = 1 then f1) | pre f + pre pre f
> 	fib = (if i = n then f)
> end
> 
> I forgot the details...

This actually looks vaguely like OCAML or the other functional languages 
(which derive from lisp in the same way that Java derives from Algol).  
I've looked at them- not enough to "get it" (i.e. become an apostle) but 
enough to draw some conclusions (not that I can't draw conclusions from no 
data whatsoever, but...).

One conclusion I've come to is that functional languages don't allow 
implicit multithreading, any more than procedural languages like C and 
Pascal, or Object Oriented languages like Java and Python, do.  Well, they 
make things a little bit easier, as the analysis of what data objects this 
code branch will/can touch a little easier (except most of the functional 
languages have OO or procedural extensions, which raise all the old 
problems).

Frankly, I'm convinced that we will never be able to find signfigant 
parallelism in the compiler.  The program has to be written parallel by 
the programmer.

> Anyway the interest of this approach is that a condition can be 
> fulfilled at any time and the treatement follows, making it 
> suitable for GUIs (seems to me).

Hmm.  Here's an idea.  It's not perfect, but it fixes some of the 
problems.  OK, cilk has the idea of a "work unit"- which is generally just 
a single procedure.  It calls/spawns other work units.  With cilk, only 
the current work unit can insert new work units into the stack of work 
units pending completion.  What if external things could insert work 
units?

Basically, what we're talking about here are signals.  But not classic 
POSIX/Unix signals- which suffer many of the same problems of threading 
due to their asynchronicity (they mimic the effect of interrupts).  
Instead we're talking about cooperatively scheduled signals.  We're 
inserting threads into the work flow dynamically.  Now, so long as you 
don't have an excessive amount of time between thread spawning and sync 
statements, you have something approaching dynamic.

So you spawn off factorALargeNumber(), which starts spawning off more 
threads, etc.  Several seconds later, it has several CPUs all off cranking 
on factoring that large number, when the user hits "cancel".  The GUI 
inserts a new work unit, one not comming out of factorALargeNumber().  All 
this work unit does is a cilk abort- which doesn't kill the whole process, 
it just kills off all the outstanding cilk work units.

Hmm.

Brian