<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
<title></title>
</head>
<body text="#000000" bgcolor="#ffffff">
W dniu 2010-09-18 18:55, Mattias Gaertner pisze:
<blockquote cite="mid:20100918185509.22cb7a35@limapholos.matom.wg"
type="cite">
<pre wrap="">On Sat, 18 Sep 2010 18:08:09 +0200
Dariusz Mazur <a class="moz-txt-link-rfc2396E" href="mailto:darekm@emadar.com"><darekm@emadar.com></a> wrote:
</pre>
<blockquote type="cite">
<pre wrap=""> W dniu 2010-09-17 17:49, Mattias Gaertner pisze:
</pre>
<blockquote type="cite">
<pre wrap="">On Fri, 17 Sep 2010 14:09:59 +0200
Dariusz Mazur<a class="moz-txt-link-rfc2396E" href="mailto:darekm@emadar.com"><darekm@emadar.com></a> wrote:
</pre>
<blockquote type="cite">
<pre wrap="">[...]
Whats about CILK <a class="moz-txt-link-freetext" href="http://en.wikipedia.org/wiki/Cilk">http://en.wikipedia.org/wiki/Cilk</a>
|_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;
|
</pre>
</blockquote>
<pre wrap="">Have you noticed that most examples for multi threading are either
- easy to understand, but completely impractical (the above is an
order of magnitude slower than single threaded)
</pre>
</blockquote>
<pre wrap="">I don;t agee. First with CILK approach we deal with task, not threads.
Thus we need good task passing to workers.
But seems, that this approach will be faster because on each SPAWN
invoke we add only task (and this is very simple and short function, as
add to FIFO queue)
And each worker (worker count is similar to cores) find task to do. Even
when task are very different (shorter and longer) gueue pass task to
worker with balancing . Why You think this will be magnitude slower I
don't know.
</pre>
</blockquote>
<pre wrap="">
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.
</pre>
</blockquote>
<br>
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. <br>
Its simple example to show, that CILK can play with recurrence (even
with one invoke) . 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).<br>
<br>
<br>
<br>
<br>
<br>
<blockquote cite="mid:20100918185509.22cb7a35@limapholos.matom.wg"
type="cite">
<pre wrap="">
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">- OR practical, but hard to understand
?
Note: afaik CILK is the same as parallel loops:
</pre>
</blockquote>
<pre wrap="">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.
</pre>
</blockquote>
<pre wrap="">
And how does CILK solve this?
</pre>
</blockquote>
<br>
Pass task to workers. Each SPAWN start new task. <br>
But good implementation of background is needed.<br>
<br>
Its very similar to thread model, but not so heavy. Even short task
can be computed efficiently <br>
<br>
CILK has different attempt to task scheduling., its fullfil <font
class="fixed_width" face="Courier, Monospaced">Work-requesting
idea from</font><br>
<a class="moz-txt-link-freetext" href="http://groups.google.com/group/lock-free/browse_frm/thread/18f90bdd8c721880">http://groups.google.com/group/lock-free/browse_frm/thread/18f90bdd8c721880</a><br>
<br>
More on CILK documentation, I;m to weak in english.<br>
<br>
<blockquote cite="mid:20100918185509.22cb7a35@limapholos.matom.wg"
type="cite">
<pre wrap="">
</pre>
<blockquote type="cite">
<pre wrap="">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)
</pre>
</blockquote>
<pre wrap="">
Ehm, you know that parallel loops normally use thread pools, do you?
</pre>
</blockquote>
Thats resolved only one problem.<br>
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.<br>
<br>
<blockquote cite="mid:20100918185509.22cb7a35@limapholos.matom.wg"
type="cite">
<pre wrap="">
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">It allows to make some
special cases need less typing, can increase readability and can
decrease overhead. As always with multithreading: wrongly used it can
make code run much slower.
</pre>
</blockquote>
<pre wrap="">
Multithreading is not only for faster computing.
</pre>
</blockquote>
<pre wrap="">
Does that mean, you agree?
</pre>
</blockquote>
<br>
I don;t agree with statement: multithreading is hard thus we don`t
use them<br>
<br>
<br>
<pre class="moz-signature" cols="72">--
Darek
</pre>
</body>
</html>