Processor having parallel vector multiply and reduce operations with sequential semantics
View Patent ↗A processor comprises a plurality of arithmetic units, an accumulator unit, and a reduction unit coupled between the plurality of arithmetic units and the accumulator unit. The reduction unit receives products of vector elements from the arithmetic units and a first accumulator value from the accumulator unit, and processes the products and the first accumulator value to generate a second accumulator value for delivery to the accumulator unit. The processor implements a plurality of vector multiply and reduce operations having guaranteed sequential semantics, that is, operations which guarantee that the computational result will be the same as that which would be produced using a corresponding sequence of individual instructions.
1. A multi-threaded vector processor comprising:
a plurality of vector arithmetic units for performing parallel concurrent vector operations on vectors comprising vector elements;
a vector accumulator unit; and
a vector reduction unit coupled between the plurality of vector arithmetic units and the vector accumulator unit, the vector reduction unit receiving products of vector elements from the vector arithmetic units and a first accumulator value from the vector accumulator unit;
wherein the vector reduction unit is pipelined and operative to process the products and the first accumulator value, and to generate a second accumulator value for delivery to the vector accumulator unit;
wherein the multi-threaded vector processor implements a plurality of vector multiply and reduce instructions having guaranteed sequential semantics such that computation results of a vector multiply and reduce instruction is the same as that which is produced using a corresponding sequence of individual instructions; and
wherein a vector multiply and reduce instruction computed for a given thread is executed concurrently with operations from other threads, the number of cycles between execution of the vector multiply and reduce instruction from the given thread being greater than or equal to a number of pipeline stages in the vector reduction unit plus any additional cycles needed to write to and read from the vector accumulator unit.
2. The processor of claim 1 wherein the vector multiply and reduce add with wrap-around performs the computation:
ACCD={ . . . {{ACCS+{A[ 1 ]*B[ 1 ]}}+{A[ 2 ]*B[ 2 ]}}+ . . . +{A[k]*B[k]}},
where A and B are k-bit input vectors, ACCS denotes the first accumulator value, ACCD denotes the second accumulator value, and {T} denotes that T is computed using wrap-around arithmetic.
3. The processor of claim 1 wherein the vector multiply and reduce add with saturation performs the computation:
ACCD=< . . . <<ACCS+<A[ 1 ]*B[ 1 ]>>+<A[ 2 ]*B[ 2 ]>>+ . . . +<A[k]*B[k]>>,
where A and B are k-bit input vectors, ACCS denotes the first accumulator value, ACCD denotes the second accumulator value, and <T> denotes that T is computed using saturating arithmetic.
4. The processor of claim 1 wherein the plurality of vector multiply and reduce operations comprises a vector multiply and reduce subtract with wrap-around which multiplies pairs of vector elements and subtracts the resulting products from the first accumulator value in sequential order with wrap-around arithmetic.
5. The processor of claim 4 wherein the vector multiply and reduce subtract with wrap-around performs the computation:
ACCD={ . . . {{ACCS−{A[ 1 ]*B[ 1 ]}}−{A[ 2 ]*B[ 2 ]}}− . . . −{A[k]*B[k]}},
where A and B are k-bit input vectors, ACCS denotes the first accumulator value, ACCD denotes the second accumulator value, and {T} denotes that T is computed using wrap-around arithmetic.
6. The processor of claim 1 wherein the plurality of vector multiply and reduce operations comprises a vector multiply and reduce subtract with saturation which multiplies pairs of vector elements and subtracts the resulting products from the first accumulator value in sequential order with saturation after each multiplication and each subtraction.
7. The processor of claim 6 wherein the vector multiply and reduce subtract with saturation performs the computation:
ACCD=< . . . <<ACCS−<{A[ 1 ]*B[ 1 ]>>−<A[ 2 ]*B[ 2 ]>>− . . . −<A[k]*B[k]>>,
where A and B are k-bit input vectors, ACCS denotes the first accumulator value, ACCD denotes the second accumulator value, and <T> denotes that T is computed using saturating arithmetic.
8. The processor of claim 1 wherein input vectors to which a given one of the vector multiply and reduce operations is applied are in one of an unsigned format, a one's complement format, a two's complement format, and a sign-magnitude format.
9. The processor of claim 1 wherein input vectors to which a given one of the vector multiply and reduce operations is applied are in one of a fixed-point format and a floating-point format.
10. The processor of claim 1 wherein results of a given one of the vector multiply and reduce operations are rounded.
11. The processor of claim 1 wherein results of a given one of the vector multiply and reduce operations are maintained at full precision.
12. The processor of claim 1 wherein the first accumulator value is zero, and a given one of the vector multiply and reduce operations comprises a dot product.
13. The processor of claim 1 wherein each element of a first input vector has a value of one, and a given one of the vector multiply and reduce operations comprises adding elements of a second input vector to the first accumulator value.
14. The processor of claim 1 wherein the processor comprises a single instruction multiple data (SIMD) processor, a given one of the vector multiply and reduce operations performing parallel multiplications of vector elements.
15. The processor of claim 1 wherein the plurality of arithmetic units comprises a plurality of multipliers arranged in parallel with one another.
16. The processor of claim 1 wherein the reduction unit is configured to provide controllable selection between at least a first type of computation with saturation after each of a plurality of addition or subtraction operations and a second type of computation with wrapping around of results of the addition or subtraction operations, responsive to an applied control signal.
17. The processor of claim 1 , wherein the plurality of vector multiply and reduce instructions comprises a vector multiply and reduce add with wrap-around which multiplies pairs of vector elements and adds the resulting products to the first accumulator value with wrap-around after each multiplication and each addition and a reduce add with saturation which multiplies pairs of vector elements and adds the resulting products to the first accumulator value with saturation after each multiplication and each addition, wherein the order of adding the resulting products to the first accumulator value and selection by the vector processor of one of wrap around arithmetic and saturation arithmetic are specified by the type of vector multiply and reduce instruction.
18. An integrated circuit comprising at least one multi-threaded vector processor, the multi-threaded vector processor comprising:
a plurality of vector arithmetic units for performing parallel concurrent vector operations on vectors comprising vector elements;
a vector accumulator unit; and
a vector reduction unit coupled between the plurality of vector arithmetic units and the vector accumulator unit, the vector reduction unit being pipelined and configured to receive products of vector elements from the vector arithmetic units and a first accumulator value from the vector accumulator unit;
wherein the vector reduction unit is operative to process the products and the first accumulator value, and to generate a second accumulator value for delivery to the vector accumulator unit;
wherein the multi-threaded vector processor implements a plurality of vector multiply and reduce instructions having guaranteed sequential semantics such that computation results of a vector multiply and reduce instruction is the same as that which is produced using a corresponding sequence of individual instructions; and
wherein a vector multiply and reduce instruction computed for a given thread is executed concurrently with operations from other threads, the number of cycles between execution of the vector multiply and reduce instruction from the given thread being greater than or equal to a number of pipeline stages in the vector reduction unit plus any additional cycles needed to write to and read from the vector accumulator unit.
19. An apparatus for use in a multi-threaded vector processor comprising a plurality of vector arithmetic units for performing parallel concurrent vector operations on vectors comprising vector elements and a vector accumulator unit, the apparatus comprising:
a vector reduction unit coupled between the plurality of vector arithmetic units and the vector accumulator unit, the vector reduction unit being configured to receive products of vector elements from the arithmetic units and a first accumulator value from the vector accumulator unit;
wherein the vector reduction unit is pipelined and operative to process the products and the first accumulator value, and to generate a second accumulator value for delivery to the vector accumulator unit;
wherein the multi-threaded vector processor implements a plurality of vector multiply and reduce instructions having guaranteed sequential semantics such that computation results of a vector multiply and reduce instruction is the same as that which is produced using a corresponding sequence of individual instructions; and
wherein a vector multiply and reduce instruction computed for a given thread is executed concurrently with operations from other threads, the number of cycles between execution of the vector multiply and reduce instruction from the given thread being greater than or equal to a number of pipeline stages in the vector reduction unit plus any additional cycles needed to write to and read from the vector accumulator unit.
20. The apparatus of claim 19 , wherein the plurality of vector multiply and reduce instructions comprises a vector multiply and reduce add with wrap-around which multiplies pairs of vector elements and adds the resulting products to the first accumulator value with wrap-around after each multiplication and each addition and a reduce add with saturation which multiplies pairs of vector elements and adds the resulting products to the first accumulator value with saturation after each multiplication and each addition, wherein the order of adding the resulting products to the first accumulator value and selection by the vector processor of one of wrap around arithmetic and saturation arithmetic are specified by the type of vector multiply and reduce instruction.
21. The integrated circuit of claim 18 , wherein the plurality of vector multiply and reduce instructions comprises a vector multiply and reduce add with wrap-around which multiplies pairs of vector elements and adds the resulting products to the first accumulator value with wrap-around after each multiplication and each addition and a reduce add with saturation which multiplies pairs of vector elements and adds the resulting products to the first accumulator value with saturation after each multiplication and each addition, wherein the order of adding the resulting products to the first accumulator value and selection by the vector processor of one of wrap around arithmetic and saturation arithmetic are specified by the type of vector multiply and reduce instruction.