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

#ifdef debug
#undef debug
#endif

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

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

static
map<int, map<int, float> >
build_crown(size_t p, size_t wi, size_t skip, const map<int, map<int, float> > matrix, map<int, map<int, float> > &tree, const Platform::islands &isl)
{
        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 fo 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 = 0;
                Platform::islands::const_iterator i;
                for(i = isl.begin(); size < skip && i != isl.end(); i++)
                {
                        size += i->size();
                }
                if(size > skip && wi + skip > size)
                {
                        // This should never happen
                        throw CrownException("Configuring group misaligned with frequency islands");
                }

                // At this point, size = sum(size(all previous islands))
                size_t left = floor((float)wi / 2);
                Platform::islands::const_iterator j = i;
                j++;
                
                if(left > i->size() && j == isl.end())
                {
                        throw CrownException("Creating group spanning beyond last frequency island");
                }
        
                size_t next = i->size();
                for(; j != isl.end() && left > next; j++)
                {
                        next += j->size();
                }
                if(left < next && next < wi)
                {
                        left = next;
                }
                config = build_crown(p, left, skip, config, tree, isl);
                config = build_crown(p, wi - left, skip + left, config, tree, isl);
        }

        return config;
}

string
CrownConfigBinary::getShortDescription() const
{
        return string("bin");
}

Algebra
CrownConfigBinary::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();
        map<int, map<int, float> > tree;
        struct timespec start, stop, total_time;
        clock_gettime(CLOCK_MONOTONIC, &start); 
        map<int, map<int, float> > config = build_crown(p, p, 0, map<int, map<int, float> >(), tree, pt.getFrequencyIslands());
        clock_gettime(CLOCK_MONOTONIC, &stop);
        pelib_timespec_subtract(&total_time, &stop, &start);
        Algebra conf;

        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));
        conf.insert(new Matrix<int, int, float>(CrownConfig::crownConfigGroups, config));
        conf.insert(new Matrix<int, int, float>(CrownConfig::crownConfigTree, tree));

        return conf;
}

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

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

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

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