Halide 22.0.0 Halide compiler and libraries

Cache.h
Go to the documentation of this file.
1#ifndef BLOCK_CACHE_H
2#define BLOCK_CACHE_H
3
4#include "ASLog.h"
5#include "CostModel.h"
6#include "Featurization.h"
7#include "FunctionDAG.h"
8#include "Halide.h"
9#include "LoopNest.h"
10#include "PerfectHashMap.h"
11
12namespace Halide {
13namespace Internal {
14namespace Autoscheduler {
15
16/*
17 The adams2019 autoscheduler has two caching implementations within its schedule search:
18
19 1) Block (or tile) caching: handled by this file and Cache.cpp. If block caching is enabled
20 the below data structure (Cache) is used to save the tilings that have been generated at prior
21 passes of beam search. This allows for faster children generation when tiling is a scheduling
22 option. As noted below, this cache is a mapping of the form: Node -> vector_dim -> vector<tiled LoopNest>.
23
24 2) Featurization caching: handled within a LoopNest. The featurization of a LoopNest is used at
25 multiple points in beam search (i.e. whenever the featurization of a child LoopNest is computed),
26 so it is useful to not repeatedly calculate featurizations. As noted in LoopNest.h, this mapping
27 is of the form: (structural hash of producers) -> (StageMap of schedule features). Note that not
28 all features can be safely cached (i.e. inlined features), so some must be recomputed (see
29 LoopNest::recompute_inlined_features).
30
31 Important changes that caching impacts, outside of this file and Cache.cpp:
32
33 - LoopNest::compute_features
34 If cache_features is enabled (i.e. disable_memoized_features==0) then this function caches
35 the featurizations of its children, and if called again, reuses those cached featurizations.
36 The features are saved in a LoopNest's member, std::map<> features_cache. Some features do not
37 persist, and the FeaturesIntermediates struct (see Featurization.h) is used to cache useful
38 values that aid in recomputing such features.
39
40 - LoopNest::compute_working_set_from_features
41 Used to re-compute the working_set from cached features.
42
43 - LoopNest::recompute_inlined_features
44 Recursively recomputes the features of all inlined Funcs based on the cached FeaturesIntermediates
45 struct.
46
47 - LoopNest::compute_hash_of_producers_stored_at_root
48 Computes a structural hash for use in feature caching in a LoopNest.
49
50 - LoopNest::collect_producers
51 Collects all producers for a LoopNest for use in calculating the structural hash in
52 LoopNest::compute_hash_of_producers_stored_at_root.
53
54 - LoopNest::collect_stages
55 Collects all stages referenced by a LoopNest for use in LoopNest::collect_producers.
56
57 - State::compute_featurization
58 Calculates and stores hash_of_producers_stored_at_root for each child if feature caching
59 is enabled.
60
61 - State::generate_children
62 If block caching is enabled, and tilings for this States have been cached in the Cache object,
63 then tilings are not generated again, and the cached tilings are used instead. See
64 Cache::add_memoized_blocks below (and in Cache.cpp).
65 Additionally, if a tiling has not been cached, and it is not pruned, then the tiling will be
66 cached using Cache::memoize_blocks (see below and in Cache.cpp).
67*/
68
69struct State;
70
71/*
72Object stores caching options for autoscheduling.
73cache_blocks: decides if tilings are cached for decisions related to parallelizing the loops of a Func.
74cache_features: decides if LoopNest::compute_features will cache / will use cached featurizations.
75*/
76 struct CachingOptions {
77 bool cache_blocks = false;
78 bool cache_features = false;
79
80 static CachingOptions MakeOptionsFromParams(const Adams2019Params &params) {
81 CachingOptions options;
82 options.cache_blocks = params.disable_memoized_blocks == 0;
83 options.cache_features = params.disable_memoized_features == 0;
84 return options;
85 }
86};
87
88// Node -> (vector_dim -> vector<tiled LoopNest>)
89 using BlockCache = NodeMap<std::map<int, std::vector<IntrusivePtr<const LoopNest>>>>;
90
91// Cache for memoizing possible tilings.
92// Tracks hit/miss statistics for both block caching
93// and for feature caching (self-contained by LoopNests).
94 struct Cache {
95 CachingOptions options;
96 BlockCache memoized_compute_root_blocks;
97
98 mutable size_t cache_hits = 0;
99 mutable size_t cache_misses = 0;
100
101 Cache() = delete;
102 Cache(const CachingOptions &_options, size_t nodes_size)
103 : options(_options) {
104 if (options.cache_blocks) {
105 memoized_compute_root_blocks.make_large(nodes_size);
106 }
107 }
108
109 ~Cache() = default;
110
111 // check if we generated tilings for the current func on a previous pass
112 // if so, add them and return true.
113 // otherwise, return false (also return false if memoization is turned off).
114 bool add_memoized_blocks(const State *state,
115 std::function<void(IntrusivePtr<State> &&)> &accept_child,
116 const FunctionDAG::Node *node,
117 int &num_children,
118 const FunctionDAG &dag,
119 const Adams2019Params &params,
120 CostModel *cost_model) const;
121
122 // Generate tilings for a specific vector dimension and memoize them.
123 void memoize_blocks(const FunctionDAG::Node *node, LoopNest *new_root);
124};
125
126} // namespace Autoscheduler
127} // namespace Internal
128} // namespace Halide
129
130#endif // BLOCK_CACHE_H
ASLog.h
PerfectHashMap.h
CostModel.h
Featurization.h
FunctionDAG.h
LoopNest.h
Halide::CostModel
Definition: CostModel.h:61
PerfectHashMap
Definition: PerfectHashMap.h:38
PerfectHashMap::make_large
void make_large(int n)
Definition: PerfectHashMap.h:227
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.
Halide::Internal::Autoscheduler::Adams2019Params
Definition: CostModel.h:19
Halide::Internal::Autoscheduler::Adams2019Params::disable_memoized_blocks
int disable_memoized_blocks
If set to nonzero value: tiling sizes are not cached across passes.
Definition: CostModel.h:51
Halide::Internal::Autoscheduler::Adams2019Params::disable_memoized_features
int disable_memoized_features
If set to nonzero value: features of possible schedules are always recalculated, and are not cached a...
Definition: CostModel.h:47
Halide::Internal::Autoscheduler::Cache
Definition: Cache.h:94
Halide::Internal::Autoscheduler::Cache::options
CachingOptions options
Definition: Cache.h:95
Halide::Internal::Autoscheduler::Cache::Cache
Cache()=delete
Halide::Internal::Autoscheduler::Cache::Cache
Cache(const CachingOptions &_options, size_t nodes_size)
Definition: Cache.h:102
Halide::Internal::Autoscheduler::Cache::~Cache
~Cache()=default
Halide::Internal::Autoscheduler::Cache::add_memoized_blocks
bool add_memoized_blocks(const State *state, std::function< void(IntrusivePtr< State > &&)> &accept_child, const FunctionDAG::Node *node, int &num_children, const FunctionDAG &dag, const Adams2019Params &params, CostModel *cost_model) const
Halide::Internal::Autoscheduler::Cache::memoize_blocks
void memoize_blocks(const FunctionDAG::Node *node, LoopNest *new_root)
Halide::Internal::Autoscheduler::Cache::memoized_compute_root_blocks
BlockCache memoized_compute_root_blocks
Definition: Cache.h:96
Halide::Internal::Autoscheduler::Cache::cache_hits
size_t cache_hits
Definition: Cache.h:98
Halide::Internal::Autoscheduler::Cache::cache_misses
size_t cache_misses
Definition: Cache.h:99
Halide::Internal::Autoscheduler::CachingOptions
Definition: Cache.h:76
Halide::Internal::Autoscheduler::CachingOptions::cache_blocks
bool cache_blocks
Definition: Cache.h:77
Halide::Internal::Autoscheduler::CachingOptions::MakeOptionsFromParams
static CachingOptions MakeOptionsFromParams(const Adams2019Params &params)
Definition: Cache.h:80
Halide::Internal::Autoscheduler::CachingOptions::cache_features
bool cache_features
Definition: Cache.h:78
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::State
Definition: State.h:21
Halide::Internal::IntrusivePtr
Intrusive shared pointers have a reference count (a RefCount object) stored in the class itself.
Definition: IntrusivePtr.h:71