13,592,944 members
Technical Blog
alternative version

#### Stats

6.3K views
2 bookmarked
Posted 12 Oct 2012
Licenced CPOL

# Cudafy Me: Part 2 of 4

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

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

Posts in This Series

Full Source Code

http://cudafytsp.codeplex.com/

Recap

In the last post, we simply put together a single-threaded CPU solution to the traveling salesman problem. Here was the code that accomplished our work:

```private Answer CpuTsp()
{
var bestDistance = float.MaxValue;
var bestPermutation = -1;
var stopWatch = Stopwatch.StartNew();

for (var permutation = 0; permutation < _permutations; permutation++)
{
var path = new int[1, Cities];
var distance = FindPathDistance(_permutations, permutation,
Cities, _latitudes, _longitudes, path, 0);
if (distance < bestDistance)
{
bestDistance = distance;
bestPermutation = permutation;
}
}

return new Answer { Distance = bestDistance, Permutation = bestPermutation,
Milliseconds = stopWatch.ElapsedMilliseconds };
}```

Now we will modify the previous solution to take advantage of a multi-core CPU.

```private Answer MpuTsp()
{
var bestDistance = float.MaxValue;
var bestPermutation = -1;
var locker = new Object();
var stopWatch = Stopwatch.StartNew();

Parallel.For(0, _permutations, permutation =>
{
var path = new int[1, Cities];
var distance = FindPathDistance(_permutations, permutation, Cities, _latitudes, _longitudes, path, 0);
lock (locker)
{
if (distance < bestDistance)
{
bestDistance = distance;
bestPermutation = permutation;
}
}
});

return new Answer { Distance = bestDistance,
Permutation = bestPermutation, Milliseconds = stopWatch.ElapsedMilliseconds };
}```

The only difference in this solution is that we use a `Parallel.For` loop instead of a tradition for loop. Because the interior of the loop runs in parallel (concurrently), we need to use a bit of thread locking to ensure we find the shortest distance. The function `FindPathDistance` is identical to the single-threaded solution.

We could optimize the code above and use a more efficient locking scheme, but that is not the point of this series of posts.

Next Step

What we have left to do is to write a method that takes advantage of the code we have already written to run it on the massively parallel GPGPU.

## Share

 Software Developer (Senior) LECO Corporation United States
John Hauck has been developing software professionally since 1981, and focused on Windows-based development since 1988. For the past 17 years John has been working at LECO, a scientific laboratory instrument company, where he manages software development. John also served as the manager of software development at Zenith Data Systems, as the Vice President of software development at TechSmith, as the lead medical records developer at Instrument Makar, as the MSU student who developed the time and attendance system for Dart container, and as the high school kid who wrote the manufacturing control system at Wohlert. John loves the Lord, his wife, their three kids, and sailing on Lake Michigan.