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