src/PruhsHeuristic.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/PruhsHeuristic.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/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 50

using namespace std;

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

typedef struct taskset{
int number;
int maxnumber;
char name[LEN];
Task **list;
} Taskset;

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

typedef struct schedule{
double makespan; // makespan to be reached
int corecount; // 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;

// alpha used in greedy mapping, not used for energy computation!
// ALPHA 0.0 is used for mapping to core with minimum current load
#define ALPHA 0

// Max frequency
double max_frequency;
double *discrete_frequencies_relative;
size_t number_of_frequencies;

/*
// JK: added following declarations
#define NUMBEROFFREQUENCIES 5

// frequencies as fractions of max_frequency, in ascending order
// i.e. last frequency is 1.0
double discrete_frequencies_relative[NUMBEROFFREQUENCIES]={0.2,0.4,0.6,0.8,1.0};

#define max_frequency 100.0
*/


//void readtaskset(Taskset *ts,double *Mptr,int *pptr, char*, char*);

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

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

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

// deinit a taskset
// note: does not free the memory for tasks
// requires detail of Taskset implementation
static
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
static
void copytaskset(Taskset *trg,Taskset *src,char *name)
{ int i;

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

static
#if DUMMY == 0
void readtaskset(Taskset *ts, double *Mptr, int *pptr, const pelib::Taskgraph &tg, const pelib::Platform &arch)
{
  using namespace std;
  using namespace pelib;

  int taskcount = tg.getTasks().size();
  inittaskset(ts,taskcount, (char*) tg.getName().c_str());

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

  *Mptr = tg.getDeadline(arch); // makespan
  *pptr = arch.getCores().size(); // no. of cores

  set<float> frequencies = (*arch.getCores().begin())->getFrequencies();
  number_of_frequencies = frequencies.size();
  max_frequency = *frequencies.rbegin();
  
  discrete_frequencies_relative = (double*)malloc(sizeof(double) * number_of_frequencies);
  int i = 0;
  for(set<float>::iterator iter = frequencies.begin(); iter != frequencies.end(); iter++)
  {
    discrete_frequencies_relative[i] = *iter / max_frequency;
    i++;
  }
}
#else
void readtaskset(Taskset *ts, double *Mptr, int *pptr)
{
  *Mptr = 10; // makespan
  int taskcount = 10;
  inittaskset(ts,taskcount, (char*) std::string("taskset as read in").c_str());
  addtasktotaskset(ts,0,10.0, (char*) std::string("task 0").c_str());
  addtasktotaskset(ts,1,11.0, (char*) std::string("task 1").c_str());
  addtasktotaskset(ts,2,12.0, (char*) std::string("task 3").c_str());
  addtasktotaskset(ts,3,13.0, (char*) std::string("task 3").c_str());
  addtasktotaskset(ts,4,14.0, (char*) std::string("task 4").c_str());
  addtasktotaskset(ts,5,15.0, (char*) std::string("task 5").c_str());
  addtasktotaskset(ts,6,16.0, (char*) std::string("task 6").c_str());
  addtasktotaskset(ts,7,17.0, (char*) std::string("task 7").c_str());
  addtasktotaskset(ts,8,18.0, (char*) std::string("task 8").c_str());
  addtasktotaskset(ts,9,19.0, (char*) std::string("task 9").c_str());

  number_of_frequencies = 5;
  discrete_frequencies_relative = (double*)malloc(sizeof(double) * number_of_frequencies);
  discrete_frequencies_relative[0] = 0.2;
  discrete_frequencies_relative[1] = 0.4;
  discrete_frequencies_relative[2] = 0.6;
  discrete_frequencies_relative[3] = 0.8;
  discrete_frequencies_relative[4] = 1.0;
  max_frequency = 100;

  *Mptr = 50.0; // makespan
  *pptr = 4; // no. of cores
}
#endif

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

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

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

#if DUMMY != 0
// print a task
// requires detail of task implementation
static
void printtask(std::ostream &out, Task *t)
{
        out << "## Task " << t->idnumber << " <" << t->name << "> work " << t->work << std::endl;
}

// print a taskset
// requires detail of taskset implementation
static
void printtaskset(std::ostream &out, Taskset *ts)
{ int i;

  out << "## Taskset <" << ts->name << std::endl;
  for(i=0;i<tssize(ts);i++) printtask(out, ts->list[i]);
}

// print a taskparams
// requires detail of taskparams implementation
static
void printtaskparams(std::ostream &out, Taskparams *tp)
{
   out << "## Starttime: " << tp->start << " Frequency " << tp->frequency << " of" << std::endl;
   printtask(out, tp->ptr);
}
#endif

// Finds the makespan of a schedule
static
double schedule_makespan(Schedule *sched, float frequency = 0)
{
  int i, j;
  float makespan = 0;

  for(i = 0; i < sched->corecount; i++)
  {
    float start_time = 0;
    for(j = 0; j < sched->taskspercore[i]; j++)
    {
      Taskparams *tp = &(sched->list[i*tssize(sched->ts)+j]);
      float workload = (float)tp->ptr->work;
      float freq = frequency == 0 ? (float)tp->frequency : frequency;
      float end_time = start_time + workload / freq;
      start_time = end_time;

      //std::cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] " << "start_time = " << start_time << ", workload = " << workload << ", freq = " << freq << ", end_time = " << end_time << std::endl;

      if(end_time > makespan)
      {
        makespan = end_time;
      }
    }
  }

  return makespan;
}

// print a schedule
// requires detail of schedule implementation
static
#if DUMMY == 0
pelib::Schedule buildSchedule(Schedule *sched)
#else
void printschedule(std::ostream &out, Schedule *sched)
#endif
{
#if DUMMY == 0
  using namespace std;

  int i, j;
  vector<pelib::Task> tasks;
  
  // Count the number of tasks and reserve the necessary amount
  // to prevent C++ from copying task instances inside, making
  // pointers inserted in schedules to become invalid
  size_t num = 0;
  for(i = 0; i < sched->corecount; i++)
  {
    for(j = 0; j < sched->taskspercore[i]; j++)
    {
       num++;
    }
  }
  tasks.reserve(num);

  std::map<int, std::map<float, pair<const pelib::Task*, double> > > schedule;
  for(i = 0; i < sched->corecount; i++)
  {
    map<float, pair<const pelib::Task*, double> > core_schedule;

    for(j = 0; j < sched->taskspercore[i]; j++)
    {
      Taskparams *tp = &(sched->list[i*tssize(sched->ts)+j]);
      pelib::Task task(string(tp->ptr->name));
      tasks.push_back(task);
      pelib::Task &t = tasks[tasks.size() - 1];
      t.setFrequency(tp->frequency);
      t.setWidth(1);
      t.setWorkload(tp->ptr->work);
      t.setStartTime((float)tp->start);

      core_schedule.insert(pair<float, pair<const pelib::Task*, double> >((float)tp->start, pair<const pelib::Task*, double>(&t, t.getWorkload())));
    }

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

  //psched.setSchedule(schedule);
  pelib::Schedule psched(string("Pruhs Heuristic"), tasksetname(sched->ts), schedule);
  
  //psched.setRoundTime(sched->makespan);

  return psched;
#else
  int i,j;

  out << "## Schedule <" << sched->name << "> of taskset <" << tasksetname(sched->ts) << "> on " << sched->corecount << "cores with makespan " << sched->makespan << std::endl;

  for(i=0;i<sched->corecount;i++)
  {
    out << "## Schedule for core " << i << std::endl;
    for(j=0;j<sched->taskspercore[i];j++)
    {
      printtaskparams(out, &(sched->list[i*tssize(sched->ts)+j]));
    }
  }
#endif
}

// compare Tasks according to work, so that they are in descending order
// requires details of task implementation
static
int comparetasks(const void *t1,const void *t2)
{ Task *tp1, *tp2;

  tp1 = *((Task**)t1);
  tp2 = *((Task**)t2);
  if(tp1->work>tp2->work) return -1;
  if(tp1->work<tp2->work) return 1;
  return 0;
}

// sort the tasks of a taskset in descending order.
// requires details of Taskset implementation
static
void sorttaskset(Taskset *ts)
{
  qsort(ts->list,ts->number,sizeof(Task*),comparetasks);
}

// init the schedule
// requires detail of Schedule implementation
static
void initschedule(Schedule *sched,Taskset *ts,double makespan,int corecount,char *name)
{ int i;

  sched->makespan = makespan;
  sched->corecount = corecount;
  sched->ts = ts;
  strcpy(sched->name,name);
  sched->loadpercore = (double*)malloc(sizeof(double)*corecount);
  for(i=0;i<corecount;i++) sched->loadpercore[i]=0.0;
  sched->taskspercore = (int*)malloc(sizeof(int)*corecount);
  for(i=0;i<corecount;i++) sched->taskspercore[i]=0;
  sched->list = (Taskparams*)malloc(sizeof(Taskparams)*corecount*tssize(ts));
}

// deinit a schedule
// requires detail of schedule implementation
static
void deinitschedule(Schedule *sched)
{
  free(sched->loadpercore);
  free(sched->taskspercore);
  free(sched->list);
}

// add a task to a Taskparam entry of a schedule
// requires detail of taskparams implementation
static
void addtasktoparams(Taskparams *tp,Task *t) { tp->ptr=t; }

// set the frequency in a Taskparam entry of a schedule
// requires detail of taskparams implementation
static
void setfreqparams(Taskparams *tp,double freq) { tp->frequency=freq; }

// set the starttime in a Taskparam entry of a schedule
// return the endtime, implicitly assuming continuous frequencies
// requires that the frequency in the Taskparam entry is already set
// requires detail of taskparams implementation
static
double setstarttimeparams(Taskparams *tp,double time)
{ 
  tp->start=time;
  return time+taskload(tp->ptr)/(tp->frequency);
}

// JK: new routine
// get pointer to task in taskparams
// requires detail of taskparams implementation
static
Task *gettaskfromtaskparams(Taskparams *tp) { return tp->ptr; }

// JK: new routine
// copy a taskparams struct
// requires detail of taskparams implementation
static
void copytaskparams(Taskparams *trg,Taskparams *src)
{
    trg->ptr=src->ptr;
    trg->frequency=src->frequency;
    trg->start=src->start;
}

// JK: new routine
// copy a schedule, with provision of a new name
// requires detail of schedule implementation
static
void copyschedule(Schedule *trg,Schedule *src,char *newname)
{ int i;
    
  initschedule(trg,src->ts,src->makespan,src->corecount,newname);

  for(i=0;i<src->corecount;i++){
    trg->loadpercore[i]=src->loadpercore[i];
    trg->taskspercore[i]=src->taskspercore[i];
  }

  for(i=0;i<(src->corecount)*tssize(src->ts);i++){
    copytaskparams(&(trg->list[i]),&(src->list[i]));
  }    
}

// huge double number, larger than any load...
#define MAX_DOUBLE pow(2.0,1000)

// map a task into a schedule: greedy, i.e. search core with minimum
// increase when considering ALPHA-power
// requires detail of schedule implementation
static
void map(Task *t,Schedule *sched)
{ int i;
  int minarg=-1;
  double minincrease=MAX_DOUBLE;
  double increase;
  Taskparams *tp;
  int index;

  // find core with minimum increase
  for(i=0;i<sched->corecount;i++){
    if(ALPHA == 0.0)
      increase = sched->loadpercore[i];
    else
      increase = pow(sched->loadpercore[i] + taskload(t), ALPHA) - pow(sched->loadpercore[i], ALPHA);
    if(increase<minincrease) { minincrease=increase; minarg=i; }
  }
  // increase the load of that core
  sched->loadpercore[minarg] += taskload(t);
  // link the task
  index = minarg * (tssize(sched->ts))+(sched->taskspercore[minarg]);
  tp = &(sched->list[index]);
  addtasktoparams(tp,t);
  // increase number of tasks for that core
  sched->taskspercore[minarg]++;
}

// JK: adapted routine
// scale the frequencies of the task(params) of a schedule such that the deadline is met.
// all the tasks on one core have same frequency: sum-of-workloads/deadline
// set the starttimes of the tasks accordingly
// return 0 if all frequencies <= max_frequency, else return 1 as schedule is not feasible
// requires detail of schedule implementation
static
int scalefrequencies(Schedule *sched)
{ int i,j;
  double freq;
  double time;
  int flag=0;

  for(i=0;i<sched->corecount;i++){
    time=0.0;
    freq=sched->loadpercore[i]/sched->makespan;
    if(freq>max_frequency) flag=1;
    for(j=0;j<sched->taskspercore[i];j++){
      setfreqparams(&(sched->list[i*tssize(sched->ts)+j]),freq);
      time=setstarttimeparams(&(sched->list[i*tssize(sched->ts)+j]),time);
    }
  }
  return flag;
}

// map the tasks to cores to balance load vector
// greedy approach: map tasks one by one, map next task such that the maximum load of any core
// is increased as little as possible, i.e. map the task to the core with the current minimum load
// return 0 if schedule feasible (ie. all frequencies <= 1.0), else return 1 as schedule is not feasible
static
int scheduletaskset(Taskset *tssorted,Schedule *sched,double makespan,int corecount)
{ int i;

  initschedule(sched,tssorted,makespan,corecount, (char*) std::string("Pruhs schedule").c_str());
  
  for(i=0;i<tssize(tssorted);i++){
    ::map(gettask(tssorted,i),sched);
  }
  return scalefrequencies(sched);  
}

// JK: removed the CONT and DISC defines

// JK: adapted routine
// adapt the frequency for discrete freq levels
// currently statically defined, see above
static
double adaptfrequency(double freq)
{ size_t i;

  if(freq>max_frequency) freq=max_frequency; // should not happen as in
    // this case the schedule is infeasible, and the computeenergy is never invoked
  for(i=0;i<number_of_frequencies;i++){
    if(freq<=discrete_frequencies_relative[i]*max_frequency){
      freq=discrete_frequencies_relative[i]*max_frequency;
      break;
    }
  }
  return freq;
}

// JK: new routine
// compute index of discrete frequency level
static
int finddiscfrequencylevel(double freq)
{ size_t i;

  if(freq>max_frequency) freq=max_frequency; // should not happen as in
    // this case the schedule is infeasible, and the computeenergy is never invoked
  for(i=0;i<number_of_frequencies;i++){
    if(freq<=discrete_frequencies_relative[i]*max_frequency){
      break;
    }
  }
  return i;
}


// JK: new routine
// scale task frequencies on each core to next higher and lower frequencies such that makespan is met, and frequency is switched only once
// requires that all frequencies are <= max_frequency
// returns 0 if all frequencies are <= max_frequency, 1 else
// requires detail of schedule implementation
static
int scaletodiscretefrequencies(Schedule *sched)
{ int i,j;
  double freq;
  double discfreq;
  int discfreqlevel;
  double time;
  double sparetime;
  double addtime;
  int flag=0;

  for(i=0;i<sched->corecount;i++){
    time=0.0;
    freq=sched->loadpercore[i]/sched->makespan;
    if(freq>max_frequency){ flag=1; freq=max_frequency; }
    discfreq=adaptfrequency(freq);
    sparetime = (sched->makespan) - (sched->loadpercore[i])/discfreq; // compute how much time saved by higher discr. freq
    discfreqlevel=finddiscfrequencylevel(freq);
    if(discfreqlevel==0) sparetime=-1.0; // if freq <= lowest discrete frequency level, then no task can be scaled down
    for(j=0;j<sched->taskspercore[i];j++){
      // compute difference between task runtimes at lower discrete frequency and at higher discrete frequency
      addtime=taskload(gettaskfromtaskparams(&(sched->list[i*tssize(sched->ts)+j])))/max_frequency*(1.0/discrete_frequencies_relative[discfreqlevel-1] - 1.0/discrete_frequencies_relative[discfreqlevel]);
      if(addtime<=sparetime){
        setfreqparams(&(sched->list[i*tssize(sched->ts)+j]),discrete_frequencies_relative[discfreqlevel-1]*max_frequency);
        sparetime -= addtime;
      }else  
        setfreqparams(&(sched->list[i*tssize(sched->ts)+j]),discfreq);
      time=setstarttimeparams(&(sched->list[i*tssize(sched->ts)+j]),time);
    }
  }
  return flag;
}

#if DUMMY != 0
// compute the power consumption of a task running at a certain frequency
// requires frequency <= 1.0
// if discrete frequency levels used, increase frequency to next available level
// power model currently hardcoded as freq^3
// return power consumption
// requires detail of Taskparams implementation
static
double powercons(Taskparams *tp)
{ double freq;

  freq=tp->frequency; // JK: removed the frequency adaptation
  return freq*freq*freq;  
}

// compute runtime of a task as division of workload and frequency
// requires frequency <= 1.0
// if discrete frequency levels used, increase frequency to next available level
// return runtime
// requires detail of Taskparams implementation
static
double taskruntime(Taskparams *tp)
{ double freq;

  freq=tp->frequency;
  return taskload(tp->ptr)/freq;  
}

// compute the energy of a task as product of power consumption (depending on freq) and runtime
// return the energy
static
double taskenergy(Taskparams *tp)
{ 
  return powercons(tp)*taskruntime(tp);
}

// compute the energy of a schedule.
// return the computed energy
// requires detail of schedule implementation
static
double computeenergy(Schedule *sched)
{ int i,j; 
  double energy=0.0;
  
  for(i=0;i<sched->corecount;i++)
    for(j=0;j<sched->taskspercore[i];j++){
      energy += taskenergy(&(sched->list[i*tssize(sched->ts)+j]));
    }
  return energy;  
}
#endif

// 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
{ Taskset ts1,tssorted;
  Schedule sched;
  double M;
  int p;
  int infeasible;
#if DUMMY != 0
  double en_cont,en_disc;
#endif
  struct timespec start, stop, total_time;
  Schedule sched_disc;

#if DUMMY == 0
  int n;

/* 
  std::ifstream tg_file(std::string(argv[1]), std::ios::in);
  std::ifstream arch_file(std::string(argv[2]), std::ios::in);

  pelib::Taskgraph tg = pelib::GraphML().parse(tg_file);
  pelib::Platform arch = pelib::AmplPlatform().parse(arch_file);

  tg_file.close();
  arch_file.close();
*/

  // read in taskset ts1 (including possible allocations in internal representation of taskset and tasks), deadline M, number of cores p
  readtaskset(&ts1, &M, &p, tg, arch);
#else
  // read in taskset ts1 (including possible allocations in internal representation of taskset and tasks), deadline M, number of cores p
  readtaskset(&ts1,&M,&p);
#endif

  /* TODO @Jörg: check if this region is indeed where the "useful" computation runs */
  clock_gettime(CLOCK_MONOTONIC, &start);

  /* Useful region */
  copytaskset(&tssorted,&ts1, (char*) std::string("taskset sorted").c_str());
  sorttaskset(&tssorted);
  /* End of useful region */

  clock_gettime(CLOCK_MONOTONIC, &stop);
  timespec_subtract(&total_time, &stop, &start);

#if DUMMY == 0
  stats.insert(pair<const string, double>("time_global", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec));

  n = tg.getTasks().size();
  stats.insert(pair<const string, double>("complexity", n * log2(n) + n * p)); 
#endif

  infeasible=scheduletaskset(&tssorted,&sched,M,p);
  stats.insert(pair<const string, double>("feasible", !infeasible));

  if(!infeasible){
    // write out the schedule...
#if DUMMY != 0
    en_cont=computeenergy(&sched);
    printschedule(std::cerr, &sched); // NM: We can only print one schedule or the framework cannot parse correctly the output
    std::cerr << "quality = " << schedule_makespan(&sched, 1) << std::endl; 
#else
  stats.insert(pair<const string, double>("quality", schedule_makespan(&sched, 1)));
#endif
    copyschedule(&sched_disc,&sched,(char*) std::string("Pruhs schedule discrete frequencies").c_str());
    infeasible = scaletodiscretefrequencies(&sched_disc);
#if DUMMY == 0
    return buildSchedule(&sched_disc);
#else
    en_disc=computeenergy(&sched_disc);
    printschedule(std::cout, &sched_disc);
    std::cerr << "## Energy with cont. freq " << en_cont << std::endl;
    std::cerr << "## Energy with disc freq " << en_disc << std::endl;
#endif
    //printf("## Energy with cont. freq %lf\n## Energy with disc freq %lf\n",en_cont,en_disc);
  }
#if DUMMy != 0
  else{
    printschedule(std::cout, &sched);
  }
#endif
#if DUMMY != 0
  std::cerr << "feasible = " << !infeasible << std::endl;
#endif

  deinittaskset(&ts1);
  deinittaskset(&tssorted);
  deinitschedule(&sched);
  //deinitschedule(&sched_disc);
  free(discrete_frequencies_relative);
#if DUMMY == 0
  return pelib::Schedule("Pruhs Heuristic", tg.getName(), std::map<int, std::map<float, pair<const pelib::Task*, double> > >());
#else
  return EXIT_SUCCESS;
#endif
}

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

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

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

pelib::Schedule
pelib::PruhsHeuristic::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::PruhsHeuristic::solve() const
{
        std::map<const string, double> stats;
        return new pelib::Algebra(schedule(this->taskgraph, this->platform, stats).buildAlgebra());
}

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

std::string
pelib::PruhsHeuristic::getShortDescription() const
{
        return string("Pruhs-Heur.");
}

#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::PruhsHeuristic().schedule(tg, pt, statistics));

        return sched;
}

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

        return desc;
}

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

#ifdef __cplusplus
}
#endif