实现线程构建史密斯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或更高版本的任务并行库。