GPU-based agent-based modeling

[Stephen Guerin]

There's been some interest over the last couple months about using our graphics
cards (GPUs) to greatly speed up the computation of our simpler agent-based
models like 2D and 3D CAs.

Can it be done? Anyone interested?

At lunch today, we figured that perhaps the folks best suited to explore this
task are the same that use C for performance reasons instead of the higher
languages for syntactic sugar.

Here's a cool paper and support media from the Visualization '05 conference to
get started:

http://vis.computer.org/vis2005contest/schneider/
"We visualize the given data by means of our GPU-based particle engine. Designed
for interactive visualization of steady 3D flow fields, it achieves its high
frame rates by exploiting features of recent graphics processing units (GPU) for
particle advection. Particle attributes and the velocity field are kept in
graphics memory, avoiding any transfer across the bus for rendering. This allows
for rendering of millions of particles at interactive rates."


______________________________________________________________
stephen.guerin at redfish.com
http://www.redfish.com
624 Agua Fria Street, Santa Fe, NM 87501
Santa Fe, NM [phone] / London, UK [phone]

[Russell Standish]

Well if you stretch the meaning of ABM to include CAs, then yes CAs
are a good candidate for the SIMD style processing of GPUs. But in
order to get good performance, you will need to code this in as
non-agent style as possible!

In general GPUs and other SIMD style solutions will not help Agent
based modelling much. Sorry.

On Wed, Mar 01, 2006 at 02:44:36PM -0700, Stephen Guerin wrote:

> There's been some interest over the last couple months about using our graphics
> cards (GPUs) to greatly speed up the computation of our simpler agent-based
> models like 2D and 3D CAs.
>
> Can it be done? Anyone interested?
>
> At lunch today, we figured that perhaps the folks best suited to explore this
> task are the same that use C for performance reasons instead of the higher
> languages for syntactic sugar.
>
> Here's a cool paper and support media from the Visualization '05 conference to
> get started:
>
> http://vis.computer.org/vis2005contest/schneider/
> "We visualize the given data by means of our GPU-based particle engine. Designed
> for interactive visualization of steady 3D flow fields, it achieves its high
> frame rates by exploiting features of recent graphics processing units (GPU) for
> particle advection. Particle attributes and the velocity field are kept in
> graphics memory, avoiding any transfer across the bus for rendering. This allows
> for rendering of millions of particles at interactive rates."
>
>
> ______________________________________________________________
> stephen.guerin at redfish.com
> http://www.redfish.com
> 624 Agua Fria Street, Santa Fe, NM 87501
> Santa Fe, NM [phone] / London, UK [phone]
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org

--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.

----------------------------------------------------------------------------
A/Prof Russell Standish                  Phone [phone] (mobile)
Mathematics                               0425 253119 (")
UNSW SYDNEY 2052                 R.Standish at unsw.edu.au            
Australia                                http://parallel.hpc.unsw.edu.au/rks
            International prefix  +612, Interstate prefix 02
----------------------------------------------------------------------------

[Steve Smith]

> There's been some interest over the last couple months about using  
> our graphics
> cards (GPUs) to greatly speed up the computation of our simpler  
> agent-based
> models like 2D and 3D CAs.
>
> Can it be done? Anyone interested?
Yup... it can be (and has been) done...   CAs are a natural.   The  
GPU is a great "co-processor" for CA's with "reasonable  
neighborhoods" (like nearest neighbor).

The biggest limitation(s) of the GPU are things like... very  
localized memory access...  SIMD programming model...  high-latency  
overhead moving from GPU back to main memory.   The latter is being  
addressed (somewhat/maybe) with PCI express...

Caudell and his students and I have done several things.   One  
student implemented a Neural Net on the GPU, another was working on  
graph algorithms.

We are working (in the background) on adapting graph-layout  
algorithms to the GPU based on mean field approximation techniques  
and already proven approaches to Particle in a Cell (PIC) codes  
adapted to run in the GPU.

>
> At lunch today, we figured that perhaps the folks best suited to  
> explore this
> task are the same that use C for performance reasons instead of the  
> higher
> languages for syntactic sugar.
You have to be a lot more twisted than that... it's better for folks  
who really miss assembly coding.

>
> Here's a cool paper and support media from the Visualization '05  
> conference to
> get started:
>
> http://vis.computer.org/vis2005contest/schneider/
> "We visualize the given data by means of our GPU-based particle  
> engine. Designed
> for interactive visualization of steady 3D flow fields, it achieves  
> its high
> frame rates by exploiting features of recent graphics processing  
> units (GPU) for
> particle advection. Particle attributes and the velocity field are  
> kept in
> graphics memory, avoiding any transfer across the bus for  
> rendering. This allows
> for rendering of millions of particles at interactive rates."
>
>

   LANL has a GUI tool known as SCOUT that helps with GPU programming  
and it is being linked in with the Stanford "Brook" project.

www.ccs.lanl.gov/ccs1/docs/ScoutFY04-1.pdf

Unfortunately the learning curve in this game is pretty steep and by  
the time you learn enough to use even the leveraged tools (Brook,  
Scout, etc), you might as well work in the lower level tools and get  
the extra flexibility.  On top of that, it is a fast-moving target...  
card manufacturers are adding new features as fast as they can and  
unevenly documenting them.

- Steve

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://redfish.com/pipermail/friam_redfish.com/attachments/20060301/5d9766b2/attachment.htm

[Giles Bowkett]

> At lunch today, we figured that perhaps the folks best suited to explore
> this
> task are the same that use C for performance reasons instead of the higher
> languages for syntactic sugar.

> You have to be a lot more twisted than that... it's better for folks who
> really miss assembly coding.

I don't have any experience with this directly, like Steve, but that's
what I've heard too.

GPU coding gets used a bit in video games, iirc.

--
Giles Goat Boy

http://gilesmakesmusic.blogspot.com
http://gileswritescode.blogspot.com

[Jim Rutt]

Check out FPGAs as another alternative for highly parallel agent based
models (or certain other parallel problems).  It used to be you had to be a
chip designed to use the FPGA design tools from folks like Synopsys,
however in the last year or so two companies have delivered updated
versions of tools that realy work and make FPGA programming  accessible to
"software guys":  Viva from Starbridge (http://www.starbridgesystems.com)
and Handel C from Celoxica (http://www.celoxica.com) are two I've looked at
closely.   I wrote my first "FPGA program" in Viva in like 20
minutes!   I've carefully studied the Handel-C programmers reference and
expect one could write a simple FPGA program in Handel_C as quickly.

There is still an ugly several hour "place and route" bottleneck, where
software from the FPGA chip vendor (Xilinks for both Celoxica and
Starbridge http://www.xilinx.com/) takes the net-list that is produced by
"compiler" and actually figures out how to effectively layout the gates and
wires on the FPGA.

Fortunately both Celoxica and Starbridge offer a PC based FPGA simulator so
you can develop and debug code to at least the first order without having
to go thru "place and route".

I've been looking for an excuse to buy a "reconfigurable computer" based on
FPGAs .... so if someone has a clever application let me know!

=jim rutt


At 07:35 PM 3/1/2006, you wrote:

>>There's been some interest over the last couple months about using our
>>graphics
>>cards (GPUs) to greatly speed up the computation of our simpler agent-based
>>models like 2D and 3D CAs.
>>
>>Can it be done? Anyone interested?
>Yup... it can be (and has been) done...   CAs are a natural.   The GPU is
>a great "co-processor" for CA's with "reasonable neighborhoods" (like
>nearest neighbor).
>
>The biggest limitation(s) of the GPU are things like... very localized
>memory access...  SIMD programming model...  high-latency overhead moving
>from GPU back to main memory.   The latter is being addressed
>(somewhat/maybe) with PCI express...
>
>Caudell and his students and I have done several things.   One student
>implemented a Neural Net on the GPU, another was working on graph algorithms.
>
>We are working (in the background) on adapting graph-layout algorithms to
>the GPU based on mean field approximation techniques and already proven
>approaches to Particle in a Cell (PIC) codes adapted to run in the GPU.
>
>>
>>At lunch today, we figured that perhaps the folks best suited to explore this
>>task are the same that use C for performance reasons instead of the higher
>>languages for syntactic sugar.
>You have to be a lot more twisted than that... it's better for folks who
>really miss assembly coding.
>
>>
>>Here's a cool paper and support media from the Visualization '05
>>conference to
>>get started:
>>
>><http://vis.computer.org/vis2005contest/schneider/>http://vis.computer.org/vis2005contest/schneider/
>>"We visualize the given data by means of our GPU-based particle engine.
>>Designed
>>for interactive visualization of steady 3D flow fields, it achieves its high
>>frame rates by exploiting features of recent graphics processing units
>>(GPU) for
>>particle advection. Particle attributes and the velocity field are kept in
>>graphics memory, avoiding any transfer across the bus for rendering. This
>>allows
>>for rendering of millions of particles at interactive rates."
>>
>   LANL has a GUI tool known as SCOUT that helps with GPU programming and
> it is being linked in with the Stanford "Brook" project.
>
>www.ccs.lanl.gov/ccs1/docs/ScoutFY04-1.pdf
>
>Unfortunately the learning curve in this game is pretty steep and by the
>time you learn enough to use even the leveraged tools (Brook, Scout, etc),
>you might as well work in the lower level tools and get the extra
>flexibility.  On top of that, it is a fast-moving target... card
>manufacturers are adding new features as fast as they can and unevenly
>documenting them.
>
>- Steve
>
>============================================================
>FRIAM Applied Complexity Group listserv
>Meets Fridays 9a-11:30 at cafe at St. John's College
>lectures, archives, unsubscribe, maps at http://www.friam.org

===================================
Jim Rutt
voice:  505-989-1115

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://redfish.com/pipermail/friam_redfish.com/attachments/20060302/bb77c4c0/attachment.htm