# Algorithms that support parallelism?

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.

-

## migrated from stackoverflow.comApr 21 '11 at 21:36

This question came from our site for professional and enthusiast programmers.

Is there any area you like more than others? (there is huge amount of algorithm supporting parallelism) –  maxim1000 Apr 21 '11 at 5:26

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.

-

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.

-
Shared-nothing tasks are pretty boring except to work out how to use your language's parallelism primitives. –  sysrqb Apr 21 '11 at 4:15
Shared nothing "embarassingly parallel" tasks are important because they show that for some important tasks parallel solutions do really well. There are some nice tricks to make things shared-nothing too, such as special points. A nice summary is at cr.yp.to/talks/2005.06.11-1/slides.pdf –  mcdowella Apr 21 '11 at 4:40
Monte carlo in parallel requires some care in assuring that different threads get unique random numbers. Might be a bit challenging for a 10th grader. A good example, which shows tradoffs, is sorting, do you end up paying a penalty (doing more work) to use several processors versus just one? Even better, search an ordered list for a single value, binary search is the standard here for a single processor, show how much faster you can make it go with say eight processors. –  Omega Centauri Apr 21 '11 at 22:24
N-body gravity problem might be an interesting medium-difficulty problem because it is not shared-nothing. Programming Pearls has a chapter describing the thought process of its optimization. (that said, it might be too time-consuming) –  rwong Apr 23 '11 at 6:58
• Quicksort
• Factorization of big numbers
-

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.)

-

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

-
Intuitively, solving sudokus seems like something that would be very hard to parallelize. Doing it the naive way and branching on the game tree results in similar problems to doing that with games like chess - many very small tasks, where the overhead is greater than the gains from parallelization. Did you have a specific approach in mind? –  Nick Johnson Apr 21 '11 at 5:34
Sudokus can be solved using a multitude of algorithms, from brute forcing and backtracking to human-style elimination to using a SAT solver for it. Choose one that you feel comfortable with and then move on to a harder one if you feel like it. –  Michael Foukarakis Apr 21 '11 at 17:10