
Data structures required for all procs:


Can the non-root proc figure out when the root needs more edges?

   What the root sends the procs (after init):

   - an array of Actions: the number of actions can be retrieved from the
   status returned by examining status.length.  If this number is
   0, that is interpreted as a request from the root to send another
   edgeChunkSize edges.   Alternatively: probe message and look at tag?

   Non-root code outline:

Schedule Construction:

   create and init block manager;
   numOutgoingBlocks = sum using destRanks;
   MPI_Alltoall(); // get numIncomingBlocksFrom[i]
   numIncomingBlocks = sum of above;
   MPI_Alltoallv(); // get destIndices[j];
   init numBlocksRecvdFrom[]  = 0;
   create the entire list of outgoing edges;
   edgeCount = 0;
   actionCount = 0;
   numRequests = 0;
   inBlockCount = 0;
   outBlockCount = 0;

   nonroot: 

   MPI_ISend(edges, edgeBufferSize, requests[numRequests], to root, ...);
   numRequests++;
   while (inBlockCount < numIncomingBlocks ||
          outBlockCount < numOutgoingBlocks) {
     MPI_Recv(actionBuffer+actionCount, maxActionBlock, from root, ...);
     numActionsRecvd = status...;
     numEdgesRequested = tag...;
     if (numEdgesRequested > 0) {
       MPI_ISend(edgeBuffer+edgeCount, numEdgesRequested, requests[numRequests],
                 to root, ...);
       numRequests++;
       edgeCount += numEdgesRequested;
     }
     actionCount += numActionsRecvd;
     process_actions();
     if (action->sender >= 0) {
       inBlockCount += quantity;
     } 
     if (action->receiver >= 0) {
       outBlockcount += quantity;
     }
   }
   assert(edgeCount == numEdges);
   MPI_Waitall(on the edges sent to root); // these should be done
  

Schedule Execution:

   // all procs: execute schedule
   sortBlocks;
   for (i = 0; i < actionCount; i++) {
   // hypothesis: block should be arranged as follows: for each i,
   // starting at position sortVector[i] and proceeding for procCount[i]
   // blocks, are blocks destined for proc i.  Starting at position
   // procCount[numProcs] and proceeding for deadCount all blocks are dead.
   // However will be incrementing sortVector there may be "gaps"...
   // X is either dead or recvd from other proc
   // X X ... X L L ... L
     determine if send, recv, or sendrecvreplace, as the case may be;
     if (send x blocks to proc i) {
       assert(x <= procCount[i]);
       assert(numRequests < numBlocks - 1);
       post send(data+sortVector[i], x, to i, requests+numRequests,...);
       declare deadRange(sortVector[i], sortVector[i]+x-1);
       sortVector[i] += x;
       numRequests++;
     }
     else if (receive x blocks from proc i) {
       assert(x <= numBlocks - sortVector[numProcs]);
       if (not enough contiguous dead space to receive) {
         MPI_Waitall (on all outstanding sends and recvs);
         sort();
	 numSentSinceLastSort[] = 0;
       }
       post recvs into dead zone();
       update destRanks, destIndices();
       numRecvdFrom[i] +=;
     }
     else { // sendrecvreplace
       MPI_Sendrecvreplace(data+sortVector[i]+numSentSinceLastSort[i],...);
       update destRanks, destIndices();
       numSentSinceLastSort[i]++;
     }
     update destRanks, destIndices;
   }
   MPI_Waitall (on all outstanding sends and recvs);
   positionBlocks();

     
.
.
.
send-recv?
  execute a Sendrecv_replace of short msgs in opposite direction
    use a special tag for this? CYCLE_TAG
  execute the MPI_Sendrecv_replace
consolidate?
  while (numNotifications > 0) {
    waitany(w_i)
    if tag == notifyTag:
      get quantity (the message), source
      w_i: post big Irsend of quantity blocks to source using DATA_TAG
      numNotifications--;
  }
  wait all requests
  numRequests = 0;
  sort
send to proc p_i?
  w_i: post short recv for proc p_i (waiting for the "ready" message)
       using NOTIFY_TAG
  numNotifications++;
  numRequests++;
recv from proc p_i?
  v_j: post big recv for p_i using TAG (DATA_TAG)
  numRequests++;
  send short msg to p_i (the "ready" message) using NOTIFY_TAG
