Partitioning of sorted lists for multiprocessors sort and merge
US5179699A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jan 13, 1989 |
| Grant date | Jan 12, 1993 |
| Priority date | — |
| Expiry date | Jan 13, 2009 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99937
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Any number of sorted lists are efficiently partitioned into P lists, where P represents the number of processors available to sort the resulting lists. When given a large list to sort, the list is initially divided into P lists, and each processor sorts one of these lists. The lists are then exactly partitioned so that each of the elements in the new consecutive partitioned lists have values no smaller than any of the elements in the lists before it, nor larger than any of the elements in the list following it. Partitioning is done by P-1 processors. Each of the processors successively considers selected rows of elements from the sorted lists, and moves a partition boundary based on an element magnitude requirement and a partition size requirement. The new partitioned lists are then merged by the P processors, and simply strung together to provide a sorted list of all the elements.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.