src/mapping.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>

#include <crown/mapping.h>

#if LONGEST_WIDEST_LOWEST_TASK_FIRST
#undef LONGEST_WIDEST_TASK_FIRST
#define LONGEST_WIDEST_TASK_FIRST 1
#endif

#if LONGEST_WIDEST_TASK_FIRST
#undef LONGEST_TASK_FIRST
#define LONGEST_TASK_FIRST 1
#endif

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

using namespace std;
using namespace pelib;

typedef map<int, float> by_group_t;
typedef pair<int, float> group_time_t;

typedef std::map<int, float> RowType;
typedef std::map<int, RowType> MatrixType;

// Needed tp compare two group_time_t elements in the set whose definition comes right after
struct cmp_time : binary_function <group_time_t, group_time_t, bool>
{
        bool
        operator()(const group_time_t& x, const group_time_t& y) const
        {
                // Operand groups' ids
                int xfirst = x.first; 
                int yfirst = y.first;

                // Operand groups' time
                float xsecond = x.second;
                float ysecond = y.second;

                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] x.first: " << x.first << "; y.first: " << y.first << "; x.second: " << x.second << "; y.second: " << y.second << endl;
                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] xfirst: " << xfirst << "; yfirst: " << yfirst << "; xsecond: " << xsecond << "; ysecond: " << ysecond << endl;
                
                if(xsecond == ysecond)
                {
                        // If two groups have the same time, then order them by id
                        //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] " << (xfirst < yfirst) << endl;
                        return xfirst < yfirst;
                }
                else
                {
                        //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] " << (xsecond < ysecond) << endl;
                        return xsecond < ysecond;
                }
        }
};

typedef multiset<group_time_t, cmp_time> by_time_t;
typedef pair<by_group_t, by_time_t> level_time_t;
typedef map<int, level_time_t> mapping_time_t;
typedef vector<pair<int, int> > mapping_t;

static int n, b, L, p, G;
//static AmplInput data(AmplInput::floatHandlers());

static Algebra *rec;
static mapping_t schedule;
static mapping_time_t load;                                                             // Map organized by group size
static map<int, float> vector_Wi;
static map<int, float> vector_Tau;
static map<int, float> vector_wi;
static MatrixType matrix_e;

/*
static int
size(int g)
{
        return (int)pow((double)b, (double)(L - floor(log2(g))));
}

static size_t
begin(int g)
{
        return (size_t)(size(g) * (g - pow(b, floor(log2(g)))));
}

static size_t
end(int g)
{
        return begin(g) + size(g);
}
*/

/*
static void
show_group_time()
{
        for(mapping_time_t::iterator lvl = load.begin(); lvl != load.end(); lvl++)
        {
                for(by_time_t::iterator time = lvl->second.second.begin(); time != lvl->second.second.end(); time++)
                {
                        cout << "In level " << lvl->first << ": group " << time->first << " has time " << time->second << endl;
                }
        }
}
*/

static float
update_group_time(int g, float time_offset)                                                                             // O(log(p))
{
        //cerr << "Updating group " << g << " by " << time_offset << endl;
        // Update the group itself

        // Find out what level is this group in
        //int lvl = (int)(floor(log(g) / log(b)));                                                                                      // O(1)
        int lvl = (int)(floor(log2(g) / (b - 1))); // TODO: floor(log(g) / log(b)) is broken (g++ 3.4.5) and returns 2 for g = 8 and b = 2, but we have to use b so the compiler shuts up. To be restored with a compiler fix                                                                                   // O(1)
        //show_group_time();
        
        // Get the group collection of level of the group we modify
        mapping_time_t::iterator level_time = load.find(lvl);                                           // O(log(log(p)))

        // Get the run time of the group we want to modify, thanks to the group key
        float time = level_time->second.first.find(g)->second;                                          // O(log(p))

        // Get an iterator to the group we want to modify,
        // in the collection sorted by time
        group_time_t group_key = group_time_t(g, time);
        by_time_t::iterator iter = level_time->second.second.find(group_key);

        /*
        if(iter == level_time->second.second.end())
        {
                cerr << "g = " << g << "; time = " << time << endl;
                cerr << "Error" << endl;
        }
        */

        // Get a copy of the group record
        group_time_t group_time = *iter;

        // Update its time in the 
        group_time.second = time + time_offset;

        /*
        cerr << time << " + " << time_offset << endl;
        cerr << (*iter).first << " " << (*iter).second << endl;
        cerr << group_time.first << " " << group_time.second << endl
        */

        // Update the group record in the time-sorted collection
        level_time->second.second.erase(iter);                                                                          // O(log(p))
        level_time->second.second.insert(group_time);                                                           // O(log(p))

        // Update the time in the group-sorted collection
        level_time->second.first.find(g)->second = time + time_offset;                          // O(log(p))

        return time + time_offset;
}

static float
recursive_update_time(int g, float time_offset)                                                                 // O(b log(p))
{
        float max;
        float descendant;

        // Update this group time
//cerr << "[" << __FILE__ << ";" << __FUNCTION__ << ";" << __LINE__ << "] g = " << g << "; time_offset = " << time_offset << endl;
        max = update_group_time(g, time_offset);                                                                        // O(log(p))

        // Also update all groups recursively in the group being updated
        for(int i = b * g; i < G + 1 && i < (g + 1) * b; i++)                                           // O(b * log(p))
        {
                descendant = recursive_update_time(i, time_offset);                                             // O(log(p))
                if(descendant > max) max = descendant;
        }

        return max;
}

static float
update_time(int g, float time_offset)                                                                                   // O(log^2(p))
{
#if LONGEST_TASK_FIRST
        // Update group time and its descendants'
//cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] " << time_offset << endl;
        float target_time = recursive_update_time(g, time_offset);                                      // O(b log(p))

        // Also update all anscestors, but no recursive call
        while(g > b + 1)                                                                                                                        // O(log^2(p))
        {
                g = (int)floor(g / b);

                // Update ancestor's group to what is missing to make it reach the level of group g.
                //int lvl = (int)floor(log(g) / log(b));
                int lvl = (int)floor(log2(g));
                mapping_time_t::iterator level_time = load.find(lvl);                                   // O(log(log(p)))
                float time = level_time->second.first.find(g)->second;
                time = target_time - time;

                if(time > 0)
                {
                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] " << time << endl;
                        update_group_time(g, time);                                                                                     // O(log(p))
                }
        }

        return target_time;
#else
        return recursive_update_time(g, time_offset);
#endif
}

/*
static float
Wi(int task)
{
        int return_Wi = (int)vector_Wi.find(task)->second;
        //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] Task: " << task << ", Wi = " << return_Wi << endl;
        return return_Wi;
}
*/

static float
Tau(int task)
{
        return vector_Tau.find(task)->second;
}

static float
wi(int task)
{
        int return_wi = (int)vector_wi.find(task)->second;
        //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] Task: " << task << ", wi = " << return_wi << endl;
        return return_wi;
}

static float
e(int task, int p)
{
        return matrix_e.find(task)->second.find(p)->second;
}

static float
work(int task, int p)
{
        float return_work = Tau(task) / e(task, p);
        //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] Task: " << task << ", p = " << p << ", work = " << return_work << endl;
        return return_work;
}

static float
time(int task, int p)
{
        float return_time = work(task, p) / (float)p;
        //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] Task: " << task << ", p = " << p << ", time = " << return_time << endl;
        return return_time;
}

static int
level(int p)
{
        //return (int)(L - floor(log(p) / log(b)));
        return (int)(L - floor(log2(p)));
}

#if LONGEST_TASK_FIRST
// Needed tp compare two group_time_t elements in the set whose definition comes right after
struct cmp_task : binary_function <int, int, bool>
{
        bool
        operator()(const int& x, const int& y) const
        {
#if LONGEST_WIDEST_TASK_FIRST
                if(time(x, wi(x)) == time(y, wi(y)))
                {
#if LONGEST_WIDEST_LOWEST_TASK_FIRST
                        if(wi(x) == wi(y))
                        {
                                return x < y;
                        }
                        else
                        {
#endif
                                return wi(x) > wi(y);
#if LONGEST_WIDEST_LOWEST_TASK_FIRST
                        }
#endif
                }
                else
                {
#endif
                        return time(x, (int)wi(x)) > time(y, (int)wi(y));
#if LONGEST_WIDEST_TASK_FIRST
                }
#endif
        }
};
static multiset<int, cmp_task> ordered_tasks;
#endif

static void
parse()
{
        schedule = mapping_t();
        load = mapping_time_t();
        vector_Wi = map<int, float>();
        vector_Tau = map<int, float>();
        vector_wi = map<int, float>();
        matrix_e = MatrixType();
        AmplInput data(AmplInput::floatHandlers());
        
        // Read all values
        n = (int)rec->find<Scalar<float> >("n")->getValue();
        b = (int)rec->find<Scalar<float> >("b")->getValue();
        p = (int)rec->find<Scalar<float> >("p")->getValue();

        vector_Wi = rec->find<Vector<int, float> >("Wi")->getValues();
        vector_Tau = rec->find<Vector<int, float> >("Tau")->getValues();
        vector_wi = rec->find<Vector<int, float> >("wi")->getValues();
        
        matrix_e = rec->find<Matrix<int, int, float> >("e")->getValues();

        // Compute other values from parameters
        L = (int)(log2(p));

        // Number of groups
        G = 2 * p - 1;

        // Load of each p processors, initialized to 0
        for(int i = 0; i < L + 1; i++)
        {
                // typedef pair<map<group_t, run_t>, set<group_t, run_t> > level_time_t;
                // Inserting already sorted values, takes constant time each
                by_group_t by_group;
                by_time_t by_time;
                for(int j = (int)pow((double)b, (double)i); j < (int)pow((double)b, (double)i + 1); j++)
                {
                        by_group.insert(group_time_t(j, 0));
                        by_time.insert(group_time_t(j, 0));
                }
                load.insert(pair<int, level_time_t>(i, level_time_t(by_group, by_time)));
        }
}

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

static float
group_recursive_load(int g, int b, int p, float *group)
{
        int i;
        float load, max_load = 0;

        for(i = g * b; i < (g + 1) * b && i < 2 * p; i++)
        {
                load = group_recursive_load(i, b, p, group);
                if(load > max_load) max_load = load;
        }

        return max_load + group[g - 1];
}

float
mapping_quality(const pelib::Algebra &input)
{
        float p = input.find<Scalar<float> >("p")->getValue();
        float b = input.find<Scalar<float> >("b")->getValue();
        map<int, float> tau = input.find<Vector<int, float> >("Tau")->getValues();
        map<int, float> wi = input.find<Vector<int, float> >("wi")->getValues();
        map<int, float> group = input.find<Vector<int, float> >("group")->getValues();
        map<int, map<int, float> > e = input.find<Matrix<int, int, float> >("e")->getValues();
        
        float g = 2 * p - 1;
        float *group_load = (float*)calloc((size_t)g, sizeof(float));

        // Get all the tasks's parallel time, add them to group load
        for(map<int, float>::const_iterator i = tau.begin(); i != tau.end(); i++)
        {
                float load = (float)i->second / (float)wi[i->first] / e[i->first][(int)wi[i->first]];
                group_load[(int)group[i->first] - 1] += load;
        }

        float final_load = group_recursive_load(1, (int)b, (int)p, group_load);
        free(group_load);

        return final_load;
}

Algebra
mapping_ltlg(const Algebra &record)
{
        Algebra input = record;
        struct timespec start, stop, total_time;

        rec = &input;
        parse();

        clock_gettime(CLOCK_MONOTONIC, &start); 

// Start timer here
#if LONGEST_TASK_FIRST
        ordered_tasks = multiset<int, cmp_task>();
        for(int i = 0; i < n; i++)              // O(n)
        {
                int task = i + 1;
                ordered_tasks.insert(task);                                                                                     // O(log n)
        }
#endif

        // Use a temporary vector to reduce asymptotic time with n 
        vector<pair<int, float> > schedule_vector;
                                                                                                                                                                //O(n log^2(p))
#if LONGEST_TASK_FIRST
        for(set<int>::iterator iter = ordered_tasks.begin(); iter != ordered_tasks.end(); iter++)
#else
        for(int i = 0; i < n; i++)
#endif
        {
#if LONGEST_TASK_FIRST
                int task = *iter;
#else
                int task = i + 1;;
#endif
                float task_wi = wi(task);
                float task_time = time(task, (int)wi(task));
        //cerr << "(" << task_time << ", " << task_wi << ")" << endl;

                int task_level = level((int)task_wi);
                mapping_time_t::iterator level_queue = load.find(task_level);
                level_time_t level_time = level_queue->second;
                by_time_t group_queue = level_time.second;
                by_time_t::iterator group_queue_iter = group_queue.begin();
                int group = group_queue_iter->first;
                // All the above in one line
                //int group = load.find(level(task_wi))->second.second.begin()->first;
                
                schedule_vector.push_back(pair<int, int>(task, group));                                 // O(1)
        //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] " << task_time << endl;
                update_time(group, task_time);                                          // O(log^2(p))

                for(by_time_t::iterator j = group_queue.begin(); j != group_queue.end(); j++)
                {
                        //level_time_t level_time = level_queue->second;
                //cerr << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] group: " << j->first << "; time: " << level_queue->second.first.find(j->first)->second << endl;
                }
        }
        clock_gettime(CLOCK_MONOTONIC, &stop);

        // Build the final schedule cppelib structure from schedule_vector
        // Outside time measurement
        for(vector<pair<int, float> >::iterator iter = schedule_vector.begin(); iter != schedule_vector.end(); iter++)
        {
                schedule.push_back(pair<int, int>(iter->first, (int)iter->second));
        }
        
        timespec_subtract(&total_time, &stop, &start);
        Scalar<float> param_time("_total_solve_elapsed_time", (total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec);
        rec->insert(&param_time);

        // Make
        map<int, float> vector_group;
        bool all_sequential = true;
        for(mapping_t::iterator iter = schedule.begin(); iter != schedule.end(); iter++)
        {
                all_sequential = all_sequential && wi(iter->first) == 1;
                vector_group.insert(pair<int, int>(iter->first, iter->second));
        }
        Vector<int, float> group("group", vector_group);
        rec->insert(&group);

        Scalar<float> all_seq("all_sequential", (int)all_sequential);
        rec->insert(&all_seq);

        return input;
}

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

        return n * (p * log(p) + log(p) * log(p));
}