impact-development Mailing List for Impact Finite Element Program

Hi,
first of all, thank you very much for this open source effort!
I am currently working on a translator between different FEM Solver formats.
I would like to use a common language (such as Fembic) and add some 
modules for reading and writing from different solvers formats, such as 
Radioss, Nastran and Code Aster.
I would greatly help me if you could share you work, even if not 
finished yet, such as the RadiossTrackWriter ... I also hope to be able 
to contribute with some code.

Thank you very much in advance, any advice is greatly appreciated!

Best Regards,
Luca

Dear Open Source developer

I am doing a research project on "Fun and Software Development" in which I kindly invite you to participate.
You will find the online survey under http://fasd.ethz.ch/qsf/. The questionnaire consists of 53 questions and you will need about 15 minutes to complete it.

With the FASD project (Fun and Software Development) we want to define the motivational significance of fun when software developers decide to engage in Open Source projects. What is special about our research project is that a similar survey is planned with software developers in commercial firms. This procedure allows the immediate comparison between the involved individuals and the conditions of production of these two development models. Thus we hope to obtain substantial new insights to the phenomenon of Open Source Development.


With many thanks for your participation,
Benno Luthiger


PS:
The results of the survey will be published under http://www.isu.unizh.ch/fuehrung/blprojects/FASD/.
We have set up the mailing list fa...@we... for this study. Please see http://fasd.ethz.ch/qsf/mailinglist_en.html for registration to this mailing list.

_______________________________________________________________________

Benno Luthiger
Swiss Federal Institute of Technology Zurich
8092 Zurich

Mail: benno.luthiger(at)id.ethz.ch
_______________________________________________________________________

Hi,

Jonas Forssell wrote:
> Never thought about that the doc could be generated if
> needed. Feel free to remove it.

Ok, the docs are gone. Use

    ant doc

in the base directory to regenerate documentation.

> Since I added it, my update times has been a pain (I'm
> behind a 56k modem), so removing it will help
> conciderably.

Hope, things turn better now...


Best regards,  Bernhard.

Bernhard,

Never thought about that the doc could be generated if
needed. Feel free to remove it.

Since I added it, my update times has been a pain (I'm
behind a 56k modem), so removing it will help
conciderably.

Thanks
/Jonas


 --- Bernhard Haumacher <ha...@ha...> skrev: >
Hi,
> 
> just to verify that Impact still compiles after
> reformatting, I added an
> Apache ant build description to the head branch.
> Having Apache ant
> installed (http://ant.apache.org/), type
> 
>     ant
> 
> in the base directory to have Impact built. To
> generate the API
> documentation run
> 
>     ant doc
> 
> All generated files are stored to a directory named
> build/.
> 
> I saw, that the generated API documentation seems to
> be stored in the
> repository, too. Is this necessary? It can easily be
> regenerated on demand.
> 
> 
> Best regards,  Bernhard.
> 
> 
> 
>
-------------------------------------------------------
> This SF.net email is sponsored by: SF.net Giveback
> Program.
> Does SourceForge.net help you be more productive? 
> Does it
> help you create better code?   SHARE THE LOVE, and
> help us help
> YOU!  Click Here: http://sourceforge.net/donate/
> _______________________________________________
> Impact-development mailing list
> Imp...@li...
>
https://lists.sourceforge.net/lists/listinfo/impact-development 

Höstrusk och grå moln - köp en resa till solen på Yahoo! Resor på adressen http://se.docs.yahoo.com/travel/index.html

Hi,

just to verify that Impact still compiles after reformatting, I added an
Apache ant build description to the head branch. Having Apache ant
installed (http://ant.apache.org/), type

    ant

in the base directory to have Impact built. To generate the API
documentation run

    ant doc

All generated files are stored to a directory named build/.

I saw, that the generated API documentation seems to be stored in the
repository, too. Is this necessary? It can easily be regenerated on demand.


Best regards,  Bernhard.

Hi,

I finished reformatting the Impact source using jalopy. I applied the
new style to the "HEAD" branch and the "parallel" branch.

To facilitate merging changes from the "HEAD" branch into the
"parallel" branch, I move the tag "Root_parallel" to the actual
revision, where the "parallel" branch really diverges (there were
commits to the "parallel" branch after the tag "Root_parallel" that
already merged changes from the "HEAD" branch to the "parallel"
branch).

Since the revision tagged with "Root_parallel" is now formatted in
another style than "HEAD" and "parallel", changes are still hard to
merge into the "parallel" branch. Therefore, I promoted the
"Root_parallel" tag to a branch and reformatted this version also.

Now the following diff can be applied to the parallel branch to bring
it in synch with the "HEAD" branch:

    cvs diff -u -r Root_parallel -r HEAD

The application of this patch only fails in the file "run/Smack.java",
because there have been lots of changes in the "parallel"
branch. Therefore, I did not yet apply this patch. This has to be done
by somebody who is familiar with the changes on the "parallel"
branch. Claus? :-)) Maybe you do that, when the parallel version
reaches some stability.

Best regards,   Bernhard Haumacher.

That's fine for me as well.

Regards,
Claus



Bernhard Haumacher wrote:

> Hi all,
>
> Jonas Forssell wrote:
>
>> Good idea!
>>
>> Looks neat. I'd like to commit some changes from Youriy first. Will
>> do that this weekend so Monday is a good time for you to do this.
>
>
> Ok, so if nobody else posts a veto :-), I'll start
>
>    Monday 2003-11-03 18:00 CET
>
> applying the suggested modifications to the Impact repository in the
> branches HEAD and parallel. Please have all your modifications checked
> in at this time, I'll post an announcement when I've got completed the
> check-in.
>
> Should I try to merge changes from the HEAD branch to the parallel
> branch before reformatting? Afterwards it may be difficult to resync the
> branches. What do you think Jonas and Claus?
>
>
> Best regards,   Bernhard.
>
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: SF.net Giveback Program.
> Does SourceForge.net help you be more productive?  Does it
> help you create better code?   SHARE THE LOVE, and help us help
> YOU!  Click Here: http://sourceforge.net/donate/
> _______________________________________________
> Impact-development mailing list
> Imp...@li...
> https://lists.sourceforge.net/lists/listinfo/impact-development

Bernhardt,

Please feel free to do that.

Thanks
/Jonas

 --- Bernhard Haumacher <ha...@ha...> skrev: >
Hi all,
> 
> Jonas Forssell wrote:
> > Good idea!
> > 
> > Looks neat. I'd like to commit some changes from
> Youriy first. Will
> > do that this weekend so Monday is a good time for
> you to do this.
> 
> Ok, so if nobody else posts a veto :-), I'll start
> 
>     Monday 2003-11-03 18:00 CET
> 
> applying the suggested modifications to the Impact
> repository in the
> branches HEAD and parallel. Please have all your
> modifications checked
> in at this time, I'll post an announcement when I've
> got completed the
> check-in.
> 
> Should I try to merge changes from the HEAD branch
> to the parallel
> branch before reformatting? Afterwards it may be
> difficult to resync the
> branches. What do you think Jonas and Claus?
> 
> 
> Best regards,   Bernhard.
> 
> 
> 
> 
>
-------------------------------------------------------
> This SF.net email is sponsored by: SF.net Giveback
> Program.
> Does SourceForge.net help you be more productive? 
> Does it
> help you create better code?   SHARE THE LOVE, and
> help us help
> YOU!  Click Here: http://sourceforge.net/donate/
> _______________________________________________
> Impact-development mailing list
> Imp...@li...
>
https://lists.sourceforge.net/lists/listinfo/impact-development 

Höstrusk och grå moln - köp en resa till solen på Yahoo! Resor på adressen http://se.docs.yahoo.com/travel/index.html

Hi all,

Jonas Forssell wrote:
> Good idea!
> 
> Looks neat. I'd like to commit some changes from Youriy first. Will
> do that this weekend so Monday is a good time for you to do this.

Ok, so if nobody else posts a veto :-), I'll start

    Monday 2003-11-03 18:00 CET

applying the suggested modifications to the Impact repository in the
branches HEAD and parallel. Please have all your modifications checked
in at this time, I'll post an announcement when I've got completed the
check-in.

Should I try to merge changes from the HEAD branch to the parallel
branch before reformatting? Afterwards it may be difficult to resync the
branches. What do you think Jonas and Claus?


Best regards,   Bernhard.

Hi,

what do you think of automatic source code formatting? This would also
solve the file encoding problems. I found a very neat tool at
SourceForge called "Jalopy", which applies coding conventions to
existing Java source code in a highly configurable way.

    http://sourceforge.net/projects/jalopy/

Of course, this can only be done in a hands-off/hands-on manner, because
it touches nearly all files in the repository and produces hardly
mergeable changes.

How files would look like after reformatting (with my personal favorite
coding style file :-)) can you see by looking at my local Impact working
copy, which I temporarily exported to the web at:

    http://www.ipd.uka.de/~hauma/Impact/

If we could agree about a time window in which such modification could
be done, I also offer to apply these changes (to the head and parallel
branch).


Best regards,    Bernhard Haumacher.

Bernhard,

Concider yourself a team member. I should have done
this long time ago :-) The CVS should work. If not,
please let me know and I'll change your permission.

The File ending is trickier. I understand exactly what
you refer to and will try to solve it ASAP.

Thanks
/Jonas

Höstrusk och grå moln - köp en resa till solen på Yahoo! Resor på adressen http://se.docs.yahoo.com/travel/index.html

Hi,

encoding of the line termination in Impact source files differ. Most of
the files are Unix-style with LF line termination, but some of them are
DOS-style with CRLF or Mac-style with CR only. Normally cvs should
adjust the encoding automatically upon checkout/checkin, but here, the
encoding is probably broken in the repository. At least my development
tools do not cope well with this mixture of encodings (diff does produce
one line, complete file diffs for Mac-encoded files). Could we fix that
by switching the following files to Unix encoding?

run/elements/Contact_Triangle.java:              CR line terminators
run/elements/Shell_C0_3.java:                    CR line terminators
run/elements/Contact_Line.java:                  CR line terminators
post/VerticalFlowLayout.java:                    CRLF line terminators


Best regards,  Bernhard Haumacher.

Hi Jonas,

is it possible to add me to the Impact developers? I will not contribute
much code, but I want to get access to the primary CVS server of the
project, because I like to see Claus's changes immediately without
waiting 24h for the backup CVS to update. If I could select a role, I
would whish "Advisor/Mentor/Consultant" :-)).


BTW my SourceForge ID is haui.


Best regards,  Bernhard Haumacher.

Hello Claus,

To test the new list and to give you some backgound, I
post the discussion me and Bernhard had prior to your
participation. There might be some good input there to
your model. Hope it is readable.

All the best
/Jonas


************* Message 1
*********************************************

Hi Jonas,

 > I have chosen to make parallell capability of
Impact the next
 > release theme (starting pretty soon).
 >
 > JavaParty will be the basis.
 >
 > Do you have any recommendation for me on how to
proceed? I know you
 > had concerns about the speed benefit last time we
"spoke".

First, you have to think about how to partition a
model into parts
that are minimal connected. As I've understood, the
model is the
central part of Impact. Each computation step uses the
current state
of a model node and its neighbors to compute a
modification in the
first half and applies this modification to the node
in the second
half. If you want to distribute the partitioned model
do different
nodes, you must make sure that this distribution
maximizes
locality. This means that most of the neighbor
relations of model
nodes point to nodes in the same partition. This
minimizes remote
accesses and maximizes performance.

The second step - the parallelization - is
algorithmically trivial:
Allocate each partition on a separate computing node
and create a
thread for each partition that performs the steps
"exchange the border
of the partition with neighbor nodes" "synchronize
with other threads"
"compute the modification" "apply the modifications".
This is what the
single processor version does except for the first two
steps.

To implement this in a nice and transparent way will
be pretty hard
:-). JavaParty does not alleviate implementing data
structures that
are spread over multiple VMs. The basic approach of
JavaParty only
distributes a data structure to some node as a whole.

    In detail: A remote object (an instance of a class
that is declared
    remote) and all the local objects that this remote
object
    references build up a data structure that is
assigned to a node as
    a whole. You can see a remote object as having its
own private
    address space. One can access this data structure
(the address
    space of a remote object) only through the remote
object that
    serves a single access point. But in exchange this
access is
    possible from all over the distributed
environment.

In your case, if you see the model as one single data
structure, it
will be allocated on only one node and the
parallelization approach
sketched above will not work.

    In detail: The JavaParty realization of this
inappropriate solution
    would be a remote class say "Model" that
internally keeps track of
    all node objects. All accesses to the node objects
are now forced
    to go through the Model object. You never get a
direct reference to
    a node object outside the model, because local
objects are deeply
    copied when used as method arguments and return
values in calls to
    a remote object. This enforces the private address
space property.

The approach to the other extreme would be to see each
node as a
single data structure that can be accessible globally.
Then you could
distribute each node object to some computer and keep
track that nodes
in the same partition get allocated on the same VM. In
this case all
references from a node to its neighbor nodes are
global references
that may point to an object allocated in another VM.
When computing
the modification of a node in the border of a
partition by accessing
its neighbors, method calls that access neighbors on a
remote machine
are remote method invocations and the other ones are
"nearly" local
method invocations. Here everything works really
transparently. The
drawback of this approach is that each node object has
its own private
address space and cannot share local data with another
remote
object. Everything referenced from such remote node
object (the
material description, and whatever...) is private to
that node object
(each node will end up having its private copy).

To make an object transparently accessible from remote
nodes there is
some non-negligible overhead in terms of space and
access time. If you
have thousands of such node objects, you will
experience resource
problems on your machines. What's worse, when
accessing such remote
node object - and there will be thousands times the
connectivity of a
node such accesses - each access, even if it's a local
access, is by
some factor slower than an access to a regular local
object. Even if
JavaParty tries to minimize this access penalty for
local accesses to
potentially remote objects, this can become the main
performance
bottleneck. The good thing with this approach is that
it is "almost
trivial" to implement in JavaParty - but I'm afraid
that you could be
disappointed by the performance.

   In detail: Just declare the node class "remote" and
make sure that
   all nodes in one partition get allocated on the
same machine. You
   even do not need the first step "exchange data" in
the
   parallelization scheme sketched above, because the
data is accessed
   on demand in a remote method invocation.

The optimal solution would be a model data structure
that itself is
spread around the participating virtual machines. The
border of each
partition should be available as local copy on each
neighboring
machine. In this case, the computation step on each
machine can be
performed truly local without any performance
obstacle. The "exchange
data" step now must bring the replicated border of the
spread data
structure in sync (copy the modifications to a node on
the border to
all machines that have a copy of such node).
Unfortunately, JavaParty
does not help much programming such a scheme.

   In detail: One could have some number of remote
classes say
   Partition that encapsulate a partition of the
model. Each partition
   object could be allocated on some machine and
access each other
   partition object for data exchange. The node
objects in a partition
   could stay as regular local Java objects. Now the
computation step
   within one partition could be exactly the same as
in the single
   threaded version of the program. The complex part
is to exchange the
   modifications done to the border of each partition
with neighboring
   partitions. This is not impossible to do, but there
is no black
   magic built into JavaParty that does this for you.

Currently, I'm working on some form of replication
within
JavaParty. The goal is to have replicated objects
beside remote
ones. The idea is that a replicated object is not
allocated on a
dedicated machine, but is locally accessible on each
VM with some form
of consistency protocol. Unfortunately, replicated
objects - at least
the replicated objects I'm thinking about at the
moment - do not solve
your problem, either. In your case, the "border" of a
partition must
be replicated on each machine that keeps a neighboring
partition. Obviously, the decision whether a node
belongs to the
border and which are the partitions a border node
belongs to cannot be
done transparently... and I'm thinking of transparent
replicated
objects...

Anyway, during my quest for replicated objects, I
started implementing
an "differencing and patching facility" for object
graphs. Maybe this
could be useful to find the modifications of the
border of a partition
and apply these modifications to the copies of the
border nodes on
other machines (this could be a piece of the black
magic, you are
looking for :-). Basically, one puts an object and all
its referenced
objects under patch control. This creates a backup
copy of the object
graph that is used later on for finding differences.
Now one can
modify the original object graph (by changing instance
variables,
adding more objects to the graph, and removing other
objects from the
graph). After that one can create a patch that
encapsulates the
difference of the original and its backup copy. This
patch can be seen
as the output of the unix diff command applied to
object graphs. The
patch can now be applied to a corresponding object
graph that
potentially resides on another virtual machine. This
facility can be
used to keep object graphs on different virtual
machines in sync.


Now I think, I've written more than one is willing to
read at a
time... I whish you a happy weekend. Here will be a
(controlled :-))
blackout this weekend here, so we will shutdown all
machines today
afternoon. Therefore, my e-mail and the JavaParty web
site will be
offline until Monday morning (in the worst case)...


Best regards,  Bernhard.                              
              


*************** Message 2
*********************************************
Hi Jonas,

since my last e-mail regarding the parallelization of
Impact and the
possible usage of JavaParty as parallelization
platform (did you get
this mail - the long one?) I intensively thought about
extensions to
JavaParty that would ease parallelizing such problems
like Impact.

Bye the way, at the time I wrote my last mail, I had
not read your
release plan for Impact. You mention there
parallelization at several
granularity levels (solving multiple models
concurrently and solving
one model in parallel). I only thought about the
second fine-grained
parallelization approach, because this is the
interesting one from my
point of view. Of cause the first one is also possible
and can be done
already easily using JavaParty: Encapsulate a whole
model within a
remote object, allocate multiple remote objects on
multiple nodes, and
start solving them using different threads. Because
there is no
interaction between these threads, all classes that
represent the
model nodes can stay as local ones - and you will get
the same
efficiency of the sequential program for each solution
(except the
time that is necessary to send the model to the remote
node during the
creation of the encapsulating remote object).

Currently, I'm thinking about having a data structure
of linked
regular Java objects distributed among several
machines. Each machine
could get a partition of the whole structure plus an
amount of shared
objects that are required on multiple machines. The
border of each
partition of this data structure - the shared objects
- would be
replicated at the machines that are using them. Now
several threads -
at least one per machine - could operate on their
local objects and
update them. After one update step and just before a
local thread
needs to see the modification of its neighbors, all
machines could
consistently update the shared objects by re-playing
modifications
done to them on other nodes.

To make things easier for the beginning, the
programmer would provide
the distribution function that decides, which object
is required on
witch machine. I'm not yet sure about the concrete API
of this
function, but it must at least provide information
like the following:

    boolean isShared(Object obj)
    boolean isRequiredAt(Object obj, int node)

Maybe, it would be better to move these methods to an
interface that
the distributed objects must implement.

What do you think about the proposal? Do you think,
you could provide
such distribution information for a model of Impact?

Best regards,  Bernhard.

********************** Message 3
***************************************

Hi Jonas,

 > I recieved both your mails and it got me thinking. 
It is clear that
 > I will need to write a small prototype before the
writing on the
 > next version begins.

The best strategy would be to first parallelize the
code before
distributing it. Debugging a Java parallel Java
program is hard,
debugging a distributed one can become really
annoying.

A parallel non-distributed version is useful anyway.
It stays pure
Java, and can serve as benchmark for the distributed
version. If the
non-distributed one does not scale, you can not expect
the distributed
one to scale.

All steps required for parallelization are also
required for
distribution. Partition the model among several
threads, create worker
threads, define synchronization points where the
workers must exchange
data.

 > I agree with your thinking on the API. It would be
 > ideal if the object itself can determine if it is
time
 > to change host.
 > In the case of Impact, the nodes and elements are
the
 > objects to migrate. 80 % of the work is done in the
 > elements, so they are most critical. The function
 > there would be for the element to check its nodes
to
 > see which host they are on, and if most of them are
on
 > another host, it is time for the element to migrate
 > there as well.

This sounds little much automatic. For getting started
- and again for
having a benchmark for comparison - I think it could
be useful to have
an algorithm that looks at the model and decides which
element is
computed by which thread to minimize accesses to
"foreign"
elements/nodes. Normally an automatism does not better
than the
informed programmer.

 > What will the node criteria be then? Well, since
the
 > problem already from the start is divided into
 > sections of the model (partitioned), which
corresponds
 > well with the contact algorithm configuration, the
 > time to complete one time step for all the elements
 > and nodes within a partition would be the criteria.
 >
 > For example, if a node finds that it took 20%
longer
 > time to complete the calculation within it's
current
 > partition, compared with it's neighbour partition,
 > this would be a trigger to move to that partition
 > instead. Ideally, a range of nodes and elements
along
 > the partition border would then move and
effectively,
 > the partition border change.
 > This would then give automatic load balancing,
 > assuming that the partitions are placed on separate
 > hosts.

Yes, that would be a great thing, when the basics are
working
well. But I would start with little steps :-)

 > So, your assumption of an interface is perfectly
 > feasable and I think this is the way to go.

I'm now working on a JavaParty extension that allows
graphs of regular
Java objects to be replicated among several virtual
machines. If you
think of the Impact model as such a graph, this
extension could make
it available on more than on virtual machine. A thread
on each machine
can now make updates to the graph. After each update
step, all threads
merge their changes and go ahead seeing the changes of
their
neighbors. Using such feature, I expect it would be
easy to move from
a parallel version of Impact to a (efficient?)
parallel distributed
one.

I let you know, if I've got something to show.


Best regards,   Bernhard.


Höstrusk och grå moln - köp en resa till solen på Yahoo! Resor på adressen http://se.docs.yahoo.com/travel/index.html

Hello Claus,

To test the new list and to give you some backgound, I
post the discussion me and Bernhard had prior to your
participation. There might be some good input there to
your model. Hope it is readable.

All the best
/Jonas


************* Message 1
*********************************************

Hi Jonas,

 > I have chosen to make parallell capability of
Impact the next
 > release theme (starting pretty soon).
 >
 > JavaParty will be the basis.
 >
 > Do you have any recommendation for me on how to
proceed? I know you
 > had concerns about the speed benefit last time we
"spoke".

First, you have to think about how to partition a
model into parts
that are minimal connected. As I've understood, the
model is the
central part of Impact. Each computation step uses the
current state
of a model node and its neighbors to compute a
modification in the
first half and applies this modification to the node
in the second
half. If you want to distribute the partitioned model
do different
nodes, you must make sure that this distribution
maximizes
locality. This means that most of the neighbor
relations of model
nodes point to nodes in the same partition. This
minimizes remote
accesses and maximizes performance.

The second step - the parallelization - is
algorithmically trivial:
Allocate each partition on a separate computing node
and create a
thread for each partition that performs the steps
"exchange the border
of the partition with neighbor nodes" "synchronize
with other threads"
"compute the modification" "apply the modifications".
This is what the
single processor version does except for the first two
steps.

To implement this in a nice and transparent way will
be pretty hard
:-). JavaParty does not alleviate implementing data
structures that
are spread over multiple VMs. The basic approach of
JavaParty only
distributes a data structure to some node as a whole.

    In detail: A remote object (an instance of a class
that is declared
    remote) and all the local objects that this remote
object
    references build up a data structure that is
assigned to a node as
    a whole. You can see a remote object as having its
own private
    address space. One can access this data structure
(the address
    space of a remote object) only through the remote
object that
    serves a single access point. But in exchange this
access is
    possible from all over the distributed
environment.

In your case, if you see the model as one single data
structure, it
will be allocated on only one node and the
parallelization approach
sketched above will not work.

    In detail: The JavaParty realization of this
inappropriate solution
    would be a remote class say "Model" that
internally keeps track of
    all node objects. All accesses to the node objects
are now forced
    to go through the Model object. You never get a
direct reference to
    a node object outside the model, because local
objects are deeply
    copied when used as method arguments and return
values in calls to
    a remote object. This enforces the private address
space property.

The approach to the other extreme would be to see each
node as a
single data structure that can be accessible globally.
Then you could
distribute each node object to some computer and keep
track that nodes
in the same partition get allocated on the same VM. In
this case all
references from a node to its neighbor nodes are
global references
that may point to an object allocated in another VM.
When computing
the modification of a node in the border of a
partition by accessing
its neighbors, method calls that access neighbors on a
remote machine
are remote method invocations and the other ones are
"nearly" local
method invocations. Here everything works really
transparently. The
drawback of this approach is that each node object has
its own private
address space and cannot share local data with another
remote
object. Everything referenced from such remote node
object (the
material description, and whatever...) is private to
that node object
(each node will end up having its private copy).

To make an object transparently accessible from remote
nodes there is
some non-negligible overhead in terms of space and
access time. If you
have thousands of such node objects, you will
experience resource
problems on your machines. What's worse, when
accessing such remote
node object - and there will be thousands times the
connectivity of a
node such accesses - each access, even if it's a local
access, is by
some factor slower than an access to a regular local
object. Even if
JavaParty tries to minimize this access penalty for
local accesses to
potentially remote objects, this can become the main
performance
bottleneck. The good thing with this approach is that
it is "almost
trivial" to implement in JavaParty - but I'm afraid
that you could be
disappointed by the performance.

   In detail: Just declare the node class "remote" and
make sure that
   all nodes in one partition get allocated on the
same machine. You
   even do not need the first step "exchange data" in
the
   parallelization scheme sketched above, because the
data is accessed
   on demand in a remote method invocation.

The optimal solution would be a model data structure
that itself is
spread around the participating virtual machines. The
border of each
partition should be available as local copy on each
neighboring
machine. In this case, the computation step on each
machine can be
performed truly local without any performance
obstacle. The "exchange
data" step now must bring the replicated border of the
spread data
structure in sync (copy the modifications to a node on
the border to
all machines that have a copy of such node).
Unfortunately, JavaParty
does not help much programming such a scheme.

   In detail: One could have some number of remote
classes say
   Partition that encapsulate a partition of the
model. Each partition
   object could be allocated on some machine and
access each other
   partition object for data exchange. The node
objects in a partition
   could stay as regular local Java objects. Now the
computation step
   within one partition could be exactly the same as
in the single
   threaded version of the program. The complex part
is to exchange the
   modifications done to the border of each partition
with neighboring
   partitions. This is not impossible to do, but there
is no black
   magic built into JavaParty that does this for you.

Currently, I'm working on some form of replication
within
JavaParty. The goal is to have replicated objects
beside remote
ones. The idea is that a replicated object is not
allocated on a
dedicated machine, but is locally accessible on each
VM with some form
of consistency protocol. Unfortunately, replicated
objects - at least
the replicated objects I'm thinking about at the
moment - do not solve
your problem, either. In your case, the "border" of a
partition must
be replicated on each machine that keeps a neighboring
partition. Obviously, the decision whether a node
belongs to the
border and which are the partitions a border node
belongs to cannot be
done transparently... and I'm thinking of transparent
replicated
objects...

Anyway, during my quest for replicated objects, I
started implementing
an "differencing and patching facility" for object
graphs. Maybe this
could be useful to find the modifications of the
border of a partition
and apply these modifications to the copies of the
border nodes on
other machines (this could be a piece of the black
magic, you are
looking for :-). Basically, one puts an object and all
its referenced
objects under patch control. This creates a backup
copy of the object
graph that is used later on for finding differences.
Now one can
modify the original object graph (by changing instance
variables,
adding more objects to the graph, and removing other
objects from the
graph). After that one can create a patch that
encapsulates the
difference of the original and its backup copy. This
patch can be seen
as the output of the unix diff command applied to
object graphs. The
patch can now be applied to a corresponding object
graph that
potentially resides on another virtual machine. This
facility can be
used to keep object graphs on different virtual
machines in sync.


Now I think, I've written more than one is willing to
read at a
time... I whish you a happy weekend. Here will be a
(controlled :-))
blackout this weekend here, so we will shutdown all
machines today
afternoon. Therefore, my e-mail and the JavaParty web
site will be
offline until Monday morning (in the worst case)...


Best regards,  Bernhard.                              
              


*************** Message 2
*********************************************
Hi Jonas,

since my last e-mail regarding the parallelization of
Impact and the
possible usage of JavaParty as parallelization
platform (did you get
this mail - the long one?) I intensively thought about
extensions to
JavaParty that would ease parallelizing such problems
like Impact.

Bye the way, at the time I wrote my last mail, I had
not read your
release plan for Impact. You mention there
parallelization at several
granularity levels (solving multiple models
concurrently and solving
one model in parallel). I only thought about the
second fine-grained
parallelization approach, because this is the
interesting one from my
point of view. Of cause the first one is also possible
and can be done
already easily using JavaParty: Encapsulate a whole
model within a
remote object, allocate multiple remote objects on
multiple nodes, and
start solving them using different threads. Because
there is no
interaction between these threads, all classes that
represent the
model nodes can stay as local ones - and you will get
the same
efficiency of the sequential program for each solution
(except the
time that is necessary to send the model to the remote
node during the
creation of the encapsulating remote object).

Currently, I'm thinking about having a data structure
of linked
regular Java objects distributed among several
machines. Each machine
could get a partition of the whole structure plus an
amount of shared
objects that are required on multiple machines. The
border of each
partition of this data structure - the shared objects
- would be
replicated at the machines that are using them. Now
several threads -
at least one per machine - could operate on their
local objects and
update them. After one update step and just before a
local thread
needs to see the modification of its neighbors, all
machines could
consistently update the shared objects by re-playing
modifications
done to them on other nodes.

To make things easier for the beginning, the
programmer would provide
the distribution function that decides, which object
is required on
witch machine. I'm not yet sure about the concrete API
of this
function, but it must at least provide information
like the following:

    boolean isShared(Object obj)
    boolean isRequiredAt(Object obj, int node)

Maybe, it would be better to move these methods to an
interface that
the distributed objects must implement.

What do you think about the proposal? Do you think,
you could provide
such distribution information for a model of Impact?

Best regards,  Bernhard.

********************** Message 3
***************************************

Hi Jonas,

 > I recieved both your mails and it got me thinking. 
It is clear that
 > I will need to write a small prototype before the
writing on the
 > next version begins.

The best strategy would be to first parallelize the
code before
distributing it. Debugging a Java parallel Java
program is hard,
debugging a distributed one can become really
annoying.

A parallel non-distributed version is useful anyway.
It stays pure
Java, and can serve as benchmark for the distributed
version. If the
non-distributed one does not scale, you can not expect
the distributed
one to scale.

All steps required for parallelization are also
required for
distribution. Partition the model among several
threads, create worker
threads, define synchronization points where the
workers must exchange
data.

 > I agree with your thinking on the API. It would be
 > ideal if the object itself can determine if it is
time
 > to change host.
 > In the case of Impact, the nodes and elements are
the
 > objects to migrate. 80 % of the work is done in the
 > elements, so they are most critical. The function
 > there would be for the element to check its nodes
to
 > see which host they are on, and if most of them are
on
 > another host, it is time for the element to migrate
 > there as well.

This sounds little much automatic. For getting started
- and again for
having a benchmark for comparison - I think it could
be useful to have
an algorithm that looks at the model and decides which
element is
computed by which thread to minimize accesses to
"foreign"
elements/nodes. Normally an automatism does not better
than the
informed programmer.

 > What will the node criteria be then? Well, since
the
 > problem already from the start is divided into
 > sections of the model (partitioned), which
corresponds
 > well with the contact algorithm configuration, the
 > time to complete one time step for all the elements
 > and nodes within a partition would be the criteria.
 >
 > For example, if a node finds that it took 20%
longer
 > time to complete the calculation within it's
current
 > partition, compared with it's neighbour partition,
 > this would be a trigger to move to that partition
 > instead. Ideally, a range of nodes and elements
along
 > the partition border would then move and
effectively,
 > the partition border change.
 > This would then give automatic load balancing,
 > assuming that the partitions are placed on separate
 > hosts.

Yes, that would be a great thing, when the basics are
working
well. But I would start with little steps :-)

 > So, your assumption of an interface is perfectly
 > feasable and I think this is the way to go.

I'm now working on a JavaParty extension that allows
graphs of regular
Java objects to be replicated among several virtual
machines. If you
think of the Impact model as such a graph, this
extension could make
it available on more than on virtual machine. A thread
on each machine
can now make updates to the graph. After each update
step, all threads
merge their changes and go ahead seeing the changes of
their
neighbors. Using such feature, I expect it would be
easy to move from
a parallel version of Impact to a (efficient?)
parallel distributed
one.

I let you know, if I've got something to show.


Best regards,   Bernhard.


Höstrusk och grå moln - köp en resa till solen på Yahoo! Resor på adressen http://se.docs.yahoo.com/travel/index.html