An optimal parallelization of the two-list algorithm of cost O(2~(n/2))

摘要

In 1994, Chang et al. [Parallel Computing 20 (1994)] claimed a parallelization of the two-list algorithm of cost O(2~(5n/8)) based on a shared memory CREW SIMD PRAM model of computation. In 1997, Lou and Chang [Parallel Computing 22 (1997)] proposed a nov