Methods, Systems, and Circuits for Coordinated Optimization in In-Memory Sorting

A computer-readable medium storing instructions, that when executed by a processing in memory (PIM) based system, cause the system to perform a method for sorting a dataset, the method comprising:

• receiving a request to sort a dataset stored in a 3D-stacked memory of the PIM-based system, wherein the request identifies a specific dataset and sorting criteria, wherein the sorting criteria includes a plurality of keys used to sort pieces of data in the dataset;
• partitioning the dataset into a plurality of subarrays across a plurality of memory banks within the 3D-stacked memory, wherein each subarray includes at least one piece of data from the dataset;
• separating each piece of data in each subarray into a plurality of buckets based on the plurality of keys, wherein each bucket corresponds to a particular key of the plurality of keys, wherein a same plurality of buckets is used for each subarray;
• generating a plurality of local histogram for each subarray, wherein each local histogram of a particular subarray corresponds to a particular bucket of the plurality of buckets, and wherein each local histogram indicates a frequency of a particular key in the corresponding bucket;
• generating a plurality of bank histograms based on the plurality of local histograms, wherein each bank histogram corresponds to a particular bucket of the plurality of buckets, wherein the generating comprises combining key counts from all local histograms corresponding to a same bucket of the plurality of buckets;
• performing a prefix-sum operation on the plurality of bank histograms to determine individual positions of the pieces of data for a sorted dataset;
• aggregating the subarrays from all memory banks to form the sorted dataset based on the individual positions;
• and
• returning the sorted dataset.

A processing in memory (PIM) based system for sorting a dataset, the system comprising:

• a 3D-stacked memory configured to store a dataset, the 3D-stacked memory including a plurality of memory banks and partitionable into a plurality of subarrays across the memory banks, wherein each subarray includes at least one piece of data from the dataset;
• a processing unit configured to receive a request to sort the dataset, the request identifying a specific dataset and sorting criteria, wherein the sorting criteria includes a plurality of keys used to sort pieces of data in the dataset;
• a plurality of subarray-level processing units (SPUs) operatively coupled to the subarrays, the SPUs configured to separate each piece of data in each subarray into a plurality of buckets based on the plurality of keys, wherein each bucket corresponds to a particular key of the plurality of keys, and to generate a plurality of local histograms for each subarray, wherein each local histogram of a particular subarray corresponds to a particular bucket of the plurality of buckets and indicates a frequency of a particular key in the corresponding bucket;
• a bank histogram generator configured to generate a plurality of bank histograms based on the plurality of local histograms, wherein each bank histogram corresponds to a particular bucket of the plurality of buckets, and wherein the generating comprises combining key counts from all local histograms corresponding to a same bucket of the plurality of buckets;
• a prefix-sum operation module configured to perform a prefix-sum operation on the plurality of bank histograms to determine individual positions of the pieces of data for a sorted dataset;
• and
• an aggregator configured to aggregate the subarrays from all memory banks to form the sorted dataset based on the individual positions and to return the sorted dataset.