# Looking for parallel programming problem

I am trying to come up with a problem that is easily solvable in a parallel manner and that requires communication between threads for a test. I also am trying to avoid problems that require require random waits, which rules out dining philosophers and producer-consumer (bounded buffer), two of the classics. My goal is for the student to be able to write the program in less than 20-30 minutes in front of a computer not knowing of the problem beforehand. (This is to prevent preparation more than to come up with something novel.) I am trying to stress the communication aspect of the program, though the multi-threaded nature is also important.

Does anyone have some ideas?

Edit: I'm using Google Go for the language and testing comprehension of the goroutines/channels combo vs an actors library that I authored.

-
Going to need a language here. –  TheLQ Sep 17 '10 at 0:12
I just saw this question. It is not very recent but have you thought about using merge sort? –  Giorgio Apr 7 '12 at 19:46

This presentation describes the use of channels to implement a prime number sieve. Very loosely, it works like this (sorry, don't know erlang, hopefully this pseudoerlang will be adequate):

``````numbers(num) =
numbers(num + 1)
end

filter(sourceChannel, predicate) =
sourceChannel ! { next, self() }
{ num } when predicate(num) == true -> replyChan ! { num }
{ _ } -> self() ! { next, replyChan }
end
filter(sourceChannel, predicate)
end

primes(currentNumberStream, number) =
print number
newNumberStream = spawn(filter, [currentNumberStream, fun x -> x % number <> 0])
newNumberStream ! { next, self() }
{ newPrime } -> prime(newNumberStream, newPrime)
end
end

// init with:
//    counter = spawn(numbers, [3])
//    primeStream = spawn(primes, [counter, 2])
``````

Starting with an infinite stream of numbers, you filter the stream by a prime. You get the next prime and filter the first stream by your new prime. Continue the process indefinitely, should output a sequence of prime.

I don't know if this is exactly what your looking for, but it should be a easy-to-understand introduction to channels and actors.

-
The linked presentation was very helpful, as was your suggestion. I ended up turning it into a on-paper design, then implement the sieve function for the program. –  Chris Lieb Sep 22 '10 at 23:25