runtime/onert/core/src/compiler/HEScheduler.h

   1 /*
   2  * Copyright (c) 2019 Samsung Electronics Co., Ltd. All Rights Reserved
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /**
  18  * @file  HEScheduler.h
  19  * @brief This file contains HEScheduler class to define and run task Heterogeneous Execution
  20  * Scheduler
  21  */
  22
  23 #ifndef __ONERT_COMPILER_H_E_SCHEDULER_H_
  24 #define __ONERT_COMPILER_H_E_SCHEDULER_H_
  25
  26 #include "IScheduler.h"
  27 #include "../backend/builtin/Config.h"
  28 #include "../exec/ExecTime.h"
  29
  30 #include <backend/Backend.h>
  31 #include <compiler/BackendManager.h>
  32 #include <compiler/Compiler.h>
  33 #include <ir/Graph.h>
  34 #include <ir/OperationIndexMap.h>
  35
  36 #include <map>
  37 #include <memory>
  38
  39 namespace onert
  40 {
  41
  42 namespace compiler
  43 {
  44 /**
  45  * @brief Class to schedule tasks
  46  */
  47 class HEScheduler : IScheduler
  48 {
  49 public:
  50   /**
  51    * @brief     Construct a new Heterogeneous Execution Scheduler object
  52    * @param[in] model Graph model
  53    * @param[in] backend_resolver backend resolver
  54    */
  55   HEScheduler(const std::vector<const backend::Backend *> &backends, const CompilerOptions &options)
  56     : _is_supported{}, _backends_avail_time{}, _ops_eft{},
  57       _op_to_rank{std::make_shared<ir::OperationIndexMap<int64_t>>()},
  58       _is_profiling_mode{options.he_profiling_mode}, _is_linear_exec{options.executor == "Linear"},
  59       _is_parallel_exec{options.executor == "Parallel"}
  60   {
  61     for (auto &&entry : backends)
  62     {
  63       if (entry->config()->id() == backend::builtin::Config::ID)
  64         continue;
  65       _all_backends.push_back(entry);
  66     }
  67     _backend_resolver = std::make_unique<compiler::BackendResolver>();
  68     _exec_time = std::make_unique<exec::ExecTime>(_all_backends);
  69
  70     // Find cpu backend
  71     auto cpu_backend_it =
  72       std::find_if(_all_backends.begin(), _all_backends.end(), [](const backend::Backend *backend) {
  73         return backend->config()->id() == "cpu";
  74       });
  75     if (cpu_backend_it == _all_backends.end())
  76       throw std::runtime_error("HEScheduler could be used only if 'cpu' backend is available");
  77     _cpu_backend = *cpu_backend_it;
  78   }
  79
  80 public:
  81   /**
  82    * @brief   Task scheduling
  83    *
  84    * @note    The main idea is taken from HSIP algo:
  85    *          https://www.hindawi.com/journals/sp/2016/3676149/
  86    */
  87   std::unique_ptr<compiler::BackendResolver> schedule(const ir::Graph &graph) final;
  88   std::shared_ptr<ir::OperationIndexMap<int64_t>> getIndexedRanks() { return _op_to_rank; }
  89
  90 private:
  91   bool isNodeProfiled(const ir::IOperation &);
  92
  93   bool schedule(const ir::OperationIndex &, const backend::Backend *parent_backend);
  94   /**
  95    * @brief   Get earliest starting time and execution time of an operation on a backend.
  96    *
  97    * @note  Returns a time when operation's inputs are ready and backend is available
  98    *        It also returns exec time. If this is "cpu" backend, then exec_time*CPU_DELAY
  99    *
 100    * @param[in] backend: backend, for which to return the time
 101    * @param[in] index: index of an operation
 102    * @param[out] transfer_st_exec_time: est and exec time of data transfer operation
 103    *
 104    * @return earliest starting time and execution time
 105    */
 106   std::pair<int64_t, int64_t>
 107   ESTAndExecTime(const backend::Backend *backend, const ir::OperationIndex &index,
 108                  std::multimap<int64_t, int64_t> &transfer_st_exec_time);
 109   /**
 110    * @brief   Returns the latest finishing time of parents of a node.
 111    *
 112    * @param[in] backend: backend, for which to return the time
 113    * @param[in] node: node to get eft of parents
 114    * @param[out] transfer_st_exec_time: est and exec time of data transfer operation
 115    *
 116    * @return earliest finishing time of parent nodes
 117    */
 118   int64_t predMaxEFT(const backend::Backend *backend, const ir::IOperation &node,
 119                      std::multimap<int64_t, int64_t> &transfer_st_exec_time);
 120
 121   void makeRank();
 122
 123   int64_t DFSMaxRank(const ir::OperationIndex &index);
 124
 125   int64_t DFSChildrenMaxRank(const ir::OperationIndex &index);
 126   /**
 127    * @brief   Returns the time, when backend is available for at least given amount of time.
 128    *
 129    * @note  Returns either hole/gap between two performing two already scheduled operations,
 130    *        or the finishing time of the last scheduled operation
 131    *
 132    * @param[in] backend backend, for which to return the time
 133    * @param[in] starting_time time, starting which to look for gap
 134    * @param[in] time_amount amount of the time, for which to look gap
 135    *
 136    * @return time, when backend has at least time_amount free time
 137    */
 138   int64_t backendAvailableTime(const backend::Backend *backend, const int64_t &starting_time,
 139                                const int64_t &time_amount);
 140
 141   int64_t getOpTime(const backend::Backend *backend, const std::string &operation, bool quant,
 142                     uint32_t size);
 143
 144   int64_t getPermuteTime(const backend::Backend *src_backend, const backend::Backend *dst_backend,
 145                          bool quant, uint32_t size);
 146
 147   void scheduleShufflingBackends();
 148
 149   int64_t tryBackend(const ir::IOperation &node, const backend::Backend *backend);
 150
 151   /**
 152    * @brief   Schedule a node and its successor until:
 153    *            1. there is no branching or connection of multiple branches
 154    *            2. for subsequent nodes: other than predecessor's backend is prefered
 155    *
 156    * @param[in] index: index of an operation
 157    * @param[in] scheduled: a map to check if this node has already been scheduled
 158    *
 159    * @return N/A
 160    */
 161   void scheduleBranch(const ir::OperationIndex &index, ir::OperationIndexMap<bool> &scheduled);
 162
 163 private:
 164   // This variable stores backend/node pairs with unknown execution time, and hints scheduler
 165   // whether it should assign these backends to these nodes:
 166   // * It stores false for unsupported nodes
 167   // * During rank calculation with enabled profiling mode it stores true for supported nodes
 168   std::unordered_map<const backend::Backend *, std::unordered_map<std::string, bool>> _is_supported;
 169   // Finishing and starting time of each backend
 170   std::unordered_map<const backend::Backend *, std::map<int64_t, int64_t>> _backends_avail_time;
 171   ir::OperationIndexMap<int64_t> _ops_eft;
 172   std::multimap<int64_t, ir::OperationIndex, std::greater<int64_t>> _rank_to_op;
 173   std::shared_ptr<ir::OperationIndexMap<int64_t>> _op_to_rank;
 174   std::unique_ptr<compiler::BackendResolver> _backend_resolver;
 175   std::unique_ptr<exec::ExecTime> _exec_time;
 176   const ir::Graph *_graph{nullptr};
 177   std::vector<const backend::Backend *> _all_backends;
 178   const backend::Backend *_cpu_backend{nullptr}; // TODO Change this to _builtin_backend
 179   bool _is_profiling_mode;
 180   bool _is_linear_exec;
 181   bool _is_parallel_exec;
 182 };
 183
 184 } // namespace compiler
 185
 186 } // namespace onert
 187
 188 #endif // __ONERT_COMPILER_H_E_SCHEDULER_H_