You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tvm.apache.org by GitBox <gi...@apache.org> on 2021/11/05 11:00:23 UTC
[GitHub] [tvm] mbaret opened a new pull request #9458: [ETHOSU][1] Add affine analysis structures for the cascader
mbaret opened a new pull request #9458:
URL: https://github.com/apache/tvm/pull/9458
RFC: https://github.com/apache/tvm-rfcs/pull/37
Issue: https://github.com/apache/tvm/issues/9429
The cascader relies heavily on being able to determine data dependencies between operators. This is so that it can calculate how stripes should be propagated through a cascade.
To do this, two data structures are defined: StripeConfig and Propagator. StripeConfig stores information for how a tensor should be broken up into stripes and executed. Propagator transforms a StripeConfig using an affine transform matrix, allowing an input StripeConfig for an operator to be determined by 'propagating' the output StripeConfig.
By chaining together Propagators, we can analyse how data dependencies vary throughout a cascade and therefore calculate the memory requirements (and approximate the performance).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] mbaret commented on pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
mbaret commented on pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#issuecomment-964243973
> minor note: not needed for now, but it may be helpful to take a look at https://github.com/apache/tvm/blob/main/include/tvm/arith/iter_affine_map.h to see if there is any utils that can be reused
I did spend a little bit of time looking at this after @junrushao1994 made me aware of it. It looks like it'd make for a good integration point for a 'v2' - especially once we upgrade to TensorIR. However, I think there are a few representational issues that would make it hard to directly leverage in the current design.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] mbaret commented on pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
mbaret commented on pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#issuecomment-964230676
also cc @csullivan
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] leandron commented on pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
leandron commented on pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#issuecomment-983617401
This is merged now, thanks @csullivan @mbaret @NicolaLancellotti @manupa-arm and @tqchen.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] mbaret commented on pull request #9458: [ETHOSU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
mbaret commented on pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#issuecomment-961801637
cc @mbs-octoml @junrushao1994 @jacobbohlin @manupa-arm @NicolaLancellotti
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] mbaret commented on pull request #9458: [ETHOSU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
mbaret commented on pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#issuecomment-961801637
cc @mbs-octoml @junrushao1994 @jacobbohlin @manupa-arm @NicolaLancellotti
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] mbaret commented on a change in pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
mbaret commented on a change in pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#discussion_r756737847
##########
File path: src/contrib/ethosu/cascader/stripe_config.h
##########
@@ -0,0 +1,218 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file src/contrib/ethosu/cascader/stripe_config.h
+ * \brief StripeConfig object for the NPU cascader
+ */
+#ifndef TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+#define TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+
+#include <tvm/node/reflection.h>
+#include <tvm/runtime/object.h>
+
+#include <functional>
+#include <map>
+#include <vector>
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+class StripeConfig;
+class PropagatorNode;
+
+/*! \brief Node to represent a StripeConfig */
+class StripeConfigNode : public Object {
+ public:
+ void VisitAttrs(AttrVisitor* v);
+
+ /*!
+ * \brief Get the shape of the stripe config.
+ * \return The shape of the stripe config.
+ * \note The shape refers to the size of the stripes in each dimension.
+ */
+ inline std::vector<int> GetShape() const { return shape_; }
+ /*!
+ * \brief Get the extent of the stripe config.
+ * \return The extent of the stripe config.
+ * \note The extent refers to the extent over which a StripeConfig operates.
+ * Specifically, it is the extent in each axis between the lowest value read
+ * by a stripe and the highest value read by a stripe.
+ */
+ inline std::vector<int> GetExtent() const { return extent_; }
+ /*!
+ * \brief Get the strides of the stripe config.
+ * \return The strides of the stripe config.
+ * \note The strides refer to the stride between stripes in each axis.
+ * The strides are represented as a float rather than an int to account for
+ * cases of 'fractional striding'. This may happen, for instance, with an
+ * upscaling operation where elements of the affine transformation matrix
+ * are not integers. In this case we can't simply round the strides as the
+ * error will compound when we need to multiply the strides by the number of
+ * stripes along a given axis.
+ */
+ inline std::vector<float> GetStrides() const { return strides_; }
+ /*!
+ * \brief Get the order of the stripe config.
+ * \return The order of the stripe config.
+ * \note The order refers to order in which the axes are iterated over.
+ * The first (outermost) axis is labelled as 1 with the rest increasing
+ * according to the axis' position. Any axis labelled with 0 isn't iterated over.
+ * For example, [1, 3, 2] would mean axis 0 is the outermost iteration axis,
+ * then axis 2, then finally axis 1.
+ */
+ inline std::vector<int> GetOrder() const { return order_; }
+ /*!
+ * \brief Get the stripes of the stripe config.
+ * \return The stripes of the stripe config.
+ * \note The stripes refer to the number of stripes in each axis.
+ * There must be at least one stripe in any given axis.
+ */
+ inline std::vector<int> GetStripes() const { return stripes_; }
+ /*!
+ * \brief Get the offset of the stripe config.
+ * \return The offset of the stripe config.
+ * \note The offset refers to the offset of the first stripe
+ * from the first element of the tensor. For example, in a 2D padding operation
+ * that is padding by 1 in every dimension, the offset would be [-1, -1].
+ */
+ inline std::vector<int> GetOffset() const { return offset_; }
+ /*! \return The hash of the StripeConfigNode */
+ size_t GetHash() const { return hash_; }
+
+ static constexpr const char* _type_key = "contrib.ethosu.cascader.StripeConfig";
+ TVM_DECLARE_FINAL_OBJECT_INFO(StripeConfigNode, Object);
+
+ protected:
+ friend class StripeConfig;
+ friend class PropagatorNode;
+
+ /*! \brief Compute the hash of the StripeConfigNode */
+ void ComputeHash_();
+
+ /*! \brief The shape of the stripes */
+ std::vector<int> shape_;
+ /*! \brief The extent of region to stripe over */
+ std::vector<int> extent_;
+ /*! \brief The strides of the stripes */
+ std::vector<float> strides_;
+ /*! \brief The order of the striping axes */
+ std::vector<int> order_;
+ /*! \brief The number of stripes in each axis */
+ std::vector<int> stripes_;
+ /*! \brief The offset of the first stripe */
+ std::vector<int> offset_;
+ /*! \brief The hash of the StripeConfigNode */
+ std::size_t hash_{0};
+};
+
+/*!
+ * \brief An object to describe how a tensor should be computed as a series
+ of n-dimensional tiles, or 'stripes'.
+ * \note The StripeConfig is a verbose way of specifying how to tile a tensor.
+ * We can imagine taking a 2D tensor of size (12, 12) and wanting to compute
+ * it in tiles of (4, 4). The tile is referred to as a stripe here to generalize
+ * this to n-dimensional tiles.
+ *
+ * The size of that stripe in each axis is the 'shape'. The strides is how far
+ * you should move between stripes, so also (4, 4) for a simple non-overlappping
+ * tiling. However, we explore some overlapping scheduling options so shape != strides
Review comment:
I've added an example based on 2x2 upscale.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] leandron merged pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
leandron merged pull request #9458:
URL: https://github.com/apache/tvm/pull/9458
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] tqchen commented on pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#issuecomment-964233802
minor note: not needed for now, but it may be helpful to take a look at https://github.com/apache/tvm/blob/main/include/tvm/arith/iter_affine_map.h to see if there is any utils that can be reused
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] NicolaLancellotti commented on a change in pull request #9458: [ETHOSU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
NicolaLancellotti commented on a change in pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#discussion_r743835952
##########
File path: src/contrib/ethosu/cascader/propagator.cc
##########
@@ -0,0 +1,132 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+#include "propagator.h"
+
+#include <tvm/relay/expr.h>
+#include <tvm/runtime/container/array.h>
+#include <tvm/runtime/object.h>
+
+#include <utility>
+#include <vector>
+
+#include "common.h"
+#include "stripe_config.h"
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+void PropagatorNode::VisitAttrs(AttrVisitor* v) {
+ Array<Array<FloatImm> > tmp_transform;
+ for (const auto& vec : transform_) {
+ tmp_transform.push_back(make_array(vec));
+ }
+ v->Visit("_transform", &tmp_transform);
+ Array<Integer> tmp_arr = make_array(offset_);
+ v->Visit("_offset", &tmp_arr);
+}
+
+Propagator::Propagator(const std::vector<std::vector<float> >& transform,
+ const std::vector<int>& offset) {
+ auto n = make_object<PropagatorNode>();
+ size_t rows = transform.size();
+ ICHECK_GT(rows, 0) << "The transform matrix must have at least 1 row.";
+ size_t columns = transform[0].size();
+ for (const auto& row : transform) {
+ ICHECK_EQ(row.size(), columns)
+ << "All rows of the transform matrix must be of the same length.";
+ }
+ ICHECK_EQ(offset.size(), rows - 1)
+ << "The offset vector length must be equal to the transform matrix rows - 1.";
+ n->transform_ = std::move(transform);
+ n->offset_ = std::move(offset);
+ data_ = std::move(n);
+}
+
+StripeConfig PropagatorNode::propagate(const StripeConfig& stripe_config) const {
+ size_t input_dimensions = transform_[0].size() - 1;
+ size_t output_dimensions = transform_.size() - 1;
+ auto n = make_object<StripeConfigNode>();
+ n->shape_.resize(output_dimensions);
+ n->extent_.resize(output_dimensions);
+ n->strides_.resize(output_dimensions);
+ n->order_.resize(output_dimensions);
+ n->stripes_.resize(output_dimensions);
+ n->offset_.resize(output_dimensions);
+ for (size_t i = 0; i < output_dimensions; i++) {
+ float new_shape_acc{};
+ float new_extent_acc{};
+ const float* row = &transform_[i][0];
+ for (size_t j = 0; j < input_dimensions; j++) {
+ new_shape_acc += row[j] * stripe_config->shape_[j];
+ new_extent_acc += row[j] * stripe_config->extent_[j];
+ n->strides_[i] += row[j] * stripe_config->strides_[j];
+ // Order, stripes and offset should only get re-ordered, so we only
+ // care about whether or not transform elements are non-zero.
+ int non_zero = row[j] != 0;
+ n->order_[i] += non_zero * stripe_config->order_[j];
+ n->stripes_[i] += non_zero * stripe_config->stripes_[j];
+ n->offset_[i] += non_zero * stripe_config->offset_[j];
+ }
+ // Shape and extent gain an additional constant term
+ new_shape_acc += row[input_dimensions];
+ new_extent_acc += row[input_dimensions];
+ // Shape and extent are ceil-rounded back to integers
+ n->shape_[i] = std::ceil(new_shape_acc);
+ n->extent_[i] += std::ceil(new_extent_acc);
+ // Apply the offset
+ n->offset_[i] += offset_[i];
+ // No axis can have '0 stripes', so change all 0 elements to 1
+ n->stripes_[i] = n->stripes_[i] == 0 ? 1 : n->stripes_[i];
+ }
+ // Remember to compute the hash
+ n->ComputeHash_();
+ return StripeConfig(n);
+}
+
+TVM_REGISTER_GLOBAL("contrib.ethosu.cascader.Propagator")
+ .set_body_typed([](Array<Array<FloatImm> > transform, Array<Integer> offset) {
+ std::vector<std::vector<float> > vtransform;
+ for (const auto& vec : transform) {
+ vtransform.push_back(make_vector<float, FloatImm>(vec));
+ }
+ std::vector<int> voffset = make_vector<int, Integer>(offset);
+ return Propagator(vtransform, voffset);
+ });
+
+TVM_REGISTER_GLOBAL("contrib.ethosu.cascader.PropagatorPropagate")
+ .set_body_typed([](Propagator propagator, StripeConfig stripe_config) {
+ return propagator->propagate(stripe_config);
+ });
+
+TVM_REGISTER_GLOBAL("contrib.ethosu.cascader.PropagatorPropagateBenchmark")
+ .set_body_typed([](Propagator propagator, StripeConfig stripe_config, int repeats) {
+ for (int i = 0; i < repeats; i++) {
+ propagator->propagate(stripe_config);
+ }
+ return propagator->propagate(stripe_config);
+ });
Review comment:
This is not used, isn't it?
##########
File path: src/contrib/ethosu/cascader/stripe_config.h
##########
@@ -0,0 +1,202 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file src/contrib/ethosu/cascader/stripe_config.h
+ * \brief StripeConfig object for the NPU cascader
+ */
+#ifndef TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+#define TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+
+#include <tvm/node/reflection.h>
+#include <tvm/runtime/object.h>
+
+#include <functional>
+#include <map>
+#include <vector>
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+class StripeConfig;
+class PropagatorNode;
+
+/*! \brief Node to represent a StripeConfig */
+class StripeConfigNode : public Object {
+ public:
+ void VisitAttrs(AttrVisitor* v);
+
+ /*!
+ * \brief Get the shape of the stripe config.
+ * \return The shape of the stripe config.
+ * \note The shape refers to the size of the stripes in each dimension.
+ */
+ inline std::vector<int> GetShape() const { return shape_; }
+ /*!
+ * \brief Get the extent of the stripe config.
+ * \return The extent of the stripe config.
+ * \note The extent refers to the extent over which a StripeConfig operates.
+ * Specifically, it is the extent in each axis between the lowest value read
+ * by a stripe and the highest value read by a stripe.
+ */
+ inline std::vector<int> GetExtent() const { return extent_; }
+ /*!
+ * \brief Get the strides of the stripe config.
+ * \return The strides of the stripe config.
+ * \note The strides refer to the stride between stripes in each axis.
+ * The strides are represented as a float rather than an int to account for
+ * cases of 'fractional striding'. This may happen, for instance, with an
+ * upscaling operation where elements of the affine transformation matrix
+ * are not integers. In this case we can't simply round the strides as the
+ * error will compound when we need to multiply the strides by the number of
+ * stripes along a given axis.
+ */
+ inline std::vector<float> GetStrides() const { return strides_; }
+ /*!
+ * \brief Get the order of the stripe config.
+ * \return The order of the stripe config.
+ * \note The order refers to order in which the axes are iterated over.
+ * The first (outermost) axis is labelled as 1 with the rest increasing
+ * according to the axis' position. Any axis labelled with 0 isn't iterated over.
+ * For example, [1, 3, 2] would mean axis 0 is the outermost iteration axis,
+ * then axis 2, then finally axis 1.
+ */
+ inline std::vector<int> GetOrder() const { return order_; }
+ /*!
+ * \brief Get the stripes of the stripe config.
+ * \return The stripes of the stripe config.
+ * \note The stripes refer to the number of stripes in each axis.
+ * There must be at least one stripe in any given axis.
+ */
+ inline std::vector<int> GetStripes() const { return stripes_; }
+ /*!
+ * \brief Get the offset of the stripe config.
+ * \return The offset of the stripe config.
+ * \note The offset refers to the offset of the first stripe
+ * from the first element of the tensor. For example, in a 2D padding operation
+ * that is padding by 1 in every dimension, the offset would be [-1, -1].
+ */
+ inline std::vector<int> GetOffset() const { return offset_; }
+ /*! \return The hash of the StripeConfigNode */
+ size_t GetHash() const { return hash_; }
+
+ static constexpr const char* _type_key = "contrib.ethosu.cascader.StripeConfig";
+ TVM_DECLARE_FINAL_OBJECT_INFO(StripeConfigNode, Object);
+
+ protected:
+ friend class StripeConfig;
+ friend class PropagatorNode;
+
+ /*! \brief Compute the hash of the StripeConfigNode */
+ void ComputeHash_();
+
+ /*! \brief The shape of the stripes */
+ std::vector<int> shape_;
+ /*! \brief The extent of region to stripe over */
+ std::vector<int> extent_;
+ /*! \brief The strides of the stripes */
+ std::vector<float> strides_;
+ /*! \brief The order of the striping axes */
+ std::vector<int> order_;
+ /*! \brief The number of stripes in each axis */
+ std::vector<int> stripes_;
+ /*! \brief The offset of the first stripe */
+ std::vector<int> offset_;
+ /*! \brief The hash of the StripeConfigNode */
+ std::size_t hash_{0};
+};
+
+/*!
+ * \brief An object to describe how a tensor should be computed as a series
+ of n-dimensional tiles, or 'stripes'.
+ * \note The StripeConfig is a verbose way of specifying how to tile a tensor.
+ * We can imagine taking a 2D tensor of size (12, 12) and wanting to compute
+ * it in tiles of (4, 4). The tile is referred to as a stripe here to generalize
+ * this to n-dimensional tiles.
+ *
+ * The size of that stripe in each axis is the 'shape'. The strides is how far
+ * you should move between stripes, so also (4, 4) for a simple non-overlappping
+ * tiling. However, we explore some overlapping scheduling options so shape != strides
+ * in general. The 'extent' is simply (12, 12), the region over which we're conducting
+ * our tiling.
+ *
+ * The 'order' tells us which axis to iterate over first and which second and the
+ * 'stripes' tells us how many stripes we need to compute in each of those axes.
+ *
+ * Finally, the 'offset' tells us where to start the first stripe. In this simple
+ * case the offset is just (0, 0), but in something like a padding operation we
+ * may want to start from a negative index, which is captured by the offset.
+ */
+class StripeConfig : public ObjectRef {
+ public:
+ StripeConfig(const std::vector<int>& shape, const std::vector<int>& extent,
+ const std::vector<float>& strides, const std::vector<int>& order,
+ const std::vector<int>& stripes, const std::vector<int>& offset);
+ /*!
+ * \brief Check if two StripeConfigs are equals to each other.
+ * \param other StripeConfig to be checked.
+ * \return Whether the two StripeConfigs equal each other.
+ */
+ bool operator==(const StripeConfig& other) const;
+
+ TVM_DEFINE_OBJECT_REF_METHODS(StripeConfig, ObjectRef, StripeConfigNode);
+};
+
+/*!
+ * \brief Count the number of stripes of each shape that are executed for a given
+ StripeConfig.
+ * \param stripe_config The StripeConfig to count the stripes for.
+ * \param enable_sliding_window Whether to assume the sliding window optimization.
+ * \return A map between stripe shapes and the number of stripes of that shape that need
+ * executing.
+ */
Review comment:
Can you improve the documentation to make it cleaner?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] mbaret commented on a change in pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
mbaret commented on a change in pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#discussion_r756737741
##########
File path: src/contrib/ethosu/cascader/stripe_config.h
##########
@@ -0,0 +1,218 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file src/contrib/ethosu/cascader/stripe_config.h
+ * \brief StripeConfig object for the NPU cascader
+ */
+#ifndef TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+#define TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+
+#include <tvm/node/reflection.h>
+#include <tvm/runtime/object.h>
+
+#include <functional>
+#include <map>
+#include <vector>
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+class StripeConfig;
+class PropagatorNode;
+
+/*! \brief Node to represent a StripeConfig */
+class StripeConfigNode : public Object {
+ public:
+ void VisitAttrs(AttrVisitor* v);
+
+ /*!
+ * \brief Get the shape of the stripe config.
+ * \return The shape of the stripe config.
+ * \note The shape refers to the size of the stripes in each dimension.
+ */
+ inline std::vector<int> GetShape() const { return shape_; }
+ /*!
+ * \brief Get the extent of the stripe config.
+ * \return The extent of the stripe config.
+ * \note The extent refers to the extent over which a StripeConfig operates.
+ * Specifically, it is the extent in each axis between the lowest value read
+ * by a stripe and the highest value read by a stripe.
+ */
+ inline std::vector<int> GetExtent() const { return extent_; }
+ /*!
+ * \brief Get the strides of the stripe config.
+ * \return The strides of the stripe config.
+ * \note The strides refer to the stride between stripes in each axis.
+ * The strides are represented as a float rather than an int to account for
+ * cases of 'fractional striding'. This may happen, for instance, with an
+ * upscaling operation where elements of the affine transformation matrix
+ * are not integers. In this case we can't simply round the strides as the
+ * error will compound when we need to multiply the strides by the number of
+ * stripes along a given axis.
+ */
+ inline std::vector<float> GetStrides() const { return strides_; }
Review comment:
The best example of this is an upscale operation. If we have a 2x2 upscale and choose to stripe the output in 3x3 stripes, the input stripes will get a fractional stride of 3/2. We can't just ceil round this, otherwise as we increase the striding it'll get further and further from the truth. I'll add this to the docs.
Side note: I have considered re-expressing this as a rational number rather than a float, but I think that can be a future improvement for now.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] mbaret commented on pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
mbaret commented on pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#issuecomment-982842745
ping @csullivan
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] NicolaLancellotti commented on a change in pull request #9458: [ETHOSU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
NicolaLancellotti commented on a change in pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#discussion_r743835952
##########
File path: src/contrib/ethosu/cascader/propagator.cc
##########
@@ -0,0 +1,132 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+#include "propagator.h"
+
+#include <tvm/relay/expr.h>
+#include <tvm/runtime/container/array.h>
+#include <tvm/runtime/object.h>
+
+#include <utility>
+#include <vector>
+
+#include "common.h"
+#include "stripe_config.h"
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+void PropagatorNode::VisitAttrs(AttrVisitor* v) {
+ Array<Array<FloatImm> > tmp_transform;
+ for (const auto& vec : transform_) {
+ tmp_transform.push_back(make_array(vec));
+ }
+ v->Visit("_transform", &tmp_transform);
+ Array<Integer> tmp_arr = make_array(offset_);
+ v->Visit("_offset", &tmp_arr);
+}
+
+Propagator::Propagator(const std::vector<std::vector<float> >& transform,
+ const std::vector<int>& offset) {
+ auto n = make_object<PropagatorNode>();
+ size_t rows = transform.size();
+ ICHECK_GT(rows, 0) << "The transform matrix must have at least 1 row.";
+ size_t columns = transform[0].size();
+ for (const auto& row : transform) {
+ ICHECK_EQ(row.size(), columns)
+ << "All rows of the transform matrix must be of the same length.";
+ }
+ ICHECK_EQ(offset.size(), rows - 1)
+ << "The offset vector length must be equal to the transform matrix rows - 1.";
+ n->transform_ = std::move(transform);
+ n->offset_ = std::move(offset);
+ data_ = std::move(n);
+}
+
+StripeConfig PropagatorNode::propagate(const StripeConfig& stripe_config) const {
+ size_t input_dimensions = transform_[0].size() - 1;
+ size_t output_dimensions = transform_.size() - 1;
+ auto n = make_object<StripeConfigNode>();
+ n->shape_.resize(output_dimensions);
+ n->extent_.resize(output_dimensions);
+ n->strides_.resize(output_dimensions);
+ n->order_.resize(output_dimensions);
+ n->stripes_.resize(output_dimensions);
+ n->offset_.resize(output_dimensions);
+ for (size_t i = 0; i < output_dimensions; i++) {
+ float new_shape_acc{};
+ float new_extent_acc{};
+ const float* row = &transform_[i][0];
+ for (size_t j = 0; j < input_dimensions; j++) {
+ new_shape_acc += row[j] * stripe_config->shape_[j];
+ new_extent_acc += row[j] * stripe_config->extent_[j];
+ n->strides_[i] += row[j] * stripe_config->strides_[j];
+ // Order, stripes and offset should only get re-ordered, so we only
+ // care about whether or not transform elements are non-zero.
+ int non_zero = row[j] != 0;
+ n->order_[i] += non_zero * stripe_config->order_[j];
+ n->stripes_[i] += non_zero * stripe_config->stripes_[j];
+ n->offset_[i] += non_zero * stripe_config->offset_[j];
+ }
+ // Shape and extent gain an additional constant term
+ new_shape_acc += row[input_dimensions];
+ new_extent_acc += row[input_dimensions];
+ // Shape and extent are ceil-rounded back to integers
+ n->shape_[i] = std::ceil(new_shape_acc);
+ n->extent_[i] += std::ceil(new_extent_acc);
+ // Apply the offset
+ n->offset_[i] += offset_[i];
+ // No axis can have '0 stripes', so change all 0 elements to 1
+ n->stripes_[i] = n->stripes_[i] == 0 ? 1 : n->stripes_[i];
+ }
+ // Remember to compute the hash
+ n->ComputeHash_();
+ return StripeConfig(n);
+}
+
+TVM_REGISTER_GLOBAL("contrib.ethosu.cascader.Propagator")
+ .set_body_typed([](Array<Array<FloatImm> > transform, Array<Integer> offset) {
+ std::vector<std::vector<float> > vtransform;
+ for (const auto& vec : transform) {
+ vtransform.push_back(make_vector<float, FloatImm>(vec));
+ }
+ std::vector<int> voffset = make_vector<int, Integer>(offset);
+ return Propagator(vtransform, voffset);
+ });
+
+TVM_REGISTER_GLOBAL("contrib.ethosu.cascader.PropagatorPropagate")
+ .set_body_typed([](Propagator propagator, StripeConfig stripe_config) {
+ return propagator->propagate(stripe_config);
+ });
+
+TVM_REGISTER_GLOBAL("contrib.ethosu.cascader.PropagatorPropagateBenchmark")
+ .set_body_typed([](Propagator propagator, StripeConfig stripe_config, int repeats) {
+ for (int i = 0; i < repeats; i++) {
+ propagator->propagate(stripe_config);
+ }
+ return propagator->propagate(stripe_config);
+ });
Review comment:
This is not used, isn't it?
##########
File path: src/contrib/ethosu/cascader/stripe_config.h
##########
@@ -0,0 +1,202 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file src/contrib/ethosu/cascader/stripe_config.h
+ * \brief StripeConfig object for the NPU cascader
+ */
+#ifndef TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+#define TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+
+#include <tvm/node/reflection.h>
+#include <tvm/runtime/object.h>
+
+#include <functional>
+#include <map>
+#include <vector>
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+class StripeConfig;
+class PropagatorNode;
+
+/*! \brief Node to represent a StripeConfig */
+class StripeConfigNode : public Object {
+ public:
+ void VisitAttrs(AttrVisitor* v);
+
+ /*!
+ * \brief Get the shape of the stripe config.
+ * \return The shape of the stripe config.
+ * \note The shape refers to the size of the stripes in each dimension.
+ */
+ inline std::vector<int> GetShape() const { return shape_; }
+ /*!
+ * \brief Get the extent of the stripe config.
+ * \return The extent of the stripe config.
+ * \note The extent refers to the extent over which a StripeConfig operates.
+ * Specifically, it is the extent in each axis between the lowest value read
+ * by a stripe and the highest value read by a stripe.
+ */
+ inline std::vector<int> GetExtent() const { return extent_; }
+ /*!
+ * \brief Get the strides of the stripe config.
+ * \return The strides of the stripe config.
+ * \note The strides refer to the stride between stripes in each axis.
+ * The strides are represented as a float rather than an int to account for
+ * cases of 'fractional striding'. This may happen, for instance, with an
+ * upscaling operation where elements of the affine transformation matrix
+ * are not integers. In this case we can't simply round the strides as the
+ * error will compound when we need to multiply the strides by the number of
+ * stripes along a given axis.
+ */
+ inline std::vector<float> GetStrides() const { return strides_; }
+ /*!
+ * \brief Get the order of the stripe config.
+ * \return The order of the stripe config.
+ * \note The order refers to order in which the axes are iterated over.
+ * The first (outermost) axis is labelled as 1 with the rest increasing
+ * according to the axis' position. Any axis labelled with 0 isn't iterated over.
+ * For example, [1, 3, 2] would mean axis 0 is the outermost iteration axis,
+ * then axis 2, then finally axis 1.
+ */
+ inline std::vector<int> GetOrder() const { return order_; }
+ /*!
+ * \brief Get the stripes of the stripe config.
+ * \return The stripes of the stripe config.
+ * \note The stripes refer to the number of stripes in each axis.
+ * There must be at least one stripe in any given axis.
+ */
+ inline std::vector<int> GetStripes() const { return stripes_; }
+ /*!
+ * \brief Get the offset of the stripe config.
+ * \return The offset of the stripe config.
+ * \note The offset refers to the offset of the first stripe
+ * from the first element of the tensor. For example, in a 2D padding operation
+ * that is padding by 1 in every dimension, the offset would be [-1, -1].
+ */
+ inline std::vector<int> GetOffset() const { return offset_; }
+ /*! \return The hash of the StripeConfigNode */
+ size_t GetHash() const { return hash_; }
+
+ static constexpr const char* _type_key = "contrib.ethosu.cascader.StripeConfig";
+ TVM_DECLARE_FINAL_OBJECT_INFO(StripeConfigNode, Object);
+
+ protected:
+ friend class StripeConfig;
+ friend class PropagatorNode;
+
+ /*! \brief Compute the hash of the StripeConfigNode */
+ void ComputeHash_();
+
+ /*! \brief The shape of the stripes */
+ std::vector<int> shape_;
+ /*! \brief The extent of region to stripe over */
+ std::vector<int> extent_;
+ /*! \brief The strides of the stripes */
+ std::vector<float> strides_;
+ /*! \brief The order of the striping axes */
+ std::vector<int> order_;
+ /*! \brief The number of stripes in each axis */
+ std::vector<int> stripes_;
+ /*! \brief The offset of the first stripe */
+ std::vector<int> offset_;
+ /*! \brief The hash of the StripeConfigNode */
+ std::size_t hash_{0};
+};
+
+/*!
+ * \brief An object to describe how a tensor should be computed as a series
+ of n-dimensional tiles, or 'stripes'.
+ * \note The StripeConfig is a verbose way of specifying how to tile a tensor.
+ * We can imagine taking a 2D tensor of size (12, 12) and wanting to compute
+ * it in tiles of (4, 4). The tile is referred to as a stripe here to generalize
+ * this to n-dimensional tiles.
+ *
+ * The size of that stripe in each axis is the 'shape'. The strides is how far
+ * you should move between stripes, so also (4, 4) for a simple non-overlappping
+ * tiling. However, we explore some overlapping scheduling options so shape != strides
+ * in general. The 'extent' is simply (12, 12), the region over which we're conducting
+ * our tiling.
+ *
+ * The 'order' tells us which axis to iterate over first and which second and the
+ * 'stripes' tells us how many stripes we need to compute in each of those axes.
+ *
+ * Finally, the 'offset' tells us where to start the first stripe. In this simple
+ * case the offset is just (0, 0), but in something like a padding operation we
+ * may want to start from a negative index, which is captured by the offset.
+ */
+class StripeConfig : public ObjectRef {
+ public:
+ StripeConfig(const std::vector<int>& shape, const std::vector<int>& extent,
+ const std::vector<float>& strides, const std::vector<int>& order,
+ const std::vector<int>& stripes, const std::vector<int>& offset);
+ /*!
+ * \brief Check if two StripeConfigs are equals to each other.
+ * \param other StripeConfig to be checked.
+ * \return Whether the two StripeConfigs equal each other.
+ */
+ bool operator==(const StripeConfig& other) const;
+
+ TVM_DEFINE_OBJECT_REF_METHODS(StripeConfig, ObjectRef, StripeConfigNode);
+};
+
+/*!
+ * \brief Count the number of stripes of each shape that are executed for a given
+ StripeConfig.
+ * \param stripe_config The StripeConfig to count the stripes for.
+ * \param enable_sliding_window Whether to assume the sliding window optimization.
+ * \return A map between stripe shapes and the number of stripes of that shape that need
+ * executing.
+ */
Review comment:
Can you improve the documentation to make it cleaner?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] NicolaLancellotti commented on a change in pull request #9458: [ETHOSU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
NicolaLancellotti commented on a change in pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#discussion_r743835952
##########
File path: src/contrib/ethosu/cascader/propagator.cc
##########
@@ -0,0 +1,132 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+#include "propagator.h"
+
+#include <tvm/relay/expr.h>
+#include <tvm/runtime/container/array.h>
+#include <tvm/runtime/object.h>
+
+#include <utility>
+#include <vector>
+
+#include "common.h"
+#include "stripe_config.h"
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+void PropagatorNode::VisitAttrs(AttrVisitor* v) {
+ Array<Array<FloatImm> > tmp_transform;
+ for (const auto& vec : transform_) {
+ tmp_transform.push_back(make_array(vec));
+ }
+ v->Visit("_transform", &tmp_transform);
+ Array<Integer> tmp_arr = make_array(offset_);
+ v->Visit("_offset", &tmp_arr);
+}
+
+Propagator::Propagator(const std::vector<std::vector<float> >& transform,
+ const std::vector<int>& offset) {
+ auto n = make_object<PropagatorNode>();
+ size_t rows = transform.size();
+ ICHECK_GT(rows, 0) << "The transform matrix must have at least 1 row.";
+ size_t columns = transform[0].size();
+ for (const auto& row : transform) {
+ ICHECK_EQ(row.size(), columns)
+ << "All rows of the transform matrix must be of the same length.";
+ }
+ ICHECK_EQ(offset.size(), rows - 1)
+ << "The offset vector length must be equal to the transform matrix rows - 1.";
+ n->transform_ = std::move(transform);
+ n->offset_ = std::move(offset);
+ data_ = std::move(n);
+}
+
+StripeConfig PropagatorNode::propagate(const StripeConfig& stripe_config) const {
+ size_t input_dimensions = transform_[0].size() - 1;
+ size_t output_dimensions = transform_.size() - 1;
+ auto n = make_object<StripeConfigNode>();
+ n->shape_.resize(output_dimensions);
+ n->extent_.resize(output_dimensions);
+ n->strides_.resize(output_dimensions);
+ n->order_.resize(output_dimensions);
+ n->stripes_.resize(output_dimensions);
+ n->offset_.resize(output_dimensions);
+ for (size_t i = 0; i < output_dimensions; i++) {
+ float new_shape_acc{};
+ float new_extent_acc{};
+ const float* row = &transform_[i][0];
+ for (size_t j = 0; j < input_dimensions; j++) {
+ new_shape_acc += row[j] * stripe_config->shape_[j];
+ new_extent_acc += row[j] * stripe_config->extent_[j];
+ n->strides_[i] += row[j] * stripe_config->strides_[j];
+ // Order, stripes and offset should only get re-ordered, so we only
+ // care about whether or not transform elements are non-zero.
+ int non_zero = row[j] != 0;
+ n->order_[i] += non_zero * stripe_config->order_[j];
+ n->stripes_[i] += non_zero * stripe_config->stripes_[j];
+ n->offset_[i] += non_zero * stripe_config->offset_[j];
+ }
+ // Shape and extent gain an additional constant term
+ new_shape_acc += row[input_dimensions];
+ new_extent_acc += row[input_dimensions];
+ // Shape and extent are ceil-rounded back to integers
+ n->shape_[i] = std::ceil(new_shape_acc);
+ n->extent_[i] += std::ceil(new_extent_acc);
+ // Apply the offset
+ n->offset_[i] += offset_[i];
+ // No axis can have '0 stripes', so change all 0 elements to 1
+ n->stripes_[i] = n->stripes_[i] == 0 ? 1 : n->stripes_[i];
+ }
+ // Remember to compute the hash
+ n->ComputeHash_();
+ return StripeConfig(n);
+}
+
+TVM_REGISTER_GLOBAL("contrib.ethosu.cascader.Propagator")
+ .set_body_typed([](Array<Array<FloatImm> > transform, Array<Integer> offset) {
+ std::vector<std::vector<float> > vtransform;
+ for (const auto& vec : transform) {
+ vtransform.push_back(make_vector<float, FloatImm>(vec));
+ }
+ std::vector<int> voffset = make_vector<int, Integer>(offset);
+ return Propagator(vtransform, voffset);
+ });
+
+TVM_REGISTER_GLOBAL("contrib.ethosu.cascader.PropagatorPropagate")
+ .set_body_typed([](Propagator propagator, StripeConfig stripe_config) {
+ return propagator->propagate(stripe_config);
+ });
+
+TVM_REGISTER_GLOBAL("contrib.ethosu.cascader.PropagatorPropagateBenchmark")
+ .set_body_typed([](Propagator propagator, StripeConfig stripe_config, int repeats) {
+ for (int i = 0; i < repeats; i++) {
+ propagator->propagate(stripe_config);
+ }
+ return propagator->propagate(stripe_config);
+ });
Review comment:
This is not used, isn't it?
##########
File path: src/contrib/ethosu/cascader/stripe_config.h
##########
@@ -0,0 +1,202 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file src/contrib/ethosu/cascader/stripe_config.h
+ * \brief StripeConfig object for the NPU cascader
+ */
+#ifndef TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+#define TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+
+#include <tvm/node/reflection.h>
+#include <tvm/runtime/object.h>
+
+#include <functional>
+#include <map>
+#include <vector>
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+class StripeConfig;
+class PropagatorNode;
+
+/*! \brief Node to represent a StripeConfig */
+class StripeConfigNode : public Object {
+ public:
+ void VisitAttrs(AttrVisitor* v);
+
+ /*!
+ * \brief Get the shape of the stripe config.
+ * \return The shape of the stripe config.
+ * \note The shape refers to the size of the stripes in each dimension.
+ */
+ inline std::vector<int> GetShape() const { return shape_; }
+ /*!
+ * \brief Get the extent of the stripe config.
+ * \return The extent of the stripe config.
+ * \note The extent refers to the extent over which a StripeConfig operates.
+ * Specifically, it is the extent in each axis between the lowest value read
+ * by a stripe and the highest value read by a stripe.
+ */
+ inline std::vector<int> GetExtent() const { return extent_; }
+ /*!
+ * \brief Get the strides of the stripe config.
+ * \return The strides of the stripe config.
+ * \note The strides refer to the stride between stripes in each axis.
+ * The strides are represented as a float rather than an int to account for
+ * cases of 'fractional striding'. This may happen, for instance, with an
+ * upscaling operation where elements of the affine transformation matrix
+ * are not integers. In this case we can't simply round the strides as the
+ * error will compound when we need to multiply the strides by the number of
+ * stripes along a given axis.
+ */
+ inline std::vector<float> GetStrides() const { return strides_; }
+ /*!
+ * \brief Get the order of the stripe config.
+ * \return The order of the stripe config.
+ * \note The order refers to order in which the axes are iterated over.
+ * The first (outermost) axis is labelled as 1 with the rest increasing
+ * according to the axis' position. Any axis labelled with 0 isn't iterated over.
+ * For example, [1, 3, 2] would mean axis 0 is the outermost iteration axis,
+ * then axis 2, then finally axis 1.
+ */
+ inline std::vector<int> GetOrder() const { return order_; }
+ /*!
+ * \brief Get the stripes of the stripe config.
+ * \return The stripes of the stripe config.
+ * \note The stripes refer to the number of stripes in each axis.
+ * There must be at least one stripe in any given axis.
+ */
+ inline std::vector<int> GetStripes() const { return stripes_; }
+ /*!
+ * \brief Get the offset of the stripe config.
+ * \return The offset of the stripe config.
+ * \note The offset refers to the offset of the first stripe
+ * from the first element of the tensor. For example, in a 2D padding operation
+ * that is padding by 1 in every dimension, the offset would be [-1, -1].
+ */
+ inline std::vector<int> GetOffset() const { return offset_; }
+ /*! \return The hash of the StripeConfigNode */
+ size_t GetHash() const { return hash_; }
+
+ static constexpr const char* _type_key = "contrib.ethosu.cascader.StripeConfig";
+ TVM_DECLARE_FINAL_OBJECT_INFO(StripeConfigNode, Object);
+
+ protected:
+ friend class StripeConfig;
+ friend class PropagatorNode;
+
+ /*! \brief Compute the hash of the StripeConfigNode */
+ void ComputeHash_();
+
+ /*! \brief The shape of the stripes */
+ std::vector<int> shape_;
+ /*! \brief The extent of region to stripe over */
+ std::vector<int> extent_;
+ /*! \brief The strides of the stripes */
+ std::vector<float> strides_;
+ /*! \brief The order of the striping axes */
+ std::vector<int> order_;
+ /*! \brief The number of stripes in each axis */
+ std::vector<int> stripes_;
+ /*! \brief The offset of the first stripe */
+ std::vector<int> offset_;
+ /*! \brief The hash of the StripeConfigNode */
+ std::size_t hash_{0};
+};
+
+/*!
+ * \brief An object to describe how a tensor should be computed as a series
+ of n-dimensional tiles, or 'stripes'.
+ * \note The StripeConfig is a verbose way of specifying how to tile a tensor.
+ * We can imagine taking a 2D tensor of size (12, 12) and wanting to compute
+ * it in tiles of (4, 4). The tile is referred to as a stripe here to generalize
+ * this to n-dimensional tiles.
+ *
+ * The size of that stripe in each axis is the 'shape'. The strides is how far
+ * you should move between stripes, so also (4, 4) for a simple non-overlappping
+ * tiling. However, we explore some overlapping scheduling options so shape != strides
+ * in general. The 'extent' is simply (12, 12), the region over which we're conducting
+ * our tiling.
+ *
+ * The 'order' tells us which axis to iterate over first and which second and the
+ * 'stripes' tells us how many stripes we need to compute in each of those axes.
+ *
+ * Finally, the 'offset' tells us where to start the first stripe. In this simple
+ * case the offset is just (0, 0), but in something like a padding operation we
+ * may want to start from a negative index, which is captured by the offset.
+ */
+class StripeConfig : public ObjectRef {
+ public:
+ StripeConfig(const std::vector<int>& shape, const std::vector<int>& extent,
+ const std::vector<float>& strides, const std::vector<int>& order,
+ const std::vector<int>& stripes, const std::vector<int>& offset);
+ /*!
+ * \brief Check if two StripeConfigs are equals to each other.
+ * \param other StripeConfig to be checked.
+ * \return Whether the two StripeConfigs equal each other.
+ */
+ bool operator==(const StripeConfig& other) const;
+
+ TVM_DEFINE_OBJECT_REF_METHODS(StripeConfig, ObjectRef, StripeConfigNode);
+};
+
+/*!
+ * \brief Count the number of stripes of each shape that are executed for a given
+ StripeConfig.
+ * \param stripe_config The StripeConfig to count the stripes for.
+ * \param enable_sliding_window Whether to assume the sliding window optimization.
+ * \return A map between stripe shapes and the number of stripes of that shape that need
+ * executing.
+ */
Review comment:
Can you improve the documentation to make it cleaner?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] mbaret commented on pull request #9458: [ETHOSU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
mbaret commented on pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#issuecomment-961801637
cc @mbs-octoml @junrushao1994 @jacobbohlin @manupa-arm @NicolaLancellotti
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] mbaret commented on a change in pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
mbaret commented on a change in pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#discussion_r756809770
##########
File path: src/contrib/ethosu/cascader/stripe_config.h
##########
@@ -0,0 +1,218 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file src/contrib/ethosu/cascader/stripe_config.h
+ * \brief StripeConfig object for the NPU cascader
+ */
+#ifndef TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+#define TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+
+#include <tvm/node/reflection.h>
+#include <tvm/runtime/object.h>
+
+#include <functional>
+#include <map>
+#include <vector>
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+class StripeConfig;
+class PropagatorNode;
+
+/*! \brief Node to represent a StripeConfig */
+class StripeConfigNode : public Object {
+ public:
+ void VisitAttrs(AttrVisitor* v);
+
+ /*!
+ * \brief Get the shape of the stripe config.
+ * \return The shape of the stripe config.
+ * \note The shape refers to the size of the stripes in each dimension.
+ */
+ inline std::vector<int> GetShape() const { return shape_; }
+ /*!
+ * \brief Get the extent of the stripe config.
+ * \return The extent of the stripe config.
+ * \note The extent refers to the extent over which a StripeConfig operates.
+ * Specifically, it is the extent in each axis between the lowest value read
+ * by a stripe and the highest value read by a stripe.
+ */
+ inline std::vector<int> GetExtent() const { return extent_; }
+ /*!
+ * \brief Get the strides of the stripe config.
+ * \return The strides of the stripe config.
+ * \note The strides refer to the stride between stripes in each axis.
+ * The strides are represented as a float rather than an int to account for
+ * cases of 'fractional striding'. This may happen, for instance, with an
+ * upscaling operation where elements of the affine transformation matrix
+ * are not integers. In this case we can't simply round the strides as the
+ * error will compound when we need to multiply the strides by the number of
+ * stripes along a given axis.
+ */
+ inline std::vector<float> GetStrides() const { return strides_; }
+ /*!
+ * \brief Get the order of the stripe config.
+ * \return The order of the stripe config.
+ * \note The order refers to order in which the axes are iterated over.
+ * The first (outermost) axis is labelled as 1 with the rest increasing
+ * according to the axis' position. Any axis labelled with 0 isn't iterated over.
+ * For example, [1, 3, 2] would mean axis 0 is the outermost iteration axis,
+ * then axis 2, then finally axis 1.
+ */
+ inline std::vector<int> GetOrder() const { return order_; }
+ /*!
+ * \brief Get the stripes of the stripe config.
+ * \return The stripes of the stripe config.
+ * \note The stripes refer to the number of stripes in each axis.
+ * There must be at least one stripe in any given axis.
+ */
+ inline std::vector<int> GetStripes() const { return stripes_; }
+ /*!
+ * \brief Get the offset of the stripe config.
+ * \return The offset of the stripe config.
+ * \note The offset refers to the offset of the first stripe
+ * from the first element of the tensor. For example, in a 2D padding operation
+ * that is padding by 1 in every dimension, the offset would be [-1, -1].
+ */
+ inline std::vector<int> GetOffset() const { return offset_; }
+ /*! \return The hash of the StripeConfigNode */
+ size_t GetHash() const { return hash_; }
+
+ static constexpr const char* _type_key = "contrib.ethosu.cascader.StripeConfig";
+ TVM_DECLARE_FINAL_OBJECT_INFO(StripeConfigNode, Object);
+
+ protected:
+ friend class StripeConfig;
+ friend class PropagatorNode;
+
+ /*! \brief Compute the hash of the StripeConfigNode */
+ void ComputeHash_();
+
+ /*! \brief The shape of the stripes */
+ std::vector<int> shape_;
+ /*! \brief The extent of region to stripe over */
+ std::vector<int> extent_;
+ /*! \brief The strides of the stripes */
+ std::vector<float> strides_;
+ /*! \brief The order of the striping axes */
+ std::vector<int> order_;
+ /*! \brief The number of stripes in each axis */
+ std::vector<int> stripes_;
+ /*! \brief The offset of the first stripe */
+ std::vector<int> offset_;
+ /*! \brief The hash of the StripeConfigNode */
+ std::size_t hash_{0};
+};
+
+/*!
+ * \brief An object to describe how a tensor should be computed as a series
+ of n-dimensional tiles, or 'stripes'.
+ * \note The StripeConfig is a verbose way of specifying how to tile a tensor.
+ * We can imagine taking a 2D tensor of size (12, 12) and wanting to compute
+ * it in tiles of (4, 4). The tile is referred to as a stripe here to generalize
+ * this to n-dimensional tiles.
+ *
+ * The size of that stripe in each axis is the 'shape'. The strides is how far
+ * you should move between stripes, so also (4, 4) for a simple non-overlappping
+ * tiling. However, we explore some overlapping scheduling options so shape != strides
+ * in general. The 'extent' is simply (12, 12), the region over which we're conducting
+ * our tiling.
+ *
+ * The 'order' tells us which axis to iterate over first and which second and the
+ * 'stripes' tells us how many stripes we need to compute in each of those axes.
+ *
+ * Finally, the 'offset' tells us where to start the first stripe. In this simple
+ * case the offset is just (0, 0), but in something like a padding operation we
+ * may want to start from a negative index, which is captured by the offset.
Review comment:
I've updated the doc to use slice as the example here because I think that's easier to follow. Regarding the padding case, it's a bit of a challenge to explain without a diagram but I'll give it a go here.
Let's say we have an op A that represents a symmetric pad by 1 and two tensors T_in and T_out such that T_in -> A -> T_out. If T_in has shape (4, 4) then T_out will have shape (6, 6) after the padding. Now, we choose a StripeConfig for T_out which is equivalent to (2, 2) tiling:
```
StripeConfig T_out =
{
shape=[2, 2],
extent=[6, 6],
strides=[2, 2],
order=[1, 2],
stripes=[3, 3],
offset=[0, 0],
}
```
The question then is, what StripeConfig will need to be produced when we propagate to T_in? Well, if we state that any part of a stripe that lies outside of the tensor bounds can be ignored, then the input StripeConfig should be this:
```
StripeConfig T_in =
{
shape=[2, 2],
extent=[6, 6],
strides=[2, 2],
order=[1, 2],
stripes=[3, 3],
offset=[-1, -1],
}
```
This will effectively 'overlay' the output StripeConfig on the (4, 4) input tensor T_in, but such that outer 1-wide padding margin is always out-of-bounds (either <0 or >=4 in either axis). This way, reads will never be generated for the padding but they will for the 'interior'.
If this is still unclear - which I appreciate it might be - I can potentially produce a quick diagram.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] csullivan commented on a change in pull request #9458: [microNPU][1] Add affine analysis structures for the cascader
Posted by GitBox <gi...@apache.org>.
csullivan commented on a change in pull request #9458:
URL: https://github.com/apache/tvm/pull/9458#discussion_r753605721
##########
File path: src/contrib/ethosu/cascader/stripe_config.h
##########
@@ -0,0 +1,218 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file src/contrib/ethosu/cascader/stripe_config.h
+ * \brief StripeConfig object for the NPU cascader
+ */
+#ifndef TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+#define TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+
+#include <tvm/node/reflection.h>
+#include <tvm/runtime/object.h>
+
+#include <functional>
+#include <map>
+#include <vector>
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+class StripeConfig;
+class PropagatorNode;
+
+/*! \brief Node to represent a StripeConfig */
+class StripeConfigNode : public Object {
+ public:
+ void VisitAttrs(AttrVisitor* v);
+
+ /*!
+ * \brief Get the shape of the stripe config.
+ * \return The shape of the stripe config.
+ * \note The shape refers to the size of the stripes in each dimension.
+ */
+ inline std::vector<int> GetShape() const { return shape_; }
+ /*!
+ * \brief Get the extent of the stripe config.
+ * \return The extent of the stripe config.
+ * \note The extent refers to the extent over which a StripeConfig operates.
+ * Specifically, it is the extent in each axis between the lowest value read
+ * by a stripe and the highest value read by a stripe.
+ */
+ inline std::vector<int> GetExtent() const { return extent_; }
+ /*!
+ * \brief Get the strides of the stripe config.
+ * \return The strides of the stripe config.
+ * \note The strides refer to the stride between stripes in each axis.
+ * The strides are represented as a float rather than an int to account for
+ * cases of 'fractional striding'. This may happen, for instance, with an
+ * upscaling operation where elements of the affine transformation matrix
+ * are not integers. In this case we can't simply round the strides as the
+ * error will compound when we need to multiply the strides by the number of
+ * stripes along a given axis.
+ */
+ inline std::vector<float> GetStrides() const { return strides_; }
+ /*!
+ * \brief Get the order of the stripe config.
+ * \return The order of the stripe config.
+ * \note The order refers to order in which the axes are iterated over.
+ * The first (outermost) axis is labelled as 1 with the rest increasing
+ * according to the axis' position. Any axis labelled with 0 isn't iterated over.
+ * For example, [1, 3, 2] would mean axis 0 is the outermost iteration axis,
+ * then axis 2, then finally axis 1.
+ */
+ inline std::vector<int> GetOrder() const { return order_; }
+ /*!
+ * \brief Get the stripes of the stripe config.
+ * \return The stripes of the stripe config.
+ * \note The stripes refer to the number of stripes in each axis.
+ * There must be at least one stripe in any given axis.
+ */
+ inline std::vector<int> GetStripes() const { return stripes_; }
+ /*!
+ * \brief Get the offset of the stripe config.
+ * \return The offset of the stripe config.
+ * \note The offset refers to the offset of the first stripe
+ * from the first element of the tensor. For example, in a 2D padding operation
+ * that is padding by 1 in every dimension, the offset would be [-1, -1].
+ */
+ inline std::vector<int> GetOffset() const { return offset_; }
+ /*! \return The hash of the StripeConfigNode */
+ size_t GetHash() const { return hash_; }
+
+ static constexpr const char* _type_key = "contrib.ethosu.cascader.StripeConfig";
+ TVM_DECLARE_FINAL_OBJECT_INFO(StripeConfigNode, Object);
+
+ protected:
+ friend class StripeConfig;
+ friend class PropagatorNode;
+
+ /*! \brief Compute the hash of the StripeConfigNode */
+ void ComputeHash_();
+
+ /*! \brief The shape of the stripes */
+ std::vector<int> shape_;
+ /*! \brief The extent of region to stripe over */
+ std::vector<int> extent_;
+ /*! \brief The strides of the stripes */
+ std::vector<float> strides_;
+ /*! \brief The order of the striping axes */
+ std::vector<int> order_;
+ /*! \brief The number of stripes in each axis */
+ std::vector<int> stripes_;
+ /*! \brief The offset of the first stripe */
+ std::vector<int> offset_;
+ /*! \brief The hash of the StripeConfigNode */
+ std::size_t hash_{0};
+};
+
+/*!
+ * \brief An object to describe how a tensor should be computed as a series
+ of n-dimensional tiles, or 'stripes'.
+ * \note The StripeConfig is a verbose way of specifying how to tile a tensor.
+ * We can imagine taking a 2D tensor of size (12, 12) and wanting to compute
+ * it in tiles of (4, 4). The tile is referred to as a stripe here to generalize
+ * this to n-dimensional tiles.
+ *
+ * The size of that stripe in each axis is the 'shape'. The strides is how far
+ * you should move between stripes, so also (4, 4) for a simple non-overlappping
+ * tiling. However, we explore some overlapping scheduling options so shape != strides
+ * in general. The 'extent' is simply (12, 12), the region over which we're conducting
+ * our tiling.
+ *
+ * The 'order' tells us which axis to iterate over first and which second and the
+ * 'stripes' tells us how many stripes we need to compute in each of those axes.
+ *
+ * Finally, the 'offset' tells us where to start the first stripe. In this simple
+ * case the offset is just (0, 0), but in something like a padding operation we
+ * may want to start from a negative index, which is captured by the offset.
Review comment:
A note about how negative indexing is handled for an operation would be helpful. For example, the stripe config between two operations Op1 and Op2, will depend on the padding needed by Op2, but will influence where Op1 writes its memory. Is that correct?
##########
File path: src/contrib/ethosu/cascader/stripe_config.h
##########
@@ -0,0 +1,218 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file src/contrib/ethosu/cascader/stripe_config.h
+ * \brief StripeConfig object for the NPU cascader
+ */
+#ifndef TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+#define TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+
+#include <tvm/node/reflection.h>
+#include <tvm/runtime/object.h>
+
+#include <functional>
+#include <map>
+#include <vector>
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+class StripeConfig;
+class PropagatorNode;
+
+/*! \brief Node to represent a StripeConfig */
+class StripeConfigNode : public Object {
+ public:
+ void VisitAttrs(AttrVisitor* v);
+
+ /*!
+ * \brief Get the shape of the stripe config.
+ * \return The shape of the stripe config.
+ * \note The shape refers to the size of the stripes in each dimension.
+ */
+ inline std::vector<int> GetShape() const { return shape_; }
+ /*!
+ * \brief Get the extent of the stripe config.
+ * \return The extent of the stripe config.
+ * \note The extent refers to the extent over which a StripeConfig operates.
+ * Specifically, it is the extent in each axis between the lowest value read
+ * by a stripe and the highest value read by a stripe.
+ */
+ inline std::vector<int> GetExtent() const { return extent_; }
+ /*!
+ * \brief Get the strides of the stripe config.
+ * \return The strides of the stripe config.
+ * \note The strides refer to the stride between stripes in each axis.
+ * The strides are represented as a float rather than an int to account for
+ * cases of 'fractional striding'. This may happen, for instance, with an
+ * upscaling operation where elements of the affine transformation matrix
+ * are not integers. In this case we can't simply round the strides as the
+ * error will compound when we need to multiply the strides by the number of
+ * stripes along a given axis.
+ */
+ inline std::vector<float> GetStrides() const { return strides_; }
+ /*!
+ * \brief Get the order of the stripe config.
+ * \return The order of the stripe config.
+ * \note The order refers to order in which the axes are iterated over.
+ * The first (outermost) axis is labelled as 1 with the rest increasing
+ * according to the axis' position. Any axis labelled with 0 isn't iterated over.
+ * For example, [1, 3, 2] would mean axis 0 is the outermost iteration axis,
+ * then axis 2, then finally axis 1.
+ */
+ inline std::vector<int> GetOrder() const { return order_; }
+ /*!
+ * \brief Get the stripes of the stripe config.
+ * \return The stripes of the stripe config.
+ * \note The stripes refer to the number of stripes in each axis.
+ * There must be at least one stripe in any given axis.
+ */
+ inline std::vector<int> GetStripes() const { return stripes_; }
+ /*!
+ * \brief Get the offset of the stripe config.
+ * \return The offset of the stripe config.
+ * \note The offset refers to the offset of the first stripe
+ * from the first element of the tensor. For example, in a 2D padding operation
+ * that is padding by 1 in every dimension, the offset would be [-1, -1].
+ */
+ inline std::vector<int> GetOffset() const { return offset_; }
+ /*! \return The hash of the StripeConfigNode */
+ size_t GetHash() const { return hash_; }
+
+ static constexpr const char* _type_key = "contrib.ethosu.cascader.StripeConfig";
+ TVM_DECLARE_FINAL_OBJECT_INFO(StripeConfigNode, Object);
+
+ protected:
+ friend class StripeConfig;
+ friend class PropagatorNode;
+
+ /*! \brief Compute the hash of the StripeConfigNode */
+ void ComputeHash_();
+
+ /*! \brief The shape of the stripes */
+ std::vector<int> shape_;
+ /*! \brief The extent of region to stripe over */
+ std::vector<int> extent_;
+ /*! \brief The strides of the stripes */
+ std::vector<float> strides_;
+ /*! \brief The order of the striping axes */
+ std::vector<int> order_;
+ /*! \brief The number of stripes in each axis */
+ std::vector<int> stripes_;
+ /*! \brief The offset of the first stripe */
+ std::vector<int> offset_;
+ /*! \brief The hash of the StripeConfigNode */
+ std::size_t hash_{0};
+};
+
+/*!
+ * \brief An object to describe how a tensor should be computed as a series
+ of n-dimensional tiles, or 'stripes'.
+ * \note The StripeConfig is a verbose way of specifying how to tile a tensor.
+ * We can imagine taking a 2D tensor of size (12, 12) and wanting to compute
+ * it in tiles of (4, 4). The tile is referred to as a stripe here to generalize
+ * this to n-dimensional tiles.
+ *
+ * The size of that stripe in each axis is the 'shape'. The strides is how far
+ * you should move between stripes, so also (4, 4) for a simple non-overlappping
+ * tiling. However, we explore some overlapping scheduling options so shape != strides
Review comment:
Ping on earlier comment ⬆️ , an example like one of these when stride value is non-integral would be nice.
##########
File path: src/contrib/ethosu/cascader/stripe_config.h
##########
@@ -0,0 +1,218 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file src/contrib/ethosu/cascader/stripe_config.h
+ * \brief StripeConfig object for the NPU cascader
+ */
+#ifndef TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+#define TVM_CONTRIB_ETHOSU_CASCADER_STRIPE_CONFIG_H_
+
+#include <tvm/node/reflection.h>
+#include <tvm/runtime/object.h>
+
+#include <functional>
+#include <map>
+#include <vector>
+
+namespace tvm {
+namespace contrib {
+namespace ethosu {
+namespace cascader {
+
+class StripeConfig;
+class PropagatorNode;
+
+/*! \brief Node to represent a StripeConfig */
+class StripeConfigNode : public Object {
+ public:
+ void VisitAttrs(AttrVisitor* v);
+
+ /*!
+ * \brief Get the shape of the stripe config.
+ * \return The shape of the stripe config.
+ * \note The shape refers to the size of the stripes in each dimension.
+ */
+ inline std::vector<int> GetShape() const { return shape_; }
+ /*!
+ * \brief Get the extent of the stripe config.
+ * \return The extent of the stripe config.
+ * \note The extent refers to the extent over which a StripeConfig operates.
+ * Specifically, it is the extent in each axis between the lowest value read
+ * by a stripe and the highest value read by a stripe.
+ */
+ inline std::vector<int> GetExtent() const { return extent_; }
+ /*!
+ * \brief Get the strides of the stripe config.
+ * \return The strides of the stripe config.
+ * \note The strides refer to the stride between stripes in each axis.
+ * The strides are represented as a float rather than an int to account for
+ * cases of 'fractional striding'. This may happen, for instance, with an
+ * upscaling operation where elements of the affine transformation matrix
+ * are not integers. In this case we can't simply round the strides as the
+ * error will compound when we need to multiply the strides by the number of
+ * stripes along a given axis.
+ */
+ inline std::vector<float> GetStrides() const { return strides_; }
Review comment:
Is there an example that we can write or link to in this doc string to illustrate the error accumulation that occurs from using ceildiv style rounding. I didn't quite follow the current description. By fractional striding are you trying to describe the case when the stripe shape dims are not divisors of the input shape dims?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org