Home Research Papers Posters Manuals Talks Download People Help Internal

ck-cp/controlPoints.h

Go to the documentation of this file.

#ifndef __CONTROLPOINTS_H__
#define __CONTROLPOINTS_H__

#include "conv-config.h"

#if CMK_WITH_CONTROLPOINT


#include "ControlPoints.decl.h"

#include <vector>
#include <map>
#include <cmath>
#include <pup_stl.h>
#include <string>
#include <set>
#include <cmath>
#include <math.h>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <sstream>
#include <set>
#include <vector>
#include <utility>
#include <limits>
#include <algorithm>
#include <float.h>
#include <charm-api.h>

#include "LBDatabase.h"
#include "arrayRedistributor.h"
#include "pathHistory.h" 


#include <cp_effects.h>

#define DEBUG 0

/* readonly */ extern CProxy_controlPointManager controlPointManagerProxy;
/* readonly */ extern int random_seed;
/* readonly */ extern long controlPointSamplePeriod;
/* readonly */ extern int whichTuningScheme;
/* readonly */ extern bool writeDataFileAtShutdown;
/* readonly */ extern bool shouldFilterOutputData;
/* readonly */ extern bool loadDataFileAtStartup;
/* readonly */ extern char CPDataFilename[512];



void registerCPChangeCallback(CkCallback cb, bool frameworkShouldAdvancePhase);

void setFrameworkAdvancePhase(bool frameworkShouldAdvancePhase);


void registerControlPointTiming(double time);

void controlPointTimingStamp();
FLINKAGE void FTN_NAME(CONTROLPOINTTIMINGSTAMP,controlpointtimingstamp)();


void gotoNextPhase();
FLINKAGE void FTN_NAME(GOTONEXTPHASE,gotonextphase)();

int controlPoint2Pow(const char *name, int c1, int c2);

int controlPoint(const char *name, int lb, int ub);

FLINKAGE int FTN_NAME(CONTROLPOINT,controlpoint)(CMK_TYPEDEF_INT4 *lb, CMK_TYPEDEF_INT4 *ub);


int controlPoint(const char *name, std::vector<int>& values);

void ControlPointWriteOutputToDisk();

void gotoNextPhase();




class controlPointMsg : public CMessage_controlPointMsg {
 public:
  char *data;
};





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);
  }
  
}; 


class overheadContainer {
public:
  double min;
  double avg;
  double max;
  
  overheadContainer(){
    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] Overhead Time is Min=%.2lf%% Avg=%.2lf%% Max=%.2lf%%\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);    
    else
      CkPrintf("[%d] Overhead Time is invalid\n", CkMyPe(), min*100.0, avg*100.0, max*100.0);
  }
  
}; 



class instrumentedPhase {
public:
  std::map<std::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

#if USE_CRITICAL_PATH_HEADER_ARRAY
  std::vector<PathHistoryTableEntry> criticalPaths;
#endif
  
  double memoryUsageMB;

  idleTimeContainer idleTime;
  overheadContainer overheadTime;


  double bytesPerInvoke;

  double grainSize;


  instrumentedPhase(){
    memoryUsageMB = -1.0;
    grainSize = -1.0;
    bytesPerInvoke = -1.0;
  }
  
  void clear(){
    controlPoints.clear();
    times.clear();
    memoryUsageMB = -1.0;
    grainSize = -1.0;
    bytesPerInvoke = -1.0;
    //    criticalPaths.clear();
  }

  // Provide a previously computed value, or a value from a previous run
  bool haveValueForName(const char* name){
    std::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<std::string,int>::iterator iter1 = controlPoints.begin();
    std::map<std::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<std::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<std::string,int>::iterator iter1 = controlPoints.begin();
    std::map<std::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;
  }

  bool hasSameKeysAs(const instrumentedPhase& p){
    
    if(controlPoints.size() != p.controlPoints.size())
      return false;

    std::map<std::string,int>::iterator iter1 = controlPoints.begin(); 
    std::map<std::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<std::string> names_) {
    
    std::set<std::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(std::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() const {
    std::map<std::string,int>::const_iterator iter;

    if(controlPoints.size() == 0){
      CkPrintf("no control point values found\n");
    }
    
    for(iter = controlPoints.begin(); iter != controlPoints.end(); iter++){
      const std::string name = iter->first;
      const int val = iter->second;
      CkPrintf("%s ---> %d\n",  name.c_str(),  val);
    } 
    
  }

  double medianTime(){
    std::vector<double> sortedTimes = times;
    std::sort(sortedTimes.begin(), sortedTimes.end());
    if(sortedTimes.size()>0){
        return sortedTimes[sortedTimes.size() / 2];
    } else {
        CkAbort("Cannot compute medianTime for empty sortedTimes vector");
        return -1;
    }
  }

  
};


class instrumentedData {
public:

  std::vector<instrumentedPhase*> phases;

  std::set<std::string> getNames(){
    std::set<std::string> names;
    
    std::vector<instrumentedPhase*>::iterator iter;
    for(iter = phases.begin();iter!=phases.end();iter++) {
      
      std::map<std::string,int>::iterator iter2;
      for(iter2 = (*iter)->controlPoints.begin(); iter2 != (*iter)->controlPoints.end(); iter2++){
    names.insert(iter2->first);
      }
      
    }  
    return names;

  } 


  void cleanupNames(){
    std::set<std::string> names = getNames();
    
    std::vector<instrumentedPhase*>::iterator iter;
    for(iter = phases.begin();iter!=phases.end();iter++) {
      (*iter)->addAllNames(names);
    }
  }


  bool filterOutOnePhase(){
#if 1
    // 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;
  }
  
  void filterOutIncompletePhases(){
    bool done = false;
    while(filterOutOnePhase()){
      // do nothing
    }
  }


  std::string toString(){
    std::ostringstream s;

    // HEADER:
    s << "# HEADER:\n";
    s << "# Data for use with Isaac Dooley's Control Point Framework\n";
    s << "# Number of instrumented timings in this file:\n"; 
    s << phases.size() << "\n" ;
    
    if(phases.size() > 0){
      
      std::map<std::string,int> &ps = phases[0]->controlPoints; 
      std::map<std::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 << "# There are " << ps.size()  << " control points\n";
      s << "# number of recorded phases: " << phases.size() << "\n";
      
      s << "# Memory (MB)\tIdle Min\tIdle Avg\tIdle Max\tOverhead Min\tOverhead Avg\tOverhead Max\tByte Per Invoke\tGrain Size\t";
      for(cpiter = ps.begin(); cpiter != ps.end(); cpiter++){
    s << cpiter->first << "\t";
      }
      s << "Median Timing\tTimings\n";
      
   
      std::vector<instrumentedPhase*>::iterator runiter;
      for(runiter=phases.begin();runiter!=phases.end();runiter++){
    
    // Print the memory usage
    s << (*runiter)->memoryUsageMB << "\t"; 

    s << (*runiter)->idleTime.min << "\t" << (*runiter)->idleTime.avg << "\t" << (*runiter)->idleTime.max << "\t";
    s << (*runiter)->overheadTime.min << "\t" << (*runiter)->overheadTime.avg << "\t" << (*runiter)->overheadTime.max << "\t";


    s << (*runiter)->bytesPerInvoke << "\t";

    s << (*runiter)->grainSize << "\t";


    // Print the control point values
    for(cpiter = (*runiter)->controlPoints.begin(); cpiter != (*runiter)->controlPoints.end(); cpiter++){ 
      s << cpiter->second << "\t"; 
    }

    // Print the median time
    if((*runiter)->times.size()>0){
        s << (*runiter)->medianTime() << "\t";
    } else {
        s << "-1\t";
    }

    // 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();
    
  }


  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()>1);

    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;
  }
  
};


class simplexScheme {
private:
    typedef enum simplexStateEnumT {beginning, reflecting, expanding, contracting, doneExpanding, stillContracting}  simplexStateT;

    std::set<int> simplexIndices;
    simplexStateT simplexState;

    double alpha;
    // Contraction coefficient
    double beta;
    // Expansion coefficient
    double gamma;


    int firstSimplexPhase;

    // Worst performing point in the simplex
    int worstPhase;
    double worstTime;
    std::vector<double> worst; // p_h

    // Centroid of remaining points in the simplex
    std::vector<double> centroid;

    // Best performing point in the simplex
    int bestPhase;
    double bestTime;
    std::vector<double> best;

    // P*
    std::vector<double> P;
    int pPhase;

    // P**
    std::vector<double> P2;
    int p2Phase;

    // A set of phases for which (P_i+P_l)/2 ought to be evaluated
    std::set<int> stillMustContractList;

    bool useBestKnown;

    void computeCentroidBestWorst(std::map<std::string, std::pair<int,int> > & controlPointSpace, std::map<std::string,int> &newControlPoints, const int phase_id, instrumentedData &allData);

    void doReflection(std::map<std::string, std::pair<int,int> > & controlPointSpace, std::map<std::string,int> &newControlPoints, const int phase_id, instrumentedData &allData);
    void doExpansion(std::map<std::string, std::pair<int,int> > & controlPointSpace, std::map<std::string,int> &newControlPoints, const int phase_id, instrumentedData &allData);
    void doContraction(std::map<std::string, std::pair<int,int> > & controlPointSpace, std::map<std::string,int> &newControlPoints, const int phase_id, instrumentedData &allData);


    std::vector<double> pointCoords(instrumentedData &allData, int i);

        inline int keepInRange(int v, int lb, int ub){
            if(v < lb)
                return lb;
            if(v > ub)
                return ub;
            return v;
        }

        void printSimplex(instrumentedData &allData){
            char s[2048];
            s[0] = '\0';
            for(std::set<int>::iterator iter = simplexIndices.begin(); iter != simplexIndices.end(); ++iter){
                sprintf(s+strlen(s), "%d: ", *iter);

                for(std::map<std::string,int>::iterator citer = allData.phases[*iter]->controlPoints.begin(); citer != allData.phases[*iter]->controlPoints.end(); ++citer){
                    sprintf(s+strlen(s), " %d", citer->second);
                }

                sprintf(s+strlen(s), "\n");
            }
            CkPrintf("Current simplex is:\n%s\n", s);
        }

public:

    simplexScheme() :
        simplexState(beginning),
        alpha(1.0), beta(0.5), gamma(2.0),
        firstSimplexPhase(-1),
        useBestKnown(false)
    {
        // Make sure the coefficients are reasonable
        CkAssert(alpha >= 0);
        CkAssert(beta >= 0.0 && beta <= 1.0);
        CkAssert(gamma >= 1.0);
    }

    void adapt(std::map<std::string, std::pair<int,int> > & controlPointSpace, std::map<std::string,int> &newControlPoints, const int phase_id, instrumentedData &allData);

};



class controlPointManager : public CBase_controlPointManager {
public:
    
  instrumentedData allData;
  
  std::map<std::string, std::pair<int,int> > controlPointSpace;

  std::set<std::string> staticControlPoints;

  std::map<std::string, std::set<int> > affectsPrioritiesEP;
  std::map<std::string, std::set<int> > affectsPrioritiesArray;

  
  std::map<std::string,int> newControlPoints;
  int generatedPlanForStep;

  simplexScheme s;

  
  CkCallback controlPointChangeCallback;
  bool haveControlPointChangeCallback;
  bool frameworkShouldAdvancePhase;
  
  int phase_id;

  bool alreadyRequestedMemoryUsage;
  bool alreadyRequestedIdleTime;
  bool alreadyRequestedAll;

  bool exitWhenReady;


  controlPointManager();
     
  ~controlPointManager();

  void pup(PUP::er &p);
  
 controlPointManager(CkMigrateMessage* m) : CBase_controlPointManager(m) {
    // CkPrintf("Warning: control point framework likely won't work after checkpoint restart, please fix this problem if you need the functionality.");
  }


  void loadDataFile();

  void writeDataFile();

  void setCPCallback(CkCallback cb, bool _frameworkShouldAdvancePhase);

  void setFrameworkAdvancePhase(bool _frameworkShouldAdvancePhase);

  void processControlPoints();
  
  bool controlPointAffectsThisEP(int ep);
  
  bool controlPointAffectsThisArray(int array);

  void generatePlan();

  instrumentedPhase *currentPhaseData();

  instrumentedPhase *previousPhaseData();

  instrumentedPhase *twoAgoPhaseData();

  void gotoNextPhase();

  void setTiming(double time);

  void checkForShutdown();

  void exitIfReady();

  void doExitNow();

  void writeOutputToDisk();


  void requestMemoryUsage(CkCallback cb);
  void gatherMemoryUsage(CkReductionMsg *msg);


  void requestIdleTime(CkCallback cb);
  void gatherIdleTime(CkReductionMsg *msg);
  

  void requestAll(CkCallback cb);
  void gatherAll(CkReductionMsg *msg);
  

/*   /// 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

#endif

---