Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

put on hold as too broad by Martijn Pieters, GlenH7, MichaelT, gnat, amon 17 hours ago

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

    
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

3 Answers 3

up vote 4 down vote accepted

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) =
    receive
        { next, replyChan } ->
            replyChan ! { num };
            numbers(num + 1)
    end

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

primes(currentNumberStream, number) =
    receive
        { next, replyChan } ->
            print number
            newNumberStream = spawn(filter, [currentNumberStream, fun x -> x % number <> 0])
            newNumberStream ! { next, self() }
            receive
                { 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.

share|improve this answer
    
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.

share|improve this answer
    
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

There are the easy version of The Cowichan Problems. They were thought to be quickly coded. My teacher presented them to us in a undergraduate course in parallel programming techniques. It is close of what you are looking for. I implemented some of them myself.

http://software-carpentry.org/blog/2010/06/the-cowichan-problems.html

share|improve this answer

protected by gnat yesterday

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.