Mercurial > hg > Papers > 2016 > masa-master
changeset 23:1803c5766d06
c3 finish
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 05 Feb 2016 01:20:20 +0900 |
parents | b11c33acd891 |
children | beadec12c1e7 |
files | c3.tex c4.tex |
diffstat | 2 files changed, 51 insertions(+), 22 deletions(-) [+] |
line wrap: on
line diff
--- a/c3.tex Thu Feb 04 20:55:30 2016 +0900 +++ b/c3.tex Fri Feb 05 01:20:20 2016 +0900 @@ -1,15 +1,17 @@ \chapter{並列処理向け I/O} -\section{mmap} -\section{Blocked Read} -ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。 +ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較して大きくなることが多い。 計算処理の並列化を図ったとしても I/O がボトルネックになってしまい処理全体が高速にならない。 -本項では Cerium に実装した並列処理用 I/O を行ない、I/O 部分の高速化を図った。 +従来の例題のファイル読み込み部分では mmap を利用していたが、読み込みと Task が並列に動くような実装を行ない、プログラム全体の高速化を図った。 +本項では mmap による読み込みと、今回実装した並列処理向け I/O について述べる。 + +\section{mmap} Cerium の例題ではファイル読み込みを mmap にて実装していた。 -しかし、mmap だとファイルを読み込んでから Task を実行するので、読み込んでいる間は他の CPU が動作せず並列度が落ちる。 + +mmap は function call 後にすぐにファイルを読みに行くのではなく、仮想メモリ領域にファイルの中身を対応させ、 その後メモリ空間にアクセスされたときに、OS が対応したファイルを読み込む。 -mmap は function call 後にすぐにファイルを読みに行くのではなく、仮想メモリ領域にファイルの中身を対応させる。 -その後メモリ空間にアクセスされたときに、OS が対応したファイルを読み込む。 +そのため、mmap によるファイルを読み込みは読み込み後に Task を実行するので、その間は他の CPU が動作せず並列度が落ちる。 + また、読み込む方法が OS 依存となってしまうため環境に左右されやすく、プログラムの書き手が読み込みの制御をすることが難しい。 図\ref{fig:mmap}は mmap で読み込んだファイルに対して Task1 、 Task2 がアクセスしてそれぞれの処理を行うときのモデルである。 @@ -25,13 +27,15 @@ \label{fig:mmap} \end{figure} -mmap を使わず、読み込みを独立した Thread で行ない、ファイルを一度に全て読み込むのではなくある程度の大きさ(Block)分読み込み、読み込まれた部分に対して並列に Task を起動する。 -これを Blocked Read と呼び、高速化を図った。 +\section{Blocked Read} +読み込みを独立した Thread で行ない、ファイルを一度に全て読み込むのではなくある程度の大きさ(Block)分読み込み、読み込まれた部分に対して並列に Task を起動する。 +これを Blocked Read と呼び、I/O の読み込みと Task の並列化を図った。 -Blocked Read を実装するにあたり、WordCount を例題に挙げる。 -ファイルを読み込む Task (以下、ReadTask) と、読み込んだファイルに対して計算を行う Task (以下、WordCount) を別々に生成する。ReadTask は一度にファイル全体を読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。分割して読み込んだ範囲に対して WordCount を行う。 +ファイルを読み込む Task (以下、Blocked Read) と、読み込んだファイルに対して計算を行う Task を別々に生成する。 +Blocked Read は一度にファイル全体を読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。 +分割して読み込んだ範囲に対して Task を実行する。 -WordCount を Blocked Read で読み込み処理をしたとき以下の図\ref{fig:BlockedRead}の様になる。 +ファイル読み込みを含むプログラムを Blocked Read で読み込み処理をしたとき以下の図\ref{fig:BlockedRead}の様になる。 \begin{figure}[htpb] \begin{center} @@ -41,13 +45,12 @@ \label{fig:BlockedRead} \end{figure} -Task を一定の単位でまとめた Task Block ごとに生成して WordCount を行なっている。 +Task を一定の単位でまとめた Task Block ごとに生成して Task を行なっている。 Task Block で計算される領域が Blocked Read で読み込む領域を追い越して実行してしまうと、まだ読み込まれていない領域に対して計算されてしまう。 その問題を解決するために依存関係を適切に設定する必要がある。 Blocked Read による読み込みが終わってから TaskBlock が起動されるようにするため、Cerium の API である wait\_for にて依存関係を設定する。 -また、ReadTask は連続で処理される必要がある。 -なぜならば、ReadTask でファイルを読み込む前提で WordCount がその領域に対して計算を行うので、ReadTask の処理が遅くなってしまうだけでオーバーヘッドとなってしまう。\ref{fig:BlockedReadModel} +(図\ref{fig:BlockedReadModel}) \begin{figure}[htpb] \begin{center} @@ -57,12 +60,15 @@ \label{fig:BlockedReadModel} \end{figure} -\newpage -Blocked Read を実装することにより、読み込み部分と処理部分の並列化を行なった。Blocked Read は連続で読み込まれる必要があるため、さらに I/O 専用 thread を実装した。 +\section{I/O 専用 thread の追加} + +Blocked Read は読み込みを含む処理なので、Task 1 つあたりの処理時間が大きくなる。 +Blocked Read がファイルを読み込む前提で Task がその領域に対して計算を行うので、ReadTask の処理によってプログラム全体の処理速度が左右されてしまう。 Cerium Task Manager では、それぞれの Task に対してデバイスを設定することができる。 SPE\_ANY 設定をすると、Task Manager が CPU の割り振りを自動的に行う。 -Blocked Read は連続で読み込まれなければならないが、SPE\_ANY で設定すると Blocked Read 間に別の Task が割り込まれる恐れがある。(図\ref{fig:spe_any_blockedread}) +しかし、自動的に割り振りを行なってしまうと、Blocked Read Task 間に Task が割り込まれてしまい、読み込みが遅延してしまう可能性がある。 +(図\ref{fig:spe_any_blockedread}) \begin{figure}[htpb] \begin{center} @@ -72,11 +78,12 @@ \label{fig:spe_any_blockedread} \end{figure} -Task が Blocked Read 間に割り込まれないようにするため、I/O 専用 thread である iO\_0 の設定を追加した。 +そこで、Task が Blocked Read Task 間に割り込まれないようにするため、I/O 専用 thread である iO\_0 の設定を追加した。 IO\_0 は SPE\_ANY とは別 thread の scheduler で動作するので、SPE\_ANY で動作している Task に割り込むことはない。 -しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事がある。 +しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事があるため、 pthread\_getschedparam() で IO\_0 の priority の設定を行う必要がある(図:\ref{fig:iothread_blockedread})。 + \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.7]{./images/cerium/iothread.pdf} @@ -84,5 +91,3 @@ \caption{IO Thread による BlockedRead} \label{fig:iothread_blockedread} \end{figure} - -IO\_0 で実行される Task は Blocked Read のみで、さらに IO\_0 の priority を高く設定することにより Blocked Read が他の Task に割り込まれることなく連続に実行される。
--- a/c4.tex Thu Feb 04 20:55:30 2016 +0900 +++ b/c4.tex Fri Feb 05 01:20:20 2016 +0900 @@ -106,3 +106,27 @@ \label{fig:nfa} \end{figure} +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/parser.pdf} + \end{center} + \caption{parser} + \label{fig:parser} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/setstate.pdf} + \end{center} + \caption{set state} + \label{fig:set state} +\end{figure} + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/implementation/transitiontable.pdf} + \end{center} + \caption{Transition Table} + \label{fig:transitiontable} +\end{figure} +