\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvipdfm]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{Cerium による並列処理向け I/O の設計と実装}
\author{085726C {古波倉}{正隆} 指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy}

\section{はじめに}
\subsection{研究背景}
近年、CPU 1 コア当たりのクロック数が頭打ちとなっているので、シングルコアでの処理能力はほとんど上がっていない。
それを解決した結果、シングルコアからマルチコアへの移行によって CPU 性能が向上している。
しかし、マルチコア CPU を最大限に活かすためには、プログラムの並列度を向上させなければならない。
そこで当研究室では Cerium Library を提供することによって並列プログラミングを容易にしている。

\subsection{研究目的}
先行研究による Task の並列化によって、プログラム全体の処理速度は飛躍的に向上しているが\cite{kinjyo} 、
ファイル読み込み等の I/O と Task が並列で動作するようには実装されていない。
ファイル読み込みと Task を並列化させることにより、さらなる処理速度の向上が見込まれる。
I/O と Task が並列に動作し、高速かつ容易に記述できるような API を Cerium Library が提供することにより、様々な人が容易に並列プログラミングが記述できるようになるであろうと考えている。

本研究では、 I/O と Task の並列化の設計・実装によって既存の正規表現の処理速度、処理効率を上げることを目指す。

\section{Cerium Task Manager}
Cerium Task Managerは、並列処理をTask単位で記述する。関数やサブルーチンをTaskとして扱い、そのTaskに対してInput Data、Output Data及び依存関係を設定する。そして、それに基づいた設定の元でTaskに管理し、実行される。本稿で述べるInput Dataとは、検索対象となるテキストファイルのことである。

Cerium Task ManagerはPlayStation 3/Cell、Mac OS X及びLinux上で利用することが可能で、近年ではGPUへの利用も可能となった。\cite{tomari}

\section{I/O を含む Task の概要}
ファイルを読み込んで一定の大きさでファイルを分割し (File Read)、それらに対してそれぞれ文字列検索等の処理 (Run Tasks)を行う。
そしてそれぞれの処理から返されたの結果 (Output Data)を最後に集計をして結果を返す(Run resultTask)。(図\ref{fig:includeio})

図\ref{fig:includeio}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.4\textwidth]{pic/includeio.pdf}
\end{center}
\caption{I/O を含む Task}
\label{fig:includeio}
\end{figure}

先行研究では、File Readの部分は mmap 関数を使用して実装していた。mmap 関数での実装の場合はコードの記述が容易である。

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

\subsection{mmap での実装の問題点}

mmap でファイルを読み込むタイミングは、mmap 関数が呼ばれたときではなく、mmap した領域に対して何らかのアクセスをしたときに初めてファイルが読み込まれる。
つまり、分割された Task は文字列検索をすぐに行うのではなく、文字列検索を行おうとした時に初めてファイルが格納される。
Task は複数一斉に実行されることが望ましいが、mmap だとそれぞれの Task で読み込みが起こってしまうので、I/O ネックによる Task の待ちが発生する恐れがある。

\subsection{Blocked Read の設計と実装}
Blocked Read とは、あるサイズずつで読み込む処理と、それらに文字列検索行う処理を分離させるための実装方法である。
この方法では、読み込み専用の Blocked Read と、文字列検索を行う Task Blocks をを別々に生成し処理を行う。
Read Task はファイル全体を一度に読み込むのではなく、ある程度の大きさで分割を行い、読み込みされ次第それぞれの文字列検索が行われる。

Task は 1つずつ起動すると、起動した Task でメモリを圧迫してしまうため、Task を複数まとめたブロック単位で起動を行う。
この1つのブロックで処理されるテキストファイルを、Blocked Read で読み込んでいき、読み込みが終わったら読み込まれた範囲の Task Blocks を起動する。
もし、Blocked Read で読み込まれる前にその範囲を担当する Task が起動してしまうと、正しい結果が返ってこない。
それを防止するために、Task Blocks は必ず Blocked Read が行われてから起動するように wait をかけている。
(図\ref{fig:blockedreadwait})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.4\textwidth]{pic/blockedreadwait.pdf}
\end{center}
\caption{Wait for Blocked Read}
\label{fig:blockedreadwait}
\end{figure}

\subsection{I/O 専用 thread の実装}
Cerium Task Manager では Task 単位で CPU Type の設定を変更することができる。
SPE\_ANY という CPU Type を設定すると、Cerium Task Manager 側が自動的に CPU を割り振ってくれる。
しかし、今回の実装でこのCPU Type を使用してしまうと、Blocked Read Task の隙間時間に Task が割り振られてしまう問題がある。
(図\ref{fig:speany})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.4\textwidth]{pic/speany.pdf}
\end{center}
\caption{SPE\_ANYでの設定時}
\label{fig:speany}
\end{figure}

その問題を解決するために、IO\_0 という CPU Type を新しく実装した。
IO\_0 は他の CPU Type よりも priority を高く設定しているので、他の Task に割り込まれることがないようにした。
(図\ref{fig:io0})

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

\section{ベンチマーク}

\subsection{実験環境}
\begin{itemize}
 \item Mac OS X Mavericks (10.9.1)
 \item HDD 1TB、Memory 16GB、CPU 2*2.66 GHz 6-Core Intel Xeon
 \item ファイルサイズ 10GBに対して検索文字列がいくつ含まれるのかカウント
\end{itemize}
\subsection{実験結果}

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:preaddata}
      \small
      \begin{tabular}[t]{c|l}
        \hline
        読み込み方法 & 実行速度(s)\\
        \hline
        mmap & XX.XXX \\
        \hline
        Blocked Read \& SPE\_ANY & XX.XXX \\
        \hline
        Blocked Read \& IO\_0 & XX.XXX \\
        \hline
      \end{tabular}
      \caption{file read の実行結果}
    \end{center}
  \end{table}
\end{tiny}


\section{まとめと今後の課題}

\thispagestyle{fancy}
\begin{thebibliography}{9}

\bibitem{kinjyo}金城裕、河野真治、多賀野海人、小林佑亮 (琉球大学)\\
ゲームフレームワーク Cerium Task Manager の改良\\
情報処理学会システムソフトウェアとオペレーティング・システム研究会 (OS), April 2011

\bibitem{tomari}渡真利 勇飛、河野 真治(琉球大学)\\
Cerium Task Manager の GPGPU への対応\\
情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)、May 2013

\end{thebibliography}
\end{document}