# HG changeset patch # User Masataka Kohagura # Date 1455389630 -32400 # Node ID 4d42d11ebed699a7748964ba41bbf5184c8d6dc9 # Parent 69467f538e4ef549700ae6da661bfa4b1b41cf8a add diff -r 69467f538e4e -r 4d42d11ebed6 slide/s6/index.html --- a/slide/s6/index.html Sun Feb 14 02:56:09 2016 +0900 +++ b/slide/s6/index.html Sun Feb 14 03:53:50 2016 +0900 @@ -87,7 +87,7 @@ @@ -112,34 +112,8 @@ - -

はじめに

@@ -182,7 +156,7 @@

mmap の特徴

- +

    @@ -204,7 +178,7 @@

    mmap を使用せずに、read を独立したスレッドで実行させる。そして、読み込んだ部分に対して Word Count を並列に起動する。


    - +

    @@ -220,133 +194,6 @@
-

読み込みを行ってから計算を行う

-
- -
- -
    -
  • 読み込みを行ってから計算を行うので、読み込みの間、CPU に待ち時間が発生してオーバーヘッドとなる。
    • -
-
- -
-

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

- -

- I/O は、ディスクからの読み込む時間がかかる。
- -> I/O をどのように実装したら、並列処理とI/Oが干渉をなくして全体のパフォーマンスを上げれるか??
-

- -

- そこで本研究では、 -

- - -
    -
  • ファイル読み込みとアプリケーションの分離するための実装法
    • -
  • I/O専用の Threadを追加
    • -
  • mmap と比較や、様々な実験環境で計測
    • -
-

- 以上3点を行った。 -

-
- - -
-

Cerium Task Manager の構造

-

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

-
-

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

+

Cerium による文字列処理の並列処理
- - - - - - -
-
    -
  1. User が Taskを生成
    2. -
  2. 依存関係のチェック
    3. -
  3. 各Schedulerに Task を転送
    4. -
-
-

- User が Word Count などの Task を生成して、それらを GPU や CPU などに計算させるように User 自身で設定することができる。 -

-

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

-

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

- - -
-

大きなファイルに対するデータ並列

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

Blocked Read の実装

-

- 読み込みながら並列計算を実行する方法を、Blocked Read と名付けた。 -

-
- - -
- - -
- - -
-

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

-
- - -
- -

実験概要

実験環境

-
-

実験1: 使用 CPU 数を変更させた時の実行速度の比較

-
-
- - -
-

実験2: Blocked Read size を変更してみる

-

-filesize : 1GB -

-

-Blocked read Task 1つ当たりの読み込み量 : 128 kbyte * 48 -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
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
- - -

-実験1との比較
-Blocked read Task 1つ当たりの読み込み量 : 16 kbyte * 48 -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
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
-
- -
-

実験2: Blocked Read size を変更してみる

-
-
- -
-

実験3: CPU 数を固定して、Blocked Read size を変更してみる

-

- word count task 1つ当たりの処理量を 4kbyte ~ 256kbyte で変化させてみた。 -

-

- CPU 12 で全て測定している。 -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
read mode \ Blocled Read size 4k * 48 8k * 48 16k * 48 32k * 48 64k * 48 128k * 48 256k * 48
mmap
11.867
10.570
11.803
14.915
16.626
16.923
18.474
read
12.020
11.585
11.729
11.661
12.497
11.347
11.658
Blocked Read(SPE_ANY)
11.508
15.932
11.407
12.816
12.454
12.891
11.962
Blocked Read(IO_0)
11.342
12.242
11.636
12.331
10.870
11.295
11.723
- -
- -
-

実験3: CPU 数を固定して、Blocked Read size を変更してみる

-
-
- -
-

実験4: mmap 後に madvise で読み込み方法を設定する

- -

-Blocked read Task 1つ当たりの読み込み量 : 16 kbyte * 48 -

-

-OS : Mac OS 10.9.2 -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
madvise flag time(s)
MADV_NORMAL(default)
11.841
MADV_RANDOM
42.891
MADV_SEQENTIAL
38.935
MADV_WILLNEED
10.916
MADV_DONTNEED
17.506
MADV_FREE
16.863
- - -
- - - -
-

実験5: 別のコンピュータにて測定

- -

-ファイルをキャッシュから追い出すために、以下のコマンドを実行した。 - 

% sysctl -w vm.drop_caches=3
-

-Blocked read Task 1つ当たりの読み込み量 : 16 kbyte * 48 -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
read mode \ CPU numCPU 1CPU 2CPU 3CPU 4CPU 8
mmap
6.852
6.765
7.632
12.504
7.649
read
10.545
8.699
8.667
8.152
7.607
Blocked Read(SPE_ANY)
8.686
10.606
12.995
11.799
14.723
Blocked Read(IO_0)
6.751
6.800
7.311
7.016
6.755
- -

-実験1の測定結果(Mac OS X) -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
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
-
- -
-

実験5: 別のコンピュータにて測定

-
-
- -
-

考察

-

- mmap での実行時は、Blocked Read size を小さくしたほうが速度が向上した。これは、まとめと読み込むサイズが小さくなればなるほど、sequential access に近い動作になるからであると考えられる。 -

-

- I/O の読み込みと並列計算を分離して、同時に処理させたほうが、全体的に安定した速度がでるが、mmapだと一度に読み込む大きさが小さければ速い。 -

-

- mmapは読み込みの大きさによって全体の速度が変わってしまうが、どんな大きさでも安定した速度で改良する余地があると思われる。 -

-

- -

-
-

まとめ