Parallelizing a loop with tasks, avoiding the pitfall

Tue, October 13, 2009, 02:39 PM under ParallelComputing
Most readers of this blog should know that it is extremely easy to parallelize loops with .NET 4. So serial code performing matrix multiplication like this:
    for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
int tmp = 0;
for (int k = 0; k < size; k++)
{
tmp += m1[i, k] * m2[k, j];
}
result[i, j] = tmp;
}
}
…can be parallelized like this:
      Parallel.For(0, size, (int i) =>
{
for (int j = 0; j < size; j++)
{
int tmp = 0;
for (int k = 0; k < size; k++)
{
tmp += m1[i, k] * m2[k, j];
}
result[i, j] = tmp;
}
});
How about parallelizing the code using Tasks directly (instead of indirectly)? The clever thing to do is somehow partition the data (statically or dynamically) and assign chunks to tasks, but even the naïve approach of one task per outer iteration is better than nothing:
    Task[] tasks = new Task[size];
for (int i = 0; i < size; i++)
{
tasks[i] = Task.Factory.StartNew(() =>
{
for (int j = 0; j < size; j++)
{
int tmp = 0;
for (int k = 0; k < size; k++)
{
tmp += m1[i, k] * m2[k, j];
}
result[i, j] = tmp;
}
});
}
Task.WaitAll(tasks);
Can you see the issue with the code above?

TIP: the issue has nothing to do with tasks, threads or even .NET 4. It has to do with anonymous methods since the day they were introduced. The clue is that the following snippet fixes the issue:
    Task[] tasks = new Task[size];
for (int n = 0; n < size; n++)
{
int i = n;
tasks[n] = Task.Factory.StartNew(() =>
{
for (int j = 0; j < size; j++)
{
int tmp = 0;
for (int k = 0; k < size; k++)
{
tmp += m1[i, k] * m2[k, j];
}
result[i, j] = tmp;
}
});
}
Task.WaitAll(tasks);
If you know the reason please move along. If however this was news to you, go read the entire page (and the outbound links) on stackoverflow.

By the way, we could have fixed the snippet with this approach too, since tasks accept a state parameter:
    Task[] tasks = new Task[size];
for (int i = 0; i < size; i++)
{
tasks[i] = Task.Factory.StartNew(ii =>
{
int iii = (int)ii;
for (int j = 0; j < size; j++)
{
int tmp = 0;
for (int k = 0; k < size; k++)
{
tmp += m1[iii, k] * m2[k, j];
}
result[iii, j] = tmp;
}
}, i);
}
Task.WaitAll(tasks);
More on why you may choose to pass the variable as state instead of capturing it, in a future post.