# HG changeset patch # User Tatsuki IHA # Date 1518450047 -32400 # Node ID 0050ad0b4dd712d90084ce26352e34cab044f1ae # Parent 66b8451005cda600a67fdee7111c4d21d03cfb37 Fix fig diff -r 66b8451005cd -r 0050ad0b4dd7 paper/fig/codegear-datagear.graffle Binary file paper/fig/codegear-datagear.graffle has changed diff -r 66b8451005cd -r 0050ad0b4dd7 paper/fig/codegear-datagear.pdf Binary file paper/fig/codegear-datagear.pdf has changed diff -r 66b8451005cd -r 0050ad0b4dd7 paper/fig/codegear-datagear.xbb --- a/paper/fig/codegear-datagear.xbb Mon Feb 12 15:40:23 2018 +0900 +++ b/paper/fig/codegear-datagear.xbb Tue Feb 13 00:40:47 2018 +0900 @@ -4,5 +4,5 @@ %%HiResBoundingBox: 0.000000 0.000000 535.000000 427.000000 %%PDFVersion: 1.3 %%Pages: 1 -%%CreationDate: Sun Jan 7 05:20:14 2018 +%%CreationDate: Tue Feb 13 00:39:37 2018 diff -r 66b8451005cd -r 0050ad0b4dd7 paper/fig/meta_cg_dg.graffle Binary file paper/fig/meta_cg_dg.graffle has changed diff -r 66b8451005cd -r 0050ad0b4dd7 paper/fig/meta_cg_dg.pdf Binary file paper/fig/meta_cg_dg.pdf has changed diff -r 66b8451005cd -r 0050ad0b4dd7 paper/fig/meta_cg_dg.xbb --- a/paper/fig/meta_cg_dg.xbb Mon Feb 12 15:40:23 2018 +0900 +++ b/paper/fig/meta_cg_dg.xbb Tue Feb 13 00:40:47 2018 +0900 @@ -4,5 +4,5 @@ %%HiResBoundingBox: 0.000000 0.000000 608.000000 202.000000 %%PDFVersion: 1.3 %%Pages: 1 -%%CreationDate: Thu Jan 11 20:16:31 2018 +%%CreationDate: Tue Feb 13 00:36:02 2018 diff -r 66b8451005cd -r 0050ad0b4dd7 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r 66b8451005cd -r 0050ad0b4dd7 slide/images/meta_cg_dg.graffle Binary file slide/images/meta_cg_dg.graffle has changed diff -r 66b8451005cd -r 0050ad0b4dd7 slide/slide.md --- a/slide/slide.md Mon Feb 12 15:40:23 2018 +0900 +++ b/slide/slide.md Tue Feb 13 00:40:47 2018 +0900 @@ -40,7 +40,6 @@ ## Meta Gear - メタ計算 は Code Gear の接続間に行われる -- メタ計算 の処理も Code/Data Gear で実現する - この Gear を Meta Code/Data Gearと呼ぶ - Meta Code Gear は メタ計算 のプログラム部分 - Meta Data Gear は Meta Code Gear で管理されるデータ部分 @@ -76,9 +75,10 @@ - 従来のOS のスレッドやプロセスに対応し、以下の要素を定義している - 独立したメモリ空間 - Code/Data Gear へのポインタ + - Code/Data Gear は番号で指定する - 並列実行用の Task 情報 - Data Gear の型情報 -- Gears OS ではメタ計算でこの Context を経由して Data Gear にアクセスする +- Gears OS ではメタ計算で Context を経由して Code/Data Gear にアクセスする ## Data Gear の表現 - Data Gear は構造体を用いて定義する @@ -123,6 +123,7 @@ } ``` +<- このページを書き換える -> ## Context での stub Code Gear の記述の問題点 - stub Code Gear は Context から Code Gear と Data Gear の全ての組合せを展開して記述する必要がある - しかし、 Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた @@ -253,35 +254,28 @@ ``` ## 並列処理の構成 -- 今回はInterface を利用した並列処理機構の実装を行う +- 今回は並列処理機構の実装を Interface を利用して行う - 構成要素として以下が挙げられる - - Task(Context) + - Task - TaskManager - Worker の生成、依存関係を解決したTask を Worker に送信する - Worker - - SynchronizedQueue から Task を取得し、実行する + - SynchronizedQueue から Task を一つずつ取得し、実行する + - Worker は CPU、 GPU の対応した数分生成する + - Worker 毎に POSIX Therad などのスレッドを生成し、 Code Gear を実行する - SynchronizedQueue - マルチスレッド 環境でもデータの一貫性を保証する Queue -## Task(Context) -- Gears OS では並列実行する Task を Context で表現する +## Task +- Gears OS では Context が並列実行の Task に相当する - Context は Task用の情報として以下の情報をもっている - 実行する Code Gear - Input/Output Data Gear の格納場所 - 待っている Input Data Gear の数 -- 実際に実行される Code Gear の引数情報は Interface の Code Gear 実装と同等に記述できる - - Code Gear の stub Code Gear は自動生成される - -``` c -__code add(struct Integer* input1, struct Integer* input2, __code next(struct Integer* output, ...)) { - output->value = input1->value + input2->value; - goto next(output, ...); -} -``` ## TaskManger +- Worker を作成、終了処理を行う - 依存関係を解決した Task を各 Worker の Queue に送信する -- Worker を作成、終了処理も行う
@@ -289,19 +283,19 @@
    -
  1. Task を Input Data Gear として
    2. - TaskManager の spawn を呼び出す -
  2. Input Data Gear が揃っているかを確認する
    3. -
  3. 揃っている場合、 Worker の Queue に
    4. - Task を送信する +
  4. Task を Input Data Gear として
    5. + TaskManager の spawn を呼び出す +
  5. Input Data Gear が揃っているかを確認する
    6. +
  6. 揃っている場合、 Worker の Queue に
    7. + Task を送信する
## Worker -- 初期化の際にスレッドと Worker 用の Context を生成する -- 生成されたスレッドではTaskManager から送信された Task を取得して実行する +- 初期化時に Worker 用の Context を生成する +- TaskManager から送信された Task を取得して実行する
@@ -312,7 +306,7 @@
  • Worker は Queue から Task を取得する
  • Worker の Context から
    • Task の Context へ入れ替える -
  • Task の Code Gear を実行
    • +
  • Task に設定されている Code Gear を実行
  • Task の Output Data Gear の書き出し
  • Task Context から
    • Worker の Context へ入れ替える @@ -324,8 +318,8 @@ ## Synchronized Queue - Worker で使用される Queue -- Task を送信するスレッドと Task を取得するスレッドで操作される -- そのためマルチスレッドでのデータの一貫性を保証する必要がある +- Task を送信するTaskManagerと Task を取得するWorker毎で操作される +- そのためマルチスレッドでのデータの同期処理を行う - Gears OS では CAS(Check and Set、 Compare and Swap) を使用した Synchronized Queue として実装する - CAS は値を更新する際に更新前の値と実際に保存されているメモリ番地の値を比較する - この Queue は Queue Interface を実装し、 List を利用した実装を行った @@ -345,7 +339,7 @@ ## 依存関係の解決 - 依存関係の解決は Data Gear がメタレベルで持っている Queue を使用する -- この Queue には Data Gear に依存関係がある Code Gear が格納されている +- この Queue には Data Gear に依存関係がある Context が格納されている
    @@ -353,7 +347,7 @@
      -
    1. Task の Code Gear を実行する
      2. +
    2. Task に設定されている Code Gear を実行する
    3. Output Data Gear の書き出し処理を行う
      4. この際にメタレベルの Queue を参照する
    4. 依存関係にある Task を取り出し、 待っている
      5. @@ -382,11 +376,10 @@ ## CUDA への対応 - Gears OS は GPU での実行もサポートする -- GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる -- 今回は CUDA への実行のサポートをおこなった - CUDA は GPU を Device、 CPU を Host として定義する - CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する -- 今回 CUDAWorker、CUDAExecutor、 CUDABuffer を使用して CUDA に合わせた並列処理機構を提供する +- GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる +- 今回、CUDA に合わせた並列処理機構を Interface を用いて実装した ## CUDAWorker - CUDA で実行する Task を受け取る Worker @@ -497,10 +490,6 @@ - 並列処理向けのソートアルゴリズム - 決まった2点間の要素の入れ替えをステージ毎に並列に実行し、 Output Data Gear として書き出し、次のステージの Code Gear の Input Data Gear とする -
      - message -
      - ## BitonicSort の結果 - 要素数 2^24 - CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する @@ -563,16 +552,6 @@ } ``` -## OpenMP との比較 -- OpenMP で Twice を実装し、速度比較を行った -- OpenMP は 1CPU と 32CPU で約10.8倍の速度向上が見られた -- 一方 Gears OS では約27.1倍と台数効果は高くなっている -- しかし、 Gears OS は 1CPU の実行速度が OpenMP に比べて大幅に遅くなっている - -
      - message -
      - ## Go 言語との比較 - Go 言語は並列実行を **go funciton(argv)** の構文で行う。 この実行を goroutine と呼ぶ - データの待ち合わせはチャネルというデータ構造で行う @@ -596,6 +575,16 @@ } ``` +## OpenMP との比較 +- OpenMP で Twice を実装し、速度比較を行った +- OpenMP は 1CPU と 32CPU で約10.8倍の速度向上が見られた +- 一方 Gears OS では約27.1倍と台数効果は高くなっている +- しかし、 Gears OS は 1CPU の実行速度が OpenMP に比べて大幅に遅くなっている + +
      + message +
      + ## Go 言語との比較 - Go 言語でも OpenMP と同様に Twice を実装し、速度比較を行った - Go 言語は 1CPU と 32CPU で約4.33倍の速度向上が見られた