Реализация потоков для построения матрицы Смит-Ватерманн быстрее

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 сделано STH, как это:

Основная функция:

 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 от Microsoft содержит проект ParallelExtensionsExtras, который включает в себя эффективную реализацию алгоритма волнового фронта. Это использует параллельную библиотеку задач от .NET 4.0 или выше.