\chapter{並列処理向けI/O}
ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。
プログラムの並列化を行ったとしても、 I/O がボトルネックになってしまうと処理は高速にならない。
本項では Cerium に並列処理用の I/O の実装を行う。これにより I/O 部分の高速化を図る\cite{masa:2014a}。

\section{mmap}
Cerium ではファイルの読み込みを mmap により実装していた。
しかし、mmap や read によりファイルを読み込んでから処理を実行させると、
読み込んでいる間は他の CPU が動作せず、並列度が落ちてしまう。
そこで、 I/O 部分も並列に動作するよう実装した。

Read を並列に行うには、File Open ではなく mmap を使う方法がある。Cerium でも mmap を使用していた。
mmap はすぐにファイルを読みに行くのではなく、まず仮想メモリ空間にファイルの中身を対応させる。
メモリ空間にアクセスが行われると、OS が対応したファイルを読み込む。

mmap で読み込んだファイルに Task1、Task2 がアクセスし、それぞれの処理を行う際の例を図:\ref{fig:mmap}に示す。

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

Task1 が実行される時、仮想メモリ上 Open されたファイルの読み込みを行い、Task1 の処理を行う。
その後、同様に Task2 も読み込みを行ってから処理を行う。この Task1 と Task2 の間に待ちが入る。

ファイルの読み込みが起こると、アクセスした Thread/Process には wait がかかってしまう。
しかし mmap による Read は Task と並列に実行されるべきである
 mmap は逐次アクセスを仮定しているので、OS 内部で自動的にファイルの先読みを行う事も期待できる。
しかしそれは OS の実装に依存してしまう。
読み込みが並列に実行されない場合、 Task が読み込み待ちを起こしてしまう。
読み込みが OS 依存となるため、環境によって左右されやすく、汎用性を損なってしまう。

そこで、mmap を使わず、read を独立したスレッドで行い、ファイルを一度に全て読み込むのではなく
ある程度の大きさ (Block) 分読み込み、読み込まれた部分に対して並列に Task を起動する。
これを Blocked Read と呼ぶ。Blocked Read によるプログラミングは複雑になるが、高速化が期待できる。

\section{Blocked Read による I/O の並列化}
Blocked Read を実装するにあたり、WordCount を例に考える。
Blocked Read はファイル読み込み用の Task(以下、ReadTask) と
読み込んだファイルに対して処理を行う Task(今回はWordCount) を別々に生成する。
ReadTask はファイル全体を一度に全て読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。
分割後の読み込みが終わると、読み込んだ範囲に対して WordCount を行う。

BlockedRead による WordCount を行う場合、図:\ref{fig:blockedread}のようになる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.5]{./images/blockedread.pdf}
  \end{center}
  \caption{BlockedRead による WordCount}
  \label{fig:blockedread}
\end{figure}

Task を一定数まとめた単位で生成し、起動を行っている。この単位を Task Block と定義する。
TaskBlock が BlockedRead を追い越して実行してしまうと、まだ読み込まれてない領域に対して処理を行ってしまう。
その問題を解決するため、依存関係を設定する。
BlockedReadによる読み込みが終わってから TaskBlock が起動されるよう、
Cerium の API である wait\_for により依存関係を設定する。
しかし、Task が BlockedRead を追い越すことによるロックはオーバーヘッドとなるため、起こさないようにしたい。
つまり、 BlockedRead は連続で走っている必要がある。

以上を踏まえ、BlockedRead の実装を行った。
BlockedRead Task の生成はソースコード:\ref{src:blockedread_create}のように行う。

\begin{lstlisting}[frame=lrbt,label=src:blockedread_create,caption=BlockedRead を行う Task の生成,numbers=left]
HTaskPtr readTask = manager->create_task(READ_TASK)
readTask->set_cpu(DEVICE_TYPE);
readTask->set_outData(0, file_map + task_num * division_size, task_blocks * division_size);
readTask->set_param(0, fd);
readTask->set_param(1, task_num * division_size);
runTask();
readTask->set_param(2, task_num * division_size)
readTask->spawn();
\end{lstlisting}

\begin{itemize}
\item 3行目、set\_outData(0): ファイルを読み込んだ際の格納場所を設定
\item 4行目、set\_param(0): 読み込むファイルディスクリプタを設定
\item 5行目、set\_param(1): BlockedRead Task で読み込むファイルの範囲の先頭のポジションを設定
\item 7行目、set\_param(2): BlockedRead Task で読み込むファイルの範囲の末尾のポジションを設定
\end{itemize}

Cerium において、 WordCount で必要な Task を全て生成してしまうと、
その Task のデータ構造自体がメモリを消費してしまう。
そこである程度の量の Task を起動し、それが終了してから(正確には終了する前に)次の Task を生成するようになっている。
それらの機能を持った関数が6行目にあたる runTask である。
runTask に wait\_for による ReadTask との待ち合わせの処理を入れれば良い。

BlockedRead の Task をソースコード:\ref{src:blockedread_task}示す。

\begin{lstlisting}[frame=lrbt,label=src:blockedread_task,caption=BlockedRead Task,numbers=left]
static int
read_task(SchedTask *s, void *rbuf, void *wbuf) {
    long fd = (long)s->get_param(0);
    long start = (long)s->get_param(1);
    long end   = (long)s->get_param(2);
    char txt   = (char*)s->get_output(wbuf, 0);
    long size  = end - start;
    
    pread(fd, txt, size, start);
    return 0;
}
\end{lstlisting}

Cerium の API により、生成部分で設定したパラメタをそれぞれ受け取る。
ファイル読み込みの先頭・末尾のポジションが渡されているので、ファイルから読み込むサイズは求められる。
受け取ったパラメタをそれぞれ pread 関数に渡すことで Blocked Read を実現している。
\newpage
\section{I/O 専用 Thread の実装}
\label{sec:spe_problem}
Cerium Task Manager では、各種 Task にデバイスを設定することができる。
 SPE\_ANY 設定を使用すると、 Task Manager で CPU の割り振りを自動的に行う。
BlockedRead は連続で読み込まれなければならないが、
SPE\_ANY 設定で実行すると BlockedRead 間に別の Task が割り込んでしまう場合がある。
(図:\ref{fig:spe_any_blockedread})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/speblockedread.pdf}
  \end{center}
  \caption{BlockedRead と Task を同じ thread で動かした場合}
  \label{fig:spe_any_blockedread}
\end{figure}

そこで I/O 専用の Thread である IO\_0 の追加を行った。

IO\_0 は SPE\_ANY とは別 Thread の Scheduler で動くので、SPE\_ANY で動いている Task に割り込まれることはない。
しかし、読み込みの終了を通知し、次の read を行う時に他の Task がスレッドレベルで割り込んでしまう事がある。
pthread\_getschedparam() で IO\_0 の priority の設定を行う必要がある(図:\ref{fig:iothread_blockedread})。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/iothread.pdf}
  \end{center}
  \caption{IO Thread による BlockedRead}
  \label{fig:iothread_blockedread}
\end{figure}
IO\_0 で実行される Task は BlockedRead のみなので、
IO\_0 のpriority を高く設定することで Blocked Read は連続で実行される。

また、以上の事から I/O を含む並列処理において読み込みの Task と計算を行う Task を並列で走らせたい場合、
I/O を行う Thread の priority を高くする必要があるという知見を得られた。