1 | /* |
2 | * Licensed to the Apache Software Foundation (ASF) under one |
3 | * or more contributor license agreements. See the NOTICE file |
4 | * distributed with this work for additional information |
5 | * regarding copyright ownership. The ASF licenses this file |
6 | * to you under the Apache License, Version 2.0 (the |
7 | * "License"); you may not use this file except in compliance |
8 | * with the License. You may obtain a copy of the License at |
9 | * |
10 | * http://www.apache.org/licenses/LICENSE-2.0 |
11 | * |
12 | * Unless required by applicable law or agreed to in writing, |
13 | * software distributed under the License is distributed on an |
14 | * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
15 | * KIND, either express or implied. See the License for the |
16 | * specific language governing permissions and limitations |
17 | * under the License. |
18 | */ |
19 | |
20 | /*! |
21 | * \file src/relay/collage/prune_candidates.h |
22 | * \brief Try to remove candidates which will never contribute to an optimal partitioning. |
23 | */ |
24 | |
25 | #ifndef TVM_RELAY_COLLAGE_PRUNE_CANDIDATES_H_ |
26 | #define TVM_RELAY_COLLAGE_PRUNE_CANDIDATES_H_ |
27 | |
28 | #include <vector> |
29 | |
30 | #include "./candidate_partition.h" |
31 | #include "./dataflow_graph.h" |
32 | |
33 | namespace tvm { |
34 | namespace relay { |
35 | namespace collage { |
36 | |
37 | /*! |
38 | * \brief Returns \p initial_candidates with all unnecessary candidates pruned. |
39 | * |
40 | * We prune according to the following two heuristics: |
41 | * 1. Given partitions (A, target) and (B, target) then |
42 | * cost(A union B, target) < cost(A, target) + cost(B, target). |
43 | * That is, there's no use estimating the cost of small partitions when a larger partition |
44 | * containing them is also available. More precisely, call a partition 'maximal' if it is |
45 | * not contained by any other partition for the same target. Then we want to prefer maximal |
46 | * candidates when searching. |
47 | * 2. Given maximal partitions (A union B, target) and (A union B, target') where |
48 | * target != target', then min(cost(A union B, target), cost(A union B, target')) < |
49 | * min(cost(A, target) + cost(B, target'), cost(A, target') + cost(B, target)). |
50 | * That is, there's no use estimating cross-combinations of partitions which are not maximal. |
51 | * |
52 | * However, we can't prune a non-maximal candidate if it will make some other maximal candidate |
53 | * unreachable during the Collage search. We achieve this by iterating until fixed point: |
54 | * - Find maximal candidates of current set of candidates. |
55 | * - Add those maximal candidates to the output 'pruned' set. |
56 | * - If any two candidates in the 'pruned' set intersect without being equal, remove those from |
57 | * the current set of candidates and go around again. That will force more candidates to |
58 | * be considered 'maximal'. |
59 | * That over-approximates the true necessary candidates but is at least simple. |
60 | * |
61 | * CAUTION: This is pretty experimental. The above heuristics won't always be safe, and I don't |
62 | * have a proof the pruned candidate set won't lead to 'No candidate was found covering |
63 | * sub-expression...' errors in Partitioner::Partition(). |
64 | */ |
65 | std::vector<CandidatePartition> PruneCandidates( |
66 | const DataflowGraph& dataflow_graph, const std::vector<CandidatePartition>& initial_candidates); |
67 | |
68 | } // namespace collage |
69 | } // namespace relay |
70 | } // namespace tvm |
71 | |
72 | #endif // TVM_RELAY_COLLAGE_PRUNE_CANDIDATES_H_ |
73 | |