Simultaneous Parallel Reduction on SIMD Machines

Proper distribution of operations among parallel processors in a large scientific computation executed on a distributed-memory machine can significantly reduce the total computation time. In this paper we consider an operation, called simultaneous parallel reduction, that is amenable to such optimization. Simultaneous reduction performs reduction operations in parallel, each operation reducing a one-dimensional consecutive section of a distributed array. Every element of the distributed array is used as an operand to many reductions executed concurrently over the overlapping array's sections. The simultaneous reduction is distinct from a more commonly considered parallel reduction which involves the parallel evaluation of a single reduction. Several algorithms achieving some of the lower bounds on simultaneous reduction complexity are presented under various assumptions about the properties of the binary operator of the reduction and of the communication cost of the target architecture..