Advantages and specific applications of massively parallel programming thesis idea
Build a "CUDA-SAT solver" and outperform the winners of the annual Sat competitions ! :-)

Edit: I posted the answer quickly ... but - after a Google search - I found that my idea is not so original, see: NVIDIA CUDA Architecture-based Parallel Incomplete SAT Solver ... however I think that a public available project/source code of a CUDA-powered SAT solver that can be compiled and used on a standard PC (Linux and/or Win) equipped with a CUDA GPU graphics card would be very appreciated.

As a second best, I suggest you to try to implement a parallel genetic algorithm and pick one (or more) of the many possible applications to show the performance gains due to the parallelization.