src/CrownBinary.cpp

Go to the documentation of this file.

/*
  Copyright 2015 Nicolas Melot

  This file is part of Pelib.

  Pelib is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  Pelib is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with Pelib. If not, see <http://www.gnu.org/licenses/>.
*/

#include <pelib/Algebra.hpp>
#include <pelib/Scalar.hpp>
#include <pelib/AmplSolver.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/AmplInput.hpp>
#include <pelib/time.h>

#include <crown/CrownBinary.hpp>
#include <crown/CrownAllocationFastest.hpp>
#include <crown/CrownMappingLTLG.hpp>
#include <crown/CrownScalingHeight.hpp>
#include <crown/CrownConfigBinary.hpp>
#include <crown/CrownException.hpp>

#include <crown/mapping.h>
#include <crown/scaling.h>
#include <crown/annealing.h>
#include <crown/crown.h>

#ifdef debug
#undef debug
#endif

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

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

static const long long int nsec_in_sec = 1000000000;

Algebra
CrownBinary::solve(const Algebra &tg, const Algebra &pt, const pelib::Algebra &param, std::map<const std::basic_string<char>, double> &stats) const
{
    float p = pt.find<Scalar<float> >("p")->getValue();
    float logp = pow(2, floor(log(p) / log(2)));
    Algebra best_schedule;

    if(p == logp || 1)
    {
        struct timespec start, stop, total_time;
        Algebra schedule = tg.merge(pt).merge(param);
        Algebra best = schedule;
        clock_gettime(CLOCK_MONOTONIC, &start);

        float threshold = 0.5;
        float delta = 0.25;
        float derivative, min_derivative = 1;
        unsigned int round = 0;
        float m = 0;
        Algebra current;
        float power = 0;

        // Compute allocation for maximal parallelization
        // This is is to get an allocation if nothing else works
        // Yet it is not guaranteed to produce a valid schedule
        // because of a still too high makespan presure

        set<string> after_alloc;
        // Taskgraph
        after_alloc.insert(string("M"));
        after_alloc.insert(string("Tau"));
        after_alloc.insert(string("Wi"));
        after_alloc.insert(string("c"));
        after_alloc.insert(string("e"));
        after_alloc.insert(string("n"));
        after_alloc.insert(string("name"));
        // Platform
        after_alloc.insert(string("F"));
        after_alloc.insert(string("Fi"));
        after_alloc.insert(string("Fin"));
        after_alloc.insert(string("Funit"));
        after_alloc.insert(string("p"));
        // Param
        for(std::map<std::string, const AlgebraData * const>::const_iterator i = param.getAllRecords().begin(); i != param.getAllRecords().end(); i++)
        {
            after_alloc.insert(string(i->first));
        }
        // Alloc step
        after_alloc.insert(string("wi"));
        // Mapping step
        set<string> after_mapping = after_alloc;
        after_mapping.insert(string("group"));
        // Scaling step
        set<string> after_scaling = after_mapping;
        after_scaling.insert(string("frequency"));
                
        float emax = 0, emin = 1;
        float previous = 1;
        map<int, map<int, float> > map_e = tg.find<Matrix<int, int, float> >("e")->getValues();
        map<int, float> map_Wi = tg.find<Vector<int, float> >("Wi")->getValues();
        for(map<int, map<int, float> >::iterator row_iter = map_e.begin(); row_iter != map_e.end(); row_iter++)
        {
            int task = row_iter->first;
            int Wi = (int)map_Wi[task];
            map<int, float> map_row = row_iter->second;
                                        
            for(map<int, float>::iterator col_iter = map_row.begin(); col_iter != map_row.end() && col_iter->first <= Wi; col_iter++)
            {
                if(col_iter->second < 1)
                {
                    if(col_iter->second > emax)
                    {
                        emax = col_iter->second;
                    }

                    if(col_iter->second < emin)
                    {
                        emin = col_iter->second;
                    }

                    derivative = previous - col_iter->second;
                    if(derivative < min_derivative)
                    {
                        min_derivative = derivative;
                    }
                }
            }
        }

        best = CrownAllocationFastest(0, showOutput, showError).allocate(best, stats).filter(after_alloc);
        best = this->mapping->map(best, stats).filter(after_mapping);
        best = this->scaling->scale(best, stats);
        best = best.merge(param);
        float best_power = energy_static_dynamic_busy_idle_active(best);

        // Binary search for maximal minimum efficiency for all tasks
        bool retry = true;

        // Try a whole sequential schedule
        current = schedule;
        current = CrownAllocationFastest(1, showOutput, showError).allocate(current, stats).filter(after_alloc);
        current = this->mapping->map(current, stats).filter(after_mapping);
        current = this->scaling->scale(current, stats);
        current = current.merge(param);

        // Check if this allocation could produce a valid mapping
        // m is the minimal slack time
        m = current.find<Scalar<float> >("m")->getValue();
        if(m > 0)
        {
            //power = quality(current);
            power = energy_static_dynamic_busy_idle_active(current);
            if(power <= best_power)
            {
                best_power = power;
                best = current;
            }
        }

        // Loop while the current threshold is lower than the maximum non-sequential efficiency
        // and delta is higher than the minimal efficiency gap between two allocations for any task
        // And, if any maximum round was given, this threshold was not reached
        while(retry && delta * 2 > min_derivative && ((precision != 0 && round < precision) || precision == 0))
        {
            // Reset the current solution to input
            current = schedule;

            // Allocate with current threshold then run mapping and frequency scaling
            current = CrownAllocationFastest(threshold, showOutput, showError).allocate(current, stats).filter(after_alloc);
            current = this->mapping->map(current, stats).filter(after_mapping);
            current = this->scaling->scale(current, stats);
        //Taskgraph ttg(tg);
        //Platform ppt(pt);
        //sched = new Schedule(getShortDescription(), tg.getName(), p);
        
                        
            // Check if this allocation could produce a valid mapping
            // m is the minimal slack time
            m = current.find<Scalar<float> >("m")->getValue();

            // Update the threshold after the feasibility
            if(m >= 0)
            {
                current = current.merge(param);
                //power = quality(current);
                power = energy_static_dynamic_busy_idle_active(current);
                // This is a valid schedule
                // Retry if current threshold is lower than maximal efficiency
                retry = threshold < emax;
                                
                // Increase threshold by delta
                threshold = threshold + delta;
                        
                // Keep this schedule as the best found so far
                if(power < best_power)
                {
                    best = current;
                    best_power = power;
                }
            }
            else
            {
                // This was an invalid schedule
                retry = true;
                                
                // Allow lower efficiency
                threshold = threshold - delta;                  
            }
            // Reduce the delta
            delta = delta / 2;

            // Count the number of rounds
            round++;
        }

        clock_gettime(CLOCK_MONOTONIC, &stop);

        // Report mapping quality
        stats.insert(pair<string, double>("quality", best_power));

        // Report optimization time
        pelib_timespec_subtract(&total_time, &stop, &start);
        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 best;
    }
    else
    {
        throw CrownException("Consolidation scheduler cannot handle non-power of two number of cores");
    }
}

Schedule
CrownBinary::schedule(const Taskgraph &tg, const Platform &pt, const Algebra &param, map<const string, double> &statistics) const
{
    // Take task names apart
    Algebra taskgraph = tg.buildAlgebra(pt);
    Vector<int, string> name = *taskgraph.find<Vector<int, string> >("name");
    taskgraph.remove("name");

    Algebra p = param.merge(config->configure(tg, pt, param, statistics));
    p = solve(taskgraph, pt.buildAlgebra(), p, statistics);

    float time = 0;
    map<const string, double>::iterator i = statistics.find("time_allocation");
    if(i != statistics.end())
    {
        time += i->second;
    }
    i = statistics.find("time_mapping");
    if(i != statistics.end())
    {
        time += i->second;
    }
    i = statistics.find("time_scaling");
    if(i != statistics.end())
    {
        time += i->second;
    }
    i = statistics.find("time_global");
    if(i != statistics.end())
    {
        statistics.erase(i);
    }
    statistics.insert(pair<const string, double>("time_global", time));
    
    // Put back task names
    p.insert(new Vector<int, string>(name));

    p = crownToSchedule(p);
    p = Schedule::addStartTime(p, tg, pt);

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

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

    Schedule final = *sched;
    delete sched;
    return final;
    //Schedule sched(getShortDescription(), tg.getName(), p);
    //return sched;
}

Schedule
CrownBinary::schedule(const Taskgraph &tg, const Platform &pt, map<const string, double> &statistics) const
{
    return schedule(tg, pt, param, statistics);
}

float
CrownBinary::complexity(const Algebra &problem) const
{
    return 0;
    //float complexity = pt.getCores().size() * 1 * (AllocationFastest().complexity(problem) + this->mapping->complexity(problem) + this->scaling->complexity(problem));
}

float
CrownBinary::complexity(const Taskgraph &tg, const Platform &pt, const Algebra &param) const
{
    return 0;
}

CrownBinary*
CrownBinary::clone() const
{
    return new CrownBinary(*this);
}

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

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

CrownBinary::CrownBinary(const CrownConfig *config, const CrownMapping *mapping, const CrownScaling *scaling, size_t precision, bool showOutput, bool showError) : CrownScheduler(config, showOutput, showError)
{
    initialize(mapping, scaling);

    // TODO: restore arbitrary configuration
    //delete this->config;
    //this->config = new CrownConfigBinary();
    this->precision = precision;
}

CrownBinary::CrownBinary(const Algebra &param, const CrownConfig *config, const CrownMapping *mapping, const CrownScaling *scaling, size_t precision, bool showOutput, bool showError) : CrownScheduler(config, showOutput, showError)
{
    initialize(mapping, scaling);

    // TODO: restore arbitrary configuration
    //delete this->config;
    //this->config = new CrownConfigBinary();
    this->precision = precision;
}

CrownBinary::CrownBinary(const Taskgraph &tg, const Platform &pt, const Algebra &param, const CrownConfig*, const CrownMapping *mapping, const CrownScaling *scaling, size_t precision, bool showOutput, bool showError) : CrownScheduler(config, showOutput, showError)
{
    initialize(mapping, scaling);

    // TODO: restore arbitrary configuration
    //delete this->config;
    //this->config = new CrownConfigBinary();
    this->precision = precision;
}

CrownBinary::CrownBinary(const CrownBinary &src) : CrownScheduler(src.tg, src.pt, src.param, src.config, src.showOutput, src.showError)
{
    initialize(src.mapping, src.scaling);

    // TODO: restore arbitrary configuration
    //delete this->config;
    //this->config = new CrownConfigBinary();
    this->precision = src.precision;
}

CrownBinary::~CrownBinary()
{
    delete this->mapping;
    delete this->scaling;
}

string
CrownBinary::getShortDescription() const
{
    float alpha = this->param.find<Scalar<float> >("alpha")->getValue();
    float kappa = this->param.find<Scalar<float> >("kappa")->getValue();
    float eta = this->param.find<Scalar<float> >("eta")->getValue();
    float zeta = this->param.find<Scalar<float> >("zeta")->getValue();
    stringstream ss;

    const CrownConfig *config = this->config;
    if(config == NULL)
    {
        config = getDefaultConfig();
    }

    std::streamsize p = ss.precision();
    ss.precision(4);
    string alloc = CrownAllocationFastest().getShortDescription();
    string mapping = this->mapping->getShortDescription();
    string scaling = this->scaling->getShortDescription();
    string conf = this->config->getShortDescription();
    ss << "Cr-Bin-";
    ss << alloc << "-";
    ss << mapping << "-";
    ss << scaling << "-";
    ss << conf << "(a=";
    ss << alpha << ",k=";
    ss << kappa << ",e=";
    ss << eta << ",z=";
    ss << zeta << ")";
    ss.precision(p);

    if(this->config == NULL)
    {
        delete config;
    }

    return ss.str();
}

const Algebra*
CrownBinary::solve() const
{
    map<const string, double> statistics;
    Algebra *sol = new Algebra(schedule(tg, pt, param, statistics).buildAlgebra());
    return sol;
}

const Algebra*
CrownBinary::solve(map<const string, double> &statistics) const
{
    Algebra *sol = new Algebra(schedule(tg, pt, param, statistics).buildAlgebra());
    return sol;
}