
Need to make breds that don't create "schedule" first because the schedule
takes up memory.

2 possibilities:  regular phase bred until deadlock, then switch to 
cyclicScheduling.   Note once bred becomes deadlocked, ever node with
incoming has 0 deads.  After executing a cycle, this situation is
unchanged.  Hence switching permanently to cyclic is inevitable.

second posssibility is to do cyclic scheduling throughout.


---

would like to design schedule general enough to be used for parking,
cyclic, phase.

type=RECV, source=5, numBlocks=20, finalDest=6, origin=3

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


sfsiegel, Feb 23, 2008:
Here are some changes made on BGL that  never go checked in:

sfsiegel@login2:~/siegel/development/madre/src/cyclicSchedulerBred> cvs diff
siegel@laser-cvs.cs.umass.edu's password: 
? hold-cyclicSchedulerBred.c
cvs diff: Diffing .
Index: Makefile
===================================================================
RCS file: /laser/cvsroot/siegel/development/madre/src/cyclicSchedulerBred/Makefile,v
retrieving revision 1.7
diff -r1.7 Makefile
4c4
< COMPILE = $(COMPILER) -c -I$(INC_DIR)
---
> COMPILE = $(COMPILER) -c -I$(INC_DIR) -DDEBUG=0
Index: cyclicSchedulerBred.c
===================================================================
RCS file: /laser/cvsroot/siegel/development/madre/src/cyclicSchedulerBred/cyclicSchedulerBred.c,v
retrieving revision 1.11
diff -r1.11 cyclicSchedulerBred.c
2254a2255,2256
>   float time0, time1, time2;
>   MADRE_CSCB_Object bred = (MADRE_CSCB_Object)madre->bred;
2263a2266,2267
>   MPI_Barrier(madre->comm);
>   time0 = MPI_Wtime();
2264a2269,2270
>   MPI_Barrier(madre->comm);
>   time1 = MPI_Wtime();
2273a2280,2281
>   MPI_Barrier(madre->comm);
>   time2 = MPI_Wtime();
2275a2284,2288
>   if (madre->myRank == bred->root) {
>     printf("  schedule construction time   : %f\n", time1-time0);
>     printf("  schedule execution time      : %f\n", time2-time1);
>     fflush(stdout);
>   }
sfsiegel@login2:~/siegel/development/madre/src/cyclicSchedulerBred> 


--

sfsiegel@login2:~/siegel/development/madre/src/unitBred> cvs diff
siegel@laser-cvs.cs.umass.edu's password: 
cvs diff: Diffing .
Index: Makefile
===================================================================
RCS file: /laser/cvsroot/siegel/development/madre/src/unitBred/Makefile,v
retrieving revision 1.4
diff -r1.4 Makefile
4c4
< COMPILE = $(COMPILER) -c -I$(INC_DIR)
---
> COMPILE = $(COMPILER) -c -I$(INC_DIR) -DSTACK
sfsiegel@login2:~/siegel/development/madre/src/unitBred> 


--


cvs diff: Diffing exp1
Index: exp1/Makefile
===================================================================
RCS file: /laser/cvsroot/siegel/development/madre/experiments/exp1/Makefile,v
retrieving revision 1.10
diff -r1.10 Makefile
21,23c21,24
< 	$(SHORT_RUN) 32 ./exp1 unitBred 25000 20000 16000 1 20 20 40
< 	$(SHORT_RUN) 32 ./exp1 unitBred 25000 20000 16000 1 40 40 80
< 	$(SHORT_RUN) 32 ./exp1 unitBred 25000 20000 16000 1 100 100 200
---
> 	$(LONG_RUN) 512 ./exp1 unitBred 25000 20000 16000 1 100 100 200
> 
> run_phaseBred: exp1
> 	$(SHORT_RUN) 32 ./exp1 phaseBred 25000 20000 16000 1
33a35,40
> run_unitCyclicBred: exp1
> 	$(SHORT_RUN) 32 ./exp1 unitCyclicBred 25000 20000 16000 1 5 5 5
> 
> run_unitCyclicReadyBred: exp1
> 	$(SHORT_RUN) 32 ./exp1 unitCyclicReadyBred 25000 20000 16000 1 3 5 5
> 
47c54
< 	$(LONG_RUN) 32 ./exp1 cycleShiftBred 25000 20000 16000 1
---
> 	$(LONG_RUN) 128 ./exp1 cycleShiftBred 25000 20000 16000 1
50c57
< 	$(LONG_RUN) 32 ./exp1 cyclicSchedulerBred 25000 20000 16000 1
---
> 	$(SHORT_RUN) 32 ./exp1 cyclicSchedulerBred 25000 20000 16000 1
53c60
< 	$(SHORT_RUN) 2 ./exp1 cyclicSchedulerBred 25000 20000 16000 1
---
> 	$(SHORT_RUN) 4 ./exp1 cyclicSchedulerBred 25000 20000 16000 1
58a66,68
> 
> 
> run_more: exp1
Index: exp1/exp1.c
===================================================================
RCS file: /laser/cvsroot/siegel/development/madre/experiments/exp1/exp1.c,v
retrieving revision 1.6
diff -r1.6 exp1.c
115a116,136
>   } else if (strcmp(bredName, "unitCyclicReadyBred") == 0) {
>     if (numOptions > 0) {
>       int requestLimit, edgeBufferSize, actionBufferSize;
> 
>       assert(numOptions == 3);
>       sscanf(options[0], "%d", &requestLimit);
>       sscanf(options[1], "%d", &edgeBufferSize);
>       sscanf(options[2], "%d", &actionBufferSize);
>       MADRE_UCRB_setRequestLimit(madre, requestLimit);
>       MADRE_UCRB_setEdgeBufferSize(madre, edgeBufferSize);
>       MADRE_UCRB_setActionBufferSize(madre, actionBufferSize);
>     }
>     if (myRank == 0) {
>       fprintf(stream, "  requestLimit = %d\n",
> 	      MADRE_UCRB_getRequestLimit(madre));
>       fprintf(stream, "  edgeBufferSize = %d\n",
> 	      MADRE_UCRB_getEdgeBufferSize(madre));
>       fprintf(stream, "  actionBufferSize = %d\n",
> 	      MADRE_UCRB_getActionBufferSize(madre));
>       fflush(stream);
>     }
cvs diff: Diffing exp2
Index: exp2/Makefile
===================================================================
RCS file: /laser/cvsroot/siegel/development/madre/experiments/exp2/Makefile,v
retrieving revision 1.2
diff -r1.2 Makefile
23a24,29
> exp2d: exp2d.o
> 	$(LINKER) -o exp2d exp2d.o $(LIBRARIES)
> 
> exp2d.o: exp2d.c
> 	$(COMPILE) exp2d.c
> 
38a45,47
> run6: exp2d
> 	$(SHORT_RUN) 4 ./exp2d
> 
41c50
< 	rm -f *.o exp2 exp2b *~
---
> 	rm -f *.o exp2 exp2b exp2c exp2d
sfsiegel@login2:~/siegel/development/madre/experiments> 


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


sfsiegel, Jan 18, 2006:
Ideas on classification of algorithms:

contiguous vs. noncontiguous: a contiguous redistribution algorithm
requires that the blocks occupy contiguous positions in memory.  Hence
there is one big contiguous piece of memory divided into blocks.  A
noncontiguous algorithm does not make this requirement; each block may
reside anywhere in memory.  Of course, they may be contiguous, so a
noncontiguous algorithm is strictly more general than a contiguous
one---it may be applied to a contiguous problem, but may not run as
quickly.  A contiguous algorithm can take advantage of contiguity by
incorporating several blocks into a single message; in a noncontiguous
algorithm, each message consists of precisely one block.

symmetric vs root: A root algorithm requires that one process play a
special role, for example, by collecting and collating information
about the map from all the other processes and then disseminating this
information back to the other processes.  In a symmetric algorithm
each process plays a symmetric role (they are indistinguishable,
except perhaps for trivial things such as printing output).   In a root
algorithm, the root process may have to use a lot more memory than
the other processes.  If this is a significant amount of memory,
then the root process may not have room for all the data plus the extra
memory required by the algorithm.  Hence a root algorithm may be most
useful for an application in which one process can be reserved for this
sort of thing and not be used for storing data.




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



To do:

 - replace certain assertions with a better error-reporting mechanism.

Consider the requirement that all BREDs should report an error if:

   1. destRanks[i] or destIndices[i] is out of range for some i
   2. the map is not injective
   3. the map is not feasible, i.e., there is insufficient dead
      space on some proc (numDeads < numIncoming - numOutgoing)
   4. there is insufficient memory to carry out a redistribution
      (i.e., MADRE_malloc fails)
   5. an MPI call fails (i.e., returns non-zero value)

To be really careful, we might also check that the values passed to
MADRE_create (e.g.) are consistent, e.g., same datatype.

We could have a "safe" or "debugging" mode in which these checks are
performed.  Then they could be turned off for production runs.  (Just
as assertions can be turned off with the flag -DNDEBUG=1).


  - move more stuff from *.h to *.c.  Keep only stuff necessary for 
    compiling in *.h.


  - add statistics tracking capabilities to the MADRE object.  Keep
  track of amount of memory currently allocated (by MADRE_malloc), the
  maximum amount that was allocated.  Keep additional information
  specific to individual BREDs, such as number of cycles, number of
  shifts, average length of factor, total number of blocks moved,....
  Perhaps this could also be turned on or off by a flag.

To keep track of the memory we would have to add a MADRE_free like
MADRE_malloc.  Somehow there would have to be hashtable or similar
structure mapping the pointers returned by MADRE_malloc to the number
of bytes allocated. (Why can't we get this from the system itself?)


  - the unit BRED handles the requests inefficiently by deleting a
  request and shifting all remaining requests.  Find a better way.


  - do more dynamic memory allocation instead of the current static
    allocation, esp. when no tight upper bounds are known.


  - rename all the functions with unique names so they can all be
  incorporated into a single library (.a).  The user should specify
  the ID of the bred s/he wants to use in MADRE_create.  


  - add a lot more use cases to the test suite


  - add a "non-contiguous" (or really "not necessarily contiguous")
  variant to MADRE_create.  For these, an array of pointers to
  the blocks will be given, instead of a single pointer to the
  beginning of the data array.   Call it MADRE_create_nc.  Not
  every BRED will support this option.  


  - there is a lot of shared code between BREDs, such as many of the
  set and get methods, much of the create stuff, etc.  This can be
  factored out into a single file and included in compilation.


  - create some more simple exmaples of applications using MADRE


  - consider modifying the interface so that the creation process
  goes in several stages.  First MADRE_create(...) is called as we do
  now. Then, user-specified parameters can be set...perhaps by a
  function such as MADRE_setParameter(madre, "requestBound", 500).
  Then a function MADRE_initialize(madre) is called.  Now the madre
  can be used (repeatedly) for redistribution.  The parameters can be
  changed and then MADRE_initialize called again between calls to 
  redistribute.  An error can be thrown if the parameter name is
  invalid for the particular BRED in use. 


  - create a User's Manual


----

Better idea for Memory stats:

replace free(void* pointer) with MADRE_free(void* pointer, int numBytes)
to keep track of current number of malloced bytes.


----

Ideas for Memory stats:


Have functions
  
void* MADRE_malloc(int numBytes);
void MADRE_free(void* pointer);
void MADRE_computeMemStats();

and global variables


typedef struct MADRE_MemNodeStruct {

  void* pointer;

  int numBytes;

  struct MADRE_intListStruct *next;

  struct MADRE_intListStruct *prev;
} MADRE_MemNode;


typedef struct MADRE_MemMonitorStruct {

  /* monitor the memory used by MemMonitor? */

  /* current number of bytes allocated on this proc*/
  long currentMem;

  /* the maximum value taken on my currentMem on this proc*/
  long peakMem;

  /* maximum value taken on by size on this proc */
  long peakSize;

  /* The max, over all i, of peachChainLengths[i]. */
  int maxPeakChainLength;

  /* sum over all procs of peakMem */
  long peakMemSum;

  /* max over all procs of peakMem */
  long peakMemMax;

  /* average over all procs of peakMem */
  double peakMemMean;

  /* table[length]: hashtable mapping pointers to numBytes.
   * table[i] is a pointer to a linked list of MADRE_MemNodes, each of which
   * corresponds to one entry in the table.  This linked list
   * ordered by pointer (is that possible?) */
  MADRE_MemNode** table;

  /* peakChainLength[length]. [i]:the maximum length achieved by
   * the list table[i]. */
  int* peakChainLengths;

  /*  Length of table. Constant */
  int length;

  /* current number of entries in table, i.e. the number of live
   * memory allocations */
  int size;
  
} MADRE_MemMonitor;

MADRE_MemMonitor MADRE_memMonitor;

/* The hash function.  Given a pointer,
 * this returns an int in [0,length-1]. */
int MADRE_memHash(void* pointer);

/* Place entry in table */
void MADRE_memPut(void* pointer, int numBytes);

/* Return -1 if pointer is not in table, else
 * return numBytes for that pointer. */
int MADRE_memGet(void* pointer);

/* Return -1 if pointer is not in table, else
 * reutrn numBytes for that pointer, and remove
 * pointer from table. */
int MADRE_memRemove(void* pointer);

void* MADRE_malloc(int numBytes) {
  numBytes = MADRE_MAX(numBytes, 1);
  p = malloc(numBytes);
  assert(p);
  MADRE_memPut(p, numBytes);

}


void MADRE_free(void* pointer) {
  int result = MADRE_memRemove(pointer);
  assert(result > 0);
}


MADRE_init() {
 /* set up memory monitor */


}


MADRE_finalize() {


}


These last 3 values are computed by calling MADRE_computeMemStats (a
collective operation).

MADRE_malloc and MADRE_free keep track of all memory allocated/freed
by MADRE.  A hashtable will be used to map pointers to the number of
bytes allocated.  This will also be useful in debugging, to detect
memory leaks, to make sure all memory allocated is eventually freed,
etc.

For performance runs when you don't want to keep track of these stats,
a compiler directive can be used to redefine MADRE_malloc to malloc
and MADRE_free to free.


----

Other ideas for block redistributors:


1. A very memory-efficient approach: assuming you have both the map f
and its inverse f^{-1} on every proc, proceed as follows.  You will go
through approx log_2(n) stages, where n = numProcs.  In stage i, you
will learn f^m (f composed with itself m times) and f^{-m}, where
m=2^i.  You can do this because you already know g=f^{m(i-1)} and
h=f^{-m(i-1)}, so now you look at where each block goes to under g
and send that information to the relevant procs using h.

Now, for each block, you keep a little data structure which is updated
at each stage:

  type:  cycle/shift/don't know
  certainty: yes/no
  cycle info:
      lead proc:  rank of proc of least index involved in this cycle
      lead index: least index of block on lead proc involved in this cycle
      segment ID: which segment I am in this cycle, counting lead as 0
  shift info:
      lead proc: rank of proc on which shift begins
      lead index: index of block beginning the shift
      segment ID: which segment I am in this shift

Now these are updated using the information received from the new maps.
This is sort of like a min/max update.  

After completion, everyone knows their schedule to perform a
cycle-shift style redistribution.


