{"id":2603,"date":"2008-06-04T23:33:00","date_gmt":"2008-06-04T23:33:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/pfxteam\/2008\/06\/04\/ray-tracer-samples-in-the-june-2008-ctp\/"},"modified":"2008-06-04T23:33:00","modified_gmt":"2008-06-04T23:33:00","slug":"ray-tracer-samples-in-the-june-2008-ctp","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/dotnet\/ray-tracer-samples-in-the-june-2008-ctp\/","title":{"rendered":"Ray Tracer samples in the June 2008 CTP"},"content":{"rendered":"

The June 2008 Community Technology Preview (CTP) of Parallel Extensions to the .NET Framework was released on Monday, and we\u2019re really pleased at the level of excitement in the community that we\u2019re seeing in response.  <\/SPAN>As part of the CTP, we included a  <\/SPAN>variety of demos and samples to help provide a tour of the functionality.  <\/SPAN>If you haven’t already, please read the blog entries: <\/FONT>Released! Parallel Extensions to the .NET Framework June 2008 CTP<\/FONT><\/A>, <\/FONT>Known Issues in the June 2008 CTP of Parallel Extensions<\/FONT><\/A>, and <\/FONT>What’s New in the June 2008 CTP of Parallel Extensions<\/FONT><\/A><\/P>\n

In this post, I\u2019m going to explore the four separate ray tracer implementations in the samples that demonstrate how to utilize Parallel Extensions to achieve concurrent rendering (note that the actual ray tracing engine itself is not an optimized implementation, as it is intended more for discussion than performance).  <\/SPAN>There were two forms of the base sequential ray tracer, both developed by Luke Hoban, one written in C# using standard loops and other imperative programming constructs, and another implemented in C# via some huge LINQ queries that define the entire execution (read about this implementation at <\/FONT>https:\/\/blogs.msdn.com\/lukeh\/archive\/2007\/04\/03\/a-ray-tracer-in-c-3-0.aspx<\/FONT><\/A>)<\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

The samples in the CTP extend these examples in the following ways:<\/FONT><\/FONT><\/P>\n

1.<\/FONT>       <\/SPAN><\/SPAN><\/SPAN>The original C# ray tracer is converted to use Parallel Extensions (both the Task Parallel Library and some of the new Coordination Data Structures) to achieve concurrency.  <\/SPAN>This enhanced version was then ported to Visual Basic and F#, demonstrating that Parallel Extensions is usable from any .NET language.  <\/SPAN>See \u2026\\Samples\\RayTracer\\…<\/I><\/FONT><\/FONT><\/P>\n

2.<\/FONT>       <\/SPAN><\/SPAN><\/SPAN>The LINQ-style ray tracer is converted to use PLINQ  <\/SPAN>to achieve concurrency.  <\/SPAN>See \u2026\\Samples\\LINQRayTracer<\/I><\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

These ray tracer samples involve a fair number of concurrency primitives provided by Parallel Extensions:<\/FONT><\/FONT><\/P>\n

System.Threading.Parallel<\/FONT><\/P>\n

System.Threading.Task<\/FONT><\/P>\n

System.Threading.TaskManager<\/FONT><\/P>\n

System.Threading.TaskManagerPolicy<\/FONT><\/P>\n

System.Threading.LazyInit<T><\/FONT><\/P>\n

System.Threading.Collections.IConcurrentCollection<T><\/FONT><\/P>\n

System.Threading.Collections.ConcurrentQueue<T><\/FONT><\/P>\n

System.Linq.ParallelQuery<\/FONT><\/P>\n

These samples also involve some standard .NET concurrency primitives and patterns:<\/FONT><\/FONT><\/P>\n

      <\/SPAN>System.Threading.Interlocked<\/FONT><\/P>\n

      <\/SPAN>System.Windows.Forms.Control.BeginInvoke<\/FONT><\/P>\n

            <\/FONT><\/SPAN>System.Threading.Monitor<\/FONT><\/SPAN><\/SPAN> (via the <\/FONT>lock {\u2026}<\/FONT><\/SPAN><\/SPAN>  <\/SPAN>construct)<\/FONT><\/FONT><\/P>\n

                <\/SPAN><\/FONT><\/FONT><\/P>\n

Let\u2019s start by exploring the C# ray tracer.  <\/SPAN>Load up Samples\\RayTracer\\C#\\RayTracer.sln<\/I>, compile and run.  <\/SPAN>If you receive errors regarding System.Threading, please ensure that you have the .NET Framework 3.5 and the Parallel Extensions June 2008 CTP installed.  <\/SPAN>Once the app is running, press the Start button and the ray tracer animation will run in single-threaded mode:<\/FONT><\/FONT><\/P>\n

 <\/P>\n

\"Ray<\/FONT><\/FONT><\/P>\n

<\/SPAN> <\/SPAN><\/FONT><\/FONT><\/P>\n

Note that the frames-per-second is displayed in the form\u2019s title bar, and that there are controls to Start\/Stop the animation and to turn on parallel rendering.  <\/SPAN>The \u201cParallel\u201d checkbox enables switching back and forth between sequential and parallel rendering, while the “Show Threads” option (only available when using parallel rendering) performs color-adjustment on the rendered pixels to indicate which thread each pixel was rendered on.  <\/SPAN>Let\u2019s turn on Parallel computation with “Show Threads” and observe the effect, shown here on a quad-core PC:<\/FONT><\/FONT><\/P>\n

<\/FONT> <\/P>\n

\"Ray<\/FONT><\/FONT><\/P>\n

<\/SPAN><\/P>\n

<\/FONT> <\/P>\n

In this screenshot, we can clearly see four separate colorings, which represent the four underlying threads that are calculating pixel values for the rendered image.  <\/SPAN>Notice also that the allocation of pixels to threads is row-based and that the partitioning of work is not uniform based on row-counts.  <\/SPAN>This is due to <\/FONT>Parallel.For()<\/FONT><\/SPAN><\/SPAN>dynamically assigning work to the worker threads to ensure that the computational load remains.  <\/SPAN>The application code itself specifies that the work should be split up row-by-row as this is a good balance between fine-grained work decomposition and the overheads inherent in spooling out small work items.  <\/SPAN>That is, if the work was decomposed to per-pixel work-items, the extra overheads would negatively impact the performance.  <\/SPAN>As it is, parallelizing the row-by-row decomposition provides a 3x improvement when the colorization is turned off.  <\/SPAN>This is a good result, as there is a non-trivial amount of work to be done that cannot be parallelized \u2013 note that even though the timing is around the image calculation only, drawing the image to the screen and refreshing the form eats into the cycles available and affects the speed-up factor.  <\/SPAN>If drawing the image is omitted, the speed up is between 3.5x and 4x as expected and hoped for. The moral here is that drawing more images to the screen increases the overheads of the parallel renderer and that we should always keep Amdahl’s Law (<\/FONT>http:\/\/en.wikipedia.org\/wiki\/Amdahl’s_law<\/FONT><\/A>)  <\/SPAN>in mind when assessing parallel improvements.<\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

The key rendering loops are RenderSequential(), RenderParallel(), and RenderParallelShowingThreads(), all of which appear in Raytracer.cs.  <\/SPAN>Comparing the first two, we see that the only difference is a simple rewriting of the outer loops: <\/FONT><\/FONT><\/P>\n

for(int y=0; y < screenHeight; y++){ \/* funcBody *\/ }<\/FONT><\/P>\n

to <\/FONT><\/FONT><\/P>\n

Parallel<\/SPAN>.For(0, screenHeight, y => \/* funcBody *\/ )<\/SPAN><\/FONT><\/P>\n

 <\/FONT><\/P>\n

A critical part of any parallel application is that the concurrent work (such as the funcBody in the parallel version) is thread-safe. This means that <\/FONT>TraceRay()<\/FONT><\/SPAN><\/SPAN> and other work called in the parallel loop must not alter any shared-state unless appropriate thread-synchronization is used or if the updates are known to be safe.  <\/SPAN>You will note that the funcBody’s do alter a shared data-structure, <\/FONT>rgb[]<\/FONT><\/SPAN><\/SPAN>, but that each element in this array will only be written to by a single execution of the funcBody and so no conflict will arise.  <\/SPAN>The developer must always be vigilant that all concurrent work can occur without conflicts.  <\/SPAN>If in doubt, simplify the concurrent work, use locks around risky code, or analyze the code and test to ensure corrrectness.<\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

The application also makes use of a single <\/FONT>System.Threading.Task<\/FONT><\/SPAN><\/SPAN> to manage the whole process of running the animation, and to set the options regarding parallelism via a <\/FONT>TaskManager<\/FONT><\/SPAN><\/SPAN>.  <\/SPAN>The <\/FONT>TaskManager<\/FONT><\/SPAN><\/SPAN> that is provided to this task become the <\/FONT>TaskManager.Current<\/FONT><\/SPAN><\/SPAN> for every task that is created inside, and so the configuration options also apply to the <\/FONT>Parallel.For()<\/FONT><\/SPAN><\/SPAN> that runs within the task (since <\/FONT>Parallel.For()<\/FONT><\/SPAN><\/SPAN> is built using <\/FONT>Task<\/FONT><\/SPAN><\/SPAN>, and <\/FONT>Task<\/FONT><\/SPAN><\/SPAN> instances by default use <\/FONT>TaskManager.Current<\/FONT><\/SPAN><\/SPAN>).  <\/SPAN>Another useful feature of wrapping the animation loop in a task is to provide a simple means of tracking whether the animation is running, and to facilitate cancelling the animation.  <\/SPAN>Diving in to <\/FONT>btnStartStop_Click()<\/FONT><\/SPAN><\/SPAN> in MainForm.cs, we see <\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

_renderTask = Task<\/SPAN>.Create(RenderLoop, <\/FONT><\/SPAN><\/P>\n

    <\/SPAN>chkParallel.Checked ? _parallelTm.Value : _sequentialTm.Value);<\/FONT><\/SPAN><\/P>\n

 <\/FONT><\/SPAN><\/P>\n

which creates the task to wrap the <\/FONT>RenderLoop()<\/SPAN> and supplies a <\/FONT>TaskManager<\/FONT><\/SPAN><\/SPAN> to control the options for parallel execution.  <\/SPAN>The first <\/FONT>TaskManager<\/FONT><\/SPAN><\/SPAN>, <\/FONT>_parallelTm<\/FONT><\/SPAN><\/SPAN>, will schedule one thread on every core of the machine, whereas <\/FONT>_sequentialTm<\/FONT><\/SPAN><\/SPAN> only uses one thread on one core in order to simulate a simple sequential implementation.  <\/SPAN>Actually, each of these variables is actually a <\/FONT>LazyInit<\/SPAN><TaskManager<\/SPAN>> <\/SPAN>which ensure creation of the main type only if the variable is used.  <\/SPAN>This is a minor usage of <\/FONT>LazyInit<T><\/FONT><\/SPAN><\/SPAN> but the construct can be very useful for object creations that are expensive and avoidable; in this example, if you never run a parallel render, you\u2019ll never instantiate the parallel TaskManager.  <\/SPAN>Keep this handy construct in mind for objects that might go unused.<\/FONT><\/FONT><\/P>\n

<\/FONT><\/FONT> <\/P>\n

The code for handling the “stop-animation” action includes the following:<\/FONT><\/FONT><\/SPAN><\/P>\n

 <\/FONT><\/SPAN><\/P>\n

_renderTask.ContinueWith(delegate<\/SPAN><\/FONT><\/SPAN><\/P>\n

{<\/FONT><\/SPAN><\/P>\n

    <\/SPAN>BeginInvoke((Action<\/SPAN>)delegate<\/SPAN><\/FONT><\/SPAN><\/P>\n

    <\/SPAN>{<\/FONT><\/SPAN><\/P>\n

        <\/SPAN>chkParallel.Enabled = true<\/SPAN>;<\/FONT><\/SPAN><\/P>\n

        <\/SPAN>chkShowThreads.Enabled = chkParallel.Checked;<\/FONT><\/SPAN><\/P>\n

        <\/SPAN>btnStartStop.Enabled = true<\/SPAN>;<\/FONT><\/SPAN><\/P>\n

        <\/SPAN>btnStartStop.Text = “Start”<\/SPAN>;<\/FONT><\/SPAN><\/P>\n

    <\/SPAN>});<\/FONT><\/SPAN><\/P>\n

});<\/FONT><\/SPAN><\/P>\n

_renderTask.Cancel();<\/SPAN><\/FONT><\/P>\n

 <\/FONT><\/P>\n

This sets a continuation-handler for the task that is wrapping the <\/FONT>RenderLoop()<\/FONT><\/SPAN><\/SPAN>, and this continuation cleans up the GUI and re-enables various controls.  <\/SPAN>Notice that we must use <\/FONT>MainForm.BeginInvoke()<\/FONT><\/SPAN><\/SPAN> in order to run the clean-up code on the GUI thread, as tasks run on a background worker thread.  <\/SPAN>After the cleanup continuation is registered, we call <\/FONT>Task.Cancel()<\/FONT><\/SPAN><\/SPAN>.  <\/SPAN>Notice that the <\/FONT>RenderLoop()<\/FONT><\/SPAN><\/SPAN> is checking for <\/FONT>t.IsCanceled<\/FONT><\/SPAN><\/SPAN> in order to detect the cancellation and co-operatively bail out of its animation loop.  <\/SPAN>The standard overload for <\/FONT>Task.ContinueWith()<\/FONT><\/SPAN><\/SPAN>  <\/SPAN>will run the continuation whenever the task finishes, whether due to successful termination, failure or cancellation, but there are additional overloads to control when the continuation fires and other task-related options.<\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

There is an interesting system used for managing the bitmaps used for rendering.  <\/SPAN>In particular, allocation of the image bitmaps is expensive, but we don\u2019t want to have to wait for the GUI to display a bitmap before we start computation of the next.  <\/SPAN>One way to solve this is a classic double-buffered solution with one bitmap for scene-drawing and another that is ready for blitting<\/I> to the screen (this was the approach taken in the sample included with the December 2007 CTP).  <\/SPAN>A more general solution is to keep rendering images at the maximum rate and add them to a queue for blitting.  <\/SPAN>This solution has been implemented by using a set of bitmaps for drawing, and each is sent for blitting by calling <\/FONT>Form.BeginInvoke()<\/FONT><\/SPAN><\/SPAN>with an appropriate delegate.  <\/SPAN>In order to reuse bitmaps rather than creating and disposing them repeatedly, an <\/FONT>ObjectPool<T><\/FONT><\/SPAN><\/SPAN> (see ObjectPools.cs) has been built around a <\/FONT>ConcurrentQueue<T><\/FONT><\/SPAN><\/SPAN> that supports object reuse and creation of new objects if no reusable ones are available.  <\/SPAN>The <\/FONT>ConcurrentQueue<T><\/FONT><\/SPAN><\/SPAN> is particularly useful as it provides all the machinery required to make the <\/FONT>ObjectPool<T><\/FONT><\/SPAN><\/SPAN> thread-safe.<\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

The C# ray tracer has been ported to Visual Basic and F#, including all of the items discussed above except for image colorization.  <\/SPAN>To build and run the F# version, download the F# languge support pack from <\/FONT>http:\/\/research.microsoft.com\/fsharp\/fsharp.aspx<\/FONT><\/A>. (To compile the sample, if you\u2019re running on x64, you\u2019ll need to modify the project settings to point to System.Core.dll in the correct location, as it\u2019s a different path than if running on x86.) In particular, notice that F# can directly make direct use of the Parallel Extensions and also gets an excellent performance boost on multi-core PCs:<\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

member this.RenderToArrayParallel(scene, rgb : int[]) = <\/FONT><\/P>\n

    <\/SPAN>Parallel.For(0, screenHeight, fun y -> <\/FONT><\/P>\n

        <\/SPAN>let stride = y * screenWidth<\/FONT><\/P>\n

        <\/SPAN>for x = 0 to screenWidth – 1 do <\/FONT><\/P>\n

            <\/SPAN>let color = TraceRay ({Start = scene.Camera.Pos; Dir = GetPoint x y scene.Camera }, scene, 0)<\/FONT><\/P>\n

            <\/SPAN>let intColor = color.ToInt ()<\/FONT><\/P>\n

            <\/SPAN>rgb.[x + stride] <- intColor)<\/FONT><\/P>\n

 <\/FONT><\/P>\n

Finally, a completely different ray tracer implementation is shown in Samples\\LINQRayTracer.<\/FONT><\/FONT><\/P>\n

When you run this ray tracer, you will notice that it has a more complicated scene and does not perform animation, but as it renders you will see the concurrency in effect as the rows get drawn.  <\/SPAN>The original query was written in the form:<\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

from<\/SPAN> y in<\/SPAN> Enumerable<\/SPAN>.Range(0, screenHeight)<\/SPAN><\/FONT><\/P>\n

   <\/SPAN>\u2026<\/FONT><\/SPAN><\/P>\n

   <\/SPAN>select<\/SPAN> from<\/SPAN> x in<\/SPAN> Enumerable<\/SPAN>.Range(0, screenWidth)<\/SPAN><\/FONT><\/P>\n

 <\/FONT><\/SPAN><\/P>\n

which is a natural 2-D construct to loop over each pixel in each row.  <\/SPAN>In order to make this run concurrently on a per-row basis (as for the other ray tracers), we only have to ask for the outer query to be run in parallel mode:<\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

from<\/SPAN> y in<\/SPAN> Enumerable<\/SPAN>.Range(0, screenHeight).AsParallel()<\/I><\/B><\/SPAN><\/FONT><\/P>\n

   <\/SPAN>\u2026<\/FONT><\/SPAN><\/P>\n

   <\/SPAN>select<\/SPAN> from<\/SPAN> x in<\/SPAN> Enumerable<\/SPAN>.Range(0, screenWidth)<\/SPAN><\/FONT><\/P>\n

 <\/FONT><\/P>\n

This sets the query to use PLINQ to partition the work of outer query over all the available cores.   <\/SPAN>The other adjustment is to enumerate the query via <\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P>\n

pixelsQuery.ForAll(row =><\/FONT><\/SPAN><\/P>\n

{<\/FONT><\/SPAN><\/P>\n

    <\/SPAN>foreach<\/SPAN> (var<\/SPAN> pixel in<\/SPAN> row)<\/FONT><\/SPAN><\/P>\n

    <\/SPAN>{<\/FONT><\/SPAN><\/P>\n

        <\/SPAN>rgb[pixel.X + (pixel.Y * screenWidth)] = pixel.Color.ToInt32();<\/FONT><\/SPAN><\/P>\n

    <\/SPAN>}<\/FONT><\/SPAN><\/P>\n

    <\/SPAN>int<\/SPAN> processed = Interlocked<\/SPAN>.Increment(ref<\/SPAN> rowsProcessed);<\/FONT><\/SPAN><\/P>\n

    <\/SPAN>if<\/SPAN> (processed % rowsPerUpdate == 0 ||<\/FONT><\/SPAN><\/P>\n

        <\/SPAN>processed >= screenHeight) updateImageHandler(rgb);<\/FONT><\/SPAN><\/P>\n

});<\/FONT><\/SPAN><\/P>\n

 <\/FONT><\/P>\n

which causes the query to run to completion in parallel.  <\/SPAN>Notice that the per-row worker delegate includes thread-safe access to the <\/FONT>rowsProcessed<\/FONT><\/SPAN><\/SPAN> counter to be safe in concurrent execution.<\/FONT><\/FONT><\/P>\n

 <\/FONT><\/P><\/p>\n","protected":false},"excerpt":{"rendered":"

The June 2008 Community Technology Preview (CTP) of Parallel Extensions to the .NET Framework was released on Monday, and we\u2019re really pleased at the level of excitement in the community that we\u2019re seeing in response.  As part of the CTP, we included a  variety of demos and samples to help provide a tour of the […]<\/p>\n","protected":false},"author":482,"featured_media":58792,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[7908],"tags":[7911,7916,7909,7910,7912],"class_list":["post-2603","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-pfxteam","tag-code-samples","tag-coordination-data-structures","tag-parallel-extensions","tag-plinq","tag-task-parallel-library"],"acf":[],"blog_post_summary":"

The June 2008 Community Technology Preview (CTP) of Parallel Extensions to the .NET Framework was released on Monday, and we\u2019re really pleased at the level of excitement in the community that we\u2019re seeing in response.  As part of the CTP, we included a  variety of demos and samples to help provide a tour of the […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/2603","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/users\/482"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/comments?post=2603"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/2603\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/media\/58792"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/media?parent=2603"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/categories?post=2603"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/tags?post=2603"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}