levenshtein算法並行

我已經使用parallel_for實現了算法。但主要是我使用同步部分，所以我沒有利潤。也許有更好的選擇？levenshtein算法並行

tbb::parallel_for (tbb::blocked_range<int>(1, m * n), apply_transform(d, j, this, m, n)); 

    void apply_transformation(int * d, int i, int j, int n){ 
     int elem1 = (*v1)[i]; 
     int elem2 = (*v2)[j]; 
     if(elem1 == elem2){ 
      dLock.acquire(dMutex); 
      d[i*n + j] = d[(i-1)*n + j-1];  // no operation required 
      dLock.release(); 
     } else { 
      dLock.acquire(dMutex); 
      d[i*n + j] = std::min(std::min(d[(i-1)*n + j] + 1, //deletion 
        d[i*n + j-1] + 1), //insertion 
        d[(i-1)*n + j-1] + 1); //substitution 
      dLock.release(); 
     } 
    } 

    class apply_transform{ 
     int * array; 
     int m_j; 
     Levenstein * m_l; 

     int m, n; 
     public: 
      apply_transform (int* a, int j, Levenstein * l, int width, int height): 
       array(a), m_j(j), m_l(l), m(width), n(height) {} 

      void operator()(const tbb::blocked_range<int>& r) const { 
       for (int i=r.begin(); i!=r.end(); i++){ 
        m_l->apply_transformation(array, i, m_j, n); 
       } 
      } 
    };

來源

2012-12-12 Alex A. Renoire

'更好的選擇？'你可以改變你的算法爲'FASTA'＆'BLASTA' –

或者如果你有GUP啓用系統[this]（http://www.iaeng.org/publication/WCE2010/WCE2010_pp499- 504.pdf）將幫助你。 –

@Rick：其實，enumerable_thread_specific :) –

的編輯距離計算本質上是一個波前圖案，其中的d(i,j)計算需要的d(i-1,j-1)，d(i-1,j)，和d(i,j-1)知識。這些依賴關係自然會形成一個DAG任務;一個計算d(i,j)的任務只能在其所有前輩（以及前輩等）完成時才能執行。可以並行處理所有依賴關係已解決且不相互依賴的任務（例如，d(1,2)和d(2,1)）。除了遵循依賴關係之外，不需要其他同步。

在TBB中有幾種表達波前圖形的方法：使用低級別任務（複雜且不推薦），使用parallel_do加上原子計數器（如TBB Design Patterns documentation中所述;此處使用的示例非常接近您做）和流程圖（如the TBB blog中所述）。我建議你研究這些文檔並進行自己的實驗。

另請注意，計算單個d(i,j)的工作量太小，無法證明並行執行的開銷。爲了實現一些加速，將一個矩形塊的計算集合到一個單獨的任務中，在任務內串行處理塊元素。這些塊將具有相同的依賴模式。但是可以實現更少的並行性的更大塊，因此您可能需要嘗試塊大小以獲得最佳性能。

來源

2012-12-19 21:22:28

levenshtein算法並行

回答

相關問題