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

\section{map reduce}

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

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

\section{Bloked Read の設計と実装}
Blocked Read とは、読み込みの Task と、それに対する何らかの処理の Task を切り離すための実装方法で、pread 関数で実装した。
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}




\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 に新しいデバイス設定を追加した。

・ Cerium の Task に CPU Type を設定することができる。しかし、同じCPU Type を使用すると、IO を担当している CPU に Task が割り振られて、read 全体の速度が遅くなってしまう。
・ Cerium では ptherad で並列処理を記述している

・ SPY\_ANY という CPU Type は、Cerium 側が自動的に CPU 割り当てを行う便利なマクロ

・ SPE\_ANY を使用すると、IO の部分にも割り込まれてしまうので、これをどうにかしたい。

・ IO\_0 という新しい CPU Type を追加

・ pthread の API で CPU の priority をあげることができる。



図\ref{fig:io0}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=1.0\textwidth]{fig/io0.pdf}
\end{center}
\caption{[image]priority を上げたときの image 図}
\label{fig:io0}
\end{figure}

・ これで IO 部分に割り込みがおこらないよね!!