<p>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?</p>

CC BY-SA 3.0
2012-02-01T20:57:16.593Z
not bad this one too :D
Paul
CC BY-SA 3.0
2012-02-09T21:04:08.763Z
If you like this not very theoretical answer, you might want to ask your question over at [scicomp.SE](http://scicomp.stackexchange.com/).
Raphael
CC BY-SA 3.0
2012-02-01T20:22:24.603Z
2012-02-01T20:22:24.603Z
Raphael
<p>Build a "<em>CUDA-SAT solver</em>" and outperform the winners of the annual <a href="http://www.satcompetition.org/" rel="nofollow">Sat competitions</a> ! :-)</p>

<p><strong>Edit</strong>: I posted the answer quickly ... but - after a Google search - I found that my idea is not so original, see: <a href="http://www.cs.rit.edu/~ark/students/yxw9319/report.pdf" rel="nofollow">NVIDIA CUDA Architecture-based Parallel Incomplete SAT Solver</a> ... 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.</p>

<p>As a second best, I suggest you to try to implement a <a href="http://tracer.uc3m.es/tws/cEA/documents/cant98.pdf" rel="nofollow">parallel genetic algorithm</a> and pick one (or more) of the <a href="http://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications" rel="nofollow">many possible applications</a> to show the performance gains due to the parallelization.</p>

CC BY-SA 3.0
2012-02-01T20:17:50.243Z
this one's good too: GA with cuda, interesting.. although it has already been done
Paul
CC BY-SA 3.0
2012-02-01T22:51:37.967Z
... probably you already know it, but if you're looking for some original CUDA applications, you must take a look to this page, too: http://www.nvidia.it/object/cuda_apps_flash_it.html ... the task seems not so easy :-( ...
Marzio De Biasi
CC BY-SA 3.0
2012-02-10T13:24:50.387Z
You're totally right, seems hard
Paul
CC BY-SA 3.0
2012-02-01T17:49:36.487Z
2012-02-01T18:26:53.103Z
2012-02-01T18:26:53.103Z
Marzio De Biasi
<p>the <a href="http://en.wikipedia.org/wiki/Protein_folding" rel="nofollow">protein folding problem</a> seems a good candidate; its a hot area of bio-informatics &amp; already highly parallelized via some apps, (<a href="http://folding.stanford.edu/" rel="nofollow">folding@home</a>) and there is a large community holding bi-yearly contests &amp; prizes for solutions see eg <a href="http://en.wikipedia.org/wiki/CASP" rel="nofollow">CASP</a>. 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.</p>

CC BY-SA 3.0
2012-02-01T22:11:19.050Z
2012-02-01T22:11:19.050Z
vzn
<p>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.</p>

<p>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.</p>

<p>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. </p>

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

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

<p>Anyways, I think non of these ideas is a new one.</p>

CC BY-SA 3.0
2012-02-02T02:40:43.887Z
2012-02-02T02:40:43.887Z
Helium
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-02T06:37:07.870Z
2012-02-02T06:43:55.943Z
2012-02-02T06:43:55.943Z
Massimo Cafaro
<p>I'm nearly graduated in computer science engineering and my thesis should discuss the massively parallel computational model of <a href="http://en.wikipedia.org/wiki/CUDA" rel="nofollow">CUDA</a> and its advantages/applications.</p>

<p>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.</p>

<p>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</p>

CC BY-SA 3.0
2012-02-01T13:25:01.887Z
Try cracking [md5](https://en.wikipedia.org/wiki/MD5) :)
Pratik Deoghare
CC BY-SA 3.0
2012-02-01T15:18:09.497Z
That's not a bad idea, I was searching for something more original but this isn't bad though
Paul
CC BY-SA 3.0
2012-02-01T16:22:06.887Z
Ok, I feel stupid, but: what is CUDA?  Should the readers of this website know the meaning of this word without explanation?
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-01T16:50:56.500Z
CUDA is an architecture for massively parallel computing. 

Explained as simple as I can: normally a program runs on a CPU and is executed sequentially (first one operation, second another one, third another one, etc..). CUDA is a set of drivers and libraries that allow you to use your GPU (graphic card processing unit) to execute a LOT of operations and instructions at the same time (GPU are faster than CPU with parallel work, they're built to execute simultaneously operations, CPU are not, they've been optimized to execute operations sequentially ).
Paul
CC BY-SA 3.0
2012-02-01T20:20:53.657Z
I think you will get better answers over at [scicomp.SE](http://scicomp.stackexchange.com/).
Raphael
CC BY-SA 3.0
2012-02-01T23:43:49.057Z
I think this might violate our [policy on project topics](http://meta.cstheory.stackexchange.com/q/802/1037), I have started a discussion on [meta](http://meta.cstheory.stackexchange.com/q/1482/1037) and voted to close for now.
Artem Kaznatcheev
<pl.programming-languages><dc.parallel-comp><ct.category-theory><project-topic>
Advantages and specific applications of massively parallel programming thesis idea
Paul
# Advantages and specific applications of massively parallel programming thesis idea

(Asked by: username_0 on 2012-02-01)

I'm nearly graduated in computer science engineering and my thesis should discuss the massively parallel computational model of [CUDA](http://en.wikipedia.org/wiki/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

**Tags:** pl.programming-languages, dc.parallel-comp, ct.category-theory, project-topic
> **Comments:**
> **username_1**: Try cracking [md5](https://en.wikipedia.org/wiki/MD5) :)  
> **username_0**: That's not a bad idea, I was searching for something more original but this isn't bad though  
> **username_2**: Ok, I feel stupid, but: what is CUDA?  Should the readers of this website know the meaning of this word without explanation?  
> **username_0**: CUDA is an architecture for massively parallel computing.   Explained as simple as I can: normally a program runs on a CPU and is executed sequentially (first one operation, second another one, third another one, etc..). CUDA is a set of drivers and libraries that allow you to use your GPU (graphic card processing unit) to execute a LOT of operations and instructions at the same time (GPU are faster than CPU with parallel work, they're built to execute simultaneously operations, CPU are not, they've been optimized to execute operations sequentially ).  
> **username_3**: I think you will get better answers over at [scicomp.SE](http://scicomp.stackexchange.com/).  
> **username_4**: I think this might violate our [policy on project topics](http://meta.cstheory.stackexchange.com/q/802/1037), I have started a discussion on [meta](http://meta.cstheory.stackexchange.com/q/1482/1037) and voted to close for now.  

---

## 5 answers

### Answer by username_3 on 2012-02-01. Score: 0 | Accepted answer

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?

> **Comments:**
> **username_0**: not bad this one too :D  
> **username_3**: If you like this not very theoretical answer, you might want to ask your question over at [scicomp.SE](http://scicomp.stackexchange.com/).  

---

### Answer by username_5 on 2012-02-01. Score: 5

Build a "*CUDA-SAT solver*" and outperform the winners of the annual [Sat competitions](http://www.satcompetition.org/) ! :-)

**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](http://www.cs.rit.edu/~ark/students/yxw9319/report.pdf) ... 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](http://tracer.uc3m.es/tws/cEA/documents/cant98.pdf) and pick one (or more) of the [many possible applications](http://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications) to show the performance gains due to the parallelization.

> **Comments:**
> **username_0**: this one's good too: GA with cuda, interesting.. although it has already been done  
> **username_5**: ... probably you already know it, but if you're looking for some original CUDA applications, you must take a look to this page, too: http://www.nvidia.it/object/cuda_apps_flash_it.html ... the task seems not so easy :-( ...  
> **username_0**: You're totally right, seems hard  

---

### Answer by username_6 on 2012-02-01. Score: 3

the [protein folding problem](http://en.wikipedia.org/wiki/Protein_folding) seems a good candidate; its a hot area of bio-informatics & already highly parallelized via some apps, ([folding@home](http://folding.stanford.edu/)) and there is a large community holding bi-yearly contests & prizes for solutions see eg [CASP](http://en.wikipedia.org/wiki/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.


---

### Answer by username_7 on 2012-02-02. Score: 0

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 a = CUDAArray(1000);
CUDAArray b = CUDAArray(1000);
// Use GPU to compute
CUDAArray c = a * 2 + b;

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


---

### Answer by username_8 on 2012-02-02. Score: 0

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.


---

