src/XuILP.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 <string>

#include <pelib/XuILP.hpp>
#include <pelib/AmplSolver.hpp>
#include <pelib/Schedule.hpp>
#include <pelib/XMLSchedule.hpp>
#include <pelib/Scalar.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/Set.hpp>
#include <pelib/Task.hpp>
#include <pelib/Taskgraph.hpp>
#include <pelib/Platform.hpp>
#include <pelib/CastException.hpp>
#include <pelib/ParseException.hpp>
#include <pelib/AmplOutput.hpp>
#include <pelib/PelibException.hpp>

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

using namespace std;
using namespace pelib;

extern char _binary_xu_mod_start;
extern char _binary_xu_mod_end;
extern char _binary_xu_run_start;
extern char _binary_xu_run_end;

XuILP::XuILP(bool showOutput, bool showError)
{
        param.insert(new Scalar<float>("alpha", 3));
        this->showError = showError;
        this->showOutput = showOutput;
}

XuILP::XuILP(const Algebra &param, bool showOutput, bool showError)
{
        this->param = param;
        this->showError = showError;
        this->showOutput = showOutput;
}

XuILP::XuILP(const Taskgraph &tg, const Platform &pt, const Algebra &param, bool showOutput, bool showError)
{
        this->taskgraph = tg;
        this->platform = pt;
        this->param = param;
        this->showError = showError;
        this->showOutput = showOutput;
}

Schedule
XuILP::schedule(const Taskgraph &tg, const Platform &pt, std::map<const string, double>& stats) const
{
        return schedule(tg, pt, this->param, stats);
}

Schedule
XuILP::schedule(const Taskgraph &tg, const Platform &pt, const Algebra &param, std::map<const string, double>& stats) const
{
        // Add default values, if necessary
        Algebra p = param;
        if(p.find<Scalar<float> >("alpha") == NULL)
        {
                p.insert(new Scalar<float>("alpha", 3));
        }
        
        // Build input collection
        map<const string, const Algebra> data;
        data.insert(pair<const string, const Algebra>(string("platform.dat"), pt.buildAlgebra()));
        data.insert(pair<const string, const Algebra>(string("parameters.dat"), p));

        // Save and remove name vector from data
        Algebra taskgraph = tg.buildAlgebra(pt);
        const Vector<int, string> *name_ptr = taskgraph.find<Vector<int, string> >("name");
        if(name_ptr == NULL)
        {
                throw PelibException("Missing tasks' name vector from taskgraph conversion to Algebra record");
        }
        Vector<int, string> name(*name_ptr);
        taskgraph.remove("name");
        data.insert(pair<const string, const Algebra>(string("taskgraph.dat"), taskgraph));

        // Build model and run scripts input streams
        stringstream model(string(&_binary_xu_mod_start, &_binary_xu_mod_end));
        stringstream run(string(&_binary_xu_run_start, &_binary_xu_run_end));

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

        // Insert back name vector
        alg.insert(new Vector<int, string>(name));
        p = solution->merge(pt.buildAlgebra());
        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_schedule", time));
                stats.insert(pair<const string, double>("time_global", time));
        }
        if(stats.find("feasible")->second != 0)
        {
                return this->buildSchedule(alg, tg.getName());
        }
        else
        {
                return Schedule("ILP Unrestricted", tg.getName(), Schedule::table());
        }
}

const Algebra*
XuILP::solve() const
{
        map<const string, double> stats;
        return new Algebra(schedule(this->taskgraph, this->platform, this->param, stats).buildAlgebra());
}

const Algebra*
XuILP::solve(map<const string, double> &stats) const
{
        return new Algebra(schedule(this->taskgraph, this->platform, this->param, stats).buildAlgebra());
}

std::string
XuILP::getShortDescription() const
{
        float alpha = this->param.find<Scalar<float> >("alpha")->getValue();
        stringstream ss;

        std::streamsize p = ss.precision();
        ss.precision(4);
        ss << "XuILP." << "(a=" << alpha << ")";
        ss.precision(p);

        return ss.str();
}

Schedule
XuILP::buildSchedule(const Algebra &in, const std::string &name) const
{
        AmplOutput output(AmplOutput::floatHandlers());

        Algebra alg = in;

        int p = alg.find<Scalar<float> >("p")->getValue();
        map<int, float> degree = alg.find<Vector<int, float> >("wi")->getValues();
        map<int, float> level = alg.find<Vector<int, float> >("level")->getValues();
        map<int, float> time = alg.find<Vector<int, float> >("time")->getValues();
        const Matrix<int, int, float> *ampl_tasks = alg.find<Matrix<int, int, float> >("tasks");
        map<int, map<int, float> > tasks = ampl_tasks->getValues();
        map<int, map<int, float> > schedule;

        float cumulated_time = 0;
        map<int, float> level_start;
        for(map<int, float>::iterator i = level.begin(); i != level.end(); i++)
        {
                level_start.insert(pair<int, float>(i->first, cumulated_time));
                cumulated_time += time.find(i->first)->second;
        }

        map<int, float> start;
        for(map<int, map<int, float> >::iterator i = tasks.begin(); i != tasks.end(); i++)
        {
                start.insert(pair<int, float>(i->first, level_start.find(level.find(i->first)->second)->second));
                for(int k = 0; k < p; k++)
                {
                        schedule[k + 1][round(i->first)] = 0;
                }
        }

        for(map<int, map<int, float> >::iterator i = tasks.begin(); i != tasks.end(); i++)
        {
                int offset = 0;
                int level = i->first;
                for(map<int, float>::iterator j = i->second.begin(); j != i->second.end(); j++)
                {
                        if(j->second != 0)
                        {
                                int task = round(j->second);
                                int wi = round(degree[task]);

                                for(int k = 0; k < wi; k++)
                                {
                                        schedule[offset + k + 1][level] = task;
                                }
                                offset += wi;
                        }
                }
        }

        Vector<int, float> start_vector("start", start);
        alg.insert(&start_vector);
        Matrix<int, int, float> schedule_matrix("schedule", schedule);
        alg.insert(&schedule_matrix);
        Schedule sched("Xu ILP", name, alg);

        return sched;
}

#ifdef __cplusplus
extern "C" {
#endif

struct args
{
        double alpha;
        bool showError, showOutput;
        
};
typedef struct args args_t;

static args_t
parse(char **args)
{
        args_t out;
        out.showError = false;
        out.showOutput = false;
        out.alpha = 3;

        for(; args[0] != NULL; args++)
        {
                if(strcmp(args[0], "--show-stdout") == 0)
                {
                        out.showOutput = true;
                        continue;
                }
                if(strcmp(args[0], "--show-stderr") == 0)
                {
                        out.showError = true;
                        continue;
                }
                if(strcmp(args[0], "--alpha") == 0)
                {
                        args++;
                        stringstream str(args[0]);
                        str >> out.alpha;
                        continue;
                }
        }

        return out;
}

const pelib::Schedule*
pelib_schedule(const pelib::Taskgraph &tg, const pelib::Platform &pt, size_t argc, char **argv, map<const string, double>& statistics)
{
        args_t args = parse(argv);
        Algebra param;
        param.insert(new Scalar<float>("alpha", args.alpha));

        // Convert solver output to general schedule
        Schedule *sched;
        sched = new Schedule(XuILP(param, args.showOutput, args.showError).schedule(tg, pt, statistics));

        return sched;
}

string
pelib_description(size_t argc, char **argv)
{
        args_t args = parse(argv);
        Algebra param;
        param.insert(new Scalar<float>("alpha", args.alpha));

        // Convert solver output to general schedule
        string desc;
        desc = XuILP(param, args.showOutput, args.showError).getShortDescription();

        return desc;
}

void
pelib_delete(pelib::Schedule *sched)
{
        delete sched;
}

#ifdef __cplusplus
}
#endif