src/SandersSpeck.cpp

Go to the documentation of this file.

// The following definitions might be exchanged for others,
// when integrating the following code into the framework.
// The code implements a greedy heuristic to loadbalance the tasks
// over cores such that the l2-norm of the load vector is minimized.
// This should also minimize the l3-norm of the load vector.
// J. Keller, July 14, 2014

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include <string>
#include <iostream>
#if DUMMY == 0
#include <pelib/SandersSpeck.hpp>
#include <pelib/AmplSolver.hpp>
#include <pelib/Schedule.hpp>
#include <pelib/Scalar.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/Set.hpp>
#include <pelib/Task.hpp>
#include <pelib/Link.hpp>
#include <pelib/Taskgraph.hpp>
#include <pelib/Platform.hpp>
#include <pelib/CastException.hpp>
#include <pelib/ParseException.hpp>
#include <pelib/AmplOutput.hpp>
#include <pelib/PelibException.hpp>

#endif

#define debug(var) cout << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] " << #var << " = \"" << (var) << "\"" << endl;

#define LEN 100

#define TAUTHRESHOLD 0.0001
#define MINFACT 0.0001

// define a constant to simulate infinity
#define MAX_DOUBLE pow(2.0,50.0)

// define a threshold when interval halving shall stop, instead of exact solution
#define THRESHOLD 0.000001

using namespace std;

typedef struct task{
int idnumber;
double work;
int maxwidth;
int pbar;
double *htab;
char name[LEN];
} Task;

typedef struct taskset{
int number;
int maxnumber;
int maxcores; // max. number of cores for which taskset can be scheduled
char name[LEN];
Task **list;
} Taskset;

typedef struct taskparams{
Task *ptr;
double frequency;
double start;
double end;
} Taskparams;

typedef struct schedule{
double makespan; // makespan to be reached
int corecount; // number of cores actually used for scheduling
int fullcorecount; // full number of cores
Taskset *ts; // taskset that schedule refers to
char name[LEN];
double *loadpercore; // sums up the loads of the tasks mapped to each core
int *taskspercore; // array of how many tasks are mapped to each core
Taskparams *list; // 2-dim array of size corecount*tasksetsize where element [i*tasksetsize+j] points to j-th task on core i
} Schedule;

typedef struct etable{
Taskset *ts;
int size;
int cores;
double *etab;
} ETable;
    
double alpha;

// give the workload of a task
// requires details of task implementation
double taskload(Task *t) { return t->work; }

// give an element of the h-table of a task
// requires 0<=p<=pbar
// requires details of task implementation
double taskhtab(Task *t,int p) { return t->htab[p]; }

// init a taskset (given the number of tasks)
// note: does not set the number of tasks
// requires detail of Taskset implementation
void inittaskset(Taskset *ts,int n,char *name,int maxcores)
{ 
  ts->number = 0;
  ts->maxnumber = n;
  ts->maxcores = maxcores;
  strcpy(ts->name,name);
  ts->list = (Task**)malloc(sizeof(Task*)*n);
}

double g(int i) { return (double)i*(double)i; }

// specific: the efficiency function is e(0)=1, e(i)=1-R*g(i)/g(maxwidth) for 1<=i<=maxwidth, with g(x)=g^2, and R=0.3
// requires that 1<=i and 1<=maxwidth
double efficiency(int i,int maxwidth)
{ double R=0.3;

  if(i==1) return 1.0;
  else if (i>maxwidth) return 0.000001;
  else return 1.0-R*g(i)/g(maxwidth);
}

// compute the table of h function, and pbar for task
void computehtab(Task *t,int maxcores)
{ int i;
  double eff;
  
  t->pbar=maxcores;// patch for case that real pbar is larger than corecount available!
  t->htab=(double*)malloc(sizeof(double)*(1+maxcores)); // one more as htab starts with 0
  t->htab[0]=0.0;
  for(i=1;i<=maxcores;i++){
      eff=efficiency(i,t->maxwidth);
      // h(i)=sqrt[alpha-1](speedup(i)^alpha/i)
      // as speedup(i)=eff(i)*i, we get:
      t->htab[i]=pow(eff,alpha/(alpha-1.0))*(double)i;
      if((t->htab[i])<(t->htab[i-1])) { t->pbar=i-1; break; }
  }
}  

// add a task to a taskset
// requires detail of Task and Taskset implementation
void addtasktotaskset(Taskset *ts,int id,double work,int maxwidth,char *name)
{
  ts->list[ts->number]=(Task*)malloc(sizeof(Task));
  ts->list[ts->number]->idnumber=id;
  ts->list[ts->number]->work=work;
  ts->list[ts->number]->maxwidth=maxwidth;
  strcpy(ts->list[ts->number]->name,name);
  computehtab(ts->list[ts->number],ts->maxcores);
  ts->number++;
}

// note: does not free the memory for tasks
// requires detail of Taskset implementation
void deinittaskset(Taskset *ts)
{
  free(ts->list);
}

// copy a taskset: requires details of taskset implementation
// does not copy the tasks themselves, only the pointers to the tasks
// includes a taskset initialization, i.e. if taskset trg has been initialized before, it should be deinited first
void copytaskset(Taskset *trg,Taskset *src,char *name)
{ int i;

  inittaskset(trg,src->number,name,src->maxcores);
  trg->number = src->number;
  for(i=0;i<trg->number;i++) *((trg->list)+i) = *((src->list)+i);
}

#if DUMMY != 0 
// dummy, just for testing
// requires detail of Taskset implementation
void readinput(Taskset *ts,int maxcores)
{ int taskcount=10;
  inittaskset(ts, taskcount, (char*)string("Dummy task set").c_str(), maxcores);
//  addtasktotaskset(ts,id,workload,maxwidth,name);
/*  addtasktotaskset(ts,0,4.0,8, (char*)string("task 0").c_str());
  addtasktotaskset(ts,1,3.0,6, (char*)string("task 1").c_str());
  addtasktotaskset(ts,2,5.0,4, (char*)string("task 2").c_str());
  addtasktotaskset(ts,3,0.4,3, (char*)string("task 3").c_str());
  addtasktotaskset(ts,4,0.3,2, (char*)string("task 4").c_str());
  addtasktotaskset(ts,5,0.2,1, (char*)string("task 5").c_str());
*/
addtasktotaskset(ts,0,27.0,4, (char*)string("task 1").c_str());
  addtasktotaskset(ts,1,13.0,4, (char*)string("task 2").c_str());
  addtasktotaskset(ts,2,16.0,4, (char*)string("task 3").c_str());
  addtasktotaskset(ts,3,11.0,1, (char*)string("task 4").c_str());
  addtasktotaskset(ts,4,27.0,4, (char*)string("task 5").c_str());
  addtasktotaskset(ts,5,16.0,4, (char*)string("task 6").c_str());
  addtasktotaskset(ts,6,34.0,4, (char*)string("task 7").c_str());
  addtasktotaskset(ts,7,25.0,4, (char*)string("task 8").c_str());
  addtasktotaskset(ts,8,27.0,4, (char*)string("task 9").c_str());
  addtasktotaskset(ts,9,17.0,4, (char*)string("task 10").c_str());
}
#else
void readinput(Taskset *ts, const pelib::Taskgraph &tg, const pelib::Platform &arch)
{
        using namespace std;
        using namespace pelib;

        int taskcount = tg.getTasks().size();
        inittaskset(ts, taskcount, (char*)string("taskset as read in").c_str(), arch.getCores().size());

        for(set<pelib::Task>::const_iterator i = tg.getTasks().begin(); i != tg.getTasks().end(); i++)
        {
                size_t id = std::distance(tg.getTasks().begin(), i);
                addtasktotaskset(ts, id, i->getWorkload(), i->getMaxWidth(), (char*) i->getName().c_str());
        }       
}

#endif

// return the name string of a taskset
// requires detail of Taskset implementation
char *tasksetname(Taskset *ts) { return ts->name; }

// give number of tasks in taskset
// requires details of taskset implementation
int tssize(Taskset *ts) { return ts->number; }

// requires details of taskset implementation
Task *gettask(Taskset *ts,int i) { return ts->list[i]; }

// print a task
// requires detail of task implementation
void printtask(Task *t)
{ int i;
    
  printf("Task %d <%s> work %lf maxwidth %d pbar %d\nh-table:",t->idnumber,t->name,t->work,t->maxwidth,t->pbar);
  for(i=0;i<=t->pbar;i++) printf(" %lf",t->htab[i]);
  printf("\n");
}

// print a taskset
// requires detail of taskset implementation
void printtaskset(Taskset *ts)
{ int i;

  printf("Taskset <%s> for up to %d cores\n",ts->name,ts->maxcores);
  for(i=0;i<tssize(ts);i++) printtask(ts->list[i]);
}

//#define fprintf(...)
#define printf_d(expr) fprintf(stderr, "[%s:%s:%d] %s = %d\n", __FILE__, __FUNCTION__, __LINE__, #expr, (int)expr);
#define printf_lf(expr) fprintf(stderr, "[%s:%s:%d] %s = %lf\n", __FILE__, __FUNCTION__, __LINE__, #expr, (double)expr);
double etau(Task *t,int p,double tau,double M)
{ double et;
/*
  printf_lf(-pow(taskload(t),alpha))
  printf_lf(pow(tau*taskhtab(t,p+1)+(1.0-tau)*taskhtab(t,p),-alpha))
  printf_lf(taskhtab(t,p+1));
  printf_lf(taskhtab(t,p));
  printf_lf(taskhtab(t,p+1)-taskhtab(t,p));
  printf_lf(pow(M, alpha - 1.0));
*/

  et=-pow(taskload(t),alpha)*(alpha-1.0)*pow(tau*taskhtab(t,p+1)+(1.0-tau)*taskhtab(t,p),-alpha)*(taskhtab(t,p+1)-taskhtab(t,p)) / pow(M, alpha - 1.0);
  return et;
}

void initetable(ETable *et,Taskset *ts,int cores)
{
   et->ts=ts;
   et->size=tssize(ts);
   et->cores=cores;
   et->etab=(double*)malloc(sizeof(double)*(et->size)*(2*cores+1));
}

void deinitetable(ETable *et)
{
  free(et->etab);
}

// requires: cores <= ts->maxcores
// note: all entries are scaled by makespan^{alpha-1}
void computeetable(ETable *et,Taskset *ts,int cores, double M)
{ int i,j;
  
  // etable[i*(2*cores+1)+j] gives for task i, element j of its bend points:
  // if j is even: E<-(j/2), if j is odd: E->((j+1)/2), i.e. in order:
  // E<-(0), E->(1), E<-(1), E->(2),...
  // last element is E<-(pbar), i.e. j=2*pbar
  initetable(et,ts,cores);
  for(i=0;i<tssize(ts);i++){
    et->etab[i*(2*cores+1)]=-MAX_DOUBLE; // E<-(0)=-infinity
    for(j=1;j<=2*(gettask(ts,i)->pbar);j++){
      et->etab[i*(2*cores+1)+j]=etau(gettask(ts,i),(j-1)/2,1.0, M);  
      j++;
      et->etab[i*(2*cores+1)+j]=etau(gettask(ts,i),j/2,0.0, M);  
    }    
  }
}

void printetable(ETable *et)
{ int i,j;

  printf("e-table for task set %s\n",et->ts->name);
  for(i=0;i<et->size;i++){
    printf("Task %d:",i);
    for(j=0;j<1+2*gettask(et->ts,i)->pbar;j++){
      printf(" %lf",et->etab[i*(1+2*(et->cores))+j]);
    }
    printf("\n");    
  }      
}    

void computeinitialc(Taskset *ts,ETable *et,double *clp,double *cup, double M)
{ int i;
  int pm;
  double taum;
  double cl,cltmp,cu,cutmp;
  
  if(tssize(ts)>et->cores){ pm=0; taum=(double)(et->cores)/(double)(tssize(ts)); } else { pm=1; taum=0.0; }
  cl=0.0; cu=0.0;
  for(i=0;i<tssize(ts);i++){
    cltmp=etau(gettask(ts,i),pm,taum, M);
    //printf_lf(cltmp);
    if(cltmp<cl) cl=cltmp;
    cutmp=et->etab[i*(1+2*(et->cores))+2*(gettask(ts,i)->pbar)];
    if(cutmp<cu) cu=cutmp;
  }    

  *clp=cl;
  *cup=cu;
}

double invertefunction(Taskset *ts,ETable *et,int i,double c,double cl,double cu,int *bendpointsleftptr,double M)
{ int j;
  int pint;
  double proc,tau;
    
  // find adjacent bendpoints for c
  // in final version, use binary search. Here: linear
  for(j=0;j<2*gettask(ts,i)->pbar;j++)
    if(c<et->etab[i*(2*(ts->maxcores)+1)+j]) break;
  // now know that c is between j-1 and j
//  printf("task %d position in etable %d\n",i,j-1);
  // check if cl and cu are between bendpoints or not
  if(!((cl>et->etab[i*(2*(ts->maxcores)+1)+j-1])&&(cu<et->etab[i*(2*(ts->maxcores)+1)+j]))) (*bendpointsleftptr)++;

  // check if case 1 or case 2
  if((j-1)&1){  // j-1 is odd
    // case 2
    proc=(double)(j>>1);
//    printf("case 2 p+tau=%lf\n",proc);
  }else{ // case 1
    pint=(j-1)>>1;
    proc=(double)pint;
// simple workaround: linear interpolation
      //tau = (c-(et->etab[i*(2*(ts->maxcores)+1)+j-1]))/((et->etab[i*(2*(ts->maxcores)+1)+j])-(et->etab[i*(2*(ts->maxcores)+1)+j-1]));
        tau = ((ts->list[i]->work)*pow((1.0-alpha)*((ts->list[i]->htab[1+pint])-(ts->list[i]->htab[pint]))/(c*pow(M,alpha-1.0)),1.0/alpha)-(ts->list[i]->htab[pint]))/((ts->list[i]->htab[1+pint])-(ts->list[i]->htab[pint]));
      proc += tau;
//    proc += ((ts->list[i]->work)*pow((1.0-alpha)*((ts->list[i]->htab[1+pint])-(ts->list[i]->htab[pint]))/(c*pow(M,alpha-1.0)),1.0/alpha)-(ts->list[i]->htab[pint]))/((ts->list[i]->htab[1+pint])-(ts->list[i]->htab[pint]));
        //printf_d(j);
//    printf("nominator prefactor %lf\n",(ts->list[i]->work));
//    printf("nominator -(alpha-1)*(h(p+1)-h(p)) %lf\n",(1.0-alpha)*((ts->list[i]->htab[1+pint])-(ts->list[i]->htab[pint])));
//printf_lf(c);
//printf_lf(alpha);
//printf_lf(M);
//    printf("nominator c*M to alpha-1 %lf\n",(c*pow(M,alpha-1.0)));
//    printf("nominator 2nd addend %lf\n",-(ts->list[i]->htab[pint]));
//    printf("denominator %lf\n",((ts->list[i]->htab[1+pint])-(ts->list[i]->htab[pint])));
//    printf("case 1 p=%d tau=%lf\n",pint,proc-(double)pint);
  }        
  // compute p+tau, and return
  
  return proc;
}
    
int checktoomany(Taskset *ts,ETable *et,double c,double cl,double cu,int *bendpointsleftptr,double M)
{ double m,m2;
  int i;
  int singletaskbendpointsleft = 0;

  *bendpointsleftptr = 0;
  m=0.0;
  for(i=0;i<tssize(ts);i++){
    m2 = invertefunction(ts,et,i,c,cl,cu,&singletaskbendpointsleft,M);
//    printf("Task %d alloc %lf\n",i,m2);
    m += m2;
        //printf_lf(m);
    if(singletaskbendpointsleft) (*bendpointsleftptr)++;  
  }    
  if(m>(double)(et->cores)) return 1; else return 0;
}

// JKJK Nov 4, 2014: new function
double computetaskenergy(Task *t,int pistar,double taui,double deadline,double lalpha)
{ double energy;
  double workload;
  double hp,hpplusone;

  workload=taskload(t);
  if(workload == 0)
  {
    return 0;
  }
  else
  {
    hp=taskhtab(t,pistar);
    hpplusone=taskhtab(t,pistar+1);
    energy=pow(workload,lalpha)/pow(deadline*(taui*hpplusone+(1.0-taui)*hp),lalpha-1.0);
/*
        printf_lf(workload);
        printf_lf(t->idnumber);
        printf_lf(taui);
        printf_lf(pistar);
        printf_lf(deadline);
        printf_lf(lalpha);
        printf_lf(hp);
        printf_lf(hpplusone);
        printf_lf(energy);
    printf_lf(pow(workload,lalpha));
        printf_lf(pow(deadline*(taui*hpplusone+(1.0-taui)*hp),lalpha-1.0)); */
/*  if((pistar ==0) && (taui < TAUTHRESHOLD))
  {
    energy = pow(workload, lalpha) / pow(deadline * MINFACT, lalpha - 1.0);
  }
  else
  {*/
//  }
    return energy;
  }
}    

// JKJK Nov 4, 2014: changed function to return value double
#if DUMMY != 0
double computeoptc(Taskset *ts,ETable *et,int p,double M)
#else
double computeoptc(Taskset *ts,ETable *et,int p,double M, double minFreq)
#endif
{ double cl,cu,c,prev_cl = 0,prev_cu = 0;
  int bendpointsflag;
  int i;
  int dummy;
  double pistar;
  double energy; // JKJK Nov 4, 2014: added variable
    
  computeinitialc(ts,et,&cl,&cu, M);
//printf_lf(cl);
//printf_lf(cu);
  do{
    c=(cl+cu)/2.0;
    //printf_lf(c);
    prev_cl = cl;
    prev_cu = cu;
    if(checktoomany(ts,et,c,cl,cu,&bendpointsflag,M)) cu=c; else cl=c;
//  }while(bendpointsflag); // skip break when no bendpoints left in intervall,
//  directsolve(); // and skip computing direct solution
// instead: stop when interval cl,cu is sufficiently small, and compute processor allocations from c
//    printf("cl %lf cu %lf c %lf fabs(cu - cl) %lf\n",cl,cu,c,fabs(cu-cl));
  }while(fabs(cu-cl)>THRESHOLD && (cl != prev_cl || cu != prev_cu));
  c=cu=cl; // ensure that sum of processor allocations is <= number of cores
  // output: number of tasks, number of cores, deadline
//  printf("%d %d %lf\n",tssize(ts),p,M);
  energy=0.0; // JKJK Nov 4, 2014: added statement
  // for each task, compute
  for(i=0;i<tssize(ts);i++){
    pistar=invertefunction(ts,et,i,c,cl,cu,&dummy,M);
    // for each task: tasknumber, integral number of cores allocated p, fractional number of cores allocated tau,speedup of task with p cores, speedup of task with p+1 cores
    //printf("%d %d %lf %lf %lf %lf\n",ts->list[i]->idnumber,(int)pistar,pistar-(int)pistar,ts->list[i]->work,((int)pistar)*efficiency((int)pistar,ts->list[i]->maxwidth),(1+(int)pistar)*efficiency(1+(int)pistar,ts->list[i]->maxwidth));
//    printf("%d %d %lf %lf %lf %lf\n",ts->list[i]->idnumber,(int)pistar,pistar,ts->list[i]->work,((int)pistar)*efficiency((int)pistar,ts->list[i]->maxwidth),(1+(int)pistar)*efficiency(1+(int)pistar,ts->list[i]->maxwidth));
// JKlatest: add x lines
    if(pistar<1.0){
//      double taui=pistar-(int)pistar=pistar (because (int)pistar==0);
//      double time=taui*M;
//      double frequency=taskload(ts->list[i])/time;

#if DUMMY != 0 && FORCE_MIN_FREQUENCY != 0
        int minFreq = 1;
#endif

        // If the task's necessary frequency is lower than the minimal frequency given by the platform, then raise it to the minimum
#if FORCE_MIN_FREQUENCY != 0    
      double frequency=taskload(ts->list[i])/(pistar*M);
      if(frequency<minFreq){
        pistar=taskload(ts->list[i])/(minFreq * M); // set frequency to 1.0, makes taui smaller!
      }
#endif
    }
    energy+=computetaskenergy(ts->list[i],(int)pistar,pistar-(int)pistar,M,alpha); // JKJK Nov 4, 2014: added statement
/*      printf_lf(i);
        printf_lf(pistar);
        printf_lf(M);
        printf_lf(alpha);
        printf_lf(energy);*/
  }
  return energy; // JKJK Nov 4, 2014: added statement
}
    
// Quality assessment parameters
const long long int nsec_in_sec = 1000000000;

static int
timespec_subtract(struct timespec *result, struct timespec *x, struct timespec *y)
{
        /* Perform the carry for the later subtraction by updating y. */
        if (x->tv_nsec < y->tv_nsec)
        {
                int nsec = (y->tv_nsec - x->tv_nsec) / nsec_in_sec + 1;
                y->tv_nsec -= nsec_in_sec * nsec;
                y->tv_sec += nsec;
        }
        if (x->tv_nsec - y->tv_nsec > nsec_in_sec)
        {
                int nsec = (x->tv_nsec - y->tv_nsec) / nsec_in_sec;
                y->tv_nsec += nsec_in_sec * nsec;
                y->tv_sec -= nsec;
        }
     
        /* Compute the time remaining to wait. tv_nsec is certainly positive. */
        result->tv_sec = x->tv_sec - y->tv_sec;
        result->tv_nsec = x->tv_nsec - y->tv_nsec;
     
        /* Return 1 if result is negative. */
        return x->tv_sec < y->tv_sec;
}

#if DUMMY == 0
static
pelib::Schedule makeSchedule(const pelib::Taskgraph &tg, const pelib::Platform &arch, std::map<const string, double>& stats)
#else
int main(int argc,char *argv[])
#endif
{
        double M;
        int p;
        struct timespec start, stop, total_time;
        Taskset ts;
        ETable et;

        // set alpha, important for energy and computation of h-function
        alpha = 3.0;

#if DUMMY != 0
        // set number of cores and makespan
        p = 4;
        M = 33.6758;

        // read in taskset ts
        readinput(&ts, p);
#else
        p = arch.getCores().size();
        M = tg.getDeadline(arch);
        double minFreq = *(*arch.getCores().begin())->getFrequencies().begin();

        readinput(&ts, tg, arch);
#endif
        // printtaskset(&ts);
        clock_gettime(CLOCK_MONOTONIC, &start);
        computeetable(&et,&ts,p, M);
        clock_gettime(CLOCK_MONOTONIC, &stop);
#if DUMMY != 0
        double energy = computeoptc(&ts,&et,p,M);
#else
        double energy = computeoptc(&ts,&et,p,M,minFreq);
#endif

        deinittaskset(&ts);
        deinitetable(&et);

#if DUMMY != 0
        cerr << "energy = " << energy << endl;
#else
        /*
        printf_lf(energy);
        printf_lf(M);
        printf_lf((double)p);
        printf_lf(alpha);
        */
        double freq = pow(energy / (M * p), 1.0/alpha);

        pelib::Task t(string("energy"));
        t.setWorkload(energy / pow(freq, alpha));
        t.setEfficiencyString("1");
        t.setMaxWidth(p);
        t.setFrequency(freq);

        std::map<int, std::map<float, pair<const pelib::Task*, double> > > schedule;
        for(int i = 0; i < p; i++)
        {
                std::map<float, pair<const pelib::Task*, double> > core;
                core.insert(std::pair<float, pair<const pelib::Task*, double> >(0, pair<const pelib::Task*, double>(&t, t.getWorkload())));

                schedule.insert(pair<int, std::map<float, pair<const pelib::Task*, double> > >(i + 1, core));
        }

        pelib::Schedule pelib_schedule(string("Sanders and Speck"), tg.getName(), schedule);
#endif

#if DUMMY != 0
        pelib::Taskgraph newtg;
        set<pelib::Task> tasks;
        tasks.insert(t);
        newtg = pelib::Taskgraph(tasks, set<pelib::Link>());
        newtg.setName("Dummy taskgraph");
        std::ostringstream strs;
        strs << M;
        std::string str = strs.str();
        newtg.setDeadlineCalculator(strs.str());
        std::ofstream newtg_file(std::string(argv[3]), std::ios::out);
        pelib::GraphML().dump(newtg_file, newtg);
        newtg_file.close();

        pelib::XMLSchedule().dump(cout, pelib_schedule);
#endif

        timespec_subtract(&total_time, &stop, &start);
#if DUMMY != 0
        cerr << "energy = " << energy << std::endl;
#else
        stats.insert(pair<const string, double>("optimal", 1));
        stats.insert(pair<const string, double>("feasible", isfinite(energy)));
        stats.insert(pair<const string, double>("time_global", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec));
#endif

#if DUMMY == 0
        if(isfinite(energy))
        {
                return pelib_schedule;
        }
        else
        {
                return pelib::Schedule(string("Sanders and Speck"), tg.getName(), pelib::Schedule::table());
        }
#else
        return isfinite(energy) ? EXIT_SUCCESS : EXIT_FAILURE;
#endif
}

pelib::SandersSpeck::SandersSpeck()
{
        // Do nothing
}

pelib::SandersSpeck::SandersSpeck(const Taskgraph &tg, const Platform &pt)
{
        this->taskgraph = tg;
        this->platform = pt;
}

pelib::Schedule
pelib::SandersSpeck::schedule(const Taskgraph &tg, const Platform &pt, std::map<const string, double>& stats) const
{
        return makeSchedule(tg, pt, stats);
}

pelib::Schedule
pelib::SandersSpeck::schedule(const Taskgraph &tg, const Platform &pt, const Algebra &param, std::map<const string, double>& stats) const
{
        return schedule(tg, pt, stats);
}

const pelib::Algebra*
pelib::SandersSpeck::solve() const
{
        std::map<const string, double> stats;
        return new pelib::Algebra(schedule(this->taskgraph, this->platform, stats).buildAlgebra());
}

const pelib::Algebra*
pelib::SandersSpeck::solve(std::map<const string, double> &stats) const
{
        return new pelib::Algebra(schedule(this->taskgraph, this->platform, stats).buildAlgebra());
}

std::string
pelib::SandersSpeck::getShortDescription() const
{
        return string("SandersSpeck.");
}

#ifdef __cplusplus
extern "C" {
#endif

const pelib::Schedule*
pelib_schedule(const pelib::Taskgraph &tg, const pelib::Platform &pt, size_t argc, char **argv, std::map<const string, double>& statistics)
{
        // Convert solver output to general schedule
        pelib::Schedule *sched;
        sched = new pelib::Schedule(pelib::SandersSpeck().schedule(tg, pt, statistics));

        return sched;
}

string
pelib_description(size_t argc, char **argv)
{
        // Convert solver output to general schedule
        string desc;
        desc = pelib::SandersSpeck().getShortDescription();

        return desc;
}

void
pelib_delete(pelib::Schedule *sched)
{
        delete sched;
}

#ifdef __cplusplus
}
#endif