reference_count_pass.cc 7.3 KB
Newer Older
S
sneaxiy 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// Copyright (c) 2018 PaddlePaddle Authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

S
sneaxiy 已提交
15
#include <queue>
S
sneaxiy 已提交
16
#include <string>
S
fix bug  
sneaxiy 已提交
17
#include <type_traits>
S
sneaxiy 已提交
18 19 20
#include <vector>

#include "paddle/fluid/framework/details/computation_op_handle.h"
S
sneaxiy 已提交
21
#include "paddle/fluid/framework/details/eager_deletion_op_handle.h"
S
sneaxiy 已提交
22
#include "paddle/fluid/framework/details/multi_devices_helper.h"
S
fix bug  
sneaxiy 已提交
23
#include "paddle/fluid/framework/details/op_graph_view.h"
S
sneaxiy 已提交
24
#include "paddle/fluid/framework/details/reference_count_pass.h"
S
sneaxiy 已提交
25
#include "paddle/fluid/framework/details/reference_count_pass_helper.h"
X
Xin Pan 已提交
26
#include "paddle/fluid/framework/ir/graph_helper.h"
S
sneaxiy 已提交
27 28 29 30 31

namespace paddle {
namespace framework {
namespace details {

S
fix bug  
sneaxiy 已提交
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
struct OpConnectionDetector {
 public:
  enum RelationShip { kSame = 0, kNoDeps = 1, kBefore = 2, kAfter = 3 };

  explicit OpConnectionDetector(const std::vector<OpHandleBase *> &all_ops)
      : graph_(all_ops) {}

  template <typename OpSet>
  std::unordered_set<typename OpSet::key_type> MaxNoDepOps(
      const OpSet &op_set) {
    using KeyType = typename OpSet::key_type;
    static_assert(
        std::is_base_of<OpHandleBase,
                        typename std::remove_pointer<KeyType>::type>::value,
        "Key type of OpSet must be or derived of OpHandleBase");

    std::vector<OpHandleBase *> ops(op_set.begin(), op_set.end());
    std::unordered_set<KeyType> ret;
    auto rels = GetRelations(ops);
    auto not_before = [](RelationShip r) { return r != kBefore; };
    for (size_t i = 0; i < rels.size(); ++i) {
      if (std::all_of(rels[i].begin(), rels[i].end(), not_before)) {
        ret.insert(static_cast<KeyType>(ops[i]));
      }
    }
    return ret;
  }

 private:
  std::vector<std::vector<RelationShip>> GetRelations(
      const std::vector<OpHandleBase *> ops) {
    std::unordered_map<OpHandleBase *, size_t> op_to_idx;
    for (size_t i = 0; i < ops.size(); ++i) {
      PADDLE_ENFORCE(graph_.HasOp(ops[i]), "Op does not exist in graph");
      op_to_idx[ops[i]] = i;
    }

    PADDLE_ENFORCE(op_to_idx.size() == ops.size(), "Duplicate ops");

    std::vector<std::vector<RelationShip>> ret(ops.size());
    for (auto &e : ret) {
      e.assign(ops.size(), kSame);
    }

    size_t found_num = ops.size();
    size_t total_num = ops.size() * ops.size();
    auto visitor = [&](OpHandleBase *op, size_t i) {
      auto it = op_to_idx.find(op);
      if (it != op_to_idx.end()) {
        size_t j = it->second;
        if (ret[i][j] != kSame) {
          ret[i][j] = kBefore;
          ret[j][i] = kAfter;
          found_num += 2;
          if (found_num == total_num) {
            return false;
          }
        }
      }
      return true;
    };

    for (size_t i = 0; i < ops.size(); ++i) {
      auto sub_visitor = [&, i](OpHandleBase *op) { return visitor(op, i); };
      if (!graph_.VisitAllPendingOps(ops[i], sub_visitor)) {
        break;
      }
    }

    for (size_t i = 0; i < ops.size(); ++i) {
      for (size_t j = i + 1; j < ops.size(); ++j) {
        if (ret[i][j] != kSame) continue;
        ret[i][j] = kNoDeps;
        ret[j][i] = kNoDeps;
      }
    }

    return ret;
  }

  const OpGraphView graph_;
};

S
sneaxiy 已提交
115 116 117 118 119
static ComputationOpHandle *FindNextComputationOpHandleOrReturnItself(
    OpHandleBase *op, size_t scope_idx) {
  std::queue<OpHandleBase *> q;
  std::unordered_set<OpHandleBase *> visited;
  q.push(op);
S
sneaxiy 已提交
120
  do {
S
sneaxiy 已提交
121 122 123 124 125 126 127 128 129 130
    auto *op = q.front();
    q.pop();
    auto *compute_op = dynamic_cast<ComputationOpHandle *>(op);
    if (compute_op != nullptr && compute_op->GetScopeIdx() == scope_idx) {
      return compute_op;
    }
    for (auto *out_var : op->Outputs()) {
      for (auto *pending_op : out_var->PendingOps()) {
        if (visited.count(pending_op)) continue;
        visited.insert(pending_op);
S
sneaxiy 已提交
131 132
      }
    }
S
sneaxiy 已提交
133
  } while (!q.empty());
S
sneaxiy 已提交
134 135 136
  return nullptr;
}

S
sneaxiy 已提交
137 138
std::unique_ptr<ir::Graph> ReferenceCountPass::ApplyImpl(
    std::unique_ptr<ir::Graph> graph) const {
S
sneaxiy 已提交
139 140 141 142 143 144 145 146
  auto &vars = graph->Get<GraphVars>(kGraphVars);
  auto &ref_cnts = Get<std::vector<ReferenceCountMap>>(kGlobalReferenceCount);
  auto &last_live_ops_of_vars =
      Get<std::vector<LastLiveOpsOfVars>>(kLastLiveOpsOfVars);

  last_live_ops_of_vars = std::vector<LastLiveOpsOfVars>(vars.size());
  ref_cnts = std::vector<ReferenceCountMap>(vars.size());

S
fix bug  
sneaxiy 已提交
147 148
  OpConnectionDetector detector(ir::FilterByNodeWrapper<OpHandleBase>(*graph));

S
sneaxiy 已提交
149 150
  for (size_t i = 0; i < vars.size(); ++i) {
    for (auto &name_var_pair : vars[i]) {
S
fix bug  
sneaxiy 已提交
151 152 153 154 155
      if (name_var_pair.second.empty()) {
        continue;
      }

      const std::string &var_name = name_var_pair.first;
S
sneaxiy 已提交
156 157 158 159 160 161 162 163 164 165
      auto *last_ver_var = name_var_pair.second.back();

      VarDesc *var_desc = nullptr;
      std::find_if(name_var_pair.second.rbegin(), name_var_pair.second.rend(),
                   [&](VarHandle *var_handle) -> bool {
                     var_desc = var_handle->Node()->Var();
                     return var_desc != nullptr;
                   });

      if (var_desc == nullptr || var_desc->Persistable()) {
S
sneaxiy 已提交
166
        continue;
S
sneaxiy 已提交
167 168 169 170
      }

      auto var_type = var_desc->Proto()->type().type();
      if (var_type != proto::VarType::LOD_TENSOR &&
S
sneaxiy 已提交
171 172
          var_type != proto::VarType::SELECTED_ROWS &&
          var_type != proto::VarType::LOD_TENSOR_ARRAY) {
S
sneaxiy 已提交
173
        continue;
S
sneaxiy 已提交
174 175
      }

S
sneaxiy 已提交
176
      std::unordered_set<ComputationOpHandle *> last_live_op;
S
fix bug  
sneaxiy 已提交
177
      auto add_last_live_op = [&](OpHandleBase *op) -> bool {
S
sneaxiy 已提交
178 179 180
        auto *compute_op = FindNextComputationOpHandleOrReturnItself(op, i);
        if (compute_op) {
          last_live_op.insert(compute_op);
S
fix bug  
sneaxiy 已提交
181 182 183
          return true;
        } else {
          return false;
S
sneaxiy 已提交
184 185
        }
      };
S
fix bug  
sneaxiy 已提交
186 187

      bool can_delete = false;
S
sneaxiy 已提交
188 189 190
      auto &pending_ops = last_ver_var->PendingOps();
      if (pending_ops.empty()) {
        auto *generated_op = last_ver_var->GeneratedOp();
S
fix bug  
sneaxiy 已提交
191 192
        if (generated_op && add_last_live_op(generated_op)) {
          can_delete = true;
S
sneaxiy 已提交
193 194
        }
      } else {
S
fix bug  
sneaxiy 已提交
195
        can_delete = true;
S
sneaxiy 已提交
196
        for (auto *pending_op : pending_ops) {
S
fix bug  
sneaxiy 已提交
197 198 199 200
          if (!add_last_live_op(pending_op)) {
            can_delete = false;
            break;
          }
S
sneaxiy 已提交
201
        }
S
sneaxiy 已提交
202 203
      }

S
fix bug  
sneaxiy 已提交
204 205 206 207 208 209 210 211 212 213
      if (can_delete) {
        size_t original_size = last_live_op.size();
        last_live_op = detector.MaxNoDepOps(last_live_op);
        if (last_live_op.size() != original_size) {
          VLOG(10) << "Shrink last living op number of " << var_name << " from "
                   << original_size << " to " << last_live_op.size();
        }
        ref_cnts[i].emplace(var_name, last_live_op.size());
        last_live_ops_of_vars[i].emplace(var_name, std::move(last_live_op));
      }
S
sneaxiy 已提交
214 215
    }
  }
S
fix bug  
sneaxiy 已提交
216

S
sneaxiy 已提交
217 218 219 220 221 222 223 224 225 226
  return graph;
}

}  // namespace details
}  // namespace framework
}  // namespace paddle

REGISTER_PASS(reference_count_pass,
              paddle::framework::details::ReferenceCountPass)
    .RequirePassAttr(paddle::framework::details::kGlobalReferenceCount)
S
sneaxiy 已提交
227
    .RequirePassAttr(paddle::framework::details::kLastLiveOpsOfVars);