MULTIPLE PROCESSING CORE DATA SORTING

• US 20110055492A1
• Filed: 09/03/2009
• Published: 03/03/2011
• Est. Priority Date: 09/03/2009
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Hsu, Meichun, Zhang, Bin, Wu, Ren
• Application Number:
  US12/553,883
• Publication Number:
  US 20110055492A1
• Time in Patent Office: Days
• US Class Current: 711/149
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Sorting data using a multi-core processing system is disclosed. An unsorted data set is copied from a global memory device to a shared memory device. The global memory device can store data sets for the multi-core processing system. The shared memory device can store unsorted data sets for sorting. The unsorted data set can include a plurality of data elements. The unsorted data set can be sorted into sorted data in parallel on the shared memory device using a cluster of processors of the multi-core processing system. The cluster of processors may include at least as many processors as a number of the data elements in the unsorted data set. The sorted data can be copied from the shared memory device to the global memory device.

Claims

1. A multi-core processing system for data sorting, comprising:

a global memory device configured to store data sets;

a shared memory device configured to store data sets;

a plurality of processors comprising a plurality of clusters of processors, each cluster of processors further comprising shared processor memory, and each cluster of processors being configured to sort an unsorted data set in parallel in the shared processor memory, and wherein a selected cluster of processors comprises at least as many processors as a number of the data elements in the unsorted data set in shared processor memory; and

a data copy module configured to copy an unsorted data set from the global memory device to the shared processor memory for the clusters of processors to sort

2. A system in accordance with claim 1, wherein the data copy module is further configured to copy sorted data from the shared memory of the clusters of processors to the global memory device.

3. A system in accordance with claim 1, wherein the plurality of processors form a graphical processing unit (GPU).

4. A system in accordance with claim 1, wherein the plurality of processors form a central processing unit (CPU).

5. A system in accordance with claim 1, wherein each cluster of processors comprises a bitonic sorting network.

6. A system in accordance with claim 1, wherein each cluster of processors is configured to sort a different unsorted data set in parallel.

7. A system in accordance with claim 6, wherein the data copy module is configured to copy sorted data sets in parallel from each of the clusters of processors to the global memory device.

8. A system in accordance with claim 6, wherein the data copy module is configured to copy unsorted data sets in parallel from the global memory device to one or more of the clusters of processors.

9. A system in accordance with claim 1, wherein a processor in the cluster of processors sorts a data element substantially simultaneously with other processors in the cluster of processors which have data elements to sort.

10. A system in accordance with claim 1, wherein each processor in each cluster of processors is configured to execute same sorting steps.

17. A method in accordance with claim 11, wherein the cluster of processors forms a bitonic sorting network, and wherein sorting the unsorted data set further comprises performing a bitonic sort function.

11. A method for sorting data using a multi-core processing system, comprising:

copying an unsorted data set from a global memory device configured to store data sets for the multi-core processing system to a shared memory device configured to store the unsorted data set for sorting, the unsorted data set comprising a plurality of data elements; and

sorting the unsorted data set into sorted data in parallel on the shared memory device using a cluster of processors of the multi-core processing system, wherein the cluster of processors comprises at least as many processors as a number of the data elements in the unsorted data set.

12. A method in accordance with claim 11, further comprising copying the sorted data from the shared memory device to the global memory device.

13. A method in accordance with claim 11, further comprising mapping processors into the cluster of processors to efficiently maximize use of resources of the multi-core processing system.

14. A method in accordance with claim 13, wherein mapping processors further comprises logically mapping processors into processor clusters.

15. A method in accordance with claim 14, wherein processors in different clusters sort different data sets.

16. A method in accordance with claim 15, further comprising copying a plurality of sorted data sets in parallel from the shared memory device for each of the plurality of clusters of processors to the global memory device after each of the clusters of processors which received an unsorted data set has completed sorting the data set.

18. A method for sorting data using a multi-core processing system, comprising:

copying a first unsorted data set and a second unsorted data set from a global memory device configured to store sorted and unsorted data sets for the multi-core processing system to a shared memory device configured to store unsorted data sets for sorting, each of the first and second unsorted data sets comprising a plurality of data elements;

sorting the first unsorted data set into sorted first data in parallel on the shared memory device using a first cluster of processors of the multi-core processing system, wherein the first cluster of processors comprises at least as many processors as a number of the data elements in the unsorted data set;

sorting the second unsorted data set into sorted second data in parallel on the shared memory device using a second cluster of processors of the multi-core processing system, wherein the second cluster of processors comprises at least as many processors as a number of the data elements in the unsorted data set; and

copying the sorted first data and the sorted second data from the shared memory device to the global memory device.

19. A method in accordance with claim 18, wherein sorting the first unsorted data set is independent of sorting the second unsorted data set.

20. A method in accordance with claim 18, further comprising using the first and second sorted data sets to solve a mathematical model network.