スレッドマージソートはシリアル実装よりも遅い

Question

学校では、マルチスレッドアプリケーションを作成する作業があります。私たちは、マージソートのマルチスレッド実装を行うことを選択しました。

ただし、シリアル実装よりも高速に動作させることはできません。限られたスレッド（コード例2）（4つのスレッドの最大と無制限のスレッド（コード例1）と

• 実装が（非常に遅かった）
• 実装 - まだ本当に：
  は、私はすでに次のことを試してみましたParallel.Invoke（コード例3）（依然として遅い）、並列マージ機能付き
• 複雑な実装を使用して）
• 実装を遅らせる（ちょうど恥遅い）

Visual Studio（Instrumentation部）で解析ツールを使用すると、呼び出される関数のタイミングがわかりました。スレッド化されたソリューションは、シリアル実装よりも非常に遅いです。

これは考えられません。

（たとえば：ソートする5000000の番号と、シリアル実装：16.717,17;平行：20.259,97、ちょうど1余分な糸を用いた結果）：

私が所有して両方のマシン上でそれをテスト

• インテルCore 2クワッドQ9450する@ 2.66GHzの
• インテルCore i7のQ720する@ 1.60Ghz

私はこれが可能であるどのように私の人生のフィギュアアウトのために、これはただのuを高速べきではないことはできませんプロセス？

誰かが私を助けることができるなら、私は本当にgreatefullでしょう。

コード例1：

ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3); 
Thread thread = new Thread(new ThreadStart(pMerge.parallel_merge)); 
thread.Start(); 

ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1); 
pMerge2.parallel_merge(); 
thread.Join(); 

コード例2：

if(depthRemaining > 0) 
{ 
    ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3); 
    thread thread = new Thread(new ThreadStart(pMerge.parallel_merge)); 
    thread.Start(); 
    ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1); 
    pMerge2.parallel_merge(); 
    thread.Join(); 
} 
else 
{ 
    ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3); 
    pMerge.parallel_merge(); 
    ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1); 
    pMerge.parallel_merge(); 
} 

コード例3：

if (depthRemaining > 0) 
{ 
    Parallel.Invoke(
    () => threaded_merge_sort(getallen, p, q, depthRemaining-1)); 

    threaded_merge_sort(getallen, q + 1, r, 0); 
} 
else 
{ 
    threaded_merge_sort(getallen, p, q, 0); 
    threaded_merge_sort(getallen, q+1, r, 0); 
} 

Answer 1

問題はコードではなく、VSからの解析ツールであるようです。

-Arne Claerebout

Answer 2

あなたが報告されている時間の何単位？

新しいスレッドの開始は「スロー」操作です。マルチスレッドを使用した非常に短いリストの並べ替え/マージは少し遅くなる可能性があります。

番号リストの長さを半分に分割しただけでは、プログラムが高速に実行されますか？そうでない場合は、コードは単純に縮尺されません。

実際のコードを実装しないでこの質問に答えるのは少し難しいです。