Ch.10 SML#の拡張機能:マルチスレッドプログラミング

§ 10.2. MassiveThreadsを用いた細粒度スレッドプログラミング

SML# 3.3.0から,デフォルトのマルチスレッドサポートが MassiveThreadsベースのものに切り替わりました. MassiveThreadsは, 東京大学情報理工学系研究科で開発されている C言語向けの軽量細粒度スレッドライブラリです. シームレスなC言語との連携機構と スレッドを止めない並行GCにより, SML#はMassiveThreadsを直接サポートします. MassiveThreadsを利用することで, SML#プログラムから大量の(例えば100万個以上の) ユーザースレッドを マルチコアCPU上で同時に走らせることが可能です.

デフォルトでは,シングルスレッドプログラムの実行効率の 調整のため,SML#からはただ1つのコアのみを使う ように設定されています. マルチコア上でのMassiveThreadsを有効にするためには, MYTH_から始まるMassiveThreads関連の環境変数を少なくとも1 つ設定してください. 例えば,対話モードの起動時に,

$ MYTH_NUM_WORKERS=0 smlsharp

などとして,環境変数MYTH_NUM_WORKERSを定義してください. MYTH_NUM_WORKERSは, ユーザースレッドをスケジュールするワーカースレッドの数, すなわち使用するCPUコアの数を表します. MYTH_NUM_WORKERSが0のとき,Linux環境ならば,全ての CPUコアを使用することを表します.

MassiveThreadsライブラリをほぼそのままバインドした Mythストラクチャが標準で提供されています. Myth.Threadストラクチャには, スレッドの生成と結合のための基本的な関数が含まれています. 代表的な関数は以下の通りです.

  • ユーザースレッドの起動.

    Myth.Thread.create : (unit -> int) -> Myth.thread

    createff()を評価する新しいユーザースレッドを起動します. ユーザースレッドはMassiveThreadsによって適切なCPUコアに スケジュールされます. スケジューリングポリシーはノンプリエンプティブです. つまり,一度あるスレッドがあるCPUコア上で走り始めると, 終了するか,スレッドの実行を制御するMassiveThreadsライブラリ関数を 呼ばない限り, そのスレッドはそのCPUコア上で走り続けます.

  • ユーザースレッドの結合.

    Myth.Thread.join : Myth.thread -> int

    jointは スレッドtの完了を待ち,tの評価結果を返します. create関数で生成したユーザースレッドは,いつか 必ずjoinされなければなりません. このストラクチャはMassiveThreadsライブラリを直接バインドしたも のですので,多くのCライブラリと同様に,生成したスレッドは明示的に 解放されなければなりません.

  • スレッドスケジューリング.

    Myth.Thread.yield : unit -> unit

    yield()は 他のスレッドにCPUコアの制御を譲ります.

MassiveThreadsの使い方を学ぶために,簡単なタスク並列プログラム を書いてみましょう. タスク並列プログラムは,おおよそ以下の手順で書くことが できます.

  1. 分割統治を行う再帰関数を書きます.

  2. 再帰呼び出しのたびに新しいユーザースレッドが作られるように, 再帰呼び出しをcreatejoinで囲みます.

  3. ただし,スレッドの計算コストがスレッドの生成コストを 下回らないように,ある閾値(カットオフ)を下回った場合はスレッド生成を せず,同じスレッドで逐次的に再帰呼び出しをするようにします. 逐次計算に切り替える閾値は,スレッド生成のオーバーヘッドよりも 逐次処理時間が十分長くなるように決めます. 経験的には,1スレッドあたりおおよそ3〜4マイクロ秒程度の評価時間に なるように設定するのが良いようです.

例えば,fib 40を再帰的に計算するプログラムは 逐次的には以下のように書けます.

fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2)
val result = fib 40

fib (n - 1)fib (n - 2)が並列に計算されるように, その片方をcreatejoinで囲むと, タスク並列のプログラムになります.

fun fib 0 = 0
  | fib 1 = 1
  | fib n =
    let
      val t2 = Myth.Thread.create (fn () => fib (n - 2))
    in
      fib (n - 1) + Myth.Thread.join t2
    end
val result = fib 40

ただし,引数のnが十分に小さくなると, fib nの計算コストがスレッドの生成コストを下回ります. そこで,nが10を下回った場合は逐次で計算することに します.

val cutOff = 10
fun fib 0 = 0
  | fib 1 = 1
  | fib n =
    if n < cutOff
    then fib (n - 1) + fib (n - 2)
    else
      let
        val t2 = Myth.Thread.create (fn () => fib (n - 2))
      in
        fib (n - 1) + Myth.Thread.join t2
      end
val result = fib 40

これで並列fibは完成です. このプログラムを実行すると,3,524,577個のスレッドが生成されます.