algo_chooser.cpp 33.3 KB
Newer Older
1 2 3 4
/**
 * \file src/opr/impl/search_policy/algo_chooser.cpp
 * MegEngine is Licensed under the Apache License, Version 2.0 (the "License")
 *
5
 * Copyright (c) 2014-2021 Megvii Inc. All rights reserved.
6 7 8 9 10 11 12 13
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT ARRANTIES OR CONDITIONS OF ANY KIND, either express or
 * implied.
 */

#include "megbrain/opr/search_policy/algo_chooser.h"
14
#include <limits>
15 16
#include <unordered_set>
#include "megbrain/opr/dnn/convolution.h"
17
#include "megbrain/opr/internal/megdnn_opr_wrapper.h"
18
#include "megbrain/opr/search_policy/algo_chooser_helper.h"
19 20 21 22 23 24 25 26
#include "megbrain/opr/search_policy/profiler.h"

#include "../internal/invoke.h"
#include "../internal/megdnn_opr_wrapper.inl"
#include "./workspace_need_limit_getter.inl"

//! TODO: here has to be know some megdnn::opr when there is produced midout.h
//! fix it if there is another graceful way.
27
#include "megdnn/opr_param_defs.h"
28
#include "megdnn/oprs.h"
29
#include "megdnn/oprs/base.h"
30 31 32 33 34 35 36 37
#include "midout.h"
MIDOUT_DECL(megbrain_opr_algo_chooser)
#define MIDOUT_B(...) MIDOUT_BEGIN(megbrain_opr_algo_chooser, __VA_ARGS__) {
#define MIDOUT_E \
    }            \
    MIDOUT_END();

using mgb::opr::intl::WorkspaceLimitGetter;
38 39
using namespace megdnn;
using namespace mgb;
40 41 42 43 44 45 46 47

#define APPLY(statement, ...)                                  \
    mgb::apply([&](const auto&... args) { return statement; }, \
               std::tuple_cat(__VA_ARGS__))

// timeout delta to be added with fastest known algorithm for new algos
constexpr double TIMEOUT_TOLERANCE = 2;

48
#define CACHE_KEY_VERSION "v4"
49 50 51 52 53 54 55 56 57 58

namespace {
template <typename Opr>
std::string profile_name(Opr* opr) {
    std::string ret =
            std::string(MegDNNOpr2MGBOpr<Opr>::MGBOpr::typeinfo()->name) +
            CACHE_KEY_VERSION;
    ret.append(opr->get_algorithm_set_name());
    return ret;
}
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

template <typename Opr>
std::string format_fixlayouts(
        const typename opr::AlgoChooser<Opr>::FixedTensorLayouts& layouts,
        size_t arity_in, size_t arity_out) {
    std::string ret;
    ret.append(": tensor layouts(");
    for (size_t i = 0; i < arity_in; ++i) {
        if (i) {
            ret.append(", ");
        }
        ret.append(layouts[i].to_string() + " ");
        ret.append(layouts[i].dtype.name());
    }
    ret.append(") -> (");
    for (size_t i = 0; i < arity_out; ++i) {
        if (i) {
            ret.append(", ");
        }
        ret.append(layouts[i + arity_in].to_string() + " ");
        ret.append(layouts[i + arity_in].dtype.name());
    }
    return ret;
}

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
/**
 * \brief Check if the sub opr list has circular dependence.
 */
class CircularDepsChecker {
    struct SearchItemStorage {
        std::string data_hold;
        size_t hash = 0;

        SearchItemStorage(const Algorithm::SearchItem& item) {
            Algorithm::serialize_write_pod(item.opr_type, data_hold);
            for (auto&& layout : item.layouts) {
                data_hold += layout.serialize();
            }
            data_hold += item.param;
        }

        SearchItemStorage& init_hash() {
            hash = XXHash64CT::hash(data_hold.data(), data_hold.size(),
                                    20201225);
            return *this;
        }

        bool operator==(const SearchItemStorage& rhs) const {
            return data_hold == rhs.data_hold;
        }

        struct Hash {
            size_t operator()(const SearchItemStorage& s) const {
                return s.hash;
            }
        };
    };
    std::unordered_set<SearchItemStorage, SearchItemStorage::Hash> m_set;

public:
    void put(const megdnn::Algorithm::SearchItem& key) {
        SearchItemStorage key_storage(key);
        key_storage.init_hash();
        mgb_assert(m_set.find(key_storage) == m_set.end(),
                   "Circular dependency during flatten search space");
        auto ret = m_set.insert(std::move(key_storage));
        mgb_assert(ret.second);
    }
    void remove(const megdnn::Algorithm::SearchItem& key) {
        SearchItemStorage key_storage(key);
        key_storage.init_hash();
        auto&& iter = m_set.find(key_storage);
        mgb_assert(iter != m_set.end());
        m_set.erase(iter);
    }
};

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 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
///////////////// OprTypeTrait /////////////////////////////
template <megdnn::Algorithm::OprType>
struct OprFromOprTypeTrait;

template <typename Opr>
struct OprTypeFromOprTrait;

#define cb(_opr_type, _opr)                                             \
    template <>                                                         \
    struct OprFromOprTypeTrait<megdnn::Algorithm::OprType::_opr_type> { \
        using Opr = megdnn::_opr;                                       \
    };                                                                  \
    template <>                                                         \
    struct OprTypeFromOprTrait<megdnn::_opr> {                          \
        constexpr static megdnn::Algorithm::OprType opr_type =          \
                megdnn::Algorithm::OprType::_opr_type;                  \
    }

cb(MATRIX_MUL_FORWARD, MatrixMulForward);
cb(BATCHED_MATRIX_MUL_FORWARD, BatchedMatrixMulForward);
cb(CONVOLUTION_FORWARD, ConvolutionForward);
cb(CONVOLUTION_BACKWARD_DATA, ConvolutionBackwardData);
cb(CONVOLUTION_BACKWARD_FILTER, ConvolutionBackwardFilter);
cb(CONVOLUTION3D_FORWARD, Convolution3DForward);
cb(CONVOLUTION3D_BACKWARD_DATA, Convolution3DBackwardData);
cb(CONVOLUTION3D_BACKWARD_FILTER, Convolution3DBackwardFilter);
cb(LOCAL_SHARE_FORWARD, LocalShareForward);
cb(LOCAL_SHARE_BACKWARD_DATA, LocalShareBackwardData);
cb(LOCAL_SHARE_BACKWARD_FILTER, LocalShareBackwardFilter);
cb(DEFORMABLE_CONV_FORWARD, DeformableConvForward);
cb(DEFORMABLE_CONV_BACKWARD_DATA, DeformableConvBackwardData);
cb(DEFORMABLE_CONV_BACKWARD_FILTER, DeformableConvBackwardFilter);
cb(BATCH_CONV_FORWARD, BatchConvBiasForward);
cb(CONVBIAS_FORWARD, ConvBiasForward);

#undef cb

// clang-format off
#define FOREACH_OPR_TYPE_WITH_STMT(cb, stmt)  \
    cb(MATRIX_MUL_FORWARD, stmt)              \
    cb(BATCHED_MATRIX_MUL_FORWARD, stmt)      \
    cb(CONVOLUTION_FORWARD, stmt)             \
    cb(CONVOLUTION_BACKWARD_DATA, stmt)       \
    cb(CONVOLUTION_BACKWARD_FILTER, stmt)     \
    cb(CONVOLUTION3D_FORWARD, stmt)           \
    cb(CONVOLUTION3D_BACKWARD_DATA, stmt)     \
    cb(CONVOLUTION3D_BACKWARD_FILTER, stmt)   \
    cb(LOCAL_SHARE_FORWARD, stmt)             \
    cb(LOCAL_SHARE_BACKWARD_DATA, stmt)       \
    cb(LOCAL_SHARE_BACKWARD_FILTER, stmt)     \
    cb(DEFORMABLE_CONV_FORWARD, stmt)         \
    cb(DEFORMABLE_CONV_BACKWARD_DATA, stmt)   \
    cb(DEFORMABLE_CONV_BACKWARD_FILTER, stmt) \
    cb(BATCH_CONV_FORWARD, stmt)              \
    cb(CONVBIAS_FORWARD, stmt)
// clang-format on

#define _OPR_TYPE_CASE(_opr_type, _stmt)             \
    case Algorithm::OprType::_opr_type: {            \
        using _Opr = typename OprFromOprTypeTrait<   \
                Algorithm::OprType::_opr_type>::Opr; \
        _stmt;                                       \
        break;                                       \
    }

#define FOREACH_OPR_TYPE_DISPATCH(_search_items, _stmt)          \
    for (size_t _item_idx = 0; _item_idx < _search_items.size(); \
         _item_idx++) {                                          \
        auto&& _item = _search_items[_item_idx];                 \
        switch (_item.opr_type) {                                \
            FOREACH_OPR_TYPE_WITH_STMT(_OPR_TYPE_CASE, _stmt)    \
            default:                                             \
                mgb_throw(MegBrainError, "unknown opr_type");    \
        }                                                        \
    }

template <typename Opr>
TensorLayoutArray to_layout_array(
        const typename opr::AlgoChooser<Opr>::FixedTensorLayouts& layouts) {
    TensorLayoutArray ret;
    for (auto&& layout : layouts) {
        ret.push_back(layout);
    }
    return ret;
220 221
}

222 223 224 225 226 227 228 229 230 231 232 233
template <typename Opr>
typename opr::AlgoChooser<Opr>::FixedTensorLayouts to_fixed_layouts(
        const TensorLayoutArray& layouts) {
    typename opr::AlgoChooser<Opr>::FixedTensorLayouts ret;
    mgb_assert(ret.size() == layouts.size());
    size_t idx = 0;
    for (auto&& layout : layouts) {
        ret[idx++] = layout;
    }
    return ret;
}

234 235 236 237 238 239 240 241 242 243 244 245
/**
 * flatten search space in postorder traversal
 * The subopr search construct a search tree
 *
 *           A
 *        /    \
 *       B1B2   C
 *      /     \
 *     D1D2D3   E
 * We use postorder traverse the search tree.
 * D1 -> D2 -> D3 -> E -> B1 -> B2 -> C -> A
 */
246
template <typename Opr>
247 248 249 250 251 252 253
std::vector<megdnn::Algorithm::SearchItem> flatten_search_space(
        const typename opr::AlgoChooser<Opr>::ExeContext& ctx,
        CircularDepsChecker& checker) {
    auto&& search_item = megdnn::Algorithm::SearchItem{
            OprTypeFromOprTrait<Opr>::opr_type, ctx.param(),
            to_layout_array<Opr>(ctx.layouts())};
    checker.put(search_item);
254 255 256 257 258 259 260 261 262
    std::vector<megdnn::Algorithm::SearchItem> ret;
    for (auto algo_info : ctx.get_all_candidates()) {
        megdnn::Algorithm* algo = ctx.get_algorithm_from_desc(algo_info.desc);
        mgb_assert(algo, "Unknown algo description");
        std::vector<megdnn::Algorithm::SearchItem>&& sub_items =
                algo->get_subopr_list(to_layout_array<Opr>(ctx.layouts()),
                                      ctx.megdnn_opr());

        FOREACH_OPR_TYPE_DISPATCH(sub_items, {
263 264
            auto&& megdnn_opr =
                    opr::intl::create_megdnn_opr<_Opr>(ctx.comp_node());
265 266 267
            megdnn_opr->param() =
                    Algorithm::deserialize_read_pod<typename _Opr::Param>(
                            _item.param);
268
            typename opr::AlgoChooser<_Opr>::ExeContext sub_ctx(
269 270 271
                    to_fixed_layouts<_Opr>(_item.layouts), megdnn_opr.get(),
                    _item.param, ctx.mgb_opr(), ctx.comp_node(),
                    ctx.execution_policy(), ctx.allow_weight_preprocess());
272
            auto space = flatten_search_space<_Opr>(sub_ctx, checker);
273 274
            ret.insert(ret.end(), space.begin(), space.end());
        });
275
    }
276 277
    ret.push_back(search_item);
    checker.remove(search_item);
278 279
    return ret;
}
280

281 282 283 284 285
//! Test whether the algo attribute of a algo match the require
//! algo_strategy
static bool algo_attribute_match_strategy(AlgoAttribute attribute,
                                          ExecutionStrategy selected_strategy) {
    bool ret = true;
M
Megvii Engine Team 已提交
286
    if (selected_strategy & ExecutionStrategy::OPTIMIZED) {
287 288 289 290 291 292 293
        ret &= (!static_cast<bool>(AlgoAttribute::NAIVE & attribute));
    } else if (selected_strategy & ExecutionStrategy::REPRODUCIBLE) {
        ret &= static_cast<bool>(AlgoAttribute::REPRODUCIBLE & attribute);
    }
    return ret;
}

294 295 296 297 298
}  // namespace

namespace mgb {
namespace opr {

299
template <typename Opr>
300
void AlgoChooser<Opr>::profile(ExeContext& ctx,
301 302
                               ExecutionStrategy selected_strategy) {
    if (ctx.get_profile_result_from_cache(selected_strategy).valid())
303
        return;
304 305 306 307 308 309
    AlgoChooserProfileCache::Result prof_rst;

    std::string str_on_inp_shape = ssprintf(
            "on input layouts (%s, %s)", ctx.layouts()[0].to_string().c_str(),
            ctx.layouts()[1].to_string().c_str());
    double cur_timeout = 0;
310 311 312 313

    auto workspace_limit = WorkspaceLimitGetter::get_workspace_limit(
            ctx.owner_graph(), ctx.comp_node(),
            ctx.execution_policy().workspace_limit);
314
    RealTimer timer;
315
    for (auto algo : ctx.get_all_candidates()) {
316 317 318
        Maybe<AlgoChooserProfileCache::ResultEntry> cur_rst;
        std::string msg = ssprintf("profiling %s algorithm %s %s",
                                   ctx.mgb_opr()->dyn_typeinfo()->name,
319
                                   algo.name.c_str(), str_on_inp_shape.c_str());
320 321
        ImplExecutionPolicy policy;
        policy.algo = algo.desc;
322 323
        ctx.construct_execution_policy(selected_strategy, policy);
        if (ctx.get_workspace_size_bytes(policy) >= workspace_limit) {
324
            continue;
325 326 327 328 329 330 331 332 333 334
        }
        auto algo_attribute = ctx.megdnn_opr()
                                      ->get_algorithm_from_desc(policy.algo)
                                      ->attribute();
        if (!algo_attribute_match_strategy(algo_attribute, selected_strategy)) {
            mgb_log_debug(
                    "skip algo %s, which is not match the profile strategy.",
                    algo.name.c_str());
            continue;
        }
335

336
        timer.reset();
337
        MGB_TRY { cur_rst = ctx.profile_single_algo(policy, cur_timeout); }
338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362
        MGB_CATCH(std::exception & exc, {
            mgb_log_warn("caught exception during %s: %s", msg.c_str(),
                         exc.what());
            continue;
        })
        MGB_CATCH(..., {
            mgb_log_warn("caught exception during %s", msg.c_str());
            continue;
        })
        if (!cur_rst.valid()) {
            mgb_log_warn("timeout when %s; timeout setting: %.3fsec",
                         msg.c_str(), cur_timeout);
            continue;
        }
        if (!cur_timeout) {
            cur_timeout = timer.get_secs() + TIMEOUT_TOLERANCE;
        } else {
            cur_timeout =
                    std::min(cur_timeout, timer.get_secs() + TIMEOUT_TOLERANCE);
        }
        auto&& rst = cur_rst.val();
        mgb_log_debug("%s: workspace: %zu; time: %.3gsec", msg.c_str(),
                      rst.workspace, rst.time);
        prof_rst.push_back(rst);
    }
363 364 365 366
    std::string msg = ssprintf("no usable %s algorithm %s",
                                ctx.mgb_opr()->dyn_typeinfo()->name,
                                str_on_inp_shape.c_str());
    mgb_assert(!prof_rst.empty(), "%s", msg.c_str());
367

368 369 370 371 372 373 374 375
    FixedTensorLayouts origin_layouts = ctx.layouts();
    typename Opr::Param origin_param = ctx.megdnn_opr()->param();
    AlgoChooserProfileCache::Key cache_key{origin_layouts.data(),
                                           origin_layouts.size(), &origin_param,
                                           sizeof(origin_param)};

    AlgoChooserProfileCache cache(ctx.comp_node(),
                                  profile_name(ctx.megdnn_opr()).c_str());
376 377 378 379
    cache.put(cache_key, prof_rst);
}

template <typename Opr>
380
typename AlgoChooser<Opr>::ImplExecutionPolicy
381
AlgoChooser<Opr>::choose_by_profile(ExeContext& ctx,
382
                                    ExecutionStrategy selected_strategy,
383
                                    bool enable_update) {
384
    MIDOUT_B(Opr, midout_iv(MGB_HASH_STR("AlgoChooser::choose_by_profile")))
385 386 387 388
    if (ctx.owner_graph()->options().no_profiling_on_shape_change) {
        auto policy = ctx.megdnn_opr()->execution_policy();
        if (policy.algo.valid())
            return policy;
389 390
    }

391
    if (enable_update) {
392 393 394
        CircularDepsChecker circular_deps_checker;
        auto&& search_items =
                flatten_search_space<Opr>(ctx, circular_deps_checker);
395 396 397 398 399 400 401 402 403
        FOREACH_OPR_TYPE_DISPATCH(search_items, {
            auto&& megdnn_opr = intl::create_megdnn_opr<_Opr>(ctx.comp_node());
            megdnn_opr->param() =
                    Algorithm::deserialize_read_pod<typename _Opr::Param>(
                            _item.param);
            typename AlgoChooser<_Opr>::ExeContext sub_ctx(
                    to_fixed_layouts<_Opr>(_item.layouts), megdnn_opr.get(),
                    _item.param, ctx.mgb_opr(), ctx.comp_node(),
                    ctx.execution_policy(), ctx.allow_weight_preprocess());
404
            AlgoChooser<_Opr>::profile(sub_ctx, selected_strategy);
405
        });
406
    }
407
    typename AlgoChooser<Opr>::ImplExecutionPolicy policy;
408
    ctx.construct_execution_policy(selected_strategy, policy);
409
    return policy;
410 411 412 413
    MIDOUT_E
}

template <typename Opr>
414
size_t AlgoChooser<Opr>::setup_algo(const FixedTensorLayouts& layouts,
415 416 417 418 419 420
                                    Opr* megdnn_opr, const MGBOpr* mgb_opr,
                                    bool allow_weight_preprocess) {
    if (WorkspaceLimitGetter::is_prealloc_run(mgb_opr->owner_graph())) {
        return 0;
    }

421 422 423 424 425
    std::string param_str;
    Algorithm::serialize_write_pod(megdnn_opr->param(), param_str);
    ExeContext ctx(layouts, megdnn_opr, param_str, mgb_opr,
                   mgb_opr->comp_node(), mgb_opr->execution_policy(),
                   allow_weight_preprocess);
426

427
    ImplExecutionPolicy policy;
428
    if (auto algo_choose_hook = mgb_opr->algo_chooser()) {
429
        policy = algo_choose_hook(mgb_opr);
430 431 432
        ctx.construct_execution_policy((ExecutionStrategy::HEURISTIC |
                                        ExecutionStrategy::REPRODUCIBLE),
                                       policy, false);
433
    }
434 435
    if (!policy.algo.valid()) {
        policy = get_policy(ctx);
436
    }
437
    size_t workspace = ctx.get_workspace_size_bytes(policy);
M
Megvii Engine Team 已提交
438 439

    std::string ret;
440
    ret.append(mgb_opr->dyn_typeinfo()->name);
441 442 443 444
    ret += format_fixlayouts<Opr>(layouts, arity_in, arity_out);
    Algorithm* palgo = megdnn_opr->get_algorithm_from_desc(policy.algo);
    mgb_assert(palgo, "Unknown algo description");
    ret.append("): algo=" + std::string(palgo->name()));
445
    ret.append(ssprintf(" workspace=%.2fMiB attirbute=%d",
446
                        workspace / (1024 * 1024.0),
447
                        static_cast<uint32_t>(palgo->attribute())));
M
Megvii Engine Team 已提交
448 449
    mgb_log_debug("%s", ret.c_str());

450
    megdnn_opr->execution_policy() = policy;
451 452 453 454
    return workspace;
}

template <typename Opr>
455
typename AlgoChooser<Opr>::ImplExecutionPolicy AlgoChooser<Opr>::get_policy(
456 457
        ExeContext& ctx) {
    MGB_MARK_USED_VAR(TIMEOUT_TOLERANCE);
458 459 460 461 462 463 464 465
    auto opr_strategy = ctx.execution_policy().strategy;
    if ((opr_strategy & ExecutionStrategy::HEURISTIC) &&
               (opr_strategy & ExecutionStrategy::PROFILE)) {
        ImplExecutionPolicy policy =
                choose_by_profile(ctx, opr_strategy, false);
        if (!policy.algo.valid())
            policy = ctx.choose_by_heuristic(opr_strategy);
        return policy;
466 467
    } else if (!static_cast<int>(opr_strategy) ||
               (opr_strategy & ExecutionStrategy::HEURISTIC)) {
468 469
        return ctx.choose_by_heuristic(opr_strategy);
    }
470
#if MGB_ENABLE_FASTRUN
471 472 473
    else if (opr_strategy & ExecutionStrategy::PROFILE) {
        return choose_by_profile(ctx, opr_strategy);
    }
474
#endif
475
    else {
476
        mgb_throw(GraphError, "bad ExecutionPolicy strategy");
477 478 479
    }
}

480 481 482 483 484 485 486 487 488 489 490
#define INST(Opr)                                                       \
    template AlgoChooser<megdnn::Opr>::ImplExecutionPolicy              \
    AlgoChooser<megdnn::Opr>::get_policy(ExeContext& ctx);              \
    template void AlgoChooser<megdnn::Opr>::profile(ExeContext& ctx,    \
                                                    ExecutionStrategy); \
    template AlgoChooser<megdnn::Opr>::ImplExecutionPolicy              \
    AlgoChooser<megdnn::Opr>::choose_by_profile(                        \
            ExeContext& ctx, ExecutionStrategy, bool enable_update);    \
    template size_t AlgoChooser<megdnn::Opr>::setup_algo(               \
            const FixedTensorLayouts& layouts, megdnn::Opr* megdnn_opr, \
            const MGBOpr* mgb_opr, bool allow_weight_preprocess);
491 492 493 494 495 496

MGB_FOREACH_FASTRUN_OPR(INST)

#undef INST

//////////////////////////////// ExeContext /////////////////////////////
497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517
template <typename Opr>
AlgoChooser<Opr>::ExeContext::ExeContext(
        const FixedTensorLayouts& layouts, Opr* megdnn_opr,
        const std::string& param_str, const cg::OperatorNodeBase* mgb_opr,
        const CompNode& cn,
        const megdnn::param::ExecutionPolicy& execution_policy,
        bool allow_weight_preprocess)
        : m_layouts{layouts},
          m_megdnn_opr{megdnn_opr},
          m_param{param_str},
          m_base_mgb_opr{mgb_opr},
          m_cn{cn},
          m_execution_policy{execution_policy},
          m_allow_weight_preprocess{allow_weight_preprocess} {
    mgb_assert(m_layouts.size() == layouts.size());
    static_assert(std::tuple_size<FixedTensorLayouts>::value == 3 ||
                          std::tuple_size<FixedTensorLayouts>::value == 5 ||
                          std::tuple_size<FixedTensorLayouts>::value == 8,
                  "Convolution AlgoChooser assumes arity = 3 , 5 or 8 (for "
                  "deformable conv)");
}
518 519 520

template <typename Opr>
typename AlgoChooser<Opr>::ImplAlgo
521
AlgoChooser<Opr>::ExeContext::get_profile_result_from_cache(
522
        ExecutionStrategy selected_strategy) const {
523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545
    MIDOUT_B(Opr,
             midout_iv(MGB_HASH_STR(
                     "AlgoChooser::ExeContext::get_profile_result_from_cache")))
    AlgoChooserProfileCache cache(m_cn,
                                  profile_name(m_megdnn_opr).c_str());

    typename Opr::Param origin_param = m_megdnn_opr->param();
    AlgoChooserProfileCache::Key cache_key{m_layouts.data(), m_layouts.size(),
                                           &origin_param, sizeof(origin_param)};
    auto&& rst = cache.get(cache_key);
    if (!rst.valid())
        return {};

    auto&& prof = rst.val();
    std::unordered_map<std::string, ImplAlgo> algo_map;
    for (auto i : get_all_candidates()) {
        auto ins = algo_map.emplace(i.name.c_str(), i);
        mgb_assert(ins.second, "duplicated algo name: %s", i.name.c_str());
    }

    if (prof.empty())
        return {};
    for (auto&& i : prof) {
546
        if (!(selected_strategy & ExecutionStrategy::REPRODUCIBLE) ||
547 548
            static_cast<AlgoAttribute>(i.attribute) &
                    AlgoAttribute::REPRODUCIBLE) {
549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575
            auto iter = algo_map.find(i.algo);
            mgb_assert(iter != algo_map.end(),
                       "algorithm %s exists in "
                       "profiling result but not in algo_map; please "
                       "report this "
                       "bug; opr: %s{%s}, layouts: %s ",
                       i.algo.c_str(), m_base_mgb_opr->cname(),
                       m_base_mgb_opr->dyn_typeinfo()->name,
                       format_fixlayouts<Opr>(m_layouts, arity_in, arity_out)
                               .c_str());
            return iter->second;
        }
    }

    mgb_log_error(
            "Workspace requirement (%zu) could not be satisfied. Abort now "
            "to "
            "avoid further problems",
            WorkspaceLimitGetter::get_workspace_limit(
                    m_base_mgb_opr->owner_graph(), m_cn,
                    m_execution_policy.workspace_limit));
    mgb_trap();
    MIDOUT_E
}

template <typename Opr>
typename AlgoChooser<Opr>::ImplExecutionPolicy
576
AlgoChooser<Opr>::ExeContext::choose_by_heuristic(
577
        ExecutionStrategy selected_strategy) const {
578 579 580 581 582 583 584
    if (m_execution_policy.workspace_limit !=
        std::numeric_limits<decltype(
                m_execution_policy.workspace_limit)>::max()) {
        mgb_log_warn(
                "workspace_limit should not be setted if choose algo by "
                "heuristic");
    }
585
    bool reproducible = static_cast<bool>(selected_strategy &
586
                                          ExecutionStrategy::REPRODUCIBLE);
587
    auto workspace_limit = WorkspaceLimitGetter::get_workspace_limit(
588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607
            owner_graph(), m_cn, m_execution_policy.workspace_limit);
    ImplExecutionPolicy policy;
    policy.algo = APPLY(m_megdnn_opr->get_algorithm_info_heuristic(
                                args..., workspace_limit, reproducible),
                        m_layouts).desc;

    Algorithm* algo = m_megdnn_opr->get_algorithm_from_desc(policy.algo);
    mgb_assert(algo, "Unknown algo description");
    std::vector<Algorithm::SearchItem>&& sub_items = algo->get_subopr_list(
            to_layout_array<Opr>(m_layouts), m_megdnn_opr);

    FOREACH_OPR_TYPE_DISPATCH(sub_items, {
        auto&& megdnn_opr = intl::create_megdnn_opr<_Opr>(m_cn);
        megdnn_opr->param() =
                Algorithm::deserialize_read_pod<typename _Opr::Param>(
                        _item.param);
        typename AlgoChooser<_Opr>::ExeContext sub_ctx(
                to_fixed_layouts<_Opr>(_item.layouts), megdnn_opr.get(),
                _item.param, m_base_mgb_opr, m_cn, m_execution_policy,
                m_allow_weight_preprocess);
608
        policy.sub_policy.push_back(
609
                sub_ctx.choose_by_heuristic(selected_strategy));
610 611 612
    });

    return policy;
613 614 615 616 617
}

template <typename Opr>
std::vector<typename AlgoChooser<Opr>::ImplAlgo>
AlgoChooser<Opr>::ExeContext::get_all_candidates() const {
618 619
    auto heu = choose_by_heuristic(ExecutionStrategy::HEURISTIC);
    auto&& ret = APPLY(m_megdnn_opr->get_all_algorithms_info(args...), m_layouts);
620 621
    bool found = false;
    for (size_t i = 0; i < ret.size(); ++i) {
622
        if (ret[i].desc == heu.algo) {
623 624 625 626 627
            found = true;
            std::swap(ret[i], ret[0]);
            break;
        }
    }
628 629 630

    Algorithm* palgo = m_megdnn_opr->get_algorithm_from_desc(heu.algo);
    mgb_assert(palgo, "Unknown algo description");
631 632
    mgb_assert(found,
               "algo %s got by heuristic not found in "
633
               "candidate list",
634
               palgo->name());
635 636 637 638
    return std::move(ret);
}

template <typename Opr>
639
void AlgoChooser<Opr>::ExeContext::construct_execution_policy(
640
        ExecutionStrategy selected_strategy,
641 642
        typename AlgoChooser<Opr>::ImplExecutionPolicy& policy,
        bool retrive_from_cache) const {
643
    bool reproducible = static_cast<bool>(selected_strategy &
644
                                          ExecutionStrategy::REPRODUCIBLE);
645
    if (!policy.algo.valid()) {
646 647
        if (retrive_from_cache) {
            policy.algo =
648
                    get_profile_result_from_cache(selected_strategy).desc;
649 650 651 652 653
        } else {
            auto workspace_limit = WorkspaceLimitGetter::get_workspace_limit(
                    owner_graph(), m_cn, m_execution_policy.workspace_limit);
            policy.algo = APPLY(m_megdnn_opr->get_algorithm_info_heuristic(
                                        args..., workspace_limit,
654
                                        reproducible),
655 656 657
                                m_layouts)
                                  .desc;
        }
658
        mgb_assert(policy.algo.valid(),
659 660
                   "No algo found from cache or heuristic, maybe some error "
                   "occured");
661
    }
662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677

    Algorithm* algo = m_megdnn_opr->get_algorithm_from_desc(policy.algo);
    mgb_assert(algo, "Unknown algo description");
    std::vector<Algorithm::SearchItem>&& sub_items = algo->get_subopr_list(
            to_layout_array<Opr>(m_layouts), m_megdnn_opr);

    FOREACH_OPR_TYPE_DISPATCH(sub_items, {
        auto&& megdnn_opr = intl::create_megdnn_opr<_Opr>(m_cn);
        megdnn_opr->param() =
                Algorithm::deserialize_read_pod<typename _Opr::Param>(
                        _item.param);
        typename AlgoChooser<_Opr>::ExeContext sub_ctx(
                to_fixed_layouts<_Opr>(_item.layouts), megdnn_opr.get(),
                _item.param, m_base_mgb_opr, m_cn, m_execution_policy,
                m_allow_weight_preprocess);
        policy.sub_policy.push_back({});
678
        sub_ctx.construct_execution_policy(selected_strategy,
679 680
                                           policy.sub_policy.back(),
                                           retrive_from_cache);
681 682 683
    });

    return;
684 685 686 687
}

template <typename Opr>
size_t AlgoChooser<Opr>::ExeContext::get_workspace_size_bytes(
688 689
        const ImplExecutionPolicy& policy) const {
    m_megdnn_opr->execution_policy() = policy;
690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712
    size_t result;
    if_constexpr<opr_supports_preprocess<Opr>()>(
            [&](auto _) {
                auto&& opr = _(m_megdnn_opr);
                auto prep = this->construct_fake_preprocess_filter();
                PreprocessFilter<Opr>* prep_ptr =
                        prep.valid() ? &prep.val() : nullptr;
                result = std::max(
                        APPLY(opr->get_preprocess_workspace_in_bytes(args...),
                              m_layouts),
                        APPLY(opr->get_workspace_in_bytes(args..., prep_ptr),
                              m_layouts));
            },
            /* else */
            [&](auto _) {
                result = APPLY(_(m_megdnn_opr)->get_workspace_in_bytes(args...),
                               m_layouts);
            });
    return result;
}

template <typename Opr>
Maybe<AlgoChooserProfileCache::ResultEntry>
713 714
AlgoChooser<Opr>::ExeContext::profile_single_algo(
        const ImplExecutionPolicy& policy, double& timeout) const {
715 716
    typename TimedProfiler<Opr>::Param param;
    // force check copy size <= dest len-1 from gcc8 for safe
717 718 719
    param.execution_policy =
            TimedProfiler<Opr>::Param::ExecutionPolicyBlob::serialize(policy);
    param.workspace = get_workspace_size_bytes(policy);
720 721 722 723 724 725 726 727 728 729
    for (int i = 0; i < arity; ++i) {
        auto&& src = m_layouts[i];
        mgb_assert(src.format.is_default() &&
                           (src.dtype.category() == DTypeCategory::FLOAT ||
                            src.dtype.category() == DTypeCategory::INT ||
                            src.dtype.category() == DTypeCategory::QUANTIZED),
                   "unsupported layout in profiling: %s",
                   src.to_string().c_str());
        param.dtypes[i] = src.dtype.enumv();
    }
730
    param.comp_node_loc = m_cn.locator();
731 732 733 734 735 736
    mgb_assert(param.shapes.size() == m_layouts.size());
    for (size_t i = 0; i < param.shapes.size(); ++i)
        param.shapes[i] = m_layouts[i];
    param.opr_param = m_megdnn_opr->param();
    param.allow_weight_preprocess = m_allow_weight_preprocess;

737 738
    Algorithm* palgo = m_megdnn_opr->get_algorithm_from_desc(policy.algo);
    mgb_assert(palgo, "Unknown algo description");
739 740 741 742
    auto rst = TimedProfiler<Opr>::profile(param, timeout);
    // MIOpen conv profiles all available algos when a specfic shape is
    // provided for the first time, which probably adds to the result time.
    // Therefore, a second profile execution is needed.
743
    if (strncmp(palgo->name(), "MIOpen", 6) == 0)
744 745 746 747
        rst = TimedProfiler<Opr>::profile(param, timeout);
    if (!rst.valid())
        return None;
    return AlgoChooserProfileCache::ResultEntry{
748
            palgo->name(),
749
            static_cast<uint32_t>(palgo->attribute()),
750
            rst.val().time, param.workspace};
751 752 753 754 755 756 757 758 759 760
}

template <typename Opr>
Maybe<PreprocessFilter<Opr>>
AlgoChooser<Opr>::ExeContext::construct_fake_preprocess_filter() const {
    Maybe<PreprocessFilter<Opr>> result = None;
    if_constexpr<opr_supports_preprocess<Opr>()>([&](auto _) {
        if (!m_allow_weight_preprocess)
            return;
        auto opr = _(m_megdnn_opr);
761 762 763 764
        auto layouts = APPLY(opr->deduce_preprocessed_filter_layout(args...),
                             m_layouts);
        //! No preprocess layout means no need weight preprocess
        if (layouts.empty()) {
765
            return;
766 767 768 769 770 771 772 773 774 775 776 777
        }
        //! all layouts arm empty means no need weight preprocess
        bool layout_valid = false;
        for (auto&& layout : layouts) {
            if (!layout.is_empty()) {
                layout_valid = true;
            }
        }
        if (!layout_valid) {
            return;
        }

778 779 780
        result = PreprocessFilter<Opr>{};
        auto& res = result.val();
        res.algorithm_id = nullptr;
781 782 783
        res.tensors.resize(layouts.size());
        for (size_t i = 0; i < layouts.size(); i++) {
            res.tensors[i] = megdnn::TensorND(nullptr, layouts[i]);
784 785 786 787 788 789
        }
    });
    return result;
}

#define INST(Opr)                                                              \
790 791 792 793 794 795 796
    template AlgoChooser<megdnn::Opr>::ExeContext::ExeContext(                 \
            const FixedTensorLayouts& layouts, megdnn::Opr* megdnn_opr,        \
            const std::string& param_str, const cg::OperatorNodeBase* mgb_opr, \
            const CompNode& cn,                                                \
            const megdnn::param::ExecutionPolicy& execution_policy,            \
            bool allow_weight_preprocess);                                     \
    template typename AlgoChooser<megdnn::Opr>::ImplExecutionPolicy            \
797
    AlgoChooser<megdnn::Opr>::ExeContext::choose_by_heuristic(                 \
798
            ExecutionStrategy select_strategy) const;                          \
799 800
    template typename AlgoChooser<megdnn::Opr>::ImplAlgo                       \
    AlgoChooser<megdnn::Opr>::ExeContext::get_profile_result_from_cache(       \
801
            ExecutionStrategy select_strategy) const;                          \
802 803 804 805
    template std::vector<typename AlgoChooser<megdnn::Opr>::ImplAlgo>          \
    AlgoChooser<megdnn::Opr>::ExeContext::get_all_candidates() const;          \
    template size_t                                                            \
    AlgoChooser<megdnn::Opr>::ExeContext::get_workspace_size_bytes(            \
806 807
            const typename AlgoChooser<megdnn::Opr>::ImplExecutionPolicy&      \
                    policy) const;                                             \
808 809
    template void                                                              \
    AlgoChooser<megdnn::Opr>::ExeContext::construct_execution_policy(          \
810
            ExecutionStrategy select_strategy,                                 \
811 812
            typename AlgoChooser<megdnn::Opr>::ImplExecutionPolicy& policy,    \
            bool retrive_from_cache) const;                                    \
813 814
    template Maybe<AlgoChooserProfileCache::ResultEntry>                       \
    AlgoChooser<megdnn::Opr>::ExeContext::profile_single_algo(                 \
815 816 817
            const typename AlgoChooser<megdnn::Opr>::ImplExecutionPolicy&      \
                    policy,                                                    \
            double& timeout) const;
818 819 820 821 822 823 824 825

MGB_FOREACH_FASTRUN_OPR(INST)

#undef INST
}  // namespace opr
}  // namespace mgb

// vim: syntax=cpp.doxygen foldmethod=marker foldmarker=f{{{,f}}}