# HG changeset patch # User Shohei KOKUBO # Date 1455660158 -32400 # Node ID 205805e6a6d82bc621d21de1203890315e9dc5cf # Parent a6188b7c727893ca635237b5a63c784fb6295870 revision diff -r a6188b7c7278 -r 205805e6a6d8 abstract_eng.tex --- a/abstract_eng.tex Tue Feb 16 18:16:04 2016 +0900 +++ b/abstract_eng.tex Wed Feb 17 07:02:38 2016 +0900 @@ -1,2 +1,7 @@ \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. + Parallelism in a high performance Gears OS with Code/Data Segment. + We show same implementation of Gears OS using CbC(Continuation based C). \end{abstract_eng} diff -r a6188b7c7278 -r 205805e6a6d8 cbc.tex --- a/cbc.tex Tue Feb 16 18:16:04 2016 +0900 +++ b/cbc.tex Wed Feb 17 07:02:38 2016 +0900 @@ -1,12 +1,15 @@ \chapter{CbC} +Gears OS の実装には LLVM/Clang 上に実装した CbC を用いる。 + CbC は C から for 文、while 文といったループ制御構文や関数呼び出しを取り除き、Code Segment と goto による軽量継続を導入している。 図:\ref{fig:cs} は goto による Code Segment の遷移を表したものである。 -Gears OS の実装には LLVM/Clang 上に実装した CbC を用いる。 +本章では CbC の特徴である Code Segment と Gears OS に対するサポートについて説明する。 + \begin{figure}[!h] \begin{center} - \includegraphics[scale=0.7]{./images/codesegment2.pdf} + \includegraphics[scale=0.6]{./images/codesegment2.pdf} \end{center} \caption{goto による Code Segment 間の継続} \label{fig:cs} diff -r a6188b7c7278 -r 205805e6a6d8 cerium.tex --- a/cerium.tex Tue Feb 16 18:16:04 2016 +0900 +++ b/cerium.tex Wed Feb 17 07:02:38 2016 +0900 @@ -448,7 +448,7 @@ 1 CPU に対して 12 CPU では約5.2倍、GPU では約4.7倍の速度向上が見られる。 ある程度の速度向上が見られたが、CPU に劣る結果となった。 -データ転送の最適化が十分になされていない可能性があるので、GPU の実行機構を見直す必要がある。 +データ転送の最適化が十分に成されていない可能性があるので、GPU の実行機構を見直す必要がある。 \section{Cerium の問題点} Cerium では Task 間の依存関係を記述することで並列処理を実現する。 diff -r a6188b7c7278 -r 205805e6a6d8 comparison.tex --- a/comparison.tex Tue Feb 16 18:16:04 2016 +0900 +++ b/comparison.tex Wed Feb 17 07:02:38 2016 +0900 @@ -1,5 +1,5 @@ \chapter{比較} -この章では今回設計・実装した Gears OS と既存の並列フレームワークとの比較を行う。 +本章では今回設計・実装した Gears OS と既存の並列フレームワークとの比較を行う。 また、Gears OS は以下のような性質を有している。 \begin{itemize} diff -r a6188b7c7278 -r 205805e6a6d8 conclusion.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/conclusion.tex Wed Feb 17 07:02:38 2016 +0900 @@ -0,0 +1,50 @@ +\chapter{結論} +先行研究である Cerium の開発を通して得られた知見を元に Code Segment, Data Segment によって構成される Gears OS の設計・実装を行なった。 +実装には本研究室で開発している CbC(Continuation based C)を用いた。 + +Code Segment は処理、Data Segment はデータの単位である。 +Code Segment は戻り値を持たないので、関数呼び出しのようにスタックに値を積む必要がなくスタックは変更されない。 +このようなスタックに積まない継続を軽量継続と呼び、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行える。 +プログラムを Code/Data Segment で分割して記述することで並列度を高めることができる。 + +Gears OS を Code/Data Segment の考えに基づいて設計を行なった。 +Gears OS には Code/Data Segment と同等なものとして Code/Data Gear を定義した。 +Code Gear はプログラムの処理そのもので、Data Gear は int や文字列などの Primitive Data Type を複数持っている構造体として表現する。 +Code Gear は任意の数の Data Gear を参照し、任意の数の Data Gear に書き込みを行う。 +Gear の特徴として処理やデータ構造が Code/Data Gear に閉じている。 +これにより実行時間、メモリ使用量などを予測可能なものにする。 + +Gears OS の基本的な機能として Allocator, TaskQueue, Persistent Data Tree, Worker の実装を行なった。 +Gears OS では Context に情報が格納される。 +格納される情報には接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Data Gear を確保するためのメモリ空間などがある。 +Context はスレッドごとに存在し、それぞれが異なる Context を参照している。 +Allocator は Context が持っているメモリ空間のアドレスを変更し、Temporal Data Gear の確保を行う。 +確保される Data Gear は処理後には必要なくなるものなのでリニアに確保するだけの単純な処理である。 +TaskQueue は並列処理される Task を管理する。 +Gears OS で Task は実行する Code Gear と実行に必要な Data Gear の組で表現する。 +TaskQueue はすべての Context で共有され、マルチスレッドでデータの一貫性を保つために Compare and Swap(CAS) を用いた。 +Persistent Data Tree は Data Gear を管理する。 +非破壊木構造で構成され、Red-Black Tree アルゴリズムによって平衡性が保たれる。 +Persistent Data Tree はすべての Context で共有される。 +非破壊木構造なので読み書きを平行して行うことができる。 +Gears OS では Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。 +Worker は Task を並列処理する。 +個別の Context を参照しているので、メモリ空間が独立しておりメモリを確保する処理で他の Worker を止めることはない。 +CAS を用いて TaskQueue にアクセスし、Task を取得する。 +取得した Task の情報を元に Persistent Data Tree から Data Gear を取得し、Code Gear を実行する。 +また、Gears OS 自体が Code/Data Segment を用いたプログラミングの指針となるように実装を行った。 + +Gears OS を用いて簡単な例題を実装し、評価を行った。 +与えられた要素を2倍にする Twice という依存関係がない並列処理の例題を Gears OS 上に実装した。 +1 CPU と 12 CPU で約11.8倍の速度向上を確認し、Gears OS を用いることで十分な並列処理性能を引き出せることを示した。 + +\section{今後の課題} +例題として Twice を用いて並列処理の性能を示したが、Twice は依存関係がない並列処理である。 +本来、並列処理には依存関係が存在する。 +複雑な並列処理を行えるようにするために依存関係を解決する TaskManager の実装が必要である。 + +Gears OS 上でマルチコア CPU を用いた実行を可能にしたが、GPU などの他のプロセッサを演算に用いることができない。 +Code/Data Segment を用いて各プロセッサのアーキテクチャにマッピングした実行機構を実装し、演算に利用できるようにする必要がある。 + +型情報を残すために Data Segment を定義しているが Data Segment の型情報を検査していない。 +プログラムの正しさを保証するために Data Segment の型情報を検査する型システムを Gears OS 上に実装する必要がある。 diff -r a6188b7c7278 -r 205805e6a6d8 evaluation.tex --- a/evaluation.tex Tue Feb 16 18:16:04 2016 +0900 +++ b/evaluation.tex Wed Feb 17 07:02:38 2016 +0900 @@ -2,7 +2,7 @@ 現在の Gears OS には非破壊木構造を Red-Black Tree アルゴリズムに基づいて構築する Persistent Data Tree, CAS を用いてデータの一貫性を保証する TaskQueue, TaskQueue から Task を取得し並列に実行する Worker が実装されている。 つまり、依存関係のない処理ならば並列処理することが可能である。 -この章では依存関係のない簡単な例題を用いて Gears OS の評価を行う。 +本章では依存関係のない簡単な例題を用いて Gears OS の評価を行う。 \section{Twice} Twice は与えられた整数配列を2倍にする例題である。 @@ -25,30 +25,6 @@ Gears OS 上に Twice を実装し、要素数$2^{17}$*1000 のデータを640個の Task に分割してコア数を変更して測定を行なった。 結果は表:\ref{table:twice}, 図:\ref{fig:twice}の通りである。 -%% \begin{table}[!h] -%% \begin{center} -%% \small -%% \begin{tabular}[htpb]{|c||c|c|c|} -%% \hline -%% Processor & 64 Tasks(ms) & 640 Tasks(ms) & 6400 Tasks(ms) \\ -%% \hline -%% \hline -%% 1 CPU & 1245 & 1315 & 1973 \\ -%% \hline -%% 2 CPUs & 629 & 689 & 1118 \\ -%% \hline -%% 4 CPUs & 326 & 366 & 610 \\ -%% \hline -%% 8 CPUs & 165 & 189 & 327 \\ -%% \hline -%% 12 CPUs & 121 & 111 & 114 \\ -%% \hline -%% \end{tabular} -%% \caption{要素数$2^{17}$*1000 のデータに対する Twice} -%% \label{table:twice} -%% \end{center} -%% \end{table} - \begin{table}[!h] \begin{center} \small @@ -81,3 +57,11 @@ \label{fig:twice} \end{figure} +1 CPU と 12 CPU では約11.8倍の速度向上が見られた。 +十分な台数効果が出ていることがわかる。 +しかし、タスクの粒度が小さすぎると CAS の失敗が多くなり性能が出ないことがある。 +Code Gear には実行時間を予測可能なものにするという特徴があるので、その性質を利用してタスクが最適な粒度なのか検査する機能が必要になると考えられる。 + +今回、例題に用いた Twice は依存関係のない並列処理である。 +本来、並列処理には複雑な依存関係が存在するのが一般的である。 +並列フレームワークには複雑な依存関係を解決しながら十分な並列度を保てることが必須なので依存関係を解決するための TaskManager の実装が必要である。 diff -r a6188b7c7278 -r 205805e6a6d8 gearsos.tex --- a/gearsos.tex Tue Feb 16 18:16:04 2016 +0900 +++ b/gearsos.tex Wed Feb 17 07:02:38 2016 +0900 @@ -9,7 +9,7 @@ Code Gear はプログラムの処理そのものになる。 これは OpenCL/CUDA の kernel, Cerium の Task に相当する。 -Code Gear は任意の数の Data Gear を参照し、処理が完了すると 任意の数の Data Gear に書き込む。 +Code Gear は任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込む。 Code Gear は接続された Data Gear 以外にアクセスできない。 Code Gear から次の Code Gear への処理の移動は goto の後に Code Gear の名前と引数を指定することで実現できる。 Code Gear は Code Segment そのものである。 diff -r a6188b7c7278 -r 205805e6a6d8 intro.tex --- a/intro.tex Tue Feb 16 18:16:04 2016 +0900 +++ b/intro.tex Wed Feb 17 07:02:38 2016 +0900 @@ -1,1 +1,26 @@ -\chapter{並列分散環境下におけるプログラミング} +\chapter{並列環境下におけるプログラミング} +CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている。 +そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある。 +マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない。 +これはアムダールの法則により、並列化できない部分が並列化による性能向上を制限することから言える。 +つまり、プログラムを並列処理に適した形で記述するためのフレームワークが必要になる。 +また、PC の処理性能を上げるためにマルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している。 +並列処理をする上でこれらのリソースを無視することができない。 +しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる。 +並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる。 + +Cerium は本論文で開発している並列プログラミングフレームワークである。 +Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする。 +Cerium では依存関係を 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 の組で表現される。 +Input/Output Data Segment によって依存関係が決定し、それに沿って並列実行する。 +本論文では基本的な機能として Data Gear を管理する Persistent Data Tree, Task を管理する TaskQueue, 並列処理を行う Worker を実装し、簡単な例題を用いて Gears OS の評価を行う。 diff -r a6188b7c7278 -r 205805e6a6d8 master_paper.pdf Binary file master_paper.pdf has changed diff -r a6188b7c7278 -r 205805e6a6d8 master_paper.tex --- a/master_paper.tex Tue Feb 16 18:16:04 2016 +0900 +++ b/master_paper.tex Wed Feb 17 07:02:38 2016 +0900 @@ -90,7 +90,7 @@ \input{gearsos.tex} \input{comparison.tex} \input{evaluation.tex} -\chapter{結論} +\input{conclusion.tex} %謝辞 \addcontentsline{toc}{chapter}{謝辞}