src/CrownCompositeConsolidation.cpp

Go to the documentation of this file.

// The following definitions might be exchanged for others,
// when integrating the following code into the framework.
// The code implements a greedy heuristic to loadbalance the tasks
// over cores such that the l2-norm of the load vector is minimized.
// This should also minimize the l3-norm of the load vector.
// J. Keller, July 14, 2014

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <sstream>

#include <crown/allocation.h>
#include <crown/mapping.h>
#include <crown/scaling.h>
#include <crown/crown.h>
#include <crown/annealing.h>
#include <crown/CrownCompositeConsolidation.hpp>
#include <crown/CrownException.hpp>

#include <pelib/AmplInput.hpp>
#include <pelib/Schedule.hpp>
#include <pelib/Scalar.hpp>
#include <pelib/Vector.hpp>
#include <pelib/Matrix.hpp>
#include <pelib/Set.hpp>
#include <pelib/time.h>

#ifdef debug
#undef debug
#endif

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

using namespace std;
using namespace pelib;
using namespace pelib::crown;

// Quality assessment parameters
static const long long int nsec_in_sec = 1000000000;

const string CrownCompositeConsolidation::dummyTaskPrefix(DUMMY_TASK);
const string CrownCompositeConsolidation::realTaskPrefix("Real task");

Algebra
CrownCompositeConsolidation::solve(const Algebra &tg, const Algebra &pt, const pelib::Algebra &param, std::map<const std::basic_string<char>, double> &stats) const
{
        float p = pt.find<Scalar<float> >("p")->getValue();
        float logp = pow(2, floor(log(p) / log(2)));
        
        if(p == logp || 1)
        {
                Algebra taskgraph = tg;

                // Get useful problem data
                float n = taskgraph.find<Scalar<float> >("n")->getValue();
                float M = taskgraph.find<Scalar<float> >("M")->getValue();
                map<int, float> work = taskgraph.find<Vector<int, float> >("Tau")->getValues();
                map<int, float> max_width = taskgraph.find<Vector<int, float> >("Wi")->getValues();
                map<int, map<int, float> > efficiency = taskgraph.find<Matrix<int, int, float> >("e")->getValues();

                // Make mock-up efficiency function for dummy tasks
                map<int, float> dummy_e;
                dummy_e.insert(pair<int, float>(1, 1));
                for(size_t i = 1; i < p; i++)
                {
                        dummy_e.insert(pair<int, float>(i + 1, 1e-6));
                }

                // Make up task names for existing tasks
                map<int, string> name;
                for(size_t i = 0; i < n; i++)
                {
                        stringstream ssname;
                        ssname << realTaskPrefix << " " << i + 1;
                        name.insert(pair<int, string>(i + 1, ssname.str()));
                }

                // Fill up task with mock-up names, workloads and efficiency
                for(size_t i = 0; i < p - 1; i++)
                {
                        stringstream ssname;
                        ssname << dummyTaskPrefix << " " << n + i + 1;
                        name.insert(pair<int, string>(n + i + 1, ssname.str()));
                        work.insert(pair<int, float>(n + i + 1, 0));
                        max_width.insert(pair<int, float>(n + i + 1, 1));
                        efficiency.insert(pair<int, map<int, float> >(n + i + 1, dummy_e));
                }

                taskgraph.remove("n");
                taskgraph.remove("Tau");
                taskgraph.remove("Wi");
                taskgraph.remove("e");
                Scalar<float> N("n", n + p - 1);
                Vector<int, float> Tau("Tau", work);
                Vector<int, float> Wi("Wi", max_width);
                Vector<int, string> Name("name", name);
                Matrix<int, int, float> e("e", efficiency);
                taskgraph.insert(&N);
                taskgraph.insert(&Tau);
                taskgraph.insert(&Wi);
                taskgraph.insert(&Name);
                taskgraph.insert(&e);
                
                float max_freq = *pt.find<Set<float> >("F")->getValues().rbegin();

                // Compute all indices of dummy tasks
                vector<size_t> dummy_index;
                for(size_t i = 0; i < p - 1; i++)
                {
                        //stringstream ss;
                        //ss << dummyTaskPrefix << " " << i + 1;
                        //size_t index = std::distance(tg.getTasks().begin(), tg.getTasks().find(ss.str())) + 1;
                        dummy_index.push_back(n + i + 1);               
                }

                // Get direct access to task workloads
                map<int, float> &dummy_task_workload = (map<int, float>&)taskgraph.find<Vector<int, float> >("Tau")->getValues();

                // Run Crown binary
                struct timespec start, stop, total_time;
                clock_gettime(CLOCK_MONOTONIC, &start);
                //Algebra best_schedule = crown_binary(schedule, 3);
                Algebra best_schedule = scheduler->solve(taskgraph, pt, param, stats);
                float best_quality = energy_static_dynamic_busy_idle_active(best_schedule);
                //float best_quality = best_schedule.find<Scalar<float> >("quality")->getValue();
                float best_m = best_schedule.find<Scalar<float> >("m")->getValue();
                float m = best_m;
                size_t index = 0;

                // Increase the number of cores switched off until we reach p cores or
                // until it is not possible to generate any valid schedule anymore
                while(index <= p - 1 && m >= 0)
                {
                        // Then we set the dummy tasks' only admissible width to the current number
                        // of cores to switch off
                        // Set the dummy task workload so that it must run from time 0 to M at max freqeuncy to make the deadline
                        dummy_task_workload[n + index + 1] = M * max_freq;

                        // Try to compute a new schedule
                        //Algebra current = crown_binary(schedule, 3);
                        Algebra current = scheduler->solve(taskgraph, pt, param, stats);

                        // Get the new schedule's quality and correctness
                        float quality = energy_static_dynamic_busy_idle_active(current);
                        //float quality = current.find<Scalar<float> >("quality")->getValue();
                        m = current.find<Scalar<float> >("m")->getValue();

                        // If the new schedule is correct and more energy-efficient that the best schedule
                        // the replace the best schedule
                        if((m >= 0 || M <= 0) && quality < best_quality)
                        {
                                best_schedule = current;
                                best_quality = quality;
                                best_m = m;
                        }

                        // Prepare for next task to activate
                        index++;
                }

                clock_gettime(CLOCK_MONOTONIC, &stop);

                // Remove dummy tasks
                best_schedule.remove("n");
                best_schedule.remove("Tau");
                best_schedule.remove("Wi");
                best_schedule.remove("e");
                best_schedule.remove("name");
                N = Scalar<float>("n", n);
                Tau = Vector<int, float>("Tau", work);
                Wi = Vector<int, float>("Wi", max_width);
                Name = Vector<int, string>("name", name);
                e = Matrix<int, int, float>("e", efficiency);
                best_schedule.insert(tg.find<Scalar<float> >("n"));
                best_schedule.insert(tg.find<Vector<int, float> >("Tau"));
                best_schedule.insert(tg.find<Vector<int, float> >("Wi"));
                best_schedule.insert(tg.find<Matrix<int, int, float> >("e"));

                // Remove dummy tasks from best_schedule
                map<int, float> grp = best_schedule.find<Vector<int, float> >("group")->getValues();
                map<int, float> freq = best_schedule.find<Vector<int, float> >("frequency")->getValues();
                map<int, float> size = best_schedule.find<Vector<int, float> >("wi")->getValues();
                best_schedule.remove("group");
                best_schedule.remove("frequency");
                best_schedule.remove("wi");
                for(size_t i = 0; i < p - 1; i++)
                {
                        grp.erase(grp.find(n + i + 1));
                        freq.erase(freq.find(n + i + 1));
                        size.erase(size.find(n + i + 1));
                }
                Vector<int, float> group("group", grp);
                Vector<int, float> frequency("frequency", freq);
                Vector<int, float> wi("wi", size);
                best_schedule.insert(&group);
                best_schedule.insert(&frequency);
                best_schedule.insert(&wi);

                // Report mapping quality
                stats.insert(pair<string, double>("quality", best_quality));

                // Report optimization time
                float time = (float)(total_time.tv_sec * nsec_in_sec + total_time.tv_nsec) / (float)nsec_in_sec;
                stats.insert(pair<string, double>("time_global", time));

                return best_schedule;
        }
        else
        {
                throw CrownException("Binary scheduler cannot handle non-power of two number of cores");
        }
}

CrownCompositeConsolidation::CrownCompositeConsolidation(const CrownScheduler *scheduler, bool showOutput, bool showError) : CrownComposite(scheduler, showOutput, showError)
{
        /* Do nothing else */
}

CrownCompositeConsolidation::CrownCompositeConsolidation(const Algebra &param, const CrownScheduler *scheduler, bool showOutput, bool showError) : CrownComposite(param, scheduler, showOutput, showError)
{
        /* Do nothing else */
}

CrownCompositeConsolidation::CrownCompositeConsolidation(const Taskgraph &tg, const Platform &pt, const Algebra &param, const CrownScheduler *scheduler, bool showOutput, bool showError) : CrownComposite(tg, pt, param, scheduler, showOutput, showError)
{
        /* Do nothing else */
}

CrownCompositeConsolidation::CrownCompositeConsolidation(const CrownCompositeConsolidation &src) : CrownComposite(src)
{
        /* nothing else to do */
}

float
CrownCompositeConsolidation::complexity(const Algebra &problem) const
{
        return 0;
}

float
CrownCompositeConsolidation::complexity(const Taskgraph&, const Platform&, const Algebra&) const
{
        return 0;
}

CrownCompositeConsolidation*
CrownCompositeConsolidation::clone() const
{
        return new CrownCompositeConsolidation(*this);
}

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

        // TODO: Make scheduler work without scalar b
        //param.insert(new Scalar<float>("b", 2));
        param = param.merge(scheduler->addCrownConfig(tg, pt, param, stats));

        // Take task name out
        Algebra taskgraph = tg.buildAlgebra(pt);
        Vector<int, string> name = *taskgraph.find<Vector<int, string> >("name");
        taskgraph.remove("name");

        //Perform actual work
        Algebra schedule = solve(taskgraph, pt.buildAlgebra(), param, stats);

        // Put back task names
        schedule.insert(new Vector<int, string>(name));

        // Convert crown schedule to regular algebra schedule
        schedule = CrownScheduler::crownToSchedule(schedule);

        // Add task starting time
        schedule = Schedule::addStartTime(schedule, tg, pt);

        // report scheduling complexity
        float complexity = pt.getCores().size() * crown_binary_complexity(schedule) * (allocation_fastest_complexity(schedule) + mapping_ltlg_complexity(schedule) + frequency_height_complexity(schedule));
        stats.insert(pair<string, double>("complexity", complexity));

        float M = tg.getDeadline(pt);
        float m = schedule.find<Scalar<float> >("m")->getValue();
        Schedule *sched;
        if(m < 0 && M > 0)
        {
                stats.insert(pair<string, double>("feasible", 0));
                sched = new Schedule(getShortDescription(), tg.getName(), Schedule::table());
        }
        else
        {
                stats.insert(pair<string, double>("feasible", 1));
                string desc = getShortDescription();
                sched = new Schedule(desc, tg.getName(), schedule);
        }

        Schedule final = *sched;
        delete sched;
        return final;
}

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

std::string
CrownCompositeConsolidation::getShortDescription() const
{
        return string("Cons.") + scheduler->getShortDescription();
}