Parallelizing complex scans and reductions

Abstract

We present a method for automatically extracting parallel prefix programs from sequential loops, even in the presence of complicated conditional statements. Rather than searching for associative operators in the loop body directly, the method rests on the observation that functional composition itself is associative. Accordingly, we model the loop body as a multivalued function of multiple parameters, and look for a closed-form representation of arbitrary compositions of loop body instances. Careful analysis of conditionals allows this search to succeed in cases where existing automatic methods fail. The method has been implemented and used to generate code for the iWarp parallel computer.