\section{Error Checking}

It would be useful to detect erroneous uses of the RMA interface by application

codes.  It should be possible to detect all errors involving a single process

at the origin.  Errors involving multiple processes, however, will undoubtably

need to be detected at the target.  To aid in this detection at the target, one

could either mark bytes in the local window to detect collisions or log each

operation and compare their target buffers for overlaps.  In either case, one

only needs to detect access collisions for the duration of an exposure epoch.

This is complicated slightly by the ability of a shared lock being able to

effectively join an exposure epoch already in progress.

The logging technique would provide slightly more detail since the exact

processes issuing the illegal operations would be known.  Logging has the

disadvtange of potentially unbounded memory consumption.  Detecting overlaps in

any two target buffers will also be computationally expensive.  For passive

target synchronization, this extra computation will almost certainly change the

relative timing between the processes and thus decreasing the chances of

detecting an error.  For active target syncrhonization, the extra overhead of

logging should not affect the ability to detect an error since the epochs are

well defined.

The byte marking technique should provide better performance over logging.

And, while its memory consumption is bounded, that consumption is guaranteed to

be a large fraction of the window.  For each byte in the window, we really need

three bits, one for each of the possible operations (put, get, and accumulate).

It might useful to keep a list of the processes that accessed the window so

that the potential violators can be reported to the user.

Ok.  We can do this with 2 bits actually, indicating what has occurred already:

00 - nothing

01 - put

10 - get

11 - accumulate

Then you can test to see if future operations break the rules.

proposal:

- allow people to at compile time compile OUT additional debugging stuff with a

  flag (in by default)

- allow it to be turned on and off at runtime via env. variable or whatever

----------

\section{passive target accumulate, exclusive lock}

you have an exclusive lock, you're doing a get on one set of things and

an accumulate on another set of things.

assume they are nonoverlapping datatypes.

mpi_win_lock(exclusive, rank, assert, win)

mpi_get(A,...)

mpi_accumulate(B,...,sum)

mpi_win_unlock()

for cache coherent shared memory (only)

---------------------------------------

one option:

  lock the appropriate window with interprocess_lock()

  do the get

  do the accumulate

  interprocess_unlock()

- if the regions of the window didn't overlap, it might be better to 

  lock only the region(s) of interest.

- if the window is local, then this is the option to use

another option:

  don't do anything much on win_lock

  cache get

  cache acc

  interprocess_lock(), do get, do acc, unlock() as a result of win_unlock()

reordering of cached access could maybe be a win...

for remotely accessible memory (only)

-------------------------------------

there will be a lock on the remote system

there will be some sort of agent

one option:

  agent lock request

  do the get, either directly or through the agent

  do the accumulate, again through the agent or directly

  agent unlock request

option two:

   agent lock/start request, including some inefficient stuff

   do direct accesses directly that are efficient

   agent complete/unlock request

option three:

   single message that defines the entire access epoch, start to finish.

these cover the majority of the issues

side note:

  if we have a numa system in some cases it might be more efficient to 

  have the process local to the memory region pack data for a get into a

  contiguous region, then the remote process can grab that instead of 

  some set of discontiguous elements.  the same process could be used 

  for puts or accumulates.

if we want to pipeline things, then we need to have something between 

options two and three.  we want to be able to get overlap of computation

(of buffer packing) and communication of rdma options.

we can use the win info structure to help tune when we try to pipeline, when 

we wait to pack at end, and so on.

side note on lapi: 

  things like lapi have atomic counters which we might be able to use

  to avoid explicit unlock calls.  set to one when i'm done

  we might be able to use these same counters to perform locks, but that would

  be a nasty polling problem i think.

  likewise we can use the same lapi stuff to have agents set values local to

  the process performing operations in order to let it know that a set of

  operations that make up an epoch (which they have previously described to the

  agent) have been completed (and thus the process's unlock can complete)

note:

  there is more optimization that can occur here than what we have discussed so

  far; in particular nonoverlapping exclusive locks don't HAVE to be serialized

  like we have implied we would here.  we should think more about how we can

  allow these things to continue simultaneously.

----------

\section{passive target accumulate, shared lock}

you have an shared lock, you're doing a get on one set of things and

an accumulate on another set of things.

assume they are nonoverlapping datatypes.

mpi_win_lock(shared, rank, assert, win)

mpi_accumulate(B,...,sum)

mpi_win_unlock()

remember that you can call accumulate over and over, even to the same data

element.  and others can be calling accumulate to that element as well.

atomicity is maintained on the per-data-element basis only in the shared case.

brian's implementation idea:

- bust a window into a number of contiguous regions

- allow locks on each one of these regions separately

- in some cases there will be atomic operations supported by the processor, and

  in those cases we might be able to avoid the lock.

- always acquire locks in sequential order

problems with implementation:

- nasty strided datatypes which pass over the region and loop back would be 

  really slow.

  - for those you want to get all the locks ahead of time maybe - how do you

    detect?  maybe nonmonotonically increasing -> ``bad datatype''?

  - maybe cache incoming data and apply operations on elements in monotonically

    increasing order?

  - rather than this, maybe you reorganize both the source and destination 

    datatypes so that the elements arrive in monotonically increasing order?

    THIS IS A BETTER BUT SCARIER IDEA.

    - this is an interesting problem of applying identical transformations on

      the two separate data types

    - worst case this could be done by breaking out a datatype into a huge 

      struct; there should be a better/more efficient way.

    - caching transformed datatypes?

    - this could be done on portions of the datatypes as well to increase 

      the granularity of operations with respect to the locking

it sounds like we're going to want to define the mechanism for locking at

window create, or later if possible.

the number of processes within the group on which a window is created should

also be a factor when determining how to implement locking on the window.

another possibility is locking on datatypes instead -- then we need functions

which can look for overlaps between datatypes, which is kinda nasty...

we don't need single writer/mult. reader because writes to elements that are

being read is illegal.  likewise with put you don't have to lock, because it is

illegal for someone to write to the same location twice in the same epoch.

illegal operations will be detected by the bit code above.

so really it's only the accumulate that causes locking issues.

proposal:

start at random offsets into the target datatype when processing.  i (rob)

think that this is an interesting but problematic idea.  it's nondeterministic.

each guy has to get a random number.  the idea though is to try to space out operations on the target to get better lock utilization.

alternatively you could use the rank as a unique number.  divide the datatype

by N, where N = # of guys in the window object.  each guy uses his rank to

determine which block to start in.  there are all sorts of assumptions on the 

nature of the datatype here.

it will help with better utilizing locks on startup in some cases.

you have an shared lock, you're doing a get on one set of things and

an accumulate on another set of things.

back to the example

-------------------

assume they are nonoverlapping datatypes.

mpi_win_lock(shared, rank, assert, win)

mpi_accumulate(B,...,sum)

mpi_win_unlock()

process asks for shared lock (exposure epoch) on remote process

another example, looking at shmem combined with remote access

-------------------------------------------------------------

two pairs of processes on same nodes

shared memory lock on single node allows one process to look directly into the

window information so that he doesn't ahve to go through the agent of the other

process on the local node.  that same lock will be used by the communication

agent for a given process to ensure that things are kept sane in the off-node

case; in other words, this lock is utilized by processes on the same node

directly, but is also used by a single agent in the case of off-node access, in

both cases to coordinate access to the local window information.  by ``direct

access'' this may mean the process directly, or via that process's agent.

implication/question:

starting an exposure or access epoch will need support functions within the

methods.  this would possibly be used as an alternative to going through the

agent in order to have a fast path for these things.

idea for assertion (valid for shared or exclusive):

- NONOVERLAPPING

  says that i guarantee that none of the operations in the epoch will overlap.

  is this there already?  if we have this, we can avoid locking entirely,

  relying on the user to have done the right thing (tm) :).

post-wait/start-complete

------------------------

(target)                            (origin)

post(group, assert, win)            start(group, assert, win)

...                                 ...

wait(win)                           complete(win)

complete(win) - only ensures that all operations have been ``locally

completed''; they might not have yet completed at the target.

wait(win) - blocks on all complete()s, and completes all operations at the

target before returning.

start(group, assert, win) - can block until matching post(), but isn't required

to.

this is different from lock/unlock, which ensures that things are completed on

the target.

observation: there is an option passed via info on create that says no_locks;

there will be no passive target stuff.  great!

post(group, assert, win) - doesn't block.

note: all the groups here don't have to be identical; processes wanting to

perform operations on multiple windows will have the targets in their window,

while the ones that are targets will have all the sources in their groups...I

have explained this poorly...

if a post() only contains one member, it is equivalent to a win lock exclusive.

you can't have two outstanding post()s, as best we can tell, because you only

wait() on the window.  you could have different post()s on different windows...

so this approach is similar to the lock/unlock, only the post() doesn't HAVE

to finish the operations on the target (or wait for them to finish).

todo: we need to look at the overlapping window stuff and learn about the

private/public views...

approaches

----------

for little sets of messages, we can use a single message from the origin to

move all the operations across.

for large messages, we want to pipeline.

david: if we treat them like MPI messages, we could just do sends/receives as

necessary.  this keeps new concepts out of the CA code. otherwise we have this

``multiple operations in one message'' concept.

brian: people might find themselves doing the for loop of put()s instead of

using a datatype.  so aggregation makes sense in this case.

rob: those people are stupid and they should use datatypes.

anyway, we don't know what the intention is.  we should try to help people

if possible by using aggregation.

aggregation approaches:

- keep track of a size, and then cache to that size

  - david points out this will make little things slow.  he wants to be

    aggressive about performing operations locally in order to keep small 

    things fast

- keep a count?

- dynamic optimization?  watch patterns on a window and try to cache only

  when it seems like the right thing?

examples:

- for loop with little puts and computation between puts

- vs. for loop with little puts and no computation

in the first case you have the opportunity for making communication progress,

while in the second case you want to wait and aggregate.

i (rob) think we're going to want both an aggressive and a caching/combining

mode, because there are situations where one or the other are obviously

optimal.

brian: we need to be able to support this ^^^ in our interface in order to be

able to test and learn which of these modes really works.

david: there's not really much coordination here, so doing optimal ordering is

going to be tough.  BUT we do have the group on the target...but we'll never

have as much as we do in the fence case.

the accumulate is odd as usual.  if you're the only person in the target's

group, then you don't have to do the element-wise locking/atomicity (or

window-wise locking/unlocking depending on implementaiton).

brian: it would be helpful for the origin to know if he needs to lock or not

during accumulate operations.  this would allow him to know if he needs to lock

or not.  this is particularly useful in the shmem scenario.

- something in the window structure, stored in shared memory, could allow for

  this optimization

otherwise the accumulate is basically the same as in the lock/unlock window

op case (gets/puts, lock requests, etc.).

fence

-----

Q: does win_create() fill in for the first fence, or do you need a first fence?

A: you need the first fence (you have to in order to have created an exposure

   epoch).

there are optimizations here that we can get from the BSP people (collecting

and scheduling communication).

assertions:

no store - no local stores in previous epoch

no put - no remote updates to local window in new epoch

no precede- no local rma calls in previous epoch, collective assert only

no succeed - no local rma calls in new epoch, collective assert only

those last two are obviously useful for the first/last fence cases.  they are

one way to know you're done with fences.  you can also do local load/stores in

those epochs too...it's a way of saying ``i'm only doing local stuff for a

moment''.

Q: how does one cleanly switch between synchronization modes?  in particular

how does one switch cleanly OUT of the fence mode?  I think we're just not

reading the fence stuff carefully enough.

A: ``fence starts an exposure epoch IF followed by another fence call and the

local window is the target of RMA ops between fence calls''.  ``the call starts

an access epoch IF it is followed by another fence call and by RMA

communications calls issued between the two calls''.

HA!  that's nasty.  So hitting a fence really doesn't tell us as much as we

originally thought it did.  We need to figure out what we can do in the context

of these goofy rules.

bad example we think is legal

-----------------------------

(0)               (1)                 (2)                (3)

fence             fence               fence              fence

put(1)            put(0)              start(3)           post(2)

                                      put(3)             put(2)

                                      complete()         wait()

fence             fence               fence              fence

Is this legal?  The epochs are not created on 2 and 3, but not on 0 and 1 as

a result of the fences.  We know the fences are collective, but is the creation

of the epochs?

even worse example

------------------

(0)               (1)                 (2)                (3)

fence             fence               fence              fence

put(1)            put(0)              start(3)           post(2)

                                      put(3)             put(2)

                                      complete()         wait()

                                      barrier(2,3)       barrier(2,3)

                                      put(3)             put(2)

fence             fence               fence              fence

What about that one?

Bill: FIX THE TEXT! (meaning we should propose a clarification to the standard)

goals:

1) no mixed-mode stuff between fence and the others...

approach:

0) comb through chapter and see if something is already there.

1) description of problem (our examples, building up w/ 2)

2) we know this wasn't intended

3) propose clarifications

what next?

----------

david: looking this as a building-block sort of thing as we did with xfer.

is there a way to approach this in the same way?

the obvious blocks would be access and/or exposure epochs.

exposure epochs can be thought of as having a reference count, with the wait()

(or fence i guess) blocking until the refcount hits 0.

Q: do we, in our code, to explicitly define epochs?  Is it harder to follow the

rules with or without them?

scenarios:

- fence, how do you know who did ops/created epochs?

- which is the right approach?

- aggressive vs. combined?

we are probably going to punt on detecting errors between overlapping windows

at first.  later we could detect overlapping windows at create time and then do

error checking for invalid operations between windows on the destination at the

time the epochs are serviced (or whatever we call that)

brainstorm:

for non-aggregating case, a put creates a special car (including datatype etc.)

which sends a special header across to the target.  the target understands how

to receive these cars and will create a matching recv car to receive and store

the data appropriately (after creating the datatype if necessary...this is

still an unsolved problem).

an accumulate can be performed in the same manner, with a recv_mop being

created on the target instead of just a recv.

we can use the counter decrement capability we have created for use with cars

and requests in order to decrement counters in exposure epochs.  this will

allow for easy waits on epochs.

in the aggregating case, we would send a special header describing the

aggregated operations across to the target.  the target parses this header and

creates an appropriate car string.  the local side has already created the rest

of the cars necessary to perform the data transfer as well, relying on

completion dependencies on the local side to get the operations in the right

order.

we can serialize a datatype in a deterministic manner.

datatype caching is done on a demand basis.  we've talked about this before.

how does the need for retrieving a datatype fit into this special header scheme

laid out above?

For the heterogeneous case, the datatype definitions need to be expressed in

terms of element offsets, not bytes offsets.  For example, if a indexed type is

automatically converted and stored in terms of an hindexed type, the definition

sent to a remote process (with different type sizes) will contain incorrect

byte offsets for the remote machine.  We need to make sure to store the

original element displacement/offsets in the vector etc. cases where this is

how the datatype is originally defined, even if we use byte offsets locally.

With reactive caching, we cannot allow the datatypes sent to the target process

to be freed before the target has definitely completed operating with the

datatype.  In the lock/unlock and fence cases, the local process implicitly

knows that the target is done with the datatype when the unlock/fence returns.

This leaves us with the start/complete case as the only problem case.

This final case will be handled with a lazy ack based on access epochs in which

the datatype was used.  In other words, the reference count on a datatype is

incremented the first time the datatype is used by an RMA operation in an

access epoch and the datatype is "logged" in the access epoch structure.  The

access epoch structure also contains a flag stating whether a put or accumulate

operation was requested during this access epoch.  After Win_complete() detects

that all get operations have completed, if the flag is not set, it will

decrements the reference counts of the logged datatypes and free the access

epoch structure.  If the flag is set, the datatype reference counts may only be

decremented once an explicit ackowledgement has been received from the target

informing the origin that all operations requested by that access

epoch have been completed.

david proposes that rather than a single flag we would instead use a flag on

each datatype.  this would allow us to free the datatypes only used for gets

immediately, delaying only for the puts/accs.

it's reasonable for the origin to force the send of the datatype when he knows

that the target hasn't seen it yet.  we should consider this.

we don't have to send basic types.  that's important to remember too.

oops!  the fence isn't as well-behaved as we thought.  fence only implies local

completion of the last epoch.  so we're going to have to keep up with things

for fence as well.

oops!  the lock/unlock isn't either :).  the public copy on the other side is

assured to have been "updated", but that doesn't mean that you are necessarily

done with the datatype.

we could do lazy release consistency a la treadmarks, and it would give us

performance advantages in some situations, but we aren't going to do that.

we plan to have a single copy of our data.  thus our lock/unlock case will be

ok, as there is no public/private copy issue.

the fence will be implemented in a similar manner to a complete/wait on the

previous epochs (access, exposure).  we have to ensure that we don't

inadvertently create epochs that are empty.

brian's notes mention using a counter per target in order which is exchanged at

each fence.  this tells the target how many operations need to be completed

before leaving the fence.  this works well in the eager case, but is probably

overkill for the aggregated case, where you're going to pass all the operations

over anyway.  this can also be done with N reductions; we might be able to work

out an all-to-all reduce that does the right thing for this.

there are a couple of asserts which will be useful for reducing communication

here.  and we can do a little extra debugging checking based on these as well.

we know we can leave the fence when we have completed the total number of

operations counted in the reduction operation.

aside: we could use mprotect() to detect local load/stores on a local window if

we wanted to for debugging purposes.

scenario: start/complete (sort of)

----------------------------------

we can get a context id from dup'ing the communicator at create time, or we can

get a new context id based on the old communicator. generate_new_context_id()

or something like that.  everyone participating in the win create must agree on

the context_id.

start must create an access epoch which can be matched to an exposure epoch on

the other side.  we don't think we need to match anything special at start/post

time in order to match epochs, but we aren't sure.

our context ids can be used to match the AE to the appropriate window on the

target.

targets are going to have to track pending AEs until they hit a point where a

post (or whatever) has occurred.  there will be situations where multiple AEs

are queued for a single window, and we must handle this as well.  all tracking

is associated with a local window.

access epochs are just created on the fly by the target as placeholders for

what is going on.  there doesn't have to be anything special about how these

are identified.  some time prior to the origin locally completing an AE, an

origin-assigned ID is passed to the target.  this ID is returned to the origin

by the target when the AE has been completed on the target side.

puts/gets/accs don't have to have an origin-assigned id or be matched with more

than the context id and origin, under the assumption that there are no

overtaking messages and only one active AE from an origin at one time.

there is no valid case where one origin has more than one outstanding and

active AE for the same target window.

------------------------------------------------------------------------

RMA requirements

- we need the option of aggregating operations within an epoch

Window object

- states

  - local

  - public

- exposure epoch tracking (for operation on the local window)

  - need a queue for ordering exposure epochs and ensuring proper

    shared/exclusive semantics for passive target case

  - each epoch needs a queue for storing incoming operation requests associated

    with the exposure epoch

- access epoch tracking (per local window?)