# 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

I think modeling a chat server and the communication among their users could be a good idea. Is not abstract, can be modeled in top of well know systems (Facebook, messenger, Skype, twiter), is easy to explain and understand to students with not background in maths or software, and relate better to the kind of real/more common task that developers are in charge to solve. Plus, is not CPU/Bound. And is faster to grasp the idea and importance of scalability.

-
Isn't that more about concurrency rather than parallism? –  Thomas Eding Oct 1 '12 at 20:00
Can be both. Think in modeling sending a message to all the users across all the chatrooms, and each chatroom is a parallel task (or each slice of N users or as you wish) –  mamcx Oct 1 '12 at 20:50