2014年01月09日
マルチコアプログラミングで遊ぼう！
マルチコアプログラミングで遊ぼう！Part 1
Introduction
この50年間はムーアの法則のお陰で
- 回路の速度が上がりました。(MHz -> GHz)
- 利用可能なトランジスター数が増えた事によって、バスの幅、CPUのレジスタ数も増えた 8 -> 16 -> 32 -> 64bit（bitレベルの並列化とも表現できる）
- 利用可能なトランジスタ数が増えた事によって、新しいアーキテクチャが可能になりました。
- パイプライン化 [1]
- アウト・オブ・オーダー実行[2]
- 分岐予測 [3]
- などなど
- スーパースカラー化（命令レベルの並列化）[4]
- SIMDによる並列計算化（データレベルの並列化）
実行速度自体のチューニング
並列化
計算力引き上げの面では、SIMD命令がかなり増え、内部のデータの幅も増え、数倍の速度向上につながってきました（最新のCPUでは512bit幅になろうとしている[6])。
とはいえ、SIMDやベクタ計算で数倍の速度向上につながる計算パターンは限られています。
自然に効率よく複数のプログラムを動かすには同時実行できるコア数を増やすほかにありません。 ムーアの法則がもうしばらく有効で、トランジスタの集積度を高めることができるのであれば、それらをさらなるSIMD化のために割くよりは搭載コア数を増やすことに使ったほうが現実的です。
How : More power for one application
マルチコアは、互いに独立した複数のアプリケーションを同時実行する(例えばOS上で別々のプロセス・スレッドとして実行する)上ではシンプルに速度向上へ寄与しますが、単一アプリケーションで簡単に力を引き出せるかというと、そこには解決すべき課題があります。
同じアプリケーション内で多数のスレッドを利用すると、それぞれの起動、停止、スレッド間の同期、データアクセスの一貫性といった問題に直面します。 さらに、デッドロックを引き起こすケースを慎重に避ける必要があり、これらの問題は実行するスレッド数が増えれば増えるほど複雑さを増します。
これをうまく管理するのは現実的とは言えません。
出来る限り、プログラムの開発時に並列実行される事を出来るだけ意識しないで済むモデルのほうが分かりやすいと言えます。
OSが無ければ、HWだけですと（例えばゲーム機）、1コア = 1 スレッドになります。(HyperThreadingの話もあるので、Physicalコアとロジカルコアを無視します） アプリケーション内の部分部分を別のコアに割り当てられれば、リソースを最適に利用する事が出来ます。
OSの場合、スレッドの実行の仕方はOSのスケジューラーによって決められますが、今回のやり方ではアプリケーション内部で、なんらかのメカニズムを使って、アプリケーションが自分のロジックでスケジューリングをおこなう必要があります。 また、OSと違って処理をタイマーによって切り替える方法をとらず、自分の作業を出来るだけ十分短くして、終わったら次の作業を実行するというやり方にします。
このため、作業の切り替えコストが重要になります。
つまり、アプリケーションの中で「今度する仕事」の一覧を持ち、スケジューラーのポリシーに従ってそのリストから次に実行する「仕事」 を決める。
Framework :
今回紹介するフレームワークは個人的に作ったマルチコアのスケジューラーです。
こちらです：https://github.com/KLab/EnCore
開発にあたって、次の資料が参考になりました。
[1]http://molecularmusings.wordpress.com/2012/04/05/building-a-load-balanced-task-scheduler-part-1-basics/
[2]http://software.intel.com/en-us/articles/do-it-yourself-game-task-scheduling/
[3]http://www.1024cores.net/home/scalable-architecture/task-scheduling-strategies
このフレームワークの仕組みは
- スレッド毎に仕事の一覧を持つ
- スレッドが現在の仕事を終えると次の仕事を取りに行く
- スレッドが次の仕事を取りに行った時に、自分のリストが空であれば、隣のスレッドの仕事を取りに行く
開発の動機として、マルチコアを活かせて多くの環境で動作するコードにしたいという考えがありました。また、十分シンプルで簡単に変更が出来て、実験的な機能を実装出来るが欲しかった。 結果として1500行ぐらいで十分遊べるシステムになってます。
フレームワークにはすでに様々な機能を実装していますが、今回は概念の説明に留めて詳細の説明を省略し、基本機能のみを使用します。
First Test : Push/Pop Performance
まず、フレームワークを利用してみましょう。
#include "LX_MultiTasking.h" #include <stdio.h>そして、フレームワークに今回実行する「仕事」を定義します。 Taskクラスを継承して自分のtaskを定義します。
class TestTask : public Task {
public:
TestTask();
void Execute(u8 worker);
u32 m_time;
};
そして実装します。
TestTask::TestTask() {
m_time = 0; // 実行回数を初期化
TSK_SetRunFunction((execFunc)&TestTask::Execute); // 実行する関数を設定
}
void TestTask::Execute(u8 worker) {
WRK_PushExecute(worker,this); // 現在のThreadに次の仕事を設定する
m_time++; //実行回数を増やす
}
そして、システムを起動し、タスクを登録して、実行します。
int main(int argc, char* argv[])
{
// Setup library
if (WRKLIB_Init()) {
// Feed 2 cores : Create 2 tasks and queue them on workers.
TestTask* pTaskT1 = new TestTask();
TestTask* pTaskT2 = new TestTask();
WRK_PushExecute(0, pTaskT1);
WRK_PushExecute(1, pTaskT2);
// Start Cores : 2 threads.
WRK_CreateWorkers(2, false, 16384, NULL);
// Check Performances
u32 sec = 0;
Sleep(1000);
while (1) {
printf("Execution Count, Core1:%i Core2:%i %i\n", pTaskT1->m_time, pTaskT2->m_time, ++sec);
pTaskT1->m_time = 0;
pTaskT2->m_time = 0;
Sleep(1000);
}
delete pTaskT1; delete pTaskT2;
// Never reach here in our test but let's be clean anyway.
WRKLIB_Release();
}
}
実行結果は、モバイルAMD K-140@1420MHzにおいて平均720万回/秒/コアでした。
つまり、
- タスクをpopして
- そしてexecuteコールして
- タスクをpushして
- タスク実行回数を+1する
Warning:
今回のエンジンのソースはまだVisual C++ 2010 Expressでしかコンパイルしていないので、おそらくGCCでのコンパイルやLinuxでの動作には少し変更が必要です。
例えばゲームエンジンであれば、3Dオブジェクト毎のアニメーション計算、AIのステートマシン管理・Scriptなど、音声・Audio管理、ゲーム内のオブジェクトのアップデート、物理計算、 描画用のculling、ライトの計算、描画自体、パーティクル・システム、その他のタスクがたくさん存在します。さらに、タスク同士の依存性が少なく、並列化に問題なく動く。
このようなシステムで簡単にマルチコアを使いこなす事が可能になります。つまりプログラムをたくさんの細かな作業ブロックに切り分け、依存関係に気をつけながら、仕事のリストに登録すると、依存関係が守られる限りにおいてそれらが実際にどのCPUで実行されるかを意識することなくアプリケーションの正常な動作を実現できます。
今回の記事はこの辺で終わりますが、今後に考えているシリーズの中で
- このフレームワークのAPIの使い方
- 実験的に作成するテスト
- serial的な問題をどこまで並列化出来るのか
- 実際にマルチコアプログラミングで起きる問題（例：false sharing、memory bandwidth、cache alignment、thread affinityなど）
@rpiquois
