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

従来は mmap や read でファイルの読み込みの実装を行っていた。

mmap とは、sys/mman.h に含まれている関数で、ファイルの読み込み等に使用される関数である。
ユーザ(プロセスの)メモリ空間にファイルのマッピングを行う UNIX のシステムコールであり、
mmapした領域にアクセスされるときに、そのファイルが実メモリに展開される。

\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}

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

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

図\ref{fig:mmap}では、読み込んだファイルを分割して、それらの領域に何らかの処理を加えるときの図である。

1個目の Task が実行されるときに初めてそれらの領域にファイルが読み込まれ、その後何らかの処理が行われ、そして Task 2 も同様に読み込みを行ってから処理が行われる。
これら Task は並列に実行されるべきであるが、ファイル読み込みの I/O 部分がネックとなり、本来並列実行される Task が読み込み待ちを起こしてしまう恐れがある。
さらに、読み込みが OS 依存となるために環境によって左右されやすく、プログラムの書き手が読み込みに関して制御しにくい。

それらを解決するためには、ファイル読み込みと Task を分離し、ファイルの読み込みも制御できるようになれば高速で動くのではないかと考えた。


\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 の設計と実装}

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

\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 と、処理専用の Task を別々に生成する。
Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行ってから読み込む。
分割して読み込み終わったら、読み込んだ範囲内の Task が実行される。
%(図\ref{fig:block})
(図4)
Read Task が生成されて、その後 Task の生成となるので、Read Task は常に走っている必要がある。

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

この図では、Read Task 1つに対して Task 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 単体で読み込むファイルの範囲の先頭と末尾のポジションを設定する。

なお、run\_tasks 内部で、処理を行う task を生成している。
その内部で、task が生成されるたびに task\_num のインクリメントを行っている。

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 よりも priority を高く設定しているので、IO\_0 で設定された Read Task に SPE\_ANY で設定した 文字列検索 Task に割り込まれることがなくなる。
Cerium では、並列処理を pthread で記述しており、pthread\_getschedparam()でIO\_0 の priority を設定している。
pthread\_getschedparam は、〜をする関数である。
(図\ref{fig:io0})

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