Refactoring control point and critical path detection code.
authorIsaac Dooley <idooley2@illinois.edu>
Thu, 28 May 2009 18:19:34 +0000 (18:19 +0000)
committerIsaac Dooley <idooley2@illinois.edu>
Thu, 28 May 2009 18:19:34 +0000 (18:19 +0000)
src/ck-cp/arrayRedistributor.C [new file with mode: 0644]
src/ck-cp/arrayRedistributor.h [new file with mode: 0644]
src/ck-cp/controlPoints.C
src/ck-cp/controlPoints.ci
src/ck-cp/controlPoints.h
src/ck-cp/pathHistory.C [new file with mode: 0644]
src/ck-cp/pathHistory.h [new file with mode: 0644]

diff --git a/src/ck-cp/arrayRedistributor.C b/src/ck-cp/arrayRedistributor.C
new file mode 100644 (file)
index 0000000..3813f03
--- /dev/null
@@ -0,0 +1,86 @@
+#include <charm++.h>
+#include <cmath>
+#include <math.h>
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <sstream>
+#include <map>
+#include <set>
+#include <vector>
+#include <utility>
+#include <limits>
+//#include <sys/time.h>
+#include <float.h>
+
+#include "ControlPoints.decl.h"
+#include "trace-controlPoints.h"
+#include "LBDatabase.h"
+#include "controlPoints.h"
+#include "pathHistory.h"
+#include "arrayRedistributor.h"
+
+
+/**
+ *  \addtogroup ControlPointFramework
+ *   @{
+ *
+ */
+
+
+using namespace std;
+
+
+
+/// The index in the global array for my top row  
+int redistributor2D::top_data_idx(){ 
+  return (data_height * thisIndex.y) / y_chares; 
+} 
+int redistributor2D::bottom_data_idx(){ 
+  return ((data_height * (thisIndex.y+1)) / y_chares) - 1; 
+} 
+int redistributor2D::left_data_idx(){ 
+  return (data_width * thisIndex.x) / x_chares; 
+} 
+int redistributor2D::right_data_idx(){ 
+  return ((data_width * (thisIndex.x+1)) / x_chares) - 1; 
+} 
+int redistributor2D::top_neighbor(){ 
+  return (thisIndex.y + y_chares - 1) % y_chares; 
+}  
+   
+int redistributor2D::bottom_neighbor(){ 
+  return (thisIndex.y + 1) % y_chares; 
+} 
+   
+int redistributor2D::left_neighbor(){ 
+  return (thisIndex.x + x_chares - 1) % x_chares; 
+} 
+int redistributor2D::right_neighbor(){ 
+  return (thisIndex.x + 1) % x_chares; 
+} 
+  
+  
+/// the width of the non-ghost part of the local partition 
+int redistributor2D::mywidth(){ 
+  return right_data_idx() - left_data_idx() + 1; 
+} 
+   
+   
+/// the height of the non-ghost part of the local partition 
+int redistributor2D::myheight(){ 
+  return bottom_data_idx() - top_data_idx() + 1; 
+} 
+
+
+
+
+
+
+/*! @} */
+
diff --git a/src/ck-cp/arrayRedistributor.h b/src/ck-cp/arrayRedistributor.h
new file mode 100644 (file)
index 0000000..86d9e8e
--- /dev/null
@@ -0,0 +1,628 @@
+/** 
+
+    A system for exposing application and runtime "control points" 
+    to the dynamic optimization framework.
+
+*/
+#ifndef __ARRAYREDISTRIBUTOR_H__
+#define __ARRAYREDISTRIBUTOR_H__
+
+#include <vector>
+#include <map>
+#include <cmath>
+#include "ControlPoints.decl.h"
+
+#include<pup_stl.h>
+
+
+
+/**
+ * \addtogroup ControlPointFramework
+ *   @{
+ */
+
+
+/// A message containing a chunk of a data array used when redistributing to a different set of active chares 
+class redistributor2DMsg : public CMessage_redistributor2DMsg { 
+ public: 
+  int top;         
+  int left; 
+  int height;      
+  int width; 
+  int new_chare_cols; 
+  int  new_chare_rows; 
+  int which_array; 
+  double *data;
+}; 
+
+
+/// Integer Maximum
+static int maxi(int a, int b){
+  if(a>b)
+    return a;
+  else
+    return b;
+}
+
+/// Integer Minimum
+static int mini(int a, int b){
+  if(a<b)
+    return a;
+  else
+    return b;
+}
+
+
+/// A chare group that can redistribute user data arrays. It is used by binding it to a user's Chare Array
+class redistributor2D: public CBase_redistributor2D {
+ public:
+
+  std::map<int,double*> data_arrays;
+  std::map<int,int> data_arrays_sizes;
+
+  /// The array associated with this data redistribution
+  CProxyElement_ArrayElement associatedArray;
+  
+  int incoming_count;
+  std::map<int,double*> data_arrays_incoming;
+  std::map<int,int> data_arrays_incoming_sizes;
+
+  /// Is this array element active
+  bool thisElemActive;
+
+ private:
+
+
+  void *fakeMemoryUsage;
+
+
+  CkCallback dataRedistributedCallback;
+
+  int x_chares; // number of active chares in x dimension
+  int y_chares; // number of active chares in y dimension
+
+  int data_width;  // The width of the global array, not the local piece
+  int data_height; // The height of the global array, not the local piece
+
+  int data_x_ghost; // The padding in the x dimension on each side of the data
+  int data_y_ghost; // The padding in the y dimension on each side of the data
+
+
+ public:
+
+  void pup(PUP::er &p) {
+    CBase_redistributor2D::pup(p);
+
+    p | data_arrays_sizes;
+    p | data_arrays_incoming_sizes;
+    p | incoming_count;
+    p | associatedArray;
+    p | thisElemActive;
+
+    p | dataRedistributedCallback;
+
+    p | x_chares;
+    p | y_chares;
+    p | data_width;
+    p | data_height;
+    p | data_x_ghost;
+    p | data_y_ghost;
+
+    if(p.isPacking() && fakeMemoryUsage!=NULL)
+      free(fakeMemoryUsage);
+
+    fakeMemoryUsage = NULL;
+
+    ////////////////////////////////
+    // when packing, iterate through data_arrays
+    // when unpacking
+
+    {
+      std::map<int,int>::iterator iter;
+      for(iter = data_arrays_sizes.begin(); iter != data_arrays_sizes.end(); iter++){
+       int whichArray = iter->first;
+       int arraySize = iter->second;
+
+       //      CkPrintf("Pupping data array %d\n",whichArray);
+       p | whichArray;
+
+       if(p.isUnpacking())
+         data_arrays[whichArray] = new double[arraySize];
+
+       PUParray(p,data_arrays[whichArray] ,arraySize);
+       
+       if(p.isPacking())
+         delete[] data_arrays[whichArray];
+       
+      }
+    }
+
+
+    ///////////////////////////////
+    {
+      std::map<int,int>::iterator iter;
+      for(iter = data_arrays_incoming_sizes.begin(); iter != data_arrays_incoming_sizes.end(); iter++){
+       int whichArray = iter->first;
+       int arraySize = iter->second;
+
+       //      CkPrintf("Pupping incoming array %d\n",whichArray);
+       p | whichArray;
+
+       if(p.isUnpacking() && data_arrays_incoming_sizes[whichArray] > 0)
+         data_arrays_incoming[whichArray] = new double[arraySize];
+       
+       PUParray(p,data_arrays_incoming[whichArray],arraySize);
+       
+       if(p.isPacking())
+         delete[] data_arrays_incoming[whichArray];
+       
+      }
+    }
+
+    //    CkPrintf("pup redistributor2D\n");
+
+  } 
+
+
+  void ckJustMigrated(){
+    //   CkPrintf("redistributor element %02d %02d migrated to %d", thisIndex.x, thisIndex.y, CkMyPe());
+  }
+
+
+  // ------------ Some routines for computing the array bounds for this chare  ------------ 
+
+  // The index in the global array for my top row  
+  int top_data_idx();
+  int bottom_data_idx();
+  int left_data_idx();
+  int right_data_idx();
+  int top_neighbor();
+   
+  int bottom_neighbor();
+   
+  int left_neighbor();
+  int right_neighbor();
+  
+  
+  /// the width of the non-ghost part of the local partition 
+  int mywidth();
+    
+    
+  // the height of the non-ghost part of the local partition 
+  int myheight();
+    
+
+
+  // ------------ Some routines for computing the array bounds for arbitrary chares  ------------ 
+
+  int top_data_idx(int y, int y_total){
+    return (data_height * y) / y_total;
+  }
+
+  int bottom_data_idx(int y, int y_total){
+    return ((data_height * (y+1)) / y_total) - 1;
+  }
+
+  int left_data_idx(int x, int x_total){
+    return (data_width * x) / x_total;
+  }
+
+  int right_data_idx(int x, int x_total){
+    return ((data_width * (x+1)) / x_total) - 1;
+  }
+
+
+  int top_data_idx(int y){
+    return (data_height * y) / y_chares;
+  }
+
+  int bottom_data_idx(int y){
+    return ((data_height * (y+1)) / y_chares) - 1;
+  }
+
+  int left_data_idx(int x){
+    return (data_width * x) / x_chares;
+  }
+
+  int right_data_idx(int x){
+    return ((data_width * (x+1)) / x_chares) - 1;
+  }
+
+  /// Return which chare array element(x index) owns the global data item i
+  int who_owns_idx_x(int i){
+    int w=0;
+    while(1){
+      if( i >= left_data_idx(w) && i <= right_data_idx(w) ){
+       return w;
+      }
+      w++;
+    }
+  }
+  
+  /// Return which chare array element(y index) owns the global data item i
+  int who_owns_idx_y(int i){
+    int w=0;
+    while(1){
+      if( i >= top_data_idx(w) && i <= bottom_data_idx(w) ){
+       return w;
+      }
+      w++;
+    }
+  }
+  
+
+
+
+  
+  // Convert a local column,row id (0 to mywidth-1, 0 to data_width-1) to the index in the padded array
+  int local_to_padded(int x, int y){
+    return (mywidth()+2*data_x_ghost)*(y+data_y_ghost)+x+data_x_ghost;
+  }
+
+  // get a data value
+  double data_local(int which, int x, int y){
+    CkAssert(local_to_padded(x,y) < data_arrays_sizes[which]);
+    return data_arrays[which][local_to_padded(x,y)];
+  }
+
+
+  // Convert a local column id (0 to mywidth-1) to the global column id (0 to data_width-1)
+  int local_to_global_x(int x){
+    return left_data_idx() + x;
+  }
+
+  // Convert a local row id (0 to myheight-1) to the global row id (0 to data_height-1)
+  int local_to_global_y(int y){
+    return top_data_idx() + y;
+  }
+
+  int global_array_width(){
+    return data_width;
+  }
+
+  int global_array_height(){
+    return data_height;
+  }
+
+  int global_array_size(){
+    return global_array_width() * global_array_height();
+  }
+
+  int my_array_width(){
+    return mywidth()+2*data_x_ghost;
+  }
+
+  int my_array_height(){
+    return myheight()+2*data_y_ghost;
+  }
+
+  // Total size of arrays including ghost layers
+  int my_array_size(){
+    return my_array_width() * my_array_height();
+  }
+
+  /// Create an array. If multiple arrays are needed, each should have its own index
+  template <typename t> t* createDataArray(int which=0) {
+    t* data = new t[my_array_size()];
+    data_arrays[which] = data;
+    data_arrays_sizes[which] = my_array_size();
+
+    if(thisIndex.x==0 && thisIndex.y==0)  
+      CkPrintf("data_arrays_sizes[which] set to %d\n", data_arrays_sizes[which] );  
+
+
+    CkAssert(data_arrays[which] != NULL);
+#if DEBUG > 2
+    CkPrintf("Allocated array of size %d at %p\n", my_array_size(), data_arrays[which] );
+#endif
+    return data;
+  }
+  
+  template <typename t> t* getDataArray(int which=0) {
+    return data_arrays[which]; 
+  }
+
+  /// Constructor takes in the dimensions of the array, including any desired ghost layers
+  /// The local part of the arrays will have (mywidth+x_ghosts*2)*(myheight+y_ghosts*2) elements 
+  void setInitialDimensions(int width, int height, int x_chares_, int y_chares_, int x_ghosts=0, int y_ghosts=0){
+    data_width = width;      // These values cannot change after this method is called.
+    data_height = height;
+    data_x_ghost = x_ghosts;
+    data_y_ghost = y_ghosts;
+    
+    setDimensions(x_chares_, y_chares_);
+  }
+  
+
+  void setDimensions( int x_chares_, int y_chares_){
+    x_chares = x_chares_;
+    y_chares = y_chares_;
+    
+    
+    if( thisIndex.x < x_chares && thisIndex.y < y_chares ){
+      thisElemActive = true;
+    } else {
+      thisElemActive = false;
+    }
+    
+  }
+
+
+  redistributor2D(){
+    incoming_count = 0;
+    fakeMemoryUsage = NULL;
+  }
+
+
+  redistributor2D(CkMigrateMessage*){
+  }
+
+
+  void startup(){
+#if DEBUG > 3 
+   CkPrintf("redistributor 2D startup %03d,%03d\n", thisIndex.x, thisIndex.y);
+#endif
+    contribute();
+  }
+  
+
+  void printArrays(){
+#if DEBUG > 2
+    CkAssert(data_arrays.size()==2);
+    for(std::map<int,double*>::iterator diter = data_arrays.begin(); diter != data_arrays.end(); diter++){
+      int which_array = diter->first;
+      double *data = diter->second;
+      CkPrintf("%d,%d data_arrays[%d] = %p\n", thisIndex.x, thisIndex.y, which_array, data);
+    }
+#endif
+  }
+
+  
+  // Called on all elements involved with the new granularity or containing part of the old data
+  void resizeGranules(int new_active_chare_cols, int new_active_chare_rows){
+
+#if DEBUG>1
+    CkPrintf("Resize Granules called for elem %d,%d\n", thisIndex.x, thisIndex.y);     
+#endif
+
+    const bool previouslyActive = thisElemActive;
+    const int old_top = top_data_idx();
+    const int old_left = left_data_idx();
+    const int old_bottom = top_data_idx()+myheight()-1;
+    const int old_right = left_data_idx()+mywidth()-1;
+    const int old_myheight = myheight();
+    const int old_mywidth = mywidth();
+
+    setDimensions(new_active_chare_cols, new_active_chare_rows);
+    
+    const int new_mywidth = mywidth();
+    const int new_myheight = myheight();
+
+    // Transpose Data
+    // Assume only one new owner of my data
+
+    if(previouslyActive){
+     
+      // Send all my data to any blocks that will need it
+
+      int newOwnerXmin = who_owns_idx_x(old_left);
+      int newOwnerXmax = who_owns_idx_x(old_right);
+      int newOwnerYmin = who_owns_idx_y(old_top);
+      int newOwnerYmax = who_owns_idx_y(old_bottom);
+
+      for(int newx=newOwnerXmin; newx<=newOwnerXmax; newx++){
+       for(int newy=newOwnerYmin; newy<=newOwnerYmax; newy++){
+         
+         // Determine overlapping region between my data and this destination
+#if DEBUG > 2
+         CkPrintf("newy(%d)*new_myheight(%d)=%d, old_top=%d\n",newy,new_myheight,newy*new_myheight,old_top);
+#endif
+         // global range for overlapping area
+         int global_top = maxi(top_data_idx(newy),old_top);
+         int global_left = maxi(left_data_idx(newx),old_left);
+         int global_bottom = mini(bottom_data_idx(newy),old_bottom);
+         int global_right = mini(right_data_idx(newx),old_right);
+         int w = global_right-global_left+1;
+         int h = global_bottom-global_top+1;
+        
+         CkAssert(w*h>0);
+
+         int x_offset = global_left - old_left;
+         int y_offset = global_top - old_top;
+
+#if DEBUG > 2    
+         CkPrintf("w=%d h=%d x_offset=%d y_offset=%d\n", w, h, x_offset, y_offset);
+#endif
+         
+         std::map<int,double*>::iterator diter;
+         for(diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
+           
+           redistributor2DMsg* msg = new(w*h) redistributor2DMsg;  
+           //      CkPrintf("Created message msg %p\n", msg);  
+           
+           int which_array = diter->first;
+           double *t = diter->second;
+           int s = data_arrays_sizes[which_array];
+           
+           for(int j=0; j<h; j++){
+             for(int i=0; i<w; i++){           
+               CkAssert(j*w+i < w*h);
+               CkAssert((data_x_ghost*2+old_mywidth)*(j+y_offset+data_y_ghost)+(i+ x_offset+data_x_ghost) < s);
+               msg->data[j*w+i] = t[(data_x_ghost*2+old_mywidth)*(j+y_offset+data_y_ghost)+(i+ x_offset+data_x_ghost)];
+             }
+           }
+           
+           msg->top = global_top;
+           msg->left = global_left;
+           msg->height = h;
+           msg->width = w;
+           msg->new_chare_cols = new_active_chare_cols;
+           msg->new_chare_rows = new_active_chare_rows; 
+           msg->which_array = which_array;
+
+           //      CkPrintf("Sending message msg %p\n", msg);      
+           thisProxy(newx, newy).receiveTransposeData(msg);
+           
+         }
+         
+       }
+       
+       
+      }
+    } 
+    
+    if(!thisElemActive){
+#if DEBUG > 2
+      CkPrintf("Element %d,%d is no longer active\n", thisIndex.x, thisIndex.y);
+#endif
+
+      // Free my arrays
+      for(std::map<int,double*>::iterator diter = data_arrays.begin(); diter != data_arrays.end(); diter++){
+       int which_array = diter->first;
+       delete data_arrays[which_array]; 
+       data_arrays[which_array] = NULL;
+       data_arrays_sizes[which_array] = 0;
+      }
+      continueToNextStep();
+      
+    }
+
+    int newPe = (thisIndex.y * new_active_chare_cols + thisIndex.x) % CkNumPes();
+    
+    if(newPe == CkMyPe()){
+      //      CkPrintf("Keeping %02d , %02d on PE %d\n", thisIndex.x, thisIndex.y, newPe);
+    }
+    else{
+      // CkPrintf("Migrating %02d , %02d to PE %d\n", thisIndex.x, thisIndex.y, newPe);
+      migrateMe(newPe);
+    }
+    
+  }
+  
+
+  void continueToNextStep(){
+#if DEBUG > 2
+    CkPrintf("Elem %d,%d is ready to continue\n", thisIndex.x, thisIndex.y);
+#endif
+    for(std::map<int,double*>::iterator diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
+      int which_array = diter->first;
+      double *data = diter->second;
+      CkAssert( (data==NULL && !thisElemActive) || (data!=NULL && thisElemActive) );
+    }
+
+
+#if USE_EXTRAMEMORY
+#error NO USE_EXTRAMEMORY ALLOWED YET
+    if(thisElemActive){
+
+      long totalArtificialMemory = controlPoint("Artificial Memory Usage", 100, 500);
+      long artificialMemoryPerChare = totalArtificialMemory *1024*1024 / x_chares / y_chares;
+      
+      CkPrintf("Allocating fake memory of %d MB (of the total %d MB) (xchares=%d y_chares=%d)\n", artificialMemoryPerChare/1024/1024, totalArtificialMemory, x_chares, y_chares);
+      free(fakeMemoryUsage);
+      fakeMemoryUsage = malloc(artificialMemoryPerChare);
+      CkAssert(fakeMemoryUsage != NULL);
+    } else {
+      free(fakeMemoryUsage);
+      fakeMemoryUsage = NULL;
+    }
+#endif
+
+
+
+    incoming_count = 0; // prepare for future granularity change 
+    contribute();
+  }
+  
+  
+
+
+
+  void receiveTransposeData(redistributor2DMsg *msg){
+    int top_new = top_data_idx(thisIndex.y, msg->new_chare_rows);
+    int bottom_new = bottom_data_idx(thisIndex.y, msg->new_chare_rows);
+    int left_new = left_data_idx(thisIndex.x, msg->new_chare_cols);
+    int right_new = right_data_idx(thisIndex.x, msg->new_chare_cols);    
+
+    int new_height = bottom_new - top_new + 1;
+    int new_width = right_new - left_new + 1;
+
+    if(incoming_count == 0){
+      // Allocate new arrays 
+      std::map<int,double*>::iterator diter;
+      for(diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
+       int w = diter->first;
+       data_arrays_incoming[w] = new double[(new_width+2*data_x_ghost)*(new_height+2*data_y_ghost)];
+       data_arrays_incoming_sizes[w] = (new_width+2*data_x_ghost)*(new_height+2*data_y_ghost);
+
+       //      CkPrintf("data_arrays_incoming_sizes[%d] set to %d\n", w, data_arrays_incoming_sizes[w] );  
+
+      }
+    }
+    
+    
+    // Copy values from the incoming array to the appropriate place in data_arrays_incoming
+    // Current top left of my new array
+
+
+    double *localData = data_arrays_incoming[msg->which_array];
+    int s = data_arrays_incoming_sizes[msg->which_array];
+
+    //    CkPrintf("%d,%d data_arrays_incoming.size() = %d\n", thisIndex.x, thisIndex.y, data_arrays_incoming.size() );
+    //    CkPrintf("msg->which_array=%d   localData=%p   s=%d\n", msg->which_array, localData, s);
+    CkAssert(localData != NULL);
+
+    for(int j=0; j<msg->height; j++){
+      for(int i=0; i<msg->width; i++){
+
+       if( (msg->top+j >= top_new) && (msg->top+j <= bottom_new) && (msg->left+i >= left_new) && (msg->left+i <= right_new) ) {
+         CkAssert(j*msg->width+i<msg->height*msg->width);
+         CkAssert((msg->top+j-top_new)*new_width+(msg->left+i-left_new) < new_width*new_height);
+         CkAssert((msg->top+j-top_new)*new_width+(msg->left+i-left_new) >= 0);
+         
+         CkAssert((msg->top+j-top_new+data_y_ghost)*(new_width+2*data_x_ghost)+(msg->left+i-left_new+data_x_ghost) < s);
+         localData[(msg->top+j-top_new+data_y_ghost)*(new_width+2*data_x_ghost)+(msg->left+i-left_new+data_x_ghost)] = msg->data[j*msg->width+i];
+         incoming_count++;
+         
+       }
+       
+      }
+    }
+    
+    //    CkPrintf("Deleting message msg %p\n", msg); 
+    delete msg;
+
+
+    if(incoming_count == new_height*new_width*data_arrays.size()){
+
+      std::map<int,double*>::iterator diter;
+      for(diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
+       int w = diter->first;
+       delete[] data_arrays[w];
+       data_arrays[w] = data_arrays_incoming[w];
+       data_arrays_sizes[w] = data_arrays_incoming_sizes[w];
+       data_arrays_incoming[w] = NULL;
+       data_arrays_incoming_sizes[w] = 0;
+
+       //        if(thisIndex.x==0 && thisIndex.y==0)   
+         //          CkPrintf("data_arrays_incoming_sizes[%d] set to %d\n",w, data_arrays_incoming_sizes[w] );   
+
+         //        if(thisIndex.x==0 && thisIndex.y==0) 
+         //  CkPrintf("data_arrays_sizes[%d] set to %d\n",w, data_arrays_sizes[w] ); 
+
+      }
+
+      continueToNextStep();
+    }
+    
+  }
+};
+
+/** @} */
+#endif
index 061661776baade8be363e6430f6f2d70bc8f85f0..9d7ffa84f2092caffab7c548aba632059b1ace06 100644 (file)
@@ -1,23 +1,10 @@
 #include <charm++.h>
-#include <cmath>
-#include <math.h>
-#include <iostream>
-#include <fstream>
-#include <string>
-#include <sstream>
-#include <map>
-#include <set>
-#include <vector>
-#include <utility>
-#include <limits>
-//#include <sys/time.h>
-#include <float.h>
 
 #include "ControlPoints.decl.h"
 #include "trace-controlPoints.h"
-#include "LBDatabase.h"
 #include "controlPoints.h"
-
+#include "charm++.h"
+#include "trace-projections.h"
 
 /**
  *  \addtogroup ControlPointFramework
 
 using namespace std;
 
-#define CONTROL_POINT_SAMPLE_PERIOD 7000
+#define DEFAULT_CONTROL_POINT_SAMPLE_PERIOD  10000000
 #define NUM_SAMPLES_BEFORE_TRANSISTION 5
 #define OPTIMIZER_TRANSITION 5
 
 #define WRITEDATAFILE 0
 
-
+//#undef DEBUG
+//#define DEBUG 4
 
 static void periodicProcessControlPoints(void* ptr, double currWallTime);
 
 
+
 // A pointer to this PE's controlpoint manager Proxy
-/* readonly */ CProxy_controlPointManager localControlPointManagerProxy;
+/* readonly */ CProxy_controlPointManager controlPointManagerProxy;
 /* readonly */ int random_seed;
+/* readonly */ long controlPointSamplePeriod;
 
 
 /// A reduction type that combines idle time statistics (min/max/avg etc.)
@@ -74,409 +64,6 @@ CkReductionMsg *idleTimeReduction(int nMsg,CkReductionMsg **msgs){
 
 
 
-/// A container that stores idle time statistics (min/max/avg etc.)
-class idleTimeContainer {
-public:
-  double min;
-  double avg;
-  double max;
-  
-  idleTimeContainer(){
-    min = -1.0;
-    max = -1.0;
-    avg = -1.0;
-  }
-  
-  bool isValid() const{
-    return (min >= 0.0 && avg >= min && max >= avg && max <= 1.0);
-  }
-  
-  void print() const{
-    if(isValid())
-      CkPrintf("[%d] Idle Time is Min=%.2lf%% Avg=%.2lf%% Max=%.2lf%%\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);    
-    else
-      CkPrintf("[%d] Idle Time is invalid\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);
-  }
-  
-}; 
-
-
-
-/// Stores data for a phase (a time range in which a single set of control point values is used).
-/// The data stored includes the control point values, a set of timings registered by the application, 
-/// The critical paths detected, the max memory usage, and the idle time.
-class instrumentedPhase {
-public:
-  std::map<string,int> controlPoints; // The control point values for this phase(don't vary within the phase)
-  std::vector<double> times;  // A list of times observed for iterations in this phase
-
-  std::vector<PathHistory> criticalPaths;
-
-  
-  int memoryUsageMB;
-
-  idleTimeContainer idleTime;
-
-  instrumentedPhase(){
-    memoryUsageMB = -1;
-  }
-  
-  void clear(){
-    controlPoints.clear();
-    times.clear();
-    criticalPaths.clear();
-  }
-
-  // Provide a previously computed value, or a value from a previous run
-  bool haveValueForName(const char* name){
-    string n(name);
-    return (controlPoints.count(n)>0);
-  }
-
-  void operator=(const instrumentedPhase& p){
-    controlPoints = p.controlPoints;
-    times = p.times;
-    memoryUsageMB = p.memoryUsageMB;
-  }
-
-
-
-  bool operator<(const instrumentedPhase& p){
-    CkAssert(hasSameKeysAs(p)); 
-    std::map<string,int>::iterator iter1 = controlPoints.begin();
-    std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
-    for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){
-      if(iter1->second < iter2->second){
-       return true;
-      }
-    }
-    return false;
-  }
-
-
-  // Determines if the control point values and other information exists
-  bool hasValidControlPointValues(){
-    std::map<string,int>::iterator iter;
-    for(iter = controlPoints.begin();iter != controlPoints.end(); iter++){
-      if(iter->second == -1){ 
-        return false; 
-      }  
-    }
-
-    return true;
-  }
-
-  
-  int medianCriticalPathIdx() const{
-    // Bubble sort the critical path indices by Time
-    int numPaths = criticalPaths.size();
-    if(numPaths>0){
-      int *sortedPaths = new int[numPaths];
-      for(int i=0;i<numPaths;i++){
-       sortedPaths[i] = i;
-      }
-      
-      for(int j=0;j<numPaths;j++){
-       for(int i=0;i<numPaths-1;i++){
-         if(criticalPaths[sortedPaths[i]].getTotalTime() < criticalPaths[sortedPaths[i+1]].getTotalTime()){
-           // swap sortedPaths[i], sortedPaths[i+1]
-           int tmp = sortedPaths[i+1];
-           sortedPaths[i+1] = sortedPaths[i];
-           sortedPaths[i] = tmp;
-         }
-       }
-      }
-      int result = sortedPaths[numPaths/2];
-      delete[] sortedPaths;
-      return result;
-    } else {
-      return 0;
-    }
-  }
-
-
-
-  bool operator==(const instrumentedPhase& p){
-    CkAssert(hasSameKeysAs(p));
-    std::map<string,int>::iterator iter1 = controlPoints.begin();
-    std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
-    for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){ 
-      if(iter1->second != iter2->second){ 
-        return false; 
-      }  
-    }
-    return true;
-  }
-
-  /// Verify the names of the control points are consistent
-  /// note: std::map stores the pairs in a sorted order based on their first component 
-  bool hasSameKeysAs(const instrumentedPhase& p){
-    
-    if(controlPoints.size() != p.controlPoints.size())
-      return false;
-
-    std::map<string,int>::iterator iter1 = controlPoints.begin(); 
-    std::map<string,int>::const_iterator iter2 = p.controlPoints.begin(); 
-
-    for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){  
-      if(iter1->first != iter2->first)
-       return false;
-    } 
-
-    return true; 
-  }
-
-
-  void addAllNames(std::set<string> names_) {
-    
-    std::set<string> names = names_;
-    
-    // Remove all the names that we already have
-    std::map<std::string,int>::iterator iter;
-    
-    for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
-      names.erase(iter->first);
-    }
-    
-    // Add -1 values for each name we didn't find
-    std::set<std::string>::iterator iter2;
-    for(iter2 = names.begin(); iter2 != names.end(); iter2++){
-      controlPoints.insert(make_pair(*iter2,-1));
-      CkPrintf("One of the datasets was missing a value for %s, so -1 was used\n", iter2->c_str());
-    }
-
-  }
-
-
-
-  void print() {
-    std::map<std::string,int>::iterator iter;
-
-    if(controlPoints.size() == 0){
-      CkPrintf("no control point values found\n");
-    }
-    
-    for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
-      std::string name = iter->first;
-      int val = iter->second;
-      CkPrintf("%s ---> %d\n",  name.c_str(),  val);
-    } 
-    
-  }
-  
-  
-};
-
-
-/// Stores and manipulate all known instrumented phases. One instance of this exists on each PE in its local controlPointManager
-class instrumentedData {
-public:
-
-  /// Stores all known instrumented phases(loaded from file, or from this run)
-  std::vector<instrumentedPhase> phases;
-
-  /// get control point names for all phases
-  std::set<string> getNames(){
-    std::set<string> names;
-    
-    std::vector<instrumentedPhase>::iterator iter;
-    for(iter = phases.begin();iter!=phases.end();iter++) {
-      
-      std::map<string,int>::iterator iter2;
-      for(iter2 = iter->controlPoints.begin(); iter2 != iter->controlPoints.end(); iter2++){
-       names.insert(iter2->first);
-      }
-      
-    }  
-    return names;
-
-  } 
-
-
-  void cleanupNames(){
-    std::set<string> names = getNames();
-    
-    std::vector<instrumentedPhase>::iterator iter;
-    for(iter = phases.begin();iter!=phases.end();iter++) {
-      iter->addAllNames(names);
-    }
-  }
-
-
-  /// Remove one phase with invalid control point values if found
-  bool filterOutOnePhase(){
-    // Note: calling erase on a vector will invalidate any iterators beyond the deletion point
-    std::vector<instrumentedPhase>::iterator iter;
-    for(iter = phases.begin(); iter != phases.end(); iter++) {
-      if(! iter->hasValidControlPointValues()  || iter->times.size()==0){
-       // CkPrintf("Filtered out a phase with incomplete control point values\n");
-       phases.erase(iter);
-       return true;
-      } else {
-       //      CkPrintf("Not filtering out some phase with good control point values\n");
-      }
-    }
-    return false;
-  }
-  
-  /// Drop any phases that do not contain timings or control point values
-  void filterOutIncompletePhases(){
-    bool done = false;
-    while(filterOutOnePhase()){
-      // do nothing
-    }
-  }
-
-
-  string toString(){
-    ostringstream s;
-
-    verify();
-
-    filterOutIncompletePhases();
-
-    // HEADER:
-    s << "# HEADER:\n";
-    s << "# Data for use with Isaac Dooley's Control Point Framework\n";
-    s << string("# Number of instrumented timings in this file:\n"); 
-    s << phases.size() << "\n" ;
-    
-    if(phases.size() > 0){
-      
-      std::map<string,int> &ps = phases[0].controlPoints; 
-      std::map<string,int>::iterator cpiter;
-
-      // SCHEMA:
-      s << "# SCHEMA:\n";
-      s << "# number of named control points:\n";
-      s << ps.size() << "\n";
-      
-      for(cpiter = ps.begin(); cpiter != ps.end(); cpiter++){
-       s << cpiter->first << "\n";
-      }
-      
-      // DATA:
-      s << "# DATA:\n";
-      s << "# first field is memory usage (MB). Then there are the " << ps.size()  << " control points values, followed by one or more timings" << "\n";
-      s << "# number of control point sets: " << phases.size() << "\n";
-      std::vector<instrumentedPhase>::iterator runiter;
-      for(runiter=phases.begin();runiter!=phases.end();runiter++){
-
-       // Print the memory usage
-        s << runiter->memoryUsageMB << "    "; 
-
-       // Print the control point values
-       for(cpiter = runiter->controlPoints.begin(); cpiter != runiter->controlPoints.end(); cpiter++){ 
-         s << cpiter->second << " "; 
-       }
-
-       s << "     ";
-
-       // Print the times
-       std::vector<double>::iterator titer;
-       for(titer = runiter->times.begin(); titer != runiter->times.end(); titer++){
-         s << *titer << " ";
-       }
-
-       s << "\n";
-       
-      }
-    }
-
-    return s.str();
-    
-  }
-
-
-  /// Verify that all our phases of data have the same sets of control point names
-  void verify(){
-    if(phases.size() > 1){
-      instrumentedPhase & firstpoint = phases[0];
-      std::vector<instrumentedPhase>::iterator iter;
-      for(iter = phases.begin();iter!=phases.end();iter++){
-       CkAssert( firstpoint.hasSameKeysAs(*iter));
-      }  
-    } 
-  }
-
-
-  // Find the fastest time from previous runs
-  instrumentedPhase findBest(){
-    CkAssert(phases.size()>0);
-
-    double total_time = 0.0; // total for all times
-    int total_count = 0;
-
-    instrumentedPhase best_phase;
-#if OLDMAXDOUBLE
-    double best_phase_avgtime = std::numeric_limits<double>::max();
-#else
-    double best_phase_avgtime = DBL_MAX;
-#endif
-
-    int valid_phase_count = 0;
-
-    std::vector<instrumentedPhase>::iterator iter;
-    for(iter = phases.begin();iter!=phases.end();iter++){
-      if(iter->hasValidControlPointValues()){
-       valid_phase_count++;
-
-       double total_for_phase = 0.0;
-       int phase_count = 0;
-
-       // iterate over all times for this control point configuration
-       std::vector<double>::iterator titer;
-       for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
-         total_count++;
-         total_time += *titer;
-         total_for_phase += *titer;
-         phase_count ++;
-       }
-
-       double phase_average_time = total_for_phase / (double)phase_count;
-
-       if(phase_average_time  < best_phase_avgtime){
-         best_phase = *iter;
-         best_phase_avgtime = phase_average_time; 
-       }
-
-      }
-    }
-    
-    CkAssert(total_count > 0);
-
-    double avg = total_time / total_count;
-
-    if(CkMyPe() == 0){
-      CkPrintf("Best average time for a phase was %.1lf\n", best_phase_avgtime);
-      CkPrintf("Mean time for all %d times in the %d valid recorded phases was %.1lf\n", total_count, valid_phase_count, avg );
-    }
-
-    // Compute standard deviation
-    double sumx=0.0;
-    for(iter = phases.begin();iter!=phases.end();iter++){
-      if(iter->hasValidControlPointValues()){
-       std::vector<double>::iterator titer;
-       for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
-         sumx += (avg - *titer)*(avg - *titer);
-       } 
-      }
-    }
-    
-    double std_dev = sqrt(sumx / total_count);
-
-    if(CkMyPe() == 0){
-      CkPrintf("Standard Deviation for previous runs was %.2lf   or %.1lf%% of mean\n", std_dev, std_dev/avg*100.0);
-      CkPrintf("The best phase average time was %.1lf%% faster than the mean\n", (avg-best_phase_avgtime)/avg*100.0);
-
-    }
-
-    return best_phase;
-  }
-  
-};
-
 
 
 /// Return an integer between 0 and num-1 inclusive
@@ -510,56 +97,8 @@ unsigned int randInt(unsigned int num, const char* name, int seed=0){
 
 
 
-
-//=============================================================================
-// THE MODULE CODE IS HERE: 
-//=============================================================================
-
-
-/// A chare group that contains most of the control point framework data and code.
-class controlPointManager : public CBase_controlPointManager {
-public:
-  
-  char * dataFilename;
-  
-  instrumentedData allData;
-  instrumentedPhase thisPhaseData;
-  instrumentedPhase best_phase;
-  
-  /// The lower and upper bounds for each named control point
-  std::map<string, pair<int,int> > controlPointSpace;
-
-  /// A set of named control points whose values cannot change within a single run of an application
-  std::set<string> staticControlPoints;
-
-  /// Sets of entry point ids that are affected by some named control points
-  std::map<string, std::set<int> > affectsPrioritiesEP;
-  /// Sets of entry array ids that are affected by some named control points
-  std::map<string, std::set<int> > affectsPrioritiesArray;
-
-  
-  /// The control points to be used in the next phase. In gotoNextPhase(), these will be used
-  std::map<string,int> newControlPoints;
-  /// Whether to use newControlPoints in gotoNextPhase()
-  bool newControlPointsAvailable;
-  
-  /// A user supplied callback to call when control point values are to be changed
-  CkCallback granularityCallback;
-  bool haveGranularityCallback;
-  bool frameworkShouldAdvancePhase;
-  
-  int phase_id;
-
-  bool alreadyRequestedMemoryUsage;
-  bool alreadyRequestedIdleTime;
-
-
-#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
-  /// The path history
-  PathHistory maxTerminalPathHistory;
-#endif
-
-  controlPointManager(){
+controlPointManager::controlPointManager(){
+    pathHistoryTableLastIdx = 0;
     newControlPointsAvailable = false;
     alreadyRequestedMemoryUsage = false;   
     alreadyRequestedIdleTime = false;
@@ -573,7 +112,7 @@ public:
     
     phase_id = 0;
     
-    localControlPointManagerProxy = thisProxy;
+    controlPointManagerProxy = thisProxy;
     
     loadDataFile();
     
@@ -581,12 +120,17 @@ public:
       allData.findBest();
     }
     
-    if(CkMyPe() == 0)
-      CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, CONTROL_POINT_SAMPLE_PERIOD, CkMyPe());
+    if(CkMyPe() == 0){
+      CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, controlPointSamplePeriod, CkMyPe());
+    }
 
     traceRegisterUserEvent("No currently executing message", 5000);
     traceRegisterUserEvent("Zero time along critical path", 5010);
     traceRegisterUserEvent("Positive total time along critical path", 5020);
+    traceRegisterUserEvent("env->setPathHistory()", 6000);
+    traceRegisterUserEvent("Critical Path", 5900);
+    traceRegisterUserEvent("Table Entry", 5901);
+
 
 #if USER_EVENT_FOR_REGISTERTERMINALPATH
     traceRegisterUserEvent("registerTerminalPath", 100); 
@@ -594,13 +138,14 @@ public:
 
   }
   
-  ~controlPointManager(){
+
+ controlPointManager::~controlPointManager(){
     CkPrintf("[%d] controlPointManager() Destructor\n", CkMyPe());
   }
 
 
   /// Loads the previous run data file
-  void loadDataFile(){
+  void controlPointManager::loadDataFile(){
     ifstream infile(dataFilename);
     vector<string> names;
     string line;
@@ -668,7 +213,7 @@ public:
 
 
   /// Add the current data to allData and output it to a file
-  void writeDataFile(){
+  void controlPointManager::writeDataFile(){
 #if WRITEDATAFILE
     CkPrintf("============= writeDataFile() ============\n");
     ofstream outfile(dataFilename);
@@ -682,7 +227,7 @@ public:
   }
 
   /// User can register a callback that is called when application should advance to next phase
-  void setGranularityCallback(CkCallback cb, bool _frameworkShouldAdvancePhase){
+  void controlPointManager::setGranularityCallback(CkCallback cb, bool _frameworkShouldAdvancePhase){
     frameworkShouldAdvancePhase = _frameworkShouldAdvancePhase;
     granularityCallback = cb;
     haveGranularityCallback = true;
@@ -690,7 +235,7 @@ public:
 
   /// Called periodically by the runtime to handle the control points
   /// Currently called on each PE
-  void processControlPoints(){
+  void controlPointManager::processControlPoints(){
 
     CkPrintf("[%d] processControlPoints() haveGranularityCallback=%d frameworkShouldAdvancePhase=%d\n", CkMyPe(), (int)haveGranularityCallback, (int)frameworkShouldAdvancePhase);
 
@@ -720,37 +265,21 @@ public:
     for(int p=0;p<s;++p){
       const instrumentedPhase &phase = allData.phases[p];
       const idleTimeContainer &idle = phase.idleTime;
-      vector<PathHistory> const &criticalPaths = phase.criticalPaths;
+      //      vector<MergeablePathHistory> const &criticalPaths = phase.criticalPaths;
       vector<double> const &times = phase.times;
 
       CkPrintf("Phase %d:\n", p);
       idle.print();
-      CkPrintf("critical paths: (* affected by control point)\n");
-      for(int i=0;i<criticalPaths.size(); i++){
+     //   CkPrintf("critical paths: (* affected by control point)\n");
+       //   for(int i=0;i<criticalPaths.size(); i++){
        // If affected by a control point
        //      criticalPaths[i].print();
 
-
-       CkPrintf("Critical Path Time=%lf : ", (double)criticalPaths[i].getTotalTime());
-       for(int e=0;e<numEpIdxs;e++){
-
-         if(criticalPaths[i].getEpIdxCount(e)>0){
-           if(controlPointAffectsThisEP(e))
-             CkPrintf("* ");
-           CkPrintf("EP %d count=%d : ", e, (int)criticalPaths[i].getEpIdxCount(e));
-         }
-       }
-       for(int a=0;a<numArrayIds;a++){
-         if(criticalPaths[i].getArrayIdxCount(a)>0){
-           if(controlPointAffectsThisArray(a))
-             CkPrintf("* ");
-           CkPrintf("Array %d count=%d : ", a, (int)criticalPaths[i].getArrayIdxCount(a));
-         }
-       }
-       CkPrintf("\n");
+      //       criticalPaths[i].print();
+      //       CkPrintf("\n");
        
 
-      }
+      //   }
       CkPrintf("Timings:\n");
       for(int i=0;i<times.size(); i++){
        CkPrintf("%lf ", times[i]);
@@ -768,6 +297,7 @@ public:
 
     //==========================================================================================
     // If this is a phase during which we try to adapt control point values based on critical path
+#if 0
 
     if( s%5 == 4) {
 
@@ -805,13 +335,14 @@ public:
          int cpcount = 0;
          std::set<string> controlPointsAffectingCriticalPath;
 
+         
+         for(int e=0;e<path.getNumUsed();e++){
+           if(path.getUsedCount(e)>0){
+             int ep = path.getUsedEp(e);
 
-         for(int e=0;e<numEpIdxs;e++){
-           if(path.getEpIdxCount(e)>0){
-             
              std::map<string, std::set<int> >::iterator iter;
              for(iter=affectsPrioritiesEP.begin(); iter!= affectsPrioritiesEP.end(); ++iter){
-               if(iter->second.count(e)>0){
+               if(iter->second.count(ep)>0){
                  controlPointsAffectingCriticalPath.insert(iter->first);
                  CkPrintf("Control Point \"%s\" affects the critical path\n", iter->first.c_str());
                  cpcount++;
@@ -908,6 +439,7 @@ public:
     }
     
 
+#endif
 
 
     CkPrintf("\n");
@@ -915,7 +447,7 @@ public:
   }
   
   /// Determine if any control point is known to affect an entry method
-  bool controlPointAffectsThisEP(int ep){
+  bool controlPointManager::controlPointAffectsThisEP(int ep){
     std::map<string, std::set<int> >::iterator iter;
     for(iter=affectsPrioritiesEP.begin(); iter!= affectsPrioritiesEP.end(); ++iter){
       if(iter->second.count(ep)>0){
@@ -926,7 +458,7 @@ public:
   }
   
   /// Determine if any control point is known to affect a chare array  
-  bool controlPointAffectsThisArray(int array){
+  bool controlPointManager::controlPointAffectsThisArray(int array){
     std::map<string, std::set<int> >::iterator iter;
     for(iter=affectsPrioritiesArray.begin(); iter!= affectsPrioritiesArray.end(); ++iter){
       if(iter->second.count(array)>0){
@@ -937,7 +469,7 @@ public:
   }
   
   /// The data from the previous phase
-  instrumentedPhase *previousPhaseData(){
+  instrumentedPhase * controlPointManager::previousPhaseData(){
     int s = allData.phases.size();
     if(s >= 1 && phase_id > 0) {
       return &(allData.phases[s-1]);
@@ -948,11 +480,11 @@ public:
   
 
   /// Called by either the application or the Control Point Framework to advance to the next phase  
-  void gotoNextPhase(){
+  void controlPointManager::gotoNextPhase(){
 
     LBDatabase * myLBdatabase = LBDatabaseObj();
 
-#if CMK_LBDB_ON
+#if CMK_LBDB_ON && 0
     LBDB * myLBDB = myLBdatabase->getLBDB();       // LBDB is Defined in LBDBManager.h
     const CkVec<LBObj*> objs = myLBDB->getObjs();
     const int objCount = myLBDB->getObjCount();
@@ -992,28 +524,27 @@ public:
   }
 
   /// An application uses this to register an instrumented timing for this phase
-  void setTiming(double time){
+  void controlPointManager::setTiming(double time){
     thisPhaseData.times.push_back(time);
 #ifdef USE_CRITICAL_PATH_HEADER_ARRAY
        
     // First we should register this currently executing message as a path, because it is likely an important one to consider.
-    registerTerminalEntryMethod();
+    //    registerTerminalEntryMethod();
     
     // save the critical path for this phase
-    thisPhaseData.criticalPaths.push_back(maxTerminalPathHistory);
-    maxTerminalPathHistory.reset();
+    //   thisPhaseData.criticalPaths.push_back(maxTerminalPathHistory);
+    //    maxTerminalPathHistory.reset();
     
     
     // Reset the counts for the currently executing message
-    resetThisEntryPath();
-    
-    
+    //resetThisEntryPath();
+        
 #endif
     
   }
   
   /// Entry method called on all PEs to request memory usage
-  void requestIdleTime(CkCallback cb){
+  void controlPointManager::requestIdleTime(CkCallback cb){
     double i = localControlPointTracingInstance()->idleRatio();
     double idle[3];
     idle[0] = i;
@@ -1026,7 +557,7 @@ public:
   }
   
   /// All processors reduce their memory usages in requestIdleTime() to this method
-  void gatherIdleTime(CkReductionMsg *msg){
+  void controlPointManager::gatherIdleTime(CkReductionMsg *msg){
     int size=msg->getSize() / sizeof(double);
     CkAssert(size==3);
     double *r=(double *) msg->getData();
@@ -1050,7 +581,7 @@ public:
 
 
   /// Entry method called on all PEs to request memory usage
-  void requestMemoryUsage(CkCallback cb){
+  void controlPointManager::requestMemoryUsage(CkCallback cb){
     int m = CmiMaxMemoryUsage() / 1024 / 1024;
     CmiResetMaxMemory();
     CkPrintf("PE %d Memory Usage is %d MB\n",CkMyPe(), m);
@@ -1058,7 +589,7 @@ public:
   }
 
   /// All processors reduce their memory usages to this method
-  void gatherMemoryUsage(CkReductionMsg *msg){
+  void controlPointManager::gatherMemoryUsage(CkReductionMsg *msg){
     int size=msg->getSize() / sizeof(int);
     CkAssert(size==1);
     int *m=(int *) msg->getData();
@@ -1077,50 +608,118 @@ public:
   }
 
 
-  /// An entry method used to both register and reduce the maximal critical paths back to PE 0
-  void registerTerminalPath(PathHistory &path){
-#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
-  
-    double beginTime = CmiWallTimer();
-        
   if(maxTerminalPathHistory.updateMax(path) ) {
-      // The new path is more critical than the previous one
-      // propogate it towards processor 0 in a binary tree
-      if(CkMyPe() > 0){
-       int dest = (CkMyPe() -1) / 2;
-       //      CkPrintf("Forwarding better critical path from PE %d to %d\n", CkMyPe(), dest);
+  /** Trace perform a traversal backwards over the critical path specified as a 
+      table index for the processor upon which this is called.
+      
+      The callback cb will be called with the resulting msg after the path has 
+      been traversed to its origin.  
+  */
void controlPointManager::traceCriticalPathBack(pathInformationMsg *msg){
+   int count = pathHistoryTable.count(msg->table_idx);
+#if DEBUG > 2
+   CkPrintf("Table entry %d on pe %d occurs %d times in table\n", msg->table_idx, CkMyPe(), count);
+#endif
+   CkAssert(count==0 || count==1);
 
-       // This is part of a reduction-like propagation of the maximum back to PE 0
-       resetThisEntryPath();
+    if(count > 0){ 
+      PathHistoryTableEntry & path = pathHistoryTable[msg->table_idx];
+      int idx = path.sender_history_table_idx;
+      int pe = path.sender_pe;
 
-       thisProxy[dest].registerTerminalPath(path);
+#if DEBUG > 2
+      CkPrintf("Table entry %d on pe %d points to pe=%d idx=%d\n", msg->table_idx, CkMyPe(), pe, idx);
+#endif
+
+      // Make a copy of the message for broadcasting to all PEs
+      pathInformationMsg *newmsg = new(msg->historySize+1) pathInformationMsg;
+      for(int i=0;i<msg->historySize;i++){
+       newmsg->history[i] = msg->history[i];
+      }
+      newmsg->history[msg->historySize] = path;
+      newmsg->historySize = msg->historySize+1;
+      newmsg->cb = msg->cb;
+      newmsg->table_idx = idx;
+      
+      // Keep a message for returning to the user's callback
+      pathForUser = new(msg->historySize+1) pathInformationMsg;
+      for(int i=0;i<msg->historySize;i++){
+       pathForUser->history[i] = msg->history[i];
+      }
+      pathForUser->history[msg->historySize] = path;
+      pathForUser->historySize = msg->historySize+1;
+      pathForUser->cb = msg->cb;
+      pathForUser->table_idx = idx;
+      
+      
+      if(idx > -1 && pe > -1){
+       CkAssert(pe < CkNumPes() && pe >= 0);
+       thisProxy[pe].traceCriticalPathBack(newmsg);
+      } else {
+       CkPrintf("Traced critical path back to its origin.\n");
+       CkPrintf("Broadcasting it to all PE\n");
+       thisProxy.broadcastCriticalPathResult(newmsg);
       }
+    } else {
+      CkAbort("ERROR: Traced critical path back to a nonexistent table entry.\n");
     }
 
-#if USER_EVENT_FOR_REGISTERTERMINALPATH
-    traceUserBracketEvent(100, beginTime, CmiWallTimer());
-#endif
-
-#endif
+    delete msg;
   }
 
-  /// Print the maximal known critical path on this PE
-  void printTerminalPath(){
-#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
-    maxTerminalPathHistory.print();
-#endif
+
+void controlPointManager::broadcastCriticalPathResult(pathInformationMsg *msg){
+  CkPrintf("[%d] Received broadcast of critical path\n", CkMyPe());
+  int me = CkMyPe();
+  int intersectsLocalPE = false;
+
+  // Create user events for critical path
+
+  for(int i=msg->historySize-1;i>=0;i--){
+    if(CkMyPe() == msg->history[i].local_pe){
+      // Part of critical path is local
+      // Create user event for it
+
+      //      CkPrintf("\t[%d] Path Step %d: local_path_time=%lf arr=%d ep=%d starttime=%lf preceding path time=%lf pe=%d\n",CkMyPe(), i, msg->history[i].get_local_path_time(), msg-> history[i].local_arr, msg->history[i].local_ep, msg->history[i].get_start_time(), msg->history[i].get_preceding_path_time(), msg->history[i].local_pe);
+      traceUserBracketEvent(5900, msg->history[i].get_start_time(), msg->history[i].get_start_time() + msg->history[i].get_local_path_time());
+      intersectsLocalPE = true;
+    }
+
   }
+  
 
-  /// Reset the maximal known critical path on this PE  
-  void resetTerminalPath(){
-#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
-    maxTerminalPathHistory.reset();
-#endif
+#if PRUNE_CRITICAL_PATH_LOGS
+  // Tell projections tracing to only output log entries if I contain part of the critical path
+  if(! intersectsLocalPE){
+    disableTraceLogOutput();
+    CkPrintf("PE %d doesn't intersect the critical path, so its log files won't be created\n", CkMyPe() );
+  }
+#endif  
+  
+#if TRACE_ALL_PATH_TABLE_ENTRIES
+  // Create user events for all table entries
+  std::map< int, PathHistoryTableEntry >::iterator iter;
+  for(iter=pathHistoryTable.begin(); iter != pathHistoryTable.end(); iter++){
+    double startTime = iter->second.get_start_time();
+    double endTime = iter->second.get_start_time() + iter->second.get_local_path_time();
+    traceUserBracketEvent(5901, startTime, endTime);
   }
+#endif
 
+  int data=1;
+  CkCallback cb(CkIndex_controlPointManager::criticalPathDone(NULL),thisProxy[0]); 
+  contribute(sizeof(int), &data, CkReduction::sum_int, cb);
+}
 
+void controlPointManager::criticalPathDone(CkReductionMsg *msg){
+  CkPrintf("[%d] All PEs have received the critical path information. Sending critical path to user supplied callback.\n", CkMyPe());
+  pathForUser->cb.send(pathForUser);
+  pathForUser = NULL;
+}
+
+
   /// Inform the control point framework that a named control point affects the priorities of some array  
-  void associatePriorityArray(const char *name, int groupIdx){
+  void controlPointManager::associatePriorityArray(const char *name, int groupIdx){
     CkPrintf("Associating control point \"%s\" affects priority of array id=%d\n", name, groupIdx );
     
     if(affectsPrioritiesArray.count(std::string(name)) > 0 ) {
@@ -1148,7 +747,7 @@ public:
   }
   
   /// Inform the control point framework that a named control point affects the priority of some entry method
-  void associatePriorityEntry(const char *name, int idx){
+  void controlPointManager::associatePriorityEntry(const char *name, int idx){
     CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
 
       if(affectsPrioritiesEP.count(std::string(name)) > 0 ) {
@@ -1176,12 +775,11 @@ public:
 
   }
   
-};
 
 
 /// An interface callable by the application.
 void gotoNextPhase(){
-  localControlPointManagerProxy.ckLocalBranch()->gotoNextPhase();
+  controlPointManagerProxy.ckLocalBranch()->gotoNextPhase();
 }
 
 
@@ -1200,7 +798,17 @@ public:
     random_seed =  sec ^ usec;
 #endif
 
-    localControlPointManagerProxy = CProxy_controlPointManager::ckNew();
+
+    double period;
+    bool found = CmiGetArgDoubleDesc(args->argv,"+CPSamplePeriod", &period,"The time between Control Point Framework samples (in seconds)");
+    if(found){
+      CkPrintf("LBPERIOD = %ld sec\n", period);
+      controlPointSamplePeriod =  period * 1000;
+    } else {
+      controlPointSamplePeriod =  DEFAULT_CONTROL_POINT_SAMPLE_PERIOD;
+    }
+
+    controlPointManagerProxy = CProxy_controlPointManager::ckNew();
   }
   ~controlPointMain(){}
 };
@@ -1209,7 +817,7 @@ public:
 void registerGranularityChangeCallback(CkCallback cb, bool frameworkShouldAdvancePhase){
   CkAssert(CkMyPe() == 0);
   CkPrintf("registerGranularityChangeCallback\n");
-  localControlPointManagerProxy.ckLocalBranch()->setGranularityCallback(cb, frameworkShouldAdvancePhase);
+  controlPointManagerProxy.ckLocalBranch()->setGranularityCallback(cb, frameworkShouldAdvancePhase);
 }
 
 /// An interface callable by the application.
@@ -1218,14 +826,14 @@ void registerControlPointTiming(double time){
 #if DEBUG>0
   CkPrintf("Program registering its own timing with registerControlPointTiming(time=%lf)\n", time);
 #endif
-  localControlPointManagerProxy.ckLocalBranch()->setTiming(time);
+  controlPointManagerProxy.ckLocalBranch()->setTiming(time);
 }
 
 /// Shutdown the control point framework, writing data to disk if necessary
 extern "C" void controlPointShutdown(){
   CkAssert(CkMyPe() == 0);
   CkPrintf("[%d] controlPointShutdown() at CkExit()\n", CkMyPe());
-  localControlPointManagerProxy.ckLocalBranch()->writeDataFile();
+  controlPointManagerProxy.ckLocalBranch()->writeDataFile();
   CkExit();
 }
 
@@ -1240,8 +848,8 @@ static void periodicProcessControlPoints(void* ptr, double currWallTime){
 #ifdef DEBUG
   CkPrintf("[%d] periodicProcessControlPoints()\n", CkMyPe());
 #endif
-  localControlPointManagerProxy.ckLocalBranch()->processControlPoints();
-  CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, CONTROL_POINT_SAMPLE_PERIOD, CkMyPe());
+  controlPointManagerProxy.ckLocalBranch()->processControlPoints();
+  CcdCallFnAfterOnPE((CcdVoidFn)periodicProcessControlPoints, (void*)NULL, controlPointSamplePeriod, CkMyPe());
 }
 
 
@@ -1250,12 +858,12 @@ static void periodicProcessControlPoints(void* ptr, double currWallTime){
 
 // Static point for life of program: randomly chosen, no optimizer
 int staticPoint(const char *name, int lb, int ub){
-  instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
-  std::set<string> &staticControlPoints = localControlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
+  instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
+  std::set<string> &staticControlPoints = controlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
 
   int result = lb + randInt(ub-lb+1, name);
   
-  localControlPointManagerProxy.ckLocalBranch()->controlPointSpace.insert(std::make_pair(string(name),std::make_pair(lb,ub))); 
+  controlPointManagerProxy.ckLocalBranch()->controlPointSpace.insert(std::make_pair(string(name),std::make_pair(lb,ub))); 
   thisPhaseData.controlPoints.insert(std::make_pair(string(name),result)); 
   staticControlPoints.insert(string(name));
 
@@ -1266,10 +874,10 @@ int staticPoint(const char *name, int lb, int ub){
 /// Should an optimizer determine the control point values
 bool valueShouldBeProvidedByOptimizer(){
   
-  const int effective_phase = localControlPointManagerProxy.ckLocalBranch()->allData.phases.size();
-  const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id; 
+  const int effective_phase = controlPointManagerProxy.ckLocalBranch()->allData.phases.size();
+  const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id; 
   
-  std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace; 
+  std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace; 
   
   double spaceSize = 1.0;
   std::map<string, pair<int,int> >::iterator iter;
@@ -1294,8 +902,8 @@ bool valueShouldBeProvidedByOptimizer(){
 /// user observed characteristic to adapt specific control point values.
 /// @note eventually there should be a plugin system where multiple schemes can be plugged in(similar to LB)
 int valueProvidedByOptimizer(const char * name){
-  const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
-  const int effective_phase = localControlPointManagerProxy.ckLocalBranch()->allData.phases.size();
+  const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
+  const int effective_phase = controlPointManagerProxy.ckLocalBranch()->allData.phases.size();
 
 
 #define OPTIMIZER_ADAPT_CRITICAL_PATHS 1
@@ -1305,13 +913,13 @@ int valueProvidedByOptimizer(const char * name){
   // This scheme will return the median value for the range 
   // early on, and then will transition over to the new control points
   // determined by the critical path adapting code
-  if(localControlPointManagerProxy.ckLocalBranch()->newControlPointsAvailable){
-    int result = localControlPointManagerProxy.ckLocalBranch()->newControlPoints[string(name)];
+  if(controlPointManagerProxy.ckLocalBranch()->newControlPointsAvailable){
+    int result = controlPointManagerProxy.ckLocalBranch()->newControlPoints[string(name)];
     CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d  from \"newControlPoints\" is: %d\n", name, phase_id, result);
     return result;
   } 
   
-  std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
+  std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
 
   if(controlPointSpace.count(std::string(name))>0){
     int minValue =  controlPointSpace[std::string(name)].first;
@@ -1325,15 +933,15 @@ int valueProvidedByOptimizer(const char * name){
   if(firstTime){
     firstTime = false;
     CkPrintf("Finding best phase\n");
-    instrumentedPhase p = localControlPointManagerProxy.ckLocalBranch()->allData.findBest(); 
+    instrumentedPhase p = controlPointManagerProxy.ckLocalBranch()->allData.findBest(); 
     CkPrintf("p=:\n");
     p.print();
     CkPrintf("\n");
-    localControlPointManagerProxy.ckLocalBranch()->best_phase = p;
+    controlPointManagerProxy.ckLocalBranch()->best_phase = p;
   }
   
   
-  instrumentedPhase &p = localControlPointManagerProxy.ckLocalBranch()->best_phase;
+  instrumentedPhase &p = controlPointManagerProxy.ckLocalBranch()->best_phase;
   int result = p.controlPoints[std::string(name)];
   CkPrintf("valueProvidedByOptimizer(): Control Point \"%s\" for phase %d chosen out of best previous phase to be: %d\n", name, phase_id, result);
   return result;
@@ -1346,10 +954,10 @@ int valueProvidedByOptimizer(const char * name){
   // Find the best search space configuration, and try something
   // nearby it, with a radius decreasing as phases increase
   
-  std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
+  std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;  
   
   CkPrintf("Finding best phase\n"); 
-  instrumentedPhase p = localControlPointManagerProxy.ckLocalBranch()->allData.findBest();  
+  instrumentedPhase p = controlPointManagerProxy.ckLocalBranch()->allData.findBest();  
   CkPrintf("best found:\n"); 
   p.print(); 
   CkPrintf("\n"); 
@@ -1384,8 +992,8 @@ int valueProvidedByOptimizer(const char * name){
 #else
   // Exhaustive search
 
-  std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;
-  std::set<string> &staticControlPoints = localControlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
+  std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;
+  std::set<string> &staticControlPoints = controlPointManagerProxy.ckLocalBranch()->staticControlPoints;  
    
   int numDimensions = controlPointSpace.size();
   CkAssert(numDimensions > 0);
@@ -1427,8 +1035,8 @@ int valueProvidedByOptimizer(const char * name){
   config.push_back(0);
   
   // Increment until finding an unused configuration
-  localControlPointManagerProxy.ckLocalBranch()->allData.cleanupNames(); // put -1 values in for any control points missing
-  std::vector<instrumentedPhase> &phases = localControlPointManagerProxy.ckLocalBranch()->allData.phases;     
+  controlPointManagerProxy.ckLocalBranch()->allData.cleanupNames(); // put -1 values in for any control points missing
+  std::vector<instrumentedPhase> &phases = controlPointManagerProxy.ckLocalBranch()->allData.phases;     
 
   while(true){
     
@@ -1508,8 +1116,8 @@ return 0;
 // Dynamic point varies throughout the life of program
 // The value it returns is based upon phase_id, a counter that changes for each phase of computation
 int controlPoint2Pow(const char *name, int fine_granularity, int coarse_granularity){
-  instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
-  const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
+  instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
+  const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
 
   int result;
 
@@ -1546,9 +1154,9 @@ int controlPoint2Pow(const char *name, int fine_granularity, int coarse_granular
 
 /// Get control point value from range of integers [lb,ub]
 int controlPoint(const char *name, int lb, int ub){
-  instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
-  const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
-  std::map<string, pair<int,int> > &controlPointSpace = localControlPointManagerProxy.ckLocalBranch()->controlPointSpace;
+  instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
+  const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
+  std::map<string, pair<int,int> > &controlPointSpace = controlPointManagerProxy.ckLocalBranch()->controlPointSpace;
 
   int result;
 
@@ -1570,8 +1178,8 @@ int controlPoint(const char *name, int lb, int ub){
 
 /// Get control point value from set of provided integers
 int controlPoint(const char *name, std::vector<int>& values){
-  instrumentedPhase &thisPhaseData = localControlPointManagerProxy.ckLocalBranch()->thisPhaseData;
-  const int phase_id = localControlPointManagerProxy.ckLocalBranch()->phase_id;
+  instrumentedPhase &thisPhaseData = controlPointManagerProxy.ckLocalBranch()->thisPhaseData;
+  const int phase_id = controlPointManagerProxy.ckLocalBranch()->phase_id;
 
   int result;
   if(valueShouldBeProvidedByOptimizer()){
@@ -1599,123 +1207,19 @@ int controlPoint(const char *name, std::vector<int>& values){
 void controlPointPriorityArray(const char *name, CProxy_ArrayBase &arraybase){
   CkGroupID aid = arraybase.ckGetArrayID();
   int groupIdx = aid.idx;
-  localControlPointManagerProxy.ckLocalBranch()->associatePriorityArray(name, groupIdx);
+  controlPointManagerProxy.ckLocalBranch()->associatePriorityArray(name, groupIdx);
   //  CkPrintf("Associating control point \"%s\" with array id=%d\n", name, groupIdx );
 }
 
 
 /// Inform the control point framework that a named control point affects the priorities of some entry method  
 void controlPointPriorityEntry(const char *name, int idx){
-  localControlPointManagerProxy.ckLocalBranch()->associatePriorityEntry(name, idx);
+  controlPointManagerProxy.ckLocalBranch()->associatePriorityEntry(name, idx);
   //  CkPrintf("Associating control point \"%s\" with EP id=%d\n", name, idx);
 }
 
 
 
-
-
-
-/// The index in the global array for my top row  
-int redistributor2D::top_data_idx(){ 
-  return (data_height * thisIndex.y) / y_chares; 
-} 
-int redistributor2D::bottom_data_idx(){ 
-  return ((data_height * (thisIndex.y+1)) / y_chares) - 1; 
-} 
-int redistributor2D::left_data_idx(){ 
-  return (data_width * thisIndex.x) / x_chares; 
-} 
-int redistributor2D::right_data_idx(){ 
-  return ((data_width * (thisIndex.x+1)) / x_chares) - 1; 
-} 
-int redistributor2D::top_neighbor(){ 
-  return (thisIndex.y + y_chares - 1) % y_chares; 
-}  
-   
-int redistributor2D::bottom_neighbor(){ 
-  return (thisIndex.y + 1) % y_chares; 
-} 
-   
-int redistributor2D::left_neighbor(){ 
-  return (thisIndex.x + x_chares - 1) % x_chares; 
-} 
-int redistributor2D::right_neighbor(){ 
-  return (thisIndex.x + 1) % x_chares; 
-} 
-  
-  
-/// the width of the non-ghost part of the local partition 
-int redistributor2D::mywidth(){ 
-  return right_data_idx() - left_data_idx() + 1; 
-} 
-   
-   
-/// the height of the non-ghost part of the local partition 
-int redistributor2D::myheight(){ 
-  return bottom_data_idx() - top_data_idx() + 1; 
-} 
-
-
-
-
-
-
-
-
-
-
-
-
-#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
-
-
-/// Inform control point framework that the just executed entry method is a terminal one. This is used to maintain the maximum known critical path .
-void registerTerminalEntryMethod(){
-  localControlPointManagerProxy.ckLocalBranch()->registerTerminalPath(currentlyExecutingMsg->pathHistory);
-}
-
-void printPECriticalPath(){
-  localControlPointManagerProxy.ckLocalBranch()->printTerminalPath();
-}
-
-void resetPECriticalPath(){
-  localControlPointManagerProxy.ckLocalBranch()->resetTerminalPath();
-}
-
-
-
-
-
-/// A debugging routine that outputs critical path info as user events.
-void  saveCriticalPathAsUserEvent(){
-  if(currentlyExecutingMsg==NULL){
-    traceUserEvent(5000);
-  } else if(currentlyExecutingMsg->pathHistory.getTotalTime() > 0.0){
-    //traceUserEvent(5020);
-
-    char *note = new char[4096];
-    currentlyExecutingMsg->pathHistory.printHTMLToString(note);
-    traceUserSuppliedNote(note); // stores a copy of the string
-    delete[] note;
-
-  } else {
-    traceUserEvent(5010);
-  }
-
-  
-
-  
-}
-
-
-#endif
-
-
 /*! @} */
 
 
index 76f067303fa08ec9fef69168cad3e2b5eb7804c8..e054f7da1bf74fcfbd78291ae214f86584f1af1b 100644 (file)
@@ -1,12 +1,30 @@
 module ControlPoints {
 
-  readonly CProxy_controlPointManager localControlPointManagerProxy;
+  readonly CProxy_controlPointManager controlPointManagerProxy;
   readonly int random_seed;
+  readonly long controlPointSamplePeriod;
+
 
 
   initproc void registerIdleTimeReduction(void);       
+  initproc void initializeCriticalPath(void);  
+
+
+  message pathInformationMsg { 
+        PathHistoryTableEntry history[];
+  };
 
 
+ message controlPointMsg { 
+        char data[];
+ };
+
+
+ message redistributor2DMsg {  
+       double data[]; 
+ }; 
+
   mainchare controlPointMain {
     entry controlPointMain(CkArgMsg*);
   };
@@ -22,26 +40,16 @@ module ControlPoints {
     entry void requestIdleTime(CkCallback cb);
     entry void gatherIdleTime(CkReductionMsg *msg);
 
-    entry void registerTerminalPath(PathHistory &path);
-
- }   
-
-
-
-
-
- message controlPointMsg { 
-        char data[];
- };
+//    entry void registerTerminalPath(PathHistory &path);
 
 
+     entry void traceCriticalPathBack(pathInformationMsg *msg);
+     entry void broadcastCriticalPathResult(pathInformationMsg *msg);
+     entry void criticalPathDone(CkReductionMsg *msg);
 
+ }   
 
 
- message redistributor2DMsg {  
-       double data[]; 
- }; 
  
   array [2D] redistributor2D {
    entry redistributor2D(void);
index 2b1572f34cba90c5a38d149faa383f82d99b5cae..f537c5096c5e22e5daf9e21836b14f42f8bbd0a1 100644 (file)
 #include <cmath>
 #include "ControlPoints.decl.h"
 
-#include<pup_stl.h>
+#include <pup_stl.h>
+#include <string>
+#include <set>
+#include <cmath>
+#include <math.h>
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <sstream>
+#include <map>
+#include <set>
+#include <vector>
+#include <utility>
+#include <limits>
+#include <float.h>
+
+#include "LBDatabase.h"
+#include "pathHistory.h"
+#include "arrayRedistributor.h"
 
+using namespace std;
 
 
 /**
  *   @{
  */
 
-
 #define DEBUG 0
 
+/* readonly */ extern CProxy_controlPointManager controlPointManagerProxy;
+/* readonly */ extern int random_seed;
+/* readonly */ extern long controlPointSamplePeriod;
+
+
+
 void registerGranularityChangeCallback(CkCallback cb, bool frameworkShouldAdvancePhase);
 void registerControlPointTiming(double time);
 
@@ -56,8 +80,7 @@ void controlPointPriorityArray(const char *name, CProxy_ArrayBase &arraybase);
 void controlPointPriorityEntry(const char *name, int idx);
 
 
-/// A debugging routine that outputs critical path info as user events.
-void  saveCriticalPathAsUserEvent();
+
 
 /// The application specifies that it is ready to proceed to a new set of control point values.
 /// This should be called after registerControlPointTiming()
@@ -65,21 +88,6 @@ void  saveCriticalPathAsUserEvent();
 void gotoNextPhase();
 
 
-/// Integer Maximum
-static int maxi(int a, int b){
-  if(a>b)
-    return a;
-  else
-    return b;
-}
-
-/// Integer Minimum
-static int mini(int a, int b){
-  if(a<b)
-    return a;
-  else
-    return b;
-}
 
 
 /// A message used for signaling changes in control point values
@@ -91,594 +99,529 @@ class controlPointMsg : public CMessage_controlPointMsg {
 
 
 
-/// A message containing a chunk of a data array used when redistributing to a different set of active chares 
-class redistributor2DMsg : public CMessage_redistributor2DMsg { 
- public: 
-  int top;         
-  int left; 
-  int height;      
-  int width; 
-  int new_chare_cols; 
-  int  new_chare_rows; 
-  int which_array; 
-  double *data;
-}; 
-
-
-
-
-/// A chare group that can redistribute user data arrays. It is used by binding it to a user's Chare Array
-class redistributor2D: public CBase_redistributor2D {
- public:
 
-  std::map<int,double*> data_arrays;
-  std::map<int,int> data_arrays_sizes;
-
-  /// The array associated with this data redistribution
-  CProxyElement_ArrayElement associatedArray;
+/// A container that stores idle time statistics (min/max/avg etc.)
+class idleTimeContainer {
+public:
+  double min;
+  double avg;
+  double max;
   
-  int incoming_count;
-  std::map<int,double*> data_arrays_incoming;
-  std::map<int,int> data_arrays_incoming_sizes;
-
-  /// Is this array element active
-  bool thisElemActive;
-
- private:
-
-
-  void *fakeMemoryUsage;
-
-
-  CkCallback dataRedistributedCallback;
-
-  int x_chares; // number of active chares in x dimension
-  int y_chares; // number of active chares in y dimension
-
-  int data_width;  // The width of the global array, not the local piece
-  int data_height; // The height of the global array, not the local piece
-
-  int data_x_ghost; // The padding in the x dimension on each side of the data
-  int data_y_ghost; // The padding in the y dimension on each side of the data
+  idleTimeContainer(){
+    min = -1.0;
+    max = -1.0;
+    avg = -1.0;
+  }
+  
+  bool isValid() const{
+    return (min >= 0.0 && avg >= min && max >= avg && max <= 1.0);
+  }
+  
+  void print() const{
+    if(isValid())
+      CkPrintf("[%d] Idle Time is Min=%.2lf%% Avg=%.2lf%% Max=%.2lf%%\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);    
+    else
+      CkPrintf("[%d] Idle Time is invalid\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);
+  }
+  
+}; 
 
 
- public:
 
-  void pup(PUP::er &p) {
-    CBase_redistributor2D::pup(p);
 
-    p | data_arrays_sizes;
-    p | data_arrays_incoming_sizes;
-    p | incoming_count;
-    p | associatedArray;
-    p | thisElemActive;
+/// Stores data for a phase (a time range in which a single set of control point values is used).
+/// The data stored includes the control point values, a set of timings registered by the application, 
+/// The critical paths detected, the max memory usage, and the idle time.
+class instrumentedPhase {
+public:
+  std::map<string,int> controlPoints; // The control point values for this phase(don't vary within the phase)
+  std::vector<double> times;  // A list of times observed for iterations in this phase
 
-    p | dataRedistributedCallback;
+  std::vector<PathHistoryTableEntry> criticalPaths;
 
-    p | x_chares;
-    p | y_chares;
-    p | data_width;
-    p | data_height;
-    p | data_x_ghost;
-    p | data_y_ghost;
+  
+  int memoryUsageMB;
 
-    if(p.isPacking() && fakeMemoryUsage!=NULL)
-      free(fakeMemoryUsage);
+  idleTimeContainer idleTime;
 
-    fakeMemoryUsage = NULL;
+  instrumentedPhase(){
+    memoryUsageMB = -1;
+  }
+  
+  void clear(){
+    controlPoints.clear();
+    times.clear();
+    //    criticalPaths.clear();
+  }
 
-    ////////////////////////////////
-    // when packing, iterate through data_arrays
-    // when unpacking
+  // Provide a previously computed value, or a value from a previous run
+  bool haveValueForName(const char* name){
+    string n(name);
+    return (controlPoints.count(n)>0);
+  }
 
-    {
-      std::map<int,int>::iterator iter;
-      for(iter = data_arrays_sizes.begin(); iter != data_arrays_sizes.end(); iter++){
-       int whichArray = iter->first;
-       int arraySize = iter->second;
+  void operator=(const instrumentedPhase& p){
+    controlPoints = p.controlPoints;
+    times = p.times;
+    memoryUsageMB = p.memoryUsageMB;
+  }
 
-       //      CkPrintf("Pupping data array %d\n",whichArray);
-       p | whichArray;
 
-       if(p.isUnpacking())
-         data_arrays[whichArray] = new double[arraySize];
 
-       PUParray(p,data_arrays[whichArray] ,arraySize);
-       
-       if(p.isPacking())
-         delete[] data_arrays[whichArray];
-       
+  bool operator<(const instrumentedPhase& p){
+    CkAssert(hasSameKeysAs(p)); 
+    std::map<string,int>::iterator iter1 = controlPoints.begin();
+    std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
+    for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){
+      if(iter1->second < iter2->second){
+       return true;
       }
     }
+    return false;
+  }
 
 
-    ///////////////////////////////
-    {
-      std::map<int,int>::iterator iter;
-      for(iter = data_arrays_incoming_sizes.begin(); iter != data_arrays_incoming_sizes.end(); iter++){
-       int whichArray = iter->first;
-       int arraySize = iter->second;
-
-       //      CkPrintf("Pupping incoming array %d\n",whichArray);
-       p | whichArray;
+  // Determines if the control point values and other information exists
+  bool hasValidControlPointValues(){
+#if 0
+    std::map<string,int>::iterator iter;
+    for(iter = controlPoints.begin();iter != controlPoints.end(); iter++){
+      if(iter->second == -1){ 
+        return false; 
+      }  
+    }
+#endif
+    return true;
+  }
 
-       if(p.isUnpacking() && data_arrays_incoming_sizes[whichArray] > 0)
-         data_arrays_incoming[whichArray] = new double[arraySize];
-       
-       PUParray(p,data_arrays_incoming[whichArray],arraySize);
-       
-       if(p.isPacking())
-         delete[] data_arrays_incoming[whichArray];
-       
-      }
+  
+//   int medianCriticalPathIdx() const{
+//     // Bubble sort the critical path indices by Time
+//     int numPaths = criticalPaths.size();
+//     if(numPaths>0){
+//       int *sortedPaths = new int[numPaths];
+//       for(int i=0;i<numPaths;i++){
+//     sortedPaths[i] = i;
+//       }
+      
+//       for(int j=0;j<numPaths;j++){
+//     for(int i=0;i<numPaths-1;i++){
+//       if(criticalPaths[sortedPaths[i]].getTotalTime() < criticalPaths[sortedPaths[i+1]].getTotalTime()){
+//         // swap sortedPaths[i], sortedPaths[i+1]
+//         int tmp = sortedPaths[i+1];
+//         sortedPaths[i+1] = sortedPaths[i];
+//         sortedPaths[i] = tmp;
+//       }
+//     }
+//       }
+//       int result = sortedPaths[numPaths/2];
+//       delete[] sortedPaths;
+//       return result;
+//     } else {
+//       return 0;
+//     }
+//   }
+
+
+
+  bool operator==(const instrumentedPhase& p){
+    CkAssert(hasSameKeysAs(p));
+    std::map<string,int>::iterator iter1 = controlPoints.begin();
+    std::map<string,int>::const_iterator iter2 = p.controlPoints.begin();
+    for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){ 
+      if(iter1->second != iter2->second){ 
+        return false; 
+      }  
     }
+    return true;
+  }
 
-    //    CkPrintf("pup redistributor2D\n");
+  /// Verify the names of the control points are consistent
+  /// note: std::map stores the pairs in a sorted order based on their first component 
+  bool hasSameKeysAs(const instrumentedPhase& p){
+    
+    if(controlPoints.size() != p.controlPoints.size())
+      return false;
 
-  } 
+    std::map<string,int>::iterator iter1 = controlPoints.begin(); 
+    std::map<string,int>::const_iterator iter2 = p.controlPoints.begin(); 
 
+    for(;iter1 != controlPoints.end() && iter2 != p.controlPoints.end(); iter1++, iter2++){  
+      if(iter1->first != iter2->first)
+       return false;
+    } 
 
-  void ckJustMigrated(){
-    //   CkPrintf("redistributor element %02d %02d migrated to %d", thisIndex.x, thisIndex.y, CkMyPe());
+    return true; 
   }
 
 
-  // ------------ Some routines for computing the array bounds for this chare  ------------ 
-
-  // The index in the global array for my top row  
-  int top_data_idx();
-  int bottom_data_idx();
-  int left_data_idx();
-  int right_data_idx();
-  int top_neighbor();
-   
-  int bottom_neighbor();
-   
-  int left_neighbor();
-  int right_neighbor();
-  
-  
-  /// the width of the non-ghost part of the local partition 
-  int mywidth();
+  void addAllNames(std::set<string> names_) {
     
+    std::set<string> names = names_;
     
-  // the height of the non-ghost part of the local partition 
-  int myheight();
+    // Remove all the names that we already have
+    std::map<std::string,int>::iterator iter;
     
+    for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
+      names.erase(iter->first);
+    }
+    
+    // Add -1 values for each name we didn't find
+    std::set<std::string>::iterator iter2;
+    for(iter2 = names.begin(); iter2 != names.end(); iter2++){
+      controlPoints.insert(make_pair(*iter2,-1));
+      CkPrintf("One of the datasets was missing a value for %s, so -1 was used\n", iter2->c_str());
+    }
 
-
-  // ------------ Some routines for computing the array bounds for arbitrary chares  ------------ 
-
-  int top_data_idx(int y, int y_total){
-    return (data_height * y) / y_total;
-  }
-
-  int bottom_data_idx(int y, int y_total){
-    return ((data_height * (y+1)) / y_total) - 1;
-  }
-
-  int left_data_idx(int x, int x_total){
-    return (data_width * x) / x_total;
-  }
-
-  int right_data_idx(int x, int x_total){
-    return ((data_width * (x+1)) / x_total) - 1;
-  }
-
-
-  int top_data_idx(int y){
-    return (data_height * y) / y_chares;
   }
 
-  int bottom_data_idx(int y){
-    return ((data_height * (y+1)) / y_chares) - 1;
-  }
 
-  int left_data_idx(int x){
-    return (data_width * x) / x_chares;
-  }
 
-  int right_data_idx(int x){
-    return ((data_width * (x+1)) / x_chares) - 1;
-  }
+  void print() {
+    std::map<std::string,int>::iterator iter;
 
-  /// Return which chare array element(x index) owns the global data item i
-  int who_owns_idx_x(int i){
-    int w=0;
-    while(1){
-      if( i >= left_data_idx(w) && i <= right_data_idx(w) ){
-       return w;
-      }
-      w++;
+    if(controlPoints.size() == 0){
+      CkPrintf("no control point values found\n");
     }
+    
+    for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
+      std::string name = iter->first;
+      int val = iter->second;
+      CkPrintf("%s ---> %d\n",  name.c_str(),  val);
+    } 
+    
   }
   
-  /// Return which chare array element(y index) owns the global data item i
-  int who_owns_idx_y(int i){
-    int w=0;
-    while(1){
-      if( i >= top_data_idx(w) && i <= bottom_data_idx(w) ){
-       return w;
-      }
-      w++;
-    }
-  }
   
+};
 
 
+/// Stores and manipulate all known instrumented phases. One instance of this exists on each PE in its local controlPointManager
+class instrumentedData {
+public:
 
-  
-  // Convert a local column,row id (0 to mywidth-1, 0 to data_width-1) to the index in the padded array
-  int local_to_padded(int x, int y){
-    return (mywidth()+2*data_x_ghost)*(y+data_y_ghost)+x+data_x_ghost;
-  }
+  /// Stores all known instrumented phases(loaded from file, or from this run)
+  std::vector<instrumentedPhase> phases;
 
-  // get a data value
-  double data_local(int which, int x, int y){
-    CkAssert(local_to_padded(x,y) < data_arrays_sizes[which]);
-    return data_arrays[which][local_to_padded(x,y)];
-  }
+  /// get control point names for all phases
+  std::set<string> getNames(){
+    std::set<string> names;
+    
+    std::vector<instrumentedPhase>::iterator iter;
+    for(iter = phases.begin();iter!=phases.end();iter++) {
+      
+      std::map<string,int>::iterator iter2;
+      for(iter2 = iter->controlPoints.begin(); iter2 != iter->controlPoints.end(); iter2++){
+       names.insert(iter2->first);
+      }
+      
+    }  
+    return names;
 
+  } 
 
-  // Convert a local column id (0 to mywidth-1) to the global column id (0 to data_width-1)
-  int local_to_global_x(int x){
-    return left_data_idx() + x;
-  }
 
-  // Convert a local row id (0 to myheight-1) to the global row id (0 to data_height-1)
-  int local_to_global_y(int y){
-    return top_data_idx() + y;
+  void cleanupNames(){
+    std::set<string> names = getNames();
+    
+    std::vector<instrumentedPhase>::iterator iter;
+    for(iter = phases.begin();iter!=phases.end();iter++) {
+      iter->addAllNames(names);
+    }
   }
 
-  int global_array_width(){
-    return data_width;
-  }
 
-  int global_array_height(){
-    return data_height;
+  /// Remove one phase with invalid control point values if found
+  bool filterOutOnePhase(){
+#if 0
+    // Note: calling erase on a vector will invalidate any iterators beyond the deletion point
+    std::vector<instrumentedPhase>::iterator iter;
+    for(iter = phases.begin(); iter != phases.end(); iter++) {
+      if(! iter->hasValidControlPointValues()  || iter->times.size()==0){
+       // CkPrintf("Filtered out a phase with incomplete control point values\n");
+       phases.erase(iter);
+       return true;
+      } else {
+       //      CkPrintf("Not filtering out some phase with good control point values\n");
+      }
+    }
+#endif
+    return false;
   }
-
-  int global_array_size(){
-    return global_array_width() * global_array_height();
+  
+  /// Drop any phases that do not contain timings or control point values
+  void filterOutIncompletePhases(){
+    bool done = false;
+    while(filterOutOnePhase()){
+      // do nothing
+    }
   }
 
-  int my_array_width(){
-    return mywidth()+2*data_x_ghost;
-  }
 
-  int my_array_height(){
-    return myheight()+2*data_y_ghost;
-  }
+  string toString(){
+    ostringstream s;
 
-  // Total size of arrays including ghost layers
-  int my_array_size(){
-    return my_array_width() * my_array_height();
-  }
+    verify();
 
-  /// Create an array. If multiple arrays are needed, each should have its own index
-  template <typename t> t* createDataArray(int which=0) {
-    t* data = new t[my_array_size()];
-    data_arrays[which] = data;
-    data_arrays_sizes[which] = my_array_size();
+    filterOutIncompletePhases();
 
-    if(thisIndex.x==0 && thisIndex.y==0)  
-      CkPrintf("data_arrays_sizes[which] set to %d\n", data_arrays_sizes[which] );  
+    // HEADER:
+    s << "# HEADER:\n";
+    s << "# Data for use with Isaac Dooley's Control Point Framework\n";
+    s << string("# Number of instrumented timings in this file:\n"); 
+    s << phases.size() << "\n" ;
+    
+    if(phases.size() > 0){
+      
+      std::map<string,int> &ps = phases[0].controlPoints; 
+      std::map<string,int>::iterator cpiter;
 
+      // SCHEMA:
+      s << "# SCHEMA:\n";
+      s << "# number of named control points:\n";
+      s << ps.size() << "\n";
+      
+      for(cpiter = ps.begin(); cpiter != ps.end(); cpiter++){
+       s << cpiter->first << "\n";
+      }
+      
+      // DATA:
+      s << "# DATA:\n";
+      s << "# first field is memory usage (MB). Then there are the " << ps.size()  << " control points values, followed by one or more timings" << "\n";
+      s << "# number of control point sets: " << phases.size() << "\n";
+      std::vector<instrumentedPhase>::iterator runiter;
+      for(runiter=phases.begin();runiter!=phases.end();runiter++){
+
+       // Print the memory usage
+        s << runiter->memoryUsageMB << "    "; 
+
+       // Print the control point values
+       for(cpiter = runiter->controlPoints.begin(); cpiter != runiter->controlPoints.end(); cpiter++){ 
+         s << cpiter->second << " "; 
+       }
 
-    CkAssert(data_arrays[which] != NULL);
-#if DEBUG > 2
-    CkPrintf("Allocated array of size %d at %p\n", my_array_size(), data_arrays[which] );
-#endif
-    return data;
-  }
-  
-  template <typename t> t* getDataArray(int which=0) {
-    return data_arrays[which]; 
-  }
+       s << "     ";
 
-  /// Constructor takes in the dimensions of the array, including any desired ghost layers
-  /// The local part of the arrays will have (mywidth+x_ghosts*2)*(myheight+y_ghosts*2) elements 
-  void setInitialDimensions(int width, int height, int x_chares_, int y_chares_, int x_ghosts=0, int y_ghosts=0){
-    data_width = width;      // These values cannot change after this method is called.
-    data_height = height;
-    data_x_ghost = x_ghosts;
-    data_y_ghost = y_ghosts;
-    
-    setDimensions(x_chares_, y_chares_);
-  }
-  
+       // Print the times
+       std::vector<double>::iterator titer;
+       for(titer = runiter->times.begin(); titer != runiter->times.end(); titer++){
+         s << *titer << " ";
+       }
 
-  void setDimensions( int x_chares_, int y_chares_){
-    x_chares = x_chares_;
-    y_chares = y_chares_;
-    
-    
-    if( thisIndex.x < x_chares && thisIndex.y < y_chares ){
-      thisElemActive = true;
-    } else {
-      thisElemActive = false;
+       s << "\n";
+       
+      }
     }
+
+    return s.str();
     
   }
 
 
-  redistributor2D(){
-    incoming_count = 0;
-    fakeMemoryUsage = NULL;
+  /// Verify that all our phases of data have the same sets of control point names
+  void verify(){
+    if(phases.size() > 1){
+      instrumentedPhase & firstpoint = phases[0];
+      std::vector<instrumentedPhase>::iterator iter;
+      for(iter = phases.begin();iter!=phases.end();iter++){
+       CkAssert( firstpoint.hasSameKeysAs(*iter));
+      }  
+    } 
   }
 
 
-  redistributor2D(CkMigrateMessage*){
-  }
+  // Find the fastest time from previous runs
+  instrumentedPhase findBest(){
+    CkAssert(phases.size()>0);
 
+    double total_time = 0.0; // total for all times
+    int total_count = 0;
 
-  void startup(){
-#if DEBUG > 3 
-   CkPrintf("redistributor 2D startup %03d,%03d\n", thisIndex.x, thisIndex.y);
+    instrumentedPhase best_phase;
+#if OLDMAXDOUBLE
+    double best_phase_avgtime = std::numeric_limits<double>::max();
+#else
+    double best_phase_avgtime = DBL_MAX;
 #endif
-    contribute();
-  }
-  
 
-  void printArrays(){
-#if DEBUG > 2
-    CkAssert(data_arrays.size()==2);
-    for(std::map<int,double*>::iterator diter = data_arrays.begin(); diter != data_arrays.end(); diter++){
-      int which_array = diter->first;
-      double *data = diter->second;
-      CkPrintf("%d,%d data_arrays[%d] = %p\n", thisIndex.x, thisIndex.y, which_array, data);
-    }
-#endif
-  }
+    int valid_phase_count = 0;
 
-  
-  // Called on all elements involved with the new granularity or containing part of the old data
-  void resizeGranules(int new_active_chare_cols, int new_active_chare_rows){
+    std::vector<instrumentedPhase>::iterator iter;
+    for(iter = phases.begin();iter!=phases.end();iter++){
+      if(iter->hasValidControlPointValues()){
+       valid_phase_count++;
 
-#if DEBUG>1
-    CkPrintf("Resize Granules called for elem %d,%d\n", thisIndex.x, thisIndex.y);     
-#endif
+       double total_for_phase = 0.0;
+       int phase_count = 0;
 
-    const bool previouslyActive = thisElemActive;
-    const int old_top = top_data_idx();
-    const int old_left = left_data_idx();
-    const int old_bottom = top_data_idx()+myheight()-1;
-    const int old_right = left_data_idx()+mywidth()-1;
-    const int old_myheight = myheight();
-    const int old_mywidth = mywidth();
-
-    setDimensions(new_active_chare_cols, new_active_chare_rows);
-    
-    const int new_mywidth = mywidth();
-    const int new_myheight = myheight();
+       // iterate over all times for this control point configuration
+       std::vector<double>::iterator titer;
+       for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
+         total_count++;
+         total_time += *titer;
+         total_for_phase += *titer;
+         phase_count ++;
+       }
 
-    // Transpose Data
-    // Assume only one new owner of my data
+       double phase_average_time = total_for_phase / (double)phase_count;
 
-    if(previouslyActive){
-     
-      // Send all my data to any blocks that will need it
-
-      int newOwnerXmin = who_owns_idx_x(old_left);
-      int newOwnerXmax = who_owns_idx_x(old_right);
-      int newOwnerYmin = who_owns_idx_y(old_top);
-      int newOwnerYmax = who_owns_idx_y(old_bottom);
-
-      for(int newx=newOwnerXmin; newx<=newOwnerXmax; newx++){
-       for(int newy=newOwnerYmin; newy<=newOwnerYmax; newy++){
-         
-         // Determine overlapping region between my data and this destination
-#if DEBUG > 2
-         CkPrintf("newy(%d)*new_myheight(%d)=%d, old_top=%d\n",newy,new_myheight,newy*new_myheight,old_top);
-#endif
-         // global range for overlapping area
-         int global_top = maxi(top_data_idx(newy),old_top);
-         int global_left = maxi(left_data_idx(newx),old_left);
-         int global_bottom = mini(bottom_data_idx(newy),old_bottom);
-         int global_right = mini(right_data_idx(newx),old_right);
-         int w = global_right-global_left+1;
-         int h = global_bottom-global_top+1;
-        
-         CkAssert(w*h>0);
-
-         int x_offset = global_left - old_left;
-         int y_offset = global_top - old_top;
-
-#if DEBUG > 2    
-         CkPrintf("w=%d h=%d x_offset=%d y_offset=%d\n", w, h, x_offset, y_offset);
-#endif
-         
-         std::map<int,double*>::iterator diter;
-         for(diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
-           
-           redistributor2DMsg* msg = new(w*h) redistributor2DMsg;  
-           //      CkPrintf("Created message msg %p\n", msg);  
-           
-           int which_array = diter->first;
-           double *t = diter->second;
-           int s = data_arrays_sizes[which_array];
-           
-           for(int j=0; j<h; j++){
-             for(int i=0; i<w; i++){           
-               CkAssert(j*w+i < w*h);
-               CkAssert((data_x_ghost*2+old_mywidth)*(j+y_offset+data_y_ghost)+(i+ x_offset+data_x_ghost) < s);
-               msg->data[j*w+i] = t[(data_x_ghost*2+old_mywidth)*(j+y_offset+data_y_ghost)+(i+ x_offset+data_x_ghost)];
-             }
-           }
-           
-           msg->top = global_top;
-           msg->left = global_left;
-           msg->height = h;
-           msg->width = w;
-           msg->new_chare_cols = new_active_chare_cols;
-           msg->new_chare_rows = new_active_chare_rows; 
-           msg->which_array = which_array;
-
-           //      CkPrintf("Sending message msg %p\n", msg);      
-           thisProxy(newx, newy).receiveTransposeData(msg);
-           
-         }
-         
+       if(phase_average_time  < best_phase_avgtime){
+         best_phase = *iter;
+         best_phase_avgtime = phase_average_time; 
        }
-       
-       
-      }
-    } 
-    
-    if(!thisElemActive){
-#if DEBUG > 2
-      CkPrintf("Element %d,%d is no longer active\n", thisIndex.x, thisIndex.y);
-#endif
 
-      // Free my arrays
-      for(std::map<int,double*>::iterator diter = data_arrays.begin(); diter != data_arrays.end(); diter++){
-       int which_array = diter->first;
-       delete data_arrays[which_array]; 
-       data_arrays[which_array] = NULL;
-       data_arrays_sizes[which_array] = 0;
       }
-      continueToNextStep();
-      
     }
-
-    int newPe = (thisIndex.y * new_active_chare_cols + thisIndex.x) % CkNumPes();
     
-    if(newPe == CkMyPe()){
-      //      CkPrintf("Keeping %02d , %02d on PE %d\n", thisIndex.x, thisIndex.y, newPe);
+    CkAssert(total_count > 0);
+
+    double avg = total_time / total_count;
+
+    if(CkMyPe() == 0){
+      CkPrintf("Best average time for a phase was %.1lf\n", best_phase_avgtime);
+      CkPrintf("Mean time for all %d times in the %d valid recorded phases was %.1lf\n", total_count, valid_phase_count, avg );
     }
-    else{
-      // CkPrintf("Migrating %02d , %02d to PE %d\n", thisIndex.x, thisIndex.y, newPe);
-      migrateMe(newPe);
+
+    // Compute standard deviation
+    double sumx=0.0;
+    for(iter = phases.begin();iter!=phases.end();iter++){
+      if(iter->hasValidControlPointValues()){
+       std::vector<double>::iterator titer;
+       for(titer = iter->times.begin(); titer != iter->times.end(); titer++){
+         sumx += (avg - *titer)*(avg - *titer);
+       } 
+      }
     }
     
-  }
-  
+    double std_dev = sqrt(sumx / total_count);
+
+    if(CkMyPe() == 0){
+      CkPrintf("Standard Deviation for previous runs was %.2lf   or %.1lf%% of mean\n", std_dev, std_dev/avg*100.0);
+      CkPrintf("The best phase average time was %.1lf%% faster than the mean\n", (avg-best_phase_avgtime)/avg*100.0);
 
-  void continueToNextStep(){
-#if DEBUG > 2
-    CkPrintf("Elem %d,%d is ready to continue\n", thisIndex.x, thisIndex.y);
-#endif
-    for(std::map<int,double*>::iterator diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
-      int which_array = diter->first;
-      double *data = diter->second;
-      CkAssert( (data==NULL && !thisElemActive) || (data!=NULL && thisElemActive) );
     }
 
+    return best_phase;
+  }
+  
+};
 
-#if USE_EXTRAMEMORY
-#error NO USE_EXTRAMEMORY ALLOWED YET
-    if(thisElemActive){
+class controlPointManager : public CBase_controlPointManager {
+public:
+  
+  char * dataFilename;
+  
+  instrumentedData allData;
+  instrumentedPhase thisPhaseData;
+  instrumentedPhase best_phase;
+  
+  pathInformationMsg *pathForUser; // A place to store the path for the user while we go about doing other things.
 
-      long totalArtificialMemory = controlPoint("Artificial Memory Usage", 100, 500);
-      long artificialMemoryPerChare = totalArtificialMemory *1024*1024 / x_chares / y_chares;
-      
-      CkPrintf("Allocating fake memory of %d MB (of the total %d MB) (xchares=%d y_chares=%d)\n", artificialMemoryPerChare/1024/1024, totalArtificialMemory, x_chares, y_chares);
-      free(fakeMemoryUsage);
-      fakeMemoryUsage = malloc(artificialMemoryPerChare);
-      CkAssert(fakeMemoryUsage != NULL);
-    } else {
-      free(fakeMemoryUsage);
-      fakeMemoryUsage = NULL;
-    }
-#endif
+  /// The lower and upper bounds for each named control point
+  std::map<string, pair<int,int> > controlPointSpace;
 
+  /// A set of named control points whose values cannot change within a single run of an application
+  std::set<string> staticControlPoints;
 
+  /// Sets of entry point ids that are affected by some named control points
+  std::map<string, std::set<int> > affectsPrioritiesEP;
+  /// Sets of entry array ids that are affected by some named control points
+  std::map<string, std::set<int> > affectsPrioritiesArray;
 
-    incoming_count = 0; // prepare for future granularity change 
-    contribute();
-  }
   
+  /// The control points to be used in the next phase. In gotoNextPhase(), these will be used
+  std::map<string,int> newControlPoints;
+  /// Whether to use newControlPoints in gotoNextPhase()
+  bool newControlPointsAvailable;
   
+  /// A user supplied callback to call when control point values are to be changed
+  CkCallback granularityCallback;
+  bool haveGranularityCallback;
+  bool frameworkShouldAdvancePhase;
+  
+  int phase_id;
 
+  bool alreadyRequestedMemoryUsage;
+  bool alreadyRequestedIdleTime;
 
 
-  void receiveTransposeData(redistributor2DMsg *msg){
-    int top_new = top_data_idx(thisIndex.y, msg->new_chare_rows);
-    int bottom_new = bottom_data_idx(thisIndex.y, msg->new_chare_rows);
-    int left_new = left_data_idx(thisIndex.x, msg->new_chare_cols);
-    int right_new = right_data_idx(thisIndex.x, msg->new_chare_cols);    
-
-    int new_height = bottom_new - top_new + 1;
-    int new_width = right_new - left_new + 1;
+#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
+  // A table of information about all the paths leading to executions of local entry methods.
+  std::map<int, PathHistoryTableEntry> pathHistoryTable;
+  int pathHistoryTableLastIdx;
+#endif
 
-    if(incoming_count == 0){
-      // Allocate new arrays 
-      std::map<int,double*>::iterator diter;
-      for(diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
-       int w = diter->first;
-       data_arrays_incoming[w] = new double[(new_width+2*data_x_ghost)*(new_height+2*data_y_ghost)];
-       data_arrays_incoming_sizes[w] = (new_width+2*data_x_ghost)*(new_height+2*data_y_ghost);
+  controlPointManager();
+     
+  ~controlPointManager();
 
-       //      CkPrintf("data_arrays_incoming_sizes[%d] set to %d\n", w, data_arrays_incoming_sizes[w] );  
 
-      }
-    }
-    
-    
-    // Copy values from the incoming array to the appropriate place in data_arrays_incoming
-    // Current top left of my new array
+  /// Loads the previous run data file
+  void loadDataFile();
 
+  /// Add the current data to allData and output it to a file
+  void writeDataFile();
 
-    double *localData = data_arrays_incoming[msg->which_array];
-    int s = data_arrays_incoming_sizes[msg->which_array];
+  /// User can register a callback that is called when application should advance to next phase
+  void setGranularityCallback(CkCallback cb, bool _frameworkShouldAdvancePhase);
 
-    //    CkPrintf("%d,%d data_arrays_incoming.size() = %d\n", thisIndex.x, thisIndex.y, data_arrays_incoming.size() );
-    //    CkPrintf("msg->which_array=%d   localData=%p   s=%d\n", msg->which_array, localData, s);
-    CkAssert(localData != NULL);
+  /// Called periodically by the runtime to handle the control points
+  /// Currently called on each PE
+  void processControlPoints();
+  
+  /// Determine if any control point is known to affect an entry method
+  bool controlPointAffectsThisEP(int ep);
+  
+  /// Determine if any control point is known to affect a chare array  
+  bool controlPointAffectsThisArray(int array);
+  
+  /// The data from the previous phase
+  instrumentedPhase *previousPhaseData();
+  
 
-    for(int j=0; j<msg->height; j++){
-      for(int i=0; i<msg->width; i++){
+  /// Called by either the application or the Control Point Framework to advance to the next phase  
+  void gotoNextPhase();
 
-       if( (msg->top+j >= top_new) && (msg->top+j <= bottom_new) && (msg->left+i >= left_new) && (msg->left+i <= right_new) ) {
-         CkAssert(j*msg->width+i<msg->height*msg->width);
-         CkAssert((msg->top+j-top_new)*new_width+(msg->left+i-left_new) < new_width*new_height);
-         CkAssert((msg->top+j-top_new)*new_width+(msg->left+i-left_new) >= 0);
-         
-         CkAssert((msg->top+j-top_new+data_y_ghost)*(new_width+2*data_x_ghost)+(msg->left+i-left_new+data_x_ghost) < s);
-         localData[(msg->top+j-top_new+data_y_ghost)*(new_width+2*data_x_ghost)+(msg->left+i-left_new+data_x_ghost)] = msg->data[j*msg->width+i];
-         incoming_count++;
-         
-       }
-       
-      }
-    }
-    
-    //    CkPrintf("Deleting message msg %p\n", msg); 
-    delete msg;
+  /// An application uses this to register an instrumented timing for this phase
+  void setTiming(double time);
+  
+  /// Entry method called on all PEs to request memory usage
+  void requestIdleTime(CkCallback cb);
+  
+  /// All processors reduce their memory usages in requestIdleTime() to this method
+  void gatherIdleTime(CkReductionMsg *msg);
+  
 
 
-    if(incoming_count == new_height*new_width*data_arrays.size()){
+  /// Entry method called on all PEs to request memory usage
+  void requestMemoryUsage(CkCallback cb);
 
-      std::map<int,double*>::iterator diter;
-      for(diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
-       int w = diter->first;
-       delete[] data_arrays[w];
-       data_arrays[w] = data_arrays_incoming[w];
-       data_arrays_sizes[w] = data_arrays_incoming_sizes[w];
-       data_arrays_incoming[w] = NULL;
-       data_arrays_incoming_sizes[w] = 0;
+  /// All processors reduce their memory usages to this method
+  void gatherMemoryUsage(CkReductionMsg *msg);
 
-       //        if(thisIndex.x==0 && thisIndex.y==0)   
-         //          CkPrintf("data_arrays_incoming_sizes[%d] set to %d\n",w, data_arrays_incoming_sizes[w] );   
 
-         //        if(thisIndex.x==0 && thisIndex.y==0) 
-         //  CkPrintf("data_arrays_sizes[%d] set to %d\n",w, data_arrays_sizes[w] ); 
+  /** Trace perform a traversal backwards over the critical path specified as a 
+      table index for the processor upon which this is called.
+      
+      The callback cb will be called with the resulting msg after the path has 
+      been traversed to its origin.  
+  */
+ void traceCriticalPathBack(pathInformationMsg *msg);
+ void broadcastCriticalPathResult(pathInformationMsg *msg);
+ void criticalPathDone(CkReductionMsg *msg);
+  
 
-      }
 
-      continueToNextStep();
-    }
-    
-  }
+  /// Inform the control point framework that a named control point affects the priorities of some array  
+  void associatePriorityArray(const char *name, int groupIdx);
+  
+  /// Inform the control point framework that a named control point affects the priority of some entry method
+  void associatePriorityEntry(const char *name, int idx);
+  
 };
 
-/** @} */
 
 
+/** @} */
 #endif
diff --git a/src/ck-cp/pathHistory.C b/src/ck-cp/pathHistory.C
new file mode 100644 (file)
index 0000000..bf77ea6
--- /dev/null
@@ -0,0 +1,274 @@
+#include <charm++.h>
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <map>
+#include <set>
+#include <vector>
+#include <utility>
+
+#include "ControlPoints.decl.h"
+#include "trace-controlPoints.h"
+#include "LBDatabase.h"
+#include "controlPoints.h"
+#include "pathHistory.h"
+#include "arrayRedistributor.h"
+#include <register.h> // for _entryTable
+
+
+/**
+ *  \addtogroup CriticalPathFramework
+ *   @{
+ *
+ */
+
+#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
+
+
+CkpvDeclare(MergeablePathHistory, currentlyExecutingPath); // The maximal incoming path for the node
+CkpvDeclare(double, timeEntryMethodStarted);
+
+void initializeCriticalPath(void){
+  CkpvInitialize(MergeablePathHistory, currentlyExecutingPath); // The maximal incoming path for the node
+  CkpvInitialize(double, timeEntryMethodStarted);
+  CkpvAccess(timeEntryMethodStarted) = 0.0;
+}
+
+void PathHistoryEnvelope::reset(){
+  totalTime = 0.0;
+  sender_history_table_idx = -1;
+}
+
+  
+void PathHistoryEnvelope::print() const {
+  CkPrintf("print() is not implemented\n");
+}
+
+/// Write a description of the path into the beginning of the provided buffer. The buffer ought to be large enough.
+
+  
+void PathHistoryEnvelope::incrementTotalTime(double time){
+  totalTime += time;
+}
+
+
+
+void PathHistoryEnvelope::setDebug100(){
+  totalTime = 100.0;   
+}
+
+
+/// Add an entry for this path history into the table, and write the corresponding information into the outgoing envelope
+int PathHistoryTableEntry::addToTableAndEnvelope(envelope *env){
+  // Add to table
+  int new_idx = addToTable();
+
+  // Fill in outgoing envelope
+  CkAssert(env != NULL);
+  env->pathHistory.set_sender_history_table_idx(new_idx);
+  env->pathHistory.setTime(local_path_time + preceding_path_time);
+
+  // Create a user event for projections
+  char *note = new char[4096];
+  sprintf(note, "addToTableAndEnvelope<br> ");
+  env->pathHistory.printHTMLToString(note+strlen(note));
+  traceUserSuppliedNote(note); // stores a copy of the string
+  delete[] note;
+  
+  return new_idx;
+}
+  
+
+/// Add an entry for this path history into the table. Returns the index in the table for it.
+int PathHistoryTableEntry::addToTable(){
+  std::map<int, PathHistoryTableEntry> &table = controlPointManagerProxy.ckLocalBranch()->pathHistoryTable;
+  int &table_last_idx = controlPointManagerProxy.ckLocalBranch()->pathHistoryTableLastIdx;
+  int new_idx = table_last_idx++;
+  table[new_idx] = *this;
+  return new_idx;
+}
+
+
+
+  
+void resetThisEntryPath(void) {
+  CkpvAccess(currentlyExecutingPath).reset();
+}
+
+
+/// A debugging routine that outputs critical path info as user events.
+void  saveCurrentPathAsUserEvent(char* prefix){
+  if(CkpvAccess(currentlyExecutingPath).getTotalTime() > 0.0){
+    //traceUserEvent(5020);
+
+    char *note = new char[4096];
+    sprintf(note, "%s<br> saveCurrentPathAsUserEvent()<br> ", prefix);
+    CkpvAccess(currentlyExecutingPath).printHTMLToString(note+strlen(note));
+    traceUserSuppliedNote(note); // stores a copy of the string
+    delete[] note;
+
+  } else {
+    traceUserEvent(5010);
+  }
+}
+
+
+void setCurrentlyExecutingPathTo100(void){
+  CkpvAccess(currentlyExecutingPath).setDebug100();
+}
+
+
+
+/// A routine for printing out information along the critical path.
+void traceCriticalPathBack(CkCallback cb){
+
+  pathInformationMsg *newmsg = new(0) pathInformationMsg;
+  newmsg->historySize = 0;
+  newmsg->cb = cb;
+  newmsg->table_idx = CkpvAccess(currentlyExecutingPath).sender_history_table_idx;
+  int pe = CkpvAccess(currentlyExecutingPath).sender_pe;
+  CkPrintf("Starting tracing of critical path from pe=%d table_idx=%d\n", pe,  CkpvAccess(currentlyExecutingPath).sender_history_table_idx);
+  CkAssert(pe < CkNumPes() && pe >= 0);
+  controlPointManagerProxy[pe].traceCriticalPathBack(newmsg);
+}
+
+
+
+// void  printPathInMsg(void* msg){
+//   envelope *env = UsrToEnv(msg);
+//   env->printPath();
+// }
+
+
+
+/// A debugging routine that prints the number of EPs for the program, and the size of the envelope's path fields
+void  printEPInfo(){
+  CkPrintf("printEPInfo():\n");
+  CkPrintf("There are %d EPs\n", (int)_entryTable.size());
+  for (int epIdx=0;epIdx<_entryTable.size();epIdx++)
+    CkPrintf("EP %d is %s\n", epIdx, _entryTable[epIdx]->name);
+}
+
+
+
+
+/// Save information about the critical path contained in the message that is about to execute.
+void criticalPath_start(envelope * env){ 
+#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
+#if DEBUG
+  CkPrintf("criticalPath_start(envelope * env) srcpe=%d sender table idx=%d  time=%lf\n", env->getSrcPe(),  env->pathHistory.get_sender_history_table_idx(), env->pathHistory.getTotalTime() );
+#endif
+
+  CkpvAccess(currentlyExecutingPath).sender_pe = env->getSrcPe();
+  CkpvAccess(currentlyExecutingPath).sender_history_table_idx = env->pathHistory.get_sender_history_table_idx();
+  CkpvAccess(currentlyExecutingPath).preceding_path_time = env->pathHistory.getTotalTime();
+
+  CkpvAccess(currentlyExecutingPath).sanity_check();
+  
+  CkpvAccess(currentlyExecutingPath).local_ep  = -1;
+  CkpvAccess(currentlyExecutingPath).local_arr = -1;
+
+  double now = CmiWallTimer();
+  CkpvAccess(currentlyExecutingPath).timeEntryMethodStarted = now;
+  CkpvAccess(timeEntryMethodStarted) = now;
+
+  switch(env->getMsgtype()) {
+  case ForArrayEltMsg:
+    //    CkPrintf("Critical Path Detection handling a ForArrayEltMsg\n");    
+    CkpvAccess(currentlyExecutingPath).local_ep = env->getsetArrayEp();
+    CkpvAccess(currentlyExecutingPath).local_arr = env->getArrayMgrIdx();
+    
+    break;
+
+  case ForNodeBocMsg:
+    //CkPrintf("Critical Path Detection handling a ForNodeBocMsg\n");    
+    break;
+
+  case ForChareMsg:
+    //CkPrintf("Critical Path Detection handling a ForChareMsg\n");        
+    break;
+
+  case ForBocMsg:
+    //CkPrintf("Critical Path Detection handling a ForBocMsg\n");    
+    break;
+
+  case ArrayEltInitMsg:
+    // Don't do anything special with these
+    break;
+
+  default:
+    CkPrintf("Critical Path Detection can't yet handle message type %d\n", (int)env->getMsgtype());
+  }
+  
+  
+
+  saveCurrentPathAsUserEvent("criticalPath_start()<br> ");
+
+
+#endif
+}
+
+
+/// Modify the envelope of a message that is being sent for critical path detection and store an entry in a table on this PE.
+void criticalPath_send(envelope * sendingEnv){
+#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
+#if DEBUG
+  CkPrintf("criticalPath_send(envelope * sendingEnv)\n");
+#endif
+  double now = CmiWallTimer();
+  PathHistoryTableEntry entry(CkpvAccess(currentlyExecutingPath), CkpvAccess(timeEntryMethodStarted), now);
+  entry.addToTableAndEnvelope(sendingEnv);
+  
+#endif
+}
+
+
+/// Handle the end of the entry method in the critical path detection processes. This should create a forward dependency for the object.
+void criticalPath_end(){
+#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
+  saveCurrentPathAsUserEvent("criticalPath_end()<br> ");
+
+  CkpvAccess(currentlyExecutingPath).reset();
+
+#if DEBUG
+  CkPrintf("criticalPath_end()\n");
+#endif
+
+#endif
+}
+
+
+
+/// Split an entry method invocation into multiple logical tasks for the critical path analysis.
+/// SDAG doen's break up the code in useful ways, so I'll make it add calls to this in the generated code.
+void criticalPath_split(){
+  saveCurrentPathAsUserEvent("criticalPath_split()<br> ");
+
+  // save an entry in the table
+  double now = CmiWallTimer();
+  PathHistoryTableEntry entry(CkpvAccess(currentlyExecutingPath), now-CkpvAccess(timeEntryMethodStarted) );
+  int tableidx = entry.addToTable();
+
+  // end the old task
+
+  
+  // start the new task
+  CkpvAccess(currentlyExecutingPath).sender_pe = CkMyPe();
+  CkpvAccess(currentlyExecutingPath).sender_history_table_idx = tableidx;
+  CkpvAccess(currentlyExecutingPath).preceding_path_time = entry.getTotalTime();
+  CkpvAccess(currentlyExecutingPath).timeEntryMethodStarted = now;
+  CkpvAccess(timeEntryMethodStarted) = now;
+}
+
+
+
+
+#endif
+
+
+
+
+
+/*! @} */
+
diff --git a/src/ck-cp/pathHistory.h b/src/ck-cp/pathHistory.h
new file mode 100644 (file)
index 0000000..d4f0e42
--- /dev/null
@@ -0,0 +1,302 @@
+
+/**     @defgroup CriticalPathFramework Critical Path Detection
+
+       Usable for determining the critical paths in Charm++, Charisma, and SDAG programs. 
+*/
+
+/** 
+    A system for exposing application and runtime "control points" 
+    to the dynamic optimization framework.
+
+    @addtogroup CriticalPathFramework
+    @{
+
+*/
+#ifndef __PATH_HISTORY_H__
+#define __PATH_HISTORY_H__
+
+#include <vector>
+#include <map>
+#include <cmath>
+#include "ControlPoints.decl.h"
+#include "envelope.h"
+
+#include<pup_stl.h>
+
+#define DEBUG 0
+
+
+
+#ifdef USE_CRITICAL_PATH_HEADER_ARRAY
+
+
+/**
+   Augments the PathHistory in the envelope with the other necessary information
+   from the envelope. These should be derived from an incoming message.
+
+   These objects can then be used for storing of information about a path 
+   outside of the incoming message's header. 
+
+   These are used for:
+      1) information about the currently executing message
+      2) combining the maximum paths along a reduction
+      3) combining multiple paths in Charisma and SDAG programs
+
+   This can be constructed from an envelope.
+*/
+
+void initializeCriticalPath(void);
+
+
+//#warning "Usinge MergeablePathHistory in pathHistory.h"
+class MergeablePathHistory {
+ public:
+  double timeEntryMethodStarted;
+
+  double preceding_path_time;
+
+  int sender_pe;  // for traversing back over the PAG
+  int sender_history_table_idx; // for traversing back over the PAG
+  
+  int local_ep;  // The locally executing EP
+  int local_arr; // The locally executing array
+
+ MergeablePathHistory(const envelope *env) 
+   : sender_pe(env->getSrcPe()), 
+    sender_history_table_idx(env->pathHistory.get_sender_history_table_idx()), 
+    local_ep(env->getEpIdx()),
+    local_arr(env->getArrayMgrIdx()),
+    preceding_path_time(env->pathHistory.getTime()),
+    timeEntryMethodStarted(0.0)
+      {
+       // No body
+      }
+
+
+  MergeablePathHistory() {
+    reset();
+  }
+  
+  void reset(){
+    sender_pe = -1; 
+    sender_history_table_idx = -1; 
+    local_ep = -1;
+    preceding_path_time = 0.0;
+    timeEntryMethodStarted = 0.0;
+  }
+  
+  void sanity_check(){
+    if(sender_history_table_idx > -1){ 
+      CkAssert(sender_pe < CkNumPes()); 
+      CkAssert(sender_pe >= -1);
+    }
+/*     CkAssert(sender_history_table_idx < 100000); */
+/*     CkAssert(sender_history_table_idx >= 0); */
+   
+/*     CkAssert(local_ep < 500); */
+/*     CkAssert(local_ep >= 0); */
+
+  }
+
+  void updateMax(const MergeablePathHistory& other){
+    if(preceding_path_time < other.preceding_path_time)
+      *this = other;
+  }
+
+
+  void updateMax(const envelope* env){
+    updateMax(MergeablePathHistory(env));
+  }
+  
+  double getTotalTime() const{
+    return preceding_path_time;
+  }
+
+  /// Write a description of the path into the beginning of the provided buffer. The buffer ought to be large enough.
+  void printHTMLToString(char* buf) const{
+    buf[0] = '\0';
+    sprintf(buf+strlen(buf), "MergeablePathHistory time=%lf send pe=%d idx=%d timeEntryStarted=%lf", (double)preceding_path_time, (int)sender_pe, (int)sender_history_table_idx, (double)timeEntryMethodStarted);
+  }
+
+  void setDebug100(){
+    preceding_path_time = 100.0;
+    CkPrintf("Setting path length to 100\n");
+  }
+
+
+};
+
+
+
+
+/** 
+    Stores information about the critical path in the table on each PE. 
+    The PAG can be constructed by merging these together.
+
+    These can be constructed from a MergeablePathHistory, and are assumed to refer to the local PE.
+*/
+
+class PathHistoryTableEntry {
+  
+ public:
+  int sender_pe;
+  int sender_history_table_idx;
+  int local_ep;
+  int local_arr;
+  int local_pe;
+
+ private:
+  double start_time;
+  double local_path_time;
+  double preceding_path_time;
+
+ public:
+  
+ PathHistoryTableEntry() 
+   : sender_pe(-1), 
+    sender_history_table_idx(-1), 
+    start_time(0.0),
+    local_path_time(0.0), 
+    preceding_path_time(0.0),     
+    local_ep(-1),
+    local_arr(-1),
+    local_pe(CkMyPe())
+      {
+       // No body
+      }
+  
+
+  /// Construct an entry for the table assuming the start time in input path is correct
+ PathHistoryTableEntry(const MergeablePathHistory& p, double localContribution = 0.0)
+    : sender_pe(p.sender_pe), 
+    sender_history_table_idx(p.sender_history_table_idx), 
+    local_path_time(localContribution), 
+    preceding_path_time(p.preceding_path_time),
+    start_time(p.timeEntryMethodStarted),
+    local_ep(p.local_ep),
+    local_arr(p.local_arr),
+    local_pe(CkMyPe())
+      {
+       // No body
+      }
+
+  /// Construct an entry with the actual start and end times for it.
+  PathHistoryTableEntry(const MergeablePathHistory& p, double start, double finish)
+    : sender_pe(p.sender_pe), 
+    sender_history_table_idx(p.sender_history_table_idx), 
+    local_path_time(finish-start), 
+    preceding_path_time(p.preceding_path_time),
+    start_time(start),
+    local_ep(p.local_ep),
+    local_arr(p.local_arr),
+    local_pe(CkMyPe())
+      {
+       // No body
+      }
+
+  void printInfo(char *prefix = ""){
+    CkPrintf("%s [sender pe=%d table idx=%d] [local path contribution=%lf ep=%d] [Time= %lf + %lf]\n", prefix,  
+            sender_pe, sender_history_table_idx, local_path_time, local_ep, preceding_path_time, local_path_time);  
+  }
+
+
+  /// Add an entry for this path history into the table, and write the corresponding information into the provided header
+  int addToTableAndEnvelope(envelope *env);
+  
+  /// Add an entry for this path history into the table. Returns the new index in the table.
+  int addToTable();
+  
+  /// Return the length of the path up to and including this entry
+  double getTotalTime(){
+    return local_path_time + preceding_path_time;
+  }
+
+  double get_start_time() const {return start_time;}
+  double get_local_path_time() const {return local_path_time;}
+  double get_preceding_path_time() const {return preceding_path_time;}
+
+};
+
+
+/// A debugging routine that outputs critical path info as Projections user events.
+void  saveCurrentPathAsUserEvent(char* prefix="");
+
+/// A debugging helper routine that sets the values in the currently executing message's path to 100
+void setCurrentlyExecutingPathTo100(void);
+
+/// A debugging routine that outputs critical path info as Projections user events.
+void  printPathInMsg(void* msg);
+
+/// A debugging routine that outputs critical path info as Projections user events.
+void  printEPInfo();
+
+
+/// A routine for printing out information along the critical path.
+void traceCriticalPathBack(CkCallback cb);
+
+
+
+/// A message containing information about a path of entry method invocations. This contains an array of PathHistoryTableEntry objects
+class pathInformationMsg : public CMessage_pathInformationMsg {
+ public:
+  PathHistoryTableEntry *history;
+  int historySize;
+  CkCallback cb;
+  int table_idx;
+
+  void printme(){
+    CkPrintf("Path contains %d entries\n", historySize);
+    for(int i=historySize-1;i>=0;i--){
+      CkPrintf("\tPath Step %d: local_path_time=%lf arr=%d ep=%d starttime=%lf preceding path time=%lf pe=%d\n",i, history[i].get_local_path_time(),  history[i].local_arr, history[i].local_ep, history[i].get_start_time(), history[i].get_preceding_path_time(), history[i].local_pe);
+    }
+    
+  }
+  
+};
+#endif
+
+CkpvExtern(MergeablePathHistory, currentlyExecutingPath);
+CkpvExtern(double, timeEntryMethodStarted);
+
+// Reset the counts for the currently executing message. Cut the incoming path
+extern void resetThisEntryPath();
+
+extern void criticalPath_start(envelope * env); 
+extern void criticalPath_send(envelope * sendingEnv);
+extern void criticalPath_end();
+extern void criticalPath_split(); 
+
+
+
+
+/// Wrappers for Charm++ programs to use to annotate their program dependencies
+
+/// Declare a MergeablePathHistory variable, whose name is mangled with the supplied parameter
+#define MERGE_PATH_DECLARE(x) MergeablePathHistory merge_path_##x
+
+/// Reset the merge_path variable
+#define MERGE_PATH_RESET(x) merge_path_##x.reset()
+
+/// Take the maximal path from the stored merge_path variable and the currently executing path. Put the result in currently executing path.
+#define MERGE_PATH_MAX(x) merge_path_##x.updateMax(CkpvAccess(currentlyExecutingPath)); CkpvAccess(currentlyExecutingPath) = merge_path_##x; 
+
+
+
+/// Declare a dynamic MergeablePathHistory variable. Each object can have many merge points stored in this single DECLARE.
+#define MERGE_PATH_DECLARE_D(x) std::map<int,MergeablePathHistory> merge_path_D_##x
+
+/// Reset the merge_path variable
+#define MERGE_PATH_RESET_D(x,n) merge_path_D_##x[n].reset()
+
+/// Delete the merge_path variable
+#define MERGE_PATH_DELETE_D(x,n) merge_path_D_##x.erase(n)
+
+/// Delete all entries in the merge_path variable
+#define MERGE_PATH_DELETE_ALL_D(x) merge_path_D_##x.clear()
+
+/// Take the maximal path from the stored merge_path variable and the currently executing path. Put the result in currently executing path.
+#define MERGE_PATH_MAX_D(x,n) merge_path_D_##x[n].updateMax(CkpvAccess(currentlyExecutingPath)); CkpvAccess(currentlyExecutingPath) = merge_path_D_##x[n]; 
+
+
+/** @} */
+#endif