자동 벡터화

Automatic vectorization
프로그래밍 용어로서의 벡터화는 어레이 프로그래밍을 참조하십시오.래스터 그래픽을 벡터 그래픽으로 자동 변환하려면 자동 이미지 추적을 참조하십시오.

병렬 컴퓨팅에서 자동 벡터화는 컴퓨터 프로그램이 한 번에 한 쌍의 피연산자를 처리하는 스칼라 구현에서 여러 쌍의 피연산자에 대해 한 번의 연산을 동시에 처리하는 벡터 구현으로 변환되는 특별한 경우입니다.예를 들어, 특수한 슈퍼컴퓨터를 포함한 현대의 기존 컴퓨터에는 일반적으로 벡터 연산이 있으며, 벡터 연산은 (SIMD 또는 SPMD 하드웨어를 통해) 다음 4개의 추가와 같은 연산을 동시에 수행합니다.

그러나 대부분의 프로그래밍 언어에서는 일반적으로 다수의 숫자를 순차적으로 추가하는 루프를 작성합니다.이러한 루프의 예를 C로 나타냅니다.

위해서 (i = 0; i < > n; i++)     c[i] = a[i] + b[i];

벡터화 컴파일러는 이러한 루프를 벡터 연산의 시퀀스로 변환한다.이러한 벡터 연산은 어레이의 요소 블록에 추가를 수행합니다.a,b그리고.c자동 벡터화는 컴퓨터 [citation needed]과학의 주요 연구 주제이다.

배경

초기 컴퓨터는 보통 논리 유닛을 하나씩 가지고 있었는데, 이것은 한 번에 한 쌍의 오퍼랜드에 대해 하나의 명령을 실행했다.따라서 컴퓨터 언어와 프로그램은 순차적으로 실행되도록 설계되었다.하지만, 현대의 컴퓨터는 동시에 많은 것을 할 수 있다.따라서 많은 최적화 컴파일러는 순차 프로그램의 일부가 병렬 연산으로 변환되는 자동 벡터화를 수행합니다.

루프 벡터화는 오퍼랜드의 각 쌍에 처리 유닛을 할당함으로써 절차 루프를 변환합니다.프로그램은 대부분의 시간을 그러한 루프 안에서 보낸다.따라서 벡터화는 특히 대규모 데이터 집합에서 이러한 데이터를 상당히 가속화할 수 있습니다.루프 벡터화는 인텔의 MMX, SSE 및 AVX, Power ISA의 AltiVec 및 ARM의 NEON, SVE 및 SVE2 명령 세트에 구현되어 있습니다.

많은 제약이 벡터화를 방지하거나 방해한다.예를 들어 파이프라인 동기화나 데이터 이동 타이밍 때문에 벡터화가 실행 속도를 늦출 수 있습니다.루프 의존성 분석은 루프 내부의 명령의 데이터 의존성에 의존하여 벡터화할 수 있는 루프를 식별합니다.

보증

자동 벡터화는 다른 루프 최적화 또는 컴파일 시간 최적화와 마찬가지로 프로그램 동작을 정확하게 유지해야 합니다.

data 의존관계

잘못된 결과를 방지하려면 실행 중에 모든 종속성을 고려해야 합니다.

일반적으로 루프 불변 의존성과 어휘 순방향 의존성은 쉽게 벡터화할 수 있으며 어휘 역방향 의존성은 어휘 순방향 의존성으로 변환될 수 있다.그러나 이러한 변환은 모든 진술 간의 의존성이 원본에 충실하도록 보장하기 위해 안전하게 수행되어야 한다.

순환 종속성은 벡터화된 명령과 독립적으로 처리되어야 합니다.

data 정밀도

벡터 명령을 실행하는 동안 정수 정밀도(비트 크기)를 유지해야 합니다.내부 정수의 크기와 동작을 기반으로 올바른 벡터 명령을 선택해야 합니다.또한 혼합 정수형일 경우 정확성을 잃지 않고 올바르게 승격/데모할 수 있도록 각별히 주의해야 합니다.부호 확장에 각별히 주의해야 합니다(같은 레지스터 내에 여러 정수가 채워져 있기 때문에). 시프트 작업 중 또는 그렇지 않으면 고려될 반송 비트를 사용한 작업 중.

IEEE-754 준거를 끄지 않는 한 부동 소수점 정밀도도 유지해야 합니다.이 경우 동작은 빨라지지만 결과는 약간 다를 수 있습니다.IEEE-754를 무시해도 큰 변화는 보통 프로그래머 오류를 나타냅니다.

이론.

프로그램을 벡터화하기 위해 컴파일러의 옵티마이저는 먼저 문장 사이의 의존성을 이해하고 필요에 따라 다시 정렬해야 합니다.일단 의존관계가 매핑되면, 옵티마이저는 적절한 후보를 벡터 명령으로 변경하는 구현 명령어를 적절히 배열해야 하며, 이는 여러 데이터 항목에서 동작한다.

종속성 그래프 작성

첫 번째 단계는 의존관계 그래프를 작성하는 것으로, 어떤 스테이트먼트가 다른 스테이트먼트에 의존하는지 특정합니다.여기에는 각 스테이트먼트를 검사하여 스테이트먼트가 액세스하는 모든 데이터 항목을 식별하고 어레이 액세스 수식자를 함수에 매핑하며 모든 스테이트먼트의 다른 모든 액세스에 대한 의존성을 체크하는 작업이 포함됩니다.별칭 분석을 사용하여 서로 다른 변수가 메모리의 동일한 영역에 액세스(또는 교차)한다는 것을 증명할 수 있습니다.

종속성 그래프에는 거리가 벡터 크기보다 크지 않은 모든 로컬 종속성이 포함됩니다.따라서 벡터 레지스터가 128비트이고 어레이 유형이 32비트인 경우 벡터 크기는 128/32 = 4입니다.다른 모든 비순환 종속성은 벡터화를 무효화해서는 안 됩니다.이는 동일한 벡터 명령에서는 동시 액세스가 존재하지 않기 때문입니다.

벡터 크기가 4ints와 같다고 가정합니다.

위해서 (i = 0; i < > 128; i++) {     a[i] = a[i-16]; // 16 > 4, 무시해도 안전     a[i] = a[i-1]; // 1 < 4, 의존관계 그래프 유지 }

클러스터링

그런 다음 그래프를 사용하여 최적화 도구는 강하게 연결된 구성요소(SCC)를 군집화하고 벡터화 가능한 문을 나머지 항목과 분리할 수 있습니다.

예를 들어 루프 내에 (SCC1+SCC2), SCC3 및 SCC4의 3개의 스테이트먼트그룹을 포함하는 프로그램프래그먼트를 그 순서로 생각해 보겠습니다.이 순서로, 2번째 그룹(SCC3)만이 벡터화할 수 있습니다.최종 프로그램에는 각 그룹별로 하나씩 3개의 루프가 포함되며, 중간 루프만 벡터화됩니다.옵티마이저는 스테이트먼트 실행 순서를 위반하지 않으면 첫 번째와 마지막을 결합할 수 없습니다.이 경우 필요한 보증이 무효화됩니다.

관용어 검출

일부 명확하지 않은 종속성은 특정 관용구를 기반으로 더욱 최적화될 수 있습니다.

예를 들어 오른쪽 값(RHS)의 값을 가져와 왼쪽 값에 저장하기 때문에 할당 내에서 데이터가 변경되지 않기 때문에 다음과 같은 자기 데이터 의존성을 벡터화할 수 있습니다. 

a[i] = a[i] + a[i+1];

스칼라에 의한 자기 의존성은 변수 제거를 통해 벡터화할 수 있습니다.

일반적인 프레임워크

루프 벡터화의 일반적인 프레임워크는 다음 4단계로 나뉩니다.

  • 서곡:루프에 의존하지 않는 변수를 루프 내에서 사용할 수 있도록 준비합니다.이것은 보통 벡터 명령에서 사용되는 특정 패턴을 가진 벡터 레지스터로 이동하는 것을 포함합니다.런타임 종속성 검사를 삽입하는 위치이기도 합니다.검사에서 벡터화가 불가능하다고 판단되면 Cleanup으로 분기합니다.
  • 루프:원래 코드의 외관 순서대로 SCC 클러스터로 구분된 모든 벡터화(또는 벡터화되지 않음)
  • 포스트:루프에 의존하지 않는 모든 변수, 인덕션 및 리덕션을 반환합니다.
  • 청소:벡터 사이즈의 배수가 아닌 루프의 끝에 플레인(비벡터화) 루프를 실장하거나 런타임체크에서 벡터 처리가 금지되어 있는 경우에 사용합니다.

런타임과 컴파일 시간

일부 벡터화는 컴파일 시 완전히 확인할 수 없습니다.예를 들어 라이브러리 함수는 처리하는 데이터가 호출자에 의해 공급될 경우 최적화를 방해할 수 있습니다.이러한 경우에도 런타임 최적화는 루프를 즉시 벡터화할 수 있습니다.

이 런타임 체크는 전주 단계에서 이루어지며 가능하면 플로우를 벡터화된 명령으로 유도하고 그렇지 않으면 레지스터 또는 스칼라 변수에 전달되는 변수에 따라 표준 처리로 돌아갑니다.

다음 코드는 외부 파라미터에 의존하지 않기 때문에 컴파일 시에 쉽게 벡터화할 수 있습니다.또한 이 언어는 로컬 변수이며 실행 스택에만 존재하기 때문에 두 변수 모두 메모리에서 다른 변수와 동일한 영역을 차지하지 않음을 보증합니다. 

인트 a[128]; 인트 b[128]; // b 초기화  위해서 (i = 0; i< >128; i++)     a[i] = b[i] + 5;

한편, 아래의 코드에는 메모리 위치에 대한 정보가 없습니다.이는 참조가 포인터이며, 참조가 가리키는 메모리가 중복될 수 있기 때문입니다. 

무효 계산하다(인트 *a, 인트 *b) {     인트 i;     위해서 (i = 0; i < > 128; i++, a++, b++)         *a = *b + 5; }

a와 b 양쪽 주소에 대한 빠른 런타임 체크와 루프 반복 공간(128)은 배열이 겹치는지 여부를 판별하기에 충분하며, 따라서 종속성이 드러납니다.

기존 애플리케이션을 동적으로 분석하여 SIMD 병렬 처리의 내재된 잠재성을 평가하는 툴이 있습니다.이 툴은 컴파일러의 한층 더 진보된 기능이나 수동 코드 [1]변경을 통해서도 이용할 수 있습니다.

기술

예를 들어 숫자 데이터의 두 벡터를 곱하는 프로그램이 있습니다.스칼라 어프로치는 다음과 같습니다.

위해서 (i = 0; i < > 1024; i++)     c[i] = a[i] * b[i];

이는 다음과 같이 벡터화할 수 있습니다.

위해서 (i = 0; i < > 1024; i += 4)     c[i:i+3] = a[i:i+3] * b[i:i+3];

여기서 c[i:i+3]는 c[i]부터 c[i+3]까지의 4개의 어레이 요소를 나타내며, 벡터 프로세서는 1개의 벡터 명령에 대해 4개의 연산을 실행할 수 있다.4개의 벡터 연산은 1개의 스칼라 명령과 거의 동시에 완료되기 때문에 벡터 접근은 원래 코드보다 최대 4배 빠르게 실행될 수 있습니다.

두 가지 컴파일러 접근법이 있습니다.하나는 기존의 벡터화 기법에 기초한 것이고 다른 하나는 루프 언롤링에 기초한 것입니다.

루프 레벨 자동 벡터화

기존 벡터 머신에 사용되는 이 기술은 루프 레벨에서 SIMD 병렬화를 찾아 이용하려고 합니다.이것은 다음과 같은 두 가지 주요 단계로 구성됩니다.

  1. 벡터화할 수 있는 가장 안쪽 루프 찾기
  2. 루프 변환 및 벡터 코드 생성

첫 번째 단계에서 컴파일러는 벡터화를 방지할 수 있는 장애물을 찾습니다.벡터화의 주요 장애물은 벡터 길이보다 짧은 진정한 데이터 의존성이다.기타 장애로는 함수 호출 및 짧은 반복 횟수가 있습니다.

루프가 벡터화 가능하다고 판단되면 루프는 벡터 길이로 스트립마이닝되고 루프 본체 내의 각 스칼라 명령은 대응하는 벡터 명령으로 치환된다.이 스텝의 컴포넌트 변환을 위의 예를 사용하여 다음에 나타냅니다.

  • 스트립마이닝 후
위해서 (i = 0; i < > 1024; i += 4)     위해서 (j = 0; j < > 4; j++)         c[i+j] = a[i+j] * b[i+j];
  • 임시 어레이를 사용한 루프 분배 후
위해서 (i = 0; i < > 1024; i += 4) {     위해서 (j = 0; j < > 4; j++) tA[j] = A[i+j];     위해서 (j = 0; j < > 4; j++) tB[j] = B[i+j];     위해서 (j = 0; j < > 4; j++) tc[j] = tA[j] * tB[j];     위해서 (j = 0; j < > 4; j++) C[i+j] = tc[j]; }
  • 벡터 코드로 교체 후
위해서 (i = 0; i < > 1024; i += 4) {     vA = vec_ld(&A[i]);     vB = vec_ld(&B[i]);     vC = vec_mul(vA, vB);     vec_st(vC, &C[i]); }

기본 블록 레벨 자동 벡터화

이 비교적 새로운 기술은 특히 벡터 [2]길이가 짧은 현대의 SIMD 아키텍처를 대상으로 합니다.루프는 기본 블록에서 SIMD 병렬화의 양을 늘리기 위해 전개할 수 있지만, 이 기술은 루프가 아닌 기본 블록 내에서 SIMD 병렬화를 이용합니다.두 가지 주요 단계는 다음과 같습니다.

  1. 가장 안쪽의 루프는 벡터 길이의 계수에 의해 전개되어 큰 루프 본체를 형성합니다.
  2. 종속성에 의해 차단되지 않는 경우 (같은 연산을 수행하는) 동형 스칼라 명령이 벡터 명령에 팩됩니다.

이 접근방식의 단계별 변환을 표시하기 위해 동일한 예를 다시 사용합니다.

  • 루프 언롤링 후(벡터 길이 기준, 이 경우 4로 가정)
위해서 (i = 0; i < > 1024; i += 4) {     sA0 = ld(&A[i+0]);     sB0 = ld(&B[i+0]);     sC0 = sA0 * sB0;     세인트(sC0, &C[i+0]);           ...     sA3 = ld(&A[i+3]);     sB3 = ld(&B[i+3]);     sC3 = sA3 * sB3;     세인트(sC3, &C[i+3]); }
  • 포장 후
위해서 (i = 0; i < > 1024; i += 4) {     (sA0, sA1, sA2, sA3) = ld(&A[i+0:i+3]);     (sB0, sB1, sB2, sB3) = ld(&B[i+0:i+3]);     (sC0, sC1, sC2, sC3) = (sA0, sA1, sA2, sA3) * (sB0, sB1, sB2, sB3);     세인트((sC0, sC1, sC2, sC3), &C[i+0:i+3]); }
  • 코드 생성 후
위해서 (i = 0; i < > 1024; i += 4) {     vA = vec_ld(&A[i]);     vB = vec_ld(&B[i]);     vC = vec_mul(vA, vB);     vec_st(vC, &C[i]); }

여기서 sA1, sB1, ...는 스칼라 변수를 나타내고 vA, vB 및 vC는 벡터 변수를 나타냅니다.

상업용 컴파일러의 경우, IBM XL [3]컴파일러를 제외하고, 대부분의 경우, 기존의 루프 레벨 방식을 루프 레벨로 사용합니다.

제어 흐름의 존재

루프 본체에 if 문이 존재하려면 변수의 여러 값을 Marge하기 위해 모든 제어 경로에서 명령을 실행해야 합니다.한 가지 일반적인 접근법은 일련의 코드 변환 과정을 거치는 것입니다: 사전식 → 벡터화(위 방법 중 하나를 사용) → 벡터 술어 제거 → 스칼라 술어 제거.[4]이러한 변환을 나타내기 위해 다음 코드를 예로 사용하는 경우

위해서 (i = 0; i < > 1024; i++)     한다면 (A[i] > 0)         C[i] = B[i];     또 다른         D[i] = D[i-1];
  • 프리딕션 후
위해서 (i = 0; i < > 1024; i++) {     P = A[i] > 0;     NP = !P;     C[i] = B[i];     (P)     D[i] = D[i-1];   (NP) }

여기서 (P)는 스테이트먼트를 보호하는 술어를 나타냅니다.

  • 벡터화 후
위해서 (i = 0; i < > 1024; i += 4) {     vP  = A[i:i+3] > (0, 0, 0, 0);     vNP = vec_not(vP);     C[i:i+3] = B[i:i+3];     (vP)     (NP1, NP2, NP3, NP4) = vNP;     D[i+3] = D[i+2];         (NP4)     D[i+2] = D[i+1];         (NP3)     D[i+1] = D[i];           (NP2)     D[i]   = D[i-1];         (NP1) }
  • 벡터 술어를 제거한 후
위해서 (i = 0; i < > 1024; i += 4) {     vP  = A[i:i+3] > (0, 0, 0, 0);     vNP = vec_not(vP);     C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vP);     (NP1, NP2, NP3, NP4) = vNP;     D[i+3] = D[i+2];         (NP4)     D[i+2] = D[i+1];         (NP3)     D[i+1] = D[i];           (NP2)     D[i]   = D[i-1];         (NP1) }
  • 스칼라 술어를 삭제한 후
위해서 (i = 0; i < > 1024; i += 4) {     vP  = A[i:i+3] > (0, 0, 0, 0);     vNP = vec_not(vP);     C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vP);     (NP1, NP2, NP3, NP4) = vNP;     한다면 (NP4) D[i+3] = D[i+2];     한다면 (NP3) D[i+2] = D[i+1];     한다면 (NP2) D[i+1] = D[i];     한다면 (NP1) D[i]   = D[i-1]; }

제어 흐름 존재 시 벡터화 오버헤드 감소

벡터 코드의 모든 제어 경로에서 명령을 실행해야 하는 것은 스칼라 기준선에 관해 벡터 코드를 느리게 하는 주요 요인 중 하나입니다.제어 플로우가 복잡해지고 스칼라 코드로 바이패스되는 명령어가 많아질수록 벡터화 오버헤드는 커집니다.이 벡터화 오버헤드를 줄이기 위해 벡터 브랜치를 삽입하여 스칼라 브랜치가 스칼라 [5]명령을 바이패스하는 방법과 유사한 벡터 명령을 바이패스할 수 있습니다.다음에서는 AltiVec 술어를 사용하여 이를 실현하는 방법을 보여 줍니다.

  • 스칼라 베이스라인(원래 코드)
위해서 (i = 0; i < > 1024; i++) {     한다면 (A[i] > 0)     {         C[i] = B[i];         한다면 (B[i] < > 0)             D[i] = E[i];     } }
  • 제어 흐름 존재 시 벡터화 후
위해서 (i = 0; i < > 1024; i += 4) {     vPA = A[i:i+3] > (0, 0, 0, 0);     C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vPA);     VT = B[i:i+3] < > (0,0,0,0);     vPB = vec_sel((0, 0, 0, 0), VT, vPA);     D[i:i+3] = vec_sel(D[i:i+3], E[i:i+3], vPB); }
  • 벡터 분기 삽입 후
위해서 (i = 0; i < > 1024; i += 4) {     한다면 (vec_any_gt(A[i:i+3], (0, 0, 0, 0)))     {         vPA = A[i:i+3] > (0,0,0,0);         C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vPA);         VT = B[i:i+3] < > (0, 0, 0, 0);         vPB = vec_sel((0, 0, 0, 0), VT, vPA);         한다면 (vec_any_ne(vPB, (0, 0, 0, 0)))             D[i:i+3] = vec_sel(D[i:i+3], E[i:i+3], vPB);     } }

벡터 브런치를 가진 마지막 코드에는 두 가지 주의사항이 있습니다.첫 번째로 vPA의 정의 명령도 vec_any_gt를 사용하여 외부 벡터 브런치 본문 내에 포함되어 있습니다.둘째, vPB의 내부 벡터 브랜치의 수익성은 vPA가 모든 필드에 false 값을 갖는 경우 vPB가 모든 필드에 false 값을 가질 수 있는 조건부 확률에 따라 달라집니다.

스칼라 베이스라인의 외부 브랜치가 루프 본체의 대부분의 명령을 무시하고 항상 사용되는 예를 생각해 보겠습니다.위의 중간 케이스는 벡터브런치를 사용하지 않고 모든 벡터명령어를 실행합니다.벡터 브런치를 가진 마지막 코드는 비교와 브런치를 모두 벡터모드로 실행하므로 스칼라 베이스라인보다 퍼포먼스가 향상될 가능성이 있습니다.

수동 벡터화

대부분의 C와 C++ 컴파일러에서는 프로그래머의 노력과 유지보수를 희생하면서 본질 함수를 사용하여 수동으로 벡터화할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Holewinski, Justin; Ramamurthi, Ragavendar; Ravishankar, Mahesh; Fauzia, Naznin; Pouchet, Louis-Noël; Rountev, Atanas; Sadayappan, P. (6 August 2012). "Dynamic trace-based analysis of vectorization potential of applications". ACM SIGPLAN Notices. 47 (6): 371–382. doi:10.1145/2345156.2254108.
  2. ^ Larsen, S.; Amarasinghe, S. (2000). "Exploiting superword level parallelism with multimedia instruction sets". Proceedings of the ACM SIGPLAN conference on Programming language design and implementation. ACM SIGPLAN Notices. 35 (5): 145–156. doi:10.1145/358438.349320. hdl:1721.1/86445.
  3. ^ "Code Optimization with IBM XL Compilers" (PDF). June 2004. Archived from the original (PDF) on 2010-06-10.
  4. ^ Shin, J.; Hall, M. W.; Chame, J. (2005). "Superword-Level Parallelism in the Presence of Control Flow". Proceedings of the international symposium on Code generation and optimization. pp. 165–175. doi:10.1109/CGO.2005.33. ISBN 0-7695-2298-X.
  5. ^ Shin, J. (2007). "Introducing Control Flow into Vectorized Code". Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques. pp. 280–291. doi:10.1109/PACT.2007.41.