Homepage: Tokyo University, Computer Center (JSPP = Joint Symposium on Parallel Processing, PSC = Parallel Software Contest)
Terms: en, jp, Committee package (Opening and closing dates: 04/19/99 - 05/26/99)
Target machine:
Sun Enterprise 10000TM Server (SolarisTM 2.5.1)
We use a parallel bucket sort and a parallel quick sort. In the first version, buckets have a fixed size dynamically allocated at the beginning of the program. As we don't know the size of the buckets, we allocate more space than actually needed, causing a loss of virtual memory. In the second version, buckets are divided into smaller buckets 'dynamically' allocated. The algorithm relies on many spin-lock operations. These programs didn't show any speed-up above 16 processors. Better results have been reached by first counting the elements in the input array in order to allocate the right memory each bucket needs. (Requires StackThreads/MP).
first version (SolarisTM 2.6 object files), second version (SolarisTM 2.6 object files), submission version (SolarisTM 2.5.1 object files)
Performance for a typical random input: execution time, profiler time, processors activity
Other (gnuplot) performance graphs: data in figpb{pbm}.dat, execution graphs in figpb{pbm}.gp, profiler graphs in figpb{pbm}.gp.
Thanks to: Yoshihiro Oyama, Kresten Krab Thorup, and Kenjiro Taura.
Bibliography:
