Back to results
US 12,688,041 B2Granted
Vectorized operations for sparse kernels
AssigneeArm Limited
InventorsJoshua Randall, Jesse Garrett Beu, Krishnendra Nathella, Tuan Quang Ta
Life of this patent
Estimating the term…
Abstract
A data processing method and processor instructions are provided that leverage scatter operations to efficiently merge vector and matrix indices, as compared to standard matrix and vector operations, as well as merge other arithmetic results, lists of numbers, etc.
Claims17
A processor, comprising:
- an instruction decoder configured to decode instructions;
- and
- processing circuitry configured to perform data processing in response to instructions decoded by the instruction decoder,
- where, in response to one or more read instructions, the instruction decoder is configured to control the processing circuitry to read first and second vectors from a storage, each vector including at least index values,
- where, in response to a sequence of instructions, the instruction decoder is configured to control the processing circuitry to generate scatter index values for the first and second vectors based on the index values of the first and second vectors, and
- where, in response to one or more scatter instructions, the instruction decoder is configured to execute a scatter operation, using the scatter index values of the first and second vectors, to generate a sorted merged vector,
- where said generate scatter index values includes:
- generate baseline index values;
- for the first vector, in response to one or more comparison count instructions:
- generate greater than count values for the first vector, each greater than count value being associated with an index value of the first vector, and
- generate equal to count values for the first vector, each equal to count value being associated with an index value of the first vector;
- and
- for the second vector, in response to one or more comparison count instructions:
- generate greater than count values for the second vector, each greater than count value being associated with an index value of the second vector, and
- generate equal to count values for the second vector, each equal to count value being associated with an index value of the second vector.
12 more elements
A processor-based method, comprising:
- reading first and second vectors from a storage, each vector including at least index values;
- generating scatter index values for the first and second vectors based on the index values of the first and second vectors;
- and
- executing a scatter operation, using the scatter index values of the first and second vectors, to generate a sorted merged vector,
- where said generating scatter index values includes:
- generating baseline index values;
- and
- for the first vector:
- generating greater than count values for the first vector, each greater than count value being associated with an index value of the first vector,
- generating equal prefix sum values for the first vector, each equal prefix sum value being associated with an index value of the first vector,
- subtracting the equal prefix sum values from the greater than count values to generate difference values, and
- adding the baseline index values to the difference values to generate the scatter index values for the first vector,
- where each scatter index value is associated with a data value of the first vector.
10 more elements
A processor configured to:
- read first and second vectors from a storage, each vector including at least index values;
- generate scatter index values for the first and second vectors based on the index values of the first and second vectors;
- and
- execute a scatter operation, using the scatter index values of the first and second vectors, to generate a sorted merged vector,
- where said generate scatter index values includes:
- generate baseline index values;
- for the first vector:
- generate greater than count values for the first vector, each greater than count value being associated with an index value of the first vector, and
- generate equal to count values for the first vector, each equal to count value being associated with an index value of the first vector;
- for the second vector:
- generate greater than count values for the second vector, each greater than count value being associated with an index value of the second vector, and
- generate equal to count values for the second vector, each equal to count value being associated with an index value of the second vector;
- and
- generate the scatter index values for the first and second vectors based on the baseline index values, the greater than count values for the first and second vectors, and the equal to count values for the first and second vectors.
11 more elements
Dependencies are inferred from the claim text.