Advanced Micro Devices, Inc.
Spatial pipelining of software reductions and scans

Abstract:

A compute unit includes single-instruction-multiple-data (SIMD) lanes that implement a pipeline. The compute unit also includes a scheduler to schedule the SIMD lanes to apply a binary associative operation to pairs of elements associated with ordered sets of elements. Subsets of the SIMD lanes concurrently apply the binary associative operation to pairs of elements at different levels of upsweep trees associated with the ordered sets of elements. Application of the binary associative operation is used to perform a reduction operation or a scan operation on the ordered sets of elements. In the case of a scan operation, the scheduler schedules the SIMD lanes to concurrently apply the binary associative operation to pairs of elements at different levels of downsweep trees associated with the ordered sets of elements subsequent to applying the binary associative operation at different levels of the upsweep trees.