C# 3.0 and Parallel FX/LINQ in Mono

For a while I wanted to blog about the open source implementation of the Parallel Extensions for Mono that Jeremie Laval has been working on. Jeremie is one of our mentored students in the 2008 Google Summer of Code.

Update: Jeremie's code is available from our mono-soc-2008 repository.

Dual CPU laptops are becoming the norm; quad-core computers are now very affordable, and eight CPU machines are routinely purchased as developer workstations.

The Parallel Extension API makes it easy to prepare your software to run on multi processor machines by providing constructs that take care of distributing the work to various CPUs based on the computer load and the number of processors available.

There are various pieces in the Parallel Extensions framework, the simplest use case is Parallel.For, a loop construct that would execute the code in as optimally as possible given the number of processors available on the system.

Parallel.For is a simple replacement, you usually replace for loops that look like this:

	for (int i = 0; i < N; i++)
		BODY ();
        

With the following (this is using lambda expressions):

	Parallel.For (0, N, i => BODY);
        

The above would iterate from 0 to N calling the code in BODY with the parameter scattered across various CPUs.

C# 3 and Parallel LINQ

Marek Safar recently announced that Mono C# compiler was now completely compliant with the 3.0 language specification.

In his announcement he used Luke Hoban's brutal ray tracer-in-one-LINQ statement program. This was a hard test case for our C# compiler to pass, but we are finally there. I had blogged about it in the past. Luke Hoban's ray-tracer-in-one-linq-statement looks like this:

var pixelsQuery =
  from y in Enumerable.Range(0, screenHeight)
  let recenterY = -(y - (screenHeight / 2.0)) / (2.0 * screenHeight)
  select from x in Enumerable.Range(0, screenWidth)
    let recenterX = (x - (screenWidth / 2.0)) / (2.0 * screenWidth)
    let point = Vector.Norm(Vector.Plus(scene.Camera.Forward, 
                                        Vector.Plus(Vector.Times(recenterX, scene.Camera.Right),
                                                    Vector.Times(recenterY, scene.Camera.Up))))
    let ray = new Ray { Start = scene.Camera.Pos, Dir = point }
    let computeTraceRay = (Func<Func<TraceRayArgs, Color>, Func<TraceRayArgs, Color>>)
      (f => traceRayArgs =>

        (from isect in
           from thing in traceRayArgs.Scene.Things
           select thing.Intersect(traceRayArgs.Ray)
         where isect != null
         orderby isect.Dist
         let d = isect.Ray.Dir
         let pos = Vector.Plus(Vector.Times(isect.Dist, isect.Ray.Dir), isect.Ray.Start)
         let normal = isect.Thing.Normal(pos)
         let reflectDir = Vector.Minus(d, Vector.Times(2 * Vector.Dot(normal, d), normal))
         let naturalColors = 
           from light in traceRayArgs.Scene.Lights
           let ldis = Vector.Minus(light.Pos, pos)
           let livec = Vector.Norm(ldis)
           let testRay = new Ray { Start = pos, Dir = livec }
           let testIsects = from inter in
                              from thing in traceRayArgs.Scene.Things
                              select thing.Intersect(testRay)
                            where inter != null
                            orderby inter.Dist
                            select inter
           let testIsect = testIsects.FirstOrDefault()
           let neatIsect = testIsect == null ? 0 : testIsect.Dist
           let isInShadow = !((neatIsect > Vector.Mag(ldis)) || (neatIsect == 0))
           where !isInShadow
           let illum = Vector.Dot(livec, normal)
           let lcolor = illum > 0 
             ? Color.Times(illum, light.Color)
	     : Color.Make(0, 0, 0)
           let specular = Vector.Dot(livec, Vector.Norm(reflectDir))
           let scolor = specular > 0 
              ? Color.Times(Math.Pow(specular, isect.Thing.Surface.Roughness), light.Color) 
              : Color.Make(0, 0, 0)
           select Color.Plus(
             Color.Times(isect.Thing.Surface.Diffuse(pos), lcolor),
             Color.Times(isect.Thing.Surface.Specular(pos), scolor))
         let reflectPos = Vector.Plus(pos, Vector.Times(.001, reflectDir))
         let reflectColor = 
           traceRayArgs.Depth >= MaxDepth
           ? Color.Make(.5, .5, .5)
           : Color.Times(isect.Thing.Surface.Reflect(reflectPos), 
                         f(new TraceRayArgs(new Ray { Start = reflectPos, Dir = reflectDir }, 
                                            traceRayArgs.Scene, 
                                            traceRayArgs.Depth + 1)))
         select naturalColors.Aggregate(reflectColor, (color, natColor) => 
             Color.Plus(color, natColor)))
           .DefaultIfEmpty(Color.Background).First())
      let traceRay = Y(computeTraceRay)
      select new { X = x, Y = y, Color = traceRay(new TraceRayArgs(ray, scene, 0)) };

foreach (var row in pixelsQuery)
  foreach (var pixel in row)
    setPixel(pixel.X, pixel.Y, pixel.Color.ToDrawingColor());

And renders like this:

The above now compiles and runs as fast as it does on .NET.

Jeremie then modified the above program to use the parallel extensions to LINQ. He replaced Enumerable.Range with ParallelEnumerable.Range and foreach with the parallel ForAll method to take advantage of his library.

You can watch the above ray tracer with and without LINQ on his screencasts (LINQ ray tracer, Parallel LINQ ray tracer).

Tracking Parallel FX

There is much more information on the PFXTeam Blog. Another great blog to follow, in particular check out their Coordination Data Structures Overview, PLINQ Ordering and some demos.