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

#include <pelib/AmplSolver.hpp>
#include <pelib/Scalar.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/Set.hpp>
#include <pelib/Schedule.hpp>
#include <pelib/Algebra.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;

extern char _binary_scaling_mod_start;
extern char _binary_scaling_mod_end;
extern char _binary_scaling_run_start;
extern char _binary_scaling_run_end;

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

CrownScalingILP::CrownScalingILP(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 */
}

CrownScalingILP::CrownScalingILP(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 */
}

Algebra
CrownScalingILP::scale(const Algebra &alg, std::map<const string, double> &stats) const
{
        // Build input collection
        std::map<const string, const Algebra> data;
        data.insert(pair<const string, const Algebra>("parameters.dat", alg));

        // Build model and run scripts input streams
        stringstream model(string(&_binary_scaling_mod_start, &_binary_scaling_mod_end));
        stringstream run(string(&_binary_scaling_run_start, &_binary_scaling_run_end));

        // Run the solver
        const Algebra *solution = AmplSolver(model, string("model.mod"), run, data, showOutput, showError).solve(stats);

        // Insert back tasks' names
        std::map<const string, double>::iterator ii = stats.find("time");
        if(ii != stats.end())
        {
                double time = ii->second;
                stats.erase(ii);
                stats.insert(pair<const string, double>("time_scaling", time));
        }

        Algebra sol = *solution;
        delete solution;
        std::map<const string, double>::iterator jj = stats.find("feasible");
        if(jj != stats.end())
        {
                if(jj->second > 0)
                {
                        Scalar<float> m("m", 1);
                        sol.insert(&m);
                }
                else
                {
                        Scalar<float> m("m", -1);
                        sol.insert(&m);
                }
        }
        
        return sol;
}

Schedule
CrownScalingILP::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
CrownScalingILP::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
CrownScalingILP::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
CrownScalingILP::getShortDescription() const
{
        stringstream ss;
        std::streamsize p = ss.precision();
        ss.precision(4);
        ss << "ILP";
        ss.precision(p);

        return ss.str();
}

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