multi-core threading

昔にも書いたマルチコアスレッドコードです。マルチコアによる分散処理を行います。
長らく修正を反映出来ていなかったのでgithubに上げてまとめました。

github

github multi-core and muti-threading

簡単なマルチコアスレッディング管理用クラスです。
マルチコアとマルチスレッドの違いは、処理をコア（論理）に割り当ててるかどうかどうかだけの違いです。
コアに割り当てない設定も可能ですが使う機会は無いでしょう。
性能については、60fpsでの使用に耐えうるモノで、開始と待機の精度はそれほど高くありませんが、待機のCPU使用率が低めの、バランス型です。
もっと精度が欲しい場合はsleep(0)でポーリングすればいいだけなのでこのライブラリは要らないと思います。

このライブラリはWindowsXPで動作するように、XPまでの命令で組まれています。
なので、物理コアと論理コアの判別出来ず、OSに委ねられています。

マルチコア処理

マルチコアによる分散処理を行うには、基本的にスレッドをコアに割り当てるだけ。
windowsの場合は割り当てるAPIは2つあります。

SetThreadAffinityMask

https://msdn.microsoft.com/ja-jp/library/cc429346.aspx

DWORD SetThreadAffinityMask (
  HANDLE hThread,             // 操作対象スレッドのハンドル
  DWORD dwThreadAffinityMask  // スレッドアフィニティマスク
);

SetThreadIdealProcessor

https://msdn.microsoft.com/ja-jp/library/cc429348.aspx

DWORD SetThreadIdealProcessor(
  HANDLE hThread,         // スレッドのハンドル
  DWORD dwIdealProcessor  // 理想的なプロセッサ番号
);

SetThreadIdealProcessorがよく使われます。
スレッドを論理コア番号に紐付けし、使用中であれば他の空きコアを試みるので、4/8コアのような一部を使う場合にとても素直で賢い挙動を行ってくれます。
ほぼこちらの使用で問題ないでしょう。
もしCPUコアの全てを使用したい場合は、SetThreadAffinityMaskが良いでしょう。
これはスレッドに使用しても良いコア番号をビットマスクで指定します。つまり4コアなら、1,2,4,8とすることで全てのコアに振り分けます。
1+2=3で1と2コアの両方の使用を許可出来ます。使い方としては良い案が浮かびませんが、今は1物理コア2論理コアのハイパースレッディングが主なので、物理コア単位にすると安定するかも知れません。

このライブラリではCPUのコアをほぼ全部使う場合以外はSetThreadIdealProcessorを使うようになっています。

初期化

使い方は簡単です。
初期化はグローバル関数を呼ぶだけです。生成されるスレッド管理クラスは、1アプリケーションにつき1つだけのシングルトンです。
アプリケーション終了時やコア数を変えるときは、解放関数を呼んでください。

  // initialize
  _MultiCoreInitialize(4);  // 実際の生成スレッド数はCPUコア数の最大値に丸め込まれます
  corecount := _MultiCoreManager.Count;
...
  // finalize
  _MultiCoreFinalize;

タスクの登録

マルチスレッド処理の場合、処理を関数にまとめて、その関数ポインタとして管理クラスに登録します。
登録なのでまだ実行はされません。

  for i:=0 to TaskCount-1 do
    _MultiCoreManager.Add( MultiCore_HorizonBlur , @TaskRecord[i] );

与える関数で気をつけるところはマルチスレッドプログラミングと同じです。順序を伴う処理は含まないこと、読み込みは良いけど書き込みは他と重複しないこと、あたりは守る必要があります。
また、与える関数ポインタには、自由に使えるポインタ型の引数が備わっており、タスクに渡したい変数内容などはポインタ（アドレス）にして受け渡します。
上記のように構造体を定義して渡すのが一般的です。

type
  TMultiCoreData = record
    // scanline area
    StartIndex,EndIndex : integer;
  end;
  PMultiCoreData = ^TMultiCoreData;

実行と同期

タスクが登録出来たら実行、そして大事なのが同期です。
全ての処理の完了を待つ必要があります。

  _MultiCoreManager.Start; // start execute task
  _MultiCoreManager.Sync;  // sync all task finished

Startの後にすぐSyncを呼ぶ必要はありません。待ち時間にメインスレッドでなにか処理をさせたいなら間に処理を挟むと良いでしょう。

以上がマルチコア処理の1サイクルです。

仮想負荷値を与える

このライブラリにはシンプルな負荷によるタスクの振り分け機能を持っています。

  _MultiCoreManager.Add( hogefunc,@hogerecord , 100 );

例えば、重い処理と軽い処理があった場合、重さが均等になるようコアに割り当てられます。

core0 : [task][task][task]
core1 : [task][task][hevytask]
core2 : [task][hevytask][task]
core3 : [task][task][hevytask]

イメージとしてはこのように構築します。指定無しはweight:1とされます。

だいたいタスクは均等になるように調整して渡すことになるので、この機能は有用そうに見えますが、実際使うことは無いでしょう……。
パフォーマンスを求めるならコア数に対して平等に処理を分割するコードを書くので尚更不要です。

待機と同期精度のお話

昔のバージョンもこれとあまり大きな変化はありませんが、何が変わったかというとタスクが無い状態での待機処理です。
割と面倒なのがこの待機処理だったりします……。

普通の使用なら、CPU使用率は度外視できるので、セマフォで同期を取ってタスク開始フラグをポーリングするだけでOKなので簡単です。
また、1回の処理限定なら、終わったらスレッドをそのままterminate（終わり）させておけば何の問題もありません。
しかし60fps環境で使用する場合は要求がちょっとタイトです。

16ms周期で使用されるためスレッドは使い回すこと。
start/syncの応答精度が早い、個々のスレッドの待機と復帰が早いこと。
待機状態でのCPU使用率が低いこと。（負荷ではなく使用率です）

の3条件です。

上でも出たフラグポーリングですが、よくあるのが以下のようなコードです。

  while true do
  begin
    semaphore.lock;
    f := StartFlag;
    semaphore.unlock;
    if f then break;
    // sleep
    sleep(1);   // sleep(0);
  end;

StartFlagがtrueになったら抜けるだけですがsleepが問題です。
応答を早めたいならsleep(0)を使いたいところですが、実際はCPU使用率が恐ろしく跳ね上がるのでsleep(1)が妥協点です。
sleep(1)の場合1msで同期が終わるかというと、スレッド間の微妙な誤差もあるので倍の2msぐらいに膨れ上がることは考慮しなければなりません。
更にstartとsyncでそれぞれ判定が入ることを考えれば、最大2+2=4ms。
更にwindowsは3msが最小単位だとかなんとかあるので、もしかすると3+3=6msになるかも。
60fpsで動作するなら、約16msのうち4ms(6ms)が消えるのは痛い出費です。

というわけで、実際のコードはちょっと変な感じですが、semaphoreであるクリティカルセクションの二重ロック（デッドロック）による永久待ちを基本にしています。

// main thread
  _MultiCoreManager.Start; ( wait.unlock )
  _MultiCoreManager.Sync; **1

// sub thread
  wait.lock;  // lock 1
  while true do
  begin
    wait.lock;  // lock 2. wait.
    wait.unlock;  // lock 1-1=0
    // flag check
    if (flagcheck) then break;
    ...
    sleep(0);
  end;
  TaskExecute;
  wait.lock;  // lock=1 **1

ただし、この方法は不完全ですり抜けることがあります。
そこですり抜けからデッドロックされるまでのちょっとの間だけ、精度の高いsleep(0)によるフラグポーリングを行います。

あれ？

マウスでぐりぐりする最初の1回目だけ処理時間が40msとかやたらかかることがあります。
この症状、どうやらクリティカルセクションの挙動によるところのようです。
待ち時間が短いとキビキビ動くんですが、待ち時間が長いと判定を甘くして地球に優しいモードになるようです。

InitializeCriticalSectionAndSpinCount - spin count

https://msdn.microsoft.com/ja-jp/library/cc429225.aspx
スピンカウントの値で調整してくださいね！と言うことですが、単位が不明なので正直解らないです:-Q
だいたい500ms過ぎたら寝る感じなので、60fpsなりで動く分にはキビキビ動くので、このあたりは妥協しましょう……。
尚、CPU負荷率が常に高い場合だとこの待機時間が緩和されます。このあたりはハードウェアな領域なのでこれ以上足を突っ込まない方が良さそうです。

ちなみに、普通は2でデッドロック解除待ちになりますが、任意の数値にも出来るそうです。
各スレッドごとにセマフォ持つよりは一本化する方が良い結果が出そうなのでそのうちやってみますが、更新が無かったら……期待値は得られなかったと言うことで。

暈かし処理

いつか触れようと思いますが、サンプルの暈かし処理には "prefix sum" という、値を加算して蓄積していく手法を使用しています。
原理は以下のページが詳しいです。動画に至っては英語では無いですが、図解でなんとなくわかるかと思います。

prefix sum

https://en.wikipedia.org/wiki/Prefix_sum

2d sum quaries

https://www.youtube.com/watch?v=hqOqr6vFPp8
サンプルは横方向しか暈かしていませんので1次元です。ボックスの左端と右端を読み込めば、差分でボックス内の合計値がわかるという優れものです。
暈かしのボックスサイズが変わっても一律の処理負荷で行うアルゴリズムとして有名です。
shaderでやるならnVIDIAのサンプルを見るのが良いでしょう。

nVIDIA

https://docs.nvidia.com/gameworks/index.html#gameworkslibrary/graphicssamples/d3d_samples/d3dcomputefiltersample.htm
下ごしらえに加えて、RGBの深度ビット数が増える、ハードウェアなら浮動小数バッファが必要になるので、ちょっと要求が高いのが難点ですが、暈かしをリアルタイムで出来るようになったのは昨今の進化を感じます。

Ko-Taのバ・ー・ルのようなもの

Spine Animationrig

How to setup physics

Metasequia : ObjectComposition