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 "compiler/IScheduler.h"
  27 #include "compiler/BackendManager.h"
  28 #include "compiler/Compiler.h"
  29 #include "ir/Graph.h"
  30 #include "exec/ExecTime.h"
  31 #include "backend/Backend.h"
  32 #include <memory>
  33 #include "ir/OperationIndexMap.h"
  34 #include <map>
  35 #include <memory>
  36
  37 namespace onert
  38 {
  39
  40 namespace compiler
  41 {
  42 /**
  43  * @brief Class to schedule tasks
  44  */
  45 class HEScheduler : IScheduler
  46 {
  47 public:
  48   /**
  49    * @brief     Construct a new Heterogeneous Execution Scheduler object
  50    * @param[in] model Graph model
  51    * @param[in] backend_resolver backend resolver
  52    */
  53   HEScheduler(const backend::BackendContexts &backend_contexts, const CompilerOptions &options)
  54       : _backend_contexts{backend_contexts}, _is_supported{}, _backends_avail_time{}, _ops_eft{},
  55         _op_to_rank{std::make_shared<ir::OperationIndexMap<int64_t>>()},
  56         _is_profiling_mode{options.he_profiling_mode},
  57         _is_linear_exec{options.executor == "Linear"},
  58         _is_parallel_exec{options.executor == "Parallel"}
  59   {
  60     // Workaround to avoid unused-private-field warning
  61     // TODO use _backend_contexts and remove workaround
  62     (void)_backend_contexts;
  63
  64     for (auto &entry : backend_contexts)
  65     {
  66       _all_backends.push_back(entry.first);
  67     }
  68     _backend_resolver = std::make_unique<compiler::BackendResolver>();
  69     _exec_time = std::make_unique<exec::ExecTime>(_all_backends);
  70
  71     // Find cpu backend
  72     auto cpu_backend_it = std::find_if(
  73         _all_backends.begin(), _all_backends.end(),
  74         [](const backend::Backend *backend) { return backend->config()->id() == "cpu"; });
  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::Operation &);
  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::Operation &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::Operation &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   const backend::BackendContexts &_backend_contexts;
 169   std::unordered_map<const backend::Backend *, std::unordered_map<std::string, bool>> _is_supported;
 170   // Finishing and starting time of each backend
 171   std::unordered_map<const backend::Backend *, std::map<int64_t, int64_t>> _backends_avail_time;
 172   ir::OperationIndexMap<int64_t> _ops_eft;
 173   std::multimap<int64_t, ir::OperationIndex, std::greater<int64_t>> _rank_to_op;
 174   std::shared_ptr<ir::OperationIndexMap<int64_t>> _op_to_rank;
 175   std::unique_ptr<compiler::BackendResolver> _backend_resolver;
 176   std::unique_ptr<exec::ExecTime> _exec_time;
 177   const ir::Graph *_graph{nullptr};
 178   std::vector<const backend::Backend *>
 179       _all_backends; // TODO Remove this and use _backend_contexts instead
 180   const backend::Backend *_cpu_backend{nullptr}; // TODO Change this to controlflow_backend
 181   bool _is_profiling_mode;
 182   bool _is_linear_exec;
 183   bool _is_parallel_exec;
 184 };
 185
 186 } // namespace compiler
 187
 188 } // namespace onert
 189
 190 #endif // __ONERT_COMPILER_H_E_SCHEDULER_H_