\chapter{並列処理向け I/O の設計と実装}
\label{chap:poordirection}

\section{map reduce の設計}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth]{fig/mapreduce.pdf}
\end{center}
\caption{map reduce image}
\label{fig:mmap} \end{figure} 

\newpage

\section{mmap での実装の問題点}
mmap とは、sys/mman.h に含まれている関数で、ファイルの読み込み等に使用される関数である。
ファイルディスクリプタで指定したファイルを offset から len バイトの範囲を読み込む。
この時にアドレス addr からメモリを確保するようにする。
prot には、PROT\_READによるページの読み込み、PROT\_WRITEによるページへの書き込みなどを指定でき、
flags にはメモリ確保する際のオプションを指定することができる。(表\ref{table:mmap})

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:mmap}
      \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 関数の概要}
    \end{center}
  \end{table}
\end{tiny}

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

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

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

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/mmap.pdf}
\end{center}
\caption{mmap image}
\label{fig:mmap} \end{figure} 

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

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:pread}
      \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 関数の概要}
    \end{center}
  \end{table}
\end{tiny}

mmap での実装との違いは、ファイルの読み込みがどのタイミングで起こるかである。
mmap で実装したときは、Task 1つ 1つが読み込みを行ってから処理を行う。
それに対して、Blocked Readは、読み込み専用の Read Task と、処理専用の Task を別々に生成する。
Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行う。
分割して読み込み終わったら、それぞれの Task が実行される。
(図\ref{fig:block})
Read Task が生成されて、その後 Task の生成となるので、Read Task は常に走っている必要がある。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth]{fig/blockedreadimage.pdf}
\end{center}
\caption{Blocked Read image}
\label{fig:block}
\end{figure}

図\ref{fig:block} では、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$ となる。
Blocked Read が読み込み終わってから、Task Blockが起動するようにするので、Blocked Read 1つ当たりの読み込み量も $L \times n$となる。

もし、Task Block が Blocked Read よりも先走ってしまうとどうなるであろうか。
まだ読み込まれていない領域に対して何らかの処理を行ってしまうので、正しい結果が返ってこなくなってしまう。
それを防止するために、Blocked Read が読み込み終わってから Task Block が起動されるように wait をかけている。

(図\ref{fig:block})
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=1.0\textwidth]{fig/blockreadtask.pdf}
\end{center}
\caption{Blocked Read image}
\label{fig:block}
\end{figure}

\newpage

\section{I/O 専用 thread の実装}
Cerium Task Manager では、各種 Task にデバイスを設定することができる。デバイスとは、GPU や CPU であり、GPUを利用するときは GPU\_ANY、CPU を利用するときは SPE\_ANYと設定することによってデバイスを利用できる。

SPE\_ANY を使用すると、Task Manager で CPU の割り振りを自動的に行う。しかし、この機能を使用すると、Blocked Read に影響を与えてしまう。

Blocked Read 、Task それぞれに SPE\_ANY で CPUを自動的に割り振ると、Task Manager 側で自動的に CPU を割り当てる。このように CPU を割り当ててしまうと、本来 Blocked Read は連続で読み込むはずが、他の Task を割り当てられてしまう。
(図\ref{fig:speany})

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

この問題を解決するために、Task Manager に新しく I/O 専用の thread を用意した。(図\ref{fig:addio0})
%この問題を解決するために、Task Manager に IO\_0という新しいデバイス設定を追加した。

この設定は他のデバイス設定よりも priority を高く設定している。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/addio_0.pdf}
\end{center}
\caption{IO\_0 の追加}
\label{fig:addio0}
\end{figure}

SPE\_ANY で使用する CPU の設定よりも高く設定しているので、IO\_0 で設定を行う Read Task に SPE\_ANY で設定した 文字列検索 Task に割り込まれることがなくなる。
(図\ref{fig:io0})

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

\newpage
IO\_0 の priority を高く実装したソースコードは以下のようになる。
\begin{breakbox}
\begin{verbatim}
void *
CpuThreads::cpu_thread_run(void *args)
{
    cpu_thread_arg_t *argt = (cpu_thread_arg_t *) args;

        ・・・

    if (argt->cpuid >= argt->cpu_num) {
        // set IO thread priory maximum
        int policy;
        struct sched_param param;
        pthread_getschedparam(pthread_self(), &policy, &param);
        param.sched_priority = 1;
        pthread_setschedparam(pthread_self(), policy, &param);
    }

    return NULL;
}
\end{verbatim}
\end{breakbox}

(ソース説明)