Trying to parallelize prime number sieve

[Lou Franco]

Today I tried to write a parallel prime number sieve with agents

http://www.loufranco.com/blog/files/20-Days-of-Clojure-Day-11.html

I found some oddities.  

1. my sequential prime number sieve seemed to use both of my CPU's

2. When I was done it ran much slower (my approach was very naive, admittedly)

3. await didn't seem to respect when ! called ! on another agent.  If I was awaiting on them both, it returned before the second one was done. The docs say (I think) say that this is the case -- await for ! called by this thread or the agent -- but I'd like if that was extended to one of the agents calling ! on another agent I am also awaiting on.

4. When I run with clojure.lang.Script, it doesn't exit

Any insights would be appreciated.  Here's the code:

(defn divisible? [x y] (= (rem x y) 0))

(defn check-divisible [agent x]

    (merge agent {:last x :notdivisible (not (divisible? x (:prime agent)))}))

(defn check-divisible-by-agents [agents x]

    (if (not= (count agents) 0)

    (! (first agents)

        (fn [a y rest-agents]

             (let [newstate (check-divisible a y)]

                (if (:notdivisible newstate)

                        (check-divisible-by-agents rest-agents y)

                        )

                newstate)) x (rest agents))))

(defn next-prime [agents ints]

    (let [x (first ints)]

        (check-divisible-by-agents (take-nth 2 agents) x)

        (check-divisible-by-agents (take-nth 2 (drop 1 agents)) x)

        (if (every? 

                (fn [a] 

                    (await a)     

                    (or (not= (:last @a) x)

                        (:notdivisible @a)))  

            agents)

                x

                (next-prime agents (rest ints)))))

(defn agent-sieve [a ints]

    (let [p (next-prime a ints)]

        (lazy-cons p (agent-sieve (cons (agent {:prime p}) a) (iterate inc (inc p))))))

(defn par-primes []

  (agent-sieve '() (iterate inc 2)))

(prn (take 50 (par-primes)))

[loumf]

My guess on the seeming parallelization of the sequential version is
that the other CPU is where the GC is running. Either that or somehow
clojure uses some of its concurrency support under the hoods of things
I'm using.

[christop...@gmail.com]

On Mar 12, 6:03 am, "Lou Franco" <loumfra...@gmail.com> wrote:
> Today I tried to write a parallel prime number sieve with agentshttp://www.loufranco.com/blog/files/20-Days-of-Clojure-Day-11.html
>
> I found some oddities.
>

> 4. When I run with clojure.lang.Script, it doesn't exit

This one seems easy to explain: that's because the thread pool uses
the default thread factory which creates non-daemon threads: the
program can't exit while these threads exists.

Christophe

[Rich Hickey]

That part is easy - there's no thread affinity, so even a single-
threaded job may be interleaved on the 2 CPUs - chances are the total
utilization between them is just 100%.

Haven't had a chance to look at the code...

Rich

[Rich Hickey]

On Mar 12, 1:03 am, "Lou Franco" <loumfra...@gmail.com> wrote:
> Today I tried to write a parallel prime number sieve with agentshttp://www.loufranco.com/blog/files/20-Days-of-Clojure-Day-11.html

>
> I found some oddities.
>
> 1. my sequential prime number sieve seemed to use both of my CPU's
> 2. When I was done it ran much slower (my approach was very naive,
> admittedly)
>

> Any insights would be appreciated.

I'm sorry to say I can't think of a less promising candidate for
parallelization :(

The 3 things you would want in something to parallelize are
independent data/work, moderate-to-course-grained work units and/or
complex coordination logic that would be simplified with threads.
(Note - wanting it to run faster is not enough :)

Here you have none of those - the data/work is interdependent (more
later), the work is very fine grained (seq walk and a remainder test),
and the logic was pretty elegant.

It ends up the sieve is inherently serial, that is, the value of the
sieve is that the twosie stage drops every other value so the threesie
stage never has to process it. Precisely to the extent you parallelize
it, you increase your work. You can see that as follows:

;a counter for divisible?
(def divs (ref 0))

;redefine w/counter

(defn divisible? [x y]
(sync nil (alter divs inc))

(= (rem x y) 0))

and use this definition in primes and par-primes.

(def divs (ref 0))
(prn (take 50 (primes)))
-> (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83
89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179
181 191 193 197 199 211 223 227 229)

@divs
-> 1518

;reset
(def divs (ref 0))
(prn (take 50 (par-primes)))
-> (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83
89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179
181 191 193 197 199 211 223 227 229)

@divs
-> 5735

So you're doing more than 3x the work, with substantial per-unit
overhead.

Unfortunately this effort is destined for disappointment. You might
want to try another problem.

Rich

[loumf]

Ok -- point taken. I guess if I need a list, I can have two sieves
and find two primes at a time. I just need to make sure that when I
find one that the other sieve is not processing a number less than
half of the one I found.

Thanks for looking at this.

[Mark H.]

Might be better, if you're looking for primes, to check out something
like Miller-Rabin:

http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

which has a natural parallelism (apply several different trials to the
same candidate).

mfh

[Mark H.]

Dear Lou -- I have an interest in parallel programming education, so I
have some examples of things which are easier to parallelize. You may
want to try out HW1 from the class that I helped TA last semester:

http://www.cs.berkeley.edu/~yelick/cs194f07/hw/hw1/hw1.pdf

It's at least nominally nontrivial, but it illustrates a number of
parallel programming concepts.

I might try working up an example of this assignment in Clojure, just
for fun.

Best,
mfh

[loumf]

Thanks. Actually with Christophe Grand's help, I got pretty far with
parallel prime number generation

http://www.loufranco.com/blog/files/20-Days-of-Clojure-Day-15.html

Christophe's solution is great if you are trying to find all primes as
fast as possible and not a bound list (his solution is part eager,
part lazy). The idea is not to find out if a single number is prime in
a parallel way, but to figure out the maximum list that can be split
without needing coordination. That list length grows as we get to
larger and larger numbers.