src/CrownAllocationFastest.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/CrownAllocationFastest.hpp>
#include <crown/CrownConfigBinary.hpp>

#include <pelib/XMLSchedule.hpp>
#include <pelib/AmplInput.hpp>
#include <pelib/AmplOutput.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/Set.hpp>
#include <pelib/GraphML.hpp>
#include <pelib/Schedule.hpp>
#include <pelib/Task.hpp>
#include <pelib/time.h>

#ifdef debug
#undef debug
#endif

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

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

static const long long int nsec_in_sec = 1000000000;

// Group structure containing the number of the groupand its width
struct Group
{
    int number;
    int width;

    Group(int gn, int gt, int gw)
        {
            number = gn;
            width = gw;
        }
};

CrownAllocationFastest::CrownAllocationFastest(float gemin, bool showOutput, bool showError) : CrownAllocation(showOutput, showError)
{
    this->gemin = gemin;
}

Algebra
CrownAllocationFastest::allocate(const Algebra &alg, std::map<const string, double> &stats) const
{
    Algebra input = alg;
    struct timespec start, stop, total_time;

    // Read tasks's efficiency and decide on their optimal allocation
    int p = (int)input.find<Scalar<float> >("p")->getValue();

    map<int, float> vector_tau = input.find<Vector<int, float> >("Tau")->getValues();
    map<int, map<int, float> > matrix_e = input.find<Matrix<int, int, float> >("e")->getValues();
    map<int, float> vector_wi;
    map<int, map<int, float> > matrix_groups = input.find<Matrix<int, int, float> >(CrownConfig::crownConfigGroups)->getValues();
    set<int> vector_wig = set<int>();
    map<int, Group*> groupmap = map<int, Group*>();

    // Creating the group map and setting the width
    for(unsigned int i = 1 ; i <= matrix_groups.size() ; ++i)
    {
        groupmap.insert(std::make_pair(i, new Group(i, 0, 0)));
        for(unsigned int j = 1 ; j <= matrix_groups.begin()->second.size() ; ++j)
        {
            if(matrix_groups.find(i)->second.find(j)->second) groupmap[i]->width++;
        }
    }

    // Creating the group queue
    for(map<int, Group*>::iterator it = groupmap.begin() ; it != groupmap.end() ; ++it)
    {
        if(vector_wig.find(it->second->width) == vector_wig.end())
        {
            vector_wig.insert(it->second->width);
        }
    }

    clock_gettime(CLOCK_MONOTONIC, &start);     

    for(map<int, float>::iterator i = vector_tau.begin(); i != vector_tau.end(); i++)
    {
        int task = i->first;
        float max_efft = 0;
        int best_p = 0;

        map<int, float> et = matrix_e[task];
                
        for(map<int, float>::iterator j = et.begin(); j != et.end() && j->first <= p; j++)
        {
            int p = j->first;

            float e = j->second;
            float efft = p * e;

            if(max_efft < efft && e >= gemin && vector_wig.find(p) != vector_wig.end())
            {
                max_efft = efft;
                best_p = p;
            }
        }
        vector_wi.insert(pair<int, int>(task, best_p));
    }

    clock_gettime(CLOCK_MONOTONIC, &stop);
    pelib_timespec_subtract(&total_time, &stop, &start);
        
    stats.insert(pair<const string, double>("time", (total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec));

    Vector<int, float> *wi = new Vector<int, float>("wi", vector_wi);
    input.insert(wi);

    return input;
}

Taskgraph
CrownAllocationFastest::allocate(const Taskgraph &tg, const Platform &pt, const Algebra &param, const CrownConfig *config, std::map<const string, double> &stats) const
{
    Algebra alg = tg.buildAlgebra(pt);
    alg = alg.merge(pt.buildAlgebra());
    alg = alg.merge(param);
    if(config == NULL)
    {
        CrownConfigBinary conf;
        config = &conf;
    }
    alg = alg.merge(config->configure(tg, pt, param, stats));

    return Taskgraph(allocate(alg, stats));
}

float
CrownAllocationFastest::complexity(const Taskgraph &tg, const Platform &pt, const Algebra &param, const CrownConfig* config) const
{
    Algebra alg = tg.buildAlgebra(pt);
    alg = alg.merge(pt.buildAlgebra());
    alg = alg.merge(param);
    if(config == NULL)
    {
        CrownConfigBinary conf;
        config = &conf;
    }
    std::map<const string, double> stats;
    alg = alg.merge(config->configure(tg, pt, param, stats));

    return complexity(alg);
}

float
CrownAllocationFastest::complexity(const pelib::Algebra &schedule) const
{
    float n = schedule.find<Scalar<float> >("n")->getValue();
    float p = schedule.find<Scalar<float> >("p")->getValue();

    return n * p;
}

std::string
CrownAllocationFastest::getShortDescription() const
{
    stringstream ss;
    std::streamsize p = ss.precision();
    ss.precision(4);
    ss << "newFast";
    ss.precision(p);

    return ss.str();
}

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