Vectorisation Nested Loop - SIMD

Question

Quelqu'un sait-il à vectoriser quelque chose comme ceci en utilisant 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

permettez-moi de proposer une solution. Initialement, calculer les valeurs de L [i] [0] et L [0] [j]. Commencez maintenant l'itération de i = 1 et j = 1. Maintenant, la vérification de i == 0 ou j == 0 dans chaque itération de la boucle peut être supprimée. Et un avantage de plus est que pour chaque L [i] [j] dans chaque itération sur une ligne, la valeur de L [i-1] [j-1] est disponible. Maintenant, disons si les registres vectoriels peuvent contenir 4 éléments du tableau. Maintenant, nous pouvons charger 4 éléments de refSeq, otherSeq, L (ligne précédente) et L (ligne courante). Théoriquement, nous obtenons la vectorisation maintenant. Je suppose que le vectorizer automatique ne le reconnaîtra pas. Nous devons donc le faire manuellement. Corrigez-moi si j'ai tort, s'il-vous plait.

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; 
    } 
} 

Un inconvénient serait que maintenant nous chargions la ligne précédente, peu importe si RefSeq [i] est égal à otherSeq [j] ou pas avec le code d'origine où l'élément diagonale est accessible uniquement si les séquences sont égaux.

Answer 2

Il s'agit d'un problème de programmation dynamique et une mise en œuvre d'un canal de détresse a trop de dépendance aux données pour convenir aux calculs SIMD. Cependant, si vous modifiez l'algorithme de l'itération en ligne à l'itération en diagonale, la diagonale entière peut être calculée en parallèle. Voir l'image ci-dessous.

Le code « pseudo » ci-dessous utilise une matrice avec une ligne/colonne supplémentaire afin de simplifier le calcul « intérieur ». Cette ligne/colonne supplémentaire est initialisée avant chaque diagonale-itération.

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; 
    } 
} 

Je ne sais pas si vous vouliez les instructions SIMD réelles pour le calcul, ou tout simplement savoir comment paralléliser/vectoriser le calcul.