Parallel Reduction method with C++AMP

Question

I am writing a C++AMP library, and as one of my utility methods I am implementing a parallel reduction algorithm based on the cascade method documented on this blog post with slight improvements by utilizing asynchronous CPU execution.

Does anyone have any performance/correctness/language improvements to offer?

template <typename T, std::size_t TileSize = DEFAULT_TILE_SIZE, std::size_t NumTiles = DEFAULT_NUM_TILES>
auto ParallelAccumulate( const concurrency::array_view<const T, 1>& avData ) -> decltype(std::declval<T>() + std::declval<T>())
{
    static_assert(IsPowerOfTwo( TileSize ), "Tile Size must be a power of two");
    static_assert(is_amp_compatible<T>::value, "The internal type of the array_view must be amp comptible");
    static_assert(NumTiles > 0, "There must be a non-zero number of tiles");

    std::size_t sArrayLength = avData.extent.size();
    const std::size_t sStrideLength = TileSize * NumTiles * 2U;

    // Accumulate tail (if necessary):
    const std::size_t sTailLength = sArrayLength % sStrideLength;
    std::future<decltype(std::declval<T>() + std::declval<T>())> futTailSum;
    if( sTailLength != 0 )
    {
        std::vector<T> vecTail( sTailLength );
        concurrency::copy( avData.section( concurrency::index<1>( sArrayLength - sTailLength ) ), vecTail.begin() );
        futTailSum = std::async( std::launch::async, [&vecTail]{ return concurrency::parallel_reduce( vecTail.begin(), vecTail.end(), static_cast<T>(0) ); } );

        if( (sArrayLength -= sTailLength) == 0 )
        {
            return futTailSum.get();
        }
    }

    concurrency::array<decltype(std::declval<T>() + std::declval<T>()), 1> arrPartialResult( NumTiles );
    concurrency::parallel_for_each( concurrency::extent<1>( TileSize * NumTiles ).tile<TileSize>(), [=, &arrPartialResult]( concurrency::tiled_index<1> tIndex ) restrict( amp ) {
        tile_static decltype(std::declval<T>() + std::declval<T>()) tTileData[TileSize];
        std::size_t sLocalIndex = tIndex.local[0];

        std::size_t sInputIndex = (tIndex.tile[0] * 2U * TileSize) + sLocalIndex;
        tTileData[sLocalIndex] = static_cast<decltype(std::declval<T>() + std::declval<T>())>(0);

        do {
            tTileData[sLocalIndex] += avData[sInputIndex] + avData[sInputIndex + TileSize];
            sInputIndex += sStrideLength;
        } while( sInputIndex < sArrayLength );

        tIndex.barrier.wait();

        for( std::size_t sStride = TileSize / 2U; sStride > 0; sStride /= 2U )
        {
            if( sLocalIndex < sStride )
            {
                tTileData[sLocalIndex] += tTileData[sLocalIndex + sStride];
            }

            tIndex.barrier.wait();
        }

        if( sLocalIndex == 0 )
        {
            arrPartialResult[tIndex.tile[0]] = tTileData[0];
        }
    } );

    std::vector<decltype(std::declval<T>() + std::declval<T>())> vecPartialResult( NumTiles );
    concurrency::copy( arrPartialResult, vecPartialResult );
    return concurrency::parallel_reduce( vecPartialResult.begin(), vecPartialResult.end(), static_cast<T>(0) ) + futTailSum.get();
}

Answer 1

I only see some possible stylistic/reusability improvements:

• You use decltype(std::declval<T>() + std::declval<T>()) five times in the function (plus the one in the return type). You could probably typedef that to improve readability. I don't know how you would call it, but I am pretty sure that you can find a meaningful name.

• By the way, are there many types for which decltype(std::declval<T>() + std::declval<T>) is different from T while still being amp compatible? If it is the case, that may break some other pieces of your code anyway (I didn't check though; that's a wild guess).

• Whenever possible, try to use std::begin and std::end instead of the member functions. It helps to write reusable code; you might someday want to extract parts of your function to write smaller and more generic functions that could work on old C arrays.

• By default, if you don't specify the rank of an array_view, it is one. Therefore, you actually don't have to specify it since you always use 1.

• Your lines are really long. As I said in the comments, you might want to split some of them to improve readability:

  futTailSum = std::async( std::launch::async, [&vecTail]
      {
          return concurrency::parallel_reduce( std::begin(vecTail),
                                               std::end(vecTail),
                                               static_cast<T>(0) );
      } );