Katyusha's blog

1
// implementation of absSerial() above, but it is vectorized using CS149 intrinsics
2
void absVector(float* values, float* output, int N) {
3
  __cs149_vec_float x;
4
  __cs149_vec_float result;
5
  __cs149_vec_float zero = _cs149_vset_float(0.f);
6
  __cs149_mask maskAll, maskIsNegative, maskIsNotNegative;
7

8
//  Note: Take a careful look at this loop indexing.  This example
9
//  code is not guaranteed to work when (N % VECTOR_WIDTH) != 0.
10
//  Why is that the case?
11
  int i;
12
  for (i=0; i + VECTOR_WIDTH - 1 <N; i+=VECTOR_WIDTH) {
13

14
    // All ones
15
    maskAll = _cs149_init_ones();
16

17
    // All zeros
18
    maskIsNegative = _cs149_init_ones(0);
19

20
    // Load vector of values from contiguous memory addresses
21
    _cs149_vload_float(x, values+i, maskAll);               // x = values[i];
22

23
    // Set mask according to predicate
24
    _cs149_vlt_float(maskIsNegative, x, zero, maskAll);     // if (x < 0) {
25

26
    // Execute instruction using mask ("if" clause)
27
    _cs149_vsub_float(result, zero, x, maskIsNegative);      //   output[i] = -x;
28

29
    // Inverse maskIsNegative to generate "else" mask
30
    maskIsNotNegative = _cs149_mask_not(maskIsNegative);     // } else {
31

32
    // Execute instruction ("else" clause)
33
    _cs149_vload_float(result, values+i, maskIsNotNegative); //   output[i] = x; }
34

35
    // Write results back to memory
36
    _cs149_vstore_float(output+i, result, maskAll);
37
  }
38
  if (N % VECTOR_WIDTH == 0) return;
39
  i = N - VECTOR_WIDTH;
40
  maskAll = _cs149_init_ones();
41
  maskIsNegative = _cs149_init_ones(0);
42
  _cs149_vload_float(x, values + i, maskAll);
43
  _cs149_vlt_float(maskIsNegative, x, zero, maskAll);
44
  _cs149_vsub_float(result, zero, x, maskIsNegative);
45
  _cs149_mask_not(maskIsNegative);
46
  _cs149_vmove_float(result, x, maskIsNegative);
47
  _cs149_vstore_float(output, result, maskAll);
48
}

1
void clampedExpVector(float* values, int* exponents, float* output, int N) {
2

3
  //
4
//   CS149 STUDENTS TODO: Implement your vectorized version of
5
  // clampedExpSerial() here.
6
  //
7
  // Your solution should work for any value of
8
  // N and VECTOR_WIDTH, not just when VECTOR_WIDTH divides N
9
  //
10
    __cs149_mask maskAll = _cs149_init_ones();
11
    __cs149_vec_int zero = _cs149_vset_int(0);
12
    __cs149_vec_int one = _cs149_vset_int(1);
13

14
    auto calc = [&] (int i) {
15
        __cs149_vec_int count;
16
        _cs149_vload_int(count, exponents + i, maskAll);
17
        __cs149_vec_float base;
18
        _cs149_vload_float(base, values + i, maskAll);
19
        __cs149_vec_float result = _cs149_vset_float(1.f);
20
        __cs149_mask Ispositive;
21
        _cs149_vgt_int(Ispositive, count, zero, maskAll);
22
        while (_cs149_cntbits(Ispositive) > 0) {    //while(count > 0)
23
            _cs149_vmult_float(result, result, base, Ispositive);   //if (count[i] > 0) result[i] *= values[i]
24
            _cs149_vsub_int(count, count, one, maskAll);    //count--
25
            _cs149_vgt_int(Ispositive, count, zero, maskAll);
26
        }
27

28
        __cs149_vec_float bound = _cs149_vset_float(9.999999f);
29
        _cs149_vgt_float(Ispositive, result, bound, maskAll);   //if (result[i] > bound)
30
        _cs149_vmove_float(result, bound, Ispositive);  //result[i] = bound
31
        _cs149_vstore_float(output + i, result, maskAll); //output[i] = result[i]
32
    };
33

34
    for (int i = 0; i + VECTOR_WIDTH - 1 < N; i += VECTOR_WIDTH) {
35
        calc(i);
36
    }
37
    if (N % VECTOR_WIDTH == 0) return;
38
    calc(N - VECTOR_WIDTH);
39
}

1
CLAMPED EXPONENT (required)
2
Results matched with answer!
3
****************** Printing Vector Unit Statistics *******************
4
Vector Width:              4
5
Total Vector Instructions: 97070
6
Vector Utilization:        90.4%
7
Utilized Vector Lanes:     350981
8
Total Vector Lanes:        388280
9
************************ Result Verification *************************
10
Passed!!!

1
// returns the sum of all elements in values
2
// You can assume N is a multiple of VECTOR_WIDTH
3
// You can assume VECTOR_WIDTH is a power of 2
4
float arraySumVector(float* values, int N) {
5

6
  //
7
  // CS149 STUDENTS TODO: Implement your vectorized version of arraySumSerial here
8
  //
9
    __cs149_vec_float acc = _cs149_vset_float(0.f);
10
    __cs149_mask maskAll = _cs149_init_ones();
11

12
    for (int i=0; i<N; i+=VECTOR_WIDTH) {
13
        __cs149_vec_float vec_values;
14
        _cs149_vload_float(vec_values, values + i, maskAll);
15
        _cs149_vadd_float(acc, acc, vec_values, maskAll);
16
    }
17
    for (int i = 1; i < VECTOR_WIDTH; i <<=1) {
18
        _cs149_hadd_float(acc, acc);
19
        _cs149_interleave_float(acc, acc);
20
    }
21
    float *ptr = new float[VECTOR_WIDTH];
22
    _cs149_vstore_float(ptr, acc, maskAll);
23
    float result = ptr[0];
24
    delete ptr;
25
    return result;
26
}

1
[sqrt serial]:          [633.462] ms
2
[sqrt ispc]:            [168.335] ms
3
[sqrt task ispc]:       [13.948] ms
4
                                (3.76x speedup from ISPC)
5
                                (45.42x speedup from task ISPC)

1
[sqrt serial]:          [2752.093] ms
2
[sqrt ispc]:            [573.343] ms
3
[sqrt task ispc]:       [50.224] ms
4
                                (4.80x speedup from ISPC)
5
                                (54.80x speedup from task ISPC)

1
[sqrt serial]:          [420.101] ms
2
[sqrt ispc]:            [547.059] ms
3
[sqrt task ispc]:       [49.483] ms
4
                                (0.77x speedup from ISPC)
5
                                (8.49x speedup from task ISPC

1
export void sqrt_ispc(uniform int N,
2
                      uniform float initialGuess,
3
                      uniform float values[],
4
                      uniform float output[])
5
{
6
    foreach (i = 0 ... N) {
7

8
        float x = values[i];
9
        float guess = initialGuess;
10

11
        float pred = abs(guess * guess * x - 1.f);
12

13
        while (pred > kThreshold) {
14
            guess = (3.f * guess - x * guess * guess * guess) * 0.5f;
15
            pred = abs(guess * guess * x - 1.f);
16
        }
17

18
        output[i] = x * guess;
19

20
    }
21
}

1
static void AVX2_invsqrt(int n, float initialGuess, float values[], float outputs[]) {
2
    __m256 vec_one = _mm256_set1_ps(1.0f);
3
    __m256 vec_three = _mm256_set1_ps(3.0f);
4
    __m256 vec_half = _mm256_set1_ps(0.5f);
5
    __m256 vec_neg = _mm256_set1_ps(-0.0f);
6
    __m256 vec_threshold = _mm256_set1_ps(kThreshold);
7

8
    auto calc = [&](int i) {
9
        __m256 vec_x = _mm256_loadu_ps(values + i);
10
        __m256 vec_guess = _mm256_set1_ps(initialGuess);
11

12
        __m256 vec_pred = _mm256_mul_ps(vec_guess, vec_guess);
13
        vec_pred = _mm256_mul_ps(vec_pred, vec_x);
14
        vec_pred = _mm256_sub_ps(vec_pred, vec_one);
15
        vec_pred = _mm256_andnot_ps(vec_neg, vec_pred);
16

17
        __m256 mask = _mm256_cmp_ps(vec_pred, vec_threshold, _CMP_GT_OQ);
18
        while (_mm_popcnt_u32(_mm256_movemask_ps(mask))) {
19
            __m256 vec_sub, new_guess;
20
            new_guess = _mm256_mul_ps(vec_guess, vec_three);
21
            vec_sub = _mm256_mul_ps(vec_guess, vec_guess);
22
            vec_sub = _mm256_mul_ps(vec_sub, vec_guess);
23
            vec_sub = _mm256_mul_ps(vec_sub, vec_x);
24
            new_guess = _mm256_sub_ps(new_guess, vec_sub);
25
            new_guess = _mm256_mul_ps(new_guess, vec_half);
26
            vec_guess = _mm256_blendv_ps(vec_guess, new_guess, mask);
27

28
            __m256 new_pred;
29
            new_pred = _mm256_mul_ps(vec_guess, vec_guess);
30
            new_pred = _mm256_mul_ps(new_pred, vec_x);
31
            new_pred = _mm256_sub_ps(new_pred, vec_one);
32
            new_pred = _mm256_andnot_ps(vec_neg, new_pred);
33
            vec_pred = _mm256_blendv_ps(vec_pred, new_pred, mask);
34

35
            mask = _mm256_cmp_ps(vec_pred, vec_threshold, _CMP_GT_OQ);
36
        }
37

38
        _mm256_storeu_ps(outputs + i, _mm256_mul_ps(vec_guess, vec_x));
39
    };
40
    for (int i = 0; i + 7 < n; i += 8) calc(i);
41
    if (n % 8 == 0) return;
42
    calc(n - 8);
43
}

1
[sqrt serial]:          [425.807] ms
2
[sqrt ispc]:            [541.254] ms
3
[sqrt AVX2]:            [520.926] ms
4
[sqrt task ispc]:       [53.460] ms
5
                                (0.79x speedup from ISPC)
6
                                (0.82x speedup from AVX2)
7
                                (7.96x speedup from task ISPC)