
nonblocking version re-do:

allocate request array at creation. 3*numProcs
set all requests to MPI_REQUEST_NULL
deallocate in destroy.

for each proc from whom I will receive data in this phase:
  post recv for data from source
  post recv for indices from source
  post "signal" send to source
for each proc to whom I will send data in this phase:
  receive "signal" send from target
  send data to target
  set indices to target
waitall on all requests. (requestCount)



-----


parkBred: pinar-hendrickson parking algorithm

how to fix problem of no free blocks?
Check when redistribute is called if total free is 0.
(collective)
If that's the case, every process allocates one spare block.
Copies one of its blocks (assuming there is at least one?) to the spare
space, frees (declares dead) the space.
Carry out the whole redistribution as before.
It should complete now.
At the end, each process needs to ....

how about skip test 2 for now.
-----------------------




there is one process expecting a block (it could be root).
Root needs to send, this other process needs to receive.


Data structures: used in both parking and moving acts of phase

int outgoing[nprocs]: number of blocks I have destined for proc i.
int incoming[nprocs]: the number of blocks proc i has to send to me.
int totalOutgoing: sum of outgoing
int totalIncoming: sum of incoming (k)
int numDead: number of free spaces (m)
int parkDelta:
int recvCounts[nprocs]: number of blocks to receive from i in this act
int sendCounts[nprocs]: number of blocks to send to i in this act
int recvDisplacements[nprocs]: partial sum of recvCount----
int parkRecvCounts[nprocs]
int parkSendCounts[nprocs]

Pair incomingAddresses[numBlocks]:
   destination addresses of the incoming blocks
   organized by recvDisplacements
Pair outgoingAddresses[numBlocks]:
   destination addresses of the outgoing blocks
   organized by sendDisplacements

Additional Root Data structures:

parkDeltas[nprocs]: park delta for each proc


Algorithm:
  while (true) {
    sortAndUpdate();
    MPI_Allreduce (AND) done in place.
    if (done) break;
    computeDirectMoves();
    computeParkingMoves();
    executePhase();
  }


Note:

sortAndUpdate sets totalOutgoing, totalIncoming, and numDead
to correct figures.

computeDirectMoves will set sendCount[] and recvCount[] on each proc.
Let s=sum of sendCount[] and r=sum of recvCount[].  So s is the number
of blocks that will be sent from this proc directly to destination
in this phase.  r is the number of blocks that will be received by
this proc as final destination in this phase.

computeParkingMoves works as follows.  if totalIncoming-numDead<0 then
I have free parking spaces now; set parkDelta=totalIncoming-numDead.

Else if totalIncoming-numDead-s>0 then I have data to park.

Where do I get this figure?   I have data to park, if at the end of this
phase, I will have more totalIncoming then numDead.  Let us use primes (')
to denote values after this phase.

totalIncoming' = totalIncoming-r
numDead' = numDead-r+s
totalIncoming'-numDead'= totalIncoming-numDead-s.

So let d=totalIncoming-numDead.

parkDelta = { d,   if d<0          (I have parking spaces)
              d-s, if d>s          (I have d-s data to park)
              0,   otherwise }     (I'm going to finish in next phase
                                    but have no spare space and no need
                                    to park.)


ddddddddddddddd000000000~~~~d-s~~~~~~~
---------------000000000++++++++++++++

Now the parkDelta is gathered on root and returns parkRecv vector,
which is transposed to yield parkSend vector.  These are added to
sendCounts and recvCounts.

executePhase: prepares recvDisplacements, executes alltoall on data, preares
addresses, executes alltoall, updates block manager.











Note: after move completes, if a proc still has more incoming, then it
has 0 free space.  (Move as much as possible in each phase.)  Conversely,
if a proc has positive free space, it has no more incoming.   So a proc
with 0 free space cannot receive parking blocks, but may send them.  A
proc with + free space cannot send parking blocks, but can receive them.

sortAndUpdate():
  sorts, updates outgoing[], incoming[], totalIncoming, totalOutgoing, numDead.
  preconditions: none.
you know where each block has to go (proc,index).
so you know how many blocks you need to send to each proc.
  updates outgoing[] using bman
  updates totalOutgoing
do a collective and you know how many blocks to receive from each proc.
  updates incoming[]
sum to get total num blocks you need to receive: k
  updates totalIncoming
you know how many free spaces you have: m
  update numDead using MADRE_BMAN_getDeadCount()


exchangeBlocks():
  preconditions: 
    1. bman is sorted.
    2. recvCount[] and sendCount[] have been filled in with the
       number of blocks to send and/or recv to/from each proc;
    3. outgoingAddresses[] have been filled in with final destinations
       of outgoing blocks.
  fills in recvDisplacements/sendDisplacements;
  Alltoalls to exchange blocks, receiving into dead zone.
  Alltoalls to send outgoingAddresses[] and receive incomingAddresses[]
  Tells bman to set sent blocks to dead and fills in final addresses of 
    received blocks.

Move:
  preconditions: sortedAndUpdate just called.
  fill in recvCount[] using hueristic;
  Alltoall fills in sendCount[];
  set outgoingAddresses from bman;

Park:
  preconditions: move, sortAndUpdate just called.
if m=0 may have stuff to park (if k-m=k>0)
if m>0 then k=0 so k-m=-m (parking spaces available). Why?


????????????

If k-m>0 you have data to park on another proc
If k-m<0 you can receive parking data from another proc
  parkDelta = totalIncoming - numDead;
  MPI_Gather to root: parkDelta.  Root gathers into parkDeltas[].
  root:
  for (i=0; i<nprocs; i++) {
    rank:     0.......6 7 8 ...
    deltas: -10 ...  3 6 7 ...
    Send to 0: vector of length nprocs, how many to park/recv from each proc:
    send:     0 ....  3 6 1 .....
    deltas:   0 ....  0 0 6 .....
    Send to 1: vector of length nprocs...
  }
  root can use sendCount[] as temp. sendbuffer.
  non-root: receive into recvCount[].
...In the end, if there are any positive numbers left in this array,
then there will be no more negative numbers left.  (If some have data to
park, then all parking spaces will be used.)

Now do an AllToAll transpose to find out how many to park/send to each
proc.  receive into sendCount[]

If you are a park/sender: you know how many blocks to park/send to
each proc.  If you are to park p blocks on proc j then you know that
you cannot have any blocks destined for j, but you must have at least
p outgoing blocks.  Choose any p of those outgoing blocks and send
them to j.  So store the destination ranks/indices into
outgoingAddresses.  Reset the bman->destinationRanks to the parking
receivers and sort.  recvCounts[] should be zeroed out.

If you are a park/recvr: you know how many blocks to park/recv from
each proc.   Alltoall receive them into dead zone.  Then alltoall receive
into incomingAddresses, tell bman the new addresses for the blocks.
sendCounts[] should be zeroed out.

exchangeBlocks();
