\section{並列処理向け I/O の設計と実装}

I/Oを平行に行うには、従来の read loop を行うのでは
read がプログラム全体を止めてしまう。
もっとも簡単にreadを並行して行うには、file open の代わりに
mmap を使う方法がある。mmap は直ぐにファイルを読みに行くのではなく、
仮想メモリ空間にファイルの中身を対応させる。
そのメモリ空間にアクセスに行くと、それに対応した部分のファイルをOSが見に行く。
ファイルが読み込まれるまでは、アクセスしたスレッド/プロセスは、その場で待たされる。
しかし、mmap は逐次アクセスを仮定しているので、OS内部で自動的にファイルの先読みを
行うと期待される。


\if0
\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \small
      void * mmap(void *addr, size\_t len,
                    int prot, int flags, int fd, off\_t offset);

      \begin{tabular}[t]{c|l}
        \hline
        void *addr &  メモリに確保するときの先頭のアドレス\\
        \hline
        size\_t len &  メモリを確保するサイズ\\
        \hline
        int prot &  ファイルモード選択\\
        \hline
        int flags &  確保するときのオプション指定\\
        \hline
        int fd &  読み込むファイルのファイルディスクリプタ\\
        \hline
        off\_t offset & ファイル先頭からの読み込み開始位置 \\
        \hline
      \end{tabular}
      \caption{mmap 関数の概要}
      \label{table:mmap}
    \end{center}
  \end{table}
\end{tiny}
\fi

\if0
ファイルディスクリプタで指定したファイルを offset から len バイトの範囲を読み込む。
この時にアドレス addr からメモリを確保するようにする。
prot には、PROT\_READによるページの読み込み、PROT\_WRITEによるページへの書き込みなどを指定でき、
flags にはメモリ確保する際のオプションを指定することができる。(表\ref{table:mmap})
\fi

% mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。

1個目の Task が実行されるときに初めてそれらの領域にファイルが読み込まれ、その後何らかの処理が行われ、そして Task 2 も同様に読み込みを行ってから処理が行われる。
mmap の read は、Task と並列に実行されるべきであるが、それは OS の実装に依存する。実際、mmap のフラグのほとんどは実装されていない。
読み込みの実行が、うまく並列に実行されなければ、Task が読み込み待ちを起こしてしまう。
読み込みが OS 依存となるために環境によって左右されやすく、mmap では細かく制御することができない。

そこで、mmap を使わずに read を独立したスレッドで行い、読み込まれた部分に対して、並列
タスクを起動する方法があるが、プログラミングは煩雑になる。今回は、この部分を
実装し、mmap に対して、どれだけ性能が向上するかを調べる

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.5]{images/mmap.pdf}
\end{center}
\caption{mmap Model}
\label{fig:mmap}
\end{figure}


\subsection{Blocked Read の設計と実装} \label{cap:block}

% Asynchronous Read の方が良いね。

Blocked Read とは、読み込みの Task と、それらに対して何らかの処理を行う Task を切り離すための実装方法である。それを実現するため、pread 関数にて実装した。
pread 関数は、unistd.h に含まれている UNIX 専用の関数である。
ファイルディスクリプタで指定したファイルの先頭から offset 分ずれた場所を基準として、その基準から count バイトを読み込み、それを buf に格納する。
(表\ref{table:pread})

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \small
      ssize\_t pread(int d, void *buf, size\_t nbyte, off\_t offset);
      \begin{tabular}[t]{c|l}
        \hline
        int d & 読み込むファイルのファイルディスクリプタ\\
        \hline
        void *buf & 読み込んだファイルの格納場所 \\
        \hline
        size\_t nbyte & 読み込むファイル量\\
        \hline
        off\_t offset & ファイル先頭からの読み込み開始位置\\
        \hline
      \end{tabular}
      \caption{pread 関数の概要}
      \label{table:pread}
    \end{center}
  \end{table}
\end{tiny}

従来の実装との違いは、ファイルの読み込みがどのタイミングで起こるかである。
Blocked Readは、読み込み専用の Read Task と、WordCount を別々に生成する。
Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行ってから読み込む。
分割して読み込み終わったら、読み込んだ範囲内の WordCount が実行される。
(図\ref{fig:block})

Read Task が生成されて、その後 WordCount Task の実行となるので、Read Task は連続で走っている必要がある。

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.4]{images/blockedreadimage.pdf}
\end{center}
\caption{Read Task と WordCount の分離}
\label{fig:block}
\end{figure}

この図では、Read Task 1つに対して WordCount を1つ起動しているが、このように1つ1つ生成、起動をすると Task 生成でメモリを圧迫してしまい、全体的な動作に影響を与えてしまう。
実際には Task をある一定数まとめた単位で生成し、起動を行っている。この単位を Task Block と定義する。

Task Block 1つ当たりがの Task 量を $n$ とおく。Task 1つ当たりの読み込む量を $L$ とすると、Task Block 1つ当たりの読み込む量は $L \times n$ となる。

Task Block が Blocked Read よりも先走ってしまうと、
まだ読み込まれていない領域に対して処理を行ってしまうので、正しい結果が返ってこなくなってしまう。
それを防止するために、Blocked Read が読み込み終わってから Task Block が起動されるように Cerium の API である wait\_for にて依存関係を設定する。
(図\ref{fig:block})

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.35]{images/blockreadtask.pdf}
\end{center}
\caption{Blocked Read image}
\label{fig:block}
\end{figure}

\newpage

以下に、Blocked Read Task の生成部分を示す。

\begin{verbatim}

HTaskPtr t_read =
        manager->create_task(READ_TASK);
t_read->set_cpu(DEVICE_TYPE);
t_read->set_outData(0,
        file_mmap + task_num * division_size,
        task_blocks * division_size);
t_read->set_param(0,fd);
t_read->set_param(1,task_num*division_size);

run_tasks(manager,w, task_blocks,・・・ );

t_read->set_param(2,task_num*division_size);
t_read->spawn();

\end{verbatim}

set\_cpu にて Read Task を担当するデバイスの設定を行う。
set\_outData(0) にファイルを読み込んだときの格納場所を指定し、set\_param(0) にて読み込むファイルディスクリプタを設定している。
set\_param(1) 、 set\_param(2) にて Blocked Read Task 単体で読み込むファイルの範囲の先頭と末尾のポジションを設定する。

Cerium の Task は、最初に word count に必要な Task を全部起動してしまうと、そのTaskを表すデータ構造自体がメモリを消費してしまう。
そこで、既にある程度の量の Task を起動し、それが終了してから(正確には、終了する前に)次のTaskを生成するようになっている。
これが \verb+run_tasks+ である。
そこの部分にファイルを読み込む Task との待ち合わせを入れれば良いので、実装は比較的容易にできる。

\verb+run_tasks+ の中で、\verb+READ_TASK+ に対する待ち合わせを \verb+wair_for()+ を使って実現している。

Blocked Read Task の記述は以下のようになる。

\begin{verbatim}
static int
read_task(SchedTask *s, void *rbuf, void *wbuf)
{
    long fd = (long)s->get_param(0);
    long start_read_position =
            (long)s->get_param(1);
    long end_read_position =
            (long)s->get_param(2);
    char *read_text =
            (char*)s->get_output(wbuf,0);
    long read_size = end_read_position -
                     start_read_position;

    pread(fd, read_text,
          read_size , start_read_position);
    return 0;
}
\end{verbatim}

Blocked Read Task の生成部分で設定したパラメータをそれぞれ受け取る。ファイル読み込みの先頭と末尾のポジションが渡されているので、どれだけファイルを読みこめばいいか求めることができる。

それらのパラメータを使用して、pread 関数に渡すことで Blocked Read によるファイル読み込みを実現している。


\subsection{I/O 専用 thread の実装}

Cerium Task Manager では、各種 Task にデバイスを設定することができる。
SPE\_ANY という設定を使用すると、Task Manager で CPU の割り振りを自動的に行う。
Blocked Read 、Task それぞれに SPE\_ANY にてデバイスの設定を行うと、Task Manager 側で自動的に CPU を割り当てられ、本来 Blocked Read は連続で読み込むはずが、他の Task を割り当てられてしまう。
(図\ref{fig:speany})

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.3]{images/speany.pdf}
\end{center}
\caption{SPE\_ANY での実装時}
\label{fig:speany}
\end{figure}

この問題を解決するため、Task Manager に新しく I/O 専用の thread 、 IO\_0 の追加を行った。

%(図\ref{fig:addio0})
%%この問題を解決するために、Task Manager に IO\_0という新しいデバイス設定を追加した。
%
%
%\begin{figure}[htbp]
%\begin{center}
%\includegraphics[scale=0.5]{images/addio_0.pdf}
%\end{center}
%\caption{IO\_0 の追加}
%\label{fig:addio0}
%\end{figure}

IO\_0 は、SPE\_ANY とは、別なスレッド動いているスケジューラーで動くので、
SPE\_ANY で動いている 文字列検索 Task に割り込まれることはない。
しかし、読み込みが完了した時に、その完了を通知し、次の read を行う時に、他の計算スレッドにスレッドレベルで割り込まれてしまうと、全体の計算が待たされてしまう。
そこで、 pthread\_getschedparam()でIO\_0 の priority を設定している。
IO thread は計算はほとんどしないので、高い優先順位を割り当てても他の計算を行うスレッドには影響しない。
IOを含む処理では IOを行うスレッドの優先順位を高くする必要があるということである。
(図\ref{fig:io0})

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.3]{images/io0.pdf}
\end{center}
\caption{Blocked Read Task を IO\_0 での実装時}
\label{fig:io0}
\end{figure}

\newpage