src/CrownScalingHeight.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/CrownScalingHeight.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>

#ifdef debug
#undef debug
#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;

static const long long int nsec_in_sec = 1000000000;

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

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

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

struct task
{
    int id, group;
    double time_unscaled, time_scaled;
};
typedef struct task task_t;

// Compare two tasks based on their running time at some given frequency
struct compare_task_per_scaled_time : binary_function <task_t, task_t, bool>
{
    bool
    operator()(const task_t& t1, const task_t& t2) const
        {               
            if(t1.time_scaled == t2.time_scaled)
            {
                // If two tasks have the same time, then order them by id
                return t1.id < t2.id;
            }
            else
            {
                // Use the opposite comparison signe in this line to make increasing or decreasing task rescaling
                return t1.time_scaled > t2.time_scaled;
            }
        }
};

typedef multiset<task_t, compare_task_per_scaled_time> by_time_t;

static by_time_t
init_frequency_max(const Algebra &input)
{
    by_time_t tasks;

    set<float> F = input.find<Set<float> >("F")->getValues();
    double maxF = *F.rbegin();

    map<int, float> tau = input.find<Vector<int, float> >("Tau")->getValues();
    map<int, float> wi = input.find<Vector<int, float> >("wi")->getValues();
    map<int, map<int, float> > e = input.find<Matrix<int, int, float> >("e")->getValues();
    map<int, float> group = input.find<Vector<int, float> >("group")->getValues();

    for(map<int, float>::const_iterator i = tau.begin(); i != tau.end(); i++)
    {
        task_t t;
                
        t.id = i->first;
        double tau_t = i->second;
        double wi_t = wi.find(t.id)->second;
        double e_t = e.find(t.id)->second.find((int)wi_t)->second;
        t.time_unscaled = tau_t / (wi_t * e_t);
        t.time_scaled = t.time_unscaled / maxF;
        t.group = (int)group.find(t.id)->second;
                
        tasks.insert(t);
    }
        
    return tasks;
}

static by_time_t
init_frequency_best(const Algebra &input)
{
    return init_frequency_max(input);
}

static void update_height(map<int, Group*> &height, int g, double diff)
{
    double son, max;
        max = height[g]->time + diff;
    for(vector<int>::iterator it = height[g]->sons.begin() ; it != height[g]->sons.end() ; ++it)
    {
        height[*it]->time += diff;
        son = height[*it]->time;
        if(son > max) max = son;
    }
    
    height[g]->time = max;
    for(vector<int>::reverse_iterator it = height[g]->parents.rbegin() ; it != height[g]->parents.rend(); ++it)
    {
        if(height[*it]->time < height[g]->time)
        {
                height[*it]->time = height[g]->time;
        }
    }
}

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

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

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

CrownScalingHeight::CrownScalingHeight(const CrownScalingHeight &src) : CrownScaling(src)
{
    /* Do nothing else */
}

Algebra
CrownScalingHeight::scale(const Algebra &input, std::map<const string, double> &stats) const
{
    struct timespec start, stop, time;
    Algebra schedule = input;
    int optimal = 0;

    // Load the crown structure
    map<int, Group*> height;

    // Problem data
    double M = input.find<Scalar<float> >("M")->getValue();
    set<float> F = input.find<Set<float> >("F")->getValues();

    MatrixType matrix_groups = input.find<Matrix<int, int, float> >(CrownConfig::crownConfigGroups)->getValues();
    MatrixType matrix_tree = input.find<Matrix<int, int, float> >(CrownConfig::crownConfigTree)->getValues();

    // Initialize the collection of groups of height 0
    for(unsigned int i = 1 ; i <= matrix_groups.size() ; ++i)
    {
        height.insert(std::make_pair(i, new Group(i, 0.0)));
    }

    // 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)
            {
                height[j]->sons.push_back(i);
                height[i]->parents.push_back(j);
            }
        }
    }
        
    // Set up the list of tasks at frequency max
    by_time_t tasks = init_frequency_best(input);

    // Compute an initial height for all groups
    for(by_time_t::const_iterator i = tasks.begin(); i != tasks.end(); i++)
    {
        int g = i->group;
        update_height(height, g, i->time_scaled);
    }

    clock_gettime(CLOCK_MONOTONIC, &start);

    for(set<float>::const_reverse_iterator i = F.rbegin(); i != F.rend(); i++)
    {
        double f = *i;
        by_time_t new_tasks;
        double diff;
                
        if(f == *F.begin())
        {
            optimal = 1;
        }
        else
        {
            optimal = 0;
        }
        
        for(by_time_t::const_iterator j = tasks.begin(); j != tasks.end(); j++)
        {
            task_t t = *j;
            
            if(t.time_unscaled / t.time_scaled > f)
            {
                if(M - (height[t.group]->time + (t.time_unscaled / f - t.time_scaled)) > 0)
                {
                    diff = t.time_unscaled / f - t.time_scaled;
                    t.time_scaled = t.time_unscaled / f;
                    update_height(height, t.group, diff);
                }
                else
                {
                    optimal = 0;
                }
            }
            new_tasks.insert(t);
        }
        tasks = new_tasks;
    }
    
    clock_gettime(CLOCK_MONOTONIC, &stop);
    
    pelib_timespec_subtract(&time, &stop, &start);
    stats.insert(pair<const string, double>("time_scaling", (time.tv_sec * nsec_in_sec + time.tv_nsec) / (float)nsec_in_sec));
    stats.insert(pair<const string, double>("frequency_optimal", optimal));

    // Generate a frequency vector
    map<int, float> frequency;
    for(by_time_t::const_iterator i = tasks.begin(); i != tasks.end(); i++)
    {
        if(!isnan(i->time_unscaled / i->time_scaled))
        {
            frequency.insert(pair<int, float>(i->id, i->time_unscaled / i->time_scaled));
        }
        else
        {
            frequency.insert(pair<int, float>(i->id, *F.begin()));
        }
    }

    // Insert values to collection
    Vector<int, float> ampl_frequency("frequency", frequency);
    schedule.insert(&ampl_frequency);

    Scalar<float> ampl_m("m", M - height[1]->time);
    schedule.insert(&ampl_m);
    return schedule;
}

Schedule
CrownScalingHeight::scale(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));
    alg = Schedule::addStartTime(alg, tg, pt);

    Schedule sched(getShortDescription(), tg.getName(), alg);

    return sched;
}

float
CrownScalingHeight::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
CrownScalingHeight::complexity(const pelib::Algebra &input) const
{
    double n = input.find<Scalar<float> >("n")->getValue();
    double p = input.find<Scalar<float> >("p")->getValue();
    set<float> F = input.find<Set<float> >("F")->getValues();

    return n * p * (1 + F.size() * log(n));
}

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

    return ss.str();
}

CrownScaling*
CrownScalingHeight::clone() const
{
    return new CrownScalingHeight(*this);
}