Paper ID: 421
Title: Single-Pass List Partitioning
Authors: Leonor Frias, Johannes Singler, Peter Sanders
Abstract: Parallel algorithms divide computation among several
threads. In many cases, the input must also be divided. Consider an
input consisting of a linear sequence of elements whose length is
unknown a priori. We can evenly divide it naïvely by either traversing
it twice (first determine length, then divide) or by using linear
additional memory to hold an array of pointers to the
elements. Instead, we propose an algorithm that divides a linear
sequence into p parts of similar length traversing the sequence only
once, and using sub-linear additional space. The experiments show that
our list partitioning algorithm is effective and fast in practice.