邁爾斯差異是否適合在GPU上運行？

我有興趣通過在GPU上運行更快的Myers diff實現，即使用OpenCL。我對算法有了很好的理解，但對GPU編程來說是新的。我的直覺是GPU的表現不佳，但我想聽聽想法和想法。邁爾斯差異是否適合在GPU上運行？

下面是對C中算法迭代的描述。我們有兩個字節'left'和'right'的常量緩衝區（我們正在比較的數據）以及一個共享的可變數組int32，稱爲向量。 'idx'是迭代指數。那麼算法本質上是這樣的：

void myers_diff_iteration(const uint8 *left, const uint8 *right, int32 *vector, int32 idx) { 
     int32 x = MAX(vector[idx-1], vector[idx+1]); 
     int32 y = idx - x; 
     while (left[x] == right[y]) { 
      x++; 
      y++; 
     } 
     vector[x] = x; 
    }

我的猜測是，while循環（其中有重複的一個非常難以預測的數字，從零到一百萬不等）可能是非常糟糕的GPU，並消除任何性能增益。真的嗎？有關如何改進它的任何提示？

另外，矢量在循環的所有迭代之間共享。每次迭代寫入不同的位置，因此不需要同步（除了要求寫入對齊的4字節字不會影響鄰近字）。這樣的共享矢量會表現出色嗎？

感謝您的幫助！

來源

2011-06-04 fish

你可以試試。 GPU會在while循環中遇到嚴重問題，但只要有足夠的「迭代」（線程）運行，就不應該有任何速度丟失。

void myers_diff_iteration(const uint8 *left, const uint8 *right, int32 *vector, int32 idx) { 
     int id = get_global_id(0); 
     int32 x = MAX(vector[idx-1], vector[idx+1]) + id; 
     int32 y = idx - x + id; 
     if (left[x] != right[y]) { 
      vector[x] = x; 
     } 
    }

只有這樣，你需要運行，而線的環NUMER最大：

你可以這樣重寫。但它只會產生每個OpenCL運行的矢量的1個結果。

最好的嘗試，然後做一些變化。

來源

2011-06-06 11:20:06 DarkZeros

邁爾斯差異是否適合在GPU上運行？

回答

相關問題