Binary multiplier for binary vector factorization

1. A processor, comprising:

decode circuitry to decode instructions;

a data cache unit including circuitry to cache data for the processor; and

an approximate matrix multiplication (AMM) circuit comprising:

a data receptor circuit to receive a weight vector w and an input vector x, both of size N, and a compression regulating parameter n;

a factorizer circuit to factorize w into w≅B·s, by computing a binary factorized matrix B of size N×n, and a dictionary vector s of size n; and

a binary multiplier circuit to compute w T x≅(B·s) T x=s T (B T x), the binary multiplier circuit comprising a hardware accelerator circuit to compute an array product (B T x), wherein the hardware accelerator circuit is one of a two-dimensional array of multiplier accumulators and flip flops, a two-dimensional array of adders and flip flops, or an adder tree.

2. The processor of claim 1 , wherein the hardware accelerator circuit is a two-dimensional array of multiplier accumulators and flip flops to walk an outer loop such that each cycle's partial result of elements is accumulated, and wherein all inputs X are multiplied by all weights W.

3. The processor of claim 1 , wherein the hardware accelerator circuit is a two-dimensional array of adders and flip flops to compute a sum of numbers, wherein each weight is a 0 or 1.

4. The processor of claim 1 , wherein the hardware accelerator is an adder tree.

5. The processor of claim 4 , wherein the adder tree is a full adder tree.

6. The processor of claim 5 , wherein the full adder tree is to compute a conditional sum of g elements, of the form

∑

i

=

0

g

-

1

⁢

X

i

*

W

g

-

1

i

.

7. The processor of claim 4 , wherein the adder tree is a shared adder tree comprising a shared adder block, and an array of half adder trees, wherein the shared adder block is shared by the array of half adder trees.

8. The processor of claim 7 , wherein the half adder trees comprise a multiplexed input, wherein weight W selects between X0+X1, X1, X0, and 0.

9. A system on a chip (SoC), comprising:

a memory;

an input/output device; and

a core comprising:

decode circuitry to decode instructions;

a data cache unit including circuitry to cache data for the processor; and

a compute unit having an approximate matrix multiplication (AMM) circuit comprising:

a data receptor circuit to receive a weight vector w and an input vector x, both of size N, and a compression regulating parameter n;

a factorizer circuit to factorize w into w≅B·s, by computing a binary factorized matrix B of size N×n, and a dictionary vector s of size n; and

a binary multiplier circuit to compute w T x≅(B·s) T x=s T (B T x), the binary multiplier circuit comprising a hardware accelerator circuit to compute an array product (B T x), wherein the hardware accelerator circuit is one of a two-dimensional array of multiplier accumulators and flip flops, a two-dimensional array of adders and flip flops, or an adder tree.

10. The SoC of claim 9 , wherein the hardware accelerator circuit is a two-dimensional array of multiplier accumulators and flip flops to walk an outer loop such that each cycle's partial result of elements is accumulated, and wherein all inputs X are multiplied by all weights W.

11. The SoC of claim 9 , wherein the hardware accelerator circuit is a two-dimensional array of adders and flip flops to compute a sum of numbers, wherein each weight is a 0 or 1.

12. The SoC of claim 9 , wherein the hardware accelerator is an adder tree.

13. The SoC of claim 12 , wherein the adder tree is a full adder tree.

14. The SoC of claim 13 , wherein the full adder tree is to compute a conditional sum of g elements, of the form

∑

i

=

0

g

-

1

⁢

X

i

*

W

g

-

1

i

.

15. The SoC of claim 12 , wherein the adder tree is a shared adder tree comprising a shared adder block, and an array of half adder trees, wherein the shared adder block is shared by the array of half adder trees.

16. The SoC of claim 15 , wherein the half adder trees comprise a multiplexed input, wherein weight W selects between X0+X1, X1, X0, and 0.

17. A method of performing approximate matrix multiplication, comprising:

receiving, by a data receptor circuit, a weight vector w and an input vector x, both of size N, and a compression regulating parameter n;

factorizing, by a factorizer circuit, w into w≅B·s, by computing a binary factorized matrix B of size N×n, and a dictionary vector s of size n; and

computing w T x≅(B·s) T x=s T (B T x) by a binary multiplier circuit, the binary multiplier circuit comprising a hardware accelerator circuit to compute an array product (B T x), wherein the hardware accelerator circuit is one of a two-dimensional array of multiplier accumulators and flip flops, a two-dimensional array of adders and flip flops, or an adder tree.

18. The method of claim 17 , wherein the hardware accelerator circuit is a two-dimensional array of multiplier accumulators and flip flops to walk an outer loop such that each cycle's partial result of elements is accumulated, and wherein all inputs X are multiplied by all weights W.

19. The method of claim 17 , wherein the hardware accelerator circuit is a two-dimensional array of adders and flip flops to compute a sum of numbers, wherein each weight is a 0 or 1.

20. The method of claim 17 , wherein the hardware accelerator is an adder tree.

21. The method of claim 20 , wherein the adder tree is a full adder tree.

22. The method of claim 21 , wherein the full adder tree is to compute a conditional sum of g elements, of the form

∑

i

=

0

g

-

1

⁢

X

i

*

W

g

-

1

i

.

23. The method of claim 20 , wherein the adder tree is a shared adder tree comprising a shared adder block, and an array of half adder trees, wherein the shared adder block is shared by the array of half adder trees.

24. The method of claim 23 , wherein the half adder trees comprise a multiplexed input, wherein weight W selects between X0+X1, X1, X0, and 0.