向量化嵌套循環 - SIMD

有誰知道該向量化像這樣使用SIMD：向量化嵌套循環 - 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; 
    } 
}

來源

2012-05-09 vanste25

當你說「SIMD」時，你需要指定你在說什麼CPU系列，例如， x86（在這種情況下，您需要指定可以假定的SSE/AVX級別），PowerPC（AltiVec），POWER（VMX/VSX），ARM（氖燈），Cell等。 –

此外，什麼是數據類型'refSeq []'，'otherSeq []'和'L [] []'？ –

你確實很持久地使這個最長的子串算法並行:)再次 - 數據依賴。 SIMD在獨立的數據塊上工作。在這裏你有循環內部的if（壞）和if（更壞）。你需要重新設計算法來使用掩碼而不是分支，我不確定它是否會運行得更快。 –

讓我嘗試提出解決方案。最初計算L [i] [0]和L [0] [j]的值。現在開始從i = 1和j = 1迭代。現在，可以刪除循環的每次迭代中檢查i == 0或j == 0。還有一個優點是對於每一行中的每個L [i] [j]，L [i-1] [j-1]的值是可用的。現在，說如果矢量寄存器可以容納4個元素的數組。現在我們可以加載4個元素的refSeq，otherSeq，L（前一行）和L（當前行）。理論上我們現在可以獲得矢量化了。我假設自動矢量化器不會識別這個。所以我們必須手動做到這一點。如果我錯了，請糾正我。

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]或不與其中對角線元素被訪問只有在序列的原代碼是平等的。

來源

2012-07-23 08:36:44 arunmoezhi

這是一個動態規劃問題，海峽前沿實現具有太多數據依賴性，無法用於SIMD計算。

但是，如果將算法從逐行迭代更改爲對角線迭代，則可以並行計算整個對角線。見下圖。

下面的「僞」的代碼使用與1個額外行/列的矩陣中，爲了簡化的「內部」的計算。這個額外的行/列在每次對角線迭代之前被初始化。

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

不確定是否需要實際的SIMD指令進行計算，或者只知道如何並行化/向量化計算。

來源

2016-03-14 20:58:25 gustf

向量化嵌套循環 - SIMD

回答

相關問題