W dniu 2010-09-20 09:25, Mattias Gaertner pisze:
On Sun, 19 Sep 2010 22:22:21 +0200
Dariusz Mazur<[email protected]> wrote:
W dniu 2010-09-18 18:55, Mattias Gaertner pisze:
[...]
Whats about CILK http://en.wikipedia.org/wiki/Cilk
|_function_ fib (n: integer):integer;
var
x,y : integer;
begin
if (n< 2) then exit(n)
else begin
x :=_spawn_ fib (n-1);
y := fib (n-2);
_sync_;
exit(x+y);
end;
end;
|
[...]
Only the first 46 Fibonacci numbers fit into an integer, which a
simple loop can compute. I don't know any task scheduler
that produces less enough overhead to compute this faster.
But this is not that case. Its can`t be compared do iteration computing.
We can compare different algorithms. Faster than loop is cons array with
results, but this tell nothing.
Yes, it does:
Before using multi threading, try to use a better single threaded
algorithm. And when comparing multi with single threading speed, you
must not compare a multi threaded algorithm running single threaded, but
a multi threaded algorithm with a good single threaded algorithm.
I don;t talk about best solution of fibbonaci computing. But about
possibility do deal with some class of task using multithreading.
Its easy imagine task, which is hard to resolve with loops.
Its simple example to show, that CILK can play with recurrence (even
with one invoke).
Yes.
BTW: Same for parallel loops. You can write the above as parallel loop:
...
for i:=0 to 1 paralleldo begin
if i=0 then x := fib (n-1)
else y := fib (n-2);
end;
exit(x+y);
...
I doubt this run. Very soon you receive lack of threads. Second this two
iteration has very different time of computing.
I don;t know approach, that balance this.
Third: readability is poor.
On real programs are many plays, that can be done
concurrency, but when its to short, overhead in classic thread model is
too big (computing or programing time).
- OR practical, but hard to understand
?
Note: afaik CILK is the same as parallel loops:
No. On loop we divide iterations on start loops. When each iteration has
different time of computing, we lost concurrence, because one thread
finish, but rest work.
And how does CILK solve this?
Pass task to workers. Each SPAWN start new task.
But good implementation of background is needed.
Its very similar to thread model, but not so heavy. Even short task can
be computed efficiently
CILK has different attempt to task scheduling., its fullfil
Work-requesting idea from
http://groups.google.com/group/lock-free/browse_frm/thread/18f90bdd8c721880
That's an implementation detail.
This is not detail, but quite different attempt.
Parallel loops implementations can use
this too. There are for example plugins for OpenMP using work stealing.
Probably some use some form of work requesting too.
OpenMP is heavy framework, not suitable to all area. Some need something
light. But as You notice, work stealing is not useless. Am best with
strong integration with FPC.
More on CILK documentation, I;m to weak in english.
Second: we not initialize thread on SPAWN (with
loops threads are initializing on start loop), Workers wait for task on
idle. Push and pop task from queue can be very fast. Of course this
depend on implementation (for example each worker should deal with own
queue, but should be possibility to draw task form other queue, this
approach is faster than single MPMC FIFO queue)
Ehm, you know that parallel loops normally use thread pools, do you?
Thats resolved only one problem.
Thread switching is done slowly (less than 100Hz) and rather expensive,
thus we cant start one thread per iteration. We should a priori pass
iteration to threads.
Of course. I don't know any parallel loop implementation starting one
thread per iteration (only in extreme cases).
But CILK can effective play with this.
--
Darek
--
_______________________________________________
Lazarus mailing list
[email protected]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
