スレッドと再帰を一緒に使用する必要がありますか？

Question

私はしばらくの間BSPツリーをいじくり回しており、スレッドで遊んでいます。 BSPツリーに三角形を追加すると、データを並列処理するために新しいスレッドを作成する機会が生じます。

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    insert(frontpiece, bspnode.front)
    insert(backpiece, bspnode.back)
  }
  ....
}

上記の2つの挿入操作は2つのスレッドで実行でき、同じデータを変更しないため、安価な同期を使用できます。

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    handle = beginthread(insert(backpiece, bspnode.front))
    insert(frontpiece, bspnode.back)
    if(handle)
    {
      waitforthread(handle)
    }
    else
    {
      insert(backpiece, bspnode.front)
    }
  }
  ....
}

この新しいメソッドは、スレッドを作成して操作を並列に完了しようとしますが、スレッドを作成できない場合は失敗しません（元のアルゴリズムに単純に戻ります）。

これは適切なプログラミング手法ですか、それともスレッドを不適切に使用していますか？私はこの技術に関する文献を見つけることができませんでした。私はCPUを最大限（2コア）まで使用する傾向があり、理論的には利用可能な任意の数のプロセッサーに拡張できることが気に入っています。 CPUとメモリがひどく無駄になるのは嫌です。

Answer 1

スレッドは、処理の一部が外部（ユーザー入力、I / O、その他の処理）で待機している場合に優れています-待機中のスレッドは待機を継続でき、待機中のスレッドは先に偽造できます。

ただし、処理集中型のタスクの場合、プロセッサよりも多くのスレッドが実際にオーバーヘッドを作成します。スレッドがすべての「CPU作業」を実行しているようですので、コアごとに1つのスレッドに固執します。ただし、最適な数を見つけるためにテストしてください。

作成される最大のオーバーヘッドは、コンテキストの切り替え（1つのスレッドの凍結と次のスレッドの実行コンテキストのロード）、およびスレッドが異なるメモリでタスクを実行しているときのキャッシュミス（スレッドがCPUキャッシュを効率的に使用できる場合） 。

Answer 2

最善の方法は、スレッドプールを作成し、それを「透過的に」使用してノードを追加することです。

たとえば、プログラムの起動時に2つのスレッドを作成し、セマフォまたはイベントで待機させます。追加するノードがある場合、データをキューにポップし、セマフォをトリガーします。これは、キューからデータをポップして処理を実行するスレッドの1つを呼び起こします。 （キューへのアクセスがスレッドセーフであることを確認してください-クリティカルセクションと完全に同期することが最適です。）

データをキューにコピーして追加のスレッドを実行するオーバーヘッドが増えるため、アプリの全体的なパフォーマンスは低下しますが、以前はシングルコアで実行していた場合は2で実行します。スレッド処理が高価な場合。

Answer 3

たとえば、Quicksortは非常に簡単にマルチスレッドでプログラムでき、マルチコアシステムではパフォーマンスが大幅に向上し、非マルチスレッドではパフォーマンスがわずかに低下します。オーバーヘッドを2回追加していることを覚えておいてください-再帰のためにスタックを保存するために1回、スレッドに対して1回保存します。