src/CrownCompositeAnnealing.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 <iostream>
#include <sstream>

#include <crown/allocation.h>
#include <crown/mapping.h>
#include <crown/scaling.h>
#include <crown/crown.h>
#include <crown/annealing.h>
#include <crown/CrownCompositeAnnealing.hpp>
#include <crown/CrownConfigBinary.hpp>
#include <crown/CrownException.hpp>
#include <crown/CrownAllocationFastest.hpp>
#include <crown/CrownMappingLTLG.hpp>
#include <crown/CrownScalingHeight.hpp>

#include <pelib/AmplInput.hpp>
#include <pelib/Schedule.hpp>
#include <pelib/Scalar.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/Set.hpp>
#include <pelib/time.h>

#ifdef debug
#undef debug
#endif

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

using namespace std;
using namespace pelib;
using namespace pelib::crown;

// Quality assessment parameters
static const long long int nsec_in_sec = 1000000000;
const float CrownCompositeAnnealing::default_init_temperature = 8;
const float CrownCompositeAnnealing::default_cooling_factor = 0.6;
const float CrownCompositeAnnealing::default_final_temperature = 0.9;
const float CrownCompositeAnnealing::default_max_transformations = 2;
const float CrownCompositeAnnealing::default_max_new_states = 2;
const float CrownCompositeAnnealing::default_distance = 0.5;

Algebra
CrownCompositeAnnealing::neighbor(const Algebra &solution, float tasks, float cores) const
{
        Algebra schedule = solution;
        // distance == 1 -> change all neighbors by +- Wi processors
        // distance == 0 -> change only one neighbor by 1 processor

        map<int, float> vector_wi = schedule.find<Vector<int, float> >("wi")->getValues();
        //int b = (int)schedule.find<Scalar<float> >("b")->getValue();
        int b = 2;
        int p = (int)schedule.find<Scalar<float> >("p")->getValue();
        const Vector<int, float> *Wi = schedule.find<Vector<int, float> >("Wi");
        map<int, float> vector_Wi = Wi->getValues();
        int n = vector_wi.size();

        int num_tasks = ((int)((float)rand() / (float)RAND_MAX * n * tasks));
        while (num_tasks > 0 && vector_Wi.size() > 0)
        {
                int size = vector_Wi.size();
                map<int, float>::iterator itask = vector_Wi.begin();
                int index = rand() % size;

                for(int i = 0; i < index; i++)
                {
                        itask++;
                }

                // If a task is sequential, there is no neighbor to find there, remove that task from list and continue
                if(itask->second < 2)
                {
                        vector_Wi.erase(itask);
                        continue;
                }

                // Task maximal width > 1 (Wit > 0)
                int task = itask->first;
                int Wit = (int)vector_Wi[task];
                Wit = Wit > p ? p : Wit;
                Wit = (int)(log(Wit) / log(b));

                // task current allocated width
                int wi = (int)(log(vector_wi.find(task)->second) / log(b));

                int amplitude = Wit * (int)cores; // + 1 to count the number of possibilities, -1 to remove the current allocation from possible new allocation
                amplitude = amplitude < 1 ? 1 : amplitude; // Make sure at least one transformation is performed

                // Count how many spots are available below and above current wi
                int avail_lower = wi;
                int avail_higher = Wit - wi;
        
                // Cound how many spots we need below and above current wi
                int wi_lower, wi_higher;
                if(rand() % 2 == 0)
                {
                        wi_lower = (int)floor((float)amplitude / 2);
                        wi_higher = (int)ceil((float)amplitude / 2);
                }
                else
                {
                        wi_lower = (int)ceil((float)amplitude / 2);
                        wi_higher = (int)floor((float)amplitude / 2);
                }
                
                int len_lower, len_higher;
                if(avail_lower >= wi_lower && avail_higher >=wi_higher)
                {
                        len_lower = wi_lower;
                        len_higher = wi_higher;
                }
                else if(avail_lower < wi_lower)
                {
                        len_lower = avail_lower;
                        len_higher = wi_higher + (wi_lower - avail_lower);
                }
                else if(avail_higher < wi_higher)
                {
                        len_higher = avail_higher;
                        len_lower = wi_lower + (wi_higher - avail_higher);
                }
                else
                {
                        // Not enough space to fit the amplitude, aborting
                        cerr << "# Not enough allocation opportunities to fit the amplitude" << endl;
                        cerr << "# Task " << task << "; p = " << p << "; log2(Wi) = " << Wit << "; log2(wi) = " << wi << "; amplitude = " << amplitude << "; avail_lower = " << avail_lower << "; avail_higher = " << avail_higher << "; wi_lower = " << wi_lower << "; wi_higher = " << wi_higher << endl; 
                        abort();
                }

                int alternative = ((int)rand() % (amplitude)) + 1; // Start counting the new allocation number with 1
                int new_wi = 0;
                if(alternative <= len_lower)
                {
                        new_wi = wi - (len_lower - alternative + 1);
                }
                else if(alternative <= len_lower + len_higher)
                {
                        new_wi = wi + alternative - len_lower;
                }
                else
                {
                        cerr << "# Chosen alternative is beyond the spots available" << endl;
                        cerr << "# Task " << task << "; p = " << p << "; log2(Wi) = " << Wit << "; log2(wi) = " << wi << "; amplitude = " << amplitude << "; avail_lower = " << avail_lower << "; avail_higher = " << avail_higher << "; wi_lower = " << wi_lower << "; wi_higher = " << wi_higher << "; alternative = " << alternative << endl; 
                        len_lower = avail_lower;
                        len_higher = wi_higher + (wi_lower - avail_lower);
                }
                        
                if(wi == new_wi || new_wi > Wit || new_wi < 0)
                {
                        cerr << "# Task " << task << "; Wi " << Wit << "; wi " << wi << "; amplitude " << amplitude << "; new_wi " << new_wi << endl;
                        abort();
                }

                new_wi = (int)pow((double)b, (double)new_wi);
                if(new_wi == 64)
                {
                        cerr << "# Task " << task << "; Wi " << Wit << "; wi " << wi << "; amplitude " << amplitude << "; new_wi " << new_wi << endl;
                }
                vector_wi[task] = new_wi;

                // Done with this task, continue with the next
                vector_Wi.erase(itask);
                num_tasks--;

        }

        Vector<int, float> wi("wi", vector_wi);
        schedule.insert(&wi);

        return schedule;
}

float
CrownCompositeAnnealing::energy(const Algebra &solution)
{
        Algebra rec = crownToSchedule(solution);
        int n = rec.find<Scalar<float> >("n")->getValue();
        int p = rec.find<Scalar<float> >("p")->getValue();
        float M = rec.find<Scalar<float> >("M")->getValue();
        float kappa = rec.find<Scalar<float> >("kappa")->getValue();
        float eta = rec.find<Scalar<float> >("eta")->getValue();
        float zeta = rec.find<Scalar<float> >("zeta")->getValue();
        float alpha = rec.find<Scalar<float> >("alpha")->getValue();
        Vector<int, float> tau = rec.find<Vector<int, float> >("Tau");
        const Vector<int, string> *nameptr = rec.find<Vector<int, string> >("name");
        Vector<int, string> name("name", nameptr != NULL ? nameptr->getValues() : map<int, string>());
        Vector<int, float> Wi = rec.find<Vector<int, float> >("Wi");
        Vector<int, float> frequency = rec.find<Vector<int, float> >("frequency");
        Set<float> F = rec.find<Set<float> >("F");
        Matrix<int, int, float> e = rec.find<Matrix<int, int, float> >("e");
        Matrix<int, int, float> schedule = rec.find<Matrix<int, int, float> >("schedule");
        Vector<int, float> wi = rec.find<Vector<int, float> >("wi");
        vector<double> busy_task(n, 0);
        vector<double> area_task(n, 0);
        vector<double> met_task(n, 0);
        
        float lowest_freq = *(F.getValues().begin());
        kappa = kappa * lowest_freq;
        eta = eta * (zeta * pow(lowest_freq, alpha) + (1 - zeta) * (lowest_freq + kappa)) / zeta;
        double idle_energy = p * M * pow(lowest_freq, alpha);
        double busy_energy = 0;

        map<float, int> core_active;
        for(size_t i = 0; i < (size_t)p; i++)
        {
                core_active[i + 1] = 0;
        }
        int total_core_active = 0;

        // Iterate through all task names until we find the dummy task;
        vector<size_t> dummy_index;
        size_t index = 0;
        for(map<int, string>::const_iterator i = name.getValues().begin(); i != name.getValues().end(); i++, index++)
        {
                stringstream ss;
                ss << DUMMY_TASK << " " << index + 1;
                if(string(i->second).compare(ss.str()) == 0)
                {
                        dummy_index.push_back(index + 1);       
                }
        }

        // Now evaluate the quality of this schedule
        float total_area = 0;
        for(map<int, map<int, float> >::const_iterator i = schedule.getValues().begin(); i != schedule.getValues().end(); i++)
        {
                //int core = i->first;
                for(map<int, float>::const_iterator j = i->second.begin(); j != i->second.end(); j++)
                {
                        //int index = j->first;
                        int task = j->second;
                        //cout << "Core " << core << ", task " << task << endl;

                        // Check if the task index is a dummy task
                        bool dummy = false;
                        for(size_t k = 0; k < dummy_index.size(); k++)
                        {
                                if((size_t)task == dummy_index[k])
                                {
                                        dummy = true;
                                        break;
                                }
                        }

                        // We don't take dummy task power consumption into account
                        if(task > 0 && !dummy)
                        {
                                float width_t = wi.getValues().find(task)->second;
                                double time = (double)tau.find(task) / (width_t * e.find(width_t, task) * (double)frequency.find(task));
                                total_area += time;
                                float power = (zeta * pow(frequency.find(task), alpha) + (1 - zeta) * (frequency.find(task) + kappa)) / zeta;
                                busy_energy += time * power;

                                // Mark this core as active
                                if(core_active[i->first] == 0)
                                {
                                        core_active[i->first] = 1;
                                        total_core_active++;
                                }
                        }
                }
        }

        idle_energy = (M * (total_core_active) - total_area) * eta;

        return zeta * busy_energy + (1 - zeta) * idle_energy;
}

Algebra
CrownCompositeAnnealing::solve(const Algebra &tg, const Algebra &pt, const pelib::Algebra &parameters, std::map<const std::basic_string<char>, double> &stats) const
{
        Algebra param = parameters;
        const Scalar<float> *b = param.find<Scalar<float> >("b");
        Scalar<float> bb("b", 2);
        if(b == NULL)
        {
                param.insert(new Scalar<float>("b", 2));
                b = param.find<Scalar<float> >("b");
                b = &bb;
        }
        float p = pt.find<Scalar<float> >("p")->getValue();
        Algebra best_schedule;

        if(b != NULL && p == pow(b->getValue(), floor(log(p) / log(b->getValue()))))
        {
                struct timespec start, stop, total_time;
                //Algebra schedule = tg.merge(pt);
                //schedule = schedule.merge(param);
                clock_gettime(CLOCK_MONOTONIC, &start);

                // Run Crown binary
                Algebra schedule = scheduler->solve(tg, pt, param, stats);
                //Algebra schedule = crown_binary(best, 0);

                //best_schedule = crown_binary_annealing_allocation(schedule, this->init_temperature, this->cooling_factor, this->final_temperature, this->max_transformations, this->max_new_states, this->distance);

        schedule = this->neighbor(schedule, distance, 0);

        float m;
        int counter = 0;
        float T = init_temperature;

        Algebra best = schedule;
        //float best_q = quality(best);
        float best_q = energy(best);
        Vector<int, float> *best_solution = best.find<Vector<int, float> >("wi")->clone();
        float q = best_q; //quality(schedule);

        while (T > final_temperature)
        {
                int new_state = 0;

                for(int i = 0; i < max_transformations; i++)
                {
                        // Keep track of the solution of last iteration
                        Vector<int, float> *old_solution = schedule.find<Vector<int, float> >("wi")->clone();
                        float old_q = q;

                        // Transform the solution
                        schedule = neighbor(schedule, distance, 0);
                        schedule = this->mapping->map(schedule, stats);
                        schedule = this->scaling->scale(schedule, stats);
                        //schedule = mapping_ltlg(schedule);
                        //schedule = frequency_height(schedule);

                        m = schedule.find<Scalar<float> >("m")->getValue();
                        //q = quality(schedule);
                        q = energy(schedule);
                        
                        // If the new energy is lower than the previous one, then we accept this solution
                        if (q - old_q <= 0 && m >= 0)
                        {
                                delete old_solution;

                                // If this solution is better than the best found so far, then keep this best solution
                                if (q < best_q)
                                {
                                        best_solution = schedule.find<Vector<int, float> >("wi")->clone();
                                        best_q = q;
                                }

                                // One new state validated
                                new_state++;
                        }
                        else
                        {
                                // Randomly accept a degrading solution, more likely when the temperature is higher
                                if (rand() / RAND_MAX <= exp(-(q - old_q) / T) && m >= 0)
                                {
                                        // Update current solution
                                        delete old_solution;

                                        // One new state validated
                                        new_state++;
                                }
                                else
                                {
                                        // Revert old solution 
                                        schedule.insert(old_solution);
                                        q = old_q;
                                }
                        }
                        
                        // Too much successful transformations
                        if(new_state == max_new_states) 
                        {
                                break;
                        }
                }
        
                T = T * cooling_factor;
                counter++;
        }

        schedule.insert(best_solution);
        schedule = this->mapping->map(schedule, stats);
        schedule = this->scaling->scale(schedule, stats);
        //schedule = mapping_ltlg(schedule);
        //schedule = frequency_height(schedule);

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

                // Report mapping quality
                //float best_quality = best_schedule.find<Scalar<float> >("quality")->getValue();
                //stats.insert(pair<string, double>("quality", best_quality));

                // Report optimization time
                float time = (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec;
                stats.insert(pair<string, double>("time", time));

                return schedule;
        }
        else
        {
                throw CrownException("Simulated annealing does not support non-power of two number of cores or non-balanced binary configured Crown Scheduler");
        }
}

void
CrownCompositeAnnealing::initialize(const CrownMapping *mapping, const CrownScaling *scaling)
{
        CrownAllocationFastest alloc;
        if(mapping == NULL)
        {
                this->mapping = new CrownMappingLTLG(config, &alloc, showOutput, showError);
        }
        else
        {
                this->mapping = mapping->clone();
        }

        if(scaling == NULL)
        {
                this->scaling = new CrownScalingHeight(config, &alloc, mapping, showOutput, showError);
        }
        else
        {
                this->scaling = scaling->clone();
        }
}

CrownCompositeAnnealing::CrownCompositeAnnealing(float init_temperature, float cooling_factor, float final_temperature, float max_transformations, float max_new_states, float distance, const CrownScheduler *scheduler, const CrownMapping *map, const CrownScaling *scale, bool showOutput, bool showError) : CrownComposite(scheduler, showOutput, showError)
{
        this->init_temperature = init_temperature;
        this->cooling_factor = cooling_factor;
        this->final_temperature = final_temperature;
        this->max_transformations = max_transformations;
        this->max_new_states = max_new_states;
        this->distance = distance;
        initialize(map, scale);
}

CrownCompositeAnnealing::CrownCompositeAnnealing(const Algebra &param, float init_temperature, float cooling_factor, float final_temperature, float max_transformations, float max_new_states, float distance, const CrownScheduler *scheduler, const CrownMapping *map, const CrownScaling *scale, bool showOutput, bool showError) : CrownComposite(param, scheduler, showOutput, showError)
{
        this->init_temperature = init_temperature;
        this->cooling_factor = cooling_factor;
        this->final_temperature = final_temperature;
        this->max_transformations = max_transformations;
        this->max_new_states = max_new_states;
        this->distance = distance;
        initialize(map, scale);
}

CrownCompositeAnnealing::CrownCompositeAnnealing(const Taskgraph &tg, const Platform &pt, const Algebra &param, float init_temperature, float cooling_factor, float final_temperature, float max_transformations, float max_new_states, float distance, const CrownScheduler *scheduler, const CrownMapping *map, const CrownScaling *scale, bool showOutput, bool showError) : CrownComposite(tg, pt, param, scheduler, showOutput, showError)
{
        this->init_temperature = init_temperature;
        this->cooling_factor = cooling_factor;
        this->final_temperature = final_temperature;
        this->max_transformations = max_transformations;
        this->max_new_states = max_new_states;
        this->distance = distance;
        initialize(map, scale);
}

CrownCompositeAnnealing::CrownCompositeAnnealing(const CrownCompositeAnnealing &src) : CrownComposite(src.tg, src.pt, src.param, src.scheduler, src.showOutput, src.showError)
{
        this->init_temperature = init_temperature;
        this->cooling_factor = cooling_factor;
        this->final_temperature = final_temperature;
        this->max_transformations = max_transformations;
        this->max_new_states = max_new_states;
        this->distance = distance;
        initialize(src.mapping, src.scaling);
}

float
CrownCompositeAnnealing::complexity(const Algebra &problem) const
{
        return 0;
        //return max_transform * ceil(log(temperature / final) / log(1 / cooling));
}

float
CrownCompositeAnnealing::complexity(const Taskgraph&, const Platform&, const Algebra&) const
{
        return 0;
        //return max_transform * ceil(log(temperature / final) / log(1 / cooling));
}

CrownCompositeAnnealing*
CrownCompositeAnnealing::clone() const
{
        CrownCompositeAnnealing *sched = new CrownCompositeAnnealing(*this);
        return sched;
}

Schedule
CrownCompositeAnnealing::schedule(const Taskgraph &tg, const Platform &pt, std::map<const string, double>& stats) const
{
        Algebra param = this->param;

        // TODO: Make scheduler work without scalar b
        param.insert(new Scalar<float>("b", 2));
        param = param.merge(scheduler->addCrownConfig(tg, pt, param, stats));

        // Take task name out
        Algebra taskgraph = tg.buildAlgebra(pt);
        Vector<int, string> name = *taskgraph.find<Vector<int, string> >("name");
        taskgraph.remove("name");

        //Perform actual work
        Algebra schedule = solve(taskgraph, pt.buildAlgebra(), param, stats);

        // Put back task names
        schedule.insert(new Vector<int, string>(name));

        // Convert crown schedule to regular algebra schedule
        schedule = CrownScheduler::crownToSchedule(schedule);

        // Add task starting time
        schedule = Schedule::addStartTime(schedule, tg, pt);

        // report scheduling complexity
        float complexity = this->complexity(tg, pt, param);
        stats.insert(pair<string, double>("complexity", complexity));

        float M = tg.getDeadline(pt);
        float m = schedule.find<Scalar<float> >("m")->getValue();
        Schedule *sched;
        if(m < 0 && M > 0)
        {
                stats.insert(pair<string, double>("feasible", 0));
                sched = new Schedule(getShortDescription(), tg.getName(), Schedule::table());
        }
        else
        {
                stats.insert(pair<string, double>("feasible", 1));
                sched = new Schedule(getShortDescription(), tg.getName(), schedule);
        }

        Schedule final = *sched;
        delete sched;
        return final;
}

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

std::string
CrownCompositeAnnealing::getShortDescription() const
{
        return string("Ann.") + scheduler->getShortDescription();
}