4
\$\begingroup\$

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();
}
\$\endgroup\$
3
\$\begingroup\$

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) );
        } );
    
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer; you had a good point about my recurring use of decltype(<expr>), so I've made a aliased typedef template <typename T> using SumType = decltype(std::declval<T>() + std::declval<T>()) and that has improved the conciseness of my code considerably. I'll change the begin()/end() member functions to the standalone functions, and try and add better line spacing. \$\endgroup\$ – Thomas Russell Aug 3 '14 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.