實現線程構建史密斯Watermann矩陣更快

Question

我有一個線程在C＃以下循環的實現問題：

 for (int i = 1; i < matrix.scoreMatrix.GetLength(0); i++) 
     { 

      for (int j = 1; j < matrix.scoreMatrix.GetLength(1); j++) 
      { 
       matrix.CalculateScore(i, j); 
      } 
     } 

這個循環填充匹配的數組Smith Waterman算法。這需要很長時間，因爲我想改進填充矩陣的過程。

填充矩陣必須從左上角開始執行，因爲以下單元格是根據位於上方和左側的單元格計算的。

我的想法是藉此2-3其他線程，將填補每一行數組作爲顯示在下面的圖像的優點：

任何提示或類似的佈置將是非常有益的。

I`v做過某事像這樣：

主要功能：

 int i = 0, t1_row=0, t2_row=0, t3_row=0, finished_lines=0; 

     Thread t1 = new Thread(() => getnext1(matrix, i, t1_row, t2_row, t3_row, finished_lines)); 
     Thread t2 = new Thread(() => getnext2(matrix, i, t1_row, t2_row, t3_row, finished_lines)); 
     Thread t3 = new Thread(() => getnext3(matrix, i, t1_row, t2_row, t3_row, finished_lines)); 

     t1.Start(); 
     t2.Start(); 
     t3.Start(); 
     t1.Join(); 
     t2.Join(); 
     t3.Join(); 

線程函數：

public static void getnext1(SWMatrix matrix, int i, int t1_row, int t2_row, int t3_row, int finished_lines) 
    { 
     do 
     { 
      for (int j = 1; j < matrix.scoreMatrix.GetLength(1); j++) 
      { 
       if (t1_row <= t3_row - 1 || finished_lines >= i - 2) 
       { 
        matrix.CalculateScore(i, j); 
        t1_row++; 
       } 
       else 
       { 
        j--; 
       } 
      } 
      finished_lines++; 
      i++; 
      t1_row = 0; 
     } 
     while (i >= matrix.scoreMatrix.GetLength(0)); 
    } 

    public static void getnext2(SWMatrix matrix, int i, int t1_row, int t2_row, int t3_row, int finished_lines) 
    { 
     do 
     { 
      for (int j = 1; j < matrix.scoreMatrix.GetLength(1); j++) 
      { 
       if (t2_row <= t1_row - 1 || finished_lines >= i - 2) 
       { 
        matrix.CalculateScore(i, j); 
        t2_row++; 
       } 
       else 
       { 
        j--; 
       } 
      } 
      finished_lines++; 
      i++; 
      t2_row = 0; 
     } 
     while (i >= matrix.scoreMatrix.GetLength(0)); 
    } 

    public static void getnext3(SWMatrix matrix, int i, int t1_row, int t2_row, int t3_row, int finished_lines) 
    { 
     do 
     { 
      for (int j = 1; j < matrix.scoreMatrix.GetLength(1); j++) 
      { 
       if (t3_row <= t2_row - 1 || finished_lines >= i - 2) 
       { 
        matrix.CalculateScore(i, j); 
        t3_row++; 
       } 
       else 
       { 
        j--; 
       } 
      } 
      finished_lines++; 
      i++; 
      t3_row = 0; 
     } 
     while (i >= matrix.scoreMatrix.GetLength(0)); 
    } 

查詢執行時間延長至將近兩倍。但我也有線程工作的信息。如何優化此代碼？任何建議？我使用4個處理器在一臺機器上測試它。

Answer 1

你寫的代碼不正確。例如：有一個競爭條件，多個線程可以同時增加finished_lines併產生錯誤的結果。您使用靜態變量進行線程間通信的想法存在一個稱爲false sharing的問題，並會降低性能。 [編輯：仔細查看你的代碼，我發現你根本沒有使用共享變量。你的代碼無法工作。]

我認爲你最好使用塊或瓦而不是單行。如果您的瓷磚安排是這樣的：

A B C D ... 
B C D E ... 
C D E F ... 
D E F G ... 
. . . . ... 

然後用相同的標籤（在相同的反對角線）的所有瓦片可以並行計算一次以前所有的瓦塊已被計算，並且你不需要擔心線程之間的同步。

這實際上比它需要的限制多一點。你需要的是波前算法。恰巧，微軟的Samples for Parallel Programming with the .NET Framework包含一個ParallelExtensionsExtras項目，其中包括波前算法的高效實現。這使用.NET 4.0或更高版本的任務並行庫。