Parallel Sorting on the Hypercube Concurrent Processor
Tao Tang · 2005
This paper describes a generalized version of a previously published sort algorithm, parallel shell merge.[3] This version was implemented on the JPLKaltech Mark I11 hypercube concurrent processor. Each node starts out with a sublist of items to be sorted first internally, and then among the other nodes. Parallel shell merge is an algorithm used to produce a whole sorted list across the hypercube once each sublist is sorted internally. This version is general in the sense that it allows sublists of very different sizes to be sorted as well as being able to handle balanced sublists. This general version performs quite well when it is used to sort balanced loads of data; however, there are some efficiency losses due to the generalization, but they are acceptable. I. Background A prototype of SEQGEN, the software that verifies and expands high-level activities into low-level command sequences for PL flight projects, is in the process of development on the JPL/Caltech Mark I11 hypercube concurrent processor.[l1[21 The purpose of this prototype is to show that the process of generating commands and sending them to the spacecraft, generally called uplink, can be greatly sped up utilizing computers. Since SEQGEN spends a significant portion of its time sorting commands in time order, a sort algorithm is necessary for the best possible speed UP. 11. Parallel Sort The sort works as follows. Each node of the hypercube starts out containing a sublist of commands in which there are time fields to be sorted. Each sublist can be of any arbw size. The algorithm to be described is a generalization of shell merge. [3] The algorithm's prerequisite is that the sublist on each node is sorted; therefore, the sequential version of quick sort is applied to each sublist independently using the median-of-three method to select a pivot point where partition starts. Once each sublist is sorted independently by quick sort as node 0 node 1 node 3 node 2