# Advantages and specific applications of massively parallel programming thesis idea

I'm nearly graduated in computer science engineering and my thesis should discuss the massively parallel computational model of CUDA and its advantages/applications.

I'm searching for an application field (an idea) to show off some of CUDA capabilities and (definitely) also my skills as programmer and engineer.

I'm up for a bit of challenge to integrate an interesting work into my thesis project and discussion so I'm asking for advices or ideas

• Try cracking md5 :) – Pratik Deoghare Feb 1 '12 at 13:25
• That's not a bad idea, I was searching for something more original but this isn't bad though – Paul Feb 1 '12 at 15:18
• Ok, I feel stupid, but: what is CUDA? Should the readers of this website know the meaning of this word without explanation? – Tsuyoshi Ito Feb 1 '12 at 16:22
• I think you will get better answers over at scicomp.SE. – Raphael Feb 1 '12 at 20:20
• I think this might violate our policy on project topics, I have started a discussion on meta and voted to close for now. – Artem Kaznatcheev Feb 1 '12 at 23:43

I would be interested in integration of GPU processsing (wether CUDA does not matter) into standard compilers. Can you figure out where application makes sense programmatically? Can you efficiently use GPUs?

• not bad this one too :D – Paul Feb 1 '12 at 20:57
• If you like this not very theoretical answer, you might want to ask your question over at scicomp.SE. – Raphael Feb 9 '12 at 21:04

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.

• this one's good too: GA with cuda, interesting.. although it has already been done – Paul Feb 1 '12 at 20:17
• ... probably you already know it, but if you're looking for some original CUDA applications, you must take a look to this page, too: nvidia.it/object/cuda_apps_flash_it.html ... the task seems not so easy :-( ... – Marzio De Biasi Feb 1 '12 at 22:51
• You're totally right, seems hard – Paul Feb 10 '12 at 13:24

the protein folding problem seems a good candidate; its a hot area of bio-informatics & already highly parallelized via some apps, (folding@home) and there is a large community holding bi-yearly contests & prizes for solutions see eg CASP. good/effective/accurate solutions are quite scientifically and commerically valuable and some are patented. the difficulty in this area (in contrast to eg the other good candidate given by Vor, SAT) is that some of the algorithms could probably be very difficult to implement solely from papers.

It depends on how much time and effort you want to spend for it. I think, cracking md5 is not a very time consuming job since you need to implement a simple brute-force search algorithm only.

Integrating the power of GPUs into an existing programming language would be a great idea since many other applications such as the ones mentioned by other answers can be written using such a language. I'd prefer to do the job in such a way which is either transparent to the user or he needs only a little effort to use the capability.

One idea is to write an object file optimizer or alter an open source compiler which looks for specific patterns (like loops with simple body) in programs and replaces them with a CUDA version. That might be too much job to do.

The other option is to implement a simple matrix library with matlab-like operations. In C++, it would look like this:

CUDAArray<int> a = CUDAArray<int>(1000);
CUDAArray<int> b = CUDAArray<int>(1000);
// Use GPU to compute
CUDAArray<int> c = a * 2 + b;


Anyways, I think non of these ideas is a new one.

I may be wrong, but I think that a GPU implementation of parallel graph partitioning is missing. This would be of great value, and you could compare the performances obtained with ParMetis and Zoltan, which are standard parallel implementations of graph partitioning. Why graph partitioning ? Because it is suitable for irregular, unstructured communication patterns lacking a well-known graph topology, a feature of many graph-based applications. Your work will be useful to many people working in the field.

You may choose to implement just a single technique (e.g., Space-Filling Curves), or a little library. Finally, did you consider implementing your work using OpenCL ? While CUDA is a proprietary technology, OpenCL is a standard and you code will run on any current GPU device.