Cudafy Me: Part 4 of 4

These posts are meant to inspire you to enter into the world of graphics processor programming.

Posts in This Series

• Part 1 – Introduction & Single Threaded CPU Solution
• Part 2 – Multi-Threaded CPU Solution
• Part 3 – Massively Parallel GPGPU Solution
• Part 4 – Discussion

Full Source Code

http://cudafytsp.codeplex.com/

Benchmarks

Computing an 11 city solution with 40 million permutations
on a Dell T7500 (Xeon X5690 @ 3.47GHz)
with an NVidia Tesla C2050:

1. Single CPU: 47.340 seconds
2. Multi threaded: 7.965 seconds
3. GPGPU: 0.117 seconds
   Note: 12 cities - 480 million permutations – it took 2.206 seconds on the GPGPU

Computing an 11 city solution with 40 million permutations
on a 2009 HP Pavilion dv7 (i7 CPU Q 720 @ 1.60GHz)
with an NVidia GeForce GT 230M (48 CUDA cores):

1. Single CPU: 162.535 seconds
2. Multi threaded: 36.240 seconds
3. GPGPU: 2.181 seconds

Computing a 10 city solution with 3.6 million permutations
on a Dell T3400 (Core 2 Duo E6850 @ 3.00GHz)
with an NVidia Quadro NVS 290:

1. Single CPU: 5.707 seconds
2. Multi threaded: 3.097 seconds
3. GPGPU: 0.888 seconds

Nuances

There are a few things that took me a while to figure out that might be helpful to others.

• I used VS2010 Pro. I heard you can use the express editions if you install both the C# and C++ versions. It seems Microsoft is making harder to find the VS2010 though.
• You cannot use VS2012 yet, and probably never be able to use the express edition of VS2012 since I doubt express will support desktop applications.
• It really is not that hard to add CL.EXE to your path. Just type “environment” into the Windows 7 start box that states “search programs and files” and pick the “Edits system and environment variables”.
• If your video card is older, try this:
  CudafyTranslator.Cudafy(eArchitecture.sm_11);
• If the GPGPU call takes more than a few seconds then the video driver resets. I think you can tweak the timeout somewhere.
• Things go a bit wonky if you call functions in your Cudafied code that return void.
• It is a bit faster to call the version of launch that takes the function to call as a string.
• I think calling CopyFromDevice forces a call to Synchronize first.
• You cannot allocate arrays in Cudafied code, so get used to calling AllocateShared for all threads.
• Recursion is not supported in Cudafied code.

Can We Go Faster? Oh Yeah!

The GPGPU algorithm described in this series is an introductory primer meant to inspire you to enter into the world of graphics processor programming. For those who are looking for phonemically fast solutions to the traveling salesman problem, you might consider starting with the link from GPU Science below. The author Dr. Kamil Rocki of the University of Tokyo taunts us: "Anyone faster out there?"

• GPUScience Article
  LOGO – GPU Accelerated Travelling Salesman Problem (TSP) Solver
• Dr. Kamil Rocki’s Project Website
  http://olab.is.s.u-tokyo.ac.jp/~kamil.rocki/projects.html

Essential Resources

• CudafyTSP on Codeplex companion source for this series of blog posts.
• Using Cudafy for GPGPU Programming in .NET an excellent introduction to Cudafy.
• Cudafy Commercial Site and on Codeplex the geniuses behind Cudafy.
• NVidia CUDA Zone the geniuses behind CUDA.
• CUDA By Example a nice book – buy one for a friend too.