Project ideas for Parallel Programming

[delon]

Hello, I am taking a parallel programming course with X10 language. We need to work on a parallel programming project for the whole semester. I am brainstorming from the first day of the class to come up with a project proposal. I would appreciate if anyone share some project ideas with me.

My background is Electrical Engineering and we can choose project from any field. I was thinking about working on the basic sorting algorithms but I guess if it is possible to come up with some other interesting concepts.

Thanks in advance!

 

[AyashiKaibutsu]

I don't know if it can be made a parallel programming project, but I always liked genetic algorithms. Maybe something like solving the travelling salesman problem with one.

 

[delon]

Thank you for sharing your thoughts. I will look it up I am not a CS major. So, I don't have extensive programming background and most of my programming project was based on Mathlab (random signal processing, DSP etc).

Waiting eagerly for to see what others think!

 

[eLiu]

I don't know if it can be made a parallel programming project, but I always liked genetic algorithms. Maybe something like solving the travelling salesman problem with one.

If he's going for something more practical, TSP with genetic algorithms is pretty ridiculous. Genetic algorithms are useful when you have an optimization problem that you more or less know nothing about in terms of its underlying structure. TSP has a lot of underlying structure and there are tons of relaxations, approximations, and other heuristics that do quite well in practice & are fast. I mean even simulated annealing will be better than a genetic algorithm for tsp.

That said, finding some NP (complete) problem that you care about & doing a parallel implementation of a known algorithm would probably be pretty good.

Or you could implement a game AI (chess for example). Something using the minimax algorithm with alpha-beta pruning? My understanding is that isn't easy to parallelize efficiently (as each thread makes decisions, the others may/may not want to know about it).

Or if you like signal processing, you could give a parallel implementation of something you've worked on before, except now using gigantic data sets or something. Not much to suggest here b/c I know little of DSP. An example with image processing would be say doing object recognition via parallel filtering.

Or you could do something mathy if partial differential equations (PDE) or linear algebra interest you at all. Parallel direct or iterative solvers for linear systems of equations is not easy. Or parallel implementations of some simple PDE solvers with different communication patterns. Or FFT implementations.

A (web) search engine could be fun too. No experience there but it sounds neat. Along kinda similar lines, cache-oblivious database operations using parallel B-trees.

 

[Cogman]

Nbody simulations can be pretty entertaining and pretty to watch.

In fact, get microsoft's DirectX SDK and look through some of their GPGPU projects (nbody is one of them) that should give you some good ideas of what can be done and how to do it.

 

[delon]

Can anyone suggest me some ideas from digital signal processing? I found some image processing concepts to implement with parallel prog. What about implementing parallel FFT algorithms or viterbi decoding algorithm ?

Thanks in advance.