pelib  2.0.0
src/Schedule.cpp
Go to the documentation of this file.
00001 /*
00002  Copyright 2015 Nicolas Melot
00003 
00004  This file is part of Pelib.
00005 
00006  Pelib is free software: you can redistribute it and/or modify
00007  it under the terms of the GNU General Public License as published by
00008  the Free Software Foundation, either version 3 of the License, or
00009  (at your option) any later version.
00010 
00011  Pelib is distributed in the hope that it will be useful,
00012  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
00014  GNU General Public License for more details.
00015 
00016  You should have received a copy of the GNU General Public License
00017  along with Pelib. If not, see <http://www.gnu.org/licenses/>.
00018 */
00019 
00020 
00021 #include <set>
00022 #include <string>
00023 
00024 #include <pelib/Schedule.hpp>
00025 #include <pelib/Scalar.hpp>
00026 #include <pelib/Vector.hpp>
00027 #include <pelib/Matrix.hpp>
00028 #include <pelib/Set.hpp>
00029 #include <pelib/CastException.hpp>
00030 #include <pelib/PelibException.hpp>
00031 
00032 #ifdef debug
00033 #undef debug
00034 #endif 
00035 
00036 #define debug(expr) cout << "[" << __FILE__ << ":" << __FUNCTION__ << ":" << __LINE__ << "] " << (#expr) << " = \"" << (expr) << "\"." << endl;
00037 
00038 using namespace std;
00039 
00040 namespace pelib
00041 {
00042         Schedule::Schedule(const std::string &name, const std::string &appName, const table &schedule)
00043         {
00044                 this->name = name;
00045                 this->appName = appName;
00046         
00047                 // Copy taskgraph       
00048                 this->setSchedule(schedule);
00049         }
00050 
00051         Schedule::~Schedule()
00052         {
00053                 // Do nothing
00054         }
00055 
00056         void
00057         Schedule::setSchedule(const table &schedule)
00058         {
00059                 this->schedule = Schedule::table();
00060                 this->tasks.clear();
00061                 this->core_tasks.clear();
00062 
00063                 for(table::const_iterator i = schedule.begin(); i != schedule.end(); i++)
00064                 {
00065                         set<const Task*> this_core_tasks;
00066                         sequence new_sequence;
00067                         for(sequence::const_iterator j = i->second.begin(); j != i->second.end(); j++)
00068                         {
00069                                 const Task *task = j->second.first;
00070                                 Task t = *task;
00071                                 this->tasks.insert(t);
00072                                 const Task &task_ref = *(this->getTasks().find(t));
00073                                 pair<float, work> new_pair = pair<float, work>(j->first, work(&task_ref, j->second.second));
00074                                 new_sequence.insert(new_pair);
00075 
00076                                 // Insert a reference to this task in the core's task list
00077                                 this_core_tasks.insert(&task_ref);
00078                         }
00079 
00080                         this->schedule.insert(pair<int, sequence>(i->first, new_sequence));
00081 
00082                         // Add the tasks list to the list of lists of tasks
00083                         this->core_tasks.insert(pair<int, set<const Task*> >(i->first, this_core_tasks));
00084                 }
00085         }
00086 
00087         Schedule::Schedule(const std::string &name, const Algebra &algebra)
00088         {
00089                 buildFromAlgebra(name, string("Generated from Algebra"), algebra);      
00090         }
00091 
00092         Schedule::Schedule(const std::string &name, const string &appName, const Algebra &algebra)
00093         {
00094                 buildFromAlgebra(name, appName, algebra);
00095         }
00096 
00097         Schedule::Schedule(const Schedule& src)
00098         {
00099                 this->name = src.getName();
00100                 this->appName = src.getName();
00101                 this->tasks = src.getTasks();
00102                 this->setSchedule(src.getSchedule());
00103         }
00104 
00105         void
00106         Schedule::buildFromAlgebra(const string &name, const string &appName, const Algebra &algebra)
00107         {
00108                 this->name = name;
00109                 this->appName = appName;
00110 
00111                 const Vector<int, float> *tau = algebra.find<Vector<int, float> >("Tau");
00112                 const Vector<int, float> *start = algebra.find<Vector<int, float> >("start");
00113                 const Vector<int, float> *wi = algebra.find<Vector<int, float> >("wi");
00114                 const Matrix<int, int, float> *sched = algebra.find<Matrix<int, int, float> >("schedule");
00115                 const Vector<int, float> *freq = algebra.find<Vector<int, float> >("frequency");
00116                 const Vector<int, string> *task_name = algebra.find<Vector<int, string> >("name");
00117 
00118                 table schedule;
00119                 set<Task> tasks;
00120         
00121                 if(start == NULL || tau == NULL || wi == NULL || sched == NULL || freq == NULL || task_name == NULL)
00122                 {
00123                         throw CastException("Missing some input data structure instance. Check start, Tau, wi, schedule, frequency and name.");
00124                 }
00125                 else
00126                 {
00127                         for(map<int, map<int, float> >::const_iterator i = sched->getValues().begin(); i != sched->getValues().end(); i++)
00128                         {
00129                                 sequence core_schedule;
00130                                 
00131                                 for(map<int, float>::const_iterator j = i->second.begin(); j != i->second.end(); j++)
00132                                 {
00133                                         if(floor(j->second) > 0)
00134                                         {
00135                                                 string task_str;
00136                                                 if(task_name == NULL)
00137                                                 {
00138                                                         stringstream estr;
00139                                                         estr << "task_" << j->second;
00140                                                         task_str = string(estr.str());
00141                                                 }
00142                                                 else
00143                                                 {
00144                                                         task_str = string(task_name->getValues().find((int)j->second)->second);
00145                                                 }
00146 
00147                                                 tasks.insert(Task(task_str));
00148                                                 Task &task = (Task&)*tasks.find(task_str);
00149                                                 task.setModule("dummy");
00150 
00151                                                 if(task.getWorkload() > 0)
00152                                                 {
00153                                                         task.setWidth(wi->getValues().find((int)floor(j->second))->second);
00154                                                         task.setFrequency(freq->getValues().find((int)floor(j->second))->second);
00155                                                         task.setWorkload(tau->getValues().find((int)floor(j->second))->second);
00156                                                         task.setStartTime(start->getValues().find((int)j->second)->second);
00157                                                         core_schedule.insert(pair<float, work>(task.getStartTime(), work(&task, tau->getValues().find((int)floor(j->second))->second)));
00158                                                 }
00159                                         }
00160                                 }
00161 
00162                                 schedule.insert(pair<int, sequence>(i->first, core_schedule));
00163                         }
00164                 }
00165 
00166                 for(Schedule::table::const_iterator i = schedule.begin(); i != schedule.end(); i++)
00167                 {
00168                         for(Schedule::sequence::const_iterator j = i->second.begin(); j != i->second.end(); j++)
00169                         {
00170                                 string taskid = j->second.first->getName();
00171                         }
00172                 }
00173 
00174                 this->tasks = tasks;
00175                 this->setSchedule(schedule);
00176         }
00177         
00178         Schedule*
00179         Schedule::clone() const
00180         {
00181                 Schedule *clone = new Schedule(getName(), getName(), getSchedule());
00182 
00183                 return clone;
00184         }
00185 
00186         Algebra
00187         Schedule::buildAlgebra() const
00188         {
00189                 Algebra algebra;
00190                 
00191                 map<string, int> taskid2id; 
00192                 for(table::const_iterator i = schedule.begin(); i != schedule.end(); i++)
00193                 {
00194                         for(sequence::const_iterator j = i->second.begin(); j != i->second.end(); j++)
00195                         {
00196                                 taskid2id.insert(pair<string, int>(j->second.first->getName(), std::distance(this->getTasks().begin(), this->getTasks().find(*j->second.first)) + 1));
00197                         }
00198                 }
00199 
00200                 map<int, map<int, float> > sched;
00201                 map<int, float> frequencies, start;
00202                 table schedule = getSchedule();
00203 
00204                 size_t ordering, max_tasks = 0;
00205                 for(table::const_iterator i = schedule.begin(); i != schedule.end(); i++)
00206                 {
00207                         map<int, float> schedule_row;
00208                         int core = i->first;
00209         
00210                         ordering = 0;
00211                         for(sequence::const_iterator j = i->second.begin(); j != i->second.end(); j++, ordering++)
00212                         {
00213                                 int id = taskid2id.find(j->second.first->getName())->second;
00214                                 schedule_row.insert(pair<int, int>(ordering, id));
00215                                 frequencies.insert(pair<int, float>(id, j->second.first->getFrequency()));
00216 
00217                                 max_tasks = ordering > max_tasks ? ordering : max_tasks;
00218                                 start.insert(pair<int, float>(std::distance(this->getTasks().begin(), this->getTasks().find(j->second.first->getName())), j->second.first->getStartTime())); 
00219                         }
00220 
00221                         sched.insert(pair<int, map<int, float> >(core, schedule_row));
00222                 }
00223 
00224                 // pad with 0
00225                 for(table::const_iterator i = schedule.begin(); i != schedule.end(); i++)
00226                 {
00227                         size_t base = i->second.size();
00228                         for(ordering = base; ordering < max_tasks; ordering++)
00229                         {
00230                                 sched.find(i->first)->second.insert(pair<int, int>(ordering, 0));
00231                         }
00232                 }
00233 
00234                 Matrix<int, int, float> ampl_schedule("schedule", sched);
00235                 Vector<int, float> ampl_frequencies("frequency", frequencies);
00236                 Vector<int, float> ampl_start("start", start);
00237 
00238                 algebra.insert(&ampl_schedule);
00239                 algebra.insert(&ampl_frequencies);
00240                 algebra.insert(&ampl_start);
00241 
00242                 return algebra;
00243         }
00244 
00245         std::string
00246         Schedule::getName() const
00247         {
00248                 return this->name;
00249         }
00250 
00251         std::string
00252         Schedule::getAppName() const
00253         {
00254                 return this->appName;
00255         }
00256 
00257         const Schedule::table&
00258         Schedule::getSchedule() const
00259         {
00260                 return schedule;
00261         }
00262         
00263         const set<Task>&
00264         Schedule::getTasks() const
00265         {
00266                 return this->tasks;
00267         }
00268 
00269         const Task&
00270         Schedule::getTask(int id) const
00271         {
00272                 set<Task>::const_iterator it = this->getTasks().begin();
00273                 std::advance(it, id - 1);
00274                 return *it;
00275         }
00276 
00277         Schedule&
00278         Schedule::operator=(const Schedule &copy)
00279         {
00280                 this->name = name;
00281                 this->appName = appName;
00282                 this->tasks = copy.getTasks();
00283         
00284                 // Copy taskgraph       
00285                 this->setSchedule(schedule);
00286 
00287                 return *this;
00288         }
00289 
00290         const set<const Task*>&
00291         Schedule::getTasks(int core) const
00292         {
00293                 return this->core_tasks.find(core)->second;
00294         }
00295 
00296         set<const Task*>
00297         Schedule::getTasksSharedMemoryIsland(const set<int>& islands, const Platform &pt) const
00298         {
00299                 set<const Task*> tasks;
00300 
00301                 for(set<int>::const_iterator i = islands.begin(); i != islands.end(); i++)
00302                 {
00303                         Platform::islands::const_iterator ii = pt.getSharedMemoryIslands().begin();
00304                         std::advance(ii, *i - 1);
00305 
00306                         for(Platform::island::const_iterator j = ii->begin(); j != ii->end(); j++)
00307                         {
00308                                 size_t core_id = std::distance(pt.getCores().begin(), pt.getCores().find(*j)) + 1;
00309                                 for(set<const Task*>::const_iterator k = this->getTasks((int)core_id).begin(); k !=  this->getTasks((int)core_id).end(); k++)
00310                                 {
00311                                         tasks.insert(*k);
00312                                 }
00313                         }
00314                 }
00315 
00316                 return tasks;
00317         }
00318 
00319         multiset<const Task*>
00320         Schedule::getRemoteSharedMemoryIslandProducers(const set<int> &islands, const Taskgraph &tg, const Platform &pt) const
00321         {
00322                 multiset<const Task*> producers;
00323                 for(set<int>::const_iterator i = islands.begin(); i != islands.end(); i++)
00324                 {
00325                         if(*i > (int)pt.getSharedMemoryIslands().size())
00326                         {
00327                                 throw CastException("Requested shared memory islands not existing in platform.");
00328                         }
00329                 }
00330 
00331                 set<const Task*> tasks_in_islands = this->getTasksSharedMemoryIsland(islands, pt);
00332                 for(set<const Task*>::const_iterator i = tasks_in_islands.begin(); i != tasks_in_islands.end(); i++)
00333                 {
00334                         const Task *task_p = *i;
00335                         if(tg.getTasks().find(*task_p) == tg.getTasks().end())
00336                         {
00337                                 stringstream ss;
00338                                 ss << "Cannot find task \"" << task_p->getName() << "\" in taskgraph.";
00339                                 throw CastException(ss.str());
00340                         }
00341                         const Task &task_tg = *tg.getTasks().find(*task_p);
00342                         set<int> consumer_cores = this->getCores(task_tg);
00343                         set<int>::const_iterator j = consumer_cores.begin();
00344                         Platform::islands consumer_core_islands = pt.getSharedMemoryIslands(*j);
00345                         for(; j != consumer_cores.end(); j++)
00346                         {
00347                                 if(pt.getSharedMemoryIslands(*j) != consumer_core_islands)
00348                                 {
00349                                         throw CastException("Task mapped to cores that belong to different shared memory islands.");
00350                                 }       
00351                         }
00352                         
00353                         for(set<const Link*>::const_iterator j = task_tg.getProducers().begin(); j != task_tg.getProducers().end(); j++)
00354                         {
00355                                 const Link *l = *j;
00356                                 const Task *producer = l->getProducer();
00357                                 set<int> producer_cores = this->getCores(*producer);
00358                                 set<int>::const_iterator k = producer_cores.begin();
00359                                 Platform::islands producer_core_islands = pt.getSharedMemoryIslands(*k);
00360                                 for(; k != producer_cores.end(); k++)
00361                                 {
00362                                         if(pt.getSharedMemoryIslands(*k) != producer_core_islands)
00363                                         {
00364                                                 throw CastException("Task mapped to cores that belong to different shared memory islands.");
00365                                         }       
00366                                 }
00367 
00368                                 if(consumer_core_islands != producer_core_islands)
00369                                 {
00370                                         producers.insert(producer);
00371                                 }
00372                         }
00373                 }
00374 
00375                 return producers;
00376         }
00377 
00378         multiset<const Task*>
00379         Schedule::getRemoteSharedMemoryIslandTaskProducers(const Task &t, const Taskgraph &tg, const Platform &pt) const
00380         {
00381                 multiset<const Task*> producers;
00382                 if(this->getTasks().find(t) == this->getTasks().end())
00383                 {
00384                         stringstream ss;
00385                         ss << "Task \"" << t.getName() << "\" does not figure in schedule.";
00386                         throw CastException(ss.str());
00387                 }
00388 
00389                 if(tg.getTasks().find(t) == tg.getTasks().end())
00390                 {
00391                         stringstream ss;
00392                         ss << "Task \"" << t.getName() << "\" does not figure in taskgraph.";
00393                         throw CastException(ss.str());
00394                 }
00395 
00396                 const Task &task_tg = *tg.getTasks().find(t);
00397                 set<int> consumer_cores = this->getCores(task_tg);
00398                 set<int>::const_iterator j = consumer_cores.begin();
00399                 Platform::islands consumer_core_islands = pt.getSharedMemoryIslands(*j);
00400                 for(; j != consumer_cores.end(); j++)
00401                 {
00402                         if(pt.getSharedMemoryIslands(*j) != consumer_core_islands)
00403                         {
00404                                 throw CastException("Task mapped to cores that belong to different shared memory islands.");
00405                         }       
00406                 }
00407         
00408                 for(set<const Link*>::const_iterator j = task_tg.getProducers().begin(); j != task_tg.getProducers().end(); j++)
00409                 {
00410                         const Link *l = *j;
00411                         const Task *producer = l->getProducer();
00412                         set<int> producer_cores = this->getCores(*producer);
00413                         set<int>::const_iterator k = producer_cores.begin();
00414 
00415                         Platform::islands producer_core_islands = pt.getSharedMemoryIslands(*k);
00416                         for(; k != producer_cores.end(); k++)
00417                         {
00418                                 if(pt.getSharedMemoryIslands(*k) != producer_core_islands)
00419                                 {
00420                                         throw CastException("Task mapped to cores that belong to different shared memory islands.");
00421                                 }       
00422                         }
00423 
00424                         if(consumer_core_islands != producer_core_islands)
00425                         {
00426                                 producers.insert(producer);
00427                         }
00428                 }
00429 
00430                 return producers;
00431         }
00432 
00433         multiset<const Task*>
00434         Schedule::getRemoteTaskConsumers(const Task &t, const Taskgraph &tg, const Platform &pt) const
00435         {
00436                 set<Task>::const_iterator iter = tg.getTasks().find(t);
00437                 if(iter == tg.getTasks().end())
00438                 {
00439                         throw PelibException("Task in schedule does not exist in taskgraph.");
00440                 }
00441                 const Task &task = *iter;       
00442 
00443                 multiset<const Task*> consumers;
00444                 for(set<const Link*>::const_iterator j = task.getConsumers().begin(); j != task.getConsumers().end(); j++)
00445                 {
00446                         const Task *consumer = (*j)->getConsumer();
00447                         if(this->getCores(t) != this->getCores(*consumer))
00448                         {
00449                                 consumers.insert(consumer);
00450                         }
00451                 }
00452         
00453                 return consumers;
00454         }
00455 
00456         multiset<const Task*>
00457         Schedule::getRemoteTaskProducers(const Task &t, const Taskgraph &tg, const Platform &pt) const
00458         {
00459                 set<Task>::const_iterator iter = tg.getTasks().find(t);
00460                 if(iter == tg.getTasks().end())
00461                 {
00462                         throw PelibException("Task in schedule does not exist in taskgraph.");
00463                 }
00464                 const Task &task = *iter;       
00465 
00466                 multiset<const Task*> producers;
00467                 for(set<const Link*>::const_iterator j = task.getProducers().begin(); j != task.getProducers().end(); j++)
00468                 {
00469                         const Task *producer = (*j)->getProducer();
00470                         if(this->getCores(t) != this->getCores(*producer))
00471                         {
00472                                 producers.insert(producer);
00473                         }
00474                 }
00475         
00476                 return producers;
00477         }
00478 
00479         multiset<const Task*>
00480         Schedule::getRemoteConsumers(int core, const Taskgraph &tg, const Platform &pt) const
00481         {
00482                 multiset<const Link*> links = getRemoteConsumersLink(core, tg, pt);
00483                 multiset<const Task*> tasks;
00484                 for(multiset<const Link*>::iterator i = links.begin(); i != links.end(); i++)
00485                 {
00486                         const Link* link = *i;
00487                         tasks.insert(link->getConsumer());
00488                 }
00489 
00490                 return tasks;
00491         }
00492 
00493         multiset<const Link*>
00494         Schedule::getRemoteConsumersLink(int core, const Taskgraph &tg, const Platform &pt) const
00495         {
00496                 table::const_iterator iter = this->getSchedule().find(core);
00497                 if(iter == this->getSchedule().end())
00498                 {
00499                         throw PelibException("Cannot find requested core in schedule");
00500                 }
00501 
00502                 const sequence &seq = iter->second;
00503 
00504                 multiset<const Link*> consumers;
00505                 for(sequence::const_iterator i = seq.begin(); i != seq.end(); i++)
00506                 {
00507                         set<Task>::const_iterator iter = tg.getTasks().find(*i->second.first);
00508                         if(iter == tg.getTasks().end())
00509                         {
00510                                 throw PelibException("Task in schedule does not exist in taskgraph.");
00511                         }
00512                         const Task &task = *iter;       
00513 
00514                         for(set<const Link*>::const_iterator j = task.getConsumers().begin(); j != task.getConsumers().end(); j++)
00515                         {
00516                                 const Task *consumer = (*j)->getConsumer();
00517                                 if(this->getCores(*i->second.first) != this->getCores(*consumer))
00518                                 {
00519                                         consumers.insert(*j);
00520                                 }
00521                         }
00522                 }
00523         
00524                 return consumers;
00525         }
00526 
00527         multimap<const Task*, const Link*>
00528         Schedule::getRemoteConsumersTaskLink(int core, const Taskgraph &tg, const Platform &pt) const
00529         {
00530                 multiset<const Link*> links = getRemoteConsumersLink(core, tg, pt);
00531                 multimap<const Task*, const Link*> tasklink;
00532                 for(multiset<const Link*>::iterator i = links.begin(); i != links.end(); i++)
00533                 {
00534                         const Link* link = *i;
00535                         tasklink.insert(pair<const Task*, const Link*>(link->getConsumer(), *i));
00536                 }
00537 
00538                 return tasklink;
00539         }
00540 
00541         multiset<const Task*>
00542         Schedule::getRemoteProducers(int core, const Taskgraph &tg, const Platform &pt) const
00543         {
00544                 multiset<const Link*> links = getRemoteProducersLink(core, tg, pt);
00545                 multiset<const Task*> tasks;
00546                 for(multiset<const Link*>::iterator i = links.begin(); i != links.end(); i++)
00547                 {
00548                         const Link* link = *i;
00549                         tasks.insert(link->getProducer());
00550                 }
00551 
00552                 return tasks;
00553         }
00554 
00555         multiset<const Link*>
00556         Schedule::getRemoteProducersLink(int core, const Taskgraph &tg, const Platform &pt) const
00557         {
00558                 table::const_iterator iter = this->getSchedule().find(core);
00559                 if(iter == this->getSchedule().end())
00560                 {
00561                         throw PelibException("Cannot find requested core in schedule");
00562                 }
00563 
00564                 const sequence &seq = iter->second;
00565 
00566                 multiset<const Link*> producers;
00567                 for(sequence::const_iterator i = seq.begin(); i != seq.end(); i++)
00568                 {
00569                         set<Task>::const_iterator iter = tg.getTasks().find(*i->second.first);
00570                         if(iter == tg.getTasks().end())
00571                         {
00572                                 throw PelibException("Task in schedule does not exist in taskgraph.");
00573                         }
00574                         const Task &task = *iter;       
00575 
00576                         for(set<const Link*>::const_iterator j = task.getProducers().begin(); j != task.getProducers().end(); j++)
00577                         {
00578                                 const Task *producer = (*j)->getProducer();
00579                                 if(this->getCores(*i->second.first) != this->getCores(*producer))
00580                                 {
00581                                         producers.insert(*j);
00582                                 }
00583                         }
00584                 }
00585         
00586                 return producers;
00587         }
00588 
00589         multimap<const Task*, const Link*>
00590         Schedule::getRemoteProducersTaskLink(int core, const Taskgraph &tg, const Platform &pt) const
00591         {
00592                 multiset<const Link*> links = getRemoteProducersLink(core, tg, pt);
00593                 multimap<const Task*, const Link*> tasklink;
00594                 for(multiset<const Link*>::iterator i = links.begin(); i != links.end(); i++)
00595                 {
00596                         const Link* link = *i;
00597                         tasklink.insert(pair<const Task*, const Link*>(link->getProducer(), *i));
00598                 }
00599 
00600                 return tasklink;
00601         }
00602 
00603         multiset<const Task*>
00604         Schedule::getRemoteSharedMemoryIslandConsumers(const set<int> &islands, const Taskgraph &tg, const Platform &pt) const
00605         {
00606                 multiset<const Task*> consumers;
00607                 for(set<int>::const_iterator i = islands.begin(); i != islands.end(); i++)
00608                 {
00609                         if(*i > (int)pt.getSharedMemoryIslands().size())
00610                         {
00611                                 throw CastException("Requested shared memory islands not existing in platform.");
00612                         }
00613                 }
00614 
00615                 set<const Task*> tasks_in_islands = this->getTasksSharedMemoryIsland(islands, pt);
00616                 for(set<const Task*>::const_iterator i = tasks_in_islands.begin(); i != tasks_in_islands.end(); i++)
00617                 {
00618                         const Task *task_p = *i;
00619                         if(tg.getTasks().find(*task_p) == tg.getTasks().end())
00620                         {
00621                                 stringstream ss;
00622                                 ss << "Trying to schedule task \"" << task_p->getName() << "\" that does not exist in taskgraph.";
00623                                 throw CastException(ss.str());
00624                         }
00625                         const Task &task_tg = *tg.getTasks().find(*task_p);
00626                         set<int> producer_cores = this->getCores(task_tg);
00627                         set<int>::const_iterator j = producer_cores.begin();
00628                         Platform::islands producer_core_islands = pt.getSharedMemoryIslands(*j);
00629                         for(; j != producer_cores.end(); j++)
00630                         {
00631                                 if(pt.getSharedMemoryIslands(*j) != producer_core_islands)
00632                                 {
00633                                         throw CastException("Task mapped to cores that belong to different shared memory islands.");
00634                                 }       
00635                         }
00636                         
00637                         for(set<const Link*>::const_iterator j = task_tg.getConsumers().begin(); j != task_tg.getConsumers().end(); j++)
00638                         {
00639                                 const Link *l = *j;
00640                                 const Task *consumer = l->getConsumer();
00641                                 set<int> consumer_cores = this->getCores(*consumer);
00642                                 set<int>::const_iterator k = consumer_cores.begin();
00643 
00644                                 Platform::islands consumer_core_islands = pt.getSharedMemoryIslands(*k);
00645                                 for(; k != consumer_cores.end(); k++)
00646                                 {
00647                                         if(pt.getSharedMemoryIslands(*k) != consumer_core_islands)
00648                                         {
00649                                                 throw CastException("Task mapped to cores that belong to different shared memory islands.");
00650                                         }       
00651                                 }
00652 
00653                                 if(producer_core_islands != consumer_core_islands)
00654                                 {
00655                                         consumers.insert(consumer);
00656                                 }
00657                         }
00658                 }
00659 
00660                 return consumers;
00661         }
00662 
00663         multiset<const Task*>
00664         Schedule::getRemoteSharedMemoryIslandTaskConsumers(const Task &t, const Taskgraph &tg, const Platform &pt) const
00665         {
00666                 multiset<const Task*> consumers;
00667                 if(this->getTasks().find(t) == this->getTasks().end())
00668                 {
00669                         stringstream ss;
00670                         ss << "Task \"" << t.getName() << "\" does not figure in schedule.";
00671                         throw CastException(ss.str());
00672                 }
00673 
00674                 if(tg.getTasks().find(t) == tg.getTasks().end())
00675                 {
00676                         stringstream ss;
00677                         ss << "Task \"" << t.getName() << "\" does not figure in taskgraph.";
00678                         throw CastException(ss.str());
00679                 }
00680 
00681                 const Task &task_tg = *tg.getTasks().find(t);
00682                 set<int> producer_cores = this->getCores(task_tg);
00683                 set<int>::const_iterator j = producer_cores.begin();
00684                 Platform::islands producer_core_islands = pt.getSharedMemoryIslands(*j);
00685                 for(; j != producer_cores.end(); j++)
00686                 {
00687                         if(pt.getSharedMemoryIslands(*j) != producer_core_islands)
00688                         {
00689                                 throw CastException("Task mapped to cores that belong to different shared memory islands.");
00690                         }       
00691                 }
00692                 
00693                 for(set<const Link*>::const_iterator j = task_tg.getConsumers().begin(); j != task_tg.getConsumers().end(); j++)
00694                 {
00695                         const Link *l = *j;
00696                         const Task *consumer = l->getConsumer();
00697                         set<int> consumer_cores = this->getCores(*this->getTasks().find(*consumer));
00698                         set<int>::const_iterator k = consumer_cores.begin();
00699 
00700                         Platform::islands consumer_core_islands = pt.getSharedMemoryIslands(*k);
00701                         for(; k != consumer_cores.end(); k++)
00702                         {
00703                                 if(pt.getSharedMemoryIslands(*k) != consumer_core_islands)
00704                                 {
00705                                         throw CastException("Task mapped to cores that belong to different shared memory islands.");
00706                                 }       
00707                         }
00708 
00709                         if(producer_core_islands != consumer_core_islands)
00710                         {
00711                                 consumers.insert(consumer);
00712                         }
00713                 }
00714 
00715                 return consumers;
00716         }
00717 
00718         const set<int>
00719         Schedule::getCores(const Task &t) const
00720         {
00721                 if(this->getTasks().find(t) == this->getTasks().end())
00722                 {
00723                         stringstream ss;
00724                         ss << "Task \"" << t.getName() << "\" does not figure in schedule.";
00725                         throw PelibException(ss.str());
00726                 }
00727                 const Task &tt = *this->getTasks().find(t);
00728 
00729                 set<int> cores;
00730                 for(table::const_iterator i = this->getSchedule().begin(); i != this->getSchedule().end(); i++)
00731                 {
00732                         for(sequence::const_iterator j = i->second.begin(); j != i->second.end(); j++)
00733                         {
00734                                 if(*(j->second.first) == tt)
00735                                 {
00736                                         cores.insert(i->first);
00737                                 }
00738                         }
00739                 }
00740 
00741                 return cores;
00742         }
00743 
00744         Algebra
00745         Schedule::addStartTime(const Algebra &data, const Taskgraph &tg, const Platform &platform)
00746         {
00747                 // Now browse all tasks in all cores and compute a starting time matrix
00748                 Algebra sched = data;
00749                 Algebra input = tg.buildAlgebra(platform);
00750                 input = input.merge(platform.buildAlgebra());
00751                 input = input.merge(sched);
00752 
00753                 map<int, float> start_time = input.find<Vector<int, float> >("Tau")->getValues();
00754                 map<int, float> frequency = input.find<Vector<int, float> >("frequency")->getValues();
00755                 map<int, float> workload = input.find<Vector<int, float> >("Tau")->getValues();
00756                 map<int, float> width = input.find<Vector<int, float> >("wi")->getValues();
00757                 map<int, float> max_width = input.find<Vector<int, float> >("Wi")->getValues();
00758                 map<int, map<int, float> > efficiency = input.find<Matrix<int, int, float> >("e")->getValues();
00759                 map<int, map<int, float> > map_sched = input.find<Matrix<int, int, float> >("schedule")->getValues();
00760 
00761                 for(map<int, float>::iterator i = start_time.begin(); i != start_time.end(); i++)
00762                 {
00763                         i->second = 0;
00764                 }
00765 
00766                 for(map<int, map<int, float> >::const_iterator i = map_sched.begin(); i != map_sched.end(); i++)
00767                 {
00768                         double mystart = 0;
00769                         for(map<int, float>::const_iterator j = i->second.begin(); j != i->second.end(); j++)
00770                         {
00771                                 int n = (int)j->second;
00772                                 if(n > 0)
00773                                 {
00774                                         if(start_time.find((int)n)->second < mystart)
00775                                         {
00776                                                 start_time.find((int)n)->second = mystart;
00777                                         }
00778 
00779                                         double tau = workload.find((int)n)->second;
00780                                         size_t wi = (size_t)floor((width.find((int)n)->second + 0.5));
00781                                         size_t Wi = (size_t)max_width.find((int)n)->second;
00782                                         double e = wi <= Wi ? efficiency.find((int)n)->second.find((int)wi)->second : 1e-06;
00783                                         double f = frequency.find((int)n)->second;
00784                                         double delta = (tau / (wi * e) / f);
00785                                         mystart = mystart + delta;
00786                                 }
00787                         }
00788                 }
00789 
00790                 const Vector<int, string> *name = input.find<Vector<int, string> >("name");
00791                 if(name == NULL)
00792                 {
00793                         map<int, string> names;
00794                         for(set<Task>::const_iterator iter = tg.getTasks().begin(); iter != tg.getTasks().end(); iter++)
00795                         {
00796                                 names.insert(pair<int, string>(std::distance(tg.getTasks().begin(), iter) + 1, iter->getName()));
00797                         }
00798 
00799                         name = new Vector<int, string>("name", names);
00800                         sched.insert(name);
00801                 }
00802 
00803                 Vector<int, float> *start = new Vector<int, float>("start", start_time);
00804                 sched.insert(start);
00805 
00806                 return sched;
00807         }
00808 }