src/lpt.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 <pelib/Task.hpp>
#include <pelib/XMLSchedule.hpp>

#include <pelib/scheduler.h>

#ifdef debug
#undef debug
#endif

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

using namespace std;
using namespace pelib;

// Compare task per workload
struct task_per_work : binary_function <Task, Task, bool>
{
        bool
        operator()(const Task &t1, const Task &t2) const
        {
                if(t1.isStreaming() == t2.isStreaming())
                {
                        if(t1.getWorkload() == t2.getWorkload())
                        {
                                return t2.getName().compare(t1.getName());
                        }
                        else
                        {
                                return t2.getWorkload() < t1.getWorkload();
                        }
                }
                else
                {
                        return t2.isStreaming() < t1.isStreaming();
                }
        }
};

// Compare sequences per workload
struct core_per_work : binary_function <Schedule::sequence, Schedule::sequence, bool>
{
        bool
        operator()(const Schedule::sequence &s1, const Schedule::sequence &s2) const
        {
                double stop1 = 0;
                if(s1.size() > 0)
                {
                        const Task *t1 = s1.rbegin()->second.first;
                        stop1 = s1.rbegin()->first + t1->runtime(t1->getWidth(), t1->getFrequency());
                }

                double stop2 = 0;
                if(s2.size() > 0)
                {
                        const Task *t2 = s2.rbegin()->second.first;
                        stop2 = s2.rbegin()->first + t2->runtime(t2->getWidth(), t2->getFrequency());
                }

                return stop1 < stop2;
        }
};

const pelib::Schedule*
pelib_schedule(const pelib::Taskgraph &taskgraph, const pelib::Platform &pt, size_t argc, char** argv, map<const string, double>& stats)
{
        Taskgraph tg = taskgraph;
        set<Task, task_per_work> sorted_start_tasks, sorted_tasks;
        multiset<Schedule::sequence, core_per_work> table;
        multiset<Schedule::sequence, core_per_work> start_table;
        multiset<Schedule::sequence, core_per_work> final_table;

        // Sort tasks per workload
        for(set<Task>::const_iterator i = tg.getTasks().begin(); i != tg.getTasks().end(); i++)
        {
                if(i->isStreaming())
                {
                        sorted_tasks.insert(*i);
                }
                else
                {
                        sorted_start_tasks.insert(*i);
                }
        }

        // Initialize schedule
        for(set<const Core*>::const_iterator i = pt.getCores().begin(); i != pt.getCores().end(); i++)
        {
                table.insert(Schedule::sequence());
                start_table.insert(Schedule::sequence());
        }

        // Perform mapping of starting tasks with LPT
        for(set<Task>::iterator i = sorted_start_tasks.begin(); i != sorted_start_tasks.end(); i++)
        {
                Schedule::sequence seq = *start_table.begin();
                start_table.erase(start_table.begin());

                Task &t = (Task&)*i;
                if(!t.isStreaming())
                {
                        t.setFrequency(*(*pt.getCores().begin())->getFrequencies().rbegin());
                        if(seq.size() > 0)
                        {
                                const Task *last = seq.rbegin()->second.first;
                                double start_time = last->getStartTime() + tg.getTasks().find(*last)->runtime(last->getWidth(), last->getFrequency());
                                t.setStartTime(start_time);
                                Schedule::work work(&t, t.getWorkload());
                                pair<float, Schedule::work> pair(start_time, work);
                                seq.insert(pair);
                        }
                        else
                        {
                                seq.insert(pair<float, Schedule::work>(0, Schedule::work(&t, t.getWorkload())));
                        }
                        start_table.insert(seq);
                }
        }

        // Do mapping with LPT
        // Iterate through task in decreasing workload order
        for(set<Task>::iterator i = sorted_tasks.begin(); i != sorted_tasks.end(); i++)
        {
                Schedule::sequence seq = *table.begin();
                table.erase(table.begin());

                Task &t = (Task&)*i;
                if(t.isStreaming())
                {
                        t.setFrequency(*(*pt.getCores().begin())->getFrequencies().rbegin());
                        if(seq.size() > 0)
                        {
                                const Task *last = seq.rbegin()->second.first;
                                double start_time = last->getStartTime() + tg.getTasks().find(*last)->runtime(last->getWidth(), last->getFrequency());
                                t.setStartTime(start_time);
                                Schedule::work work(&t, t.getWorkload());
                                pair<float, Schedule::work> pair(start_time, work);
                                seq.insert(pair);
                        }
                        else
                        {
                                seq.insert(pair<float, Schedule::work>(0, Schedule::work(&t, t.getWorkload())));
                        }
                        table.insert(seq);
                }
        }

        // Merge both start and run tasks into one unique sequence
        for(multiset<Schedule::sequence, core_per_work>::const_iterator i = table.begin(); i != table.end(); i++)
        {
                size_t offset = std::distance(table.begin(), i);
                multiset<Schedule::sequence, core_per_work>::iterator ii = start_table.begin();
                Schedule::sequence seq;
                if(start_table.size() > offset)
                {
                        std::advance(ii, offset);
                        seq = *ii;
                        //start_table.erase(ii);
                }
                double time = 0;
                // If there is a task already mapped to this core in the start time scheduling phase
                // Then offset the starting time by the time the last task terminates
                if(seq.size() > 0)
                {
                        const Task *last = seq.rbegin()->second.first;
                        time = last->getStartTime() + tg.getTasks().find(*last)->runtime(last->getWidth(), last->getFrequency()); // + tg.getTasks().find(*last)->runtime(last->getWidth(), last->getFrequency());
                }

                // Now add all tasks from the run table
                for(Schedule::sequence::const_iterator j = i->begin(); j != i->end(); j++)
                {
                        pair<float, Schedule::work> w = *j;
                        w.first += time;
                        Task *t = (Task*)w.second.first;
                        t->setStartTime(w.first);
                        seq.insert(w);
                }

                final_table.insert(seq);
        }

        // Do frequency scaling with bin packing
        for(multiset<Schedule::sequence, core_per_work>::const_iterator i = table.begin(); i != table.end(); i++)
        {
                // TODO: something
        }

        int core = 0;
        Schedule::table sched;
        for(multiset<Schedule::sequence, core_per_work>::const_iterator i = final_table.begin(); i != final_table.end(); i++, core++)
        {
                sched.insert(pair<int, Schedule::sequence>(pt.getCores().size() - core, *i));
        }

        Schedule *schedule = new Schedule("lpt", tg.getName(), sched);

        return schedule;
}

void
pelib_delete(pelib::Schedule *sched)
{
        delete sched;
}