inference-engine/thirdparty/fluid/modules/gapi/src/compiler/passes/islands.cpp

   1 // This file is part of OpenCV project.
   2 // It is subject to the license terms in the LICENSE file found in the top-level directory
   3 // of this distribution and at http://opencv.org/license.html.
   4 //
   5 // Copyright (C) 2018-2019 Intel Corporation
   6
   7
   8 #include "precomp.hpp"
   9
  10 #include <sstream>
  11 #include <stack>
  12 #include <ade/util/chain_range.hpp>
  13 #include <ade/graph.hpp>
  14
  15 #include "compiler/gmodel.hpp"
  16 #include "compiler/passes/passes.hpp"
  17
  18 namespace
  19 {
  20     bool is_within_same_island(const cv::gimpl::GModel::Graph &gr,
  21                                const ade::NodeHandle          &dataNode,
  22                                const std::string              &island)
  23     {
  24         // A data node is within the same island as it's reader node
  25         // if and only if data object's producer island (if there's a producer)
  26         // is the same as the specified one.
  27         //
  28         // An object may have only a single producer, but multiple consumers,
  29         // and these consumers may be assigned to different Islands.
  30         // Since "initIslands" traversal direction is op-to-args, i.e. reverse,
  31         // a single Data object may be visited twice during Islands initialization.
  32         //
  33         // In this case, Data object is part of Island A if and only if:
  34         // - Data object's producer is part of Island A,
  35         // - AND any of Data obejct's consumers is part of Island A.
  36         //
  37         //   Op["island0"] --> Data[ ? ] --> Op["island0"]
  38         //                       :
  39         //                       '---------> Op["island1"]
  40         //
  41         // In the above example, Data object is assigned to "island0" as
  42         // it is surrounded by operations assigned to "island0"
  43
  44         using namespace cv::gimpl;
  45
  46         if (   gr.metadata(dataNode).contains<Island>()
  47             && gr.metadata(dataNode).get<Island>().island != island)
  48             return false;
  49
  50         if (dataNode->inNodes().empty())
  51             return false;
  52
  53         GAPI_Assert(dataNode->inNodes().size() == 1u);
  54         const auto prod_h = dataNode->inNodes().front();
  55
  56         // FIXME: ADE should have something like get_or<> or get<>(default)
  57         GAPI_Assert(gr.metadata(prod_h).get<NodeType>().t == NodeType::OP);
  58         return     (   gr.metadata(prod_h).contains<Island>()
  59                     && gr.metadata(prod_h).get<Island>().island == island)
  60                     && (ade::util::any_of(dataNode->outNodes(), [&](ade::NodeHandle cons_h)
  61                     {
  62                         return (   gr.metadata(cons_h).contains<Island>()
  63                                 && gr.metadata(cons_h).get<Island>().island == island);
  64                     }));
  65     }
  66 } // anonymous namespace
  67
  68 // Initially only Operations have Island tag. This pass adds Island tag
  69 // to all data objects within an Island.
  70 // A data object is considered within an Island if and only if
  71 // its reader and writer are assigned to this Island (see above).
  72 void cv::gimpl::passes::initIslands(ade::passes::PassContext &ctx)
  73 {
  74     GModel::Graph gr(ctx.graph);
  75     for (const auto &nh : gr.nodes())
  76     {
  77         if (gr.metadata(nh).get<NodeType>().t == NodeType::OP)
  78         {
  79             if (gr.metadata(nh).contains<Island>())
  80             {
  81                 const auto island = gr.metadata(nh).get<Island>().island;
  82
  83                 // It is enough to check only input nodes
  84                 for (const auto &in_data_node : nh->inNodes())
  85                 {
  86                     if (is_within_same_island(gr, in_data_node, island))
  87                     {
  88                         gr.metadata(in_data_node).set(Island{island});
  89                     }
  90                 } // for(in_data_node)
  91             } // if (contains<Island>)
  92         } // if (OP)
  93     } // for (nodes)
  94 }
  95
  96 // There should be no multiple (disconnected) islands with the same name.
  97 // This may occur if user assigns the same islands name to multiple ranges
  98 // in the graph.
  99 // FIXME: How it could be avoided on an earlier stage?
 100 void cv::gimpl::passes::checkIslands(ade::passes::PassContext &ctx)
 101 {
 102     GModel::ConstGraph gr(ctx.graph);
 103
 104     // The algorithm is teh following:
 105     //
 106     // 1. Put all Tagged nodes (both Operations and Data) into a set
 107     // 2. Initialize Visited set as (empty)
 108     // 3. Initialize Traversal stack as (empty)
 109     // 4. Initialize Islands map (String -> Integer) as (empty)
 110     // 5. For every Tagged node from a set
 111     //    a. Skip if it is Visited
 112     //    b. For every input/output node:
 113     //       * if it is tagged with the same island:
 114     //         - add it to Traversal stack
 115     //         - remove from Tagged nodes if it is t
 116     //    c. While (stack is not empty):
 117     //       - Take a node from Stack
 118     //       - Repeat (b)
 119     //    d. Increment Islands map [this island] by 1
 120     //
 121     //
 122     // If whatever Island has counter is more than 1, it is a disjoint
 123     // one (i.e. there's two islands with the same name).
 124
 125     using node_set = std::unordered_set
 126          < ade::NodeHandle
 127          , ade::HandleHasher<ade::Node>
 128          >;
 129     node_set tagged_nodes;
 130     node_set visited_tagged_nodes;
 131     std::unordered_map<std::string, int> island_counters;
 132
 133     for (const auto &nh : gr.nodes())
 134     {
 135         if (gr.metadata(nh).contains<Island>())
 136         {
 137             tagged_nodes.insert(nh);
 138             island_counters[gr.metadata(nh).get<Island>().island] = 0;
 139         }
 140     }
 141
 142     // Make a copy to allow list modifications during traversal
 143     for (const auto &tagged_nh : tagged_nodes)
 144     {
 145         if (visited_tagged_nodes.end() != ade::util::find(visited_tagged_nodes, tagged_nh))
 146             continue;
 147
 148         // Run the recursive traversal process as described in 5/a-d.
 149         // This process is like a flood-fill traversal for island.
 150         // If there's to distint successful flood-fills happened for the same island
 151         // name, there are two islands with this name.
 152         std::stack<ade::NodeHandle> stack;
 153         stack.push(tagged_nh);
 154
 155         while (!stack.empty())
 156         {
 157             const auto this_nh = stack.top();
 158             stack.pop();
 159
 160             // Since _this_ node is visited, it is a part of processed island
 161             // so mark it as visited to skip in other recursive processes
 162             visited_tagged_nodes.insert(this_nh);
 163
 164             GAPI_DbgAssert(gr.metadata(this_nh).contains<Island>());
 165             GAPI_DbgAssert(   gr.metadata(this_nh  ).get<Island>().island
 166                          == gr.metadata(tagged_nh).get<Island>().island);
 167             const auto &this_island = gr.metadata(this_nh).get<Island>().island;
 168
 169             for (const auto neighbor_nh : ade::util::chain(this_nh->inNodes(), this_nh->outNodes()))
 170             {
 171                 if (   gr.metadata(neighbor_nh).contains<Island>()
 172                     && gr.metadata(neighbor_nh).get<Island>().island == this_island
 173                     && !visited_tagged_nodes.count(neighbor_nh))
 174                 {
 175                     stack.push(neighbor_nh);
 176                 }
 177             } // for (neighbor)
 178         } // while (stack)
 179
 180         // Flood-fill is over, now increment island counter for this island
 181         island_counters[gr.metadata(tagged_nh).get<Island>().island]++;
 182     } // for(tagged)
 183
 184     bool check_failed = false;
 185     std::stringstream ss;
 186     for (const auto &ic : island_counters)
 187     {
 188         GAPI_Assert(ic.second > 0);
 189         if (ic.second > 1)
 190         {
 191             check_failed = true;
 192             ss << "\"" << ic.first << "\"(" << ic.second << ") ";
 193         }
 194     }
 195     if (check_failed)
 196     {
 197         util::throw_error
 198             (std::logic_error("There are multiple distinct islands "
 199                               "with the same name: [" + ss.str() + "], "
 200                               "please check your cv::gapi::island() parameters!"));
 201     }
 202 }
 203
 204 void cv::gimpl::passes::checkIslandsContent(ade::passes::PassContext &ctx)
 205 {
 206     GModel::ConstGraph gr(ctx.graph);
 207     std::unordered_map<std::string, cv::gapi::GBackend> backends_of_islands;
 208     for (const auto& nh : gr.nodes())
 209     {
 210         if (NodeType::OP == gr.metadata(nh).get<NodeType>().t &&
 211             gr.metadata(nh).contains<Island>())
 212         {
 213             const auto island      = gr.metadata(nh).get<Island>().island;
 214             auto island_backend_it = backends_of_islands.find(island);
 215             const auto& op         = gr.metadata(nh).get<Op>();
 216
 217             if (island_backend_it != backends_of_islands.end())
 218             {
 219                 // Check that backend of the operation coincides with the backend of the island
 220                 // Backend of the island is determined by the backend of the first operation from this island
 221                 if (island_backend_it->second != op.backend)
 222                 {
 223                     util::throw_error(std::logic_error(island + " contains kernels " + op.k.name +
 224                                                        " with different backend"));
 225                 }
 226             }
 227             else
 228             {
 229                 backends_of_islands.emplace(island, op.backend);
 230             }
 231         }
 232     }
 233 }