src/allocation.cpp

Go to the documentation of this file.

/*
 Copyright 2015 Nicolas Melot

 This file is part of Crown.

 Crown 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.

 Crown 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 Crown. If not, see <http://www.gnu.org/licenses/>.

*/


#include <fstream>
#include <set>

#include <cstdlib>

#include <crown/allocation.h>

#include <pelib/AmplInput.hpp>
#include <pelib/AmplOutput.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.hpp>

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

using namespace pelib;
using namespace std;

static const long long int nsec_in_sec = 1000000000;

static int
timespec_subtract(struct timespec *result, struct timespec *x, struct timespec *y)
{
        /* Perform the carry for the later subtraction by updating y. */
        if (x->tv_nsec < y->tv_nsec)
        {
                int nsec = (y->tv_nsec - x->tv_nsec) / nsec_in_sec + 1;
                y->tv_nsec -= nsec_in_sec * nsec;
                y->tv_sec += nsec;
        }
        if (x->tv_nsec - y->tv_nsec > nsec_in_sec)
        {
                int nsec = (x->tv_nsec - y->tv_nsec) / nsec_in_sec;
                y->tv_nsec += nsec_in_sec * nsec;
                y->tv_sec -= nsec;
        }
     
       /* Compute the time remaining to wait. tv_nsec is certainly positive. */
        result->tv_sec = x->tv_sec - y->tv_sec;
        result->tv_nsec = x->tv_nsec - y->tv_nsec;
     
        /* Return 1 if result is negative. */
        return x->tv_sec < y->tv_sec;
}

pelib::Algebra
allocation_fastest(const pelib::Algebra &schedule)
{
        Algebra input = schedule;
        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();
        int b = (int)input.find<Scalar<float> >("b")->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;

        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;

                        // Only proceed if p in a power of b
                        if(pow(b, floor(log(p) / log(b))) == p)
                        {
                                float e = j->second;
                                float efft = p * e;
                                if(max_efft < efft)
                                {
                                        max_efft = efft;
                                        best_p = p;
                                }
                        }
                }
                vector_wi.insert(pair<int, float>(task, best_p));
        }

        clock_gettime(CLOCK_MONOTONIC, &stop);
        timespec_subtract(&total_time, &stop, &start);
        
        Scalar<float> *param_time = new Scalar<float>("_total_solve_elapsed_time", (total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        input.insert(param_time);

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

        return input;
}

Algebra
allocation_random(const Algebra &schedule)
{
        Algebra input = schedule;

        struct timespec start, stop, total_time;

        // Read tasks's efficiency and decide on their optimal allocation
        int b = (int)input.find<Scalar<float> >("b")->getValue();
        int L = (int)(log(input.find<Scalar<float> >("p")->getValue()) / log(b));
        map<int, float> vector_Wi = input.find<Vector<int, float> >("Wi")->getValues();
        map<int, float> vector_wi;

        clock_gettime(CLOCK_MONOTONIC, &start); 

        for(map<int, float>::iterator i = vector_Wi.begin(); i != vector_Wi.end(); i++)
        {
                int task = i->first;
                int Wi = (int)i ->second;

                Wi = (int)(log(Wi) / log(b));
                Wi = Wi > L ? L : Wi;           
                
                vector_wi.insert(pair<int, float>(task, (float)pow((double)b, (double)(rand() % (Wi + 1)))));
        }

        clock_gettime(CLOCK_MONOTONIC, &stop);
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> *param_time = new Scalar<float>("_total_solve_elapsed_time", (total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        input.insert(param_time);

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

        return input;
}

Algebra
allocation_temin(const Algebra &schedule)
{
        Algebra input = schedule;
        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();
        int b = (int)input.find<Scalar<float> >("b")->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;

        // Extract the global threshold scalar, if any, or build one
        const Scalar<float> *gemin = input.find<Scalar<float> >("gemin");
        if(gemin == NULL)
        {
                gemin = new Scalar<float>("gemin", 0.5);
                input.insert(gemin);
                delete gemin;
                gemin = input.find<Scalar<float> >("gemin");
        }
        
        // Extract the threshold vector, if any, or build one
        const Vector<int, float> *temin = input.find<Vector<int, float> >("temin");
        if(temin == NULL)
        {
                map<int, float> t;
                for(map<int, float>::iterator iter = vector_wi.begin(); iter != vector_wi.end(); iter++)
                {
                        //cerr << "Task " << iter->first << ", efficiency = " << global_threshold->getValue() << endl;
                        t.insert(pair<int, float>(iter->first, gemin->getValue()));
                }

                temin = new Vector<int, float>("temin", t);
                input.insert(temin);
                delete temin;
                temin = input.find<Vector<int, float> >("temin");
        }
        map<int, float> map_temin = temin->getValues();

        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;
                float emin = map_temin[task];
                //cerr << "# Task " << task << "; emin = " << emin << endl;

                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;
                        //cerr << "# Task " << task << "; p = " << p << endl;

                        // Only proceed if p in a power of b
                        if(pow(b, floor(log(p) / log(b))) == p)
                        {
                                float e = j->second;
                                float efft = p * e;
                                //cerr << "# Task " << task << "; p = " << p << "; e = " << e << "; efft = " << efft << "; max_efft = " << max_efft << "; emin = " << emin << endl;
                                if(max_efft < efft && e >= emin)
                                {
                                        //cerr << "# Task " << task << "; best_p = " << p << "; max_efft = " << efft << endl;
                                        max_efft = efft;
                                        best_p = p;
                                }
                        }
                }
                vector_wi.insert(pair<int, int>(task, best_p));
        }

        clock_gettime(CLOCK_MONOTONIC, &stop);
        timespec_subtract(&total_time, &stop, &start);
        
        Scalar<float> *param_time = new Scalar<float>("_total_solve_elapsed_time", (total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        input.insert(param_time);

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

        cerr << "# Redoing allocation" << endl;

        return input;
}

Algebra
allocation_gemin(const Algebra &schedule, float gemin)
{
        Algebra input = schedule;
        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();
        int b = (int)input.find<Scalar<float> >("b")->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;

        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;

                        // Only proceed if p in a power of b
                        if(pow(b, floor(log(p) / log(b))) == p)
                        {
                                float e = j->second;
                                float efft = p * e;

                                //cerr << "e = " << e << "; efft = " << efft << endl;
                                if(max_efft < efft && e >= gemin)
                                {
                                        max_efft = efft;
                                        best_p = p;
                                        //cerr << "max_efft = " << efft << "; best p = " << p << endl;
                                }
                        }
                }
                vector_wi.insert(pair<int, int>(task, best_p));
        }

        clock_gettime(CLOCK_MONOTONIC, &stop);
        timespec_subtract(&total_time, &stop, &start);
        
        Scalar<float> *param_time = new Scalar<float>("_total_solve_elapsed_time", (total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        input.insert(param_time);

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

        return input;
}

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

        return n * log(p);
}