# US 10,768,895 B2 · Dot product calculators and methods of operating the same

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,768,895 B2
- Document ID: US10768895B2
- Status: Granted
- Kind: B2
- Application number: 16/184,985
- Filed: 2018-11-08
- Published: 2020-05-14
- Granted: 2020-09-08
- Earliest claimed: 2018-11-08
- Assignees: Movidius Limited
- Applicants: Movidius Ltd.
- Inventors: Fergal Connor; David Bernard; Niall Hanrahan
- Web page: https://patentgrep.com/patent/US10768895B2

## CPC

- G06F 7/523: Multiplying only
- G06F 9/3001: {Arithmetic instructions}
- G06F 7/5443: {Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00)}
- G06F 9/30018: {Bit or string instructions}
- G06F 9/30038: {using a mask}
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/0495: Quantised networks; Sparse networks; Compressed networks
- G06F 2207/4824: Neural networks
- G06N 3/045: Combinations of networks
- G06N 3/063: using electronic means
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Methods, apparatus, systems and articles of manufacture to perform dot product calculations using sparse vectors are disclosed. An example dot product calculator includes a counter to determine a trailing binary count of a control vector, the control vector corresponding to a first result of a first logic AND operation on a first bitmap of a first sparse vector and a second bitmap of a second sparse vector. The example dot product calculator further includes a mask generator to generate a mask vector based on the trailing binary count. The example dot product calculator further includes an interface to access a first value of the first sparse vector based on a second result of a second logic AND operation on the first bitmap and the mask vector and access a second value of the second sparse vector based on a third result of a third logic AND operation on the second bitmap and the mask vector. The example dot product calculator further includes a multiplier to multiply the first value with the second value to generate a product.

## Claims

### Claim 1

A dot product calculator comprising:
a counter to determine a trailing binary count of a control vector, the control vector corresponding to a first result of a first logic AND operation on a first bitmap of a first sparse vector and a second bitmap of a second sparse vector;
a mask generator to generate a mask vector based on the trailing binary count;
an interface to:
access a first value of the first sparse vector based on a second result of a second logic AND operation on the first bitmap and the mask vector; and
access a second value of the second sparse vector based on a third result of a third logic AND operation on the second bitmap and the mask vector; and
a multiplier to multiply the first value with the second value to generate a product.

### Claim 2 (depends on 1)

The dot product calculator of claim 1, wherein:
the first bitmap is to identify whether first elements of the first vector respectively correspond to zero values or non-zero values and the second bitmap is to identify whether second elements of the second vector respectively correspond to zero values or non-zero values; and
the first sparse vector corresponds to non-zero values of a first dense vector and the second sparse vector corresponds to non-zero values of a second dense vector.

### Claim 3 (depends on 1)

The dot product calculator of claim 1, further including a logic gate to generate the control vector based on the first logic AND operation with the first bitmap and the second bitmap as inputs.

### Claim 4 (depends on 1)

The dot product calculator of claim 1, wherein the mask generator is to generate the mask vector to include a number of first binary values in the least significant bits, the number corresponding to the trailing binary count, the mask generator to generate the mask vector to have the same dimensions as a first vector.

### Claim 5 (depends on 1)

The dot product calculator of claim 1, further including an element position determiner to:
determine a first number of binary values in the second result, the interface to access the first value based on a first address corresponding to the first number of binary values; and
determine a second number of binary values in the third result, the interface to access the second value based on a second address corresponding to the second number of binary values.

### Claim 6 (depends on 1)

The dot product calculator of claim 1, further including storage to store the product.

### Claim 7 (depends on 1)

The dot product calculator of claim 1, further including:
a subtractor to generate a difference vector by subtracting one from a value corresponding to binary bits of the control vector; and
an iterative control vector generator to:
generate an updated control vector corresponding to a logic AND operation on the control vector and the difference vector; and
determine if all elements of the update control vector correspond to a same binary value.

### Claim 8 (depends on 7)

The dot product calculator of claim 7, wherein the interface is to output the product as a dot product result when the iterative control vector generator determines that all the elements of the updated control vector correspond to the same binary value.

### Claim 9 (depends on 7)

The dot product calculator of claim 7, wherein the trailing binary count is a first trailing binary count, the mask vector is a first mask vector, the product is a first product, and, when the iterative control vector generator determines that all the elements of the updated control vector do not correspond to the same binary value:
the counter is to determine a second trailing binary count of the updated control vector;
the mask generator is to generate a second mask vector corresponding to the second trailing binary count;
the interface is to:
access a third value of the first sparse vector based on a fourth result of a fourth logic AND operation on the first bitmap and the second mask vector;
access a fourth value of the second sparse vector based on a fifth result of a fifth logic AND operation on the second bitmap and the second mask vector; and
the multiplier is to multiply the third value by the fourth value to generate a second product, the dot product calculator further including:
a summer to sum the first product with the second product.

### Claim 10 (depends on 9)

The dot product calculator of claim 9, wherein the difference vector is a first difference vector, the updated control vector is a first updated control vector, and the elements are first elements, and:
the subtractor is to generate a second difference vector by subtracting one from a value translation of the binary value of the updated control vector; and
the iterative control vector generator is to generate a second updated control vector corresponding to a logic AND operation on the updated control vector and the second difference vector; and
the interface is to, when all second elements of the second updated control vector correspond to the same binary value, output a sum of the first product with the second product as a dot product result.

### Claim 11

At least one non-transitory computer readable storage medium comprising instructions which, when executed, cause a machine to at least:
determine a trailing binary count of a control vector, the control vector corresponding to a first result of a first logic AND operation on a first bitmap of a first sparse vector and a second bitmap of a second sparse vector;
generate a mask vector based on the trailing binary count; and
multiply (A) a first value of the first sparse vector based on a second result of a second logic AND operation on the first bitmap and the mask vector with (B) a second value of the second sparse vector corresponding to a second vector based on a third result of a third logic AND operation on the second bitmap and the mask vector.

### Claim 12 (depends on 11)

The computer readable storage medium of claim 11, wherein:
the first bitmap is to identify zero values or non-zero values of a first vector respectively and the second bitmap respectively is to identify zero values or non-zero values of the second vector; and
the first sparse vector corresponds to non-zero values of a first dense vector and the second sparse vector corresponds to non-zero values of a second dense vector.

### Claim 13 (depends on 11)

The computer readable storage medium of claim 11, wherein the instructions cause the machine to generate the control based on the first logic AND operation with first bitmap and the second bitmap as inputs.

### Claim 14 (depends on 11)

The computer readable storage medium of claim 11, wherein the instructions cause the machine to generate the mask vector to include a number of first binary values in the least significant bits, the number corresponding to the trailing binary count, the mask vector having the same dimensions as a first vector.

### Claim 15 (depends on 11)

The computer readable storage medium of claim 11, wherein the instructions cause the machine to:
determine a first number of binary values in the second result;
access the first value based on a first address corresponding to the first number of binary values;
determine a second number of binary values in the third result; and
access the second value based on a second address corresponding to the second number of binary values.

### Claim 16 (depends on 11)

The computer readable storage medium of claim 11, wherein the instructions cause the machine to store the product of the first value and the second value in local memory.

### Claim 17 (depends on 11)

The computer readable storage medium of claim 11, wherein the instructions cause the machine to:
generate a difference vector by subtracting one from a value corresponding to binary bits of the control vector;
generate an updated control vector corresponding to a logic AND operation on the control vector and the difference vector; and
determine if all elements of the update control vector correspond to a same binary value.

### Claim 18 (depends on 17)

The computer readable storage medium of claim 17, wherein the instructions cause the machine to output the product of the first value and the second value as a dot product result when all the elements of the updated control vector correspond to the same binary value.

### Claim 19 (depends on 17)

The computer readable storage medium of claim 17, wherein the trailing binary count is a first trailing binary count, the mask vector is a first mask vector, the product is a first product, and, the instructions to cause the machine to, when all the elements of the updated control vector do not correspond to the same binary value:
determine a second trailing binary count of the updated control vector;
generate a second mask vector corresponding to the second trailing binary count;
access a third value of the first sparse vector based on a fourth result of a fourth logic AND operation on the first bitmap and the second mask vector;
access a fourth value of the second sparse vector based on a fifth result of a fifth logic AND operation on the second bitmap and the second mask vector; and
multiply the third value by the fourth value to generate a second product; and
sum the first product with the second product.

### Claim 20 (depends on 19)

The computer readable storage medium of claim 19, wherein the difference vector is a first difference vector, the updated control vector is a first updated control vector, and the elements are first elements, and, the instruction cause the machine to:
generate a second difference vector by subtracting one from a value translation of the binary value of the updated control vector;
generate a second updated control vector corresponding to a logic AND function between the updated control vector and the second difference vector; and
when all second elements of the second updated control vector correspond to the same binary value, output a sum of the first product with the second product as a dot product result.

### Claim 21

A method to determine a dot product between two vectors, the method comprising:
determining, with at least one logic circuit, a trailing binary count of a control vector, the control vector corresponding to a first result of a first logic AND operation on a first bitmap of a first vector and a second bitmap of a second vector;
generating, with the at least one logic circuit, a mask vector corresponding to the trailing binary count;
accessing a first value of a first sparse vector corresponding to the first vector based on a second result of a second logic AND operation on the first bitmap and the mask vector; and
accessing a second value of a second sparse vector corresponding to the second vector based on a third result of a third logic AND operation on the second bitmap and the mask vector; and
multiplying, with the at least one logic circuit, the first value with the second value to generate a product.

### Claim 22 (depends on 21)

The method of claim 21, further including:
generating the control vector based on the first logic AND operation with first bitmap and the second bitmap as inputs; and
generating the mask vector to include a number of first binary values in the least significant bits, the number corresponding to the trailing binary count, the mask vector having the same dimensions as the first vector.

### Claim 23 (depends on 21)

The method of claim 21, further including:
determining a first number of binary values in the second result;
accessing the first value based on a first address corresponding to the first number of binary values;
determining a second number of binary values in the third result;
accessing the second value based on a second address corresponding to the second number of binary values; and
storing the product of the first value and the second value in local memory.

### Claim 24 (depends on 21)

The method of claim 21, further including:
generating a difference vector by subtracting one from a value corresponding to binary bits of the control vector;
generating an updated control vector corresponding to a logic AND operation on the control vector and the difference vector; and
determining if all elements of the update control vector correspond to a same binary value.

### Claim 25 (depends on 24)

The method of claim 24, wherein the trailing binary count is a first trailing binary count, the mask vector is a first mask vector, the product is a first product, the difference vector is a first difference vector, the updated control vector is a first updated control vector, and the elements are first elements, and, further including, when all the elements of the updated control vector do not correspond to the same binary value:
determining a second trailing binary count of the updated control vector;
generating a second mask vector corresponding to the second trailing binary count;
accessing a third value of the first sparse vector based on a fourth result of a fourth logic AND operation on the first bitmap and the second mask vector;
accessing a fourth value of the second sparse vector based on a fifth result of a fifth logic AND operation on the second bitmap and the second mask vector;
multiplying the third value by the fourth value to generate a second product; and
summing the first product with the second product;
generating a second difference vector by subtracting one from a value translation of the binary value of the updated control vector;
generating a second updated control vector corresponding to a logic AND operation on the updated control vector and the second difference vector; and
when all second elements of the second updated control vector correspond to the same binary value, outputting a sum of the first product with the second product as a dot product result.

### Claim 26

A dot product calculator comprising:
first means for determining a trailing binary count of a control vector, the control vector corresponding to a first result of a first logic AND operation on a first bitmap of a first sparse vector and a second bitmap of a second sparse vector;
second means for generating a mask vector based on the trailing binary count;
third means for:
accessing a first value of the first sparse vector based on a second result of a second logic AND operation on the first bitmap and the mask vector; and
accessing a second value of the second sparse vector based on a third result of a third logic AND operation on the second bitmap and the mask vector; and
fourth means for multiplying the first value with the second value to generate a product.

### Claim 27 (depends on 26)

The dot product calculator of claim 26, further including fifth means for generating the control vector based on the first logic AND operation with the first bitmap and the second bitmap as inputs, wherein the second means includes means for generating the mask vector to include a number of first binary values in the least significant bits, the number corresponding to the trailing binary count, the second means including means for generating the mask vector to have the same dimensions as a first vector.

### Claim 28 (depends on 26)

The dot product calculator of claim 26, further including,
sixth means for:
determining a first number of binary values in the second result, the third means including means for accessing the first value based on a first address corresponding to the first number of binary values; and
determining a second number of binary values in the third result, the third means including means for accessing the second value based on a second address corresponding to the second number of binary values; and
seventh means for storing the product.

### Claim 29 (depends on 26)

The dot product calculator of claim 26, further including:
eighth means for generating a difference vector by subtracting one from a value corresponding to binary bits of the control vector; and
ninth means for:
generating an updated control vector corresponding to a logic AND operation on the control vector and the difference vector; and
determining if all elements of the update control vector correspond to a same binary value.

### Claim 30 (depends on 29)

The dot product calculator of claim 29, wherein the trailing binary count is a first trailing binary count, the mask vector is a first mask vector, the product is a first product, the difference vector is a first difference vector, the updated control vector is a first updated control vector, and the elements are first elements and, when the ninth means determines that all the elements of the updated control vector do not correspond to the same binary value:
the first means including means for determining a second trailing binary count of the updated control vector;
the second means includes means for generating a second mask vector corresponding to the second trailing binary count;
the third means including means for:
accessing a third value of the first sparse vector based on a fourth result of a fourth logic AND operation on the first bitmap and the second mask vector; and
accessing a fourth value of the second sparse vector based on a fifth result of a fifth logic AND operation on the second bitmap and the second mask vector; and
the fourth means including means for multiplying the third value by the fourth value to generate a second product, the dot product calculator further including:
a tenth means for summing the first product with the second product; and
the eight means includes means for generating a second difference vector by subtracting one from a value translation of the binary value of the updated control vector; and
the ninth means includes means for generating a second updated control vector corresponding to a logic AND operation on the updated control vector and the second difference vector; and
the third means including means for, when all second elements of the second updated control vector correspond to the same binary value, outputting a sum of the first product with the second product as a dot product result.