Boots – shoes – and leggings
Patent
1989-01-13
1993-01-12
Lee, Thomas C.
Boots, shoes, and leggings
395200, 395800, 3649622, 3649623, 3649314, 364DIG2, 3401462, G06F 706, G06F 716
Patent
active
051796996
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.
REFERENCES:
patent: 4030077 (1977-06-01), Florence et al.
patent: 4210961 (1980-07-01), Whitlow et al.
patent: 4575798 (1986-03-01), Lindstrom et al.
patent: 4595995 (1986-06-01), Alles
patent: 4794521 (1988-12-01), Zeigler et al.
patent: 4797815 (1989-01-01), Moore
patent: 4799152 (1989-01-01), Chuang et al.
patent: 4843542 (1989-06-01), Dashiell et al.
patent: 4862356 (1989-08-01), Van Trigt
patent: 4920487 (1990-04-01), Baffes
patent: 4951193 (1990-08-01), Muramatsu et al.
patent: 4991134 (1991-02-01), Ivsin
"A Benchmark Parallel Sort for Shared Memory Multiprocessors" R S Francis and I D Mathieson, IEEE Transactions on Computers, vol. 37, No. 12, Dec. 1988.
"An Efficient Percentile Partitioning Algorithm for Parallel Sorting" B R Iyer, G R Ricard, P J Varman RJ 6954 (66060) Aug. 9, 1989 Computer Science Research Report.
"Parallel Sorting Algorithms for tightly coupled multiprocessors", M J Quinn, Parallel Computing 6 (1988) 349-357, #3, Mar. 1988.
Iyer Balakrishna R.
Ricard Gary R.
Varman Peter J.
Forrest Bradley A.
International Business Machines - Corporation
Lee Thomas C.
Roth Steven W.
Treat William M.
LandOfFree
Partitioning of sorted lists for multiprocessors sort and merge does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Partitioning of sorted lists for multiprocessors sort and merge, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioning of sorted lists for multiprocessors sort and merge will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1226315