1// Copyright 2015 The Gemmlowp 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// block_params.h: Logic to choose L1 and L2 block sizes
16// to optimize cache-friendliness.
17
18#ifndef GEMMLOWP_INTERNAL_BLOCK_PARAMS_H_
19#define GEMMLOWP_INTERNAL_BLOCK_PARAMS_H_
20
21#include "common.h"
22
23namespace gemmlowp {
24
25// A BlockParams instance contains a full description of all the block size
26// parameters to be used by a Gemm.
27// There are two nested levels of block subdivisions: first a subdivision
28// into large blocks that should fit in last-level cache (what we call L2 here)
29// and then another subdivision into smaller blocks that should fit in
30// L1 cache. There is then actually a third level of subdivision to fit
31// in registers, but we are not concerned with that here.
32struct BlockParams {
33 // L1 block parameters determine the size of small blocks that should
34 // fit in L1 cache.
35 int l1_rows;
36 int l1_cols;
37 int l1_depth;
38
39 // L2 block parameters determine the size of larger blocks that should
40 // fit in L2 cache.
41 int l2_rows;
42 int l2_cols;
43 int l2_depth;
44
45 template <typename KernelFormat>
46 void Init(int rows, int cols, int depth, int num_threads, int l1_bytes_to_use,
47 int l2_bytes_to_use, float l2_rhs_factor) {
48 FindL2BlockSizes<KernelFormat>(rows, cols, depth, num_threads,
49 l2_bytes_to_use, l2_rhs_factor, &l2_rows,
50 &l2_cols, &l2_depth);
51 FindL1BlockSizes<KernelFormat>(l2_rows, l2_cols, l2_depth, l1_bytes_to_use,
52 &l1_rows, &l1_cols, &l1_depth);
53 }
54
55 template <typename KernelFormat>
56 static void FindL2BlockSizes(int rows, int cols, int depth, int num_threads,
57 int l2_bytes_to_use, float l2_rhs_factor,
58 int* out_l2_rows, int* out_l2_cols,
59 int* out_l2_depth) {
60 int l2_rows = 0;
61 int l2_cols = 0;
62 int l2_depth = 0;
63
64 int per_thread_rows =
65 std::max(1, RoundUp<KernelFormat::kRows>(rows) / num_threads);
66
67 // No L2 blocking in the depth dimension at the moment.
68 // Too much loss of accuracy due to storing intermediate results in
69 // low precision.
70 // However, we still want to round l2_depth up to the next multiple
71 // of register size, so as to avoid having to special-case unaligned depths.
72 l2_depth = RoundUp<kRegisterSize>(depth);
73
74 {
75 int max_cache_friendly_l2_cols = std::max(
76 1, static_cast<int>(l2_rhs_factor * (l2_bytes_to_use / l2_depth)));
77 int min_l2_cols_blocks =
78 std::max(1, CeilQuotient(cols, max_cache_friendly_l2_cols));
79 l2_cols =
80 RoundUp<KernelFormat::kCols>(CeilQuotient(cols, min_l2_cols_blocks));
81 }
82
83 // No L2 blocking in the row dimension if l2_rhs_factor is 1.0 as the row
84 // dimension concerns only the LHS. Blocking only RHS matrix for L2 enhances
85 // the performance on x86.
86 if (l2_rhs_factor == 1.0f) {
87 l2_rows = RoundUp<KernelFormat::kRows>(per_thread_rows);
88 } else {
89 int max_cache_friendly_l2_rows =
90 std::max(1, (l2_bytes_to_use - l2_depth * l2_cols) /
91 (num_threads * (l2_depth + 4 * l2_cols)));
92 int min_l2_rows_blocks = std::max(
93 1, CeilQuotient(per_thread_rows, max_cache_friendly_l2_rows));
94 l2_rows = RoundUp<KernelFormat::kRows>(
95 CeilQuotient(per_thread_rows, min_l2_rows_blocks));
96 }
97
98 *out_l2_rows = l2_rows;
99 *out_l2_cols = l2_cols;
100 *out_l2_depth = l2_depth;
101 }
102
103 template <typename KernelFormat>
104 static void FindL1BlockSizes(int rows, int cols, int depth,
105 int l1_bytes_to_use, int* out_l1_rows,
106 int* out_l1_cols, int* out_l1_depth) {
107 int l1_rows = 0;
108 int l1_cols = 0;
109 int l1_depth = 0;
110
111 // L2 block sizes should already be multiples of kernel block sizes.
112 assert(rows % KernelFormat::kRows == 0);
113 assert(cols % KernelFormat::kCols == 0);
114 assert(depth % KernelFormat::kDepth == 0);
115
116 // No L1 blocking in the columns dimension at the moment.
117 // Thought not to be needed. Similar to Eigen.
118 l1_cols = cols;
119
120 {
121 int max_cache_friendly_l1_depth = std::max(
122 1, (l1_bytes_to_use - 4 * KernelFormat::kRows * KernelFormat::kCols) /
123 (KernelFormat::kRows + KernelFormat::kCols));
124 int min_l1_depth_blocks =
125 std::max(1, CeilQuotient(depth, max_cache_friendly_l1_depth));
126 l1_depth =
127 RoundUp<kRegisterSize>(CeilQuotient(depth, min_l1_depth_blocks));
128 }
129
130 {
131 int max_cache_friendly_l1_rows =
132 std::max(1, l1_bytes_to_use / (l1_depth + 4 * l1_cols));
133 int min_l1_rows_blocks =
134 std::max(1, CeilQuotient(rows, max_cache_friendly_l1_rows));
135 l1_rows =
136 RoundUp<KernelFormat::kRows>(CeilQuotient(rows, min_l1_rows_blocks));
137 }
138
139 *out_l1_rows = l1_rows;
140 *out_l1_cols = l1_cols;
141 *out_l1_depth = l1_depth;
142 }
143};
144
145// A SideBlockParams instance contains only the block params relevant to
146// one side (LHS or RHS), expressed in terms of 'width' instead of
147// rows/colums. See the explanation in kernel.h: in the LHS, 'width' means
148// the number of rows, while in the RHS, 'width' means the number of columns.
149// That allows us to write generic code that applies to either LHS or RHS.
150struct SideBlockParams {
151 // L1 block parameters determine the size of small blocks that should
152 // fit in L1 cache.
153 int l1_width;
154 int l1_depth;
155
156 // L2 block parameters determine the size of larger blocks that should
157 // fit in L2 cache.
158 int l2_width;
159 int l2_depth;
160};
161
162enum class Side { Lhs, Rhs };
163
164inline void GetSideBlockParams(Side side, SideBlockParams* side_block_params,
165 const BlockParams& block_params) {
166 side_block_params->l1_width =
167 side == Side::Lhs ? block_params.l1_rows : block_params.l1_cols;
168 side_block_params->l2_width =
169 side == Side::Lhs ? block_params.l2_rows : block_params.l2_cols;
170
171 side_block_params->l1_depth = block_params.l1_depth;
172 side_block_params->l2_depth = block_params.l2_depth;
173}
174
175} // namespace gemmlowp
176
177#endif // GEMMLOWP_INTERNAL_BLOCK_PARAMS_H_
178