src/crown.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 <crown/mapping.h>
#include <crown/scaling.h>
#include <crown/annealing.h>
#include <crown/crown.h>

#include <pelib/AmplInput.hpp>
#include <pelib/AmplOutput.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/Set.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;

namespace pelib
{
namespace crown
{

// Quality assessment parameters
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;
}

// This is not valid if we consider swithing off unused cores
#if RETURN_EARLY && 0
#define return_now_if_best(solution) if(solution.find<Scalar<float> >("all_sequential")->getValue() == 1 && solution.find<Scalar<float> >("frequency_optimal")->getValue() == 1) return solution
#else
#define return_now_if_best(solution)
#endif

static Algebra
crown_binary_quality(const Algebra &taskgraph, float (*quality)(const Algebra &solution), unsigned int precision)
{
        Algebra schedule = taskgraph;
        float threshold = 0.5;
        float delta = 0.25;
        float derivative, min_derivative = 1;
        unsigned int round = 0;
        //int need_schedule = 1;
        float m = 0;
        Algebra current, best;
        float power = 0, best_power;

        // Compute allocation for maximal parallelization
        // This is is to get an allocation if nothing else works
        // Yet it is not guaranteed to produce a valid schedule
        // because of a still too high makespan presure
        best = schedule;
        
        best = allocation_fastest(best);
        best = mapping_ltlg(best);
        best = frequency_height(best);
        best_power = quality(best);

        //return_now_if_best(best);

        float emax = 0, emin = 1;
        float previous = 1;
        map<int, map<int, float> > map_e = schedule.find<Matrix<int, int, float> >("e")->getValues();
        map<int, float> map_Wi = schedule.find<Vector<int, float> >("Wi")->getValues();
        for(map<int, map<int, float> >::iterator row_iter = map_e.begin(); row_iter != map_e.end(); row_iter++)
        {
                int task = row_iter->first;
                int Wi = (int)map_Wi[task];
                map<int, float> map_row = row_iter->second;
                                
                for(map<int, float>::iterator col_iter = map_row.begin(); col_iter != map_row.end() && col_iter->first <= Wi; col_iter++)
                {
                        if(col_iter->second < 1)
                        {
                                if(col_iter->second > emax)
                                {
                                        emax = col_iter->second;
                                }

                                if(col_iter->second < emin)
                                {
                                        emin = col_iter->second;
                                }

                                derivative = previous - col_iter->second;
                                if(derivative < min_derivative)
                                {
                                        min_derivative = derivative;
                                }
                        }
                }
        }

        // Binary search for maximal minimum efficiency for all tasks
        //bool threshold_ok = true;
        bool retry = true;

        // Try a whole sequential schedule
        current = schedule;
        current = allocation_gemin(current, 1);
        current = mapping_ltlg(current);
        current = frequency_height(current);

        //AmplOutput(AmplOutput::floatHandlers()).dump(cerr, current);
        //return_now_if_best(current);
                
        // Check if this allocation could produce a valid mapping
        // m is the minimal slack time
        m = current.find<Scalar<float> >("m")->getValue();
        if(m > 0)
        {
                power = quality(current);
                if(power <= best_power)
                {
                        best_power = power;
                        best = current;
                }
        }

        // Loop while the current threshold is lower than the maximum non-sequential efficiency
        // and delta is higher than the minimal efficiency gap between two allocations for any task
        // And, if any maximum round was given, this threshold was not reached
        while(retry && delta * 2 > min_derivative && ((precision != 0 && round < precision) || precision == 0))
        {
                // Reset the current solution to input
                current = schedule;

                // Allocate with current threshold then run mapping and frequency scaling
                //cerr << "######################################" << endl;
                //AmplInput().dump(cerr, current);
                //cerr << endl;
                
                current = allocation_gemin(current, threshold);
                
                //AmplInput().dump(cerr, current);
                
                current = mapping_ltlg(current);
                current = frequency_height(current);

                //return_now_if_best(current);
                
                // Check if this allocation could produce a valid mapping
                // m is the minimal slack time
                m = current.find<Scalar<float> >("m")->getValue();

                // Update the threshold after the feasibility
                if(m > 0)
                {
                        power = quality(current);
#if SHOWPOWER
                        // Output the energy of current schedule
                        cout << "# Statistics: " << threshold << " " << power << endl;
#endif
                        // This is a valid schedule
                        // Retry if current threshold is lower than maximal efficiency
                        retry = threshold < emax;
                        
                        // Increase threshold by delta
                        threshold = threshold + delta;
                
                        // Keep this schedule as the best found so far
                        if(power < best_power)
                        {
                                best = current;
                        }
                }
                else
                {
                        // This was an invalid schedule
                        retry = true;
                        
                        // Allow lower efficiency
                        threshold = threshold - delta;                  
                }

                // Reduce the delta
                delta = delta / 2;

                // Count the number of rounds
                round++;
        }

        Scalar<float> best_quality_scalar("quality", best_power);
        best.remove("best_quality");
        best.insert(&best_quality_scalar);

/*
        Scalar<float> scalar_threshold = Scalar<float>("gemin", threshold);
        best.insert(&scalar_threshold);
        Scalar<float> scalar_gemax = Scalar<float>("gemax", emax);
        best.insert(&scalar_gemax);
*/

        // Compute and insert scheduling time
/*
        Scalar<float> scalar_round = Scalar<float>("round", round);
        best.insert(&scalar_round);
*/

        return best;
}

Algebra
crown_binary_simple(const Algebra &taskgraph, unsigned int precision)
{
        return crown_binary_quality(taskgraph, quality_simple, precision);
}

Algebra
crown_binary_idle(const Algebra &taskgraph, unsigned int precision)
{
        return crown_binary_quality(taskgraph, quality_idle, precision);
}

Algebra
crown_binary_off(const Algebra &taskgraph, unsigned int precision)
{
        return crown_binary_quality(taskgraph, quality_off, precision);
}

Algebra
crown_binary(const Algebra &taskgraph, unsigned int precision)
{
        return crown_binary_quality(taskgraph, energy_static_dynamic_busy_idle_active, precision);
}

Algebra
crown_binary_annealing_allocation(const Algebra &initial, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        Algebra schedule = initial;
        Algebra best = schedule;
        // Compute an initial best solution     
        best = crown_binary(best, 0);

        return annealing(best, best, energy_static_dynamic_busy_idle_active, neighbor_allocation_tasks, temperature, cooling, final, max_transform, max_new_state, distance);
}

Algebra
crown_annealing_allocation_idle(const Algebra &initial, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        struct timespec start, stop, total_time;
        Algebra schedule = initial;

        Algebra best = schedule;
        clock_gettime(CLOCK_MONOTONIC, &start); 
        // Compute an initial best solution     
        best = allocation_fastest(best);
        best = mapping_ltlg(best);
        best = frequency_height(best);

        // Generate a random initial solution
        schedule = allocation_random(schedule);
        schedule = mapping_ltlg(schedule);
        schedule = frequency_height(schedule);

        schedule = annealing(schedule, best, quality_idle, neighbor_allocation_full, temperature, cooling, final, max_transform, max_new_state, distance);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        schedule.insert(&param_time);

        return schedule;
}

Algebra
crown_annealing_allocation_off(const Algebra &initial, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        struct timespec start, stop, total_time;
        Algebra schedule = initial;

        Algebra best = schedule;
        clock_gettime(CLOCK_MONOTONIC, &start); 
        // Compute an initial best solution     
        best = allocation_fastest(best);
        best = mapping_ltlg(best);
        best = frequency_height(best);

        // Generate a random initial solution
        schedule = allocation_random(schedule);
        schedule = mapping_ltlg(schedule);
        schedule = frequency_height(schedule);

        schedule = annealing(schedule, best, quality_off, neighbor_allocation_full, temperature, cooling, final, max_transform, max_new_state, distance);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        schedule.insert(&param_time);

        return schedule;
}

Algebra
crown_annealing_allocation_simple(const Algebra &initial, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        struct timespec start, stop, total_time;
        Algebra schedule = initial;
        Algebra best = schedule;

        clock_gettime(CLOCK_MONOTONIC, &start); 

        // Compute an initial best solution     
        best = allocation_fastest(best);
        best = mapping_ltlg(best);
        best = frequency_height(best);

        // Generate a random initial solution
        schedule = allocation_random(schedule);
        schedule = mapping_ltlg(schedule);
        schedule = frequency_height(schedule);

        schedule = annealing(schedule, best, quality_simple, neighbor_allocation_full, temperature, cooling, final, max_transform, max_new_state, distance);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        schedule.insert(&param_time);

        return schedule;
}

Algebra
crown_binary_annealing_allocation_idle(const Algebra &initial, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        struct timespec start, stop, total_time;
        Algebra schedule = initial;

        Algebra best = schedule;
        clock_gettime(CLOCK_MONOTONIC, &start); 
        // Compute an initial best solution     
        best = crown_binary_idle(best, 0);

        schedule = annealing(best, best, quality_idle, neighbor_allocation_tasks, temperature, cooling, final, max_transform, max_new_state, distance);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        schedule.insert(&param_time);

        return schedule;
}

Algebra
crown_binary_annealing_allocation_off(const Algebra &initial, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        struct timespec start, stop, total_time;
        Algebra schedule = initial;

        Algebra best = schedule;
        clock_gettime(CLOCK_MONOTONIC, &start); 
        // Compute an initial best solution     
        best = crown_binary_off(best, 0);

        schedule = annealing(best, best, quality_off, neighbor_allocation_tasks, temperature, cooling, final, max_transform, max_new_state, distance);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        schedule.insert(&param_time);

        return schedule;
}

Algebra
crown_binary_annealing_allocation_simple(const Algebra &initial, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        struct timespec start, stop, total_time;
        Algebra schedule = initial;

        Algebra best = schedule;
        clock_gettime(CLOCK_MONOTONIC, &start); 
        // Compute an initial best solution     
        best = crown_binary_simple(best, 0);

        schedule = annealing(best, best, quality_simple, neighbor_allocation_full, temperature, cooling, final, max_transform, max_new_state, distance);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        schedule.insert(&param_time);

        return schedule;
}

static Algebra
add_extreme_e(const Algebra &schedule)
{
        float emax = 0, emin = 1;
        //float previous = 1;
        map<int, map<int, float> > map_e = schedule.find<Matrix<int, int, float> >("e")->getValues();
        map<int, float> map_Wi = schedule.find<Vector<int, float> >("Wi")->getValues();
        for(map<int, map<int, float> >::iterator row_iter = map_e.begin(); row_iter != map_e.end(); row_iter++)
        {
                int task = row_iter->first;
                int Wi = (int)map_Wi[task];
                map<int, float> map_row = row_iter->second;
                                
                for(map<int, float>::iterator col_iter = map_row.begin(); col_iter != map_row.end() && col_iter->first <= Wi; col_iter++)
                {
                        if(col_iter->second < 1)
                        {
                                if(col_iter->second > emax)
                                {
                                        emax = col_iter->second;
                                }

                                if(col_iter->second < emin)
                                {
                                        emin = col_iter->second;
                                }
                        }
                }
        }

        Algebra input = schedule;
        Scalar<float> scalar_threshold = Scalar<float>("gemin", emin);
        input.insert(&scalar_threshold);
        Scalar<float> scalar_gemax = Scalar<float>("gemax", emax);
        input.insert(&scalar_gemax);

        return input;
}

Algebra
crown_binary_annealing_efficiency_simple(const Algebra &schedule, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        struct timespec start, stop, total_time;

        Algebra initial, best;
        clock_gettime(CLOCK_MONOTONIC, &start);
        
        // Compute an initial solution  
        initial = add_extreme_e(schedule);
        float gemin = initial.find<Scalar<float> >("gemin")->getValue();
        float gemax = initial.find<Scalar<float> >("gemax")->getValue();
        float random = (float)rand() / RAND_MAX;
        initial = allocation_gemin(initial, gemin + random * (gemax - gemin));
        initial = mapping_ltlg(initial);
        initial = frequency_height(initial);

        // Compute an initial best solution
        best = allocation_fastest(schedule);
        best = mapping_ltlg(best);
        best = frequency_height(best);

        best = annealing(initial, best, quality_simple, neighbor_efficiency, temperature, cooling, final, max_transform, max_new_state, distance);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        best.insert(&param_time);

        return best;
}

Algebra
crown_binary_annealing_efficiency_idle(const Algebra &schedule, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        struct timespec start, stop, total_time;

        Algebra initial, best;
        clock_gettime(CLOCK_MONOTONIC, &start);
        
        // Compute an initial solution  
        initial = add_extreme_e(schedule);
        float gemin = initial.find<Scalar<float> >("gemin")->getValue();
        float gemax = initial.find<Scalar<float> >("gemax")->getValue();
        float random = (float)rand() / RAND_MAX;
        initial = allocation_gemin(initial, gemin + random * (gemax - gemin));
        initial = mapping_ltlg(initial);
        initial = frequency_height(initial);

        // Compute an initial best solution
        best = allocation_fastest(schedule);
        best = mapping_ltlg(best);
        best = frequency_height(best);

        best = annealing(initial, best, quality_idle, neighbor_efficiency, temperature, cooling, final, max_transform, max_new_state, distance);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        best.insert(&param_time);

        return best;
}

Algebra
crown_binary_annealing_efficiency_off(const Algebra &schedule, float temperature, float cooling, float final, int max_transform, int max_new_state, float distance)
{
        struct timespec start, stop, total_time;

        Algebra initial, best;
        clock_gettime(CLOCK_MONOTONIC, &start);
        
        // Compute an initial solution  
        initial = add_extreme_e(schedule);
        float gemin = initial.find<Scalar<float> >("gemin")->getValue();
        float gemax = initial.find<Scalar<float> >("gemax")->getValue();
        float random = (float)rand() / RAND_MAX;
        initial = allocation_gemin(initial, gemin + random * (gemax - gemin));
        initial = mapping_ltlg(initial);
        initial = frequency_height(initial);

        // Compute an initial best solution
        best = allocation_fastest(schedule);
        best = mapping_ltlg(best);
        best = frequency_height(best);

        best = annealing(initial, best, quality_off, neighbor_efficiency, temperature, cooling, final, max_transform, max_new_state, distance);
        clock_gettime(CLOCK_MONOTONIC, &stop);
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        best.insert(&param_time);

        return best;
}

float
crown_binary_complexity(const Algebra &schedule, unsigned int precision)
{
        if(precision > 0)
        {
                return precision;
        }
        else
        {
                float emax = 0, emin = 1;
                float previous = 1;
                float derivative, min_derivative = 0.25;
                map<int, map<int, float> > map_e = schedule.find<Matrix<int, int, float> >("e")->getValues();
                map<int, float> map_Wi = schedule.find<Vector<int, float> >("Wi")->getValues();
                
                for(map<int, map<int, float> >::iterator row_iter = map_e.begin(); row_iter != map_e.end(); row_iter++)
                {
                        int task = row_iter->first;
                        int Wi = (int)map_Wi[task];
                        map<int, float> map_row = row_iter->second;
                        
                        for(map<int, float>::iterator col_iter = map_row.begin(); col_iter != map_row.end() && col_iter->first <= Wi; col_iter++)
                        {
                                if(col_iter->first > 1)
                                {
                                        if(col_iter->second > emax)
                                        {
                                                emax = col_iter->second;
                                        }

                                        if(col_iter->second < emin)
                                        {
                                                emin = col_iter->second;
                                        }

                                        derivative = previous - col_iter->second;
                                        //cerr << "derivative = " << derivative << endl;
                                        previous = col_iter->second;
                                        if(derivative < min_derivative)
                                        {
                                                min_derivative = derivative;
                                                //cerr << "min_derivative = " << min_derivative << endl;
                                        }
                                        //cerr << "previous = " << previous << endl;
                                }
                                else
                                {
                                        previous = col_iter->second; // ... which should be always 1.
                                        //min_derivative = 0.25; // If a task is sequential, then the complexity will be 1.
                                        //cerr << "min_derivative = " << min_derivative << endl;
                                }
                        }
                }

                //cerr << "min_derivative = " << min_derivative << endl;
                //cerr << ceil(log2 (0.5 / min_derivative)) << endl;
                return ceil(log2 (0.5 / min_derivative));
        }
}

}
}