1 /* Copyright 2018 The TensorFlow Authors. All Rights Reserved.
2 
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
6 
7     http://www.apache.org/licenses/LICENSE-2.0
8 
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License.
14 ==============================================================================*/
15 #ifndef TENSORFLOW_CORE_GRAPPLER_OPTIMIZERS_SCOPED_ALLOCATOR_OPTIMIZER_H_
16 #define TENSORFLOW_CORE_GRAPPLER_OPTIMIZERS_SCOPED_ALLOCATOR_OPTIMIZER_H_
17 
18 #include <atomic>
19 #include <unordered_set>
20 #include <vector>
21 
22 #include "absl/container/flat_hash_map.h"
23 #include "absl/container/flat_hash_set.h"
24 #include "tensorflow/core/grappler/optimizers/graph_optimizer.h"
25 #include "tensorflow/core/grappler/utils.h"
26 #include "tensorflow/core/protobuf/rewriter_config.pb.h"
27 
28 namespace tensorflow {
29 class Graph;
30 
31 namespace grappler {
32 class GraphProperties;
33 class NodeMap;
34 class ScopedAllocatorOptimizer;
35 
36 // An Optimizer that introduces ScopedAllocators in order to reduce data
37 // movement and consolidate some kinds of Ops.
38 class ScopedAllocatorOptimizer : public GraphOptimizer {
39  public:
40   ScopedAllocatorOptimizer(RewriterConfig::Toggle opt_level,
41                            const ScopedAllocatorOptions& opts);
42   ~ScopedAllocatorOptimizer() override;
43 
name()44   string name() const override { return "scoped_allocator_optimizer"; }
45 
UsesFunctionLibrary()46   bool UsesFunctionLibrary() const override { return true; }
47 
48   Status Optimize(Cluster* cluster, const GrapplerItem& item,
49                   GraphDef* optimized_graph) override;
50 
Feedback(Cluster * cluster,const GrapplerItem & item,const GraphDef & optimized_graph,double result)51   void Feedback(Cluster* cluster, const GrapplerItem& item,
52                 const GraphDef& optimized_graph, double result) override {}
53 
54   // Map from an Op name to a vector of Nodes with that Op.
55   typedef absl::flat_hash_map<string, std::vector<NodeDef*>> DevOpOccurrences;
56   // Map from a device name to a DevOpOccurrences map.
57   typedef absl::flat_hash_map<string, DevOpOccurrences> GraphOpOccurrences;
58   typedef absl::flat_hash_set<string> OpNameSet;
59 
60   Status ProcessGraphDef(GraphDef* graph,
61                          const GraphProperties& graph_properties);
62 
63   // Populates *occs by grouping Nodes with common Ops, according to
64   // their assigned devices.
65   void FindOpOccurrences(GraphDef* graph, const OpNameSet& op_names,
66                          GraphOpOccurrences* occs);
67 
68   // Returns a new, unused scope_id to be assigned to a ScopedAllocator that
69   // will allocate num_fields (> 0) separate tensors.
70   int NewScopedAllocatorId(int num_fields);
71 
72   // Returns a new, unused id to be assigned to an IdentityOp used in this graph
73   // rewrite.
74   Status NewIdentityId(int* id);
75 
node_map()76   NodeMap* node_map() { return node_map_.get(); }
77 
repeated_outputs()78   const absl::flat_hash_set<string>& repeated_outputs() {
79     return repeated_outputs_;
80   }
81 
82   // Appends values to the attr value under name in node_def, if present.
83   // If not present does an assignment.
84   static void ExtendNodeAttr(StringPiece name, const std::vector<int32>& values,
85                              NodeDef* node_def);
86 
87   // Class that knows how to do graph rewriting for a particular kind of Op in
88   // order to take advantage of a ScopedAllocator.
89   class Rewriter {
90    public:
~Rewriter()91     virtual ~Rewriter() {}
92 
93     virtual Status Rewrite(ScopedAllocatorOptimizer* paopti,
94                            int64 invocation_count, GraphDef* graph,
95                            const string& op_name,
96                            const std::vector<NodeDef*>& nodes,
97                            bool* applied) = 0;
98 
SetGraphProperties(const GraphProperties & graph_properties)99     void SetGraphProperties(const GraphProperties& graph_properties) {
100       graph_properties_ = &graph_properties;
101       CHECK(graph_properties_);
102     }
103 
104    protected:
105     const GraphProperties* graph_properties_;
106   };
107 
108  private:
109   Rewriter* GetRewriter(const string& op_name);
110 
111   Status OrderNodeSet(std::vector<NodeDef*>* nodes) const;
112 
113   RewriterConfig::Toggle opt_level_;
114   std::unordered_set<string> nodes_to_preserve_;
115   OpNameSet op_name_set_;
116   absl::flat_hash_map<string, Rewriter*> rewriters_;
117   std::vector<Rewriter*> to_delete_;
118   int next_sa_id_ = 1;
119   int next_identity_id_ = 1;
120   std::unique_ptr<NodeMap> node_map_;
121   // Keeps track of outputs, i.e. a node and an output index, that are inputs to
122   // more than one op groups that are candidates for scoped allocator
123   // optimization.
124   absl::flat_hash_set<string> repeated_outputs_;
125 };
126 
127 }  // namespace grappler
128 }  // namespace tensorflow
129 #endif  // TENSORFLOW_CORE_GRAPPLER_OPTIMIZERS_SCOPED_ALLOCATOR_OPTIMIZER_H_
130