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       : _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     for (auto &entry : backend_contexts)
  61     {
  62       _all_backends.push_back(entry.first);
  63     }
  64     _backend_resolver = std::make_unique<compiler::BackendResolver>();
  65     _exec_time = std::make_unique<exec::ExecTime>(_all_backends);
  66
  67     // Find cpu backend
  68     auto cpu_backend_it = std::find_if(
  69         _all_backends.begin(), _all_backends.end(),
  70         [](const backend::Backend *backend) { return backend->config()->id() == "cpu"; });
  71     if (cpu_backend_it == _all_backends.end())
  72       throw std::runtime_error("HEScheduler could be used only if 'cpu' backend is available");
  73     _cpu_backend = *cpu_backend_it;
  74   }
  75
  76 public:
  77   /**
  78    * @brief   Task scheduling
  79    *
  80    * @note    The main idea is taken from HSIP algo:
  81    *          https://www.hindawi.com/journals/sp/2016/3676149/
  82    */
  83   std::unique_ptr<compiler::BackendResolver> schedule(const ir::Graph &graph) final;
  84   std::shared_ptr<ir::OperationIndexMap<int64_t>> getIndexedRanks() { return _op_to_rank; }
  85
  86 private:
  87   bool isNodeProfiled(const ir::Operation &);
  88
  89   bool schedule(const ir::OperationIndex &, const backend::Backend *parent_backend);
  90   /**
  91    * @brief   Get earliest starting time and execution time of an operation on a backend.
  92    *
  93    * @note  Returns a time when operation's inputs are ready and backend is available
  94    *        It also returns exec time. If this is "cpu" backend, then exec_time*CPU_DELAY
  95    *
  96    * @param[in] backend: backend, for which to return the time
  97    * @param[in] index: index of an operation
  98    * @param[out] transfer_st_exec_time: est and exec time of data transfer operation
  99    *
 100    * @return earliest starting time and execution time
 101    */
 102   std::pair<int64_t, int64_t>
 103   ESTAndExecTime(const backend::Backend *backend, const ir::OperationIndex &index,
 104                  std::multimap<int64_t, int64_t> &transfer_st_exec_time);
 105   /**
 106    * @brief   Returns the latest finishing time of parents of a node.
 107    *
 108    * @param[in] backend: backend, for which to return the time
 109    * @param[in] node: node to get eft of parents
 110    * @param[out] transfer_st_exec_time: est and exec time of data transfer operation
 111    *
 112    * @return earliest finishing time of parent nodes
 113    */
 114   int64_t predMaxEFT(const backend::Backend *backend, const ir::Operation &node,
 115                      std::multimap<int64_t, int64_t> &transfer_st_exec_time);
 116
 117   void makeRank();
 118
 119   int64_t DFSMaxRank(const ir::OperationIndex &index);
 120
 121   int64_t DFSChildrenMaxRank(const ir::OperationIndex &index);
 122   /**
 123    * @brief   Returns the time, when backend is available for at least given amount of time.
 124    *
 125    * @note  Returns either hole/gap between two performing two already scheduled operations,
 126    *        or the finishing time of the last scheduled operation
 127    *
 128    * @param[in] backend backend, for which to return the time
 129    * @param[in] starting_time time, starting which to look for gap
 130    * @param[in] time_amount amount of the time, for which to look gap
 131    *
 132    * @return time, when backend has at least time_amount free time
 133    */
 134   int64_t backendAvailableTime(const backend::Backend *backend, const int64_t &starting_time,
 135                                const int64_t &time_amount);
 136
 137   int64_t getOpTime(const backend::Backend *backend, const std::string &operation, bool quant,
 138                     uint32_t size);
 139
 140   int64_t getPermuteTime(const backend::Backend *src_backend, const backend::Backend *dst_backend,
 141                          bool quant, uint32_t size);
 142
 143   void scheduleShufflingBackends();
 144
 145   int64_t tryBackend(const ir::Operation &node, const backend::Backend *backend);
 146
 147   /**
 148    * @brief   Schedule a node and its successor until:
 149    *            1. there is no branching or connection of multiple branches
 150    *            2. for subsequent nodes: other than predecessor's backend is prefered
 151    *
 152    * @param[in] index: index of an operation
 153    * @param[in] scheduled: a map to check if this node has already been scheduled
 154    *
 155    * @return N/A
 156    */
 157   void scheduleBranch(const ir::OperationIndex &index, ir::OperationIndexMap<bool> &scheduled);
 158
 159 private:
 160   // This variable stores backend/node pairs with unknown execution time, and hints scheduler
 161   // whether it should assign these backends to these nodes:
 162   // * It stores false for unsupported nodes
 163   // * During rank calculation with enabled profiling mode it stores true for supported nodes
 164   std::unordered_map<const backend::Backend *, std::unordered_map<std::string, bool>> _is_supported;
 165   // Finishing and starting time of each backend
 166   std::unordered_map<const backend::Backend *, std::map<int64_t, int64_t>> _backends_avail_time;
 167   ir::OperationIndexMap<int64_t> _ops_eft;
 168   std::multimap<int64_t, ir::OperationIndex, std::greater<int64_t>> _rank_to_op;
 169   std::shared_ptr<ir::OperationIndexMap<int64_t>> _op_to_rank;
 170   std::unique_ptr<compiler::BackendResolver> _backend_resolver;
 171   std::unique_ptr<exec::ExecTime> _exec_time;
 172   const ir::Graph *_graph{nullptr};
 173   std::vector<const backend::Backend *> _all_backends;
 174   const backend::Backend *_cpu_backend{nullptr}; // TODO Change this to controlflow_backend
 175   bool _is_profiling_mode;
 176   bool _is_linear_exec;
 177   bool _is_parallel_exec;
 178 };
 179
 180 } // namespace compiler
 181
 182 } // namespace onert
 183
 184 #endif // __ONERT_COMPILER_H_E_SCHEDULER_H_