Data structure specifying differing fan-in tree and fan-out tree computation patterns supporting a generic reduction object for data parallelism

摘要

A data structure supporting a data-parallel reduction operation performed by a group of threads, a rope, participating in a multi-level two-phase tree structure: a fan-in computation phase followed by a fan- out broadcast phase. Local reductions are performed at each subtree during the fan-in phase, and the final reduced value is broadcast to all the threads during the fan-out phase. As the reduction operation is a data-parallel operation, the reduction operation is rope specific and is provided by the use of a parallel computation skeleton defined by the data structure which is a fan-in followed by the fan-out, a data-type specific binary operation, and a final broadcast that takes place in the reduction operation. When the rope object is constructed, the parallel computation skeleton is automatically constructed from information contained in the data structure. When a reduction operation is invoked, this parallel computation skeleton is used to build a data-type specific reduction object which is used by all the threads in the rope. The threads in a rope may perform type-specific reduction operations by cloning this parallel computation skeleton to a data-type specific reduction object for that type. This data-type specific reduction object is an instance of a template instance which is parametrized on two data- types: a data-type of the values used in the reduction operation and a type of a binary operation function object.