Parallel Game of Life

[Scott Fraser]

I have taken Larry's "Game of Life" example that he originally posted
here:

http://groups.google.com/group/clojure/msg/fdfc88f1ba95bdee

...and updated it to use all the CPU's your JVM has access to. My
first attempts ran into the classic map -> pmap slowdown. My next
attempt had too much dosync, in that there were many threads but they
were all waiting for each other.

I finally rewrote the calc-state routine to batch the units of work
into meaty sizes, and to minimize the dosync granularity. It gets the
batches of new-state together, then goes and applies these in batches.
In both events I use pmap.

Now it is running really fast on my 4-core Intel i7. You will really
notice a difference at larger grid sizes. On my i7 it keeps the 8 (due
to hyperthreading) "cpus" busy at about 60% when I run a huge grid.

I also updated paint-cells with a type hint that greatly reduces
reflection in that performance critical code.

I am very new to clojure and would appreciate feedback. I am concerned
I may have overcomplicated things with my usage of the map/pmap form.
I am guessing there may be a simpler way to write what I did.

Note at the start it will automatically select how many "available-
procs" you have. Try tweaking this on your hardware to see how it
impacts performance. Watching the threads with a profiler is
interesting.

Here is is:

(def cells (ref {}))
(def running (ref false))
;(def x-cells ( * 32 4))
;(def y-cells ( * 48 4))
(def x-cells 32)
(def y-cells 32)
(def range-cells (for [x (range x-cells) y (range y-cells)] [x y]))
(def length-range-cells (count range-cells))
(def cell-size 10)
(def life-delay 0)
(def life-initial-prob 3)
(def available-procs (.. java.lang.Runtime getRuntime
availableProcessors))

(defn determine-initial-state [x y]
(= 0 (rand-int life-initial-prob)))

(defn determine-new-state [x y]
(let [alive (count (for [dx [-1 0 1] dy [-1 0 1]
:when (and (not (= 0 dx dy))
(cells [ (mod (+ x dx) x-cells)
(mod (+ y dy) y-cells)]))]
:alive))]
(if (cells [x y])
(< 1 alive 4)
(= alive 3))))

(defn update-batch-of-new-cells [new-cells list-of-batches]
(dosync
(dorun (map #(commute new-cells assoc (first %) (second %))
list-of-batches))
))

(defn calc-batch-of-new-cell-states [cell-state batch-cells]
(doall (map
#(let [new-cell-state (cell-state (first %) (second %))]
[[(first %) (second %)] new-cell-state])
batch-cells)))

(defn calc-state [cell-state]
(let [new-cells (ref {})]
(dorun (pmap #(update-batch-of-new-cells new-cells %)
(pmap #(calc-batch-of-new-cell-states cell-state %)
(for [cpu (range available-procs)] (take-nth available-
procs (drop cpu range-cells))))))
(dosync (ref-set cells @new-cells))))

(defn paint-cells [#^java.awt.Graphics graphics]
(doseq [[[x,y] state] @cells]
(doto graphics
(. setColor (if state Color/RED Color/WHITE))
(. fillRect (* cell-size x) (* cell-size y) cell-size cell-
size))))

(defn toggle-thread [#^JPanel panel button]
(if @running
(do (dosync (ref-set running false))
(. button (setText "Start")))
(do (dosync (ref-set running true))
(. button (setText "Stop"))
(. (Thread.
#(loop []
(calc-state determine-new-state)
(. panel repaint)
(if life-delay (Thread/sleep life-delay))
(if @running (recur))))
start))))

(defn -main[]

(calc-state determine-initial-state)

(let [f (JFrame.)
b (JButton. "Start")
panel (proxy [JPanel] [] (paint [graphics] (paint-cells
graphics)))]

(doto f
(. setLayout (BorderLayout.))
(. setLocation 100 100)
(. setPreferredSize (Dimension. (* cell-size x-cells) (+ 60 (*
cell-size y-cells))))
(. add b BorderLayout/SOUTH)
(. add panel BorderLayout/CENTER)
(. setDefaultCloseOperation JFrame/EXIT_ON_CLOSE)
(. pack)
(. setVisible true))

(. b addActionListener
(proxy [ActionListener] []
(actionPerformed [evt] (toggle-thread panel b))))))

[bOR_]

Nice! A few more days of work and I've time to play with these kind of
things again. Here are some comments, based on your description.

As game of life is a cellular automata, you do not need any blocking
at all, so you could use agents, rather than refs. It does become an
asynchronous CA then, but that fits for game of life :).

Every cell would be an agent. Agents read the state of their
neighbouring cells and update their own state. If world is a vector of
agents, then (doseq [a world] (send a update)) (apply await world)
would update the whole grid once, using all the processors that java
can find.

[Larry Sherrill]

It would be interesting to throw gridgain (http://www.gridgain.com/)
into the mix and let people register their machines as part of a CA
grid. Not sure the remote overhead would pay for itself but it would
be interesting.

[Laurent PETIT]

Hello,

2009/3/16 bOR_ <boris....@gmail.com>

Nice! A few more days of work and I've time to play with these kind of
things again. Here are some comments, based on your description.

As game of life is a cellular automata, you do not need any blocking
at all, so you could use agents, rather than refs. It does become an
asynchronous CA then, but that fits for game of life :).

Every cell would be an agent. Agents read the state of their
neighbouring cells and update their own state. If world is a vector of
agents, then (doseq [a world] (send a update)) (apply await world)
would update the whole grid once, using all the processors that java
can find.

I'm not very used to concurrent programming, so I have a few questions you may find naïve, but well, let's just pretend they're interesting  ... :

It seems to me that the game of life works in "increments" of its "world". So I don't see at first what can be gained by using one agent for each cell. Because then, you'll still have to coordinate the work of the agents in your code.
I suspect you suggested to use agents because by using agents, you gain an abstraction for parallel programming for free, and that you are not using agent for what I think they are for in the first place: asynchronized computing.

Regards,

--
Laurent

[Kyle R. Burton]

On Mon, Mar 16, 2009 at 12:31 AM, Scott Fraser <Scott.E...@gmail.com> wrote:
>
> I have taken Larry's "Game of Life" example that he originally posted
> here:
>
> http://groups.google.com/group/clojure/msg/fdfc88f1ba95bdee
>

> ...and updated it to use all the CPU's your JVM has access to...

Scott,

Your changes indeed make it run significantly faster for me. Thanks!

I added a 'reset' button and changed some of the java method calls to
be a bit more (I think) idomatic clojure.

The full file is here:
http://asymmetrical-view.com/personal/code/clojure/life.clj

And a patch is attached (you also left off the import statements in you email).

FYI: Scott Fraser is giving a talk on clojure at the Philly Emerging
Technologies for the Enterprise conference next week:

http://phillyemergingtech.com/abstractsTab.php?sessID=39
http://phillyemergingtech.com/speakers.php

Regards,

Kyle Burton

--
------------------------------------------------------------------------------
kyle....@gmail.com http://asymmetrical-view.com/
------------------------------------------------------------------------------

[Larry Sherrill]

Hi Kyle,

I added life-conway.clj to the files section last week. It has rand,
clear, and bounded buttons, and the ability to use your mouse to draw
the pattern rather than rely on rand. It's a good way to experiment
with different automata such as gliders.

Larry Sherrill

On Mar 16, 9:33 am, "Kyle R. Burton" <kyle.bur...@gmail.com> wrote:

> On Mon, Mar 16, 2009 at 12:31 AM, Scott Fraser <Scott.E.Fra...@gmail.com> wrote:
>
> > I have taken Larry's "Game of Life" example that he originally posted
> > here:
>
> >http://groups.google.com/group/clojure/msg/fdfc88f1ba95bdee
>
> > ...and updated it to use all the CPU's your JVM has access to...
>
> Scott,
>
> Your changes indeed make it run significantly faster for me.  Thanks!
>
> I added a 'reset' button and changed some of the java method calls to
> be a bit more (I think) idomatic clojure.
>
> The full file is here:http://asymmetrical-view.com/personal/code/clojure/life.clj
>
> And a patch is attached (you also left off the import statements in you email).
>
> FYI: Scott Fraser is giving a talk on clojure at the Philly Emerging
> Technologies for the Enterprise conference next week:
>
>  http://phillyemergingtech.com/abstractsTab.php?sessID=39
>  http://phillyemergingtech.com/speakers.php
>
> Regards,
>
> Kyle Burton
>
> --
> --------------------------------------------------------------------------- ---

> kyle.bur...@gmail.com                            http://asymmetrical-view.com/
> --------------------------------------------------------------------------- ---
>
>  life.patch
> 3KViewDownload

[bOR_]

>
> I'm not very used to concurrent programming, so I have a few questions you
> may find naïve, but well, let's just pretend they're interesting  ... :

Learning here as well :).

>
> It seems to me that the game of life works in "increments" of its "world".
> So I don't see at first what can be gained by using one agent for each cell.
> Because then, you'll still have to coordinate the work of the agents in your
> code.

> I suspect you suggested to use agents because by using agents, you gain an
> abstraction for parallel programming for free, and that you are not using
> agent for what I think they are for in the first place: asynchronized
> computing.

Each cell in a cellular automata (of which game of life is an
example) only wants to change itself, based on certain rules and its
neighbours.. so there should never be any blocking. You are right that
the cellular automata would become asynchronous when using agents, and
whether or not you want that depends on what you want to simulate.
I'll see if I can write a agent-based version for it when time allows.
it will be a good exercise for me as well.

[Scott Fraser]

Larry, that you added mouse-drawing is awesome, I wanted to do that
too.

Kyle - my bad on the imports, thanks for the patch.

I will take all these and refold in when I get some time. I also have
some ideas on further speed ups. My gut tells me we could make this
run faster.

One other idea - add a throttle for the "available-procs" value, and a
real time "Frames Per Second" display. It would be interesting to
figure out on various hardware what is the right setting for available-
procs, which currently in this version is really more related to the
size and number of the chunks of work as opposed to how many threads
actually get deployed behind the scenes by pmap. Note that based on my
profiling, if I have 8 CPU's available, and I throw out there 8 chunks
of work, pmap is using a pool of 8 or so threads behind the scenes to
process the work. Would be good to understand how pmap sizes that
executor pool.

-Scott

[Scott Fraser]

I have not had a chance to merge the parallel updates in to life-
conway.clj in the files section yet, but for now I thought I would
note I did make one fun enhancement, which is to have each thread
color code the cells. So all cells with the same color were processed
by one pmap thread. On my 8-core it is quite colorful and fun.

As always, comments appreciate. Here is it:

-Scott

(import '(javax.swing JFrame JPanel JButton)
'(java.awt BorderLayout Dimension Color)
'(java.awt.event ActionListener))

(def cells (ref {}))
(def running (atom false))
(def x-cells ( * 32 1))
(def y-cells ( * 48 1))
;(def x-cells 32)

;(def y-cells 32)
(def range-cells (for [x (range x-cells) y (range y-cells)] [x y]))
(def length-range-cells (count range-cells))
(def cell-size 10)
(def life-delay 0)
(def life-initial-prob 3)
(def available-procs (.. java.lang.Runtime getRuntime
availableProcessors))

;(def available-procs 8)
(def batch-sets (for [cpu (range available-procs)] (take-nth available-
procs (drop cpu range-cells))))

; some things we will use to give each thread a different color
(def counter (ref 0))
(def color-list [Color/RED Color/ORANGE Color/GREEN Color/YELLOW Color/
BLUE Color/MAGENTA Color/PINK Color/CYAN])
(def num-colors (count color-list))
(def empty-color Color/BLACK)

(defn next-color []
(dosync (if (or (= @counter (dec num-colors)) (= @counter (dec
available-procs)))
(ref-set counter 0)
(alter counter inc))))

(defn determine-initial-state [x y]
(= 0 (rand-int life-initial-prob)))

(defn determine-new-state [x y]
(let [alive (count (for [dx [-1 0 1] dy [-1 0 1]
:when (and (not (= 0 dx dy))

(not (= empty-color (cells [ (mod
(+ x dx) x-cells) (mod (+ y dy) y-cells)]))))]
:alive))]
(if (not (= (cells [x y]) empty-color))

(< 1 alive 4)
(= alive 3))))

(defn update-batch-of-new-cells [new-cells list-of-batches]
(dosync
(dorun (map #(commute new-cells assoc (first %) (second %))
list-of-batches))
))

(defn calc-batch-of-new-cell-states [cell-state batch-cells]

( let [thread-color (nth color-list (next-color))]
doall (map
#(let [new-cell-state (if (cell-state (first %) (second
%)) thread-color empty-color)]

[[(first %) (second %)] new-cell-state])
batch-cells)))

(defn calc-state [cell-state]
(let [new-cells (ref {})]
(dorun (pmap #(update-batch-of-new-cells new-cells %)
(pmap #(calc-batch-of-new-cell-states cell-state %)

batch-sets)))

(dosync (ref-set cells @new-cells))))

(defn paint-cells [#^java.awt.Graphics graphics]
(doseq [[[x,y] state] @cells]
(doto graphics

(.setColor state)
(.fillRect (* cell-size x) (* cell-size y) cell-size cell-

size))))

(defn toggle-thread [#^JPanel panel button]
(if @running

(do (dosync (reset! running false))

(. button (setText "Start")))

(do (dosync (reset! running true))

(. button (setText "Stop"))
(. (Thread.
#(loop []
(calc-state determine-new-state)

(.repaint panel)

(if life-delay (Thread/sleep life-delay))
(if @running (recur))))
start))))

(defn -main[]

(calc-state determine-initial-state)

(let [f (JFrame.)
b (JButton. "Start")
panel (proxy [JPanel] [] (paint [graphics] (paint-cells
graphics)))]

(doto f
(.setLayout (BorderLayout.))
(.setLocation 100 100)

(.setPreferredSize (Dimension. (* cell-size x-cells) (+ 60 (*

cell-size y-cells))))
(.add b BorderLayout/SOUTH)
(.add panel BorderLayout/CENTER)
(.setDefaultCloseOperation JFrame/EXIT_ON_CLOSE)
(.pack)

(.setVisible true))

(. b addActionListener
(proxy [ActionListener] []
(actionPerformed [evt] (toggle-thread panel b))))))

On Mar 16, 11:51 am, Larry Sherrill <lps...@gmail.com> wrote: