Loading...
Searching...
No Matches
SearchSpace.h
Go to the documentation of this file.
#ifndef SEARCH_SPACE_H
#define SEARCH_SPACE_H
#include "ASLog.h"
#include "CostModel.h"
#include "DefaultCostModel.h"
#include "Featurization.h"
#include "FunctionDAG.h"
#include "LoopNest.h"
#include "LoopNestParser.h"
#include "PerfectHashMap.h"
#include "SearchSpaceOptions.h"
#include "State.h"
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>
namespace Halide {
namespace Internal {
namespace Autoscheduler {
struct SearchSpace {
using StateVector = std::vector<IntrusivePtr<State>>;
const FunctionDAG &dag;
const Anderson2021Params &params;
const Target &target;
SearchSpaceOptions search_space_options;
std::mt19937 &rng;
CostModel *cost_model;
Statistics &stats;
const LoopNestParser *partial_schedule;
NodeMap<bool> inlined_nodes;
NodeMap<std::vector<IntrusivePtr<const LoopNest>>> compute_root_nodes;
NodeMap<std::map<int, std::vector<IntrusivePtr<const LoopNest>>>> memoized_compute_root_blocks;
SearchSpace(const FunctionDAG &dag,
const Anderson2021Params &params,
const Target &target,
std::mt19937 &rng,
CostModel *cost_model,
Statistics &stats,
const LoopNestParser *partial_schedule);
// Sort / filter parallel tile options
struct ParallelTileOption {
vector<int64_t> outer_tiling;
vector<int64_t> inner_tiling;
double idle_core_wastage;
int64_t min_parallelism;
int64_t max_parallelism;
bool operator<(const ParallelTileOption &other) const {
return idle_core_wastage < other.idle_core_wastage;
}
// Ensure we don't accidentally copy this type
ParallelTileOption() = default;
ParallelTileOption(ParallelTileOption &&) = default;
ParallelTileOption &operator=(ParallelTileOption &&) = default;
ParallelTileOption(const ParallelTileOption &) = delete;
ParallelTileOption &operator=(const ParallelTileOption &) = delete;
};
vector<ParallelTileOption> filter_parallel_tile_options(const IntrusivePtr<State> &state,
const FunctionDAG::Node *node,
vector<vector<int64_t>> &inner_tilings,
const vector<int64_t> &pure_size) const;
vector<ThreadTileOption> filter_thread_tile_options(vector<IntrusivePtr<const LoopNest>> &loop_nests) const;
void memoize_blocks(const FunctionDAG::Node *node,
LoopNest *new_root);
bool add_states_from_memoized_blocks(const IntrusivePtr<State> &state,
std::function<void(IntrusivePtr<State> &&)> &accept_child,
const FunctionDAG::Node *node,
int &num_children) const;
// Generate successor states for given 'state'
void generate_children(const IntrusivePtr<State> &state,
std::function<void(IntrusivePtr<State> &&)> &accept_child,
int pass_idx,
bool is_pre_pass);
void freeze_lowest_cost_stages(const IntrusivePtr<State> &best);
vector<vector<int64_t>> generate_compute_root_serial_tilings(const IntrusivePtr<const LoopNest> &pure_stage,
const FunctionDAG::Node *node) const;
bool add_child(const IntrusivePtr<State> &state,
const IntrusivePtr<const LoopNest> &new_root,
std::function<void(IntrusivePtr<State> &&)> &accept_child) const;
void process_pending_states(std::unordered_map<uint64_t, StateVector> &primary_options,
std::unordered_map<uint64_t, StateVector> &secondary_options,
int &num_children,
std::function<void(IntrusivePtr<State> &&)> &accept_child,
const FunctionDAG::Node *node);
bool is_in_partial_schedule(const FunctionDAG::Node *node) const;
};
} // namespace Autoscheduler
} // namespace Internal
} // namespace Halide
#endif // SEARCH_SPACE_H
ASLog.h
LoopNestParser.h
PerfectHashMap.h
SearchSpaceOptions.h
CostModel.h
DefaultCostModel.h
Featurization.h
FunctionDAG.h
LoopNest.h
State.h
Halide::CostModel
Definition CostModel.h:61
Halide::Internal::Autoscheduler::LoopNestParser
Definition LoopNestParser.h:17
Halide::Internal::Autoscheduler
Definition AutoSchedule.h:10
Halide::Internal::Autoscheduler::NodeMap
PerfectHashMap< FunctionDAG::Node, T > NodeMap
Definition LoopNest.h:21
Halide::Internal
Definition AbstractGenerator.h:24
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition AbstractGenerator.h:19
int64_t
signed __INT64_TYPE__ int64_t
Definition runtime_internal.h:22
Halide::Internal::Autoscheduler::Anderson2021Params
Definition CostModel.h:18
Halide::Internal::Autoscheduler::FunctionDAG::Node
Definition FunctionDAG.h:378
Halide::Internal::Autoscheduler::FunctionDAG
Definition FunctionDAG.h:367
Halide::Internal::Autoscheduler::LoopNest
Definition LoopNest.h:34
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::idle_core_wastage
double idle_core_wastage
Definition SearchSpace.h:50
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::operator<
bool operator<(const ParallelTileOption &other) const
Definition SearchSpace.h:53
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::operator=
ParallelTileOption & operator=(const ParallelTileOption &)=delete
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::operator=
ParallelTileOption & operator=(ParallelTileOption &&)=default
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::ParallelTileOption
ParallelTileOption(const ParallelTileOption &)=delete
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::outer_tiling
vector< int64_t > outer_tiling
Definition SearchSpace.h:48
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::ParallelTileOption
ParallelTileOption(ParallelTileOption &&)=default
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::max_parallelism
int64_t max_parallelism
Definition SearchSpace.h:52
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::inner_tiling
vector< int64_t > inner_tiling
Definition SearchSpace.h:49
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::ParallelTileOption
ParallelTileOption()=default
Halide::Internal::Autoscheduler::SearchSpace::ParallelTileOption::min_parallelism
int64_t min_parallelism
Definition SearchSpace.h:51
Halide::Internal::Autoscheduler::SearchSpace::add_states_from_memoized_blocks
bool add_states_from_memoized_blocks(const IntrusivePtr< State > &state, std::function< void(IntrusivePtr< State > &&)> &accept_child, const FunctionDAG::Node *node, int &num_children) const
Halide::Internal::Autoscheduler::SearchSpace::rng
std::mt19937 & rng
Definition SearchSpace.h:29
Halide::Internal::Autoscheduler::SearchSpace::StateVector
std::vector< IntrusivePtr< State > > StateVector
Definition SearchSpace.h:24
Halide::Internal::Autoscheduler::SearchSpace::memoize_blocks
void memoize_blocks(const FunctionDAG::Node *node, LoopNest *new_root)
Halide::Internal::Autoscheduler::SearchSpace::stats
Statistics & stats
Definition SearchSpace.h:31
Halide::Internal::Autoscheduler::SearchSpace::process_pending_states
void process_pending_states(std::unordered_map< uint64_t, StateVector > &primary_options, std::unordered_map< uint64_t, StateVector > &secondary_options, int &num_children, std::function< void(IntrusivePtr< State > &&)> &accept_child, const FunctionDAG::Node *node)
Halide::Internal::Autoscheduler::SearchSpace::filter_parallel_tile_options
vector< ParallelTileOption > filter_parallel_tile_options(const IntrusivePtr< State > &state, const FunctionDAG::Node *node, vector< vector< int64_t > > &inner_tilings, const vector< int64_t > &pure_size) const
Halide::Internal::Autoscheduler::SearchSpace::compute_root_nodes
NodeMap< std::vector< IntrusivePtr< const LoopNest > > > compute_root_nodes
Definition SearchSpace.h:35
Halide::Internal::Autoscheduler::SearchSpace::partial_schedule
const LoopNestParser * partial_schedule
Definition SearchSpace.h:32
Halide::Internal::Autoscheduler::SearchSpace::params
const Anderson2021Params & params
Definition SearchSpace.h:26
Halide::Internal::Autoscheduler::SearchSpace::filter_thread_tile_options
vector< ThreadTileOption > filter_thread_tile_options(vector< IntrusivePtr< const LoopNest > > &loop_nests) const
Halide::Internal::Autoscheduler::SearchSpace::add_child
bool add_child(const IntrusivePtr< State > &state, const IntrusivePtr< const LoopNest > &new_root, std::function< void(IntrusivePtr< State > &&)> &accept_child) const
Halide::Internal::Autoscheduler::SearchSpace::generate_compute_root_serial_tilings
vector< vector< int64_t > > generate_compute_root_serial_tilings(const IntrusivePtr< const LoopNest > &pure_stage, const FunctionDAG::Node *node) const
Halide::Internal::Autoscheduler::SearchSpace::is_in_partial_schedule
bool is_in_partial_schedule(const FunctionDAG::Node *node) const
Halide::Internal::Autoscheduler::SearchSpace::inlined_nodes
NodeMap< bool > inlined_nodes
Definition SearchSpace.h:34
Halide::Internal::Autoscheduler::SearchSpace::target
const Target & target
Definition SearchSpace.h:27
Halide::Internal::Autoscheduler::SearchSpace::freeze_lowest_cost_stages
void freeze_lowest_cost_stages(const IntrusivePtr< State > &best)
Halide::Internal::Autoscheduler::SearchSpace::memoized_compute_root_blocks
NodeMap< std::map< int, std::vector< IntrusivePtr< const LoopNest > > > > memoized_compute_root_blocks
Definition SearchSpace.h:36
Halide::Internal::Autoscheduler::SearchSpace::generate_children
void generate_children(const IntrusivePtr< State > &state, std::function< void(IntrusivePtr< State > &&)> &accept_child, int pass_idx, bool is_pre_pass)
Halide::Internal::Autoscheduler::SearchSpace::search_space_options
SearchSpaceOptions search_space_options
Definition SearchSpace.h:28
Halide::Internal::Autoscheduler::SearchSpace::dag
const FunctionDAG & dag
Definition SearchSpace.h:25
Halide::Internal::Autoscheduler::SearchSpace::SearchSpace
SearchSpace(const FunctionDAG &dag, const Anderson2021Params &params, const Target &target, std::mt19937 &rng, CostModel *cost_model, Statistics &stats, const LoopNestParser *partial_schedule)
Halide::Internal::Autoscheduler::SearchSpace::cost_model
CostModel * cost_model
Definition SearchSpace.h:30
Halide::Internal::Autoscheduler::SearchSpaceOptions
Definition SearchSpaceOptions.h:12
Halide::Internal::Autoscheduler::Statistics
Definition Statistics.h:65
Halide::Internal::IntrusivePtr
Intrusive shared pointers have a reference count (a RefCount object) stored in the class itself.
Definition IntrusivePtr.h:71
Halide::Target
A struct representing a target machine and os to generate code for.
Definition Target.h:19