Algorithms that support parallelism?

Question

Incoming 10th grader here. I recently posted about a science fair project idea and someone suggested that I do "The Effect of Parallelism on selected computational tasks." I'm having difficulty figuring out what I should do for those "selected computational tasks." I've got about a year and a half of c# experience. I asked on freenode's ##programming and someone suggested I do Ray Tracing (http://65.39.148.34/KB/graphics/Simple_Ray_Tracing_in_C_.aspx). Any ideas for other easy-medium difficulty tasks that I could use in my experiment? Thanks.

Answer 1

I have a couple of suggestions. Even easier than ray tracing, you could do

• drawing Mandelbrot sets or
• Monte Carlo estimation of the area of arbitrary shapes (paint a random shape inside a bounding box; randomly generate points in the box; count the ratio of "hits" on "painted" bits to estimate the area of the random shape - the longer you run for, the more accurate your result will be; you can do several estimations in parallel and take the mean result).

If you want to do something more exciting, you could build a simulation of a pipelined RISC processor, where each pipeline stage runs in a separate thread.

Hope this helps!

EDIT: someone said that the first two suggestions are dull because they're embarrassingly parallel, to use the vernacular. They are embarrassingly parallel, but that's exactly what you want to show off, surely!

I really like the pipelined CPU simulation, but if that doesn't rock your boat, why not try something in between, like Conway's Game of Life? You can divide the grid into separate areas, each of which you can evolve in parallel, but the areas have to communicate along their boundaries. You could draw some interesting graphs about the speedup vs boundary size.

Answer 2

I'll give you a couple of tips that may prove useful.

The first is that you should read up about MapReduce. There are a lot of parallelizable tasks that are best parallelized with that technique.

The second is that you should include some task that requires locking and transactions in some way. For instance maintaining an accounting system that can handle money transfers reliably. The reason to include this is to show a practical example which doesn't parallelize. (After all if you just give examples that parallelize well, then the lesson people walk away with is that parallelization is easy. An example where it doesn't parallelize is a good antidote to that.)

Answer 3

• Quicksort
• Factorization of big numbers

Answer 4

The minimax search algorithm used in games like chess and checkers can be run in parallel to some extent, but it's not trivial since results in one part of the game tree can eliminate the need to search another part of it (which a you may already be doing in parallel).

Many things in image processing can be run in parallel. Box filters, FFTs, etc.

Other suggestions in the answers are all good too.

You really should post your areas of interest. There are usually some parts that can be run in parallel no mater what you're interested in, and following your area of interest will keep you on track and more productive. This is true of many programming concepts - they can be applied effectively in many many areas.

Answer 5

Some of the easiest tasks to parallelize are matrix multiplication and linear equation system solving. Or solving sudokus. Take your pick.