Hardware accelerator for performing 1-dimensional k-means clustering in parallel

A computerized method, comprising:

• storing a plurality of 1-dimensional inputs to be clustered;
• performing k-means clustering on the 1-dimensional inputs sorted in non-descending order by implementing a dynamic programming algorithm on a hardware accelerator that computes a minimum within-cluster sum of squares matrix for a predetermined number of clusters and also computes a backtrack index of index values for the 1-dimensional inputs that produce the minimum values in the minimum within-cluster sum of squares matrix;
• and
• backtracking through the backtrack index to compute cluster labels for each of the 1-dimensional inputs, and outputting the cluster labels.

A computing system, comprising:

• processing circuitry and associated memory storing a plurality of 1-dimensional inputs to be clustered;
• and
• a hardware accelerator configured to:
• load the plurality of 1-dimensional inputs into global memory of the hardware accelerator;
• perform parallel execution of a k-means clustering program via each of a plurality of threads of a plurality of thread blocks executing on a plurality of processing elements of the hardware accelerator, at least in part by:
• at each thread block:
• looping through each thread on a first loop to:
• copy a respective predetermined number (N) of the 1-dimensional inputs from global memory into a respective memory bank of shared memory, such that each thread accesses a different one of the memory banks to retrieve its respective 1-dimensional inputs;
• and
• precompute a first constant (C1) and a second constant (C2) for each of the predetermined number of the 1-dimensional inputs and store precomputed values for the first constant (C1) and second constant (C2) in the respective memory bank for each thread in shared memory;
• and
• perform first syncing of the threads;
• loop through each thread in a second loop to:
• at each thread, loop through each element in a successive row of a minimum within-cluster sum of squares matrix, to:
• read one or more values in a source row of a ping pong buffer as inputs,
• compute a sum of squares based on the one or more source row values, the first constant and the second constant,
• evaluate the computed sum of squares for a minimum within-cluster sum of squares value, and
• write the computed minimum within-cluster sum of squares value to a target row of the ping-pong buffer in shared memory as output;
• write an index value for the 1-dimensional input with the minimum within-cluster sum of squares value to a backtrack index stored in global memory;
• backtrack through the backtrack index to identify the start of and end index value each cluster;
• label all 1-dimensional inputs with cluster labels;
• and
• output the cluster labels for the 1-dimensional inputs.