You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mxnet.apache.org by GitBox <gi...@apache.org> on 2020/03/20 13:53:34 UTC
[GitHub] [incubator-mxnet] access2rohit opened a new pull request #17882:
[WIP]Improve performance of broadcast_axis
access2rohit opened a new pull request #17882: [WIP]Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882
## Description ##
Improves the performance of broadcast axis by reducing ALU operations and caching stride values
## Checklist ##
### Essentials ###
- [ ] Changes are complete (i.e. I finished coding on this PR)
- [ ] All changes have test coverage:
- Unit tests are added for small changes to verify correctness (e.g. adding a new operator)
- Nightly tests are added for complicated/long-running ones (e.g. changing distributed kvstore)
- Build tests will be added for build configuration changes (e.g. adding a new build option with NCCL)
- [ ] Code is well-documented:
- For user-facing API changes, API doc string has been updated.
- For new C++ functions in header files, their functionalities and arguments are documented.
- For new examples, README.md is added to explain the what the example does, the source of the dataset, expected performance on test set and reference to the original paper if applicable
- Check the API doc at https://mxnet-ci-doc.s3-accelerate.dualstack.amazonaws.com/PR-$PR_ID/$BUILD_ID/index.html
- [ ] To the best of my knowledge, examples are either not affected by this change, or have been fixed to be compatible with this change
### Changes ###
- [ ] Feature1, tests, (and when applicable, API doc)
- [ ] Feature2, tests, (and when applicable, API doc)
## Comments ##
- If this change is a backward incompatible change, why must this change be made.
- Interesting edge cases to note here
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410407354
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1058,50 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const uint64_t *axes,
+ const uint64_t *out_stride,
+ const size_t no_axes) {
Review comment:
ok ... will do. `num_broadcast_axes` makes more sense to me.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit edited a comment on issue #17882:
Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit edited a comment on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-615379148
> Please add more details in the PR description to explain the rationale of this change:
@apeforest
1) Its there in the PR Heading. Additionally, its being done to improve BERT performance regression when using Large Tensor Build
2) Leverages vectorization. Can't explain line by line as to how. Too much text to write. I can share a link about vectorization for reviewers to read. Let me know if you meant something else. I can write 1 line each for 3 cases which is necessary
3) I didn't understand this question. Could you clarify what meant by side-effect.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410409695
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,55 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
- if (dst_shape.ndim() == 2) {
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
+ int iter = dst_shape.ndim() - 1, i = 0;
+ bool flag = false;
Review comment:
this flag ensure if broadcast_axis is supplied with input where input shape = output shape(i.e. no broadcast). In such a case we are simply invoking copy. will change it to `shape_changed`
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410407354
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1058,50 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const uint64_t *axes,
+ const uint64_t *out_stride,
+ const size_t no_axes) {
Review comment:
ok ... will do
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request
#17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410368675
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1090,6 +1118,7 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
mxnet::TShape src_shape, dst_shape;
BroadcastReduceShapeCompact(outputs[0].shape_, small, &dst_shape, &src_shape);
Stream<xpu> *s = ctx.get_stream<xpu>();
+ bool enable_lt = dst_shape.Size() > INT_MAX;
Review comment:
Let's remove this flag and check the performance gain. If indeed we need to handle int64 case differently we need a more holistic 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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on issue #17882: Improve
performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-615362596
> Could we also take Da's suggestion by using int32_t for GPU kernels?
@apeforest
For this op only or all ? For this op only I can take a look.
If for all ops I would like to do that in a separate PR.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request
#17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410369128
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,55 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
- if (dst_shape.ndim() == 2) {
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
Review comment:
why use uint64_t here?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410409817
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,55 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
- if (dst_shape.ndim() == 2) {
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
Review comment:
will use `size_t` instead
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410357561
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,52 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
+ int iter = dst_shape.ndim() - 1, i = 0;
+ out_stride[iter] = 1;
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ --iter;
+ for (; iter >= 0; --iter) {
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ out_stride[iter] = out_stride[iter+1] * dst_shape[iter+1];
+ }
if (dst_shape.ndim() == 2) {
Tensor<xpu, 2, OType> out =
outputs[0].get_with_shape<xpu, 2, OType>(dst_shape.get<2>(), s);
Tensor<xpu, 2, IType> data =
inputs[0].get_with_shape<xpu, 2, IType>(src_shape.get<2>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], 2);
+ if (!enable_lt) {
+ typedef int32_t index_t;
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ } else {
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ }
} else {
const int ndim = MXNET_SPECIAL_MAX_NDIM;
Tensor<xpu, ndim, OType> out =
outputs[0].get_with_shape<xpu, ndim, OType>(dst_shape.get<ndim>(), s);
Tensor<xpu, ndim, IType> data =
inputs[0].get_with_shape<xpu, ndim, IType>(src_shape.get<ndim>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], ndim);
+ if (!enable_lt) {
Review comment:
ok
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on issue #17882: Improve
performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-615363096
> @access2rohit can you rebase on latest master to see if that fixes CI?
Was still failing after rebase. I have fixed the failing case and pushed new changes 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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410408515
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1058,50 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const uint64_t *axes,
+ const uint64_t *out_stride,
+ const size_t no_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ switch (no_axes) {
Review comment:
good question! max only 3 broadcast_axes are possible, since all consecutive broadcast and non-broadcast axes are merged together and we only support total of 5 Dimension are merging axes.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410409817
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,55 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
- if (dst_shape.ndim() == 2) {
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
Review comment:
ahh ... missed replacing it with `size_t` instead.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request
#17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r409088529
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,52 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
+ int iter = dst_shape.ndim() - 1, i = 0;
+ out_stride[iter] = 1;
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ --iter;
+ for (; iter >= 0; --iter) {
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ out_stride[iter] = out_stride[iter+1] * dst_shape[iter+1];
+ }
if (dst_shape.ndim() == 2) {
Tensor<xpu, 2, OType> out =
outputs[0].get_with_shape<xpu, 2, OType>(dst_shape.get<2>(), s);
Tensor<xpu, 2, IType> data =
inputs[0].get_with_shape<xpu, 2, IType>(src_shape.get<2>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], 2);
+ if (!enable_lt) {
+ typedef int32_t index_t;
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ } else {
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ }
} else {
const int ndim = MXNET_SPECIAL_MAX_NDIM;
Tensor<xpu, ndim, OType> out =
outputs[0].get_with_shape<xpu, ndim, OType>(dst_shape.get<ndim>(), s);
Tensor<xpu, ndim, IType> data =
inputs[0].get_with_shape<xpu, ndim, IType>(src_shape.get<ndim>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], ndim);
+ if (!enable_lt) {
Review comment:
Can we remove this to see how much perf gain we have with the operator speedup alone?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request
#17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410367429
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1058,50 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const uint64_t *axes,
+ const uint64_t *out_stride,
+ const size_t no_axes) {
Review comment:
no_axes is a confusing name. Please use `num_axes`
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410408741
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1090,6 +1118,7 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
mxnet::TShape src_shape, dst_shape;
BroadcastReduceShapeCompact(outputs[0].shape_, small, &dst_shape, &src_shape);
Stream<xpu> *s = ctx.get_stream<xpu>();
+ bool enable_lt = dst_shape.Size() > INT_MAX;
Review comment:
will do
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit edited a comment on issue #17882:
Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit edited a comment on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-615379148
> Please add more details in the PR description to explain the rationale of this change:
@apeforest
1) Its there in the PR Headiong
2) Leverages vectorization. Can't explain line by line as to how. Too much text to explain. I can share a link about vectorization for you to read.
3) I didn't understand this question. Could you clarify what meant by side-effect.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request
#17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410368950
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,55 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
- if (dst_shape.ndim() == 2) {
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
+ int iter = dst_shape.ndim() - 1, i = 0;
+ bool flag = false;
Review comment:
what does the flag here mean? Please use a more informative name.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] leezu commented on issue #17882: Improve
performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
leezu commented on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-614189798
@access2rohit can you rebase on latest master to see if that fixes CI?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] ptrendx commented on issue #17882: [WIP]Improve
performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
ptrendx commented on issue #17882: [WIP]Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-601958174
The biggest speedup you can get here would be from vectorization, so that you don't need to do those index calculations all the time (just once per vector).
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410408515
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1058,50 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const uint64_t *axes,
+ const uint64_t *out_stride,
+ const size_t no_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ switch (no_axes) {
Review comment:
good question! max only 3 broadcast_axes are possible, since all consecutive broadcast and non-broadcast axes are merged together(https://github.com/apache/incubator-mxnet/pull/17882/files#diff-b669acf192ce8ff1658871e6d9dcca5dR1119) and we only support total of 5 Dimension are merging axes.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request
#17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410367756
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1058,50 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const uint64_t *axes,
+ const uint64_t *out_stride,
+ const size_t no_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ switch (no_axes) {
Review comment:
Are we only supporting max of 3 axes here?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410409695
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,55 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
- if (dst_shape.ndim() == 2) {
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
+ int iter = dst_shape.ndim() - 1, i = 0;
+ bool flag = false;
Review comment:
this flag ensure if broadcast_axis is supplied with input where input shape = output shape(i.e. no broadcast). In such a case we are simply invoking copy
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request
#17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410369128
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,55 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
- if (dst_shape.ndim() == 2) {
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
Review comment:
why use a hardcoded `uint64_t` here?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit edited a comment on issue #17882:
Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit edited a comment on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-615379148
> Please add more details in the PR description to explain the rationale of this change:
@apeforest
1) Its there in the PR Heading. Additionally, its being done to improve BERT performance regression when using Large Tensor Build
2) Leverages vectorization. Can't explain line by line as to how. Too much text to write. I can share a link about vectorization for reviewers to read.
3) I didn't understand this question. Could you clarify what meant by side-effect.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-650083468
@mxnet-bot run ci [unix-cpu, clang, website, centos-cpu, edge, miscellaneous, unix-gpu, windows-gpu, centos-gpu, windows-cpu]
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit edited a comment on issue #17882:
Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit edited a comment on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-615379148
> Please add more details in the PR description to explain the rationale of this change:
@apeforest
1) Its there in the PR Heading
2) Leverages vectorization. Can't explain line by line as to how. Too much text to write. I can share a link about vectorization for reviewers to read.
3) I didn't understand this question. Could you clarify what meant by side-effect.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] apeforest commented on issue #17882: Improve
performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-615373674
Please add more details in the PR description to explain the rationale of this change:
(1) Why make the change
(2) How this change improved performance
(3) Any side effect
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] ptrendx commented on issue #17882: [WIP]Improve
performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
ptrendx commented on issue #17882: [WIP]Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-601957908
Is this going to concentrate on CPU performance? GPU performance of broadcast_axis/like/etc is really poor too (few days ago I was measuring it and got ~150 GB/s on V100 GPU out of 900 GB/s peak BW.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit edited a comment on issue #17882:
Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit edited a comment on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-615379148
> Please add more details in the PR description to explain the rationale of this change:
@apeforest
1) Its there in the PR Heading
2) Leverages vectorization. Can't explain line by line as to how. Too much text to explain. I can share a link about vectorization for you to read.
3) I didn't understand this question. Could you clarify what meant by side-effect.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on issue #17882: Improve
performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on issue #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-615379148
> change
@apeforest
1) Its there in the PR Headiong
2) Leverages vectorization. Can't explain line by line as to how. Too much text to explain. I can share a link about vectorization for you to read.
3) I didn't understand this question. Could you clarify what meant by side-effect.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull
request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r410408515
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1058,50 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const uint64_t *axes,
+ const uint64_t *out_stride,
+ const size_t no_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ switch (no_axes) {
Review comment:
max only 3 broadcast_axes are possible, since all consecutive broadcast and non-broadcast axes are merged together and we only support total of 5 Dimension are merging axes.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445869399
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1114,6 +1124,92 @@ struct broadcast_kernel {
}
};
+/**
+ * Changed the thread workload mapping from 1
+ * thread/output element to 1 thread/input to be broadcasted
+ * This approach leverages vectorization when fastest varying
+ * index(stride=1) of the tensor is to be broadcasted.
+ * In other cases it simply performs better by better load balancing.
+ */
+template<typename OP>
+struct broadcast_kernel_cpu {
+ template<typename IType, typename OType>
+ MSHADOW_XINLINE static void Map(index_t i,
+ IType *input,
+ OType *output,
+ const ShapeAndStride& aux_data,
+ const OpReqType req,
+ const int ndim) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % aux_data.input_shape[iter];
+ init_off += dim_idx * aux_data.out_stride[iter];
+ idx /= aux_data.input_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (aux_data.num_broadcast_axes) {
+ // when input shape is one of the follwing forms
+ // (x_1,1) or (x_1,1,x_2) or (1,x_1)
+ // x_1, x_2 are size of the dimensions that are not to be broadcasted
+ // in case of (x_1,1) the system leverages vectorization but in other 2
+ // the performance is improved due avoidance of duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 1 :
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t l=0; l < aux_data.output_shape[aux_data.axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is one of the follwing forms
+ // (x_1,1,x_2,1) or (1,x_1,1,x_2) or (x_1,1,x_2,1,x_3)
+ // x_1, x_2, x_3 are size of the dimensions that are not to be broadcasted
+ // in the inner most loop can be vectorized by compiler in outer loops
+ // the performance is improved due avoidance of duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 2:
+ stride_1 = aux_data.out_stride[aux_data.axes[1]];
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t k=0; k < aux_data.output_shape[aux_data.axes[1]]; k++) {
Review comment:
nit: space around '='
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] mxnet-bot commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
mxnet-bot commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-647616252
Jenkins CI successfully triggered : [unix-cpu, clang, website, centos-cpu, edge, miscellaneous, sanity, unix-gpu, windows-gpu, centos-gpu, windows-cpu]
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-650485641
@zheng-da Can you please review?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull request #17882: [WIP]Improve CPU performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r442511375
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (num_broadcast_axes) {
+ // when input shape is amogst one of the form
+ // [(x,1), (x,1,x), (1,x)]
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 1 :
+ stride_0 = out_stride[axes[0]];
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is amogst one of the form
+ // [(x,1,x,1), (1,x,1,x), (x,1,x,1,x)]
+ // x can be any +ve number >1 or =0(the axis ) and they need not be equal to each other
+ case 2:
+ stride_1 = out_stride[axes[1]], stride_0 = out_stride[axes[0]];
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ break;
+ // when input shape is of the form [(1,x,1,x,1)] and
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 3:
+ stride_2 = out_stride[axes[2]], stride_1 = out_stride[axes[1]];
+ stride_0 = out_stride[axes[0]];
+ for (int j=0; j < out_shape[axes[2]]; j++) {
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + j*stride_2 + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ }
+ break;
+ }
Review comment:
WIll update will default choice. Though it should ideally be unreachable.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r444736360
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (num_broadcast_axes) {
+ // when input shape is amogst one of the form
+ // [(x,1), (x,1,x), (1,x)]
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 1 :
+ stride_0 = out_stride[axes[0]];
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is amogst one of the form
+ // [(x,1,x,1), (1,x,1,x), (x,1,x,1,x)]
+ // x can be any +ve number >1 or =0(the axis ) and they need not be equal to each other
+ case 2:
+ stride_1 = out_stride[axes[1]], stride_0 = out_stride[axes[0]];
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ break;
+ // when input shape is of the form [(1,x,1,x,1)] and
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 3:
+ stride_2 = out_stride[axes[2]], stride_1 = out_stride[axes[1]];
+ stride_0 = out_stride[axes[0]];
+ for (int j=0; j < out_shape[axes[2]]; j++) {
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + j*stride_2 + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ }
+ break;
+ }
Review comment:
Deafult case with LOG(FATAL) will cause build failure since `cout` cannot be used inside device code. This is due to the way kernel launches are written
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r411751450
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (num_broadcast_axes) {
+ // when input shape is amogst one of the form
+ // [(x,1), (x,1,x), (1,x)]
+ // x can be any +ve number >=0 and they need not be equal to each other
Review comment:
what does +ve mean?
##########
File path: src/operator/numpy/np_matmul_op-inl.h
##########
@@ -157,12 +157,50 @@ inline void MatmulImpl(const OpContext& ctx,
DType* bc_b_ptr = bc_a_ptr + bc_size_a;
MSHADOW_TYPE_SWITCH_WITH_BOOL(input_a.type_flag_, IType, {
MSHADOW_TYPE_SWITCH_WITH_BOOL(input_b.type_flag_, OType, {
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, bc_size_a, input_a.dptr<IType>(), bc_a_ptr,
- k_a_shape, k_a_shape_bc, OpReqType::kWriteTo, ndim);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, bc_size_b, input_b.dptr<IType>(), bc_b_ptr,
- k_b_shape, k_b_shape_bc, OpReqType::kWriteTo, ndim);
+ bool a_shape_changed = false, b_shape_changed = false;
+ size_t axes[ndim], out_stride[ndim], axes_b[ndim], out_stride_b[ndim];
+ int iter = ndim - 1, idx_a = 0, idx_b = 0;
+ out_stride[iter] = 1;
+ out_stride_b[iter] = 1;
+ if (k_a_shape[iter] != k_a_shape_bc[iter]) {
Review comment:
Can these two if blocks be included in the for loop below?
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (num_broadcast_axes) {
+ // when input shape is amogst one of the form
+ // [(x,1), (x,1,x), (1,x)]
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 1 :
+ stride_0 = out_stride[axes[0]];
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is amogst one of the form
+ // [(x,1,x,1), (1,x,1,x), (x,1,x,1,x)]
+ // x can be any +ve number >1 or =0(the axis ) and they need not be equal to each other
+ case 2:
+ stride_1 = out_stride[axes[1]], stride_0 = out_stride[axes[0]];
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ break;
+ // when input shape is of the form [(1,x,1,x,1)] and
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 3:
+ stride_2 = out_stride[axes[2]], stride_1 = out_stride[axes[1]];
+ stride_0 = out_stride[axes[0]];
+ for (int j=0; j < out_shape[axes[2]]; j++) {
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + j*stride_2 + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ }
+ break;
+ }
Review comment:
Add a default case to error out.
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (num_broadcast_axes) {
+ // when input shape is amogst one of the form
+ // [(x,1), (x,1,x), (1,x)]
Review comment:
No need to use [] in the comment.
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
Review comment:
Again, could you please explain why there are only 3 cases regarding the number of axes?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445868759
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1114,6 +1124,92 @@ struct broadcast_kernel {
}
};
+/**
+ * Changed the thread workload mapping from 1
+ * thread/output element to 1 thread/input to be broadcasted
+ * This approach leverages vectorization when fastest varying
+ * index(stride=1) of the tensor is to be broadcasted.
+ * In other cases it simply performs better by better load balancing.
+ */
+template<typename OP>
+struct broadcast_kernel_cpu {
+ template<typename IType, typename OType>
+ MSHADOW_XINLINE static void Map(index_t i,
+ IType *input,
+ OType *output,
+ const ShapeAndStride& aux_data,
+ const OpReqType req,
+ const int ndim) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % aux_data.input_shape[iter];
+ init_off += dim_idx * aux_data.out_stride[iter];
+ idx /= aux_data.input_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (aux_data.num_broadcast_axes) {
+ // when input shape is one of the follwing forms
+ // (x_1,1) or (x_1,1,x_2) or (1,x_1)
+ // x_1, x_2 are size of the dimensions that are not to be broadcasted
+ // in case of (x_1,1) the system leverages vectorization but in other 2
+ // the performance is improved due avoidance of duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 1 :
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t l=0; l < aux_data.output_shape[aux_data.axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is one of the follwing forms
+ // (x_1,1,x_2,1) or (1,x_1,1,x_2) or (x_1,1,x_2,1,x_3)
+ // x_1, x_2, x_3 are size of the dimensions that are not to be broadcasted
+ // in the inner most loop can be vectorized by compiler in outer loops
+ // the performance is improved due avoidance of duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 2:
+ stride_1 = aux_data.out_stride[aux_data.axes[1]];
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t k=0; k < aux_data.output_shape[aux_data.axes[1]]; k++) {
+ for (index_t l=0; l < aux_data.output_shape[aux_data.axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ break;
+ // when input shape is of the form (1,x_1,1,x_2,1)
+ // x_1, x_2 are size of the dimensions that are not to be broadcasted
+ // here the last axis which is [4] is the one where compiler can vectorize
+ // the code the outer 2 loops improve preformance by avoiding
+ // duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 3:
+ stride_2 = aux_data.out_stride[aux_data.axes[2]];
+ stride_1 = aux_data.out_stride[aux_data.axes[1]];
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t j=0; j < aux_data.output_shape[aux_data.axes[2]]; j++) {
Review comment:
nit: add space between "="
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] mxnet-bot commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
mxnet-bot commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-650083555
Jenkins CI successfully triggered : [unix-gpu, centos-cpu, website, edge, miscellaneous, windows-gpu, unix-cpu, centos-gpu, clang, windows-cpu]
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445869162
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1114,6 +1124,92 @@ struct broadcast_kernel {
}
};
+/**
+ * Changed the thread workload mapping from 1
+ * thread/output element to 1 thread/input to be broadcasted
+ * This approach leverages vectorization when fastest varying
+ * index(stride=1) of the tensor is to be broadcasted.
+ * In other cases it simply performs better by better load balancing.
+ */
+template<typename OP>
+struct broadcast_kernel_cpu {
+ template<typename IType, typename OType>
+ MSHADOW_XINLINE static void Map(index_t i,
+ IType *input,
+ OType *output,
+ const ShapeAndStride& aux_data,
+ const OpReqType req,
+ const int ndim) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % aux_data.input_shape[iter];
+ init_off += dim_idx * aux_data.out_stride[iter];
+ idx /= aux_data.input_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (aux_data.num_broadcast_axes) {
+ // when input shape is one of the follwing forms
+ // (x_1,1) or (x_1,1,x_2) or (1,x_1)
+ // x_1, x_2 are size of the dimensions that are not to be broadcasted
+ // in case of (x_1,1) the system leverages vectorization but in other 2
+ // the performance is improved due avoidance of duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 1 :
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t l=0; l < aux_data.output_shape[aux_data.axes[0]]; l++) {
Review comment:
nit: space around '='
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r411749878
##########
File path: src/operator/numpy/np_matmul_op-inl.h
##########
@@ -157,12 +157,50 @@ inline void MatmulImpl(const OpContext& ctx,
DType* bc_b_ptr = bc_a_ptr + bc_size_a;
MSHADOW_TYPE_SWITCH_WITH_BOOL(input_a.type_flag_, IType, {
MSHADOW_TYPE_SWITCH_WITH_BOOL(input_b.type_flag_, OType, {
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, bc_size_a, input_a.dptr<IType>(), bc_a_ptr,
- k_a_shape, k_a_shape_bc, OpReqType::kWriteTo, ndim);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, bc_size_b, input_b.dptr<IType>(), bc_b_ptr,
- k_b_shape, k_b_shape_bc, OpReqType::kWriteTo, ndim);
+ bool a_shape_changed = false, b_shape_changed = false;
+ size_t axes[ndim], out_stride[ndim], axes_b[ndim], out_stride_b[ndim];
+ int iter = ndim - 1, idx_a = 0, idx_b = 0;
+ out_stride[iter] = 1;
Review comment:
should this be named out_stride_a?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445866782
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1147,16 +1249,26 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
outputs[0].get_with_shape<xpu, 2, OType>(dst_shape.get<2>(), s);
Tensor<xpu, 2, IType> data =
inputs[0].get_with_shape<xpu, 2, IType>(src_shape.get<2>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ if (isCPU) {
+ Kernel<broadcast_kernel_cpu<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ } else {
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ }
} else {
const int ndim = MXNET_SPECIAL_MAX_NDIM;
Tensor<xpu, ndim, OType> out =
outputs[0].get_with_shape<xpu, ndim, OType>(dst_shape.get<ndim>(), s);
Tensor<xpu, ndim, IType> data =
inputs[0].get_with_shape<xpu, ndim, IType>(src_shape.get<ndim>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], ndim);
+ if (isCPU) {
+ Kernel<broadcast_kernel_cpu<mshadow_op::identity>, xpu>::Launch(
Review comment:
If it's only CPU you don't need to use the generic kernel, right? You can just use the Kernel<OP, cpu> template.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-651333667
@mxnet-label-bot update [pr-awaiting-merge]
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r411024747
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,52 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
+ int iter = dst_shape.ndim() - 1, i = 0;
+ out_stride[iter] = 1;
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ --iter;
+ for (; iter >= 0; --iter) {
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ out_stride[iter] = out_stride[iter+1] * dst_shape[iter+1];
+ }
if (dst_shape.ndim() == 2) {
Tensor<xpu, 2, OType> out =
outputs[0].get_with_shape<xpu, 2, OType>(dst_shape.get<2>(), s);
Tensor<xpu, 2, IType> data =
inputs[0].get_with_shape<xpu, 2, IType>(src_shape.get<2>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], 2);
+ if (!enable_lt) {
+ typedef int32_t index_t;
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ } else {
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ }
} else {
const int ndim = MXNET_SPECIAL_MAX_NDIM;
Tensor<xpu, ndim, OType> out =
outputs[0].get_with_shape<xpu, ndim, OType>(dst_shape.get<ndim>(), s);
Tensor<xpu, ndim, IType> data =
inputs[0].get_with_shape<xpu, ndim, IType>(src_shape.get<ndim>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], ndim);
+ if (!enable_lt) {
Review comment:
@apeforest
Here are the results after removing typedef and enable_lt conditional check. There is a slight improvement in the results. But its not that significant.
| code version | cases | avg | p50 | p90 |
|--------------|---------------------------------------------|--------|--------|--------|
| master LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 28.89 | 26.91 | 34.51 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 28.70 | 26.45 | 34.03 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 123.14 | 121.88 | 125.35 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 65.18 | 61.52 | 74.58 |
| | | | | |
| master no-LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 13.82 | 13.24 | 16.83 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 13.46 | 13.00 | 16.18 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 52.38 | 51.36 | 53.51 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 35.29 | 38.65 | 40.23 |
| | | | | |
| new LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 15.91 | 15.79 | 18.23 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 16.44 | 17.50 | 17.97 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 124.17 | 125.65 | 126.42 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 37.33 | 36.76 | 38.07 |
| | | | | |
| new no-LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 9.76 | 9.91 | 11.98 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 9.04 | 9.54 | 9.96 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 58.40 | 60.54 | 61.01 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 23.45 | 23.11 | 26.79 |
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445868990
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1114,6 +1124,92 @@ struct broadcast_kernel {
}
};
+/**
+ * Changed the thread workload mapping from 1
+ * thread/output element to 1 thread/input to be broadcasted
+ * This approach leverages vectorization when fastest varying
+ * index(stride=1) of the tensor is to be broadcasted.
+ * In other cases it simply performs better by better load balancing.
+ */
+template<typename OP>
+struct broadcast_kernel_cpu {
+ template<typename IType, typename OType>
+ MSHADOW_XINLINE static void Map(index_t i,
+ IType *input,
+ OType *output,
+ const ShapeAndStride& aux_data,
+ const OpReqType req,
+ const int ndim) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % aux_data.input_shape[iter];
+ init_off += dim_idx * aux_data.out_stride[iter];
+ idx /= aux_data.input_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (aux_data.num_broadcast_axes) {
+ // when input shape is one of the follwing forms
+ // (x_1,1) or (x_1,1,x_2) or (1,x_1)
+ // x_1, x_2 are size of the dimensions that are not to be broadcasted
+ // in case of (x_1,1) the system leverages vectorization but in other 2
+ // the performance is improved due avoidance of duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 1 :
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t l=0; l < aux_data.output_shape[aux_data.axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is one of the follwing forms
+ // (x_1,1,x_2,1) or (1,x_1,1,x_2) or (x_1,1,x_2,1,x_3)
+ // x_1, x_2, x_3 are size of the dimensions that are not to be broadcasted
+ // in the inner most loop can be vectorized by compiler in outer loops
+ // the performance is improved due avoidance of duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 2:
+ stride_1 = aux_data.out_stride[aux_data.axes[1]];
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t k=0; k < aux_data.output_shape[aux_data.axes[1]]; k++) {
+ for (index_t l=0; l < aux_data.output_shape[aux_data.axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
Review comment:
nit: space round '*'
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest edited a comment on issue #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest edited a comment on issue #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-616859584
> > Please add more details in the PR description to explain the rationale of this change:
>
> @apeforest
>
> 1. Its there in the PR Heading. Additionally, its being done to improve BERT performance regression when using Large Tensor Build
> 2. Leverages vectorization. Can't explain line by line as to how. Too much text to write. I can share a link about vectorization for reviewers to read. Let me know if you meant something else. I can write 1 line each for 3 cases which is necessary
> 3. I didn't understand this question. Could you clarify what meant by side-effect.
1. The title tells readers this PR will change the performance of broadcast_axis. However, I am not familiar with which tricks/algorithms you employed to make it faster. It would greatly help people understand code if you could mention it in PR description with a few sentences or a pseudo code.
2. vectorization is a very general term. Please add more details here. You could even copy some of them from your code comment
3. Side effect means any downside or potential problem will this change cause. e.g. slow down with other inputs, or not supporting certain inputs, backward compatibility etc.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on issue #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on issue #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-616859584
> > Please add more details in the PR description to explain the rationale of this change:
>
> @apeforest
>
> 1. Its there in the PR Heading. Additionally, its being done to improve BERT performance regression when using Large Tensor Build
> 2. Leverages vectorization. Can't explain line by line as to how. Too much text to write. I can share a link about vectorization for reviewers to read. Let me know if you meant something else. I can write 1 line each for 3 cases which is necessary
> 3. I didn't understand this question. Could you clarify what meant by side-effect.
1. The title tells readers this PR will change the performance of broadcast_axis. However, I am not familiar with which tricks/algorithms you employed to make it faster. It would greatly help people understand code if you could mention it in PR description with a few sentences or a pseudo code.
2. vectorization is a very general term. Please add more details here. You could even copy some of them from your code comment
3. Side effect means any downside or potential problem will this change. e.g. slow down with other inputs, or not supporting certain inputs, backward compatibility etc.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445871587
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (num_broadcast_axes) {
+ // when input shape is amogst one of the form
+ // [(x,1), (x,1,x), (1,x)]
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 1 :
+ stride_0 = out_stride[axes[0]];
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is amogst one of the form
+ // [(x,1,x,1), (1,x,1,x), (x,1,x,1,x)]
+ // x can be any +ve number >1 or =0(the axis ) and they need not be equal to each other
+ case 2:
+ stride_1 = out_stride[axes[1]], stride_0 = out_stride[axes[0]];
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ break;
+ // when input shape is of the form [(1,x,1,x,1)] and
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 3:
+ stride_2 = out_stride[axes[2]], stride_1 = out_stride[axes[1]];
+ stride_0 = out_stride[axes[0]];
+ for (int j=0; j < out_shape[axes[2]]; j++) {
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + j*stride_2 + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ }
+ break;
+ }
Review comment:
In that case, could you add an assertion around line: https://github.com/apache/incubator-mxnet/pull/17882/files#diff-b669acf192ce8ff1658871e6d9dcca5dR1095
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on pull request #17882: [WIP]Improve CPU performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-646309265
@apeforest
SSD 1 epoch time master(int32 w/o large tensor) : 230sec
SSD 1 epoch time optimized broadcast_axis for CPU(int64 large tensor) : 190sec
Still unable to fix the case:
(1, 1, 1, 1)->(1000, 10, 100, 5): 125 sec as compared to 65 sec
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r446069194
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (num_broadcast_axes) {
+ // when input shape is amogst one of the form
+ // [(x,1), (x,1,x), (1,x)]
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 1 :
+ stride_0 = out_stride[axes[0]];
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is amogst one of the form
+ // [(x,1,x,1), (1,x,1,x), (x,1,x,1,x)]
+ // x can be any +ve number >1 or =0(the axis ) and they need not be equal to each other
+ case 2:
+ stride_1 = out_stride[axes[1]], stride_0 = out_stride[axes[0]];
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ break;
+ // when input shape is of the form [(1,x,1,x,1)] and
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 3:
+ stride_2 = out_stride[axes[2]], stride_1 = out_stride[axes[1]];
+ stride_0 = out_stride[axes[0]];
+ for (int j=0; j < out_shape[axes[2]]; j++) {
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + j*stride_2 + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ }
+ break;
+ }
Review comment:
Done!
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r411024747
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,52 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
+ int iter = dst_shape.ndim() - 1, i = 0;
+ out_stride[iter] = 1;
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ --iter;
+ for (; iter >= 0; --iter) {
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ out_stride[iter] = out_stride[iter+1] * dst_shape[iter+1];
+ }
if (dst_shape.ndim() == 2) {
Tensor<xpu, 2, OType> out =
outputs[0].get_with_shape<xpu, 2, OType>(dst_shape.get<2>(), s);
Tensor<xpu, 2, IType> data =
inputs[0].get_with_shape<xpu, 2, IType>(src_shape.get<2>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], 2);
+ if (!enable_lt) {
+ typedef int32_t index_t;
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ } else {
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ }
} else {
const int ndim = MXNET_SPECIAL_MAX_NDIM;
Tensor<xpu, ndim, OType> out =
outputs[0].get_with_shape<xpu, ndim, OType>(dst_shape.get<ndim>(), s);
Tensor<xpu, ndim, IType> data =
inputs[0].get_with_shape<xpu, ndim, IType>(src_shape.get<ndim>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], ndim);
+ if (!enable_lt) {
Review comment:
Here are the results after removing typedef and enable_lt conditional check
| code version | cases | avg | p50 | p90 |
|--------------|---------------------------------------------|--------|--------|--------|
| master LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 28.89 | 26.91 | 34.51 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 28.70 | 26.45 | 34.03 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 123.14 | 121.88 | 125.35 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 65.18 | 61.52 | 74.58 |
| | | | | |
| master no-LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 13.82 | 13.24 | 16.83 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 13.46 | 13.00 | 16.18 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 52.38 | 51.36 | 53.51 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 35.29 | 38.65 | 40.23 |
| | | | | |
| new LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 15.91 | 15.79 | 18.23 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 16.44 | 17.50 | 17.97 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 124.17 | 125.65 | 126.42 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 37.33 | 36.76 | 38.07 |
| | | | | |
| new no-LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 9.76 | 9.91 | 11.98 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 9.04 | 9.54 | 9.96 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 58.40 | 60.54 | 61.01 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 23.45 | 23.11 | 26.79 |
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-650484776
@apeforest can you review. I have addressed your comments
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445868275
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1125,8 +1221,14 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
using namespace mshadow::expr;
using namespace mxnet_op;
mxnet::TShape src_shape, dst_shape;
+ // combines 2 or more consecutive broadcast/non-broadcast axes together
+ // e.g. (3,4,1,1,5,1,6,7) (2,3,5) (5,10,9) -> (3*4,1*1,5,1,6*7) (1,3) (5*10, 9)
+ // -> (12,1,5,1,42) (1,3) (50, 9)
+ // and this is the new input for broadcast_kernel whose total
+ // num of dimensions cannot be greater than 5(throws an error otherwise).
BroadcastReduceShapeCompact(outputs[0].shape_, small, &dst_shape, &src_shape);
Stream<xpu> *s = ctx.get_stream<xpu>();
+ bool isCPU = ctx.run_ctx.get_ctx().dev_type == Context::kCPU;
Review comment:
You can just use `if (std::is_same<xpu, cpu>::value)` right?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-648596357
@apeforest I am investigating the windows CI timeout on my PR. In the meantime can you review ?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445872765
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1125,8 +1221,14 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
using namespace mshadow::expr;
using namespace mxnet_op;
mxnet::TShape src_shape, dst_shape;
+ // combines 2 or more consecutive broadcast/non-broadcast axes together
+ // e.g. (3,4,1,1,5,1,6,7) (2,3,5) (5,10,9) -> (3*4,1*1,5,1,6*7) (1,3) (5*10, 9)
+ // -> (12,1,5,1,42) (1,3) (50, 9)
+ // and this is the new input for broadcast_kernel whose total
+ // num of dimensions cannot be greater than 5(throws an error otherwise).
BroadcastReduceShapeCompact(outputs[0].shape_, small, &dst_shape, &src_shape);
Stream<xpu> *s = ctx.get_stream<xpu>();
+ bool isCPU = ctx.run_ctx.get_ctx().dev_type == Context::kCPU;
Review comment:
good point .. let me try it
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445871712
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (num_broadcast_axes) {
+ // when input shape is amogst one of the form
+ // [(x,1), (x,1,x), (1,x)]
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 1 :
+ stride_0 = out_stride[axes[0]];
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is amogst one of the form
+ // [(x,1,x,1), (1,x,1,x), (x,1,x,1,x)]
+ // x can be any +ve number >1 or =0(the axis ) and they need not be equal to each other
+ case 2:
+ stride_1 = out_stride[axes[1]], stride_0 = out_stride[axes[0]];
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ break;
+ // when input shape is of the form [(1,x,1,x,1)] and
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 3:
+ stride_2 = out_stride[axes[2]], stride_1 = out_stride[axes[1]];
+ stride_0 = out_stride[axes[0]];
+ for (int j=0; j < out_shape[axes[2]]; j++) {
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + j*stride_2 + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ }
+ break;
+ }
Review comment:
i.e. aux_data->num_broadcast_axes = i;
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r411540591
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
Review comment:
shall we use `int` for ndim as we do for all other places?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-650481684
@mxnet-label-bot add [pr-awaiting-review]
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-646939424
Code | SSD 1 Epoch time (sec) | %age Speedup/Slowdown w.r.t Master (large tensor disabled)
-- | -- | --
Master (large tensor disabled) | 226 | 0
Master (large tensor enabled) | 335 | 48.23% slowdown
Master + CPU Optimized broadcast_axis (large tensor disabled) | 130 | 42.5% speedup
Master + CPU Optimized broadcast_axis (large tensor enabled) | 184 | 18.5% speedup
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445916032
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1147,16 +1249,26 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
outputs[0].get_with_shape<xpu, 2, OType>(dst_shape.get<2>(), s);
Tensor<xpu, 2, IType> data =
inputs[0].get_with_shape<xpu, 2, IType>(src_shape.get<2>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ if (isCPU) {
+ Kernel<broadcast_kernel_cpu<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ } else {
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ }
} else {
const int ndim = MXNET_SPECIAL_MAX_NDIM;
Tensor<xpu, ndim, OType> out =
outputs[0].get_with_shape<xpu, ndim, OType>(dst_shape.get<ndim>(), s);
Tensor<xpu, ndim, IType> data =
inputs[0].get_with_shape<xpu, ndim, IType>(src_shape.get<ndim>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], ndim);
+ if (isCPU) {
+ Kernel<broadcast_kernel_cpu<mshadow_op::identity>, xpu>::Launch(
Review comment:
Kernel<broadcast_kernel_cpu<mshadow_op::identity>, cpu> actually causes build failure and gives the following error:
```
../src/operator/nn/./../tensor/broadcast_reduce_op.h(1246): error: no instance of overloaded function "mxnet::op::mxnet_op::Kernel<OP, mxnet::cpu>::Launch [with OP=mxnet::op::broadcast_kernel_cpu<mxnet::op::mshadow_op::identity>]" matches the argument list
argument types are: (mshadow::Stream<mshadow::gpu> *, mshadow::index_t, float *, float *, mxnet::op::<unnamed>::ShapeAndStride, const mxnet::OpReqType, int)
detected during:
instantiation of "void mxnet::op::BroadcastComputeImpl<xpu>(const nnvm::NodeAttrs &, const mxnet::OpContext &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const std::vector<mxnet::OpReqType, std::allocator<mxnet::OpReqType>> &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const mxnet::TShape &) [with xpu=mxnet::gpu]"
../src/operator/nn/./moments-inl.h(215): here
instantiation of "void mxnet::op::MomentsBackwardImpl<xpu>(const nnvm::NodeAttrs &, const mxnet::OpContext &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const std::vector<mxnet::OpReqType, std::allocator<mxnet::OpReqType>> &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const dmlc::optional<mxnet::TShape> &) [with xpu=mxnet::gpu]"
../src/operator/nn/./moments-inl.h(249): here
instantiation of "void mxnet::op::MomentsBackward<xpu>(const nnvm::NodeAttrs &, const mxnet::OpContext &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const std::vector<mxnet::OpReqType, std::allocator<mxnet::OpReqType>> &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &) [with xpu=mxnet::gpu]"
../src/operator/nn/moments.cu(36): here
```
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1147,16 +1249,26 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
outputs[0].get_with_shape<xpu, 2, OType>(dst_shape.get<2>(), s);
Tensor<xpu, 2, IType> data =
inputs[0].get_with_shape<xpu, 2, IType>(src_shape.get<2>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ if (isCPU) {
+ Kernel<broadcast_kernel_cpu<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ } else {
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ }
} else {
const int ndim = MXNET_SPECIAL_MAX_NDIM;
Tensor<xpu, ndim, OType> out =
outputs[0].get_with_shape<xpu, ndim, OType>(dst_shape.get<ndim>(), s);
Tensor<xpu, ndim, IType> data =
inputs[0].get_with_shape<xpu, ndim, IType>(src_shape.get<ndim>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], ndim);
+ if (isCPU) {
+ Kernel<broadcast_kernel_cpu<mshadow_op::identity>, xpu>::Launch(
Review comment:
`Kernel<broadcast_kernel_cpu<mshadow_op::identity>, cpu>` actually causes build failure and gives the following error:
```
../src/operator/nn/./../tensor/broadcast_reduce_op.h(1246): error: no instance of overloaded function "mxnet::op::mxnet_op::Kernel<OP, mxnet::cpu>::Launch [with OP=mxnet::op::broadcast_kernel_cpu<mxnet::op::mshadow_op::identity>]" matches the argument list
argument types are: (mshadow::Stream<mshadow::gpu> *, mshadow::index_t, float *, float *, mxnet::op::<unnamed>::ShapeAndStride, const mxnet::OpReqType, int)
detected during:
instantiation of "void mxnet::op::BroadcastComputeImpl<xpu>(const nnvm::NodeAttrs &, const mxnet::OpContext &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const std::vector<mxnet::OpReqType, std::allocator<mxnet::OpReqType>> &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const mxnet::TShape &) [with xpu=mxnet::gpu]"
../src/operator/nn/./moments-inl.h(215): here
instantiation of "void mxnet::op::MomentsBackwardImpl<xpu>(const nnvm::NodeAttrs &, const mxnet::OpContext &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const std::vector<mxnet::OpReqType, std::allocator<mxnet::OpReqType>> &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const dmlc::optional<mxnet::TShape> &) [with xpu=mxnet::gpu]"
../src/operator/nn/./moments-inl.h(249): here
instantiation of "void mxnet::op::MomentsBackward<xpu>(const nnvm::NodeAttrs &, const mxnet::OpContext &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &, const std::vector<mxnet::OpReqType, std::allocator<mxnet::OpReqType>> &, const std::vector<mxnet::TBlob, std::allocator<mxnet::TBlob>> &) [with xpu=mxnet::gpu]"
../src/operator/nn/moments.cu(36): here
```
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445868759
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1114,6 +1124,92 @@ struct broadcast_kernel {
}
};
+/**
+ * Changed the thread workload mapping from 1
+ * thread/output element to 1 thread/input to be broadcasted
+ * This approach leverages vectorization when fastest varying
+ * index(stride=1) of the tensor is to be broadcasted.
+ * In other cases it simply performs better by better load balancing.
+ */
+template<typename OP>
+struct broadcast_kernel_cpu {
+ template<typename IType, typename OType>
+ MSHADOW_XINLINE static void Map(index_t i,
+ IType *input,
+ OType *output,
+ const ShapeAndStride& aux_data,
+ const OpReqType req,
+ const int ndim) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % aux_data.input_shape[iter];
+ init_off += dim_idx * aux_data.out_stride[iter];
+ idx /= aux_data.input_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (aux_data.num_broadcast_axes) {
+ // when input shape is one of the follwing forms
+ // (x_1,1) or (x_1,1,x_2) or (1,x_1)
+ // x_1, x_2 are size of the dimensions that are not to be broadcasted
+ // in case of (x_1,1) the system leverages vectorization but in other 2
+ // the performance is improved due avoidance of duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 1 :
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t l=0; l < aux_data.output_shape[aux_data.axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is one of the follwing forms
+ // (x_1,1,x_2,1) or (1,x_1,1,x_2) or (x_1,1,x_2,1,x_3)
+ // x_1, x_2, x_3 are size of the dimensions that are not to be broadcasted
+ // in the inner most loop can be vectorized by compiler in outer loops
+ // the performance is improved due avoidance of duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 2:
+ stride_1 = aux_data.out_stride[aux_data.axes[1]];
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t k=0; k < aux_data.output_shape[aux_data.axes[1]]; k++) {
+ for (index_t l=0; l < aux_data.output_shape[aux_data.axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ break;
+ // when input shape is of the form (1,x_1,1,x_2,1)
+ // x_1, x_2 are size of the dimensions that are not to be broadcasted
+ // here the last axis which is [4] is the one where compiler can vectorize
+ // the code the outer 2 loops improve preformance by avoiding
+ // duplicate stride calculations
+ // for each output location input[i] needs to be written to.
+ case 3:
+ stride_2 = aux_data.out_stride[aux_data.axes[2]];
+ stride_1 = aux_data.out_stride[aux_data.axes[1]];
+ stride_0 = aux_data.out_stride[aux_data.axes[0]];
+ for (index_t j=0; j < aux_data.output_shape[aux_data.axes[2]]; j++) {
Review comment:
nit: add space around "="
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit removed a comment on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit removed a comment on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-650083468
@mxnet-bot run ci [unix-cpu, clang, website, centos-cpu, edge, miscellaneous, unix-gpu, windows-gpu, centos-gpu, windows-cpu]
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] szha merged pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
szha merged pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] apeforest commented on a change in pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
apeforest commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r445867111
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1147,16 +1249,26 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
outputs[0].get_with_shape<xpu, 2, OType>(dst_shape.get<2>(), s);
Tensor<xpu, 2, IType> data =
inputs[0].get_with_shape<xpu, 2, IType>(src_shape.get<2>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ if (isCPU) {
+ Kernel<broadcast_kernel_cpu<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, aux_data, req[0], 2);
+ } else {
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
Review comment:
Maybe rename broadcast_kernel to broadcast_kernel_gpu for better readability?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on issue #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on issue #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-616680186
@ptrendx This is mainly optimizing for CPU. Can you review again?
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on pull request #17882: Improve performance of broadcast_axis on CPU
Posted by GitBox <gi...@apache.org>.
access2rohit commented on pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#issuecomment-647616132
@mxnet-bot run ci [all]
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull request #17882: Improve performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r411024747
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1103,21 +1132,52 @@ inline void BroadcastComputeImpl(const nnvm::NodeAttrs& attrs,
out_shape[i] = 1;
}
}
+ uint64_t axes[dst_shape.ndim()], out_stride[dst_shape.ndim()];
+ int iter = dst_shape.ndim() - 1, i = 0;
+ out_stride[iter] = 1;
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ --iter;
+ for (; iter >= 0; --iter) {
+ if (in_shape[iter] != dst_shape[iter]) {
+ axes[i] = iter;
+ i++;
+ }
+ out_stride[iter] = out_stride[iter+1] * dst_shape[iter+1];
+ }
if (dst_shape.ndim() == 2) {
Tensor<xpu, 2, OType> out =
outputs[0].get_with_shape<xpu, 2, OType>(dst_shape.get<2>(), s);
Tensor<xpu, 2, IType> data =
inputs[0].get_with_shape<xpu, 2, IType>(src_shape.get<2>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], 2);
+ if (!enable_lt) {
+ typedef int32_t index_t;
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ } else {
+ Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
+ s, data.shape_.Size(), data.dptr_, out.dptr_, in_shape,
+ out_shape, req[0], 2, axes, out_stride, 1);
+ }
} else {
const int ndim = MXNET_SPECIAL_MAX_NDIM;
Tensor<xpu, ndim, OType> out =
outputs[0].get_with_shape<xpu, ndim, OType>(dst_shape.get<ndim>(), s);
Tensor<xpu, ndim, IType> data =
inputs[0].get_with_shape<xpu, ndim, IType>(src_shape.get<ndim>(), s);
- Kernel<broadcast_kernel<mshadow_op::identity>, xpu>::Launch(
- s, out.shape_.Size(), data.dptr_, out.dptr_, in_shape, out_shape, req[0], ndim);
+ if (!enable_lt) {
Review comment:
@apeforest
Here are the results after removing typedef and enable_lt conditional check(I haven't pushed that code into this yet yet). There is a slight improvement in the results. But its not that significant.
| code version | cases | avg | p50 | p90 |
|--------------|---------------------------------------------|--------|--------|--------|
| master LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 28.89 | 26.91 | 34.51 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 28.70 | 26.45 | 34.03 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 123.14 | 121.88 | 125.35 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 65.18 | 61.52 | 74.58 |
| | | | | |
| master no-LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 13.82 | 13.24 | 16.83 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 13.46 | 13.00 | 16.18 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 52.38 | 51.36 | 53.51 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 35.29 | 38.65 | 40.23 |
| | | | | |
| new LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 15.91 | 15.79 | 18.23 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 16.44 | 17.50 | 17.97 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 124.17 | 125.65 | 126.42 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 37.33 | 36.76 | 38.07 |
| | | | | |
| new no-LT | (1000, 1, 100, 1)->(1000, 10, 100, 5) | 9.76 | 9.91 | 11.98 |
| | (1000, 1, 1, 100)->(1000, 10, 5, 100) | 9.04 | 9.54 | 9.96 |
| | (1, 1, 1, 1)->(1000, 10, 100, 5) | 58.40 | 60.54 | 61.01 |
| | (1, 1000, 1, 100, 1)->(2, 1000, 10, 100, 5) | 23.45 | 23.11 | 26.79 |
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [incubator-mxnet] access2rohit commented on a change in pull request #17882: [WIP]Improve CPU performance of broadcast_axis
Posted by GitBox <gi...@apache.org>.
access2rohit commented on a change in pull request #17882:
URL: https://github.com/apache/incubator-mxnet/pull/17882#discussion_r442511375
##########
File path: src/operator/tensor/broadcast_reduce_op.h
##########
@@ -1058,22 +1065,58 @@ struct broadcast_kernel {
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> in_shape,
mshadow::Shape<MXNET_SPECIAL_MAX_NDIM> out_shape,
const OpReqType req,
- const uint32_t ndim) {
- size_t in_stride = 1;
- size_t out_stride = 1;
- index_t idx = i;
- index_t in_idx = i;
- for (int iter = ndim - 1; iter >= 0; --iter) {
- size_t dim_idx = idx % out_shape[iter];
- in_idx -= dim_idx * out_stride;
- if (in_shape[iter] != 1) {
- in_idx += dim_idx * in_stride;
- }
- idx /= out_shape[iter];
- in_stride *= in_shape[iter];
- out_stride *= out_shape[iter];
- }
- KERNEL_ASSIGN(output[i], req, OP::Map(input[in_idx]));
+ const uint32_t ndim,
+ const size_t *axes,
+ const size_t *out_stride,
+ const int num_broadcast_axes) {
+ index_t idx = i;
+ index_t init_off = 0;
+ for (int iter = ndim - 1; idx > 0 && iter >= 0; --iter) {
+ size_t dim_idx = idx % in_shape[iter];
+ init_off += dim_idx * out_stride[iter];
+ idx /= in_shape[iter];
+ }
+ index_t stride_0, stride_1, stride_2;
+ // Each case is based on the number of axis to be broadcasted
+ // (1, 2 or 3) after merging axes.
+ switch (num_broadcast_axes) {
+ // when input shape is amogst one of the form
+ // [(x,1), (x,1,x), (1,x)]
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 1 :
+ stride_0 = out_stride[axes[0]];
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ break;
+ // when input shape is amogst one of the form
+ // [(x,1,x,1), (1,x,1,x), (x,1,x,1,x)]
+ // x can be any +ve number >1 or =0(the axis ) and they need not be equal to each other
+ case 2:
+ stride_1 = out_stride[axes[1]], stride_0 = out_stride[axes[0]];
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ break;
+ // when input shape is of the form [(1,x,1,x,1)] and
+ // x can be any +ve number >=0 and they need not be equal to each other
+ case 3:
+ stride_2 = out_stride[axes[2]], stride_1 = out_stride[axes[1]];
+ stride_0 = out_stride[axes[0]];
+ for (int j=0; j < out_shape[axes[2]]; j++) {
+ for (int k=0; k < out_shape[axes[1]]; k++) {
+ for (int l=0; l < out_shape[axes[0]]; l++) {
+ KERNEL_ASSIGN(output[init_off + j*stride_2 + k*stride_1 + l*stride_0],
+ req, OP::Map(input[i]));
+ }
+ }
+ }
+ break;
+ }
Review comment:
WIll update with default choice. Though it should ideally be unreachable.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org