You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tvm.apache.org by GitBox <gi...@apache.org> on 2021/08/04 16:23:31 UTC
[GitHub] [tvm-rfcs] MeeraN7 opened a new pull request #18: [RFC] Adding initial SVE implementation
MeeraN7 opened a new pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18
Introducing the addition of Arm Architecture's Scalable Vector Extension (SVE) in TVM containing initial VLA and predication implementation, based on earlier work by Giuseppe Rossini.
@mbaret
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi edited a comment on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi edited a comment on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893037035
I think it is a good idea to invite people working on RISC-V support for TVM for review/discuss, since the RISC V vector extension is similar to ARM SVE. I remember some people in Taiwan are working on this. Maybe @comaniac knows who?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tkonolige commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tkonolige commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r682981173
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
Review comment:
Can you define "scalable vectorization" in this paragraph.
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
+at compile time, and so we use VL as a way of representing that.
+
+## Implementation
+
+An agnostic constructor has been added to the Ramp node, as well as to the
+Broadcast node, with an additional parameter. This parameter is a boolean named
+_is_scalable_, in order to enable both fixed and scalable vectorisation.
+
+This boolean has also been added in _data_type.h_ as the type of the Ramp node
+has changed, it is now scalable. The constructor is:
+
+```
+DataType(int code, int bits, int lanes, bool is_scalable = false)
Review comment:
Why not use a special value for lanes to indicate that it can be a variable number?
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
+at compile time, and so we use VL as a way of representing that.
+
+## Implementation
+
+An agnostic constructor has been added to the Ramp node, as well as to the
+Broadcast node, with an additional parameter. This parameter is a boolean named
+_is_scalable_, in order to enable both fixed and scalable vectorisation.
+
+This boolean has also been added in _data_type.h_ as the type of the Ramp node
+has changed, it is now scalable. The constructor is:
+
+```
+DataType(int code, int bits, int lanes, bool is_scalable = false)
+```
+
+Originally, for fixed vectorisation, _is_scalable_ will be false, but when
+scalable vectorisation is enabled we will set _is_scalable_ to true.
+
+The _vectorize_scalable_ function triggers the transformations on the loops to
+make them scalable, by triggering a new pass called VectorizeLoopScalable. This
+pass visits the TIR nodes and transforms them so that they account for the
+unknown vector length. Currently, our prototype was implemented before the
+addition of the While node to TVM, and so it generates a variable for loop. One
+change we are planning to make is transforming a for loop into a while loop
+with unknown vector length directly, as that is what would be generated in the
+assembly.
+
+This is all handled on the TE and TIR end, but for code generation we introduce
+a file called codegen_aarch64.cc which handles the creation of SVE intrinsics
+in LLVM by visiting the Load, Store and For nodes (to be replaced with a While
+node) and generating the relevant LLVM IR.
+
Review comment:
Please include a drawbacks section.
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
Review comment:
You mention predication here, yet you never talk about how it is being added to TIR.
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
Review comment:
What do you think about adding a new `ForKind` so that we can express scalable vectorization in TIR.
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
Review comment:
We already have a concept of an unknown scalar value at compile time: `Any`. It seems like you could just have the lanes of Ramp be a PrimExpr instead of an int. Is there are reason not to take this approach?
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
Review comment:
Is this PR talking about using predicated vector instructions or scalable vector instructions? If you aren't talking about predicated vector instructions, you could probably just remove this paragraph.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] MeeraN7 commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
MeeraN7 commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-894160388
Thank you @giuseros for your answer, it looked good to me. Just to add on, we know which loops need to be legalised as in TIR we do add a new `ForKind` called `kVectorizedScalable` (cc @tkonolige) which marks the loop as able to be vectorized but the value of VL is unknown. These loops are then legalised and transformed to include the unknown value VL and later passed to the code generator as @giuseros mentioned.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] giuseros commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
giuseros commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r700256124
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
+at compile time, and so we use VL as a way of representing that.
+
+## Implementation
+
+An agnostic constructor has been added to the Ramp node, as well as to the
+Broadcast node, with an additional parameter. This parameter is a boolean named
+_is_scalable_, in order to enable both fixed and scalable vectorisation.
+
+This boolean has also been added in _data_type.h_ as the type of the Ramp node
+has changed, it is now scalable. The constructor is:
+
+```
+DataType(int code, int bits, int lanes, bool is_scalable = false)
+```
+
+Originally, for fixed vectorisation, _is_scalable_ will be false, but when
+scalable vectorisation is enabled we will set _is_scalable_ to true.
+
+In TIR we introduced a new ForKind called _kVectorizeScalable_ which marks a
+loop as able to be vectorized but the value of VL will be unknown. This loop
+is then legalised during a new pass called _VectorizeLoopScalable_ pass, which
+is triggered by the vectorize_scalable function mentioned previously. This pass
+transforms the loop so that it is able to handle the unknown constant VL. Our
+prototype was implemented before the addition of the While node to TVM, and so
+it currently transforms a For loop into a variable For loop. To do this, the For
+node had to have extra parameters added to its implementation that would only be
+used in this one specific case. One change we are planning to make is to make use
+of this existing While node and transform a For Loop into a While loop during the
+_VectorizeLoopScalable_ pass, since it is the more natural choice and it is what
+will be generated in the assembly as well. Once the loop has been legalised, it
+is passed to the code generator which will translate it to the relevant LLVM SVE
+instrinsics. The intrinsics involved are for predicated load/stores, loop
+increments and predication mask calculation. While predication is not implemented
+as a TIR construct, it is used to support VLA.
+
+This is all handled on the TE and TIR end, but for code generation we introduce
+a file called codegen_aarch64.cc which handles the creation of SVE intrinsics
+in LLVM by visiting the Load, Store and For nodes (to be replaced with a While
+node) and generating the relevant LLVM IR. For the above TIR output, the expected
+LLVM IR would be:
+```
+for_body: ; preds = %for_body, %entry
+ %indvars.iv = phi i64 [ %indvars.iv.next, %for_body ], [ 0, %entry ]
+ %8 = trunc i64 %indvars.iv to i32
+ %9 = tail call <vscale x 4 x i1> @llvm.aarch64.sve.whilelt.nxv4i1.i32(i32 %8, i32 17)
+ %10 = getelementptr inbounds float, float* %4, i64 %indvars.iv
+ %11 = tail call <vscale x 4 x float> @llvm.aarch64.sve.ld1.nxv4f32(<vscale x 4 x i1> %9, float* %10)
+ %12 = getelementptr inbounds float, float* %5, i64 %indvars.iv
+ %13 = tail call <vscale x 4 x float> @llvm.aarch64.sve.ld1.nxv4f32(<vscale x 4 x i1> %9, float* %12)
+ %14 = fadd <vscale x 4 x float> %11, %13
+ %15 = getelementptr inbounds float, float* %6, i64 %indvars.iv
+ tail call void @llvm.aarch64.sve.st1.nxv4f32(<vscale x 4 x float> %14, <vscale x 4 x i1> %9, float* %15)
+ %indvars.iv.next = add i64 %indvars.iv, %7
+ %16 = icmp slt i64 %indvars.iv, 17
+ br i1 %16, label %for_body, label %for_end, !prof !5
+```
+In the IR above we have:
+* the `whilelt` target specific SVE intrinsic, which generates a mask
+(variable %9) based on the induction variable (%8) and the loopbound (i32 17).
+This mask is only consumed by load/store instructions/intrinsics (and not e.g.
+data processing instructions such as the fadd), which is how predication is
+currently modeled in LLVM.
+* `<vscale x 4 x float>` is a scalable vector of 4 float elements
+* `<vscale x 4 x i1>` is the scalable mask consisting of 4 boolean values.
+
+
+## Drawbacks
+1. We've not been able to reuse existing code for this prototype, instead we have
+a whole a new vectorization pass and a new code generator for AArch64 specific
+intrinsics.
+2. In addition to this, we have created a new scheduling primitive which will need
+support and maintenance. This also means that the autotuner and autoscheduler must
+be modified to include the new rules needed for this primitive. These new rules are
+not supported in this prototype but have been noted as extension work in the future.
+
+## Next Steps
+
+As this is a prototype, we are aware that there are still areas that need
+further work:
+1. Our prototype was written before the While node work was merged. Instead of
+ creating a separate variable For-loop we should be using a While node, as
+ mentioned above. We think this is a straightforward rewrite, and with this
+ rewrite completed we think that this work lays the non-user facing part and
+ foundation for scalable vectorisation.
+2. The user facing part includes work to support the auto-scheduler and
+ auto-tuner will also need to be added. This would enable us to generate a
+ schedule that will call _vectorise_scalable_ and thus perform scalable
+ vectorisation, allowing users to benefit from this addition.
Review comment:
In addition to what @sjoerdmeijer pointed out in his comment, I wanted to underline that if we enable SVE via a target attribute, this means TVM will always vectorize through a scalable vectorization, i.e., always adding a while loop (or a variable for loop). This might not always bring out the best performance because for small loops it might be worth using a simpler NEON vectorization. Also, depending on the arch, it might be possible that mixing SVE and NEON could make better use of all the functional units. All in all, if we see any benefits in mixing fixed and scalable vectorizations, the type of vectorization needs to be decided at primitive level (either through `vectorize(..., scalable)` or `vectorize_scalable(..)` )
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] giuseros commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
giuseros commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893870692
HI @tqchen ,
I will try to sporadically comment, since this is a project I prototyped (and enjoyed :) ) when I was in Arm.
If I understand your comment correctly, what @MeeraN7 is doing is closer to what you are proposing. Instead of transforming a loop into a Ramp, and passing the ramp "as is" to LLVM (which is what is done for fixed vector length, but *not doable* for SVE) @MeeraN7 is legalising the loop in TIR and passing the legal loop down to the LLVM code-generator. In other words, the following loop:
```
for i = 1:1:10
A[i] = B[i]+C[i];
end
```
Once legalised becomes
```
for i = 1:VL:10
A[VL] = B[VL]+C[VL]
end
```
And then the LLVM code generator, knowing that this is a variable loop, translates this it with some LLVM intrinsics for:
* Predicated load/store
* Loop increment
* Predication mask calculation
Please note that only load/store needs to be predicated. Other register-to-register operations (e.g., add/sub/mul) won't need predication.
Please also note that while predication is not a TIR concept, we use it to support VLA (cc @tkonolige) in the LLVM codegen. In future it should be quite straightforward to expose predication also in TIR (if required).
@MeeraN7 feel free to jump in if something I said is not correct (very likely :) )
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-930488098
Thanks @sjoerdmeijer , sorry for getting back to this late. If LLVM also encodes the SVE vector as a special type(and not tying the n) it could be a precedence that we can learn from. I do want to point out that the same approach won't work when it comes to scalable matrix instruction, so it would be good to think about a loop pattern based approach from that angle.
If we conclude that we really want to introduce the scalable vector into data type and so on. A remaining thing we need to resolve is the encoding. DataType and DLDataType are part of DLPack standard, used as standard ABI convention. So ideally we do not want to change the type signature of DataType DLDataType. What we might be able to is to introduce a magic lane number (say `DataType::kScalableVectorLaneMark = -1`) that indicate a scalable vector type, and also use similar approaches for other language construct as well. This would alleviate the problems from that side.
This being said. It would still be good to get @MeeraN7 @giuseros @sjoerdmeijer 's take on the possibility of using a normalized loop pattern vs embedding into the vector.
Thank you for all the discussions so far!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] hogepodge commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
hogepodge commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r705787815
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
Review comment:
Within markdown, code is typically denoted with a pair`back single quotes` surrounding the code. I suggest using that as the convention to enclose methods, variables, and other code.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen edited a comment on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen edited a comment on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-916553296
Thanks @MeeraN7 @giuseros, to make the discussion more concrete, right now the IR after legalization looks like
```c++
for (i: int32, 0, 17;i+=VL) {
C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
}
```
This would require changes such as the ramp data structure and data type to support the VL vector types, which can be a bit adhoc because there are also additional information needed to be encoded(e.g. this VL and that VL are the same) but nevertheless not clearly encoded here.
Given we are mostly matching a for pattern, I also wonder if they are really necessary. Since we could represent a VLA loop with some form of restricted for loop, with special annotations. Here is a possible alternative way to do so
```c++
for (i: int32, 0, 17;i, annotation={"VLA"}) {
C_2[i] = A_2[i] + B_2[i];
}
```
And we will be defering the vectorized instruction generation to the codegen phase, by specially handling the patterns in the for that is annotated with VLA loop. Of course we can only support a limited set of patterns(such as read/write to the same vector index or limited reduction support), that is why legalize is needed to make sure the body of VLA for loop satiesfies the pattern.
In this way we can likely get a similar set of things without hacking into get a ramp with VL size
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697183013
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
Review comment:
Since `s[C].vectorize(x)` doesn't specify the vector length and the specific length is deduced from the target string by LLVM codegen (e.g. `llvm -mcpu=core-avx2`), I wonder if `s[C].vectorize_scalable(x)` is really necessary.
Instead, can we decide whether or not to enable scalable vectors by an appropriate target attribute?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] MeeraN7 commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
MeeraN7 commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893458074
@sjoerdmeijer @giuseros
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-940411463
@kparzysz-quic this is right. On the other hand, we still on conversion of DLDataType and DataType(e.g. getting DataType from ndarray) in many cases. So ideally we want to keep them consistent
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] sjoerdmeijer commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
sjoerdmeijer commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-933235514
Hi @tqchen , thanks for the great feedback!
> This being said. It would still be good to get @MeeraN7 @giuseros @sjoerdmeijer 's take on the possibility of using a normalized loop pattern vs embedding into the vector.
Yes, I can see that as being very useful. If my analogy is correct, the loop annotation corresponds to a loop pragma, and the scalable ramp/vector node to an IR extension. Like I wrote before, I think there's place for both of these concepts.
Can you please advise how to proceed? I guess we need to document this in the RFC. But do we want to prototype this too? Or do we just list it as an alternative, and discuss here what we would like to do first?
I have not yet commented on your remark about the ABI convention, as I am not familiar enough with TVM to comment about this. It looks though that is a solvable problem.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697187201
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
Review comment:
The semantics does change, doesn't it? Because in your example `C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`, 17 is not the length of a vector, but its the size of an input. While in the SVE example above the input length is explicitly divided by the vector length at TIR level.
Of course, I understand that the semantics of `Ramp` node in general does not change.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] sjoerdmeijer commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
sjoerdmeijer commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-917576240
Thanks for commenting @tqchen
Could you further clarify a few things for me please? See remarks inlined.
> Thanks @MeeraN7 . Yes I get what you mean. Right now we are adding a "is_scalable" field to indicate that the broadcast and ramp are "context dependent" on VL. Additionally, we might need to update DataType to indicate a scalable data type.
>
> This context dependency is the missing information I mentioned here.
I don't think I understand what you mean by context dependency. Basically, in my view of the world, the Ramp node means that we can process elements in a data parallel way. How exactly this is done, is up to backends depending on the architecture and the code. What we are doing here is annotating this Ramp node with a bit of state, which is a hint that we want a special kind of vectorisation. From this point of view it is syntactic sugar: if the hint is dropped or ignored, it could still be vectorised, but not in a vector length agnostic way.
I don't think we need to encode much more information than one boolean that specifies the vectorisation style. You could indeed argue that this is ad-hoc, but if we are going to do it in a different way, we would still need to keep a bit of state around, like the `annotation={"VLA"}` example that you gave earlier. From that point of view, I don't see any difference.
> The set of code is really undefined and should be parameterized by VL.
What do you mean by undefined here?
> Additionally, considering the case of two loops with different VL1 and VL2 and want to do some transformations, we might fall into the trap of thinking them as same type(because only "is_scalable" is marked) but in reality they are not, as a implicit dependency on VL can be ignored.
>
> I can understand that the additional flag can be helpful as we could reuse some of the vectorization logic. However, the "is_scalable" field might introduce additional confusion as above, and the additional ramp node may not carry too much additional information(apart from the fact that we use a scalar vs a vector type). So my main question is that whether or not we could use a separate normal form to hint the code generator without changing the current DataType, ramp and broadcast.
Correct me if I am wrong, but your assumption is that explicit scalable state is bad. Looking at your example:
> **N1: A possible loop normal form via annotation**
>
> ```
> for (i: int32, 0, 17;i, annotation={"VLA"}) {
> C_2[i] = A_2[i] + B_2[i];
> }
> ```
This annotation looks equivalent to a loop pragma. In Clang you can for example do:
```
#pragma loop vectorize_width(4, scalable)
for (I =0; I<17; ++i) {
C_2[i] = A_2[i] + B_2[I];
}
```
and thus request scalable vectorisation. If this annotation results in scalable vectorisation, the LLVM vectoriser will lower this to operations using `<n x 4 x i32>` scalable vector IR types.
What I would like to say with these examples, is that there are 2 things going on at different levels. I think:
- The `annotation={"VLA"}` corresponds to a loop pragma in Clang,
- The TIR Ramp node extension corresponds to LLVM IR scalable types, e.g. `<n x 4 x i32>`.
And I think these 2 concepts are different things that both have their value and place.
I we can only annotate loops as being scalable, we loose the finer grained control to request this on a statement level. I don't know if mixing fixed and scalable will be an important use-case, but I think it is possible.
Summarising, I don't think explicit encoding of scalable in TIR nodes is a bad thing, the opposite actually, I think we need it, and the annotation on the loop might be a complementary technique to this.
What do you think?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] MeeraN7 commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
MeeraN7 commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-916824223
Hi @tqchen, thank you for the comment. To clarify a few things, VL is not added to the Ramp Node at all, it is simply a string that is used when printing TIR for visual representation. The only addition to the Ramp Node (and also Broadcast Node) is a boolean called "is_scalable" which should not affect anything else as a separate constructor was added. I don't think any other information needs to be added to these nodes or data types.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697187201
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
Review comment:
For this specific example, the semantics does change, doesn't it? Because in your example `C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`, 17 is not the length of a vector, but its the size of an input. While in the SVE example above the input length is explicitly divided by the vector length at TIR level.
Of course, I understand that the semantics of `Ramp` node in general does not change.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-894279450
Thanks @MeeraN7 . I think the overall loop legalization makes sense. I wonder then if it is necessary to update the node construct such as Ramp, or can we directly make use of scalar loop in the body
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] kparzysz-quic commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
kparzysz-quic commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-940244579
Right, but users of DLPack will not see `DataType`, only `DLDataType`, unless they use TVM as well. Changing `DataType` will only affect those that use `include/tvm/runtime/data_type.h` (i.e. the ABI breakage will be limited to users of TVM).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-940227361
@kparzysz-quic DatatType is a thin wrapper around DLDataType
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697183013
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
Review comment:
Since `s[C].vectorize(x)` doesn't specify the vector length and the specific length is deduced from the target string by LLVM codegen (e.g. `llvm -mcpu=core-avx2`), I wonder if `s[C].vectorize_scalable(x)` is really necessary.
Instead, can we decide whether or not to enable scalable vectors by an appropriate target attribute? For example, when we encounter `kVectorized` for loop and the target attribute requests SVE to be enabled, we convert the loop into `kVectorizeLoopScalabled` kind.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697183013
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
Review comment:
Since `s[C].vectorize(x)` doesn't specify the vector length and the specific length is deduced from the target string (e.g. `llvm -mcpu=core-avx2`), I wonder if `s[C].vectorize_scalable(x)` is really necessary.
Instead, can we decide whether or not to enable scalable vectors by an appropriate target attribute?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi edited a comment on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi edited a comment on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-906985030
Thanks @MeeraN7 @giuseros, I like the approach of making the vectorized loop explicit with `VL` parameter at the TIR level, in contrast to how the fixed-width vectorization is done today. It would be great if you can add a section on why an alternative implementation strategy was chosen. Perhaps to make the LLVM codegen simpler?
If possible, I think it is better not to introduce user facing changes, since as far as an API is concerned, `s[C].vectorize(...)` is already vector-length agnostic.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893037035
I think it is a good idea to invite people working on RISC-V support for TVM, since the RISC V vector extension is similar to ARM SVE. I remember some people in Taiwan are working on this. Maybe @comaniac knows who?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697195878
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
Review comment:
To avoid confusion, it is probably better to talk about different sense in which `Ramp` node is used, between fixed-width vs scalable vectorization. The former one treats the entire input as one chunk while the latter one is specifically for vector-length wide chunk.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] smeijer1234 commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
smeijer1234 commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-952735188
A belated thank you for sharing further thoughts on this @tqchen and @kparzysz-quic . I am on holiday this week (and a little bit of next), but want to pick this up soon after that. In the mean time, some remarks/questions from my side.
First of all, the ABI discussion goes over my head at the moment to be honest; I am not familiar enough yet to comment or address this. My understanding from the discussion so far is, that there will be an ABI break, but it is rather limited. So that doesn't require any further attention here, would that be a correct summary?
Perhaps more fundamental is @kparzysz-quic 's remark:
> This RFC is not about SVE. It's about vectorizing (countable) loops with bounds not known at compile time. I think that would be very valuable for all targets and we can determine the list of necessary features that a target should satisfy to implement it.
>
> Even though SVE can be used to implement it, it only applies to ARM, and there is no compelling reason to introduce SVE-specific features to TIR. There may be room for unknown-length vectors in TIR, but that should be done separately from SVE.
Yep, I agree, and you're right about this: this is not really about SVE. The "only" addition to TIR is the `is_scalable` part, which I would not consider to be SVE-specific, because it indeed just represents an unknown length vector and any back-end can deal with that in any way they like (and there are quite a few architectures that now support scalable-like vectors). So just for my understanding, would you mind elaborating on your thoughts here? For example, is it just a naming issue and we need to find another term, or is it more fundamental how we would like to do things in TIR? Thanks!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893552428
cc @junrushao1994 @vinx13 as it can be related to the future tensorization optimizations
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi edited a comment on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi edited a comment on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893037035
I think it is a good idea to invite people working on RISC-V support for TVM for review/discuss, since the RISC V vector extension is similar to ARM SVE. I remember some people in Taiwan are working on this. Maybe @comaniac knows who?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-930488098
Thanks @sjoerdmeijer , sorry for getting back to this late. If LLVM also encodes the SVE vector as a special type(and not tying the n) it could be a precedence that we can learn from. I do want to point out that the same approach won't work when it comes to scalable matrix instruction, so it would be good to think about a loop pattern based approach from that angle.
If we conclude that we really want to introduce the scalable vector into data type and so on. A remaining thing we need to resolve is the encoding. DataType and DLDataType are part of DLPack standard, used as standard ABI convention. So ideally we do not want to change the type signature of DataType DLDataType. What we might be able to is to introduce a magic lane number (say `DataType::kScalableVectorLaneMark = -1`) that indicate a scalable vector type, and also use similar approaches for other language construct as well. This would alleviate the problems from that side.
This being said. It would still be good to get @MeeraN7 @giuseros @sjoerdmeijer 's take on the possibility of using a normalized loop pattern vs embedding into the vector.
Thank you for all the discussions so far!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-952986816
@smeijer1234 to be more specific. I was recommending an approach that won't break the ABI.
Introdice
```
DataType::kScalableVectorLaneMark = -1
```
And in DataType, introduce a method IsScalable(), which checks if the lane equals -1 and if yes return true. This way we reuse the data layout of the original data structure without introducing the is_scalable field.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697187201
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
Review comment:
The semantics does change, doesn't it? Because in your example `C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`, 17 is not the length of a vector, but its the size of an input. While in the SVE example above the input length is explicitly divided by the vector length at TIR level.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697200267
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
+at compile time, and so we use VL as a way of representing that.
+
+## Implementation
+
+An agnostic constructor has been added to the Ramp node, as well as to the
+Broadcast node, with an additional parameter. This parameter is a boolean named
+_is_scalable_, in order to enable both fixed and scalable vectorisation.
+
+This boolean has also been added in _data_type.h_ as the type of the Ramp node
+has changed, it is now scalable. The constructor is:
+
+```
+DataType(int code, int bits, int lanes, bool is_scalable = false)
+```
+
+Originally, for fixed vectorisation, _is_scalable_ will be false, but when
+scalable vectorisation is enabled we will set _is_scalable_ to true.
+
+In TIR we introduced a new ForKind called _kVectorizeScalable_ which marks a
+loop as able to be vectorized but the value of VL will be unknown. This loop
+is then legalised during a new pass called _VectorizeLoopScalable_ pass, which
+is triggered by the vectorize_scalable function mentioned previously. This pass
+transforms the loop so that it is able to handle the unknown constant VL. Our
+prototype was implemented before the addition of the While node to TVM, and so
+it currently transforms a For loop into a variable For loop. To do this, the For
+node had to have extra parameters added to its implementation that would only be
+used in this one specific case. One change we are planning to make is to make use
+of this existing While node and transform a For Loop into a While loop during the
+_VectorizeLoopScalable_ pass, since it is the more natural choice and it is what
Review comment:
:+1: This is a great use case of TIR `While` loop that I didn't imagine.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] kparzysz-quic commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
kparzysz-quic commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-940209842
> DataType and DLDataType are part of DLPack standard,
The `DataType` type is defined in TVM, it's not present in DLPack. Or am I missing something?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697183013
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
Review comment:
Since `s[C].vectorize(x)` doesn't specify the vector length and the specific length is deduced from the target string (e.g. `llvm -mcpu=core-avx2`), I wonder if `s[C].vectorize_scalable(x)` is really necessary.
Instead, can we decide whether or not to enable scalable vectors by the target attribute?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893037035
I think it is a good idea to invite people working on RISC-V support for TVM, since the RISC V vector extension is similar to ARM SVE. I remember some people in Taiwan are working on this. Maybe @comaniac knows who?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-916899991
Thanks @MeeraN7 . Yes I get what you mean. Right now we are adding a "is_scalable" field to indicate that the broadcast and ramp are "context dependent" on VL. Additionally, we might need to update DataType to indicate a scalable data type.
This context dependency is the missing information I mentioned here. The set of code is really undefined and should be parameterized by VL. Additionally, considering the case of two loops with different VL1 and VL2 and want to do some transformations, we might fall into the trap of thinking them as same type(because only "is_scalable" is marked) but in reality they are not, as a implicit dependency on VL can be ignored.
I can understand that the additional flag can be helpful as we could reuse some of the vectorization logic. However, the "is_scalable" field might introduce additional confusion as above, and the additional ramp node may not carry too much additional information(apart from the fact that we use a scalar vs a vector type). So my main question is that whether or not we could use a separate normal form to hint the code generator without changing the current DataType, ramp and broadcast.
Specifically, a regular loop as follows would carry same amount of information(the access to i(VLA index)) would indicate a vector load, and access to other indices would become a normal load. The main constraint could be that we can only allow `i` to appear in certain locations(say in the inner most to represent a ramp like pattern), and defer the generation of SVE code to the codegen phase, by pattern matching the indices and lookup intermediate value:
**N1: A possible loop normal form via annotation**
```
for (i: int32, 0, 17;i, annotation={"VLA"}) {
C_2[i] = A_2[i] + B_2[i];
}
```
N1 would indeed push a bit more pressure to the code generator, because now code generator needs to pattern match load/store of VLA index(i), and possibly perform broadcast if necessary. However, the additional overhead may not be too large and could help us to keep the code cleaner. My guess is that this approach is also easier to generalize to later loop patterns such as scalable matrix instruction, in which case we cannot really reuse ramp and broadcast
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-910821675
Thanks @sjoerdmeijer @giuseros, I didn't imagine that there would be a case where mixing fixed and scalable vectorization is beneficial. I prefer `s[C].vectorize(..., scalable=True)` to `s[C].vectorize_scalable(...)` but both seem fine.
Any other comments @tqchen @tkonolige?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697205476
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
+at compile time, and so we use VL as a way of representing that.
+
+## Implementation
+
+An agnostic constructor has been added to the Ramp node, as well as to the
+Broadcast node, with an additional parameter. This parameter is a boolean named
+_is_scalable_, in order to enable both fixed and scalable vectorisation.
+
+This boolean has also been added in _data_type.h_ as the type of the Ramp node
+has changed, it is now scalable. The constructor is:
+
+```
+DataType(int code, int bits, int lanes, bool is_scalable = false)
+```
+
+Originally, for fixed vectorisation, _is_scalable_ will be false, but when
+scalable vectorisation is enabled we will set _is_scalable_ to true.
+
+In TIR we introduced a new ForKind called _kVectorizeScalable_ which marks a
+loop as able to be vectorized but the value of VL will be unknown. This loop
+is then legalised during a new pass called _VectorizeLoopScalable_ pass, which
+is triggered by the vectorize_scalable function mentioned previously. This pass
+transforms the loop so that it is able to handle the unknown constant VL. Our
+prototype was implemented before the addition of the While node to TVM, and so
+it currently transforms a For loop into a variable For loop. To do this, the For
+node had to have extra parameters added to its implementation that would only be
+used in this one specific case. One change we are planning to make is to make use
+of this existing While node and transform a For Loop into a While loop during the
+_VectorizeLoopScalable_ pass, since it is the more natural choice and it is what
+will be generated in the assembly as well. Once the loop has been legalised, it
+is passed to the code generator which will translate it to the relevant LLVM SVE
+instrinsics. The intrinsics involved are for predicated load/stores, loop
+increments and predication mask calculation. While predication is not implemented
+as a TIR construct, it is used to support VLA.
+
+This is all handled on the TE and TIR end, but for code generation we introduce
+a file called codegen_aarch64.cc which handles the creation of SVE intrinsics
+in LLVM by visiting the Load, Store and For nodes (to be replaced with a While
+node) and generating the relevant LLVM IR. For the above TIR output, the expected
+LLVM IR would be:
+```
+for_body: ; preds = %for_body, %entry
+ %indvars.iv = phi i64 [ %indvars.iv.next, %for_body ], [ 0, %entry ]
+ %8 = trunc i64 %indvars.iv to i32
+ %9 = tail call <vscale x 4 x i1> @llvm.aarch64.sve.whilelt.nxv4i1.i32(i32 %8, i32 17)
+ %10 = getelementptr inbounds float, float* %4, i64 %indvars.iv
+ %11 = tail call <vscale x 4 x float> @llvm.aarch64.sve.ld1.nxv4f32(<vscale x 4 x i1> %9, float* %10)
+ %12 = getelementptr inbounds float, float* %5, i64 %indvars.iv
+ %13 = tail call <vscale x 4 x float> @llvm.aarch64.sve.ld1.nxv4f32(<vscale x 4 x i1> %9, float* %12)
+ %14 = fadd <vscale x 4 x float> %11, %13
+ %15 = getelementptr inbounds float, float* %6, i64 %indvars.iv
+ tail call void @llvm.aarch64.sve.st1.nxv4f32(<vscale x 4 x float> %14, <vscale x 4 x i1> %9, float* %15)
+ %indvars.iv.next = add i64 %indvars.iv, %7
+ %16 = icmp slt i64 %indvars.iv, 17
+ br i1 %16, label %for_body, label %for_end, !prof !5
+```
+In the IR above we have:
+* the `whilelt` target specific SVE intrinsic, which generates a mask
+(variable %9) based on the induction variable (%8) and the loopbound (i32 17).
+This mask is only consumed by load/store instructions/intrinsics (and not e.g.
+data processing instructions such as the fadd), which is how predication is
+currently modeled in LLVM.
+* `<vscale x 4 x float>` is a scalable vector of 4 float elements
+* `<vscale x 4 x i1>` is the scalable mask consisting of 4 boolean values.
+
+
+## Drawbacks
+1. We've not been able to reuse existing code for this prototype, instead we have
+a whole a new vectorization pass and a new code generator for AArch64 specific
+intrinsics.
+2. In addition to this, we have created a new scheduling primitive which will need
+support and maintenance. This also means that the autotuner and autoscheduler must
+be modified to include the new rules needed for this primitive. These new rules are
+not supported in this prototype but have been noted as extension work in the future.
+
+## Next Steps
+
+As this is a prototype, we are aware that there are still areas that need
+further work:
+1. Our prototype was written before the While node work was merged. Instead of
+ creating a separate variable For-loop we should be using a While node, as
+ mentioned above. We think this is a straightforward rewrite, and with this
+ rewrite completed we think that this work lays the non-user facing part and
+ foundation for scalable vectorisation.
+2. The user facing part includes work to support the auto-scheduler and
+ auto-tuner will also need to be added. This would enable us to generate a
+ schedule that will call _vectorise_scalable_ and thus perform scalable
+ vectorisation, allowing users to benefit from this addition.
Review comment:
I think whether or not a vector is scalable is an implementation / codegen detail that users shouldn't be concerned about. When I write `s[C].vectorize(...)`, I don't care how long each vector is. I just assume that the appropriate length is chosen automatically based on the target attribute I provide.
As I commented above, I'd like to continue using `s[C].vectorize(...)` and when the feature is available, enable SVE by a target attribute. So I don't expect any user facing work.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893549153
Thanks @MeeraN7 for the RFC. SVE is certainly an interesting topic that can be covered in different ways.
It would be very helpful to also show examples of the code along the transformations, so we can have a better understanding the possible design tradeoffs.
Specifically:
- The TIR before SVE vectorization
- The TIR after SVE vectorization right before LLVM codegen
- The corresponding lowered llvm intrinsics
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] MeeraN7 commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
MeeraN7 commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-894160941
Thank you all for the comments so far, we are currently working on a response to address them.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen edited a comment on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen edited a comment on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893549153
Thanks @MeeraN7 for the RFC. SVE is certainly an interesting topic.
Because we do not yet have SVE support in TIR. It would be useful to think carefully about how SVE can be presented and transformed. Right now the proposal contains one way to do so. However, we could use a bit of more context information, to see how the proposed design impacts the general lowering flow.
Specifically, it would be very helpful to also show examples of the code along the transformations, so we can have a better understanding the possible design tradeoffs.
Specifically:
- The TIR before SVE vectorization
- The TIR after SVE vectorization right before LLVM codegen
- The corresponding lowered llvm intrinsics
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r683009543
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
Review comment:
AVX 512, to be precise
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] comaniac commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
comaniac commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893043955
> I think it is a good idea to invite people working on RISC-V support for TVM for review/discuss, since the RISC V vector extension is similar to ARM SVE. I remember some people in Taiwan are working on this. Maybe @comaniac knows who?
Thanks for bringing up. cc @yrchen
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tkonolige commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tkonolige commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r682981173
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
Review comment:
Can you define "scalable vectorization" in this paragraph.
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
+at compile time, and so we use VL as a way of representing that.
+
+## Implementation
+
+An agnostic constructor has been added to the Ramp node, as well as to the
+Broadcast node, with an additional parameter. This parameter is a boolean named
+_is_scalable_, in order to enable both fixed and scalable vectorisation.
+
+This boolean has also been added in _data_type.h_ as the type of the Ramp node
+has changed, it is now scalable. The constructor is:
+
+```
+DataType(int code, int bits, int lanes, bool is_scalable = false)
Review comment:
Why not use a special value for lanes to indicate that it can be a variable number?
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
+at compile time, and so we use VL as a way of representing that.
+
+## Implementation
+
+An agnostic constructor has been added to the Ramp node, as well as to the
+Broadcast node, with an additional parameter. This parameter is a boolean named
+_is_scalable_, in order to enable both fixed and scalable vectorisation.
+
+This boolean has also been added in _data_type.h_ as the type of the Ramp node
+has changed, it is now scalable. The constructor is:
+
+```
+DataType(int code, int bits, int lanes, bool is_scalable = false)
+```
+
+Originally, for fixed vectorisation, _is_scalable_ will be false, but when
+scalable vectorisation is enabled we will set _is_scalable_ to true.
+
+The _vectorize_scalable_ function triggers the transformations on the loops to
+make them scalable, by triggering a new pass called VectorizeLoopScalable. This
+pass visits the TIR nodes and transforms them so that they account for the
+unknown vector length. Currently, our prototype was implemented before the
+addition of the While node to TVM, and so it generates a variable for loop. One
+change we are planning to make is transforming a for loop into a while loop
+with unknown vector length directly, as that is what would be generated in the
+assembly.
+
+This is all handled on the TE and TIR end, but for code generation we introduce
+a file called codegen_aarch64.cc which handles the creation of SVE intrinsics
+in LLVM by visiting the Load, Store and For nodes (to be replaced with a While
+node) and generating the relevant LLVM IR.
+
Review comment:
Please include a drawbacks section.
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
Review comment:
You mention predication here, yet you never talk about how it is being added to TIR.
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
Review comment:
What do you think about adding a new `ForKind` so that we can express scalable vectorization in TIR.
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
Review comment:
We already have a concept of an unknown scalar value at compile time: `Any`. It seems like you could just have the lanes of Ramp be a PrimExpr instead of an int. Is there are reason not to take this approach?
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
Review comment:
When is the vector length of the loop determined? Is this decided by the hardware?
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
+at compile time, and so we use VL as a way of representing that.
+
+## Implementation
+
+An agnostic constructor has been added to the Ramp node, as well as to the
+Broadcast node, with an additional parameter. This parameter is a boolean named
+_is_scalable_, in order to enable both fixed and scalable vectorisation.
+
+This boolean has also been added in _data_type.h_ as the type of the Ramp node
+has changed, it is now scalable. The constructor is:
+
+```
+DataType(int code, int bits, int lanes, bool is_scalable = false)
+```
+
+Originally, for fixed vectorisation, _is_scalable_ will be false, but when
+scalable vectorisation is enabled we will set _is_scalable_ to true.
+
+The _vectorize_scalable_ function triggers the transformations on the loops to
+make them scalable, by triggering a new pass called VectorizeLoopScalable. This
+pass visits the TIR nodes and transforms them so that they account for the
+unknown vector length. Currently, our prototype was implemented before the
+addition of the While node to TVM, and so it generates a variable for loop. One
+change we are planning to make is transforming a for loop into a while loop
Review comment:
Why is a while loop necessary?
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
Review comment:
Is this PR talking about using predicated vector instructions or scalable vector instructions? If you aren't talking about predicated vector instructions, you could probably just remove this paragraph.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-933448098
The ABI issue is important since it affects the DLPack, so I would suggest we agree on the encoding convention before we proceed. I am fine with having a scalable vector repr if we can take the right encoding.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen edited a comment on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen edited a comment on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893549153
Thank you @MeeraN7 for the RFC. SVE is certainly an interesting topic.
Because we do not yet have SVE support in TIR. It would be useful to think carefully about how SVE can be presented and transformed. Right now the proposal contains one way to do so. However, we could use a bit of more context information, to see how the proposed design impacts the general lowering flow.
Specifically, it would be very helpful to also show examples of the code along the transformations, so we can have a better understanding the possible design tradeoffs. It might be helpful to translate some of the examples in the [whitepaper](https://developer.arm.com/solutions/hpc/resources/hpc-white-papers/arm-scalable-vector-extensions-and-application-to-machine-learning) to tvmscript form.
Specifically:
- The TIR before SVE vectorization
- The TIR after SVE vectorization right before LLVM codegen
- The corresponding lowered llvm intrinsics
To touch a bit on the design alternatives(disclaimer, I only learnt the VLA/SVE by quickly reading through the manual, so I could be wrong). Based on my understanding, the main goal of VLA is to use intrisnics to represent a some what restricted loop pattern(in terms of possible items we can do). While the previous fixed length vectorization pushes the items onto the vector constructs such as Ramp and Broadcast.
I wonder if we could take a different approach for VLA/SVE. Because VLA in nature is closer to the loop pattern. Specifically, I feel we could come up with some form of "loop SVE legalization" that legalize a loop's body to all the patterns that SVE support, then leave the for loop as it is with annotation VLA. Then the code generator can take that and generate VLA code.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-906985030
Thanks @MeeraN7 @giuseros, I like the approach of making the vectorized loop explicit with `VL` parameter at the TIR level, in contrast to how the fixed-width vectorization is done today.
If possible, I think it is better not to introduce user facing changes, since as far as an API is concerned, `s[C].vectorize(...)` is already vector-length agnostic.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] sjoerdmeijer commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
sjoerdmeijer commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-910235468
@masahi, about:
> If possible, I think it is better not to introduce user facing changes, since as far as an API is concerned, `s[C].vectorize(...)` is already vector-length agnostic.
which I think is very closely related to an earlier inline comment:
> As I commented above, I'd like to continue using s[C].vectorize(...) and when the feature is available, enable SVE by a target attribute. So I don't expect any user facing work.
I think we do need a user-facing option to toggle fixed/scalable vectorisation. If the vectorisation strategy is selected based on an available target attribute, we loose control to choose fixed/scalable vectorisation. For architectures that do support scalable vectorisation, fixed width might still be preferable in some cases.
I think this is similar to Clang's loop pragmas. For example, the `vectorise_width` pragma has been extended with an optional second argument `fixed|scalable`:
`vectorize_width(_value_[, fixed|scalable]),`
see also the Clang docs [here](https://clang.llvm.org/docs/LanguageExtensions.html#extensions-for-loop-hint-optimizations).
So I see two approaches:
- we extend `s[C].vectorize(...)` to take an optional fixed/scalable boolean value, similar to Clang's loop pragma, which defaults to fixed if omitted,
- or introduce `s[C].vectorize_scalable(...)` as proposed in this RFC.
I personally don't have any preference. But now I am wondering if extending `s[C].vectorize(...)`, the first option, would be better. What do you think?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] tqchen commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
tqchen commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-916553296
Thanks @MeeraN7 @giuseros, to make the discussion more concrete, right now the IR after legalization looks like
```c++
for (i: int32, 0, 17;i+=VL) {
C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
}
```
This would require changes such as the ramp data structure and data type to support the VL vector types. I wonder if they are necessary. Here is a possible alternative way to do so
```c++
for (i: int32, 0, 17;i, annotation={"VLA"}) {
C_2[i] = A_2[i] + B_2[i];
}
```
And we will be defering the vectorized instruction generation to the codegen phase, by specially handling the patterns in the for that is annotated with VLA loop. Of course we can only support a limited set of patterns(such as read/write to the same vector index or limited reduction support), that is why legalize is needed to make sure the body of VLA for loop satiesfies the pattern.
In this way we can likely get a similar set of things without hacking into get a ramp with VL size
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697183013
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
Review comment:
Since `s[C].vectorize(x)` doesn't specify the vector length and the specific length is deduced from the target string by LLVM codegen (e.g. `llvm -mcpu=core-avx2`), I wonder if `s[C].vectorize_scalable(x)` is really necessary.
Instead, can we decide whether or not to enable scalable vectors by an appropriate target attribute? For example, when we encounter `kVectorized` for loop and the target attribute requests SVE to be enabled, we convert the loop into `kVectorizeLoopScalable` kind.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r697187201
##########
File path: rfcs/0018-initial-sve-addition.md
##########
@@ -0,0 +1,221 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE)
+in TVM by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation in both TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
+are still the same, the only difference is that the number of lanes is unknown
Review comment:
The semantics does change, doesn't it? Because in your example `C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`, 17 is not the length of a vector, but its the size of an input. While in the example above the input length is explicitly divided by the vector length at TIR level.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] MeeraN7 commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
MeeraN7 commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r692170052
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
+and 2048 bits. It supports a vector length agnostic programming model which
+allows code to run and scale automatically across all vector lengths without
+recompilation.
+
+## Problem Statement
+
+We would like to add support for Arm Architecture's Scalable Vector Extension (SVE) in TVM
+by introducing features for Vector Length Agnostic (VLA) programs and
+predication, i.e. the 2 main new SVE features. Thus we would like to express
+scalable vectorisation TE and TIR. The question is how to achieve that? In
+Tensor Expression language, our example to add two tensors A and B would look
+like this:
+
+```
+n = 17
+A = te.placeholder((n,), name="A", dtype = "int8")
+B = te.placeholder((n,), name="B", dtype = "int8")
+C = te.compute(A.shape, lambda i: A[i] + B[i], name="C")
+s = te.create_schedule(C.op)
+x, = C.op.axis
+s[C].vectorize(x)
+```
+
+Vectorisation along the x-axis is requested with _vectorize(x)_, and will
+result in the TIR example shown in the Introduction. However, this requires
+knowing the vector length at compile time; it is an example of fixed width
+vectorisation. Instead, we would like for it to work with an unknown vector
+length at compile time.
+
+## Solution Approach
+
+In order to address the problem of expressing scalable vectorisation, we would
+like to propose the addition of a new _vectorize_scalable_ function to the Tensor
+Expression language, for example:
+```
+s[C].vectorize_scalable(x)
+```
+The TIR output of this would be:
+
+```
+primfn(A_1: handle, B_1: handle, C_1: handle) -> ()
+ attr = {"global_symbol": "main", "tir.noalias": True}
+ buffers = {C: Buffer(C_2: Pointer(int8), int8, [17], []),
+ A: Buffer(A_2: Pointer(int8), int8, [17], []),
+ B: Buffer(B_2: Pointer(int8), int8, [17], [])}
+ buffer_map = {A_1: A, B_1: B, C_1: C} {
+ for (i: int32, 0, 17;i+=VL) {
+ C_2[ramp(i, 1, VL)] = ((int8xVL*)A_2[ramp(i, 1, VL)] + (int8xVL*)B_2[ramp(i, 1, VL)])
+ }
+}
+```
+
+In the above TIR, we can see the the for loop is looping with an agnostic
+stride _VL_, which stands for Vector Length. _VL_ is only showed for ease of
+representation and we don't store _VL_ anywhere inside the TIR data structures.
+
+We can also see the syntax of the Ramp nodes have now been modified to handle
+an unknown vector length, as seen by _ramp(i, 1, VL)_, instead of a fixed
+integer. The form is still _Ramp(base, stride, lanes)_ and the semantics of it
Review comment:
Sorry it has taken a while to get back to you. But to answer your question we feel it would be much simpler to keep the number of lanes as an int, since we know that the value will always be an integer but the exact number is what is unknown. Also, it would be slightly misleading to use the value Any as the number of lanes can't be "any" number but instead a multiple of a minimal number (in this case 128).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] giuseros edited a comment on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
giuseros edited a comment on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893870692
HI @tqchen ,
I will try to sporadically comment, since this is a project I prototyped (and enjoyed :) ) when I was in Arm.
If I understand your comment correctly, what @MeeraN7 is doing is closer to what you are proposing. Instead of transforming a loop into a Ramp, and passing the ramp "as is" to LLVM (which is what is done for fixed vector length, but *not doable* for SVE) @MeeraN7 is legalising the loop in TIR and passing the legal loop down to the LLVM code-generator. In other words, the following loop:
```
for i = 1:1:10
A[i] = B[i]+C[i];
end
```
Once legalised becomes
```
for i = 1:VL:10
A[VL] = B[VL]+C[VL]
end
```
And then the LLVM code generator, knowing that this is a variable loop, translates this it with some LLVM intrinsics for:
* Predicated load/store
* Loop increment
* Predication mask calculation
Please note that only load/store needs to be predicated. Other register-to-register operations (e.g., add/sub/mul) won't need predication.
Please also note that while predication is not a TIR concept, we use it to support VLA (cc @tkonolige) in the LLVM codegen. In future it should be quite straightforward to expose predication also in TIR (if required).
@MeeraN7 feel free to jump in if something I said is not correct (very likely :) )
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] masahi commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
masahi commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r683009543
##########
File path: rfcs/initial_sve_addition.md
##########
@@ -0,0 +1,164 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: TODO
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. This is an introductory RFC to see if the design of our
+prototype implementation, see TODO, is sound. We will cover TIR support and how
+it affects the LLVM codegen and welcome any feedback on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX and the Arm
Review comment:
AVX 512, to be precise
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] comaniac commented on pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
comaniac commented on pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#issuecomment-893043955
> I think it is a good idea to invite people working on RISC-V support for TVM for review/discuss, since the RISC V vector extension is similar to ARM SVE. I remember some people in Taiwan are working on this. Maybe @comaniac knows who?
Thanks for bringing up. cc @yrchen
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm-rfcs] kparzysz-quic commented on a change in pull request #18: [RFC] Adding initial SVE implementation
Posted by GitBox <gi...@apache.org>.
kparzysz-quic commented on a change in pull request #18:
URL: https://github.com/apache/tvm-rfcs/pull/18#discussion_r726235647
##########
File path: 0018-initial-sve-addition.md
##########
@@ -0,0 +1,229 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
Review comment:
The size is 17. There are other mentions of 18 in this paragraph as well.
##########
File path: 0018-initial-sve-addition.md
##########
@@ -0,0 +1,229 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
Review comment:
Even though SVE may be adding per-lane predication for ARM, per-lane predication as a concept is unrelated to SVE and should be done independently. This is especially important for non-ARM architectures that do support it.
##########
File path: 0018-initial-sve-addition.md
##########
@@ -0,0 +1,229 @@
+- Feature Name: Adding Initial SVE Support to TVM
+- Start Date: 2021-07-30
+- RFC PR: https://github.com/apache/tvm-rfcs/pull/18
+
+Authors: Meera Nakrani, Sjoerd Meijer
+
+## Introduction
+
+In this RFC we would like to propose a TIR extension to support scalable
+vectorisation. Scalable vectorisation is extracting data parallelism from
+code, but as opposed to a fixed width vectorisation, the vector length is
+unknown at compile time. A scalable vector's total number of elements is a
+constant multiple of a specified number of elements. The
+[LLVM LangRef](https://llvm.org/docs/LangRef.html) refers to this constant
+multiple as vscale. It is a positive integer that is unknown at compile time,
+therefore the overall vector length (VL) is also unknown. The value of vscale,
+and therefore VL, will depend on the architecture that is running the program.
+More details and an overview of this is given in
+[this tutorial](https://www.stonybrook.edu/commcms/ookami/support/_docs/ARM_SVE_tutorial.pdf),
+where an example of a daxpy kernel is given from slide 17 onwards. In this RFC,
+we will show an example of lowering from TE for a (scalable) vector addition
+kernel all the way down to LLVM IR, further illustrating the vscale concept.
+We will also cover TIR support and how it affects the LLVM codegen. This is an
+introductory RFC to see if the design of our prototype implementation, see
+https://github.com/apache/tvm/pull/8655, is sound and we welcome any feedback
+on this prosposal.
+
+Before we explain this in more detail, let's first briefly look at the current
+state and terminology with an example. Vectorisation along the x-axis of an
+addition of two one-dimensional tensors A and B of size 18, writing the result
+to C, will result in the following TIR:
+
+```
+C[ramp(0, 1, 17)] = A[ramp(0, 1, 17)] + B[ramp(0, 1, 17)]`
+```
+where the Ramp TIR node has the form 'Ramp(base, stride, lanes)' showing that
+these elements are processed in (vector) lanes.
+
+The size of 18 has been chosen to demonstrate the challenges of vectorising
+this example. Vector architecture extensions (e.g. X86 AVX512 or AArch Neon)
+typically allow to pack and operate on a power-of-2 number of elements, so 2,
+4, 8, 16, etc. elements. If the elements are integers, and a vector register
+is 128-bits wide, we can pack 4 integer elements into one vector register (if
+an integer is 4 bytes). This is an example of fixed width vectorisation,
+because the vector registers have a fixed width of 128-bits. Since we have 18, the
+number of elements in the vectors A, B, and C, is not a multiple of 4, we need
+4 vector operations processing 4 * 4 = 16 elements, and 2 scalar operations are
+required for processing the 16th and 17th elements which we call the scalar
+epilogue.
+
+## Motivation
+
+However, most modern vector architectures (e.g. X86 AVX512 and the Arm
+Architecture's MVE and SVE extensions) support predicated vector instructions,
+removing the need for such a scalar epilogue and also allowing more code to be
+vectorised. Lane predication allows the enabling/disabling of certain lanes in
+vector operations. This allows us to have just 5 vector operations for our
+example, and importantly no scalar epilogue. But since we do not need to
+process 5 * 4 = 20 elements, the last vector operation only needs to write two
+elements, which can be achieved by predication as we can enable the first two
+lanes and disable the last 2 lanes.
+
+In addition to predication, and also related to it, some new vector
+architectures also allow scalable vectorisation. As opposed to so called fixed
+width vectorisation (e.g. AArch Neon), the Arm architecture SVE vector
+extension allows implementations to choose a vector register length between 128
Review comment:
Please clarify that "implementations" means "processor implementations".
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org