Processor-Oblivious Parallel Stream Computations

Abstract

We study the problem of parallel stream computations on a multiprocessor architecture. Modelling the problem, we exhibit that any parallelisation introduces an arithmetic overhead related to intermediate copy operations. We provide lower bounds for the parallel stream computation on p processors of different speeds with two models, a strict model and a buffered model; to our knowledge, these are new results. We introduce a new parallel algorithm called processor-oblivious: it is based on the coupling of a fast sequential algorithm with a fine-grain parallel one that is scheduled by work-stealing. This algorithm is proved asymptotically optimal. We show that our algorithm has a good experimental behaviour.