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