Ruby用仮想マシンYARVにおける並列実行スレッドの実装
笹田耕一（発表者）（東京大学大学院情報理工学系研究科）
まつもとゆきひろ（NaCl）
前田敦司（筑波大）
並木美太郎（農工大）
情報処理学会プログラミング研究会 2006 10/13
1Agenda 背景と問題点
 並列実行スレッドの検討• マッピングモデル• 並列実行のための排他制御

 YARVにおける並列実行スレッドの設計• Rubyスレッドのネイティブスレッド対応• Rubyスレッドの並列実行

 実装した並列実行スレッドの評価
 まとめ2

背景 スクリプト言語Ruby• 使いやすい / 気軽に使えるオブジェクト指向言語として世界中で広く利用
Thread.new{• スレッドにも当然対応# … Thread 2• Rubyレベルで気軽に生成できるスレッド（Rubyスレッド/RT）を並行実行

 並列実行計算機のコモディティ化}# … Thread 1• 「普通のパソコン」にデュアルコアCPU• 数年後にはマルチコア（>2）が「普通」に• 並列計算機を活用できるS/W環境が必要
3

問題点
 Rubyスレッドの並列実行は不可能• ユーザレベルスレッド• 現状はあくまで「並行」実行支援（v.s. Java）

 ユーザレベルスレッドの非効率な実装• 移植性を向上するためスレッド切り替えは「setjmp/longjmp」＋「マシンスタックコピー」
ブロッキングするOSコールの利用不可• 例えば I/O に関してはselectでポーリング
4解決の方針 ネイティブスレッド処理機構の利用• 本機構で管理するスレッド：ネイティブスレッド/NT• （大体）移植性の確保• UNIX系：POSIX Thread（Pthread）• Windows系：MS-Windows Win32API• システム依存の効率的なスレッド管理• 並列計算機上で並列実行可能• ブロッキングするようなOSコールも利用可能
5

検討：
ネイティブスレッド利用
 Rubyスレッドとネイティブスレッドのマッピングモデル（1:1, M:N）の検討• 1:1→スレッド管理を全てNTで• M:N →切り替えなどをユーザレベルで• （1:N → ユーザレベルスレッド）• シンプルにするために 1:1 モデルで• ネイティブスレッド処理機構にスレッド制御の性能を担保（現在も研究されている分野なので、まだまだ性能向上は見込める）
6

システムの全体像
Rubyスレッドとネイティブスレッド
Ruby (YARV)Native Thread
System S/WNT

RTNT・・・・・・

RTNT

UL
KL（OS)

Thread Scheduler

S/W
H/W

RT

Processor(s)PEPE・・・

PE

7 Level
PE: Processor Element, UL: User Level, KL: Kernel

検討：
並列実行における排他制御 並列実行と排他制御• 排他制御は必要• 排他制御はオーバヘッド いくつか考えられる方針

str = "foo"Thread.new{
N.times{str << "bar"}}N.times{str << "baz"}• (a) 細粒度ロック（FGL）のみ• (b) 細粒度ロック＋ジャイアントロック（GL）• (c) ジャイアントロックを持つRTのみ実行• (d) 排他制御しない（Rubyプログラマ任せ）
8

現在のスレッド 並列実行が不可能
 スレッド切り替えのタイミングをコントロールできるため、排他制御が不要• そのような前提で書かれた膨大なCで記述されたメソッド（Cメソッド）が存在

CPU 1

RT 1

RT 2

RT 1
NT1

CPU 2

IDLE

9

検討：並列実行における排他制御(a) 細粒度ロックのみ
 ○ 十分な並列性を発揮
 × 全ての既存のコードに対し、FGL等によるスレッドセーフ（TS）コードへ変更が必須→「豊富なRubyライブラリ」が利用不可に
CPU 1
CPU 2

RT 1
RT 2

FGL

NT1
FGL
NT2

FGL: Fine-Grained Lock10

検討：並列実行における排他制御(b) 細粒度ロック＋ジャイアントロック
 TSでない既存のコードはGLで保護
 ○ 既存のコードが利用可能（並列実行不可）
 ○ とりあえず今までどおりCメソッド記述可能
 ○ 必要に応じてFGLによるTSコードへ移行可

CPU 1
CPU 2

RT 1

GLRT 2NT1
GL
NT2

GL: Giant Lock11

検討：並列実行における排他制御(c) ジャイアントロックを持つRTのみ実行 GLを実行権として扱い、持つRTのみ実行
 ○ 排他制御不要
 × 並列実行不可能

CPU 1
CPU 2

RT 1
GL as Right

RT 2

NT1
GL as Right
NT212

検討：並列実行における排他制御(d) 排他制御しない（Rubyプログラマ任せ）
 ○ 排他制御不要
 × 処理系エラー（SEGV等） 頻発 低級言語的アプローチ
CPU 1

RT 1
NT1

CPU 2

RT 2
NT213

検討：
排他制御の各方式のまとめスケーラビリティ（台数効果）

逐次処理 既存コードの性能の再利用

Rubyらしさ(?)
やさしさ(a)◎○×○(b)

○○○

○(c)

×◎

○○(d)

◎◎

○

性能追求
だけならSingle
Core用Hacker用？

×14

設計：ネイティブスレッドを用いた並列実行可能なRubyスレッド処理機構
 ネイティブスレッドを 1:1 で利用• Pthread or Win32APIを利用

 現状の Ruby API をほぼ実現• Rubyスレッドの割り込みも可能 システム側でスレッドセーフに• スレッドセーフに書き換え可能• TSではないCメソッドも実行可能
15

設計：Rubyスレッドのネイティブスレッド対応
生成管理 Rubyスレッドの生成・終了・排他制御→ネ

イティブスレッドのAPI利用• 実行終了後、スレッドオブジェクトはGCまで生存

 Rubyスレッドの合流→独自実装
 RTのスケジューラ→ NTのスケジューラ• RubyAPIの優先度とネイティブスレッドの優先度をマッピング

16

設計：Rubyスレッドのネイティブスレッド対応
Rubyスレッドへの割り込み
 Rubyスレッドは割り込み可能• 他スレッドに例外可能• Timeout 処理に利用

特に I/O のタイムアウト• シグナルハンドラの実行

t = Thread.new{#...
}
t.raise(exception)

 ネイティブスレッドには「割り込み」インターフェースは無し
17

設計：Rubyスレッドのネイティブスレッド対応
Rubyスレッドへの割り込み(cont.)
 (1) 割り込みフラグのポーリング• VM命令のいくつかの箇所でチェック (2) ブロック状態になる前にブロック解除関数を登録• ポーリングしない部分でも割り込みに対応• 例：selectシステムコールを中断させるブロック
解除→当該スレッドにシグナル送信（select はEINTR で中断）
18

設計：Rubyスレッドのネイティブスレッド対応
管理スレッドの用意
 UNIXでのシグナル受信• PthreadではどのNTに配送されるか不明→シグナル受信専用の管理スレッド• 他のNTはシグナルマスクで受信不可• 受信したらmainスレッドへRubyスレッドへの割り込み機能を利用して割り込み

19

設計：
Rubyスレッドの並列実行
 スレッド情報へのポインタをTLSに
 適切な同期・排他制御の導入• TSなコードの登録• 非TSなコードのための適切なGL制御
 GCのための同期 ロック競合を避けるための工夫

20

設計：Rubyスレッドの並列実行
スレッド情報へのポインタをTLSに
 スレッド情報へのポインタをネイティブスレッドが提供するTLSに格納• TLS: Thread Local Storage• GCC 拡張• Windows VC 拡張• pthread_getspecific の利用

21

設計：Rubyスレッドの並列実行
TSなコードの登録 TS（スレッドセーフ）メソッドの登録• 本質的にロック不要なCメソッド、細粒度ロックを利用して作り直したCメソッドはTSメソッドとして登録（起動時にGL獲得不要）• 具体的なTS化はライブラリ依存• Cメソッド登録APIに「TSメソッド登録」API追加• rb_define_method → rb_define_method_ts• 必要なCメソッドのみTS化することが可能• 性能に影響ある、頻繁に呼ばれるメソッドなど
22

設計：Rubyスレッドの並列実行
非TSなコードのための適切なGL制御
 非TSなコード == 既存のCメソッド実装• メソッド起動時にGL獲得

 TSなコード ==対処したCメソッド or Ruby メソッド

• GL獲得なしで起動可能

 CメソッドはRubyメソッド呼び出し（逆も）可能• メソッド呼び出し時、GL獲得状態によって処理分岐

 例外発生時のGL獲得情報に注意
23

設計：Rubyスレッドの並列実行!TSなコードのための適切なGL制御
Call Graph:
topRuby Method
Locked w/GL
notTS C Method
Ruby Method
TS C Method
notTS C Method Locked w/GL
例外発生時の大域ジャンプ例

メソッド呼び出し24

設計：Rubyスレッドの並列実行
GCのための同期
 RubyのGC → 保守的mark&sweep• GC時、すべてのRubyスレッドを停止• 割り込みのためのポーリングの機構を利用• ブロック時にはマシンコンテキストを保存

 並列GCは今後の課題

25

設計：Rubyスレッドの並列実行
ロックコストを下げるための工夫 排他制御のためのロック→オーバヘッド• とくにロック競合は高いオーバヘッド 下げるためのいくつかの工夫(1) 単一スレッド実行時にはGL無視(2) スレッドローカルヒープの用意(3) ロック不要なメソッドキャッシュ(4) スピンロックの利用(5) 利用CPUの制限(6) 並列実行しない（本質的に並列実行に向かない場合）
26

設計：Rubyスレッドの並列実行
ロックコストを下げるための工夫(cont.) ロックを不要に• (1) 単一スレッド実行時にはGL無視• (2) スレッドローカルヒープの用意• オブジェクトアロケーション時、ロック不要• (3) ロック不要なメソッドキャッシュ• キャッシュヒットすれば余計なコスト不要• キャッシュミス時、コスト増
27

設計：Rubyスレッドの並列実行
ロックコストを下げるための工夫(cont.)
 (5) 利用CPUの制限• 競合を繰り返すRubyスレッドの実行CPUを制限• NPTLのpthread_setaffinity_npを利用• Windows では SetThreadAffinityMask• 一定時間過ぎたら制限を解除• ちょっと後ろ向きの工夫（v.s. TS なコードを増やす）
28

評価
評価環境
 評価環境• CPU: Intel(R) Pentium(R) D CPU 3.46GHzプロセッ
サ（Dual Core/L2 2MB）、4GBメモリ、• OS: Linux 2.6.17-1.2174_FC5 SMP / NPTL
• Compiler: gcc version 4.1.1 20060525 (Red Hat4.1.1-1)

 比較対象のRuby• ruby 1.9.0 (2006-04-08) [x86_64-linux]

 YARV最適化オプション• 融合操作とStack caching 以外すべて
29

評価
スレッド制御 生成・合流はNT制御オーバヘッドで低速に 排他制御はCで再実装したため高速化
 この性能はNTライブラリに依存

生成
合流
排他制御

Ruby (sec) YARV
1.82 (sec) 5.06
0.58
2.32
3.32
0.43
30

評価
スレッド切り替え時間

実
行時
間（秒）

スタックの深さ（再帰の深さ）
31

検討：並列実行における排他制御(c) ジャイアントロックを持つRTのみ実行 GLを実行権として扱い、持つRTのみ実行
 ○ 排他制御不要
 × 並列実行不可能

CPU 1
CPU 2

YARV (NoLock)

RT 1
GL as RightRT 2

NT1
GL as Right
NT232

評価
並列実行（マイクロベンチマーク）
台数効果
◎

GL競合
台数効果×

33

まとめ
 Rubyスレッドを並列実行可能に• RTをNTにマッピング（1:1）• 並列実行のために排他制御・同期を導入• GLを導入し既存のコードが利用可に• TSに書き換えることで段階的に並列度向上• ロックの競合回避のための工夫• 評価の結果、TSコードは台数効果確認
34

今後の課題 処理のTS化（特に文字列・配列処理）• 頻繁に利用するがとにかく規模が大きい

 並列GCの実装
 >2 なCPUコア数での評価
 Rubyプログラミングモデルの変更• Rubyスレッド生成は「速い」→「遅い」• スレッドプールの利用など
35

おわり
ご清聴ありがとうございました。
笹田 耕一 / ささだこういち
sasada@ci.i.u-tokyo.ac.jp
ko1@atdot.net
http://www.atdot.net/yarv/【謝辞】
YARV: Yet Another RubyVM の開発には大変多くの方にご協力いただいております。
本プロジェクトでは IPA 未踏ソフトウェア創造事業の支援を受けています。
この場を借りて深く御礼申し上げます。
36

以降、補足37

Rubyを高速に実行するための処理系
YARV: Yet Another RubyVM
 昨年度未踏ユース
 VM命令セットの設計
 コンパイラの設計・開発
 仮想機械(RubyVM)の設計・開発• スタックマシン（JavaVM / .NET などと一緒） 高速化のためのさまざまな最適化

 オープンソースソフトウェアとして公開中
 http://www.atdot.net/yarv/
38

YARV完成度
 ほとんどのRubyプログラムが実行可能• テストスクリプトがほぼ動作

39

GL競合回避の工夫 その2
GL Stick 競合を繰り返すスレッドがGLを獲得し続ける（解放しない）Stick方式
 一定時間でStickは解除
 汎用的（CPU制限APIは必要なし）
 マクロベンチマークで若干いい性能• もちろん YARV (NoLock) には勝てない
40

文字列・配列処理のTS化が面倒な理由
 文字列・配列は生データを多くの場面でアクセス（参照）されているため、文字列・配列処理部分のみ作り直せばよいというわけではない• 文字列・配列のデータ型を変更し、コンパイルエラーによって上記変更が必要な箇所を洗い出して作り直す予定
41

評価
CPU制限の効果
1.6

Speedup Ratio

1.4
1.2
10.8
0.6

YARV (NoLock)
YARV (P=2, NoLimit)
YARV (P=2, Limit)

0.4
0.2
042

評価
スレッドローカルヒープの効果
2.5

Speedup Ratio

21.5
1

YARV (NoLock)
YARV (P=2, w/Lock)
YARV (P=2, wo/Lock)

0.5043

評価
ロック不要なメソッドキャッシュの評価
8Speedup Ratio

76543

YARV (NoLock)
YARV (P=2, w/Lock)YARV (P=2, wo/Lock)

21044

評価
単一スレッド時にはGL制御しない
2.5

Speedup Ratio

2
YARV (NoLock)
1.5
YARV (P=2, wo/AloneCheck)
1

YARV (P=2, w/AloneCheck)

0.5045

評価
GL獲得時スピンロックに
1.6

Speedup Ratio

1.4
1.2
10.8
0.6

YARV (NoLock)
YARV (P=2, wo/SpinLock)
YARV (P=2, w/SpinLock)

0.4
0.2
046