[parsec-users] fluidanimate

Christian Bienia cbienia at CS.Princeton.EDU
Fri Jun 11 12:25:37 EDT 2010


Jim,

 

You're absolutely right, excellent comment. The main point I wanted to get
across in my last mail is that a good partitioning algorithm is currently
not available and will take some work. The current limitation of the number
of threads to powers of two only serves to prevent pathological partitions.

 

Best,

Chris

 

 

From: parsec-users-bounces at lists.cs.princeton.edu
[mailto:parsec-users-bounces at lists.cs.princeton.edu] On Behalf Of Jim
Dempsey
Sent: Friday, June 11, 2010 11:07 AM
To: 'PARSEC Users'
Subject: Re: [parsec-users] fluidanimate

 

Chris,

 

>>This was the motivation to only allow powers of two for the number of
threads - it guarantees that XDIVS and ZDIVS have comparable size.

 

But comparable size does not always yield comparable runtimes per partition.

 

The aboveassumption would be true if:

 

   (the computational overhead for interior cells == computational overhead
for boundary cells)

       .OR.

   (all partitions have same number of boundary cells)

 

We know due to locks/interlocks clause 1 is not true.

We know for 2D partitioning and partition counts larger than 4 clause 2 is
not always true.

 

See my earlier post.

 

An example diagram of equal computational requirements for an 8-way split
might look like the following

 

_______________________________

|    |   |   |   |     |

 

|    |   |   |   |     | 

|    |___|___|___|     | 

|    |   |   |   |     | 

|    |   |   |   |     | 

|_____|___|___|___|_____|

 

The volumes of the left most and right most partitions are larger (have more
cells/particles) but also have fewer boundary cells/particles. The ideal
partitioner would factor in the overhead difference between boundary and
non-boundary cell as well as perimeter of arena (overall box) verses
interior. IOW each cell, depending on juxtaposition with other cells and
partitions would have differing computational weights. Ideal partioning
would yield partitions of equal sums of weights.

 

Weighting classes

 

corners of box

edge of box not adjacent to corner or partition

surface of box not on edge of box and not adjacent to corner or partition

interior cell not adjacent to surface of box not on edge of box and not
adjacent to corner or partition

corner of partition at edge of box

corner of partition not at edge of box

edge of partition not at corner of partition

surface of partition not at corner or edge of partition

cell adjacent to partition adjacent to cell in same partition which is
adjacent to other partition

 

Did Imiss something?

 

The computations of the weights would depend on architecture of system. What
works best on one system may not work best on a different system and or
processor archetecture.

 

The most likely solution is to select a starting partitioning scheme (e.g.
like the 8-way above), then statistically measure the computation time for
each partition. After the average of measurements per partition converge,
then if the average differs by some delta, readjust the partition (move
partition wall(s) one cell). Then re-collect statistics, move walls, etc..
until partitioning stabilizes. Or auto re-partition n iterations. The
determined partitioning could be saved to a file for use on subsequent
simulation runs (thus permitting run without gathering statistics and
adjusting partitioning).

 

Note, in the earlier post suggested enhancement, where the container may
rotate (e.g. washing machine) it may be beneficial to keep
auto-repartitioning enabled, or periodically turn on and off.

 

The strategy of making many more partitions than you have threads will tend
to equalized the computational requirements

*** but also increases the ratio ofboundary cells/non-boundary cells
(counter productive) ***

 

Jim

 

 

  _____  

From: parsec-users-bounces at lists.cs.princeton.edu
[mailto:parsec-users-bounces at lists.cs.princeton.edu] On Behalf Of Christian
Bienia
Sent: Thursday, June 10, 2010 11:41 PM
To: 'PARSEC Users'
Subject: Re: [parsec-users] fluidanimate

Hey guys,

 

A few quick points regarding this:

 

.         As was pointed out it is possible to set the number of threads for
fluidanimate to anything by setting XDIVS and ZDIVS directly. This affects
how the program partitions the volume - the number of blocks is always XDIVS
* ZDIVS, each of which will be assigned to its own thread.

.         The communication-to-computation ratio of the program varies
significantly depending on the exact values of XDIVS and ZDIVS.
Communication happens at the surface of the partitions, computation is about
proportional to their volume. The comm-to-comp ratio is lowest if
XDIVS==ZDIVS because for those values the ratio of surface to volume is
minimal.

.         In extreme situations (such as if XDIVS * ZDIVS is a prime number)
you can get very different behavior. This was the motivation to only allow
powers of two for the number of threads - it guarantees that XDIVS and ZDIVS
have comparable size.

 

Best,

Chris

 

 

From: parsec-users-bounces at lists.cs.princeton.edu
[mailto:parsec-users-bounces at lists.cs.princeton.edu] On Behalf Of kishore
kumar
Sent: Thursday, June 10, 2010 10:03 PM
To: PARSEC Users
Subject: Re: [parsec-users] fluidanimate

 

Thank you, Jim.

Best,
Kishore 



2010/6/10 Jim Dempsey <jim at quickthreadprogramming.com>

>>I was curious whether this change hurts the overall functionality (I mean,
the output quality) of the application or not?

 

It won't make it any worse, other than for the fact that the original code
had permiable walls. Particles at the bottom of the container would exude
beyond the walls. You can observe this with visualizations enabled (look
closely at the bottom corners of the container)

I made corrections with this respect to all versions of the code. Now the
particles bounce properly off the walls.

 

Jim

 

 

  _____  

From: parsec-users-bounces at lists.cs.princeton.edu
[mailto:parsec-users-bounces at lists.cs.princeton.edu] On Behalf Of kishore
kumar

Sent: Thursday, June 10, 2010 8:43 PM


To: PARSEC Users
Subject: Re: [parsec-users] fluidanimate

 

Hi Jim,
Thank you for your inputs. 

I already ran fluidanimate with non-power-2 threads by bypassing the hamming
code and setting XDVIS and ZDIVS directly.  

 I was curious whether this change hurts the overall functionality (I mean,
the output quality) of the application or not?

Thank you.

Best,
Kishore Kumar Pusukuri
http://www.cs.ucr.edu/~kishore <http://www.cs.ucr.edu/%7Ekishore> 



2010/6/10 Jim Dempsey <jim at quickthreadprogramming.com>

I think it will work if you bypass the hamming code and directly set XDIVS
and ZDIVS (or input as parameters)

 

***

 

Note, force of gravity is along Y axis, therefore partitioning  XDIVS and
ZDIVS is appropriate. If gravity direction changes then partitioning may
need to change too. The hamming code was a strategy to obtain the largest
ratio of volume/area for partitions.

i.e. to reduce the proportion of cells at boundary (requiring interlocked
operations).

 

A more natural system of particles would have gravity in an arbitrary
direction.

My rewrite attempts to take this into consideration and the input parameter
for gravity (currently constant) will drive the partitioning.

 

I also I think it would be nice if the container could be other than a
rectangular tube, complex shapes, and be rotating.

An example would be a front load washing machine. Barrel shape with paddles.
Animation of this should look really nice - and the benchmark would then be
more of a real world example. (like body track, facesim, etc...)

 

Jim Dempsey

 

 

  _____  

From: parsec-users-bounces at lists.cs.princeton.edu
[mailto:parsec-users-bounces at lists.cs.princeton.edu] On Behalf Of kishore
kumar

Sent: Thursday, June 10, 2010 7:20 PM
To: PARSEC Users
Subject: Re: [parsec-users] fluidanimate

Thank you, Matt.

Best,
Kishore Kumar Pusukuri
http://www.cs.ucr.edu/~kishore <http://www.cs.ucr.edu/%7Ekishore> 



On 10 June 2010 17:08, Matt Sinclair <msinclair at wisc.edu> wrote:

Hi Kishore,

I don't think there's any reason you can't run non-powers-of-2 with
fluidanimate.  However, I believe that somewhere in the documentation
there's a "disclaimer" saying that the way it's set up is optimal.
So, changing XDIVS and ZDIVS will obviously change that.  It should
work though, regardless.

Hope this helps,
Matt
_______________________________________________
parsec-users mailing list
parsec-users at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/parsec-users

 


_______________________________________________
parsec-users mailing list
parsec-users at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/parsec-users

 


_______________________________________________
parsec-users mailing list
parsec-users at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/parsec-users

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/parsec-users/attachments/20100611/c3085211/attachment.html>


More information about the parsec-users mailing list