Spawn function

Spawn function

Imagen de newport_j

In the current programmer's Guide on page 44 it seems that one is spawing one half of the function. What is the logic here?

void run_loop(first, last)
{
if (last -first) < grainsize
}
for (int i=first, i < last ++i) LOOP_BODY;
{
else
{
int mid = (last - first)/2;
cilk_spawn run_loop(first, mid);
run_loop(mid, last);
}
}

It seems that the spawn is only going part (half) way.

Again from the line that spawn's a function it seems that you are only spawning a finction from the first to the mid. Then you are going back to the normal functionat the next line.

run_loop(mid, last);

I do not see the logic.

Newport_j

publicaciones de 4 / 0 nuevos
Último envío
Para obtener más información sobre las optimizaciones del compilador, consulte el aviso sobre la optimización.
Imagen de William Leiserson (Intel)

The second recursive call does not need to be spawned. You can spawn it if you like, but since Cilk++ steals continuations, and since there is nothing to do after the second recursive call (except sync), there is no point to spawning it.

The key concept in Cilk++ is that when you spawn, you are creating opportunities for parallel work. But the opportunity is actually the point immediately after the spawn.

I.e.,

Function A spawns function B. The worker that was running function A immediately begins executing function B as though it had simply called it. Another worker comes along looking for work to do and actually steals function A out from under B and begins executing it where the first worker left off.

Thus, in the sample code, there is no need to spawn the second recursive call. There would be nothing for another worker to steal.

Imagen de newport_j

Iam trying to Cilkify a discrete event simulation program. These programs are driven by time. I find only a few opportunities to change a for statement to a cilk_for statement.

Thus I am looking at spawning functions. Now discrete event simulation is driven by time;it isvery serial. Time is the driver; so it seems the only possiblity of Cilkify and speed-up is by spawning functions.

It says at one point:

A cilk_spawn keyword modifies a function call statememnt to tell the Cilk++ runtime system that the funtion may (but is not required to) run in paraellel with the caller.

Now how is the spawn or not to spawn decision made?It is not the programmer that makes this decision.

Newport_j

Imagen de Barry Tannenbaum (Intel)

Remember that the Cilk++ runtime uses work-stealing to distribute the work. When your application starts running, only the initial worker has anything to do. The other workers are randomly choosing a victim worker and attempting to steal work it. The basic loop inside the runtime is

while (! shutdown)
{
 select a victim worker at random;
 if (succeed in stealing work)
 do the stolen work;
 else
 yield;
}

Thebeauty of this is that it puts the cost of looking for work on the cores that have nothing better to do.

What the cilk_spawn does is make the continuation of a function (the code after the cilk_spawn'd call) available for stealing.

So the programmer decides what code *can* run in parallel, and the runtime decides what *actually* runs in parallel, based on the available resources. As a rough guide, you should aim for about 10x the number of parallel strands (the code that can run in parallel) as the number of processors. This level of breakup allows the runtime to deal with inconsistently sized strands, and also allows your program to work well if more processors are available.

- Barry

Inicie sesión para dejar un comentario.