Search This Blog

Wednesday, June 22, 2011

IT'S NOT DEAD YET! IT'S FEELING MUCH BETTER!

OK, so there haven't been any posts lately, and I have a good reason for that; I was spending the time developing an algorithm called Plan B which is a provably good path planning algorithm to plan paths that include the probability of losing communications between a group of robots.  The handy part of this algorithm is that it is designed to accept any radio propagation model I cook up, including ones based on Fourier Optics. 

In addition, I talked with Joe Kider about working on this, and we've come up with a bit of a plan on what we're going to do.  That is the reason for this post.

So, in a vaguely ordered form:
  1. We need to step back from doing code, and do math first.  I spent some time learning about the different ways that the math for light is calculated in normal space, but neither Joe nor I have any good ideas on how some of that translates into Fourier space.  That means that we need to figure out things like reflection, refraction, polarization, etc. in an analytical form in Fourier space.  If we can do that, then just as we can calculate the affine transforms of a triangle in Fourier space, we can do the rest there as well.  Done right, that should reduce the amount of work the CPU/GPU/box of highly caffeinated squirrels needs to do, and increase accuracy (decreases the work because we won't have to do a forward FFT; the inverse FFT still needs to be done.
  2. I haven't discussed this with Joe yet, but I want to switch away from CUDA and do OpenCL instead.  From what I heard from one of the other guys in GPGPU, OpenCL is finally starting to catch up with CUDA in performance, and to surpass it in some areas.  That is a Good Thing™as it means that the code we write could run on many different vendors' platforms.  The only downside is that there aren't any really good FFT libraries for OpenCL yet, so we'd need to write one.  The good thing about that is that the FFT is an exceedingly well understood transform, so we can cut our teeth learning OpenCL by doing the FFT library we need, and comparing the output of it to other, known good implementations, like FFTW
  3. Much of the code I wrote originally is still usable, but it needs some cleanup.  I've learned a great deal more about CMake and Google Test than I knew when I wrote the original code, so one of the first tasks is to reorganize everything so that it works correctly within CMake's and Google Test's concept of 'correct'.  Some bits are probably going to go away, and other bits are going to stay.  More than likely, we're going to have to create several layers of code, to act as different abstraction layers.  So, one of the first things that will likely happen is that we put together a good FFT project, and ignore the current code until the FFT part works (at least a little bit).
And that about wraps up where things are at right now.  More than likely, the wiki is what will get updated, and that will be about it for a while.  Once we have all that really nailed down, THEN we'll move onto making the code good.

2 comments:

  1. For comparing the performance of CUDA and OpenCL, check out Varun's final report. You should also be able to run his code if you want to test it on a particular box.

    ReplyDelete