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 #include "tensorflow/compiler/xla/client/padding.h"
17
18 #include <algorithm>
19
20 #include "tensorflow/compiler/xla/util.h"
21 #include "tensorflow/core/lib/math/math_util.h"
22 #include "tensorflow/core/platform/logging.h"
23
24 namespace xla {
25
ValidatePaddingValues(absl::Span<const int64> input_dimensions,absl::Span<const int64> window_dimensions,absl::Span<const int64> window_strides)26 Status ValidatePaddingValues(absl::Span<const int64> input_dimensions,
27 absl::Span<const int64> window_dimensions,
28 absl::Span<const int64> window_strides) {
29 bool ok = input_dimensions.size() == window_dimensions.size() &&
30 input_dimensions.size() == window_strides.size();
31 if (!ok) {
32 return InvalidArgument(
33 "Want input dimensions size %u = window dimensions size %u = window "
34 "strides size %u",
35 input_dimensions.size(), window_dimensions.size(),
36 window_strides.size());
37 }
38 return Status::OK();
39 }
40
MakePadding(absl::Span<const int64> input_dimensions,absl::Span<const int64> window_dimensions,absl::Span<const int64> window_strides,Padding padding)41 std::vector<std::pair<int64, int64>> MakePadding(
42 absl::Span<const int64> input_dimensions,
43 absl::Span<const int64> window_dimensions,
44 absl::Span<const int64> window_strides, Padding padding) {
45 TF_CHECK_OK(ValidatePaddingValues(input_dimensions, window_dimensions,
46 window_strides));
47 std::vector<std::pair<int64, int64>> low_high_padding;
48 switch (padding) {
49 case Padding::kValid:
50 low_high_padding.resize(window_dimensions.size(), {0, 0});
51 return low_high_padding;
52
53 case Padding::kSame:
54 for (size_t i = 0; i < input_dimensions.size(); ++i) {
55 int64 input_dimension = input_dimensions[i];
56 int64 window_dimension = window_dimensions[i];
57 int64 window_stride = window_strides[i];
58 // We follow the same convention as in Tensorflow, such that
59 // output dimension := ceil(input_dimension / window_stride).
60 // See tensorflow/tensorflow/python/ops/nn.py
61 // for the reference. See also tensorflow/core/kernels/ops_util.cc
62 // for the part where we avoid negative padding using max(0, x).
63 //
64 //
65 // For an odd sized window dimension 2N+1 with stride 1, the middle
66 // element is always inside the base area, so we can see it as N + 1 +
67 // N elements. In the example below, we have a kernel of size
68 // 2*3+1=7 so that the center element is 4 with 123 to the
69 // left and 567 to the right.
70 //
71 // base area: ------------------------
72 // kernel at left: 1234567
73 // kernel at right: 1234567
74 //
75 // We can see visually here that we need to pad the base area
76 // by 3 on each side:
77 //
78 // padded base area: 000------------------------000
79 //
80 // For an even number 2N, there are two options:
81 //
82 // *** Option A
83 //
84 // We view 2N as (N - 1) + 1 + N, so for N=3 we have 12 to the
85 // left, 3 is the center and 456 is to the right, like this:
86 //
87 // base area: ------------------------
88 // kernel at left: 123456
89 // kernel at right: 123456
90 // padded base area: 00------------------------000
91 //
92 // Note how we pad by one more to the right than to the left.
93 //
94 // *** Option B
95 //
96 // We view 2N as N + 1 + (N - 1), so for N=3 we have 123 to
97 // the left, 4 is the center and 56 is to the right, like
98 // this:
99 //
100 // base area: ------------------------
101 // kernel at left: 123456
102 // kernel at right: 123456
103 // padded base area: 000------------------------00
104 //
105 // The choice here is arbitrary. We choose option A as this is
106 // what DistBelief and Tensorflow do.
107 //
108 // When the stride is greater than 1, the output size is smaller than
109 // the input base size. The base area is padded such that the last
110 // window fully fits in the padded base area, and the padding amount is
111 // evenly divided between the left and the right (or 1 more on the right
112 // if odd size padding is required). The example below shows the
113 // required padding when the base size is 10, the kernel size is 5, and
114 // the stride is 3. In this example, the output size is 4.
115 //
116 // base area: ----------
117 // 1'st kernel: 12345
118 // 2'nd kernel: 12345
119 // 3'rd kernel: 12345
120 // 4'th kernel: 12345
121 // padded base area: 00----------00
122 int64 output_dimension =
123 tensorflow::MathUtil::CeilOfRatio(input_dimension, window_stride);
124 int64 padding_size =
125 std::max<int64>((output_dimension - 1) * window_stride +
126 window_dimension - input_dimension,
127 0);
128 low_high_padding.emplace_back(
129 tensorflow::MathUtil::FloorOfRatio(padding_size, int64{2}),
130 tensorflow::MathUtil::CeilOfRatio(padding_size, int64{2}));
131 }
132 break;
133 }
134
135 return low_high_padding;
136 }
137
138 } // namespace xla
139