Study: related project, and proposals

[larryxiao]

• SIMD wrapper library
  • Vc - Overview - Code@Compeng
  • Project Ne10: An Open Optimized Software Library Project for the ARM Architecture @ GitHub
• Proposals
  • SIMD Types: The Vector Type & Operations
  • SIMD Types: The Mask Type & Write-Masking
• Discussions
  • AVX-512 is a big step forward - but repeating past mistakes!
• Optimization
  • Optimizing Code for ARM Cortex-A8 with NEON SIMD - MAV Computer Vision Student Team (est. 2009)

[larryxiao]

Vc - Overview - Code@Compeng

• Vc: A C++ library for explicit vectorization
  • 1.2. Previous Work on SIMD Abstractions
  • EVE library, support AltiVec of PowerPC, not free, not heterogenous
  • macstl, support AltiVec of PowerPC, not free, not heterogenous
  • 1.3. Limits of Compiler Auto-Vectorization
  • [ ] auto vectorization wasn't good, any update?
  • 2.2. Vectorization Direction
  • Vertical, Horizontal
  • 3.1. API
  • Developing vectorized code requires the use of conditional assignment/write-masking.
    • <vector object> [(<mask object>)] <assignment operator> <vector object>.
  • Question
  • [X] What to do when using struct bigger than SIMD register width? (heterogenous means I can use 256-bit cross arch)
    • can break it down to operations using multiple supported witdh regitser
    • answer: in Vc, there's no size to declare. checkout examples
  • [X] Do I have to declare the width to use? (I might want to use as much as possible)
    • answer: This size is determined by the target architecture and therefore known at compile time

[larryxiao]

SIMD Types: The Vector Type & Operations

• [X] 1 About This Document
• [X] 2 Introduction
• [X] 3 SIMD Vector T ype Requirements
• [X] 4 The Vc::Vector Class
• [X] 5 SIMD Vector Initialization
  • broadcasts, conversions
• [X] 6 Loads and Stores
  • converting, load/store flags, alignment, non-temporal access, prefetching
• [X] 7 Unary Operators
  • increment, decrement, logical negation, one’s complement, unary +, and unary -
  • integral promotion
  • Deep C: Integer Promotion - Carpe diem (Felix's blog)
  • [ ] why you can calculate as 2^16 - 40000?

// from the proposal
unsigned short a = 40000;
auto b = -a; // decltype(b) == int

ushort_v v = 40000;
auto w = -v; // decltype(w) == ushort_v

assert(b == w[0]); // this fails

#include <stdio.h>

int main(int argc, const char *argv[])
{
    unsigned short a = 40000;
    unsigned short b = -a;
    printf("a 0x%08x %d, b 0x%08x %d\n", a, a, b, b);  
    // a 0x00009c40 40000, b 0x000063c0 25536
    return 0;
}

• [X] 8 Binary Operators
  • arithmetic, comparison, bitwise, and shift operations
  • EntryType: integral, non-integral, non-member
• [x] 9 Compound Assignment Operators
• [X] 10 Subscript Operators
  • The issue is that the non-const subscript operator needs to return an lvalue reference to the scalar type (EntryReference) and assignment to this lvalue reference needs to modify the SIMD vector, which is of type VectorType.
  • Strict Aliasing
• [X] 11 Gather & Scatter
  • arbitrary nesting of structs and arrays
• [X] 12 Selecting the Default SIMD Vector Type
• [X] 13 Interface to Internal Data
• [X] 14 Design Alternatives
  • Declare multiple Vector class templates in separate namespaces for each possible SIMD target (Listing 27). This design has been discussed in Section 4 in detail and is the class design used in the Vc library.
• [X] 15 Conclusion
• [X] A Vectorized STL Algorithms
  • A possible implementation of a vectorized std::for_each.
• [X] B The AdaptSubscriptOperator class
• [X] C Acknowledgements
• [X] D References

[larryxiao]

SIMD Types: The Mask Type & Write-Masking

• [X] 1 About This Document
• [X] 2 General Introduction to Conditionals
• [X] 3 Conditionals in SIMD Context
  • For the Vc library I therefore decided that the semantics of if, for, while, and switch must not change for explicit SIMD programming
• [X] 4 The Vc::Mask Class
  • reduction functions: all_of, any_of ..
• [X] 5 Write-Masking
  • conditional operator, Vc::where,
• [X] 6 Masked Gather & Scatter
• [X] 7 Conclusion
• [X] A Example: Mandelbrot
• [X] B Acknowledgements
• [X] C References
• Listing 12: A Vc implementation of the Mandelbrot algorithm.

typedef SimdArray<int, float_v::Size> IV;
for (int y = 0; y < imageHeight; ++y) {
    const float_v c_imag = y0 + y * scale;
    for (IV x = IV::IndexesFromZero(); any_of(x < imageWidth);
        x += float_v::Size) {
        const std::complex<float_v> c(x0 + x * scale, c_imag);
    std::complex<float_v> z = c;
    IV n = 0;
    auto inside = norm(z) < 4.f;
    while (any_of(inside && n < 255)) {
        z = z * z + c;
        where(inside) | n += 1;
        inside = norm(z) < 4.f;
    }
    IV colorValue = 255 - n;
    colorizeNextPixels(colorValue);
}

• examples/mandelbrot/mandel.cpp in vc/vc:master - Gitorious

template<> void Mandel::mandelMe(QImage &image, float x0,
        float y0, float scale, int maxIt)
{
    typedef MyComplex Z;
    const unsigned int height = image.height();
    const unsigned int width = image.width();
    const float_v colorScale = 0xff / static_cast(maxIt);
    for (unsigned int y = 0; y < height; ++y) {
        unsigned int *VC_RESTRICT line = reinterpret_cast(image.scanLine(y));
        const float_v c_imag = y0 + y * scale;
        uint_m toStore;
        for (uint_v x = uint_v::IndexesFromZero(); !(toStore = x < width).isEmpty();
                x += float_v::Size) {
            const float_v c_real = x0 + static_cast(x) * scale;
            Z z(c_real, c_imag);
            float_v n = float_v::Zero();
            float_m inside = z.norm() < S;
            while (!(inside && n < maxIt).isEmpty()) {
                z = P(z, c_real, c_imag);
                ++n(inside);
                inside = z.norm() < S;
            }
            uint_v colorValue = static_cast((maxIt - n) * colorScale) * 0x10101;
            if (toStore.isFull()) {
                colorValue.store(line, Vc::Unaligned);
                line += uint_v::Size;
            } else {
                colorValue.store(line, toStore, Vc::Unaligned);
                break; // we don't need to check again wether x[0] + float_v::Size < width to break out of the loop
            }
        }
        if (restart()) {
            break;
        }
    }
}