src/CrownConfigTaskgraph.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 <crown/CrownConfigTaskgraph.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/AmplInput.hpp>
#include <pelib/time.h>

#ifdef debug
#undef debug
#endif

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

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

size_t
pick_size(set<size_t> &sizes, size_t avail, size_t alt)
{
        size_t out;
        if(sizes.size() > 0 && *sizes.rbegin() >= floor(avail / 2))
        {
                out = *sizes.rbegin();
                sizes.erase(sizes.find(out));
        }
        else
        {
                out = alt;
        }

        return out;
}

static
map<int, map<int, float> >
build_crown(size_t p, size_t wi, size_t skip, set<size_t> &sizes, const map<int, map<int, float> > matrix, map<int, map<int, float> > &tree)
{
        map<int, map<int, float> > config = matrix;
        map<int, float> group;
        for(size_t i = 0; i < p; i++)
        {
                if(i < skip || i >= skip + wi)
                {
                        group.insert(pair<int, float>(i + 1, 0));
                }
                else
                {
                        group.insert(pair<int, float>(i + 1, 1));
                }
        }

        // Dependencies for this group
        map<int, float> deps;
        for(size_t i = 0; i < 2 * p - 1; i++)
        {
                deps.insert(pair<int, float>(i + 1, 0));
        }

        // Browse all other groups already formed
        for(map<int, map<int, float> >::iterator i = config.begin(); i != config.end(); i++)
        {
                // Browse all cores
                int ii = std::distance(config.begin(), i) + 1;
                for(map<int, float>::iterator j = i->second.begin(); j != i->second.end(); j++)
                {
                        int jj = std::distance(i->second.begin(), j) + 1;
                        // If both groups have the core, then there is a dependency link
                        if(group[jj] == j->second && j->second > 0)
                        {
                                deps[ii] = 1;
                                break;
                        }
                }
        }

        // Add groups membership and dependencies to temporary outcome
        config.insert(pair<int, map<int, float> >(config.size() + 1, group));
        tree.insert(pair<int, map<int, float> >(tree.size() + 1, deps));

        // Recurse, if necessary
        if(wi > 1)
        {
                size_t size_left = pick_size(sizes, wi, floor((float)wi / 2));
                if(sizes.find(wi - size_left) != sizes.end())
                {
                        sizes.erase(sizes.find(wi - size_left));
                }
                size_t size_right = wi - size_left;
                config = build_crown(p, size_left, skip, sizes, config, tree);
                config = build_crown(p, size_right, skip + size_left, sizes, config, tree);
        }

        return config;
}

string
CrownConfigTaskgraph::getShortDescription() const
{
        return string("tg");
}

Algebra
CrownConfigTaskgraph::configure(const Taskgraph &tg, const Platform &pt, const Algebra &param, map<const string, double> &stats) const
{
        // Compute a binary crown and place it in class' Algebra container
        size_t p = pt.getCores().size();
        struct timespec start, stop, total_time;

        // Cellects the width that yields the best ratio efficiency / parallel time for each task
        set<size_t> best_group_sizes;
        clock_gettime(CLOCK_MONOTONIC, &start); 
        for(set<Task>::const_iterator i = tg.getTasks().begin(); i != tg.getTasks().end(); i++)
        {
                debug(i->getName());
                size_t best_width = 1;
                float best_ratio = 0;
                for(size_t j = 0; j < p && j < i->getMaxWidth(); j++)
                {
                        debug(j + 1);
                        debug(i->runtime(j + 1));
                        debug(i->getEfficiency(j + 1));
                        float task_time = i->runtime(j + 1, 1);
                        float quality = i->getEfficiency(j + 1) / task_time;
                        debug(quality);
                        if(quality > best_ratio)
                        {
                                best_ratio = quality;
                                best_width = j + 1;
                                debug(best_width);
                        }
                }
                if(best_width < p)
                {
                        debug(best_width);
                        best_group_sizes.insert(best_width);
                }
        }

        map<int, map<int, float> > tree;
        map<int, map<int, float> > config = build_crown(p, p, 0, best_group_sizes, map<int, map<int, float> >(), tree);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        pelib_timespec_subtract(&total_time, &stop, &start);

        stats.insert(pair<const string, double>("time_config", (float)(total_time.tv_sec * pelib_nsec_in_sec + total_time.tv_nsec) / (float)pelib_nsec_in_sec));
        Algebra conf;
        conf.insert(new Matrix<int, int, float>(CrownConfig::crownConfigGroups, config));
        conf.insert(new Matrix<int, int, float>(CrownConfig::crownConfigTree, tree));

        return conf;
}

CrownConfigTaskgraph::~CrownConfigTaskgraph()
{
        // Do nothing
}

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

float
CrownConfigTaskgraph::complexity(const Algebra &problem) const
{
        return 0;
}

float
CrownConfigTaskgraph::complexity(const Taskgraph&, const Platform&, const Algebra&) const
{
        return 0;
}