# HG changeset patch # User Shohei KOKUBO # Date 1454959294 -32400 # Node ID 52eec0b775762a37152be558dcf9b4c14365d56c # Parent 0fa000320b6aa381bb8c2ceda06b339d467babad Gears OS: allocate diff -r 0fa000320b6a -r 52eec0b77576 gearsos.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gearsos.tex Tue Feb 09 04:21:34 2016 +0900 @@ -0,0 +1,102 @@ +\chapter{Gears OS} +Cerium と Alice の開発を通して得られた知見から並列分散処理には Code の分割だけではなく Data の分割も必要であることがわかった。 +当研究室で開発している Code Segment を基本的な処理単位とするプログラミング言語 Continuation based C(CbC) を用いて Data Segment を定義し、Gears OS の設計と基本的な機能の実装を行なった。 + +本章では Gears OS の設計と実装した基本的な機能について説明する。 +\section{Code Gear と Data Gear} +Gears OS ではプログラムの単位として Gear を用いる。 +Gear は並列実行の単位、データの分割、Gear 間の接続等になる。 + +Code Gear はプログラムの処理そのものになる。 +これは OpenCL/CUDA の kernel, Cerium の Task に相当する。 +Code Gear は任意の数の Data Gear を参照し、処理が完了すると 任意の数の Data Gear に書き込む。 +Code Gear は接続された Data Gear 以外にアクセスできない。 +Code Gear から次の Code Gear への処理の移動は goto の後に Code Gear の名前と引数を指定することで実現できる。 +Code Gear は Code Segment そのものである。 + +Data Gear はデータそのものを表す。 +int や文字列などの Primitive Data Type を持っている。 + +Gear の特徴として処理やデータの構造が Code Gear, Data Gear に閉じていることにある。 +これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。 + +\section{Gears OS の構成} +Gears OS は以下の要素で構成される。 +\begin{itemize} +\item Context \\ + 接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Data Gear のためのメモリ空間等を持っており、Context を通してアクセスすることができる。 + メインとなる Context と Worker 用の Context があり、TaskQueue と Persistent Data Tree は共有される。 + Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。 + Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。 +\item TaskQueue \\ + ActiveTaskQueue と WaitTaskQueue の2つの TaskQueue を持つ。 + 先頭と末尾の Element へのポインタを持つ Queue を表す Data Gear である。 + Element は Task を表す Data Gear へのポインタと次の Element へのポインタを持っている。 + Compare and Swap(CAS) を使ってアクセスすることでスレッドセーフな Queue として利用することが可能になる。 +\item TaskManager \\ + Task には Input Data Gear, Output Data Gear が存在する。 + Input/Output Data Gear から依存関係を決定し、TaskManager が解決する。 + 依存関係が解決された Task は WaitTaskQueue から ActiveTaskQueue に移される。 + TaskManager はメインとなる Context を参照する。 +\item Persistent Data Tree \\ + 非破壊木構造で構成された Lock-free なデータストアである。 + Red-Black Tree として構成することで最悪な場合の挿入・削除・検索の計算量を保証する。 +\item Worker \\ + TaskQueue から Task の取得・実行を行う。 + Task の処理に必要なデータは Persistent Data Tree から取得する。 + 処理後、必要なデータを Persistent Data Tree に書き出して再び Task の取得・実行を行う。 +\end{itemize} + +図:\ref{fig:gearsos} は Gears OS の構成図である。 + +\begin{figure}[!ht] + \begin{center} + \includegraphics[scale=0.35]{./images/gearsos.pdf} + \end{center} + \caption{Gears OS} + \label{fig:gearsos} +\end{figure} + +\newpage + +\section{Allocator} +Gears OS では Context の生成時にある程度の大きさのメモリ領域を確保する。 +Context には確保したメモリ領域を指す情報が格納される。 +このメモリ領域を利用して Task の実行に必要な Data Gear を生成する。 + +Context の定義と生成はソースコード:\ref{context},ソースコード:\ref{initcontext} の通りである。 + +\lstinputlisting[label=context, caption=Context]{src/context.h} +\lstinputlisting[label=initcontext, caption=initContext]{src/initContext.c} + +Context はヒープサイズを示す heap\_limit, ヒープの初期位置を示す heap\_start, ヒープの現在位置を示す heap を持っている。 +必要な Data Gear のサイズに応じて heap の位置を動かすことで Allocation を実現する。 + +allocate を行うには allocate に必要な Data Gear に情報を書き込む必要がある。 +この Data Gear は Context 生成時に生成する必要がある。 + +Temporal Data Gear にある Data Gear は基本的には破棄可能なものなので heap\_limit を超えたら heap を heap\_start の位置に戻し、ヒープ領域を再利用する(図:\ref{fig:allocation})。 +必要な Data Gear は Persistent Data Tree に書き出すことで他の Worker からアクセスすることが可能になる。 + +\begin{figure}[!ht] + \begin{center} + \includegraphics[scale=0.4]{./images/allocation.pdf} + \end{center} + \caption{Allocation} + \label{fig:allocation} +\end{figure} + +実際に allocate を行うコードはソースコード:\ref{allocate} の通りである。 + +Context 生成時に実行可能な Code Gear と名前が対応付けられる。 +その対応付けられた Code Gear が Context の code に格納される。 +この code を介して遷移先の Code Gear を決定する。 + +Code Gear には Context が接続されるが Context を介して Data Gear にアクセスすることはない。 +stub を介して間接的に必要な Data Gear にアクセスする。 + +\lstinputlisting[label=allocate, caption=allocate]{src/allocate.c} + +\section{List} +\section{Synchronized Queue} +\section{Red-Black Tree} diff -r 0fa000320b6a -r 52eec0b77576 images/allocation.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/allocation.bb Tue Feb 09 04:21:34 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: ./images/allocation.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 1064 396 +%%CreationDate: Tue Feb 9 03:13:52 2016 + diff -r 0fa000320b6a -r 52eec0b77576 images/allocation.pdf Binary file images/allocation.pdf has changed diff -r 0fa000320b6a -r 52eec0b77576 images/gearsos.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/gearsos.bb Tue Feb 09 04:21:34 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: ./images/gearsos.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 1312 427 +%%CreationDate: Tue Feb 9 03:18:30 2016 + diff -r 0fa000320b6a -r 52eec0b77576 images/gearsos.pdf Binary file images/gearsos.pdf has changed diff -r 0fa000320b6a -r 52eec0b77576 images/images.graffle Binary file images/images.graffle has changed diff -r 0fa000320b6a -r 52eec0b77576 master_paper.tex --- a/master_paper.tex Fri Feb 05 04:17:47 2016 +0900 +++ b/master_paper.tex Tue Feb 09 04:21:34 2016 +0900 @@ -49,8 +49,9 @@ aboveskip=1zw, numberstyle={\scriptsize},% stepnumber=1, - numbersep=1zw,% - lineskip=-0.5ex% + numbersep=0.5zw,% + lineskip=-0.5ex, + numbers=left } %%% 索引のために以下の2行を追加 @@ -84,27 +85,7 @@ \chapter{並列分散環境下におけるプログラミング} \input{cerium.tex} \chapter{CbC} -\chapter{GearsOS} -Cerium と Alice の開発を通して得られた知見から並列分散処理には Code の分割だけではなく Data の分割も必要であることがわかった。 -当研究室で開発している Code Segment を基本的な処理単位とするプログラミング言語 Continuation based C(CbC) を用いて Data Segment を定義し、Gears OS の設計と基本的な機能の実装を行なった。 - -本章では Gears OS の設計と実装した基本的な機能について説明する。 -\section{Code Gear と Data Gear} -Gears OS ではプログラムの単位として Gear を用いる。 -Gear は並列実行の単位、データの分割、Gear 間の接続等になる。 - -Code Gear はプログラムの処理そのものになる。 -これは OpenCL/CUDA の kernel, Cerium の Task に相当する。 -Code Gear は任意の数の Data Gear を参照し、処理が完了すると 任意の数の Data Gear に書き込む。 -Code Gear は接続された Data Gear 以外にアクセスできない。 - -\section{GearsOS の構成} -Gears OS は -\section{Allocator} -\section{List} -\section{Synchronized Queue} -\section{Red-Black Tree} - +\input{gearsos.tex} \chapter{比較} \section{Cerium} \section{従来の OS} diff -r 0fa000320b6a -r 52eec0b77576 src/allocate.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/allocate.c Tue Feb 09 04:21:34 2016 +0900 @@ -0,0 +1,47 @@ +// Code Gear +__code start_code(struct Context* context) { + // start processing + goto meta(context, context->next); +} + +// Meta Code Gear +__code meta(struct Context* context, enum Code next) { + // meta computation + goto (context->code[next])(context); +} + +// Code Gear +__code code1(struct Context* context, struct Allocate* allocate) { + allocate->size = sizeof(struct Data1); + context->next = Code2; + + goto meta(context, Allocator); +} + +// Meta Code Gear(stub) +__code code1_stub(struct Context* context) { + goto code1(context, &context->data[Allocate]->allocate); +} + +// Meta Code Gear +__code allocator(struct Context* context, struct Allocate* allocate) { + context->data[++context->dataNum] = context->heap; + context->heap += allocate->size; + + goto meta(context, context->next); +} + +// Meta Code Gear(stub) +__code allocator_stub(struct Context* context) { + goto allocator(context, &context->data[Allocate]->allcate); +} + +// Code Gear +__code code2(struct Context* context, struct Data1* data1) { + // processing +} + +// Meta Code Gear(stub) +__code code2_stub(struct Context* context) { + goto code2(context, &context->data[context->dataNum]->data1); +} diff -r 0fa000320b6a -r 52eec0b77576 src/context.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/context.h Tue Feb 09 04:21:34 2016 +0900 @@ -0,0 +1,37 @@ +/* Context definition example */ +#define ALLOCATE_SIZE 1000 + +enum Code { + Code1, + Code2, + Allocator, + Exit, +}; + +enum UniqueData { + Allocate, +}; + +struct Context { + enum Code next; + int codeNum; + __code (**code) (struct Context*); + void* heapStart; + void* heap; + long heapLimit; + int dataNum; + union Data **data; +}; + +union Data { + struct Data1 { + int i; + } data1; + struct Data2 { + int i; + char c; + } data2; + struct Allocate { + long size; + } allocate; +}; diff -r 0fa000320b6a -r 52eec0b77576 src/initContext.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/initContext.c Tue Feb 09 04:21:34 2016 +0900 @@ -0,0 +1,28 @@ +#include + +#include "context.h" + +extern __code code1_stub(struct Context*); +extern __code code2_stub(struct Context*); +extern __code allocator_stub(struct Context*); +extern __code exit_code(struct Context*); + +__code initContext(struct Context* context, int num) { + context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE; + context->heapStart = malloc(context->heapLimit); + context->heap = context->heapStart; + context->codeNum = Exit; + + context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE); + context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE); + + context->code[Code1] = code1_stub; + context->code[Code2] = code2_stub; + context->code[Allocator] = allocator_stub; + context->code[Exit] = exit_code; + + context->data[Allocate] = context->heap; + context->heap += sizeof(struct Allocate); + + context->dataNum = Allocate; +}