0

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 個の追加スレッドを利用することです。

ここに画像の説明を入力

ヒントや同様の取り決めは非常に役立ちます。

私はこのようにしました：

主な機能：

        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));
    }

クエリの実行時間がほぼ 2 倍に延長されます。しかし、スレッドが機能するという情報もあります。このコードを最適化する方法は? なにか提案を？4 プロセッサを搭載したマシンでテストします。

4

1 に答える 1

1

書かれたコードは正しくありません。例: 複数のスレッドがfinished_lines同時にインクリメントし、間違った結果を生成する競合状態があります。静的変数を使用してスレッド間で通信するというあなたの考えには、偽共有と呼ばれる問題があり、パフォーマンスが低下します。[編集: コードを詳しく見てみると、共有変数をまったく使用していないことがわかります。あなたのコードは決して機能しません。]

単線ではなく、ブロックやタイルで作業したほうがよいと思います。タイルが次のように配置されている場合:

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

前のすべてのタイルが計算されると、同じラベル (同じ逆対角線上) を持つすべてのタイルを並列に計算でき、スレッド間の同期についてまったく心配する必要はありません。

これは、実際には必要以上に制限的です。必要なのは波面アルゴリズムです。たまたま、Microsoftの .NET Framework を使用した並列プログラミングのサンプルにParallelExtensionsExtras、ウェーブフロント アルゴリズムの効率的な実装を含むプロジェクトが含まれています。これは、.NET 4.0 以降の Task Parallel Library を使用します。

于 2013-11-09T21:18:03.967 に答える