# HG changeset patch # User Masataka Kohagura # Date 1399356105 -32400 # Node ID 110e54772bf9ca4b33dd5241bdf858a55a0fb1a7 # Parent ec6c5c55a19b9f3eda3c8a6e6f4d9ef7dfcba522 fix slide diff -r ec6c5c55a19b -r 110e54772bf9 slide/April_25th.html --- a/slide/April_25th.html Mon May 05 23:10:01 2014 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,364 +0,0 @@ - - - - - slide - - - - - - - - - - - - - - - - - - - - - - - - -
- -
- - - - - - - - -
-

Cerium による並列処理向け I/O の設計と実装

-
-
- 琉球大学大学院 古波倉 正隆,河野 真治 -
-
- - - -
- -

I/Oを含むアプリケーションの並列化

- I/O を含む Task は ディスクかの読み込む時間がかかる。
- -> I/O をどうにか速くできないか? -

- Cerium :
- CellおよびLinux、 Mac OS X 上で動く並列プログラミングフレームワーク -

- -
    -
  • ファイル読み込みとアプリケーションの分離
    • -
  • I/O専用の Threadを追加
    • -
- mmap 実装と比較して1.5倍の速度を得た - -
- -
- -

Cerium Task Manager の構造

- - - - - - - -
-
    -
  1. Taskを生成
    2. -
  2. 依存関係のチェック
    3. -
  3. Schedulerに転送
    4. -
  4. 並列実行
    5. -
-
-

- ファイルを読みながら、Word Count や grep などを
- 並列実行したい -

-

- 計算よりも読み込みを優先しなければならない。読み込みで待ちが入ってしまうので、IO Thread を追加 -

- -
- - -
-

Block 単位の読み込みと並列計算

-
- -
    -
  1. ファイルをある一定の大きさで読み込む
    2. -
  2. 読み込んだテキストファイルに対して、それぞれ計算を行う
    3. -
  3. 計算した結果を集計する
    4. -
-
- - -
-

mmap の特徴

- 従来では mmap を使って読み込んでいた - - - - - - - -
-
    - -
  • - mmap は、ファイルを直接メモリ空間に map する。
    - アクセスされたメモリ部分を OS が自動的に読み込む。
    -
    • -
  • - code がシンプルだが、読み込み終わるまで待たされる。
    -
    • -     -
-
-
- - -
-

読み込みながら計算を行う

-
- -
- -
    -
  • Read は 連続で動作しファイルを読み込む
    • -
  • Read の待ちは CPU を消費しない
    • -
  • 読み込み終わったブロックに対して、
    並列 Task を起動する
    • -
-
- - -
-

Blocked Read の実装

-
- -
- -
    -
  • - Task を一度に生成するとメモリを圧迫する。
    - Block 単位で徐々に起動していく。 -
    • -
  • - Blocked Read Task が読み込み終わるまで、
    Task Blockを待たせる -
    • -
  • - 待ち合わせには Cerium の wait for を使用する。 -
    • -
-
- -
-

I/O 専用 thread での Blocked Read の実装

-
- -
    -
  • priority が最優先されるので、Blocked Read Task に割り込みが行われなくなる
    -
  • pthread_setschedparam にて実装
    -
    • -
-
- -
-

I/O 専用の thread を使用しない場合

-
- -
    -
  • Blocked Read は連続で行われなければならない。
    しかし、Task が割り振られてしまう可能性がある。
    • -
-
- -
-

実験環境

-
-
    -
  • Mac OS X 10.9.1
    • -
  • 2*2.66 GHz 6-Core Intel Xeon
    • -
  • Memory 16GB 1333MHz DDR3
    • -
  • HHD 1TB
    • -
  • file size : 約 10 GB
    • -
  • ファイルに対して Boyer-Moore String Seaech で文字列検索をかける
    • -
  • ファイルの読み込みから結果までを測定
    • -
-
- - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
read modeCPU numave time(s)
mmap2106.2
mmap12154.6
一括Read12114.9
Blocked Read(SPE_ANY)12106.0
Blocked Read(IO_0)(IO) 1 + (Task) 1199.2
- -
    -
  • Blocked Read & IO_0 が mmap より1.55倍速度が向上
    • -
  • Blocked Read を IO 専用 thread で実装すると、6%改善
    • - -
  • mmap で並列の Task で走らせると 1つ1つの Task がファイルを読み込み、ランダムアクセスとなって
    しまうため速度が遅くなってしまう。
    • -
-
- - -
-

まとめ

-
    -
  • I/O と Task を分離し、同時に動くように改良した。
    • -
  • I/O 専用の Thread の追加
    • -
  • - I/O を含む Task をで並列実装するときに mmap では不向きであり、 - Blocked Read で読み込みを制御したほうが効果的。 -
    • -
-

今後の課題

-
    -
  • Cerium の API として実装
    • -
  • - 様々な実装の試み
    (I/O threads を 2つ、分割 mmap・・・) -
    • -
  • - grepの実装 -
    • -
-
- -
-
- -
-
- -
-
- - -
-
- - -
-
- -
-
- -
-
- -
- - diff -r ec6c5c55a19b -r 110e54772bf9 slide/index.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/index.html Tue May 06 15:01:45 2014 +0900 @@ -0,0 +1,490 @@ + + + + + slide + + + + + + + + + + + + + + + + + + + + + + + + +
+ +
+ + + + + + + + +
+

Cerium による並列処理向け I/O の実装

+
+
+ 古波倉 正隆,河野 真治 +
+
+ +
+

I/Oを含むアプリケーションの並列化

+ + ファイル内の文字列検索を行うようなプログラムを走らせたとき、 + 文字列検索よりもファイルの読み込みに時間がかかることが多い。 + + I/O は、ディスクからの読み込む時間がかかる。
+ -> I/O をどうにか速くできないか? +

+ Cerium :
+ CellおよびLinux、 Mac OS X 上で動く並列プログラミングフレームワーク +

+ +
    +
  • ファイル読み込みとアプリケーションの分離
    • +
  • I/O専用の Threadを追加
    • +
+ mmap 実装と比較して1.5倍の速度を得た +
+ +
+ +

Cerium Task Manager の構造

+ + + + + + + +
+
    +
  1. Taskを生成
    2. +
  2. 依存関係のチェック
    3. +
  3. Schedulerに転送
    4. +
  4. 並列実行
    5. +
+
+

+ ファイルを読みながら、Word Count や grep などを
+ 並列実行したい +

+

+ 計算よりも読み込みを優先しなければならない。読み込みで待ちが入ってしまうので、IO Thread を追加 +

+ +
+ +
+

Cerium の例題 : WordCount

+ +
+ + +
+

Block 単位の読み込みと並列計算

+
+ +
    +
  1. ファイルをある一定の大きさで読み込む
    2. +
  2. 読み込んだテキストファイルに対して、それぞれ計算を行う
    3. +
  3. 計算した結果を集計する
    4. +
+
+ + +
+

mmap の特徴

+ 従来では mmap を使って読み込んでいた + + + + + + + +
+
    + +
  • + mmap は、ファイルを直接メモリ空間に map する。
    + アクセスされたメモリ部分を OS が自動的に読み込む。
    +
    • +
  • + code がシンプルだが、読み込み終わるまで待たされる。
    +
    • +     +
+
+
+ + +
+

読み込みながら計算を行う

+
+ +
+ +
    +
  • Read は 連続で動作しファイルを読み込む
    • +
  • Read の待ちは CPU を消費しない
    • +
  • 読み込み終わったブロックに対して、
    並列 Task を起動する
    • +
+
+ + +
+

Blocked Read の実装

+
+ +
+ +
    +
  • + Task を一度に生成するとメモリを圧迫する。
    + Block 単位で徐々に起動していく。 +
    • +
  • + Blocked Read Task が読み込み終わるまで、
    Task Blockを待たせる +
    • +
  • + 待ち合わせには Cerium の wait for を使用する。 +
    • +
+
+ +
+

I/O 専用 thread での Blocked Read の実装

+
+ +
    +
  • Task とは別に Thread を割り当てているので、Read Task に割り込みが行われなくなる
    • +
  • pthread_setschedparam にて実装
    +
    • +
+
+ +
+

I/O 専用の thread を使用しない場合

+
+ +
    +
  • Blocked Read は連続で行われなければならない。
    しかし、Task が割り振られてしまう可能性がある。
    • +
+
+ +
+

実験概要

+

実験環境

+
    +
  • Mac OS X 10.9.1
    • +
  • 2*2.66 GHz 6-Core Intel Xeon
    • +
  • Memory 16GB 1333MHz DDR3
    • +
  • HDD 1TB 7200 rpm SATA 3.0 Gbps
    • +
  • ファイルに Word Count をかける
    • +
  • ファイルの読み込みから結果までを測定
    • +
+
+ +
+

実験 : CPU 数での比較

+ +

表内の数値の単位は全て秒である。

+ +division size = 128k , 48 Task num / 1 Block + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
read mode \ CPU numCPU 1CPU 4CPU 8CPU 12
mmap20.17922.86122.78922.713
read21.35115.73714.78512.520
Blocked Read(SPE_ANY)18.53115.64615.28714.028
Blocked Read(IO_0)13.93014.63414.77410.295
+ +
    +
  • CPU 12 のとき、Blocked Read(IO_0) が mmap より2.21倍 速度が向上した。
    • +
  • Blocked Read を IO 専用 thread で実装すると、1.36 倍 の改善が見られた。
    • +
  • mmap で並列の Task で走らせると 1つ1つの Task がファイルを読み込み、ランダムアクセスとなって
    しまうため速度が遅くなってしまう。
    • +
+ +

実験 : division size を変更してみる

+ +division size = 16k , 48 Task num / 1 Block + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
read mode \ CPU numCPU 1CPU 4CPU 8CPU 12
mmap15.35311.28711.70711.137
read16.84611.73011.48711.437
Blocked Read(SPE_ANY)13.29711.98410.88711.146
Blocked Read(IO_0)11.50311.43711.36511.412
+ +
+ +
+

実験 : 使用 CPU 数での比較

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
read mode \ CPU numCPU 1CPU 4CPU 8CPU 12
mmap
read
Blocked Read(SPE_ANY)
Blocked Read(IO_0)
+ +
    +
  • +
  • +
  • +
+
+ +
+

まとめ

+
    +
  • I/O と Task を分離し、同時に動くように改良した。
    • +
  • I/O 専用の Thread の追加
    • +
  • + I/O を含む Task をで並列実装するときに mmap では不向きであり、 + Blocked Read で読み込みを制御したほうが効果的。 +
    • +
+

今後の課題

+
    +
  • Cerium の API として実装
    • +
  • + 様々な実装の試み
    (I/O threads を 2つ、分割 mmap・・・) +
    • +
  • + grepの実装 +
    • +
+
+ +
+
+ +
+
+ + +
+
+ + +
+
+ +
+
+ +
+
+ +
+ +