Parallelograms

Here’s some Diagrams of Parallel Processing Code! Parallel-o-grams! Get it?!?

MS recently published an article containing a whole bunch of example applications using the parallel processing framework available in .NET 4.0. I decided to parse out a few examples along with some speed comparisons.

BabyNames

Here’s an example LINQ query against an array of baby names. This query takes about 4 seconds to execute on 3 million records.

1
2
3
4
5
6
7
_sequentialQuery = from b in _babies
    where b.Name.Equals(_userQuery.Name,
          StringComparison.InvariantCultureIgnoreCase) &&
        b.State == _userQuery.State &&
        b.Year >= YEAR_START && b.Year <= YEAR_END
    orderby b.Year
    select b;

Here’s the contrasting Parallel-LINQ query. This query takes 2.25 seconds (1.81 times faster!) against the same 3 million records on a dual-core processor.

1
2
3
4
5
6
7
8
_parallelQuery = from b in _babies.AsParallel()
      .WithDegreeOfParallelism(numProcs)
    where b.Name.Equals(_userQuery.Name,
          StringComparison.InvariantCultureIgnoreCase) &&
        b.State == _userQuery.State &&
        b.Year >= YEAR_START && b.Year <= YEAR_END
    orderby b.Year
    select b;

ComputePi

Calculating Pi using various parallel approaches with 100 million execution cycles. For comparison, the LINQ and For Loop methods took 6 and 2.2 seconds respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//ParallelEnumerable - 3.7 seconds
return (from i in ParallelEnumerable.Range(0, num_steps)
    let x = (i + 0.5) * step
    select 4.0 / (1.0 + x * x)).Sum() * step;

//Parallel.For - 1.14 seconds
Parallel.For(0, num_steps, () => 0.0, (i, state, local) =>
{
    double x = (i + 0.5) * step;
    return local + 4.0 / (1.0 + x * x);
}, local => { lock (monitor) sum += local; });
return step * sum;

//Parallel.ForEach and Parallel.Partitioner - 1.27 seconds
Parallel.ForEach(Partitioner.Create(0, num_steps), () => 0.0, (range,
  state, local) =>
{
    for (int i = range.Item1; i < range.Item2; i++)
    {
        double x = (i + 0.5) * step;
        local += 4.0 / (1.0 + x * x);
    }
    return local;
}, local => { lock (monitor) sum += local; });
return step * sum;

Strassens

There’s good examples of using parallel Task objects to break out a recursive algorithm in this project, but it has to do with matrix calculations and is horribly complex. I’ll just summarize here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//serial way - about 0.84 seconds
private void MultiplyMatrix_Serial(arguments)
{
    //calculations
    MultiplyMatrix_Serial(recursiveCallArguments);
}

//parallel way - about 0.47 seconds on dual-core
private void MultiplyMatrix_Parallel(arguments)
{
    //calculations
    //this will execute the task on whatever core is free
    Task.Factory.StartTask(() =>
      MultiplyMatrix_Parallel(recursiveCallArguments));
}

You’ll notice most of the time measurements note that I’m on a dual-core PC – as more cores (or processors) are available, the more tasks can be run at the same time, which increases the speed even more! The addition of the .NET 4.0 Parallel Framework makes parallel processing ridiculously easy, especially if you already have existing LINQ or recursive calls. Do keep in mind though that just like moving to a multi-threaded app, you have to watch what threads/tasks alter what variables, otherwise you might get results or errors you didn’t expect.

Comments