File ParallelMerge.h

↰ Parent directory (ADS/parallel)

The parallel merge of k sorted ranges, beyond the book: multiwayMerge( ex , R , out , less ) writes into out what multiwayMerge( R , out , less ) [see File MultiwayMerge.h] writes, the same items in the same order (on equal items the range of lower index first), on the threads of the executor ex [see File Executor.h].

Definition (ADS/parallel/ParallelMerge.h)

Detailed Description

The output of N items is cut into B parts of about N / B items, B = 4 p for p threads (at least :math:` 2^{14} ` items each), and the part that starts at rank r takes from each range i the items of ranks :math:` [ s_i( r ) , s_i( r’ ) ) , where :math: s( r ) ` is the exact multisequence selection: the split with :math:` sum_i s_i( r ) = r ` that leaves on its left the r least items in the total order of the triples ( item , range , position ), which is the order of the stable merge. Each part is then merged by the sequential multiwayMerge() into its place of the output, in parallel, so that no part waits for another. A split is found by narrowing a window :math:` [ lo_i , hi_i ) ` on each range: the pivot is the middle item x of the widest window, of range j and position m, and a binary search in each window counts the items before ( x , j , m ), those :math:` leq x ` in the ranges i < j and those < x in the ranges i > j; if they are fewer than r, x and all of them go to the left (each :math:` lo_i ` rises to its count, :math:` lo_j ` past x), otherwise to the right. The pivot is the middle item of a window, the weighted median of the middles of all the windows by their widths: the windows whose middles are on the side of x that goes lose half of their width, at least a quarter of the total, so that a split takes :math:` O( log( k N ) ) ` steps of k binary searches and a sort of k middles, :math:` O( k log N log( k N ) ) ` comparisons (the bound of the selection of Varman et al., up to a factor :math:` log k ); the splits are found in parallel, one per part, and cost far less than the merge, :math: O( N log k ) `.

The contracts [see File Contract.h]: the iterators are random access, each range sorted by less (an audit, as in the sequential merge), out does not overlap the ranges; the output sorted, with the items of the ranges (an audit). P. J. Varman, S. D. Scheufler, B. R. Iyer, G. R. Ricard, Merging multiple lists on hierarchical-memory multiprocessors, Journal of Parallel and Distributed Computing 12(2), 171-177, 1991, doi:10.1016/0743-7315(91)90022-2

  1. Singler, P. Sanders, F. Putze, MCSTL: the multi-core standard template library, Euro-Par 2007 Parallel Processing, LNCS 4641, 682-694, 2007, doi:10.1007/978-3-540-74466-5_72

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions