[Impact-development] Discussion summary

[<jon...@ya...>]

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