src/CrownScheduler.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/Vector.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/Set.hpp>
#include <pelib/AmplSolver.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/AmplInput.hpp>

#include <crown/CrownScheduler.hpp>
#include <crown/CrownConfigBinary.hpp>
#include <crown/CrownException.hpp>

#ifdef debug
#undef debug
#endif

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

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

CrownConfig*
CrownScheduler::getDefaultConfig() const
{
    return new CrownConfigBinary();
}

Algebra
CrownScheduler::addCrownConfig(const Taskgraph &tg, const Platform &pt, const Algebra &p, std::map<const string, double> &stats) const
{
    Algebra param = p;
    if(config != NULL)
    {
        // Use config generator to create crown configuration
        if(param.find<Matrix <int, int, float> >(CrownConfig::crownConfigGroups) != NULL)
        {
            param.remove(CrownConfig::crownConfigGroups);
        }

        if(param.find<Matrix <int, int, float> >(CrownConfig::crownConfigTree) != NULL)
        {
            param.remove(CrownConfig::crownConfigTree);
        }

        Algebra crownConfig = config->configure(tg, pt, p, stats);
        const Matrix<int, int, float> *conf = crownConfig.find<Matrix<int, int, float> >(CrownConfig::crownConfigGroups);
        param.insert(conf);
        conf = crownConfig.find<Matrix<int, int, float> >(CrownConfig::crownConfigTree);
        param.insert(conf);
    }
    else if(param.find<Matrix <int, int, float> >(CrownConfig::crownConfigGroups) == NULL ||
            param.find<Matrix <int, int, float> >(CrownConfig::crownConfigTree) == NULL)
    {
        // No config generator, use balanced binary tree
        if(param.find<Matrix <int, int, float> >(CrownConfig::crownConfigGroups) != NULL)
        {
            param.remove(CrownConfig::crownConfigGroups);
        }

        if(param.find<Matrix <int, int, float> >(CrownConfig::crownConfigTree) != NULL)
        {
            param.remove(CrownConfig::crownConfigTree);
        }
                
        CrownConfig *config = this->getDefaultConfig();
        Algebra crownConfig = config->configure(tg, pt, p, stats);
        delete config;
        const Matrix<int, int, float> *conf = crownConfig.find<Matrix<int, int, float> >(CrownConfig::crownConfigGroups);
        param.insert(conf);
        conf = crownConfig.find<Matrix<int, int, float> >(CrownConfig::crownConfigTree);
        param.insert(conf);
    }

    return param;
}

void
CrownScheduler::initialize(const CrownConfig *config)
{
    if(config == NULL)
    {
        this->config = new CrownConfigBinary();
    }
    else
    {
        this->config = config->clone();
    }
}

CrownScheduler::CrownScheduler(const CrownConfig* config, bool showOutput, bool showError)
{
    param.insert(new Scalar<float>("alpha", 3));
    param.insert(new Scalar<float>("eta", 0.018611));
    param.insert(new Scalar<float>("zeta", 0.649));
    param.insert(new Scalar<float>("kappa", 52.639161335));
    this->showError = showError;
    this->showOutput = showOutput;
    initialize(config);
}

CrownScheduler::CrownScheduler(const Algebra &param, const CrownConfig* config, bool showOutput, bool showError)
{
    this->param = param;
    this->showError = showError;
    this->showOutput = showOutput;
    initialize(config);
}

CrownScheduler::CrownScheduler(const Taskgraph &tg, const Platform &pt, const Algebra &p, const CrownConfig* config, bool showOutput, bool showError)
{
    this->tg = tg;
    this->pt = pt; // This one is the culprit
    this->param = p;
    this->showError = showError;
    this->showOutput = showOutput;
    initialize(config);
}

CrownScheduler::CrownScheduler(const CrownScheduler &src)
{
    this->tg = src.tg;
    this->pt = src.pt; // This one is the culprit
    this->param = src.param;
    this->showError = src.showError;
    this->showOutput = src.showOutput;
    initialize(src.config);
}

string
CrownScheduler::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;
    ss << "Crown-" << this->config->getShortDescription() << "(a=" << alpha << ",k=" << kappa << ",e=" << eta << ",z=" << zeta << ")";
    return ss.str();
}

const int b = 2;
typedef map<int, float> TaskWidthVector;
typedef map<int, float> TaskScheduleVector;
typedef map<int, TaskScheduleVector> ProcScheduleMatrix;

static
int
group_size(int group, int p, int b, const Vector<int, float> *size)
{
    if(size == NULL)
    {
        return p / (int)pow(b, floor((log(group) / log(b))));
    }
    else
    {
        return size->getValues().find(group)->second;
    }
}

struct cmp
{
    bool operator()(void *a, void *b)
        {
            set<void*, cmp> *aa = (set<void*, cmp>*)a;
            set<void*, cmp> *bb = (set<void*, cmp>*)b;

            if((size_t)a == (size_t)b)
            {
                return false;
            }

            if(aa->size() == bb->size())
            {
                return (size_t)a < (size_t)b;
            }
            else
            {
                return aa->size() < bb->size();
            }
        }
};

static size_t
build_schedule(set<void*, cmp> groups[], const set<void*, cmp> *root, const map<int, map<int, float> > &members, const map<int, float> &mapping, map<int, map<int, float> > &schedule)
{
    // Get number of cores
    size_t group = ((size_t)(root) - (size_t)(groups)) / sizeof(set<void*, cmp>) + 1;
    size_t num = 0;

    // Add all task into dorresponding processor
    for(map<int, float>::const_iterator i = mapping.begin(); i != mapping.end(); i++)
    {
        // Get the task and the group
        size_t task = i->first;

        // Add the task to schedule if the task is mapped to current group
        if(i->second == group)
        {
            // Add task to all processors member of current group
            for(map<int, float>::const_iterator j = members.find(group)->second.begin(); j != members.find(group)->second.end(); j++)
            {
                if((int)(j->second + 0.5) > 0)
                {
                    map<int, map<int, float> >::iterator iter = schedule.find(j->first);
                    map<int, float> sequence = iter->second;
                    schedule.erase(iter);
                    size_t size = sequence.size();
                    map<int, float>::iterator k;
                    for(k = sequence.begin(); k != sequence.end(); k++)
                    {
                        if(k->second == task)
                        {
                            break;
                        }
                    }
                    if(k == sequence.end())
                    {
                        sequence.insert(pair<int, float>(size + 1, task));
                    }
                    schedule.insert(pair<int, map<int, float> >(j->first, sequence));
                }
            }

            // Count number of tasks in this group
            num++;
        }
    }

    // Explore subgroups
    size_t max = 0;
    for(set<void*, cmp>::const_iterator i = root->begin(); i != root->end(); i++)
    {
        const set<void*, cmp> *subgroup = (set<void*, cmp>*)*i;
        size_t size = build_schedule(groups, subgroup, members, mapping, schedule);

        if(size > max)
        {
            max = size;
        }
    }

    return max + num;
}

const CrownConfig*
CrownScheduler::getCrownConfig() const
{
        return this->config;
}

Algebra
CrownScheduler::crownToSchedule(const Algebra &crown)
{
    std::ios_base::sync_with_stdio(true);
    Algebra res = crown;
    //int n = crown.find<Scalar<float> >("n")->getValue();
    int p = (int)crown.find<Scalar<float> >("p")->getValue();
    const Vector<int, float> *group = crown.find<Vector<int, float> >("group");
    const Vector<int, float> *size = crown.find<Vector<int, float> >("size");
    const Matrix<int, int, float> *precedence = crown.find<Matrix<int, int, float> >(CrownConfig::crownConfigTree);
    const Matrix<int, int, float> *member = crown.find<Matrix<int, int, float> >(CrownConfig::crownConfigGroups);
        
    //const Vector<int, float> *frequency = crown.find<Vector<int, float> >("frequency");
    vector<vector<int> > groups;
    TaskWidthVector task_width;
    ProcScheduleMatrix proc_schedule;
        
    // Create a collection of groups, each empty
    for(int group = 1; group <= 2 * p - 1; group++)
    {
        groups.push_back(vector<int>());
    }
        
    // Get the allocated width of each task
    for(map<int, float>::const_iterator i = group->getValues().begin(); i != group->getValues().end(); i++)
    {
        int task = i->first;
        int group = (int)i->second;
        
        // Get the width of the task
        task_width.insert(pair<int, float>(task, group_size(group, p, b, size)));
        // Insert the task in the relevant group
        groups[group - 1].push_back(task);
        
    }

    // Get the task sequence for each processor
    int max = 0; // This will hold the maximum number of tasks a core handles
    {
        // Compute the precedence tree
        // Initialize one set for each group
        set<void*, cmp> groups[2 * p - 1];
        set<void*, cmp> groupset;
        
        // Pre-insert empty groups
        for(size_t i = 0; i < (size_t)(2 * p - 1); i++)
        {
            void* stuff = (void*)&(groups[i]);
            groupset.insert(stuff);
        }

        const map<int, map<int, float> > pred = precedence->getValues();

        // Remove indirect inheritance links. For each group's direct of indirect ancestor group,
        // count the number or ancestor group this ancestor has.
        // The Ancestor group that has the most ancestor is the unique direct ancestor of
        // the group. If so, set the corresponding value to 1.
        map<int, map<int, float> > direct_pred = pred;
        map<int, size_t> ancestors;
        // For each group, count the number of ancestors
        for(map<int, map<int, float> >::const_iterator i = pred.begin(); i != pred.end(); i++)
        {
            size_t count = 0;
            for(map<int, float>::const_iterator j = i->second.begin(); j != i->second.end(); j++)
            {
                count += j->second;
            }
            ancestors.insert(pair<int, size_t>(i->first, count));
        }

        // For each group, browse the groups it depends on, and keep the highest number of dependencies
        for(map<int, map<int, float> >::const_iterator i = pred.begin(); i != pred.end(); i++)
        {
            size_t count = 0;
            for(map<int, float>::const_iterator j = i->second.begin(); j != i->second.end(); j++)
            {
                if(j->second > 0 && ancestors[j->first] > count)
                {
                    count = ancestors[j->first];
                }
            }

            // having the highest number of dependencies, set 1 to the groups having the same number of dependencies
            // (Only the unique direct ancestor), and remove the dependency marker to other groups (write 0).
            for(map<int, float>::const_iterator j = i->second.begin(); j != i->second.end(); j++)
            {
                float newval = 0;
                if(ancestors[j->first] == count && j->second > 0)
                {
                    newval = 1;
                }
                direct_pred.find(i->first)->second.find(j->first)->second = newval;
            }
        }

        // Build the crown tree: a groups is a set of groups, and it receives all its direct subgroups
        // If a group has a dependency to an ancestor group, then add the group to the ancestor group's
        // list of direct subgroups
        for(map<int, map<int, float> >::const_iterator i = direct_pred.begin(); i != direct_pred.end(); i++)
        {
            size_t ii = i->first - 1;
            for(map<int, float>::const_iterator j = i->second.begin(); j != i->second.end(); j++)
            {
                size_t jj = j->first - 1;
                if(j->second > 0)
                {
                    set<void*, cmp>::iterator k = groupset.find((void*)&groups[jj]);
                    set<void*, cmp> *kk = (set<void*, cmp>*)*k;
                    groupset.erase(k);
                    kk->insert((void*)&groups[ii]);
                    groupset.insert(kk);
                }
            }
        }

        // From the list of groups, remove all that appear in the list of subgroups of any group
        // Only teh subgroup remains after this step.
        for(size_t i = 0; i < (size_t)(2 * p - 1); i++)
        {
            for(set<void*, cmp>::iterator j = groups[i].begin(); j != groups[i].end(); j++)
            {
                set<void*, cmp>* jj = (set<void*, cmp>*)*j;
                if(groupset.find(jj) != groupset.end())
                {
                    groupset.erase(groupset.find(jj));
                }
            }
        }

        // Initialize an empty schedule
        for(size_t i = 0; i < (size_t)p; i++)
        {
            proc_schedule.insert(pair<int, map<int, float> >(i + 1, map<int, float>()));
        }

        // The root group is the only one left in the group collection
        set<void*, cmp> *root = (set<void*, cmp>*)*groupset.begin();
        // Build a schedule starting from the root group
        max = build_schedule(groups, root, member->getValues(), group->getValues(), proc_schedule);
    }

    // Fill smaller rows with task 0 so the matrix looks like a proper rectangle matrix
    for(int proc = 0; proc < p; proc++)
    {
        int size = proc_schedule[proc + 1].size();

        while(size < max)
        {
            size++;
            proc_schedule[proc + 1].insert(pair<int, float>(size, 0));
        }
    }

    Matrix<int, int, float> procSchedule = Matrix<int, int, float>("schedule", proc_schedule);
    res.insert(&procSchedule);

    return res;
}

CrownScheduler::~CrownScheduler()
{
    delete this->config;
}

float
CrownScheduler::complexity(const Algebra &problem) const
{
    return config->complexity(problem);
}

float
CrownScheduler::complexity(const Taskgraph &tg, const Platform &pt, const Algebra &param) const
{
    return config->complexity(tg, pt, param);
}

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

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