# HG changeset patch # User Shohei KOKUBO # Date 1455747646 -32400 # Node ID 4dcfec1bf1e7eaffaf06093e7d4a92dc15e43a04 # Parent 0188222d28866bdbc99be2c062080b922507edaa revision diff -r 0188222d2886 -r 4dcfec1bf1e7 paper/abstract.tex --- a/paper/abstract.tex Wed Feb 17 20:29:45 2016 +0900 +++ b/paper/abstract.tex Thu Feb 18 07:20:46 2016 +0900 @@ -1,7 +1,14 @@ \begin{abstract} - 本研究では Cerium を開発して得られた知見から Code Segment と Data Segment を用いた並列フレームワークの開発を行なっている。 - Code Segment と Data Segment は処理とデータの単位である。 - 今回設計した Gears OS ではプログラムを Code Segment と Data Segment で記述する。 - Code Segment と Data Segment で記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。 - 本論文では Gears OS の基本的な機能を設計し、CbC(Continuation based C) を用いて実装する。 + Cerium はオブジェクト指向言語である C++ を用いて開発した並列プログラミングフレームワークである。 + Task 間の依存関係を記述することで並列処理を行う。 + しかし、Task 間の依存関係だけではデータの正しさを保証することができない。 + また、Task とのデータの受け渡しに汎用ポインタを使うためそこでデータの型情報を失う。 + 型情報がないので誤った型変換を行うと未定義の動作となる。 + オブジェクト指向も並列処理と相性が悪い。 + 我々の研究室では Code Segment という単位でプログラミングを行う CbC(Continuation based C) を開発している。 + Code Segment は並列処理の単位として用いることができる。 + 本研究では Cerium を開発して得られた知見からデータの単位として Data Segment を定義し、Code/Data Segment を用いた並列プログラミングフレームワーク Gears OS の開発を行う。 + Code/Data Segment で記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。 + 本論文では Gears OS の基本的な機能を設計し、実装に CbC を用いる。 + また、Gears OS の実装自体が Code/Data Segment を用いたプログラミングの指針となるように実装する。 \end{abstract} diff -r 0188222d2886 -r 4dcfec1bf1e7 paper/abstract_eng.tex --- a/paper/abstract_eng.tex Wed Feb 17 20:29:45 2016 +0900 +++ b/paper/abstract_eng.tex Thu Feb 18 07:20:46 2016 +0900 @@ -1,7 +1,14 @@ \begin{abstract_eng} - We are developing parallel framework using Code/Data Segment. - Code/Data Segment are unit of processing and data. - Use Code/Data Segment in Gears OS Programming. + Cerium is parallel programming framework developed by C++. + Describe Task-Dependency for parallel computing. + Task-Dependency can't ensure data correctness. + Task parameters has no type information for the use of untyped pointer. + Wrong type cast will produce undefined results. + Object-oriented programming(OOP) is incompatible with parallel computing. + Continuation based C(CbC) is programming language which uses Code Segment. + Use Code Segment as a unit of parallel computing. + We are developing Gears OS using Code/Data Segment. Parallelism in a high performance Gears OS with Code/Data Segment. - We show same implementation of Gears OS using CbC(Continuation based C). + We show same implementation of Gears OS using CbC. + Gears OS implementation is a guide to programming using Code/Data Segment. \end{abstract_eng} diff -r 0188222d2886 -r 4dcfec1bf1e7 paper/cerium.tex --- a/paper/cerium.tex Wed Feb 17 20:29:45 2016 +0900 +++ b/paper/cerium.tex Thu Feb 18 07:20:46 2016 +0900 @@ -451,18 +451,29 @@ データ転送の最適化が十分に成されていない可能性があるので、GPU の実行機構を見直す必要がある。 \section{Cerium の問題点} -Cerium では Task 間の依存関係を記述することで並列処理を実現する。 -しかし、本来 Task はデータが揃えば実行可能になるものである。 -Task 間の依存関係だけでは待っている Task が不正な処理を行いデータがおかしくなっても Task の終了は通知され、そのまま処理が続行されてしまう。 -その場合、どこでデータがおかしくなったのか特定するのは難しくデバッグに多くの時間が取られてしまう。 -また、Cerium の Task は汎用ポインタでデータを受け取るので型の情報がない。 -型の情報がないので Task を実行するまで正しい型かどうか判断することが出来ない。 -不正な型でも強制的に型変換され実行されるのでデータの構造を破壊する可能性がある。 -型システムによってプログラムの正しさを保証することも出来ず、バグが入り込む原因になる。 - -Cerium の Allocator は Thread 間で共有されている。 -共有されているので、ある Thread がメモリを確保しようとすると他の Thread は終了を待つ必要がある -その間メモリを確保することができないので処理が止まり、なにもしない時間が生まれてしまう。 -これが並列度の低下に繋がり、処理速度が落ちる原因になる。 +\begin{itemize} + \item Task 間の依存関係 \\ + Cerium では Task 間の依存関係を記述することで並列処理を実現する。 + しかし、本来 Task はデータが揃えば実行可能になるものである。 + Task 間の依存関係だけでは待っている Task が不正な処理を行いデータがおかしくなっても Task の終了は通知され、そのまま処理が続行されてしまう。 + その場合、どこでデータがおかしくなったのか特定するのは難しくデバッグに多くの時間が取られてしまう。 + \item データの型情報 \\ + Cerium の Task は汎用ポインタでデータを受け取るので型の情報がない。 + 型の情報がないので Task を実行するまで正しい型かどうか判断することが出来ない。 + 不正な型でも強制的に型変換され実行されるのでデータの構造を破壊する可能性がある。 + 型システムによってプログラムの正しさを保証することも出来ず、バグが入り込む原因になる。 + \item Allocator \\ + Cerium の Allocator は Thread 間で共有されている。 + 共有されているので、ある Thread がメモリを確保しようとすると他の Thread は終了を待つ必要がある + その間メモリを確保することができないので処理が止まり、なにもしない時間が生まれてしまう。 + これが並列度の低下に繋がり、処理速度が落ちる原因になる。 + \item オブジェクト指向と並列処理 \\ + 一般的に同じ入力に対して、同じ出力を返すことが保証される参照透過な処理は並列化を行いやすい。 + 一方、オブジェクト指向は保守性と再利用性を高めるためにカプセル化やポリモフィズムを重視する。 + オブジェクトの状態によって振る舞いが変わるため並列処理との相性が悪いと言える。 + \item Cerium の実装 \\ + Ceirum の実装自体が並列処理を意識したものになっていない。 + 並列プログラミングフレームワークはそれ自体が並列処理を記述するための指針となるように実装されているべきである。 +\end{itemize} 今回設計した Gears OS はこれらの問題を解決することを目的としている。 diff -r 0188222d2886 -r 4dcfec1bf1e7 paper/conclusion.tex --- a/paper/conclusion.tex Wed Feb 17 20:29:45 2016 +0900 +++ b/paper/conclusion.tex Thu Feb 18 07:20:46 2016 +0900 @@ -46,5 +46,9 @@ Gears OS 上でマルチコア CPU を用いた実行を可能にしたが、GPU などの他のプロセッサを演算に用いることができない。 Code/Data Segment を用いて各プロセッサのアーキテクチャにマッピングした実行機構を実装し、演算に利用できるようにする必要がある。 +Data Segment は共用体と構造体によって定義したが、Data Segment 専用の構文を準備するべきである。 +Context は必要な Data Segment のみを持っているべきであり、すべての Data Segment を知っている必要はない。 +必要な Data Segment は実行可能な Code Segment のリストを参照することで推論することができる。 + 型情報を残すために Data Segment を定義しているが Data Segment の型情報を検査していない。 プログラムの正しさを保証するために Data Segment の型情報を検査する型システムを Gears OS 上に実装する必要がある。 diff -r 0188222d2886 -r 4dcfec1bf1e7 paper/evaluation.tex --- a/paper/evaluation.tex Wed Feb 17 20:29:45 2016 +0900 +++ b/paper/evaluation.tex Thu Feb 18 07:20:46 2016 +0900 @@ -3,6 +3,7 @@ つまり、依存関係のない処理ならば並列処理することが可能である。 本章では依存関係のない簡単な例題を用いて Gears OS の評価を行う。 +また、Gears OS の実装自体への評価も行う \section{Twice} Twice は与えられた整数配列を2倍にする例題である。 @@ -65,3 +66,21 @@ 今回、例題に用いた Twice は依存関係のない並列処理である。 本来、並列処理には複雑な依存関係が存在するのが一般的である。 並列フレームワークには複雑な依存関係を解決しながら十分な並列度を保てることが必須なので依存関係を解決するための TaskManager の実装が必要である。 + +\section{Gears OS の実装} +\begin{itemize} +\item Code Segment \\ + Code Segment は分割・統合を容易に行うことができる。 + 巨大な Code Segment を記述することも可能だが、それは好ましくない。 + 今回の実装では制御構文で Code Segment を分割するようにコーディングを行った。 + 制御構文で分割することで Code Segment のサイズを小さくすることには繋がったが、Code Segment の数が増加した。 + Code Segment には必ず stub が付属するので記述量が2倍ほどになる。 + CbC の構文サポートを利用することで記述量を減らすことはできるが、正しいコードに変換できない場合もある。 + Code Segment の継続ではスタックに値が積まれないので、デバッグの際にどの Code Segment から接続されたか特定できない。 +\item Data Segment \\ + Data Segment は共用体と構造体を用いて表現した。 + 現状ではすべての Context が同じ定義を持つことになる。 + 必要ない Data Segment を持つ場合もあるので好ましくない。 + 定義されているべき Data Segment は実行可能な Code Segment のリストから推論することが可能である。 + 専用の構文を準備し、必要な Data Segment のみ持つようにするべきである。 +\end{itemize} diff -r 0188222d2886 -r 4dcfec1bf1e7 paper/intro.tex --- a/paper/intro.tex Wed Feb 17 20:29:45 2016 +0900 +++ b/paper/intro.tex Thu Feb 18 07:20:46 2016 +0900 @@ -13,12 +13,11 @@ Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする。 Cerium では依存関係を Task 間で設定するが、本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することができない。 また、Task には汎用ポインタとしてデータの受け渡しを行うので型情報を失う。 -Task 側で正しく明示的に型変換する必要があり、間違った型変換を行うとデータ構造自体を破壊する可能性がある。 +Task 側で正しく明示的に型変換する必要があり、誤った型変換を行うとデータ構造自体を破壊する可能性がある。 型システムによって検査することも出来ず、型に基づく一連の不具合が常に付きまとう。 今回、設計・実装を行なった Gears OS は Code Segment と Data Segment によって構成される。 Code Segment は処理の単位、Data Segment はデータの単位となる。 -Gears OS を用いるプログラムも Code/Data Segment によってプログラムを分割して記述する。 Gears OS では Code/Data Segment を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする。 また、Gears OS の実装自体が Code/Data Segment を用いたプログラミングの指針となるように実装する。 Gears OS における Task は実行する Code Segment と実行に必要な Input Data Segment, 出力される Output Data Segment の組で表現される。 diff -r 0188222d2886 -r 4dcfec1bf1e7 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r 0188222d2886 -r 4dcfec1bf1e7 slide/index.html --- a/slide/index.html Wed Feb 17 20:29:45 2016 +0900 +++ b/slide/index.html Thu Feb 18 07:20:46 2016 +0900 @@ -87,7 +87,7 @@ @@ -119,30 +119,55 @@
-

Cerium の問題点(1/2)

+

Cerium の問題点

+ +

Cerium では Task 間の依存関係を設定することで並列処理を実現する。 しかし、本来 Task は必要なデータが揃うことで実行可能になるものである。 Task 同士の依存関係だけでは前の Task が不正な処理を行いデータがおかしくなっても Task の終了は通知され、そのまま処理が続行されてしまう。 データがどこでおかしくなったのか特定するのは難しく、デバックに時間が取られる。

+ -
-
- -

Cerium の問題点(2/2)

Task は汎用ポインタでデータの受け渡しを行うのでそこで型情報が落ちる。 -Task 側で正しく型変換を行うことで正しい処理を行うことができるが、間違った型変換を行うとデータ構造を破壊する可能性がある。 +Task 側で正しく型変換を行うことで正しい処理を行うことができるが、誤った型変換を行うと未定義な動作となりデータ構造を破壊する可能性がある。 型システムによるプログラムの正しさを保証することもできず、型に基づく一連の不具合が起こる危険性がつきまとう。

+

Cerium の問題点

+ + +

Cerium の Allocator は Thread 間で共有されている。 +ある Thread がメモリを確保しようとすると他の Thread はその間メモリを確保することができない。 +これが並列度の低下に繋がり、処理速度が落ちる原因になる。

+ + + +

同じ入力に対し、同じ入力を返すことが保証される参照透過な処理は並列化を行いやすい。 +一方、オブジェクト指向は保守性と再利用性を高めるためにカプセル化やポリモフィズムを重視する。 +オブジェクトの状態によって振る舞いが変わるため並列処理との相性が悪い。

+ + +
+
+

Gears OS

-

本研究では Code Segment と Data Segment によって構成される Gears OS の設計・実装を行った。 -プログラムを Code/Data Segment で分割して記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。

+

本研究では Code Segment と Data Segment によって構成される Gears OS の設計・実装を行った。

-

Gears OS の基本的な機能の実装には本研究室で開発している CbC(Continuation based C)を用いた。

+

Code/Data Segment で分割して記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。

+ +

Gears OS の基本的な機能の実装には本研究室で開発している CbC(Continuation based C) を用いた。

@@ -156,6 +181,70 @@ Code Gear には任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込みを行う。 接続された Data Gear 以外にアクセスすることは

+

Data Gear はデータそのものを表す。 +int や文字列などの Primitive Data Type を複数持つ構造体として定義する。

+ +

Gear 特徴として処理やデータの構造が Code/Data Gear に閉じていることにある。 +これにより実行時間、メモリ使用量などを予測可能なものにする。

+ + + +
+ +

Gears OS の構成

+ + +

接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、独立したメモリ空間を持っている。 +複数の Context で TaskQueue と Persistent Data Tree は共有される。

+ + + +

ActiveTaskQueue と WaitTaskQueue の2種類の TaskQueue がある。 +ActiveTaskQueue には実行可能な Task が挿入され、WaitTaskQueue には依存関係が解決されていない Task が挿入される。 +先頭と末尾の Element へのポインタを持つ Data Gear と Task へのポインタと次の Element へのポインタを持つ Data Gear で構成される。 +Compare and Swap(CAS) を利用することでスレッドセーフに Queue を操作することができる。

+ + +
+
+ +

Gears OS の構成

+ + +

Data Gear の管理を行う。 +非破壊木構造で構成されるため読み書きを平行して行うことができる。 +Red-Black Tree アルゴリズムを用いて平衡性を保ち、挿入・削除・検索における計算量を保証する。 +Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。

+ + + +

Gears OS における Task は実行する Code Gear と Input/Output Data Gear の組で表現される。 +Input/Output Data Gear から依存関係を決定する。 +TaskManager は Persistent Data Tree を監視し、Task の依存関係を解決する。

+ + +
+
+ +

Cerium の構成

+ + +

Worker は ActiveTaskQueue から Task を取得する。 +取得した Task の情報を元に必要な Data Gear を Persistent Data Tree から取得し、Code Gear を実行する。 +実行後、必要なデータを Persistent Data Tree に書き出し次の Task を取得する。

+ +

Gears OS の構成

+
diff -r 0188222d2886 -r 4dcfec1bf1e7 slide/index.md --- a/slide/index.md Wed Feb 17 20:29:45 2016 +0900 +++ b/slide/index.md Thu Feb 18 07:20:46 2016 +0900 @@ -21,22 +21,39 @@ ![Cerium の構成](./pictures/createTask.svg) -# Cerium の問題点(1/2) +# Cerium の問題点 +* Task 間の依存関係 + Cerium では Task 間の依存関係を設定することで並列処理を実現する。 しかし、本来 Task は必要なデータが揃うことで実行可能になるものである。 Task 同士の依存関係だけでは前の Task が不正な処理を行いデータがおかしくなっても Task の終了は通知され、そのまま処理が続行されてしまう。 データがどこでおかしくなったのか特定するのは難しく、デバックに時間が取られる。 -# Cerium の問題点(2/2) +* データの型情報 + Task は汎用ポインタでデータの受け渡しを行うのでそこで型情報が落ちる。 -Task 側で正しく型変換を行うことで正しい処理を行うことができるが、間違った型変換を行うとデータ構造を破壊する可能性がある。 +Task 側で正しく型変換を行うことで正しい処理を行うことができるが、誤った型変換を行うと未定義な動作となりデータ構造を破壊する可能性がある。 型システムによるプログラムの正しさを保証することもできず、型に基づく一連の不具合が起こる危険性がつきまとう。 +# Cerium の問題点 +* メモリ確保 + +Cerium の Allocator は Thread 間で共有されている。 +ある Thread がメモリを確保しようとすると他の Thread はその間メモリを確保することができない。 +これが並列度の低下に繋がり、処理速度が落ちる原因になる。 + +* オブジェクト指向と並列処理 + +同じ入力に対し、同じ入力を返すことが保証される参照透過な処理は並列化を行いやすい。 +一方、オブジェクト指向は保守性と再利用性を高めるためにカプセル化やポリモフィズムを重視する。 +オブジェクトの状態によって振る舞いが変わるため並列処理との相性が悪い。 + # Gears OS 本研究では Code Segment と Data Segment によって構成される Gears OS の設計・実装を行った。 -プログラムを Code/Data Segment で分割して記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。 -Gears OS の基本的な機能の実装には本研究室で開発している CbC(Continuation based C)を用いた。 +Code/Data Segment で分割して記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。 + +Gears OS の基本的な機能の実装には本研究室で開発している CbC(Continuation based C) を用いた。 # Code/Data Gear Gears OS ではプログラムの単位として Gear を用いる。 @@ -49,7 +66,47 @@ Data Gear はデータそのものを表す。 int や文字列などの Primitive Data Type を複数持つ構造体として定義する。 -Gear 特徴として +Gear 特徴として処理やデータの構造が Code/Data Gear に閉じていることにある。 +これにより実行時間、メモリ使用量などを予測可能なものにする。 + +# Gears OS の構成 +* Context + +接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、独立したメモリ空間を持っている。 +複数の Context で TaskQueue と Persistent Data Tree は共有される。 + +* TaskQueue + +ActiveTaskQueue と WaitTaskQueue の2種類の TaskQueue がある。 +ActiveTaskQueue には実行可能な Task が挿入され、WaitTaskQueue には依存関係が解決されていない Task が挿入される。 +先頭と末尾の Element へのポインタを持つ Data Gear と Task へのポインタと次の Element へのポインタを持つ Data Gear で構成される。 +Compare and Swap(CAS) を利用することでスレッドセーフに Queue を操作することができる。 + +# Gears OS の構成 +* Persistent Data Tree + +Data Gear の管理を行う。 +非破壊木構造で構成されるため読み書きを平行して行うことができる。 +Red-Black Tree アルゴリズムを用いて平衡性を保ち、挿入・削除・検索における計算量を保証する。 +Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。 + +* TaskManager + +Gears OS における Task は実行する Code Gear と Input/Output Data Gear の組で表現される。 +Input/Output Data Gear から依存関係を決定する。 +TaskManager は Persistent Data Tree を監視し、Task の依存関係を解決する。 + +# Gears OS の構成 +* Worker + +Worker は ActiveTaskQueue から Task を取得する。 +取得した Task の情報を元に必要な Data Gear を Persistent Data Tree から取得し、Code Gear を実行する。 +実行後、必要なデータを Persistent Data Tree に書き出し次の Task を取得する。 + +![Gears OS の構成](./pictures/gearsos.svg) + +# Allocator + # 測定結果 * OS X(10.10.5) diff -r 0188222d2886 -r 4dcfec1bf1e7 slide/pictures/gearsos.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/pictures/gearsos.svg Thu Feb 18 07:20:46 2016 +0900 @@ -0,0 +1,430 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +