Method and apparatus for compression multiplexing for sparse computations

Patent metadata

Field	Value
Publication number	US-11848689-B2
Application number	US-202217687559-A
Country	US
Kind code	B2
Filing date	Mar 4, 2022
Priority date	Mar 4, 2022
Publication date	Dec 19, 2023
Grant date	Dec 19, 2023

Abstract

Embodiments of the present disclosure include a digital circuit and method for compressing input digital values. A plurality of input digital values may include zero values and non-zero values. The input digital values are received on M inputs of a first switching stage. The first switching stage is arranged in groups that rearrange the non-zero values on first switching stage outputs according to a compression and shift. The compression and shift position the non-zero values on outputs coupled to inputs of a second switching stage. The second switching stage consecutively couples non-zero values to N outputs, where N is less than M.

First claim

What is claimed is:

1. A digital circuit comprising:
a first plurality of switches comprising M inputs and a plurality of outputs and configured to receive a plurality of input digital values having not more than N non-zero values on the M inputs, wherein the first plurality of switches are arranged in a plurality of groups of switches, wherein non-zero values received on inputs of each group of switches are compressed to adjacent outputs, beginning on a distal output, of each group, and shifted by an amount equal to a total number of non-zero inputs received on inputs of other groups between a particular group and a distal input of the M inputs of the first plurality of switches, where M and N are integers and M is greater than N; and
a second plurality of switches having a plurality of inputs and N outputs and configured to consecutively couple non-zero outputs of the first plurality of switches to the N outputs of the second plurality of switches.

2. The circuit of claim 1 , wherein M is a power of two (2) multiple of N.

3. The circuit of claim 1 , wherein the first plurality of switches arranged in a plurality of groups of switches comprise a plurality of crossbar groups.

4. The circuit of claim 3 , wherein each of the plurality of crossbar groups comprise multiplexers.

5. The circuit of claim 1 , wherein the second plurality of switches comprise N multiplexers.

6. The circuit of claim 1 , wherein the first plurality of switches comprise M outputs and the second plurality of switches comprise M inputs.

7. The circuit of claim 1 , wherein the first plurality of switches comprise a first plurality of multiplexers, and wherein the second plurality of switches comprises a second plurality of multiplexers each having a number inputs equal to one (1) minus a number of the first plurality of multiplexers.

8. The circuit of claim 1 , further comprising:
a first distal group of switches of the first plurality of switches is coupled to a lower half group of the second plurality of switches;
a second distal group of switches of the first plurality of switches, opposite the first distal group of switches, is coupled to an upper half group of the second plurality of switches; and
groups of switches between the first distal group and the second distal group are coupled to the lower half group and upper half group of the plurality of switches.

9. The circuit of claim 1 , wherein the first plurality of switches and the second plurality of switches are controlled based on a bit map vector specifying the position of the N non-zero values on the M inputs of the first plurality of switches.

10. The circuit of claim 1 , further comprising a first number of inputs of the plurality of inputs of the second plurality of switches is less than a second number of outputs of the plurality of outputs of the first plurality of switches.

11. The circuit of claim 1 , further comprising a first distal group of switches of the plurality of groups of switches is coupled to a first half of the second plurality of switches and not connected to a second half of the second plurality of switches, and a second distal group of switches of the plurality of groups of switches is coupled to the second half of the second plurality of switches and not connected to the first half of the second plurality of switches.

12. The circuit of claim 1 , wherein said shift comprises barrel shifting.

13. The circuit of claim 1 , wherein said shift is, for each group of switches, equal to a remainder of said total number for a particular group of switches divided by a number of outputs of the particular group of switches.

14. The circuit of claim 1 , wherein the first plurality of switches comprise a plurality of stages.

15. The circuit of claim 1 , wherein the second plurality of switches comprise a plurality of stages.

16. A method of compressing data comprising:
receiving a plurality of input digital values on M inputs of a first plurality of switches, the input digital values having not more than N non-zero values wherein the first plurality of switches are arranged in a plurality of groups of switches, where M and N are integers and M is greater than N;
compressing the non-zero values received on inputs of each group of switches to adjacent outputs, beginning on a distal output, of each group;
shifting the non-zero values on the adjacent outputs by an amount equal to a total number of non-zero inputs received on inputs of other groups between a particular group and a distal input of the M inputs of the first plurality of switches; and
consecutively coupling non-zero outputs of the first plurality of switches to N outputs of a second plurality of switches.

17. The method of claim 16 , wherein M is a power of two (2) multiple of N.

18. The method of claim 16 , wherein the first plurality of switches and the second plurality of switches are controlled based on a bit map vector specifying the position of the N non-zero values on the M inputs of the first plurality of switches.

19. The method of claim 16 , wherein a first number of inputs of the plurality of inputs of the second plurality of switches is less than a second number of outputs of the plurality of outputs of the first plurality of switches.

20. A non-transitory machine-readable medium storing a hardware definition language (HDL) program executable by a computer, the program comprising sets of instructions for:
receiving a plurality of input digital values on M inputs of a first plurality of switches, the input digital values having not more than N non-zero values wherein the first plurality of switches are arranged in a plurality of groups of switches, where M and N are integers and M is greater than N;
compressing the non-zero values received on inputs of each group of switches to adjacent outputs, beginning on a distal output, of each group;
shifting the non-zero values on the adjacent outputs by an amount equal to a total number of non-zero inputs received on inputs of other groups between a particular group and a distal input of the M inputs of the first plurality of switches; and
consecutively coupling non-zero outputs of the first plurality of switches to N outputs of a second plurality of switches.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• More Ankit
• Heddes Mattheus C
• Shah Nishit

Classifications

• H03M7/3082 Primary

  Vector coding (for television signals, see H04N19/94) · CPC title

• G06F5/01

  for shifting, e.g. justifying, scaling, normalising {(digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00)} · CPC title

• H03M7/3066

  by means of a mask or a bit-map · CPC title

• H03M7/6017 Primary

  Methods or arrangements to increase the throughput · CPC title

• H03M7/6005

  Decoder aspects · CPC title