#2782

C++ AMP Extras: Tile Size Checking at Compile Time

Many tiled C++ AMP algorithms rely on the tile size being a an exact multiple of two, scan and reduce are both examples of this.

    template <int TileSize, typename T>
    void InclusiveScanAmpTiled(array_view<T, 1> input, 
        array_view<T, 1> output)
    {
        // ... 

Ideally you would like to check at compile time that the TileSize template parameter is a power of two. You can do this with a combination of static_assert and a template meta-program (TMP).

        static_assert(IsPowerOfTwoStatic<TileSize>::result, 
            "TileSize must be a power of 2.");

The IsPowerOfTwoStatic template program checks that the number only contains a single set bit and hence is a power of two.

    static const unsigned int Bit08 = 0x80;
    static const unsigned int Bit16 = 0x8000;
    static const unsigned int Bit32 = 0x80000000;

    template<unsigned int N> 
    struct IsPowerOfTwoStatic 
    {
        enum 
        { 
            result = 
                ((CountBitsStatic<N, Bit32>::result == 1) ? TRUE : FALSE)
        };
    };

    // While 1 is technically 2^0, for the purposes of calculating 
    // tile size it isn't useful.
    template <>
    struct IsPowerOfTwoStatic<1>
    {
        enum { result = FALSE };
    };

    template<unsigned int N, unsigned int MaxBit>
    struct CountBitsStatic
    {
        enum 
        { 
            result = (IsBitSetStatic<N, MaxBit>::result + 
                CountBitsStatic<N, (MaxBit >> 1)>::result) 
        };
    };

    // Ensure that template program terminates.
    template<unsigned int N>
    struct CountBitsStatic<N, 0>
    {
        enum { result = FALSE };
    };

    template<unsigned int N, int MaxBit>
    struct IsBitSetStatic
    {
        enum { result = (N & MaxBit) ? 1 : 0 };
    };

Essentially this recursively unfolds the CountBitsStatic bit counting function during compilation.

There are numerous other ways to count the number of set bits at runtime. I picked a template approach because I was on a meta-programming kick.

    template <unsigned int MaxBit>
    unsigned int CountBits(unsigned int n) 
    {
        return (n & 0x1) + CountBits<MaxBit-1>(n >> 1);
    }

    // template specialization to terminate the recursion when there's only one bit left
    template<>
    unsigned int CountBits<1>(unsigned int n) 
    {
        return n & 0x1;
    }

    BOOL IsPowerOfTwo(unsigned int n)
    {
        return (CountBits<32>(n) == 1);
    };

Other approaches are discussed in Best algorithm to count the number of set bits in a 32-bit integer?