Vectorized operations for sparse kernels

1 . 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.

2 . The processor according to claim 1 , where the sorted merged vector includes merged index values.

3 . The processor according to claim 1 , where:

each vector includes data values;

each index value is associated with a data value;

each scatter index value is associated with a data value;

the scatter operation is a scatter add operation that uses the scatter index values and data values of the first and second vectors to generate the sorted merged vector; and

the sorted merged vector includes merged data values.

4 . The processor according to claim 1 , where:

said generate greater than count values for the first vector includes:

for each index value of the first vector:

determine a number of index values of the second vector that are less than the index value of the first vector, and

generate a greater than count value equal to the number;

said generate equal to count values for the first vector includes:

for each index value of the first vector:

determine a number of index values of the first vector that are equal to the index value of the second vector, and

generate an equal to count value equal to the number;

said generate greater than count values for the second vector includes:

for each index value of the second vector:

determine a number of index values of the first vector that are less than the index value of the second vector, and

generate a greater than count value equal to the number; and

said generate equal to count values for the second vector includes:

for each index value of the second vector:

determine a number of index values of the second vector that are equal to the index value of the first vector, and

generate an equal to count value equal to the number.

5 . The processor according to claim 4 , where said generate scatter index values includes:

for the first vector:

generate equal prefix sum values for the first vector based on the equal to count values for the first vector, each equal prefix sum value being associated with an index value of the first vector,

subtract the equal prefix sum values from the greater than count values to generate difference values, and

add the baseline index values to the difference values to generate the scatter index values for the first vector; and

for the second vector:

generate equal prefix sum values for the second vector based on the equal to count values for the second vector, each equal prefix sum value being associated with an index value of the second vector,

subtract the equal prefix sum values from the greater than count values to generate difference values, each scatter index value being associated with an index value of the second vector, and

add the baseline index values to the difference values to generate the scatter index values for the second vector, each scatter index value being associated with an index value of the second vector.

6 . The processor according to claim 5 , where:

said generate equal prefix sum values for the first vector includes:

for a first index value of the first vector:

generate an equal prefix sum value equal to 0;

for each index value of the first vector subsequent to the first index value of the first vector:

determine a partial sum of the equal count values from preceding index values; and

generate an equal prefix sum value equal to the partial sum;

said generate equal prefix sum values for the second vector includes:

for a first index value of the second vector:

generate an equal prefix sum value equal to 0;

for each index value of the second vector subsequent to the first index value of the second vector:

determine a partial sum of the equal count values from preceding index values; and

generate an equal prefix sum value equal to the partial sum.

7 . 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.

8 . The processor-based method according to claim 7 , where the sorted merged vector includes merged index values.

9 . The processor-based method according to claim 7 , where:

each vector includes data values;

each index value is associated with a data value;

each scatter index value is associated with a data value;

the scatter operation is a scatter add operation that uses the scatter index values and data values of the first and second vectors to generate the sorted merged vector; and

the sorted merged vector includes merged data values.

10 . The processor-based method according to claim 7 , where said generating greater than count values for the first vector includes:

for each index value of the first vector:

determine a number of index values of the second vector that are less than the index value of the first vector; and

generating a greater than count value equal to the number.

11 . The processor-based method according to claim 10 , where said generating equal prefix sum values for the first vector includes:

for each index value of the first vector:

determining a number of index values of the second vector that are equal to the index value of the first vector;

generating an equal count value equal to the number;

for a first index value of the first vector:

generating an equal prefix sum value equal to 0;

for each index value of the first vector subsequent to the first index value of the first vector:

determining a partial sum of the equal count values from preceding index values; and

generating an equal prefix sum value equal to the partial sum.

12 . The processor-based method according to claim 11 , where said generating scatter index values includes:

for the second vector:

generating greater than count values for the second vector, each greater than count value being associated with an index value of the second vector;

generating equal prefix sum values for the second vector, each equal prefix sum value being associated with an index value of the second 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 second vector,

where each scatter index value is associated with a data value of the second vector.

13 . The processor-based method according to claim 12 , where said generating less than count values for the second vector includes:

for each index value of the second vector:

determining a number of index values of the first vector that are less than the index value of the second vector; and

generating a less than count value equal to the number.

14 . The processor-based method according to claim 13 , where said generating equal prefix sum values for the second vector includes:

for each index value of the second vector:

determining a number of index values of the first vector that are equal to the index value of the second vector;

generating an equal count value equal to the number;

for a first index value of the second vector:

generating an equal prefix sum value equal to 0;

for each index value of the second vector subsequent to the first index value of the second vector:

determining a partial sum of the equal count values from preceding index values; and

generating an equal prefix sum value equal to the partial sum.

15 . 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.

16 . The processor according to claim 15 , where the sorted merged vector includes merged index values.

17 . The processor according to claim 15 , where:

each vector includes data values;

each index value is associated with a data value;

each scatter index value is associated with a data value;

the scatter operation is a scatter add operation that uses the scatter index values and data values of the first and second vectors to generate the sorted merged vector; and

the sorted merged vector includes merged data values.