src/CrownMappingLTLG.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 <fstream>
#include <cstdlib>
#include <set>
#include <map>

#include <crown/allocation.h>
#include <crown/mapping.h>
#include <crown/scaling.h>
#include <crown/crown.h>
#include <crown/CrownMappingLTLG.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>

#include <pelib/ParseException.hpp>
#include <pelib/AmplInputScalar.hpp>
#include <pelib/AmplInputVector.hpp>
#include <pelib/AmplInputSet.hpp>
#include <pelib/AmplInputMatrix.hpp>
#include <pelib/Scalar.hpp>
#include <pelib/Algebra.hpp>
#include <pelib/AmplOutputScalar.hpp>
#include <pelib/AmplOutputVector.hpp>
#include <pelib/AmplOutputSet.hpp>
#include <pelib/AmplOutputMatrix.hpp>
#include <pelib/AmplOutput.hpp>

#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/io.hpp>

#ifdef debug
#undef debug
#endif

#if LONGEST_WIDEST_LOWEST_TASK_FIRST
#undef LONGEST_WIDEST_TASK_FIRST
#define LONGEST_WIDEST_TASK_FIRST 1
#endif

#if LONGEST_WIDEST_TASK_FIRST
#undef LONGEST_TASK_FIRST
#define LONGEST_TASK_FIRST 1
#endif

#if 01
#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;
using namespace boost::numeric::ublas;

static const long long int nsec_in_sec = 1000000000;
static int ROOTNUMBER = 1;

// Group structure containing the number of the group, its height, width descendants and ancestors
struct Group
{
    int number;
    float time;
    int width;
    std::vector<int> sons;
    std::vector<int> parents;

    Group(int gn, int gt, int gw)
        {
            number = gn;
            time = gt;
            width = gw;
            sons = std::vector<int>();
            parents = std::vector<int>();
        }
};

typedef std::vector<pair<int, int> > mapping_t;
typedef std::map<int, float> RowType;
typedef std::map<int, RowType> MatrixType;

static map<int, Group*> groupmap;

// Needed to compare two int elements in a group number set
struct cmp_groupnumber_time : binary_function <int, int, bool>
{
    bool operator()(const int& x, const int& y) const
        {
            // Operand groups' time
            float xtime = groupmap[x]->time;
            float ytime = groupmap[y]->time;

            return xtime == ytime ? x < y : xtime < ytime;
        }
};

static map<int, multiset<int, cmp_groupnumber_time> > groupqueue;

static Algebra *rec;
static mapping_t schedule;
static map<int, float> vector_Wi;
static map<int, float> vector_Tau;
static map<int, float> vector_wi;
static MatrixType matrix_e;
static MatrixType matrix_tree;
static MatrixType matrix_groups;
static int n, p;

static float update_group_time(int gn, float time_offset, int task_wi)
{
    float res = 0;
    if(gn > 0)
    {
        float time = groupmap[gn]->time;
        groupqueue.find(task_wi)->second.erase(gn);
        groupmap[gn]->time += time_offset;
        groupqueue.find(task_wi)->second.insert(gn);
        res = time + time_offset;
        
    }
    else
    {
        // Not supposed to be here, something is wrong with the group number
        debug("Something is wrong with the group you try to update, you may want to check the allocation phase");
        debug(gn);
    }

    return res;
}

static float update_time(int gn, float time_offset, int task_wi)
{
    double son, max;
    
    max = update_group_time(gn, time_offset, task_wi);
    if (gn > ROOTNUMBER) {
        for(std::vector<int>::iterator it = groupmap[gn]->sons.begin() ; it != groupmap[gn]->sons.end() ; it++)
        {
            son = update_group_time(*it, time_offset, groupmap[*it]->width);
            if(son > max)
            {
                max = son;
            }
        }
        for(std::vector<int>::iterator it = groupmap[gn]->parents.begin() ; it != groupmap[gn]->parents.end(); it++)
        {
            update_group_time(*it, max - groupmap[*it]->time, groupmap[*it]->width);
        }
    }
    return max;
}

static float Tau(int task)
{
    return vector_Tau.find(task)->second;
}

static float wi(int task)
{
    int return_wi = (int)vector_wi.find(task)->second;

    return return_wi;
}

static float e(int task, int p)
{
    return matrix_e.find(task)->second.find(p)->second;
}

static float work(int task, int p)
{
    float return_work = Tau(task) / e(task, p);
    return return_work;
}

static float time(int task, int p)
{
    float return_time = work(task, p) / (float)p;
    return return_time;
}

#if LONGEST_TASK_FIRST
// Needed tp compare two group_time_t elements in the set whose definition comes right after
struct cmp_task : binary_function <int, int, bool>
{
    bool
    operator()(const int& x, const int& y) const
        {
#if LONGEST_WIDEST_TASK_FIRST
            if(time(x, wi(x)) == time(y, wi(y)))
            {
#if LONGEST_WIDEST_LOWEST_TASK_FIRST
                if(wi(x) == wi(y))
                {
                    return x < y;
                }
                else
                {
#endif
                    return wi(x) > wi(y);
#if LONGEST_WIDEST_LOWEST_TASK_FIRST
                }
#endif
            }
            else
            {
#endif
                return time(x, (int)wi(x)) > time(y, (int)wi(y));
#if LONGEST_WIDEST_TASK_FIRST
            }
#endif
        }
};
static multiset<int, cmp_task> ordered_tasks;
#endif

static void parse()
{
    schedule = mapping_t();
    vector_Wi = map<int, float>();
    vector_Tau = map<int, float>();
    vector_wi = map<int, float>();
    matrix_e = MatrixType();
    AmplInput data(AmplInput::floatHandlers());
    groupmap = map<int, Group*>();
    groupqueue = map<int, multiset<int, cmp_groupnumber_time> >();
    
    // Read all values
    n = (int)rec->find<Scalar<float> >("n")->getValue();
    p = (int)rec->find<Scalar<float> >("p")->getValue();

    vector_Wi = rec->find<Vector<int, float> >("Wi")->getValues();
    vector_Tau = rec->find<Vector<int, float> >("Tau")->getValues();
    vector_wi = rec->find<Vector<int, float> >("wi")->getValues();
    matrix_e = rec->find<Matrix<int, int, float> >("e")->getValues();
    matrix_groups = rec->find<Matrix<int, int, float> >(CrownConfig::crownConfigGroups)->getValues();
    matrix_tree = rec->find<Matrix<int, int, float> >(CrownConfig::crownConfigTree)->getValues();

    // creating the group map and setting the width : p(2p-1) = 2p²-p = O(p²)
    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++;
        }
    }

    // setting the inheritance : (2p-1)² = 4p²-4p+3 = O(p²)
    for(unsigned int i = 1 ; i <= matrix_tree.size() ; ++i)
    {
        for(unsigned int j = 1 ; j <= matrix_tree.begin()->second.size() ; ++j)
        {
            if(matrix_tree.find(i)->second.find(j)->second)
            {
                groupmap[j]->sons.push_back(i);
                groupmap[i]->parents.push_back(j);
            }
        }
    }

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

static float group_recursive_load(int g, int b, int p, float *group)
{
    int i;
    float load, max_load = 0;

    for(i = g * b; i < (g + 1) * b && i < 2 * p; i++)
    {
        load = group_recursive_load(i, b, p, group);
        if(load > max_load) max_load = load;
    }

    return max_load + group[g - 1];
}

CrownMappingLTLG::CrownMappingLTLG(const CrownConfig *config, const CrownAllocation *alloc, bool showOutput, bool showError) : CrownMapping(config, alloc, showOutput, showError)
{
    /* Do nothing else */
}

CrownMappingLTLG::CrownMappingLTLG(const Algebra &param, const CrownConfig *config, const CrownAllocation *alloc, bool showOutput, bool showError): CrownMapping(param, config, alloc, showOutput, showError)
{
    /* Do nothing else */
}

CrownMappingLTLG::CrownMappingLTLG(const Taskgraph &tg, const Platform &pt, const Algebra &param, const CrownConfig *config, const CrownAllocation *alloc, bool showOutput, bool showError): CrownMapping(tg, pt, param, config, alloc, showOutput, showError)
{
    /* Do nothing else */
}

CrownMappingLTLG::CrownMappingLTLG(const CrownMappingLTLG &src) : CrownMapping(src)
{
    // Do nothing else
}

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

    rec = &input;
    parse();
    clock_gettime(CLOCK_MONOTONIC, &start);
    
#if LONGEST_TASK_FIRST
    ordered_tasks = multiset<int, cmp_task>();
    for(int i = 0 ; i < n ; i++) // O(n)
    {
        ordered_tasks.insert(i+1); // O(log n)
    }
#endif
    
    // Use a temporary vector to reduce asymptotic time with n
    std::vector<pair<int, float> > schedule_vector;

#if LONGEST_TASK_FIRST
    for(set<int>::iterator iter = ordered_tasks.begin() ; iter != ordered_tasks.end() ; iter++)
#else
        for(int i = 0 ; i < n ; i++)
#endif
        {
            int task;
#if LONGEST_TASK_FIRST
            task = *iter;
#else
            task = i + 1;
#endif
            float task_wi = wi(task);
            float task_time = time(task, (int)task_wi);
            multiset<int, cmp_groupnumber_time> groups = groupqueue.find(task_wi)->second;
            int group = *(groups.begin());
            
            schedule_vector.push_back(pair<int, int>(task, group));
            update_time(group, task_time, task_wi);

        }

    clock_gettime(CLOCK_MONOTONIC, &stop);
    // Build the final schedule cppelib structure from schedule_vector
    // Outside time measurement
    for(std::vector<pair<int, float> >::iterator iter = schedule_vector.begin(); iter != schedule_vector.end(); iter++)
    {
        ::schedule.push_back(pair<int, int>(iter->first, (int)iter->second));
    }
    
    pelib_timespec_subtract(&total_time, &stop, &start);
    stats.insert(pair<const string, double>("time_mapping", (total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec));
    // Make
    std::map<int, float> vector_group;
    bool all_sequential = true;
    for(mapping_t::iterator iter = ::schedule.begin(); iter != ::schedule.end(); iter++)
    {
        all_sequential = all_sequential && wi(iter->first) == 1;
        vector_group.insert(pair<int, int>(iter->first, iter->second));
        // debug(iter->first);
        // debug(iter->second);
    }
    Vector<int, float> group("group", vector_group);
    rec->insert(&group);
    
    //AmplInput(AmplInput::intFloatHandlers()).dump(cout, rec->find<Vector<int, float> >("group"));
    
    return input;
}

float CrownMappingLTLG::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 CrownMappingLTLG::complexity(const pelib::Algebra &input) const
{
    float n = input.find<Scalar<float> >("n")->getValue();
    float p = input.find<Scalar<float> >("p")->getValue();
    return n * (p * log(p) + log(p) * log(p));
}

std::string CrownMappingLTLG::getShortDescription() const
{
    stringstream ss;
    std::streamsize p = ss.precision();
    ss.precision(4);
    ss << "newLTLG";
    ss.precision(p);
    return ss.str();
}

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