src/frequency.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 <cstdlib>
#include <set>

#include <pelib/ParseException.hpp>
#include <pelib/AmplInput.hpp>
#include <pelib/AmplInputScalar.hpp>
#include <pelib/AmplInputVector.hpp>
#include <pelib/AmplInputSet.hpp>
#include <pelib/AmplInputMatrix.hpp>
#include <pelib/Scalar.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.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

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

using namespace std;
using namespace pelib;

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)
{
        // TODO: implement
        return init_frequency_max(input);
}

static double
update_group(map<int, double> &height, int g, double diff)
{
        height[g] = height[g] + diff;
        
        return height[g];
}

static double
update_child_recursive(map<int, double> &height, int g, double diff, int b, int G)
{
        // Update all kid groups, if any
        for(int i = 0; i < b && g * b + i <= G; i++)
        {
                update_child_recursive(height, g * b + i, diff, b, G);
        }

        // Return the new height of this group  
        return update_group(height, g, diff);;
}

static void
update_parent_recursive(map<int, double> &height, int g, double new_height, int b, int G)
{
        if(g > 1 && new_height > height[g])
        {
                update_parent_recursive(height, (int)floor((double)g / (double)b), new_height, b, G);
        }
        if(g >= 1 && new_height > height[g])
        {
                update_group(height, g, new_height - height[g]);
        }
}

static void
update_height(map<int, double> &height, int g, double diff, int b, int G)
{       
        if(height.find(g) != height.end())
        {
                update_parent_recursive(height, (int)floor((double)g / (double)b), height[g] + diff, b, G);
                update_child_recursive(height, g, diff, b, G);
        }
        else
        {
                // Catastrophic error
        }
}

static void
print_all_heights(map<int, double> &height)
{
#if DEBUG
        for(map<int, double>::const_iterator i = height.begin(); i != height.end(); i++)
        {
                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] group " << i->first << ": " << i->second << endl;
        }
#endif
}

static void
print_all_tasks(by_time_t &tasks)
{
#if DEBUG
        for(by_time_t::const_iterator i = tasks.begin(); i != tasks.end(); i++)
        {
                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] task " << i->id << ": unscaled time = " << i->time_unscaled << "; scaled time = " << i->time_scaled << "; group = " << i->group << endl;
        }
#endif
}

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;
}

Algebra
frequency_height(const Algebra &input)
{
        struct timespec start, stop, time;
        Algebra schedule = input;
        int optimal = 0;

        // Load the crown structure
        //int b = (int)input.find<Scalar<float> >("b")->getValue();
        int b = 2;
        int p = (int)input.find<Scalar<float> >("p")->getValue();
        map<int, double> height;

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

        // Initialize a collection of groups of height 0
        // TODO: Make it general with respect to b (assume b = 2 for now)
        int G = 2 * p - 1;
        //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] p = " << p << "; G = " << G << endl;
        for(int i = 0; i < G; i++)
        {
                height.insert(pair<int, float>(i + 1, 0));
        }
        
        // 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, b, G);
        }

        // Just make sure everything is alright
        print_all_tasks(tasks);
        print_all_heights(height);

        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;
                
                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] Trying frequency f = " << f << endl;
                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)
                        {
                                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] Scaling task " << t.id << " in group " << t.group << endl;
                                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] We have " << M - height[t.group] << " slack time" << endl;
                                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] We would compute for " << (t.time_unscaled / f - t.time_scaled) << " longer time" << endl;
                                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] There would be " << M - (height[t.group] + (t.time_unscaled / f - t.time_scaled)) << " time left" << endl;
                                        
                                if(M - (height[t.group] + (t.time_unscaled / f - t.time_scaled)) > 0)
                                {
                                        double diff = t.time_unscaled / f - t.time_scaled;
                                        t.time_scaled = t.time_unscaled / f;
                                        update_height(height, t.group, diff, b, G);

                                        print_all_heights(height);
                                        print_all_tasks(tasks);
                                }
                                else
                                {
                                        optimal = 0;
                                }
                        }
                        new_tasks.insert(t);
                }
                tasks = new_tasks;
        }

        clock_gettime(CLOCK_MONOTONIC, &stop);

        print_all_tasks(tasks);
        print_all_heights(height);

        timespec_subtract(&time, &stop, &start);
    Scalar<float> param_time("_total_solve_elapsed_time", (time.tv_sec * nsec_in_sec + time.tv_nsec) / (double)nsec_in_sec);
    schedule.insert(&param_time);

        Scalar<float> param_optimal("frequency_optimal", (int)optimal);
        schedule.insert(&param_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]);
        schedule.insert(&ampl_m);
        
        return schedule;
}

float
frequency_height_complexity(const pelib::Algebra &input)
{
        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));
}