Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
PartialReduxEvaluator.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2011-2018 Gael Guennebaud <gael.guennebaud@inria.fr>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_PARTIALREDUX_H
12#define EIGEN_PARTIALREDUX_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21/***************************************************************************
22 *
23 * This file provides evaluators for partial reductions.
24 * There are two modes:
25 *
26 * - scalar path: simply calls the respective function on the column or row.
27 * -> nothing special here, all the tricky part is handled by the return
28 * types of VectorwiseOp's members. They embed the functor calling the
29 * respective DenseBase's member function.
30 *
31 * - vectorized path: implements a packet-wise reductions followed by
32 * some (optional) processing of the outcome, e.g., division by n for mean.
33 *
34 * For the vectorized path let's observe that the packet-size and outer-unrolling
35 * are both decided by the assignment logic. So all we have to do is to decide
36 * on the inner unrolling.
37 *
38 * For the unrolling, we can reuse "internal::redux_vec_unroller" from Redux.h,
39 * but we need to be careful to specify correct increment.
40 *
41 ***************************************************************************/
42
43/* logic deciding a strategy for unrolling of vectorized paths */
44template <typename Func, typename Evaluator>
45struct packetwise_redux_traits {
46 static constexpr int OuterSize =
47 int(Evaluator::IsRowMajor) ? Evaluator::RowsAtCompileTime : Evaluator::ColsAtCompileTime;
48 static constexpr int Cost = OuterSize == Dynamic
49 ? HugeCost
50 : OuterSize * Evaluator::CoeffReadCost + (OuterSize - 1) * functor_traits<Func>::Cost;
51 // A user-set EIGEN_UNROLLING_LIMIT can reach HugeCost, which therefore does not rule out a runtime size.
52 static constexpr int Unrolling =
53 (OuterSize != Dynamic && Cost <= EIGEN_UNROLLING_LIMIT) ? CompleteUnrolling : NoUnrolling;
54};
55
56/* Value to be returned when size==0 , by default let's return 0 */
57template <typename PacketType, typename Func>
58EIGEN_DEVICE_FUNC PacketType packetwise_redux_empty_value(const Func&) {
59 const typename unpacket_traits<PacketType>::type zero(0);
60 return pset1<PacketType>(zero);
61}
62
63/* For products the default is 1 */
64template <typename PacketType, typename Scalar>
65EIGEN_DEVICE_FUNC PacketType packetwise_redux_empty_value(const scalar_product_op<Scalar, Scalar>&) {
66 return pset1<PacketType>(Scalar(1));
67}
68
69/* Perform the actual reduction */
70template <typename Func, typename Evaluator, int Unrolling = packetwise_redux_traits<Func, Evaluator>::Unrolling>
71struct packetwise_redux_impl;
72
73/* Perform the actual reduction with unrolling */
74template <typename Func, typename Evaluator>
75struct packetwise_redux_impl<Func, Evaluator, CompleteUnrolling> {
76 using Base = redux_novec_unroller<Func, Evaluator, 0, Evaluator::SizeAtCompileTime>;
77 using Scalar = typename Evaluator::Scalar;
78
79 template <typename PacketType>
80 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE PacketType run(const Evaluator& eval, const Func& func, Index /*size*/) {
81 return redux_vec_unroller<Func, Evaluator, 0,
82 packetwise_redux_traits<Func, Evaluator>::OuterSize>::template run<PacketType>(eval,
83 func);
84 }
85};
86
87/* Add a specialization of redux_vec_unroller for size==0 at compiletime.
88 * This specialization is not required for general reductions, which is
89 * why it is defined here.
90 */
91template <typename Func, typename Evaluator, Index Start>
92struct redux_vec_unroller<Func, Evaluator, Start, 0> {
93 template <typename PacketType>
94 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE PacketType run(const Evaluator&, const Func& f) {
95 return packetwise_redux_empty_value<PacketType>(f);
96 }
97};
98
99/* Perform the actual reduction for dynamic sizes */
100template <typename Func, typename Evaluator>
101struct packetwise_redux_impl<Func, Evaluator, NoUnrolling> {
102 using Scalar = typename Evaluator::Scalar;
103 using PacketScalar = typename redux_traits<Func, Evaluator>::PacketType;
104
105 template <typename PacketType>
106 EIGEN_DEVICE_FUNC static PacketType run(const Evaluator& eval, const Func& func, Index size) {
107 if (size == 0) return packetwise_redux_empty_value<PacketType>(func);
108
109 const Index size4 = 1 + numext::round_down(size - 1, 4);
110 PacketType p = eval.template packetByOuterInner<Unaligned, PacketType>(0, 0);
111 // This loop is optimized for instruction pipelining:
112 // - each iteration generates two independent instructions
113 // - thanks to branch prediction and out-of-order execution we have independent instructions across loops
114 for (Index i = 1; i < size4; i += 4)
115 p = func.packetOp(
116 p, func.packetOp(func.packetOp(eval.template packetByOuterInner<Unaligned, PacketType>(i + 0, 0),
117 eval.template packetByOuterInner<Unaligned, PacketType>(i + 1, 0)),
118 func.packetOp(eval.template packetByOuterInner<Unaligned, PacketType>(i + 2, 0),
119 eval.template packetByOuterInner<Unaligned, PacketType>(i + 3, 0))));
120 for (Index i = size4; i < size; ++i)
121 p = func.packetOp(p, eval.template packetByOuterInner<Unaligned, PacketType>(i, 0));
122 return p;
123 }
124};
125
126template <typename Func, typename Evaluator>
127struct packetwise_segment_redux_impl {
128 using Scalar = typename Evaluator::Scalar;
129 using PacketScalar = typename redux_traits<Func, Evaluator>::PacketType;
130
131 template <typename PacketType>
132 EIGEN_DEVICE_FUNC static PacketType run(const Evaluator& eval, const Func& func, Index size, Index begin,
133 Index count) {
134 if (size == 0) return packetwise_redux_empty_value<PacketType>(func);
135
136 const Index size4 = 1 + numext::round_down(size - 1, 4);
137 PacketType p = eval.template packetSegmentByOuterInner<Unaligned, PacketType>(0, 0, begin, count);
138 // Grouping exposes independent packet ops and shortens the dependency chain.
139 for (Index i = 1; i < size4; i += 4)
140 p = func.packetOp(
141 p,
142 func.packetOp(
143 func.packetOp(eval.template packetSegmentByOuterInner<Unaligned, PacketType>(i + 0, 0, begin, count),
144 eval.template packetSegmentByOuterInner<Unaligned, PacketType>(i + 1, 0, begin, count)),
145 func.packetOp(eval.template packetSegmentByOuterInner<Unaligned, PacketType>(i + 2, 0, begin, count),
146 eval.template packetSegmentByOuterInner<Unaligned, PacketType>(i + 3, 0, begin, count))));
147 for (Index i = size4; i < size; ++i)
148 p = func.packetOp(p, eval.template packetSegmentByOuterInner<Unaligned, PacketType>(i, 0, begin, count));
149 return p;
150 }
151};
152
153template <typename ArgType, typename MemberOp, int Direction>
154struct evaluator<PartialReduxExpr<ArgType, MemberOp, Direction> >
155 : evaluator_base<PartialReduxExpr<ArgType, MemberOp, Direction> > {
156 using XprType = PartialReduxExpr<ArgType, MemberOp, Direction>;
157 using ArgTypeNested = typename internal::nested_eval<ArgType, 1>::type;
158 using ConstArgTypeNested = add_const_on_value_type_t<ArgTypeNested>;
159 using ArgTypeNestedCleaned = internal::remove_all_t<ArgTypeNested>;
160 using InputScalar = typename ArgType::Scalar;
161 using Scalar = typename XprType::Scalar;
162 enum {
163 TraversalSize = Direction == int(Vertical) ? int(ArgType::RowsAtCompileTime) : int(ArgType::ColsAtCompileTime)
164 };
165 using CostOpType = typename MemberOp::template Cost<int(TraversalSize)>;
166 enum {
167 CoeffReadCost = TraversalSize == Dynamic ? HugeCost
168 : TraversalSize == 0
169 ? 1
170 : int(TraversalSize) * int(evaluator<ArgType>::CoeffReadCost) + int(CostOpType::value),
171
172 ArgFlags_ = evaluator<ArgType>::Flags,
173
174 Vectorizable_ = bool(int(ArgFlags_) & PacketAccessBit) && bool(MemberOp::Vectorizable) &&
175 (Direction == int(Vertical) ? bool(ArgFlags_ & RowMajorBit) : (ArgFlags_ & RowMajorBit) == 0) &&
176 (TraversalSize != 0),
177
178 Flags = (traits<XprType>::Flags & RowMajorBit) | (evaluator<ArgType>::Flags & (HereditaryBits & (~RowMajorBit))) |
179 (Vectorizable_ ? PacketAccessBit : 0) | LinearAccessBit,
180
181 Alignment = 0 // FIXME this will need to be improved once PartialReduxExpr is vectorized
182 };
183
184 EIGEN_DEVICE_FUNC explicit evaluator(const XprType& xpr) : m_arg(xpr.nestedExpression()), m_functor(xpr.functor()) {
185 EIGEN_INTERNAL_CHECK_COST_VALUE(TraversalSize == Dynamic ? HugeCost
186 : (TraversalSize == 0 ? 1 : int(CostOpType::value)));
187 EIGEN_INTERNAL_CHECK_COST_VALUE(CoeffReadCost);
188 }
189
190 using CoeffReturnType = typename XprType::CoeffReturnType;
191
192 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE const Scalar coeff(Index i, Index j) const {
193 return coeff(Direction == Vertical ? j : i);
194 }
195
196 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE const Scalar coeff(Index index) const {
197 return m_functor(m_arg.template subVector<DirectionType(Direction)>(index));
198 }
199
200 template <int LoadMode, typename PacketType>
201 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE PacketType packet(Index i, Index j) const {
202 return packet<LoadMode, PacketType>(Direction == Vertical ? j : i);
203 }
204
205 template <int LoadMode, typename PacketType>
206 EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC PacketType packet(Index idx) const {
207 static constexpr int PacketSize = internal::unpacket_traits<PacketType>::size;
208 static constexpr int PanelRows = Direction == Vertical ? ArgType::RowsAtCompileTime : PacketSize;
209 static constexpr int PanelCols = Direction == Vertical ? PacketSize : ArgType::ColsAtCompileTime;
210 // Not an InnerPanel: the panel starts at an arbitrary inner index idx, so its outer stride says nothing about the
211 // alignment of its packets.
212 using PanelType = Block<const ArgTypeNestedCleaned, PanelRows, PanelCols, false>;
213 using PanelEvaluator = typename internal::redux_evaluator<PanelType>;
214 using BinaryOp = typename MemberOp::BinaryOp;
215 using Impl = internal::packetwise_redux_impl<BinaryOp, PanelEvaluator>;
216
217 // Workaround for issue 1612 (closed): when PacketSize==1 (i.e. complex<double> with 128bits registers) the
218 // storage-order of panel gets reversed and methods like packetByOuterInner do not make sense in this context, so
219 // bypass "vectorization":
220 EIGEN_IF_CONSTEXPR (PacketSize == 1) return internal::pset1<PacketType>(coeff(idx));
221
222 Index startRow = Direction == Vertical ? 0 : idx;
223 Index startCol = Direction == Vertical ? idx : 0;
224 Index numRows = Direction == Vertical ? m_arg.rows() : PacketSize;
225 Index numCols = Direction == Vertical ? PacketSize : m_arg.cols();
226
227 PanelType panel(m_arg, startRow, startCol, numRows, numCols);
228 PanelEvaluator panel_eval(panel);
229 PacketType p = Impl::template run<PacketType>(panel_eval, m_functor.binaryFunc(), m_arg.outerSize());
230 return p;
231 }
232
233 template <int LoadMode, typename PacketType>
234 EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE PacketType packetSegment(Index i, Index j, Index begin, Index count) const {
235 return packetSegment<LoadMode, PacketType>(Direction == Vertical ? j : i, begin, count);
236 }
237
238 template <int LoadMode, typename PacketType>
239 EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC PacketType packetSegment(Index idx, Index begin, Index count) const {
240 static constexpr int PanelRows = Direction == Vertical ? ArgType::RowsAtCompileTime : Dynamic;
241 static constexpr int PanelCols = Direction == Vertical ? Dynamic : ArgType::ColsAtCompileTime;
242 using PanelType = Block<const ArgTypeNestedCleaned, PanelRows, PanelCols, false>;
243 using PanelEvaluator = typename internal::redux_evaluator<PanelType>;
244 using BinaryOp = typename MemberOp::BinaryOp;
245 using Impl = internal::packetwise_segment_redux_impl<BinaryOp, PanelEvaluator>;
246
247 Index startRow = Direction == Vertical ? 0 : idx;
248 Index startCol = Direction == Vertical ? idx : 0;
249 Index numRows = Direction == Vertical ? m_arg.rows() : begin + count;
250 Index numCols = Direction == Vertical ? begin + count : m_arg.cols();
251
252 PanelType panel(m_arg, startRow, startCol, numRows, numCols);
253 PanelEvaluator panel_eval(panel);
254 PacketType p = Impl::template run<PacketType>(panel_eval, m_functor.binaryFunc(), m_arg.outerSize(), begin, count);
255 return p;
256 }
257
258 protected:
259 ConstArgTypeNested m_arg;
260 const MemberOp m_functor;
261};
262
263} // end namespace internal
264
265} // end namespace Eigen
266
267#endif // EIGEN_PARTIALREDUX_H
DirectionType
Definition Constants.h:264
@ Vertical
Definition Constants.h:267
constexpr unsigned int PacketAccessBit
Definition Constants.h:98
constexpr unsigned int LinearAccessBit
Definition Constants.h:134
constexpr unsigned int RowMajorBit
Definition Constants.h:71