2014年01月09日

マルチコアプログラミングで遊ぼう!

はてなブックマークに登録

マルチコアプログラミングで遊ぼう!Part 1



Introduction


この50年間はムーアの法則のお陰で しかし、数年前から動作クロック引き上げの限界が現実化し[5,p.14-24]、そしてCPUアーキテクチャ自体も すでにかなり複雑化しており、このレベルでのチューニングもすでにかなり進んだ状態です。

計算力引き上げの面では、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

このフレームワークの仕組みは

  1. スレッド毎に仕事の一覧を持つ
  2. スレッドが現在の仕事を終えると次の仕事を取りに行く
  3. スレッドが次の仕事を取りに行った時に、自分のリストが空であれば、隣のスレッドの仕事を取りに行く
つまり、仕事がなくなるまではスレッドが仕事の一覧を実行し、暇になった時に隣のスレッドの仕事を取ろうとします。 このフレームワークでは仕事は「Task」と言います。 基本的に立ち上げるスレッド数はコア数と同じです。環境によりますが、通常これらはOSのスケジューラによって各スレッドが別々のコアに割り当てられます。 現在の実装はWindows版ですが、他のOS・環境へと簡単に移植できます。

Thread and tasks

開発の動機として、マルチコアを活かせて多くの環境で動作するコードにしたいという考えがありました。また、十分シンプルで簡単に変更が出来て、実験的な機能を実装出来るが欲しかった。 結果として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万回/秒/コアでした。

つまり、
  1. タスクをpopして
  2. そしてexecuteコールして
  3. タスクをpushして
  4. タスク実行回数を+1する
を200サイクル以内で完了できていることになります。(リリース版) 詳細なプロファイルはとっていませんが、ソースコードの流れを見るとおそらく30%がexecute関数内で消費されています。つまり意図した通りスレッド実行が忙しい状態にあり、スレッド同士のロックは発生せず140~150サイクル以内にはタスクの切り替えができています。

Warning:
今回のエンジンのソースはまだVisual C++ 2010 Expressでしかコンパイルしていないので、おそらくGCCでのコンパイルやLinuxでの動作には少し変更が必要です。

例えばゲームエンジンであれば、3Dオブジェクト毎のアニメーション計算、AIのステートマシン管理・Scriptなど、音声・Audio管理、ゲーム内のオブジェクトのアップデート、物理計算、 描画用のculling、ライトの計算、描画自体、パーティクル・システム、その他のタスクがたくさん存在します。さらに、タスク同士の依存性が少なく、並列化に問題なく動く。

このようなシステムで簡単にマルチコアを使いこなす事が可能になります。つまりプログラムをたくさんの細かな作業ブロックに切り分け、依存関係に気をつけながら、仕事のリストに登録すると、依存関係が守られる限りにおいてそれらが実際にどのCPUで実行されるかを意識することなくアプリケーションの正常な動作を実現できます。

今回の記事はこの辺で終わりますが、今後に考えているシリーズの中で
  • このフレームワークのAPIの使い方
  • 実験的に作成するテスト
  • serial的な問題をどこまで並列化出来るのか
  • 実際にマルチコアプログラミングで起きる問題(例:false sharing、memory bandwidth、cache alignment、thread affinityなど)
をテーマにして、記事を書きたいと思います。
@rpiquois
klab_gijutsu2 at 18:09│Comments(0)TrackBack(0)開発 

トラックバックURL

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔   
 
 
 
Blog内検索
Archives
このブログについて
DSASとは、KLab が構築し運用しているコンテンツサービス用のLinuxベースのインフラです。現在5ヶ所のデータセンタにて構築し、運用していますが、我々はDSASをより使いやすく、より安全に、そしてより省力で運用できることを目指して、日々改良に勤しんでいます。
このブログでは、そんな DSAS で使っている技術の紹介や、実験してみた結果の報告、トラブルに巻き込まれた時の経験談など、広く深く、色々な話題を織りまぜて紹介していきたいと思います。
最新コメント
「最新トラックバック」は提供を終了しました。