# US 2024/0004649 A1 · Method and apparatus for compressing vector data, method and apparatus for decompressing vector data, and device

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

- Number: US 2024/0004649 A1
- Document ID: US20240004649A1
- Status: Published application
- Kind: A1
- Application number: 18/368,419
- Filed: 2023-09-14
- Published: 2024-01-04
- Earliest claimed: 2022-03-28
- Assignees: Tencent Technology (Shenzhen) Company Limited
- Applicants: Tencent Technology (Shenzhen) Company Limited
- Inventors: Zimu REN; Dongsheng Li
- Web page: https://patentgrep.com/patent/US20240004649A1

## CPC

- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- G06F 7/76: Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
- G06F 9/30018: {Bit or string instructions}
- G06F 9/30032: {Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE}
- G06F 9/30038: {using a mask}
- G06F 9/30109: {having multiple operands in a single register}
- H03M 7/3082: {Vector coding (for television signals, see H04N19/94)}
- H03M 7/3066: {by means of a mask or a bit-map}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

The present subject matter relates to the field of data processing technologies. Source vector data is stored in a source vector register. The source vector data is divided into n source sub-vectors. The n source sub-vectors are in a one-to-one correspondence with n sets of multiplexers. First valid elements in a source sub-vector are selectively arranged by multiplexers in the n sets of multiplexers in the source vector data to obtain a target sub-vector. A data merging apparatus shifts and merges n target sub-vectors corresponding to the n source sub-vectors to obtain target vector data. A target vector register stores second valid elements in the target vector data. Through the method, the apparatus, and the device, a congestion level of wires can be effectively reduced, thereby significantly reducing an area of a processor.

## Claims

### Claim 1

A method for compressing vector data by a processor comprising a source vector register, n sets of multiplexers, a data merging apparatus, and a target vector register, where n is an integer greater than 1, the method comprising:
storing, by the source vector register, source vector data, wherein
the source vector data is divided into n source sub-vectors, and
the n source sub-vectors are in a one-to-one correspondence with the n sets of multiplexers;
selectively arranging, by an ith set of multiplexers in the n sets of multiplexers, first valid elements in an ith source sub-vector in the source vector data to obtain an ith target sub-vector corresponding to the ith source sub-vector, wherein
the first valid elements in the ith target sub-vector are located at a header of the ith target sub-vector, and
i is a positive integer less than or equal to n;
shifting and merging, by the data merging apparatus, n target sub-vectors corresponding to the n source sub-vectors to obtain target vector data, wherein
second valid elements in the target vector data are located at a header of the target vector data; and
storing, by the target vector register, the second valid elements in the target vector data.

### Claim 2 (depends on 1)

The method according to claim 1, wherein
the ith source sub-vector comprises x elements,
the x elements comprising y valid elements, and
the ith set of multiplexers comprising x−1 multiplexers of different types, x is a positive integer, and y is a positive integer less than or equal to x−1; and
the selectively arranging comprises:
selecting, by y multiplexers in the x−1 multiplexers, the y valid elements from the x elements in ascending order of bits based on a boolean vector corresponding to the source vector data, and arranging the y valid elements in ascending order of bits to obtain the ith target sub-vector, wherein
an element in the boolean vector is used for indicating a distribution of the valid elements in the source vector data.

### Claim 3 (depends on 2)

The method according to claim 2, wherein the selecting comprises:
selecting, by a zth multiplexer in the y multiplexers, a zth valid element from a zth element to an xth element in the ith source sub-vector in ascending order of bits based on the boolean vector, wherein
z is a positive integer less than or equal to y; and
adding, by the zth multiplexer, the zth valid element to a zth position of the ith target sub-vector.

### Claim 4 (depends on 1)

The method according to claim 1, wherein
the data merging apparatus comprises:
m sets of data merging units, wherein
the m sets of data merging units are configured to perform p rounds of shifting and merging on the n target sub-vectors to obtain the target vector data, and
m is an integer greater than 1, and p is a positive integer; and
the shifting and merging comprises:
shifting and merging, by a qth set of data merging units in the m sets of data merging units for a qth round of shifting and merging, a qth set of to-be-merged vectors to obtain a qth set of merged vectors, wherein
q is a positive integer less than or equal to p; and
in a case that q is equal to 1, the qth set of to-be-merged vectors are the n target sub-vectors, and in a case that q is greater than 1, wherein
the qth set of to-be-merged vectors are a (q−1)th set of merged vectors, and
a pth set of merged vectors are the target vector data.

### Claim 5 (depends on 4)

The method according to claim 4, wherein the shifting and merging further comprises:
shifting and merging, by the data merging units in the qth set of data merging units, each two adjacent to-be-merged vectors in the qth set of to-be-merged vectors to obtain the qth set of merged vectors.

### Claim 6 (depends on 5)

The method according to claim 5, further comprising:
adding, by the data merging apparatus, a target to-be-merged vector in the qth set of to-be-merged vectors to the qth set of merged vectors in a case that a quantity of to-be-merged vectors in the qth set of to-be-merged vectors is an odd number, wherein
the target to-be-merged vector in the qth set of to-be-merged vectors is the first to-be-merged vector or the last to-be-merged vector in the qth set of to-be-merged vectors in ascending order of bits.

### Claim 7 (depends on 5)

The method according to claim 5, wherein
in a case that a first data merging unit in the qth set of data merging units shifts and merges a first to-be-merged vector and a second to-be-merged vector in the qth set of to-be-merged vectors, the shifting and merging comprises:
shifting, by the first data merging unit, the first to-be-merged vector based on the second to-be-merged vector to obtain an adjusted first to-be-merged vector; and
merging, by the first data merging unit, the adjusted first to-be-merged vector and the second to-be-merged vector to obtain a first merged vector corresponding to the qth set of merged vectors, wherein
an element corresponding to the second to-be-merged vector in the source vector data is at a lower bit than an element corresponding to the first to-be-merged vector in the source vector data.

### Claim 8 (depends on 7)

The method according to claim 7, wherein the shifting comprises:
filling, by the first data merging unit, the first to-be-merged vector with elements based on a quantity of elements in the second to-be-merged vector to obtain a filled first to-be-merged vector, wherein
a quantity of elements in the filled first to-be-merged vector is a sum of the quantity of the elements in the second to-be-merged vector and a quantity of elements in the first to-be-merged vector; and
shifting, by the first data merging unit, non-filling elements in the filled first to-be-merged vector as a whole based on a quantity of invalid elements in the second to-be-merged vector to obtain the adjusted first to-be-merged vector, wherein
a quantity of non-filling elements corresponding to a header of the adjusted first to-be-merged vector is the same as the quantity of the valid elements in the second to-be-merged vector.

### Claim 9 (depends on 7)

The method according to claim 7, wherein the merging comprises:
selecting, by the first data merging unit, elements corresponding to the first merged vector from the adjusted first to-be-merged vector and the second to-be-merged vector in ascending order of bits; and
selecting, by the first data merging unit for a kth element corresponding to the first merged vector, one of a kth element in the adjusted first to-be-merged vector and a kth element in the second to-be-merged vector as the kth element corresponding to the first merged vector, wherein
k is a positive integer.

### Claim 10 (depends on 9)

The method according to claim 9, wherein the selecting, by the first data merging unit, one of a kth element in the adjusted first to-be-merged vector and a kth element in the second to-be-merged vector as the kth element corresponding to the first merged vector comprises:
determining, by the first data merging unit, the kth element in the adjusted first to-be-merged vector as the kth element corresponding to the first merged vector in a case that the kth element in the adjusted first to-be-merged vector is a valid element; or
determining, by the first data merging unit, the kth element in the second to-be-merged vector as the kth element corresponding to the first merged vector in a case that the kth element in the second to-be-merged vector is a valid element.

### Claim 11 (depends on 1)

The method according to claim 1, wherein the n target sub-vectors are obtained through selective arrangement of valid elements of the n source sub-vectors performed by the n sets of multiplexers in parallel.

### Claim 12

A method for decompressing vector data by a processor comprising a target vector register, a data splitting apparatus, and n sets of multiplexers, wherein n is an integer greater than 1, the method comprising:
storing, by the target vector register, target vector data, wherein
first valid elements in the target vector data are located at a header of the target vector data;
shifting and splitting, by the data splitting apparatus, the target vector data to obtain n target sub-vectors, wherein
second valid elements in each of the target sub-vectors are located at a header of the target sub-vector; and
respectively decompressing, by the n sets of multiplexers, the n target sub-vectors to obtain n source sub-vectors, wherein
the n source sub-vectors are configured to be combined to obtain source vector data.

### Claim 13 (depends on 12)

The method according to claim 12, wherein the data splitting apparatus comprises m sets of data splitting units, the m sets of data splitting units are configured to perform p rounds of shifting and splitting on the target vector data to obtain the n target sub-vectors, wherein m is an integer greater than 1, and p is a positive integer; and the shifting and splitting comprises:
shifting and splitting, by a qth set of data splitting units in the m sets of data splitting units for a qth round of shifting and splitting a qth set of to-be-split vectors to obtain a qth set of split vectors, wherein
q is a positive integer less than or equal to p; and
in a case that q is equal to 1,
the qth set of to-be-split vectors are the target vector data, and
in a case that q is greater than 1,
the qth set of to-be-split vectors are a (q−1)th set of split vectors, and
a pth set of split vectors are the n target sub-vectors.

### Claim 14 (depends on 13)

The method according to claim 13, wherein
the qth set of split vectors comprise s split vectors corresponding to a first to-be-split vector in the qth set of to-be-split vectors, wherein
s is an integer greater than 1; and
in a case that a first data splitting unit in the qth set of data splitting units shifts and splits the first to-be-split vector, the s split vectors corresponding to the first to-be-split vector are obtained in the following manner:
determining, by the first data splitting unit, s split element quantities corresponding to the first to-be-split vector;
determining, by the first data splitting unit, s sets of valid split elements based on a boolean vector corresponding to the target vector data and the s split element quantities, an element in the boolean vector is used for indicating a distribution of valid elements in the source vector data;
respectively shifting, by the first data splitting unit, the s sets of valid split elements as a whole in the first to-be-split vector based on the s sets of valid split elements to obtain a shifted first to-be-split vector; and
splitting, by the first data splitting unit, the shifted first to-be-split vector based on the s split element quantities to obtain s split vectors corresponding to the first to-be-split vector.

### Claim 15 (depends on 14)

The method according to claim 14, wherein the respectively shifting comprises:
determining, by the first data splitting unit for a target split element quantity in the s split element quantities, a quantity of target to-be-shifted bits corresponding to the target split element quantity based on a difference between a position of a target valid split element corresponding to the target split element quantity in the first to-be-split vector and a position of the target split element corresponding to the target split element quantity in the boolean vector;
shifting, by the first data splitting unit, valid split elements in the first to-be-split vector corresponding to the target split element quantity as a whole based on the quantity of target to-be-shifted bits corresponding to the target split element quantity to obtain an intermediate first to-be-split vector; and
further shifting, by the first data splitting unit, the intermediate first to-be-split vector based on quantities of target to-be-shifted bits respectively corresponding to remaining split element quantities to obtain the shifted first to-be-split vector, wherein
the target valid split element corresponding to the target split element quantity is the last valid split element corresponding to the target split element quantity in descending order of bits, and
the target split element corresponding to the target split element quantity is the last split element corresponding to the target split element quantity in descending order of bits.

### Claim 16 (depends on 14)

The method according to claim 14, wherein
the s split vectors comprise a target split vector corresponding to a target split element quantity in the s split element quantities; and
the splitting comprises:
determining, by the first data splitting unit, a region corresponding to the target split vector corresponding to the target split element quantity in the boolean vector based on the target split element quantity;
determining, by the first data splitting unit, a target region corresponding to the target split vector in the shifted first to-be-split vector based on the region corresponding to the target split vector in the boolean vector; and
determining, by the first data splitting unit, an element in the target region as an element of the target split vector.

### Claim 17 (depends on 12)

The method according to claim 12, wherein
the respectively decompressing comprises:
determining, by a tth set of multiplexers in the n sets of multiplexers for a tth target sub-vector in the n target sub-vectors, a valid element position distribution corresponding to the tth target sub-vector in the n target sub-vectors based on a boolean vector corresponding to the target vector data, wherein
t is a positive integer less than or equal to n; and
successively arranging, by the tth set of multiplexers, valid elements in the tth target sub-vector to a position corresponding to the valid element position distribution in descending order of bits to obtain a tth source sub-vector corresponding to the tth target sub-vector.

### Claim 18 (depends on 12)

The method according to claim 12, wherein
the n source sub-vectors are obtained through decompression of the n target sub-vectors by the n sets of multiplexers in parallel.

### Claim 19

A method for compressing and decompressing vector data by a processor comprising a source vector register, a target vector register, n sets of multiplexers, a data merging apparatus, and a data splitting apparatus, where n is an integer greater than 1, the method comprising:
compressing the vector data, comprising:
storing, by the source vector register, source vector data, wherein
the source vector data is divided into n source sub-vectors, and
the n source sub-vectors are in a one-to-one correspondence with the n sets of multiplexers;
selectively arranging, by an ith set of multiplexers in the n sets of multiplexers, first valid elements in an ith source sub-vector in the source vector data to obtain an ith target sub-vector corresponding to the ith source sub-vector, wherein
the first valid elements in the ith target sub-vector are located at a header of the ith target sub-vector, and
i is a positive integer less than or equal to n;
shifting and merging, by the data merging apparatus, n target sub-vectors corresponding to the n source sub-vectors to obtain target vector data, wherein
second valid elements in the target vector data are located at a first header of the target vector data;
storing, by the target vector register, the second valid elements in the target vector data; and
decompressing the vector data, wherein
third valid elements in the target vector data are located at a second header of the target vector data;
shifting and splitting, by the data splitting apparatus, the target vector data to obtain n target sub-vectors, wherein
fourth valid elements in each of the target sub-vectors are located at a header of the target sub-vector; and
respectively decompressing, by the n sets of multiplexers, the n target sub-vectors to obtain the n source sub-vectors, wherein
the n source sub-vectors are configured to be combined to obtain source vector data.
