벡터화 중첩 루프 - SIMD

Question

는 사람이 사용하는 SIMD 같은 것을 벡터화을 알고 있습니까 :

for(size_t i = 0; i < refSeq.length()/4; i++){ 

    for(size_t j = 0; j<otherSeq.length(); j++){ 
    if(refSeq[i] == otherSeq[j]){ 
     if(i == 0 || j == 0) 
      L[i][j] = 1; 
     else 
     L[i][j] = L[i-1][j-1] + 1; 
    } 
     else 
     L[i][j] = 0; 
    } 
} 

Answer 1

나 해결책을 제안 해보자. 처음에 L [i] [0]과 L [0] [j]의 값을 계산하십시오. 이제 i = 1과 j = 1에서 iterating을 시작하십시오. 이제 루프의 각 반복에서 i == 0 또는 j == 0에 대한 검사를 제거 할 수 있습니다. 그리고 이것의 또 다른 이점은 행의 각 반복에서 모든 L [i] [j]에 대해 L [i-1] [j-1]의 값을 사용할 수 있다는 것입니다. 이제 벡터 레지스터가 배열의 4 요소를 보유 할 수 있다고 가정 해보십시오. 이제 refSeq, otherSeq, L (이전 행) 및 L (현재 행)의 4 개 요소를로드 할 수 있습니다. 이론적으로 우리는 이제 벡터화를 얻습니다. 자동 벡터 라이저가 이것을 인식하지 못한다고 가정합니다. 그래서 우리는 그것을 수동으로해야합니다. 내가 틀렸다면 나를 바로 잡아주세요.

for(size_t i=0;i<refSeq.length()/4;i++) 
{ 
    if(refSeq[i]==otherSeq[0]) 
     L[i][0]=1; 
    else 
     L[i][0]=0; 
} 
for(size_t j=0; j<otherSeq.length();j++) 
{ 
    if(refSeq[0]==otherSeq[j]) 
     L[0][j]=1; 
    else 
     L[0][j]=0; 
} 

for(size_t i=1;i<refSeq.length()/4;i++) 
{ 
    for(size_t j=1; j<otherSeq.length();j++) 
    { 
     if(refSeq[i]==otherSeq[j]) 
      L[i][j] = L[i-1][j-1] + 1; 
     else 
      L[i][j]=0; 
    } 
} 

단점이 나온 RefSeq [I]를 otherSeq [J]가 아닌지 대각선 요소 만 서열 경우 액세스 원래의 코드와 같은 경우 이제 이전 행을없이 로딩되는 것 같다.

Answer 2

이것은 동적 프로그래밍 문제이며 해협 정방향 구현은 너무 많은 데이터 종속성을 가지므로 SIMD 계산에 적합하지 않습니다.

그러나 알고리즘을 행별로 반복에서 대각선으로 반복하는 것으로 변경하면 전체 대각선을 병렬로 계산할 수 있습니다. 아래 이미지를 참조하십시오.

아래 '의사'코드

은 "내부"계산을 간단히하기 위해 1 개 개의 여분의 행/열을 갖는 매트릭스를 이용한다. 이 여분의 행/열은 모든 대각선 반복 전에 초기화됩니다. 당신이 계산을 위해 실제 SIMD 명령어를 원하거나/병렬 계산을 벡터화하는 방법을 알고있는 경우

int i, j, k; 
for (k = 1; ; k++) { 
    int minI = k > refLen ? k - refLen : 1; 
    int maxI = k > otherLen ? otherLen : k - 1; 

    for (i = maxI; i >= minI;) { 
     j = k - i; 

     // vectorized calculation 256 bit (AVX2) 
     if (i >= 32 && otherLen - j >= 32) { 
      // calculate 32 values of the diagonal with SIMD 
      i -= 32; 
      continue; 
     } 

     // vectorized calculation 128 bit (SSE) 
     if (i >= 16 && otherLen - j >= 16) { 
      // calculate 16 values of the diagonal with SIMD 
      i -= 16; 
      continue; 
     } 

     // scalar calculation 
     if (refSeq[i - 1] == otherSeq[j - 1]) { 
      L[i][j] = L[i - 1][j - 1] + 1; 
     } else { 
      L[i][j] = 0; 
     } 
     i--; 
    } 

    if (k == otherLen + refLen) { 
     break; 
    } 

    // initialize next j-endpoint in diagonal 
    if (k <= refLen) { 
     L[0][k] = 0; 
    } 
    // initialize next i-endpoint in diagonal 
    if (k <= otherLen) { 
     L[k][0] = 0; 
    } 
} 

확실하지.