Halide 22.0.0 Halide compiler and libraries

SearchSpace.h
Go to the documentation of this file.
1#ifndef SEARCH_SPACE_H
2#define SEARCH_SPACE_H
3
4#include "ASLog.h"
5#include "CostModel.h"
6#include "DefaultCostModel.h"
7#include "Featurization.h"
8#include "FunctionDAG.h"
9#include "LoopNest.h"
10#include "LoopNestParser.h"
11#include "PerfectHashMap.h"
12#include "SearchSpaceOptions.h"
13#include "State.h"
14#include <set>
15#include <unordered_map>
16#include <unordered_set>
17#include <vector>
18
19 namespace Halide {
20 namespace Internal {
21 namespace Autoscheduler {
22
23 struct SearchSpace {
24 using StateVector = std::vector<IntrusivePtr<State>>;
25 const FunctionDAG &dag;
26 const Anderson2021Params &params;
27 const Target &target;
28 SearchSpaceOptions search_space_options;
29 std::mt19937 &rng;
30 CostModel *cost_model;
31 Statistics &stats;
32 const LoopNestParser *partial_schedule;
33
34 NodeMap<bool> inlined_nodes;
35 NodeMap<std::vector<IntrusivePtr<const LoopNest>>> compute_root_nodes;
36 NodeMap<std::map<int, std::vector<IntrusivePtr<const LoopNest>>>> memoized_compute_root_blocks;
37
38 SearchSpace(const FunctionDAG &dag,
39 const Anderson2021Params &params,
40 const Target &target,
41 std::mt19937 &rng,
42 CostModel *cost_model,
43 Statistics &stats,
44 const LoopNestParser *partial_schedule);
45
46 // Sort / filter parallel tile options
47 struct ParallelTileOption {
48 vector<int64_t> outer_tiling;
49 vector<int64_t> inner_tiling;
50 double idle_core_wastage;
51 int64_t min_parallelism;
52 int64_t max_parallelism;
53 bool operator<(const ParallelTileOption &other) const {
54 return idle_core_wastage < other.idle_core_wastage;
55 }
56
57 // Ensure we don't accidentally copy this type
58 ParallelTileOption() = default;
59 ParallelTileOption(ParallelTileOption &&) = default;
60 ParallelTileOption &operator=(ParallelTileOption &&) = default;
61 ParallelTileOption(const ParallelTileOption &) = delete;
62 ParallelTileOption &operator=(const ParallelTileOption &) = delete;
63 };
64
65 vector<ParallelTileOption> filter_parallel_tile_options(const IntrusivePtr<State> &state,
66 const FunctionDAG::Node *node,
67 vector<vector<int64_t>> &inner_tilings,
68 const vector<int64_t> &pure_size) const;
69
70 vector<ThreadTileOption> filter_thread_tile_options(vector<IntrusivePtr<const LoopNest>> &loop_nests) const;
71
72 void memoize_blocks(const FunctionDAG::Node *node,
73 LoopNest *new_root);
74
75 bool add_states_from_memoized_blocks(const IntrusivePtr<State> &state,
76 std::function<void(IntrusivePtr<State> &&)> &accept_child,
77 const FunctionDAG::Node *node,
78 int &num_children) const;
79
80 // Generate successor states for given 'state'
81 void generate_children(const IntrusivePtr<State> &state,
82 std::function<void(IntrusivePtr<State> &&)> &accept_child,
83 int pass_idx,
84 bool is_pre_pass);
85
86 void freeze_lowest_cost_stages(const IntrusivePtr<State> &best);
87
88 vector<vector<int64_t>> generate_compute_root_serial_tilings(const IntrusivePtr<const LoopNest> &pure_stage,
89 const FunctionDAG::Node *node) const;
90
91 bool add_child(const IntrusivePtr<State> &state,
92 const IntrusivePtr<const LoopNest> &new_root,
93 std::function<void(IntrusivePtr<State> &&)> &accept_child) const;
94
95 void process_pending_states(std::unordered_map<uint64_t, StateVector> &primary_options,
96 std::unordered_map<uint64_t, StateVector> &secondary_options,
97 int &num_children,
98 std::function<void(IntrusivePtr<State> &&)> &accept_child,
99 const FunctionDAG::Node *node);
100
101 bool is_in_partial_schedule(const FunctionDAG::Node *node) const;
102};
103
104} // namespace Autoscheduler
105} // namespace Internal
106} // namespace Halide
107
108#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
PerfectHashMap
Definition: PerfectHashMap.h:38
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AbstractGenerator.h:19
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
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
Definition: SearchSpace.h:47
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
Definition: SearchSpace.h:23
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::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::StateVector
std::vector< IntrusivePtr< State > > StateVector
Definition: SearchSpace.h:24
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