1 /* Copyright 2017 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 16 #ifndef TENSORFLOW_CORE_GRAPPLER_OPTIMIZERS_DEPENDENCY_OPTIMIZER_H_ 17 #define TENSORFLOW_CORE_GRAPPLER_OPTIMIZERS_DEPENDENCY_OPTIMIZER_H_ 18 19 #include <unordered_set> 20 #include "tensorflow/core/grappler/optimizers/graph_optimizer.h" 21 #include "tensorflow/core/grappler/utils.h" 22 #include "tensorflow/core/protobuf/rewriter_config.pb.h" 23 24 namespace tensorflow { 25 namespace grappler { 26 27 // Optimize TF computations by removing control dependencies or re-arranging 28 // them to shorten the critical path for a model step or enable other 29 // optimizations, such as removing nodes that are effectively noops. 30 class DependencyOptimizer : public GraphOptimizer { 31 public: DependencyOptimizer()32 DependencyOptimizer() {} DependencyOptimizer(RewriterConfig::Toggle opt_level)33 explicit DependencyOptimizer(RewriterConfig::Toggle opt_level) {} ~DependencyOptimizer()34 ~DependencyOptimizer() override {} 35 name()36 string name() const override { return "dependency_optimizer"; }; 37 UsesFunctionLibrary()38 bool UsesFunctionLibrary() const override { return false; } 39 40 Status Optimize(Cluster* cluster, const GrapplerItem& item, 41 GraphDef* optimized_graph) override; 42 43 void Feedback(Cluster* cluster, const GrapplerItem& item, 44 const GraphDef& optimized_graph, double result) override; 45 46 private: 47 // Returns true if bypassing node does not increase the number of edges or 48 // number of edges crossing a device boundary. 49 bool BypassingNodeIsBeneficial( 50 const NodeDef& node, const std::vector<NodeDef*>& input_nodes, 51 const std::vector<NodeDef*>& output_nodes) const; 52 int NumEdgesIfBypassed(const NodeDef& node, 53 const std::vector<NodeDef*>& output_nodes) const; 54 // Returns true if node is not an Identity node or if it is an Identity 55 // that is safe to remove. 56 bool SafeToRemoveIdentity(const NodeDef& node) const; 57 // Returns true if it is safe to convert node to NoOp. 58 bool SafeToConvertToNoOp(const NodeDef& node) const; 59 // Removes all duplicate control dependencies. 60 void CleanControlInputs(); 61 // Builds a map from the &optimized_graph_->node(i) to i. 62 void BuildNodeToIdx(); 63 // Tries to optimize the node with the given index, possibly additional 64 // optimizations by inserting nodes in nodes_to_simplify, and pruning nodes by 65 // inserting them in nodes_to_delete. 66 void OptimizeNode(int node_idx, SetVector<int>* nodes_to_simplify, 67 std::set<int>* nodes_to_delete); 68 // Eliminates redundant control dependencies by computing the transitive 69 // reduction of the graph. 70 Status TransitiveReduction(); 71 // Main driver of dependency optimizations. 72 Status OptimizeDependencies(); 73 // Replaces multiple cross-device control edges from the same device with a 74 // single control edge. If `host_granularity` is true then group control 75 // edges from all devices on the same host. 76 void GroupCrossDeviceControlEdges(bool host_granularity); 77 78 bool fetch_nodes_known_; 79 std::unordered_set<string> nodes_to_preserve_; 80 std::unique_ptr<NodeMap> node_map_; 81 std::unordered_map<const NodeDef*, int> node_to_idx_; 82 GraphDef* optimized_graph_; // Not owned. 83 }; 84 85 } // end namespace grappler 86 } // end namespace tensorflow 87 88 #endif // TENSORFLOW_CORE_GRAPPLER_OPTIMIZERS_DEPENDENCY_OPTIMIZER_H_ 89