IP Library › Granted Patent US 12693860

Granted Patent B2

US 12693860 · App. 19/035,792 · Granted Jul 28, 2026

Parallel index determination for compression instructions using prefix sums in a processing pipeline

Inventors: Alexander C. Rucker (Santa Clara, CA); Dongjie Xie (Austin, TX)

G06F9/30038 G06F9/30032 G06F9/30036 G06F9/30145 G06N20/00 G06N5/046

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 12693860
App. No.: 19/035,792
Granted: Jul 28, 2026
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

Systems and methods related to efficient compression instruction handling in a processing pipeline are disclosed herein. A processing pipeline may accept a mask vector from a first register, the mask vector including a set of set bits, and may accept a payload from a second register. The processing pipeline may determine a set of prefix sums for a set of portions of the mask vector by applying the portions to a set of adders in parallel to add the set bits independently for each of the portions. The processing pipeline may determine a set of indexes for the set bits, with respect to the mask vector, in parallel, using the set of prefix sums and the set of portions of the mask vector. The processing pipeline may store a set of identified values from the payload, as identified by the set of indexes, in at least one destination register.

Claims (171)

1 . A method for executing a compression instruction in a processing pipeline comprising:

accepting a mask vector from a first register, wherein the mask vector includes a set of set bits;

accepting a payload from a second register;

determining a set of prefix sums for a set of portions of the mask vector by applying the portions in the set of portions to a set of adders in parallel to add the set bits in the set of set bits independently for each of the portions in the set of portions;

determining a set of indexes for the set bits in the set of set bits, with respect to the mask vector, in parallel, using the set of prefix sums and the set of portions of the mask vector; and

storing a set of identified values from the payload as identified by the set of indexes in a set of at least one destination registers;

wherein the compression instruction is broken into a first microoperation, a second microoperation, and a third microoperation by the processing pipeline;

wherein the first microoperation runs once per execution of the compression instruction and conducts the determining of the set of prefix sums;

wherein the second microoperation runs one or more times per execution of the compression instruction, after the first microoperation is complete, and conducts the determining of the set of indexes; and

wherein the third microoperation runs once for each destination register of the set of at least one destination registers per execution of the compression instruction and conducts the storing of the set of identified values.

2 . The method for executing the compression instruction in the processing pipeline of claim 1 , wherein:

the processing pipeline is a RISC-V processing pipeline;

the compression instruction is a vcompress instruction; and

the third microoperation uses a logic circuit that is also used by the processing pipeline when executing a vrgather instruction to select elements from an operand of the vrgather instruction.

3 . The method for executing the compression instruction in the processing pipeline of claim 1 , further comprising:

determining a length of the payload; and

conditioning the execution of the determining of the set of prefix sums for the set of portions of the mask vector on the length of the payload being above a threshold.

4 . The method for executing the compression instruction in the processing pipeline of claim 3 , further comprising:

conditioning a generation of a microoperation on the length of the payload being below the threshold;

wherein the microoperation, if executed, determines the set of indexes for the set bits in the set of set bits, with respect to the mask vector, without using the set of prefix sums.

5 . The method for executing the compression instruction in the processing pipeline of claim 1 , wherein the determining of the set of indexes for the set bits in the set of set bits comprises:

searching, by a first search circuit, for a first index that corresponds with a first set bit in the set of set bits in the mask vector, the searching by the first search circuit comprising:

identifying, by the first search circuit and using the set of prefix sums, a first portion of the mask vector containing the first set bit;

scanning, by the first search circuit, the first portion of the mask vector based on identifying the first portion of the mask vector; and

identifying, by the first search circuit, the first set bit based on scanning the first portion of the mask vector; and

searching, by a second search circuit, for a second index that corresponds with a second set bit in the set of set bits in the mask vector, the searching by the second search circuit comprising:

identifying, by the second search circuit and using the set of prefix sums, a second portion of the mask vector containing the second set bit;

scanning, by the second search circuit, the second portion of the mask vector based on identifying the second portion of the mask vector; and

identifying, by the second search circuit, the second set bit based on scanning the second portion of the mask vector;

wherein the searching by the first search circuit and the searching by the second search circuit are conducted in parallel.

6 . The method for executing the compression instruction in the processing pipeline of claim 5 , further comprising:

writing, by the first search circuit, the first index of the first set bit to a destination register; and

writing, by the second search circuit, the second index of the second set bit to the destination register.

7 . A system for executing a compression instruction in a processing pipeline comprising:

means for accepting a mask vector from a first register, wherein the mask vector includes a set of set bits;

means for accepting a payload from a second register;

means for determining a set of prefix sums for a set of portions of the mask vector by applying the portions in the set of portions to a set of adders in parallel to add the set bits in the set of set bits independently for each of the portions in the set of portions;

means for determining a set of indexes for the set bits in the set of set bits, with respect to the mask vector, in parallel, using the set of prefix sums and the set of portions of the mask vector; and

means for storing a set of identified values from the payload as identified by the set of indexes in a set of at least one destination registers;

wherein the compression instruction is broken into a first microoperation, a second microoperation, and a third microoperation by the processing pipeline;

wherein the first microoperation runs once per execution of the compression instruction and conducts the determining of the set of prefix sums;

8 . The system for executing the compression instruction in the processing pipeline of claim 7 , wherein:

the processing pipeline is a RISC-V processing pipeline;

the compression instruction is a vcompress instruction; and

the third microoperation uses a logic circuit that is also used by the processing pipeline when executing a vrgather instruction to select elements from an operand of the vrgather instruction.

9 . The system for executing the compression instruction in the processing pipeline of claim 7 , further comprising:

determining a length of the payload; and

conditioning the execution of the determining of the set of prefix sums for the set of portions of the mask vector on the length of the payload being above a threshold.

10 . The system for executing the compression instruction in the processing pipeline of claim 9 , further comprising:

conditioning a generation of a microoperation on the length of the payload being below the threshold;

wherein the microoperation, if executed, determines the set of indexes for the set bits in the set of set bits, with respect to the mask vector, without using the set of prefix sums.

11 . The system for executing the compression instruction in the processing pipeline of claim 7 , wherein the determining of the set of indexes for the set bits in the set of set bits comprises:

means for searching, by a first search circuit, for a first index that corresponds with a first set bit in the set of set bits in the mask vector, the means for searching by the first search circuit comprising:

means for identifying, by the first search circuit and using the set of prefix sums, a first portion of the mask vector containing the first set bit;

means for scanning, by the first search circuit, the first portion of the mask vector based on identifying the first portion of the mask vector; and

means for identifying, by the first search circuit, the first set bit based on scanning the first portion of the mask vector; and

means for searching, by a second search circuit, for a second index that corresponds with a second set bit in the set of set bits in the mask vector, the means for searching by the second search circuit comprising:

means for identifying, by the second search circuit and using the set of prefix sums, a second portion of the mask vector containing the second set bit;

means for scanning, by the second search circuit, the second portion of the mask vector based on identifying the second portion of the mask vector; and

means for identifying, by the second search circuit, the second set bit based on scanning the second portion of the mask vector;

wherein the searching by the first search circuit and the searching by the second search circuit are conducted in parallel.

12 . The system for executing the compression instruction in the processing pipeline of claim 11 , further comprising:

means for writing, by the first search circuit, the first index of the first set bit to a destination register; and

means for writing, by the second search circuit, the second index of the second set bit to the destination register.

13 . A processor comprising:

a processing pipeline executing a compression instruction;

a first register storing a mask vector, wherein the mask vector includes a set of set bits;

one or more second registers storing a payload;

a set of adders, the set of adders adding, in parallel, set bits in the set of set bits of portions of the mask vector independently for each portion in a set of portions of the mask vector to determine a set of prefix sums for the set of portions of the mask vector;

a set of search circuits with access to the set of prefix sums, the set of search circuits comparing, in parallel, the set bits with at least one prefix sum in the set of prefix sums to determine a set of indexes for the set bits, with respect to the mask vector, using the set of portions of the mask vector; and

a set of at least one destination registers storing a set of identified values from the payload as identified by the set of indexes;

wherein the compression instruction is broken into a first microoperation, a second microoperation, and a third microoperation by the processing pipeline;

wherein the first microoperation runs once per execution of the compression instruction and conducts the determining of the set of prefix sums;

14 . The processor of claim 13 , wherein:

the processing pipeline is a RISC-V processing pipeline;

the compression instruction is a vcompress instruction; and

the third microoperation uses a logic circuit that is also used by the processing pipeline when executing a vrgather instruction to select elements from an operand of the vrgather instruction.

15 . The processor of claim 13 , wherein:

the execution of the determining of the set of prefix sums for the set of portions of the mask vector is conditioned on a length of the payload being above a threshold.

16 . The processor of claim 15 , wherein:

a generation of a microoperation is conditioned based on the length of the payload being below the threshold; and

the microoperation, if executed, determines the set of indexes for the set bits in the set of set bits, with respect to the mask vector, without using the set of prefix sums.

17 . The processor of claim 13 , wherein:

a first search circuit in the set of search circuits searches for a first index that corresponds with a first set bit in the set of set bits in the mask vector by: (i) identifying a first portion of the mask vector containing the first set bit, (ii) scanning the first portion of the mask vector based on identifying the first portion of the mask vector, and (iii) identifying the first set bit based on scanning the first portion of the mask vector;

a second search circuit in the set of search circuits searches for a second index that corresponds with a second set bit in the set of set bits in the mask vector by: (i identifying a second portion of the mask vector containing the second set bit, (ii) scanning the second portion of the mask vector based on identifying the second portion of the mask vector, and (iii) identifying the second set bit based on scanning the second portion of the mask vector; and

the searching by the first search circuit and the searching by the second search circuit are conducted in parallel.

18 . A method for executing a compression instruction in a processing pipeline comprising:

accepting a mask vector from a first register, wherein the mask vector includes a set of set bits;

accepting a payload from a second register;

determining a length of the payload;

conditioning the execution of the determining of the set of prefix sums for the set of portions of the mask vector on the length of the payload being above a threshold;

determining a set of indexes for the set bits in the set of set bits, with respect to the mask vector, in parallel, using the set of prefix sums and the set of portions of the mask vector; and

storing a set of identified values from the payload as identified by the set of indexes in a set of at least one destination registers.

19 . The method for executing the compression instruction in the processing pipeline of claim 18 , further comprising:

conditioning a generation of a microoperation on the length of the payload being below the threshold;

wherein the microoperation, if executed, determines the set of indexes for the set bits in the set of set bits, with respect to the mask vector, without using the set of prefix sums.

20 . A method for executing a compression instruction in a processing pipeline comprising:

accepting a mask vector from a first register, wherein the mask vector includes a set of set bits;

accepting a payload from a second register;

determining a set of indexes for the set bits in the set of set bits, with respect to the mask vector, in parallel, using the set of prefix sums and the set of portions of the mask vector; and

storing a set of identified values from the payload as identified by the set of indexes in a set of at least one destination registers;

wherein the determining of the set of indexes for the set bits in the set of set bits comprises: