Parallel Programming Course Project

[Ipreferspam]

I am currently enrolled in a course for parallel programming that involves a group project. We are free to choose are own team members and what we want to do for the project. I've teamed up with two good friends and we are trying to brainstorm ideas for fun and interesting projects.

I am posting here to ask for suggestions for our project.

We are currently trying to think of ideas that either involve gaming or could be roughly related to biology/bioinformatics/medicine.

One gaming idea we've had is to write a chess engine using CUDA/OpenCL.

An idea related to medicine we've thought about might be to perform calculations on protein folding. However, none of us have a very deep knowledge in this area so we were thinking of simplifying things by looking at 2D protein folding instead of 3D.

Any and all suggestions are greatly appreciated.

It might help to know that the professor has left the choice of programming language and platform up to us as well. We do not have to use CUDA/OpenCL or any other language/framework. Any suggestions on these would also be appreciated, as none of us have any experience with any frameworks for parallel programming.

Thank you!

 

[WaitingForNehalem]

OpenCL or DirectCompute video transcoder

 

[Cogman]

Does anyone on your team have CUDA/OpenCL experience? If not, I would suggest picking a project using standard PThreads or Win32 threads instead. From what I've dealt with, CUDA is very... interesting. to work with. Nothing like you might be expecting. You might not be able to get anything productive done if nobody has ever dealt with the language.

It should be noted that OpenCL/Cuda are less of a framework for parallel coding and more of a language of GPGPU coding (which is generally very parallel in nature).

I would tend to side on the "Doable in 6 months" sort of project over the "This will be really cool" projects. WaitingForNehalems idea would definitely be awesome, however, it is something that takes a TON of work and is really not realistic for a semester project.

Some things that might be doable.

A more then 2 player multiplayer 2d game (Jazz jackrabbit comes to mind). Classic threading will occur naturally on the servers side as it has to deal with multiple incoming connections. I wouldn't suggest anything too complex as game programming introduces its own set of complexities. Rather, keep it a simple game. If you want to make the actual engine more threaded, you could do something along the lines of adding separate AI that run in their own threads.

Something that would be even easier would be a multithreaded prime finding algorithm.

Neural networks are pretty interesting, and definitely threadable. Start it off simple, get it to compute something like an xor. Then move up to more complex things like image recognization (Very hard). Or even something like a fish tank and genetic algorithms (where each fish extends life by collecting food or killing other fish.)

 

[GodlessAstronomer]

Raytracing programs are a good candidate for parallelism and not too difficult to put together.

 

[degibson]

I have several questions to raise before I can give this the right level of thought:

Is this a graduate- or undergraduate-level course? That is, are you expected to innovate or demonstrate mastery?

Are you reading any scholarly papers in your course? Perhaps on uncommon parallel abstractions? If so, look ahead on the reading list and perhaps one will catch your eye.

Does concurrent programming (e.g., Cogman's multiplayer game) fall into your course's definition of parallel programming, or not?

What is your current level of expertise, and on what platform(s)?

 

[Ipreferspam]

This is for an undergraduate level course.

We will not be reading any scholarly papers in the course.

Concurrent programming does fall within the courses definition as the syllabus says it covers "programming techniques applicable to concurrent, parallel and distributed programs."

I have more than eight years of experience as a developer using PHP/MySQL and VB.NET/C#/MSSQL. I was a software architect for a few of those years. However, none of the applications I wrote or designed were parallel in nature. I have also taken courses on Java and C++ and played around with Ruby and Python. I've also had some experience with MIPS and NQC (a language used for the lego mindstorm robot).

The majority of my development work was on Windows or for the web, but I've done a few school projects on Ubuntu.

I feel comfortable working on any platform and learning any toolset/framework as necessary for the scope of this project (and I feel the same about my two partners--we've luckily worked together on other projects and know each other well).

None of us have any experience with CUDA or OpenCL.

 

[Cogman]

Again, I'll warn you. CUDA and OpenCL are nothing like any of the programming you have done before. I consider myself to be pretty competent when it comes to programming, and I've struggled to work with them. You don't want to spend all your time just getting the language to make a "hello world" program.

If this is your first dealings with a parallel environment, I really suggest learning to walk before running. Use Pthreads as your base and go from there.

 

[degibson]

OP: Great! You are in a perfect position to have a really great course project, given your experience and your team's competency.

As for platforms, the best infrastructures (in low-level languages) for learning parallel concepts without too much parallel nastiness are: OpenMP, Intel TBB (in that order).

Both of those give you some pretty basic parallel abstractions (e.g., parallel for loops) without making you implement them yourselves (i.e., no pthread_create garbage). And, both give you enough rope to hang yourself, which is good for learning too.

If you're looking for something reasonably challenging in the parallel/game space, look into pathfinding. It's entirely doable, and sophisticated pathfinding AI is computationally dense and very important.

General advice:
- Write a fully serial version first. That version becomes your gold standard: both for correctness and to measure your speedup.
- Remember: the whole point of parallel programming is speed. A lot of students don't realize that high-performance programming begins with single-thread optimizations. Moreover, you should be ready to evaluate the speedup of your application's parallel versions.
-Look into: Amdahl's Law, high-resolution cycle counters
-Once you've read up on Amdahl's law: measure f for your parallel versions, and compare against expected speedup.
-Also, it's useful to use HR cycle counters instead of a command-line timer because HR timers can measure only computational parts of the application, rather than all the mmap(), etc., garbage that goes on when processes start and end.

Regarding CUDA: Unless one of your team has done it before, I agree with Cogman. Doing a cold-start CUDA project is asking for failure -- CUDA has an enormous learning curve, and your eventual project will be REALLY hardware-specific.

 

[esun]

There are plenty of good applications out there so I won't bother making a bunch of specific recommendations. I'm personally doing some work on software defined radio which is a great application of parallel programming. The thing I would recommend though is using a threading library no matter what language you choose. For example, if you use C/C++ then use the boost::thread library. It will make your life much easier.

I'm not sure I'd just right into using something like Intel TBB since it is a little higher in terms of abstraction than just basic threading. I would imagine the purpose of the parallel programming class will be to teach you things like synchronization primitives, and to hide it behind a higher level API would be educationally non-ideal.

 

[degibson]

I'm not sure I'd just right into using something like Intel TBB since it is a little higher in terms of abstraction than just basic threading. I would imagine the purpose of the parallel programming class will be to teach you things like synchronization primitives, and to hide it behind a higher level API would be educationally non-ideal.

There is plenty of synchronization in OpenMP and TBB. At the undergraduate level, the less a programmer needs to know about low-level synchronization, the better. Concepts matter more. (this is why I asked about the level of the course)

 

[CycloWizard]

You could write a quasi-Newton solver which performs the function evaluations in parallel. For some reason, every implementation I've found of such solvers only computes the gradient in parallel, while for many/most applications, the function evaluations are where the lion's share of computing time is spent. There's a bit of math involved, but nothing more complex than linear algebra and finite differences.

 

[Cogman]

I know I am weird in this aspect. But I really don't feel like using Pthreads or the win32 thread API is THAT big of an issue. I don't really find Boost to be significantly easier either for these situations.

My personal feeling is that having a high level of control in threading is pretty important. Frameworks such as OpenMP tend to hide that control in favor of simplicity. Don't get me wrong, Frameworks are great to learn and do make things easier. I just feel that when you use frameworks like OpenMP you loose sight of things such as the cost of creating a thread.

Either way. Profile, Profile, Profile. Make sure that the threaded implementation is ACTUALLY faster then the serial implementation. Creating threads has a fairly high overhead that you need to justify before using them blindly. Fast loops and simple procedures should NOT be threaded.

 

[EvilManagedCare]

A guy in one of my classes talked about using SDL for games. I don't know much about it, but there's another possibility. Wikipedia indicates there's a library for multithreading. I don't know much about the differences with the various thread libraries as I was always required to use pthreads.

Good luck

 

[eldavo]

I feel comfortable working on any platform and learning any toolset/framework as necessary for the scope of this project (and I feel the same about my two partners--we've luckily worked together on other projects and know each other well).

I'll bite.

If you're not afraid to learn new languages, you could step outside your comfort zone and explore a more functional level language in the lisp family of languages like Clojure (sort of like Haskell). The reason I suggest Clojure is that it is completely capable of calling into Java libraries. So if you have a game architecture like the Mario Java competition you can easily call into that library using Clojure. Since Clojure is a functional language, you would be able to use the easier methods of parallelization and concurrency. If you wanted to go the distance you would find some game (or more likely multiagent platform like MASON -- disclaimer, I got my CS Masters there) that allowed multiple actors that interacted and you would then do parallel threading for each agent with agents on teams allowed to engage in message passing between the threads (check out the Keepaway game). That's some pretty advanced stuff though.

In addition to Clojure, there's also a host of other languages that make parallel programming much easier like Erlang and Scala. Be sure to at least give these languages a cursory glance if you're looking to really learn something new. Honestly, I would not have been up to the challenge in my undergrad as I was taking a lot of math and music theory as well and wouldn't have the time for this ... so be warned that this is suggested only if you truly have chutzpah.

Now for the kind of program you tackle, I'm partial to image analysis and video processing. Games are a bit trickier. But if you wanted to do a game, I guess I would suggest canning the idea of learning a new language or platform and stick to something you know like Java or C++. Then you can pick up a GPL'd game or game platform and either make the engine parallel or use parallel worker threads to make something more interesting. A couple games I think of would be DungeonMaker (C++) and Strange Adventures in Infinite Space (SDL). Remember, you're not going to be graded for making a new game or learning a new language. You're going to be graded for how well you code up some parallel threads and explore interesting concurrency problems. Above all, when you're looking for ideas: fail early and fail often so you don't find yourself committed to something you can't complete by the end of the semester. If any of this stuff looks to be like too much work after the first week, don't be embarrassed to pull out and nail an easier woman.

We are currently trying to think of ideas that either involve gaming or could be roughly related to biology/bioinformatics/medicine.

I took some bioinformatics courses in college and would recommend not to tackle this unless you're already familiar with FASTA and BLAST algorithms. Folding is a very complicated problem that isn't fully understood yet. My opinion is that the background research necessary to even take an educated stab at this problem would far outweigh your resources.

 

[esun]

I know I am weird in this aspect. But I really don't feel like using Pthreads or the win32 thread API is THAT big of an issue. I don't really find Boost to be significantly easier either for these situations.

Although the Win32 API isn't too bad conceptually, I just think it's this glaring stylistic inconsistency when I use it in my code. I guess I could go through the trouble of wrapping it into some threading class, but if I did that I'd probably end up with something like boost::thread, which is conveniently already written for me.

Plus if you use boost you also get access to all of it's other niceties like smart pointers (resulting in automatically releasing locks, very useful for threading).

 

[GodlessAstronomer]

If you're not afraid to learn new languages, you could step outside your comfort zone and explore a more functional level language in the lisp family of languages like Clojure (sort of like Haskell). The reason I suggest Clojure is that it is completely capable of calling into Java libraries.

Better yet, F#.

 

[homercles337]

I am a computational scientist (phd level) in chembio/cheminformatics and parallelizing code is something i do all the time. Of course this is from an applied perspective since slicing a for loop up into chunks and shipping it off to the cluster is not difficult or challenging. Recently i have been playing with Matlab/CUDA (via Accelereyes and GPUmat) and see some really impressive gains with simple vectorized matlab code. I dont know the scope of this project, but if i was going to stick and undergrad with a parallel project i would want to see performance trade off between cluster/CPU and a GPGPU solution. But since i have been piloting this stuff for our Research Computing Group at work im a bit biased. Nonetheless, this does pose an interesting project since there are trade-offs for cluster/CPU v GPGPU.

 

[tatteredpotato]

I'll bite.

If you're not afraid to learn new languages, you could step outside your comfort zone and explore a more functional level language in the lisp family of languages like Clojure (sort of like Haskell).

I've been using SML for my compilers class, and it's my first time using a functional language. It definitely can describe some algorithms much more.... "elegantly" than the equivalent C or Java versions.

 

[GodlessAstronomer]

I've been using SML for my compilers class, and it's my first time using a functional language. It definitely can describe some algorithms much more.... "elegantly" than the equivalent C or Java versions.

I love functional programming And parallelizing it is so much simpler than with imperative code, if written correctly.

 

[degibson]

Wow! Some really great ideas in this thread. OP: You're lucky.

Cogman:
My personal feeling is that having a high level of control in threading is pretty important. Frameworks such as OpenMP tend to hide that control in favor of simplicity.

That's true, and lots of control is important. Speaking from experience teaching shared-memory programming, however, students don't struggle too much with thread creation and destruction. They hate the syntax, and the fact that it takes MIMD code out-of-line, but the syntax is manageable. But you still get all the really nasty and challenging stuff with frameworks... which is where the most important learning takes place.

For my part, whenever I thread, I thread explicitly, too, because I prefer the explicit control. But overall I find that my former students vastly preferred OpenMP -- again, not because they couldn't master pthreads, merely that pthreads kinda suck when you're learning.

Either way. Profile, Profile, Profile. Make sure that the threaded implementation is ACTUALLY faster then the serial implementation. Creating threads has a fairly high overhead that you need to justify before using them blindly. Fast loops and simple procedures should NOT be threaded

Great point Cogman. I couldn't agree more.

 

[GodlessAstronomer]

Either way. Profile, Profile, Profile. Make sure that the threaded implementation is ACTUALLY faster then the serial implementation. Creating threads has a fairly high overhead that you need to justify before using them blindly. Fast loops and simple procedures should NOT be threaded.

This is a good point. I wrote a multithreaded ray tracer and found that if I parallelized each row of pixels then I gained a 230% performance boost on a quad core machine versus serial processing. If I placed each pixel on its own thread I lost about 50% of that gain. Of course if you write a more complex ray tracer where each pixel could result in hundreds of thousands of rays (diffraction, depth of field, area lighting, etc) then each pixel could reasonably be on its own thread.

 

[homercles337]

This is a good point. I wrote a multithreaded ray tracer and found that if I parallelized each row of pixels then I gained a 230% performance boost on a quad core machine versus serial processing. If I placed each pixel on its own thread I lost about 50% of that gain. Of course if you write a more complex ray tracer where each pixel could result in hundreds of thousands of rays (diffraction, depth of field, area lighting, etc) then each pixel could reasonably be on its own thread.

I did some GPGPU stuff and jaccard distances (boolean logic) resulted in a 2200% speed up with a single gtx 470. I see your 2.3x and laugh, ;-) I kid because im not a real programmer, just a scientific one.

 

[GodlessAstronomer]

I did some GPGPU stuff and jaccard distances (boolean logic) resulted in a 2200% speed up with a single gtx 470. I see your 2.3x and laugh, ;-) I kid because im not a real programmer, just a scientific one.

Yeah I had 3 weeks to learn how to write a ray tracer, how to write functional programs in F# and how to parallelize it (which was amazingly simple). I'm proud of what I achieved in this time
http://www.youtube.com/watch?v=NN-DanufrsA

 

[degibson]

Just to be my usual contentious self:

A recent ISCA paper: Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU
(from Intel)
http://portal.acm.org/citation.cfm?...&dl=GUIDE&CFID=11111111&CFTOKEN=2222222&ret=1

Other links to mostly same content:
http://visionexperts.blogspot.com/2010/07/debunking-x100-gpu-myth-intel-fights.html
and
http://www.multicoreinfo.com/2010/06/debunking-gpu/

My opinion: Not a myth, but there's a lot of non-science going on out there.

 

[Net]

do the chess engine project, then when its finished get a (C) account at www.freechess.org [ (C) stands for computer, i.e. an account that is ran by a chess engine instead of a human ], then complete against other (C) and/or human accounts and see how high of an ELO you guys can get.

connecting to fics:
http://www.freechess.org/Help/HelpFiles/addresses.html