Assignment 1-2: Vectorizing Code Using SIMD intrinsics

본 포스팅은 Stanford Univ. 의 CS149 2022 fall 수업을 정리한 내용임을 밝힙니다.

From smart phones, to multi-core CPUs and GPUs, to the world's largest supercomputers and web sites, parallel processing is ubiquitous in modern computing. The goal of this course is to provide a deep understanding of the fundamental principles and engineering trade-offs involved in designing modern parallel computing systems as well as to teach parallel programming techniques necessary to effectively utilize these machines. Because writing good parallel programs requires an understanding of key machine performance characteristics, this course will cover both parallel hardware and software design.

https://gfxcourses.stanford.edu/cs149/fall22/courseinfo

GitHub - stanford-cs149/asst1: Stanford CS149 -- Assignment 1

Stanford CS149 -- Assignment 1. Contribute to stanford-cs149/asst1 development by creating an account on GitHub.

https://github.com/stanford-cs149/asst1#program-2-vectorizing-code-using-simd-intrinsics-20-points

문제

prog2_vecintrin/main.cpp 에 보면 clampedExpSerial 함수가 있다. clampedExp() 함수는 values[i] 의 값을 exponents[i] 의 값으로 제곱하는데 9.999999. 에 clamp(clip) 되도록 설계된 함수이다. 본 과제에서 해야할 일은 SIMD vector instructions으로 돌아갈 수 있도록 이 코드를 vectorized 하는 것이다.

그런데 처음부터 SSE나 AVX2를 사용하여 vectorized 하면 어려울 수 있기 때문에 CS149intrin.h 에 정의된 “fake vector intrinsics”를 사용해서 이를 구현한다. 이는 modern CPUs 에서 구동되는 진짜 vectorized 함수가 아니라 그렇게만 보이게 작성된 함수이다. (디버깅 과정에서 더 나은 피드백을 제공하기 위함임.)

CS149 intrinsics를 사용하느 예제로 main.cpp 의 vectorized version의 abs() 함수를 살펴본다. 이 예제에서는 기본적인 vector load & store 연산과 mast registers를 다루는 방법을 소개한다. 이는 아주 쉬운 예제이고 모든 가능한 경우의 input을 다룬 것도 아니다. 구체적인 동작 과정을 알고 싶으면 CS149intrin.h 의 comments를 읽어보길 바람.

Hints

1. 모든 vector intrinsics는 optional mask parameter의 대상이 된다(?). mask parameter는 어떤 연산에 대해 masked 될 출력이 어떤 lanes에 있는지를 결정한다. $0$ 은 masked 된 것이며 따라서 주어진 연산이 적용되지 않는다. 어떤 연산에 대해 mask parameter가 주어지지 않으면, 모든 lanes에 어떤 mask도 적용되지 않음을 의미한다.

2. cs149_cntbits 함수를 사용할 수 있음

3. 반복문의 총 반복 횟수가 만약 SIMD vector width의 배수가 아니라며 어떻게 될지 고려한다. ./myexp -s 3 을 사용하여 테스트 해본다. Hint: cs149_init_ones 함수를 사용한다.

4. ./myexp -l 을 사용하여 각 vector instructions의 log들을 확인한다. addUserLog() 함수를 사용할 수 있고, CS149Logger.printLog() 함수도 알잘딱 사용한다.

프로그램의 실행 결과는 구현을 정확히 했는지의 여부를 나타낸다. 만약에 틀리면 아래와 같은 출력을 보여줌.

“output”이 내가 채워야할 곳임.

To Do

1. clampExpSerial()의 vectorized version인 clampExpVector() 함수를 구현한다. 어떠한 input array size (N), vector width(VECTOR_WIDTH) 에도 동작하도록 구현해야한다.

   void clampedExpVector(float* values, int* exponents, float* output, int N) {
   
     //
     // CS149 STUDENTS TODO: Implement your vectorized version of
     // clampedExpSerial() here.
     //
     // Your solution should work for any value of
     // N and VECTOR_WIDTH, not just when VECTOR_WIDTH divides N
     //
     
     // implementation in case of N % VECTOR_WIDTH == 0
     __cs149_vec_float value, result;
     __cs149_vec_int exponent, count;
     __cs149_vec_int zeros_int = _cs149_vset_int(0);
     __cs149_vec_int ones_int = _cs149_vset_int(1);
     __cs149_vec_float ones_float = _cs149_vset_float(1.0f);
     __cs149_mask maskAll, maskIf, maskElse, maskWhile, maskClamp;
     __cs149_vec_float clamp = _cs149_vset_float(9.999999f);
   
     for(int i=0; i<N; i+=VECTOR_WIDTH) {
   		// logic for in case that given arbitrary N
       if (i + VECTOR_WIDTH > N) {
         maskAll = _cs149_init_ones(N % VECTOR_WIDTH);   
   		}
       else {
         maskAll = _cs149_init_ones();
       }
   
       _cs149_vload_float(value, values+i, maskAll); // value = values[i:i+VECWID]
       _cs149_vload_int(exponent, exponents+i, maskAll); // exponent = expoenets[i:i+VECWID]
   
       // if exponent == zeros_int -> maskIf
       _cs149_veq_int(maskIf, exponent, zeros_int, maskAll); // if exponent == 0:
       _cs149_vstore_float(output+i, ones_float, maskIf); // then output[maskIf] = 1
   
       // else (if exponent != 0)
       maskElse = _cs149_mask_not(maskIf); // !maskIf -> maskElse
       maskElse = _cs149_mask_and(maskElse, maskAll);
       result = value;
       _cs149_vsub_int(count, exponent, ones_int, maskElse); // count = expontnt - 1
   
       maskWhile = maskElse;
       while (_cs149_cntbits(maskWhile)) { // if maskElse: 
         // if count > 0: -> maksElse
         _cs149_vgt_int(maskWhile, count, zeros_int, maskWhile); 
   
         _cs149_vmult_float(result, result, value, maskWhile); // result *= result
         _cs149_vsub_int(count, count, ones_int, maskWhile); // count -= 1
       }
   
       _cs149_vstore_float(output+i, result, maskElse); // output[maskElse] = result
       
       // if result > clamp(9.999999f) -> maskIf
       _cs149_vgt_float(maskClamp, result, clamp, maskElse); 
       maskClamp = _cs149_mask_and(maskClamp, maskElse);
       _cs149_vstore_float(output+i, clamp, maskClamp); // output[maskIf] = 9.999999f
     }
   }

2. ./myexp -s 10000 을 수행한다. 그리고 vector width를 2, 4, 8, 16 으로 바꾸어가며 수행해보고 vector utilization을 기록한다. CS149intrin.h 에 정의된 #define VECTOR_WIDTH 을 바꿔가며 수행해볼 수 있다. VECTOR_WIDTH 를 바꿈에 따라 vector utilization이 증가하는가? 감소하는가? 그대로인가? 왜 그런가?를 설명하라.

N	Utilization
10,000	67.6%
2	60.6%
4	78.1%
8	73.6%
16	73.1%

VECTOR_WIDTH도 바꿔보고 N도 바꿔보면서 수행 해보았는데, utilization은 VECTOR_WIDTH=4, N=4일 때 가장 좋았다. VECTOR_WIDTH가 다른 경우는 VECTOR_WIDTH==N 일 때 utilization이 가장 높았다.

VECTOR_WIDTH > N 에 대해서는 utilization은 항상 감소한다. 왜지?????????????????

1. Extra credit (1 pt.): vectorized version의 arrauySumSerial을 arraySumVector에 구현하라. 구현시에 VECTOR_WIDTH가 array size, N의 약수임을 가정해야할 수 도 있다. 원래 시간 복잡도는 O(N) 이지만, 최종적으로 O(N/VECTOR_WIDTH + VECTOR_WIDTH) 더 나아가 O(N / VECTOR_WIDTH + log2(VECTOR_WIDTH)) 를 목표로 한다.

   💡

   일단 킵

Uploaded by N2T