Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / Languages / CUDA

Cudafy Me: Part 2 of 4

4.00/5 (1 vote)
12 Oct 2012CPOL1 min read 8.1K  
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.

CUDALibs

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:

C#
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 };
}

Multi-Threaded CPU Solution

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

C#
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.

>>> Part 3 – Massively Parallel GPGPU Solution

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)