Mercurial > hg > Papers > 2016 > masa-master
changeset 6:7a67daa0d39f
add createTask images
| author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 11 Jan 2016 11:39:37 +0900 |
| parents | 515e18cdb197 |
| children | 16d34f730a6d |
| files | cerium.tex images/createTask.pdf master_paper.bib master_paper.pdf master_paper.tex paper.mm |
| diffstat | 6 files changed, 172 insertions(+), 13 deletions(-) [+] |
line wrap: on
line diff
--- a/cerium.tex Sat Jan 09 21:07:11 2016 +0900 +++ b/cerium.tex Mon Jan 11 11:39:37 2016 +0900 @@ -1,5 +1,149 @@ \chapter{Cerium} +Cerium は、Cell 向けに開発された並列プログラミングフレームワークである。 +Cell は Sony Computer Entertainment 社が販売した PlayStation3 に搭載されているヘテロジニアスマルチコア・プロセッサである。 +本章では Cerium の実装について説明する。 + \section{Cerium の概要} +Cerium は当初 Cell 向けに開発され、C/C++ で実装されている。 +現在では Linux、 MacOS X 上で動作する並列プログラミングフレームワークである。 + +Cerium は TaskManager、SceneGraph、Rendering Engine の3要素から構成されている。 +本研究では汎用計算フレームワークである TaskManager を利用して文字列の並列計算を行なった。 + +図\ref{fig:TaskManager}は Cerium が Task の生成/実行する場合のクラス構成図である。 +TaskManager で依存関係が解消され、実行可能になった Task は ActiveTaskList に格納される。 +ActiveTaskList に格納された Task は、依存関係が解消されているのでどのような順番で実行されても問題はない。 +Task は転送を行いやすい TaskList に変換され、CpuType に対応した Scheduler に転送される。 +なお、転送はSynchronozed Queue である mail を通して行われる。 + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.7]{images/createTask.pdf} + \end{center} + \caption{Task Manager} + \label{fig:TaskManager} +\end{figure} + +\newpage + \section{Cerium TaskManager} -\section{Cerium における Task} -\section{並列 I/O} +Cerium TaskManager では、処理の単位を Task として記述していく。 +関数やサブルーチンを Task として取り扱い、その Task にて Input Data/Output Data 及び Task の依存関係を設定する。 +そして Task は設定された依存関係を考慮しながら実行される。 + +Input Data で格納した 2 つの数を乗算し、Output Data に演算結果を格納する multiply という例題のソースコード\ref{src:createTask}を以下に示す。 + +また、Task の生成時に用いる API 一覧を表\ref{table:TaskCreateAPI}に示す。 +\begin{lstlisting}[frame=lrbt,label=src:createTask,caption=Task の生成,numbers=left] +multi_init(TaskManager *manager) +{ + float *A, *B, *C; + + // create Task + HTaskPtr multiply = manager->create_task(MULTIPLY_TASK); + + // set device + multiply->set_cpu(SPE_ANY); + + // set inData + multiply->set_inData(0, (memaddr)A, sizeof(float)*length); + multiply->set_inData(1, (memaddr)B, sizeof(float)*length); + + // set outData + multiply->set_outData(0, (memaddr)C, sizeof(float)*length); + + // set parameter + multiply->set_param(0,(long)length); + + // spawn task + multiply->spawn(); +} +\end{lstlisting} + +\begin{tiny} + \begin{table}[ht] + \begin{center} + \label{table:TaskCreateAPI} + \small + \begin{tabular}[t]{c|l} + \hline + create\_task& Task を生成する \\ + \hline + set\_inData & Task への入力データのアドレスを追加 \\ + \hline + set\_outData & Task への出力データのアドレスを追加 \\ + \hline + set\_param & Task へ値を一つ渡す。ここでは length \\ + \hline + set\_cpu & Task を実行するデバイスの設定 \\ + \hline + spawn & 生成した Task を TaskList に set \\ + \hline + \end{tabular} + \caption{Task 生成における API} + \end{center} + \end{table} +\end{tiny} + +次に、デバイス側で実行される Task のソースコードを\ref{src:task}に示す。 +\begin{lstlisting}[frame=lrbt,label=src:task,caption=Task,numbers=left] +static int +run(SchedTask *s) { + // get input + float *i_data1 = (float*)s->get_input(0); + float *i_data2 = (float*)s->get_input(1); + + // get output + float *o_data = (float*)s->get_output(0); + + // get parameter + long length = (long)s->get_param(0); + + // calculate + for (int i=0; i<length; i++) { + o_data[i] = i_data1[i] * i_data2[i]; + } + return 0; +} +\end{lstlisting} +また表\ref{table:taskAPI}は Task 側で利用する API である。 +Task 生成時に設定した Input Data や parameter を取得することができる。 + +\begin{tiny} + \begin{table}[ht] + \begin{center} + \caption{Task 側で使用する API} + \label{table:taskAPI} + \small + \begin{tabular}[t]{c|l} + \hline + get\_input & Scheduler から input data を取得 \\ + \hline + get\_output & Scheduler から output data を取得 \\ + \hline + get\_param & set\_param した値を取得 \\ + \hline + \end{tabular} + \end{center} + \end{table} +\end{tiny} + +Task 生成時に設定できる要素を以下に列挙する。 + +\begin{itemize} +\item Input Data +\item Output Data +\item Parameter +\item CpuType +\item Dependency +\end{itemize} + +Input/Output Data、Parameter は関数の引数に相当する。 +Cpu Type は Task を動作させるデバイスを設定することができ、Dependency は他の Task との依存関係を設定することができる。 + +\section{並列処理向け I/O} +ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。 +計算処理の並列化を図ったとしても I/O がボトルネックになってしまい処理全体が高速にならない。 +本項では Cerium に実装した並列処理用 I/O を行ない、I/O 部分の高速化を図った。 + +Cerium の例題ではファイル読み込みを mmap にて実装していた。しかし、mmap だとファイルを読み込んでから Task を実行するので、読み込んでいる間は他の CPU が動作せず並列度が落ちる。そこで、I/O 部分も Task と並列に動作するように実装した。
--- a/master_paper.bib Sat Jan 09 21:07:11 2016 +0900 +++ b/master_paper.bib Mon Jan 11 11:39:37 2016 +0900 @@ -1,5 +1,19 @@ -@article{ - prosym_shinya, +@article{ yutaka:2012a, + author = "金城 裕", + title = "並列プログラミングフレームワーク Cerium の改良", + journal = "琉球大学工学部情報工学科平成 24 年度学位論文 (修士)", + month = "March", + year = 2012 +} + +@article{yuhi:2015, + author = "渡真利 勇飛", + title = "マルチプラットフォーム対応並列プログラミングフレームワーク", + journal = "琉球大学大学院理工学研究科情報工学専攻平成 26 年度学位論文(修士)", + year = 2013 +} + +@article{ prosym_shinya, author = "新屋 良磨,河野 真治", title = "動的なコード生成を用いた正規表現マッチャの実装", journal = "第52回プログラミング・シンポジウム", @@ -7,22 +21,19 @@ year = 2011 } -@manual{ - regex, +@manual{ regex, author = "{新屋 良磨,鈴木 勇介,高田 謙}", title ="{正規表現技術入門(技術論評社)}", year = 2015 } -@manual{ - automaton, +@manual{ automaton, author = "{Michael Sipser 著,太田 和夫・田中圭介監訳}", title ="{計算理論の基礎[原著第2版]1.オートマトンと言語}", year = 2008 } -@misc{ - cuda, +@misc{ cuda, title = "{Regular Expression Matching Can Be Simple And Fast}", howpublished = "{https://swtch.com/~rsc/regexp/regexp1.html}", year = 2007
--- a/master_paper.tex Sat Jan 09 21:07:11 2016 +0900 +++ b/master_paper.tex Mon Jan 11 11:39:37 2016 +0900 @@ -8,6 +8,7 @@ %\input{dummy.tex} %% font \jtitle{タイトル} +%\etitle{Title} \etitle{Title} \year{平成27年度 3月} \affiliation{\center% @@ -76,6 +77,7 @@ \listoftables %chapters +\pagenumbering{arabic} \input{parallelregex.tex} \input{cerium.tex} \input{ceriumex.tex}
--- a/paper.mm Sat Jan 09 21:07:11 2016 +0900 +++ b/paper.mm Mon Jan 11 11:39:37 2016 +0900 @@ -14,11 +14,13 @@ </node> <node CREATED="1452181112982" ID="ID_1013019132" MODIFIED="1452181116028" POSITION="right" TEXT="オートマトン"> <node CREATED="1452181291030" ID="ID_1662130081" MODIFIED="1452181296262" TEXT="オートマトンの定義"/> -<node CREATED="1452181307382" ID="ID_1297043172" MODIFIED="1452182066253" TEXT="非決定性オートマトン"/> -<node CREATED="1452181296911" ID="ID_1408502412" MODIFIED="1452181306606" TEXT="決定性オートマトン"/> +<node CREATED="1452181296911" ID="ID_1408502412" MODIFIED="1452342238765" TEXT="決定性オートマトン(DFA)"/> +<node CREATED="1452181307382" ID="ID_1297043172" MODIFIED="1452342244291" TEXT="非決定性オートマトン(NFA)"/> <node CREATED="1452182067881" ID="ID_1018839282" MODIFIED="1452182079360" TEXT="SubSetConstruction"/> </node> -<node CREATED="1452181243745" ID="ID_1618298196" MODIFIED="1452332172946" POSITION="right" TEXT="正規表現"/> +<node CREATED="1452181243745" ID="ID_1618298196" MODIFIED="1452332172946" POSITION="right" TEXT="正規表現"> +<node CREATED="1452342247862" ID="ID_1920433578" MODIFIED="1452342261149" TEXT="正規表現からNFAへの変換"/> +</node> <node CREATED="1452175345187" ID="ID_741844249" MODIFIED="1452175358409" POSITION="right" TEXT="ベンチマーク"/> <node CREATED="1452175359089" ID="ID_222666554" MODIFIED="1452175361600" POSITION="right" TEXT="結論"/> <node CREATED="1452176703234" ID="ID_214726388" MODIFIED="1452176706578" POSITION="left" TEXT="Cerium">