# HG changeset patch # User Yuhi TOMARI # Date 1424686339 -32400 # Node ID f9b73e12a52f9df3727ed50f62b0993586467414 # Parent 4a4d4ef632d0759276969cec42ff8fc261774cd4 fix diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/abstract.tex --- a/paper/abstract.tex Mon Feb 23 17:09:12 2015 +0900 +++ b/paper/abstract.tex Mon Feb 23 19:12:19 2015 +0900 @@ -1,11 +1,12 @@ \begin{abstract} + Cerium は並列プログラミングフレームワークである。 Cerium は Cell Broad band Engine 用のフレームワークであったが、 マルチコア CPU や GPU といったマルチプラットフォームに対応させ、より汎用的なフレームワークへ改良を行った。 マルチコア CPU は SynchronizedQueue 、 GPU は OpenCL と CUDA により実装した。 -データ並列実行をサポートすることで GPGPU を行う際に高い並列度を維持することを可能にした。 -また、Cerium ではファイル読み込みを mmap 及び専用スレッドを用いる方法で十分な性能が出ることを示した。 +データ並列実行をサポートすることで、GPGPU を行う際に高い並列度を維持することを可能にした。 +また Cerium では、ファイル読み込みを mmap 及び専用スレッドを用いる方法で十分な性能が出ることを示した。 Sort、WordCount 、FFT の例題を元に測定評価を行った。 \end{abstract} diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/chapter1.tex --- a/paper/chapter1.tex Mon Feb 23 17:09:12 2015 +0900 +++ b/paper/chapter1.tex Mon Feb 23 19:12:19 2015 +0900 @@ -1,5 +1,5 @@ \chapter{既存のマルチプラットフォーム\\フレームワーク} -マルチプラットフォームでプログラムを動作させる場合、そのアーキテクチャを意識する必要がある。 +　マルチプラットフォームでプログラムを動作させる場合、そのアーキテクチャを意識する必要がある。 マルチプラットフォームにはマルチコア CPU 、 GPU や Cell といったヘテロジニアスマルチコアのような 様々な構成がある。 @@ -40,7 +40,7 @@ \label{fig:cpuarch} \end{figure} -Shared Memory でないプロセッサとして、Cell が挙げられる。 +Shared Memory でないプロセッサとして、Cell が挙げられる\cite{cell}。 Cell は1基の制御系プロセッサコア PPE ( PowerPC Processer Element ) と 8基の演算系プロセッサコア SPE ( Synergistic Processer Element ) で構成される。 @@ -63,7 +63,7 @@ \section{OpenCL} OpenCL とは、 Khronos Group の提供するマルチコア CPU と GPU といった、 -ヘテロジニアス環境を利用した並列計算を支援するフレームワークである。 +ヘテロジニアス環境を利用した並列計算を支援するフレームワークである\cite{opencl}。 OpenCL では演算用プロセッサ側を Device 、制御用デバイス側を Host として定義する。 また、 Device 上で動作するプログラムの事を kernel と呼ぶ。 @@ -95,7 +95,7 @@ % CUDA %------ \section{CUDA} -CUDA とは、半導体メーカーNVIDIA社が提供するGPUコンピューティング向けの総合開発環境である。 +CUDA とは、半導体メーカーNVIDIA社が提供するGPUコンピューティング向けの総合開発環境である\cite{cuda}。 CUDA も OpenCL と同様、演算用プロセッサ (GPU) を Device 、制御用デバイス側を Host として定義する。 また、 Device 上で動作するプログラムの事も kernel と呼ぶ。 @@ -125,7 +125,7 @@ \section{StarPU} StarPUはフランス国立情報学自動制御研究所 (INRIA) の StarPU 開発チームの提供する、 -ヘテロジニアス環境向けのフレームワークである。 +ヘテロジニアス環境向けのフレームワークである\cite{starpu}。 GPU の制御に OpenCL と CUDA を用いており、どちらかを選択することで GPU 上で実行することができる。 OpenCL と CUDA における実行の単位は kernel だったが、 StarPU では実行の単位を Task と定義している。 @@ -133,7 +133,7 @@ StarPU では Task を制御するためにcodeletと呼ばれる構造体を使う。 codelet を Task 生成時にポインタ渡しすることで、 演算を行うリソースや実行する関数等を指定することができる。 - CPU と GPU で並列に実行する例を\ref{src:codelet}に示す。 + CPU と GPU で並列に実行する例をソースコード:\ref{src:codelet}に示す。 \begin{lstlisting}[frame=lrbt,label=src:codelet,caption=codeletの例,numbers=left] starpu_codelet codelet = { diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/chapter3.tex --- a/paper/chapter3.tex Mon Feb 23 17:09:12 2015 +0900 +++ b/paper/chapter3.tex Mon Feb 23 19:12:19 2015 +0900 @@ -8,7 +8,7 @@ FFT:Fast Fourier Transform(高速フーリエ変換) は、 信号処理や画像処理から大規模シミュレーションに至るまで幅広い分野で活用されている計算である。 -バタフライ演算などの計算の性質上、データ並列と相性がよく、 GPGPU で高い並列度を維持できる事が知られている。 +バタフライ演算などの計算の性質上、データ並列と相性がよく、 GPGPU で高い並列度を維持できる事が知られている\cite{fft}。 以上3つの例題を用いてベンチマークを行っていく。本論文で使用する各種例題について紹介する。 @@ -25,7 +25,7 @@ 指定された数の乱数を生成し、sort する例題である。 SortSimpleTask は Task の割り当てを行う Task である。 QuickSortTask は割り当てられた範囲を QuickSort により Sort する Task である。 -図:\ref{fig:sort}に Bitonic Sort の例を示す。 +図:\ref{fig:sort_example}に Bitonic Sort の例を示す。 SimpleSortTask は乱数列を分割し、 QuickSortTask に割り当てる。QuickSortTask は割り当てられた部分を Sortする。 分割した部分をQuickSortTaskに割り当て、繰り返し起動していく事でSort を行う。 @@ -44,7 +44,7 @@ \includegraphics[scale=0.7]{./images/sort_benchmark.pdf} \end{center} \caption{Bitonic Sort の例} - \label{fig:sort} + \label{fig:sort_example} \end{figure} \newpage @@ -114,7 +114,7 @@ Sort の例題を元に Task の生成について考える。 Sort の手順は\ref{sec:about_sort}節でも述べたが、 「乱数列を分割して Sort 」と -「割り当てた範囲の中間から次の範囲の中間までを Sort 」2つの Sort により構成される。 +「割り当てた範囲の中間から次の範囲の中間までを Sort 」、以上の2つの Sort により構成される。 「乱数列を分割して Sort」を fsort 、 「割り当てた範囲の中間から次の範囲の中間までを Sort 」を bsort とする。 2つの Sort の構成を図:\ref{fig:fsort_bsort}に示す。 @@ -124,7 +124,7 @@ \includegraphics[scale=0.7]{./images/fsort_bsort.pdf} \end{center} \caption{fsort と bsort} - \label{fig:sort} + \label{fig:fsort_bsort} \end{figure} bsort は fsort の結果に対して Sort を行う。つまりこの2つの Sort 間には依存関係が存在する。 @@ -134,7 +134,7 @@ Task 生成部分は複雑になるという問題がある。 Sort の例題における依存関係の記述を行う Task を SortSimple とし、ソースコード:\ref{src:sort_dependency}に示す。 -\begin{lstlisting}[frame=lrbt,label=src:sort_rependency,caption=Sort の例題における依存関係の記述,numbers=left] +\begin{lstlisting}[frame=lrbt,label=src:sort_dependency,caption=Sort の例題における依存関係の記述,numbers=left] static int sort_start(SchedTask *manager, void *d, void *e) { diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/chapter4.tex --- a/paper/chapter4.tex Mon Feb 23 17:09:12 2015 +0900 +++ b/paper/chapter4.tex Mon Feb 23 19:12:19 2015 +0900 @@ -1,5 +1,6 @@ \chapter{マルチコアへの対応} -Cerium は Cell 上で並列に動作するフレームワークであったが、 Mac OS X 、 Linux 上でも並列に実行させることを可能にした。 +Cerium は Cell 上で並列に動作するフレームワークであった\cite{yutaka:2012a}が、 + Mac OS X 、 Linux 上でも並列に実行させることを可能にした。\cite{daichi:2012a} \section{マルチコア上での実行の機構} Cell には MailBox という機能がある。 @@ -18,13 +19,14 @@ CPU を介さずに周辺装置とメモリ間でデータ転送を行う方式である。 Cerium も DMA 転送を用いている箇所がある。 -しかしマルチコア CPU 上で実行する場合は各 CPU で同じメモリ空間を利用できる。 -よって DMA 転送を用いていた部分をポインタ渡しを行うように修正し、 +しかし現在主流のアーキテクチャでは DMA をサポートしていない。 +マルチコア CPU 上で実行する場合は各 CPU で同じメモリ空間を利用できるため、 + DMA 転送を用いていた部分をポインタ渡しを行うように修正した。 メモリに直接アクセスさせることで速度の向上が見込める。 -更に、DMA には prefetch 機能がある。 -DMA の転送効率を向上させるため、 DMA で転送する送信データを予め取り込むことができる。 -Cerium では DMA によるprefetch、DMA を用いないポインタ渡し、更に明示的なコピーによるデータ転送をサポートする。 +更に、Cerium には prefetch 機能がある。 +データの転送効率を向上させるため、転送する送信データを予め取り込むことができる。 +Cerium ではprefetch、prefetch を用いないポインタ渡し、更に明示的なコピーによるデータ転送をサポートする。 \section{データ並列} \label{sec:multicore_dataparallel} @@ -38,7 +40,7 @@ 処理対象となるデータが充分な数のサブデータへ分割することが可能で、 サブデータへの処理を行うことが元のデータへの処理と同じになる場合、データ並列が有効となる。 -本研究で Cerium でデータ並列による実行を可能にした。 +本研究で Cerium でデータ並列による実行を可能にした\cite{yuhi:2013a}。 Cerium でデータ並列実行を行う場合、Task を spwan API でなく iterate API で生成すればよい。 iterate API は複数の length を引数とし、 length の値がデータ分割後に各 Task が担当するサイズ、length の個数がデータの次元数となる。 diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/chapter5.tex --- a/paper/chapter5.tex Mon Feb 23 17:09:12 2015 +0900 +++ b/paper/chapter5.tex Mon Feb 23 19:12:19 2015 +0900 @@ -1,5 +1,5 @@ \chapter{GPGPU への対応} -Cerium の新たな演算資源として GPU の使用を可能にした。 +Cerium の新たな演算資源として GPU の使用を可能にした。\cite{yuhi:2013a} 現在、GPU のような異なる種類のアーキテクチャを搭載した CPU 、つまりヘテロジニアスな CPU が増えている。 特定の計算に特化した Task の生成やスケジューリングを行い、 GPGPU により高い並列度を出す研究は様々な分野で行われている。 本研究では Cerium を特定の計算に限らず、 GPU を用いて汎用計算を行えるフレームワークに改良する。 @@ -136,7 +136,7 @@ GPU は数百個のコアを有しており、ループ部分に対してデータ並列で処理を行うことで CPU より高速に演算を行う事ができる。 プログラムの大部分がループであれば、データ並列による実行だけでプログラムの性能は向上する。 -OpenCL 、 CUDA ともにデータ並列をサポートしている。 +OpenCL 、 CUDA ともにデータ並列をサポートしている。\cite{yuhi:2014a}\cite{kkb:2014a} OpenCL と CUDA はTask を実行する際にデータをどう分割するか指定し、 kernel にデータ並列用の処理を加えることで可能となる。 \ref{sec:multicore_dataparallel}節で Cerium でマルチコア CPU におけるデータ並列を可能にした。 diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/chapter6.tex --- a/paper/chapter6.tex Mon Feb 23 17:09:12 2015 +0900 +++ b/paper/chapter6.tex Mon Feb 23 19:12:19 2015 +0900 @@ -1,7 +1,7 @@ \chapter{並列処理向けI/O} ファイル読み込みなどの I/O を含むプログラムは、読み込み時間が Task の処理時間と比較してオーバーヘッドになることが多い。 プログラムの並列化を行ったとしても、 I/O がボトルネックになってしまうと処理は高速にならない。 -本項では Cerium に並列処理用の I/O の実装を行う。これにより I/O 部分の高速化を図る。 +本項では Cerium に並列処理用の I/O の実装を行う。これにより I/O 部分の高速化を図る\cite{masa:2014a}。 \section{mmap} Cerium ではファイルの読み込みを mmap により実装していた。 @@ -34,11 +34,11 @@ 読み込みが OS 依存となるため、環境によって左右されやすく、汎用性を損なってしまう。 そこで、mmap を使わず、read を独立したスレッドで行い、ファイルを一度に全て読み込むのではなく -ある程度の大きさ (Block) 分読み込み、読み込まれた部分に倒して並列に Task を起動する。 +ある程度の大きさ (Block) 分読み込み、読み込まれた部分に対して並列に Task を起動する。 これを Blocked Read と呼ぶ。Blocked Read によるプログラミングは複雑になるが、高速化が期待できる。 \section{Blocked Read による I/O の並列化} -Blocked Read を実装するに辺り、WordCount を例に考える。 +Blocked Read を実装するにあたり、WordCount を例に考える。 Blocked Read はファイル読み込み用の Task(以下、ReadTask) と 読み込んだファイルに対して処理を行う Task(今回はWordCount) を別々に生成する。 ReadTask はファイル全体を一度に全て読み込むのではなく、ある程度の大きさで分割してから読み込みを行う。 @@ -89,7 +89,7 @@ それらの機能を持った関数が6行目にあたる runTask である。 runTask に wait\_for による ReadTask との待ち合わせの処理を入れれば良い。 -BlockedRead の Task をいかに示す。 +BlockedRead の Task をソースコード:\ref{src:blockedread_task}示す。 \begin{lstlisting}[frame=lrbt,label=src:blockedread_task,caption=BlockedRead Task,numbers=left] static int diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/introduciton.tex --- a/paper/introduciton.tex Mon Feb 23 17:09:12 2015 +0900 +++ b/paper/introduciton.tex Mon Feb 23 19:12:19 2015 +0900 @@ -1,32 +1,28 @@ \chapter{マルチプラットフォームな\\フレームワークにおける\\並列プログラミング} \pagenumbering{arabic} -% 動画の編集や再生、ゲームといったPCやタブレット等の端末でできる事・やりたい事が増えてきている。 + -% PCやタブレットの一般的な利用方法として動画の編集や再生、ゲームといったアプリケーションの利用が挙げられる。 -% Rednering や物理演算といった処理から -プログラムが PC に要求する処理性能は上がってきているが、 -%-ゲームや動画再生といったアプリケーションが高水準(？)になるにつれて -%-高水準:高解像度だったり、ぬるぬる動いたり +　プログラムが PC に要求する処理性能は上がってきているが、 消費電力・発熱・クロックの限界から、 CPU の性能を上げることによる処理性能の向上は難しい。 プロセッサメーカーはマルチコア CPU や GPU を含むヘテロジニアス構成の路線を打ち出している。 クロックの性能を上げるのではなく、コア数を増やすことでパフォーマンスを向上させている。 -マルチコア CPU や GPU といったマルチプラットフォームなアーキテクチャ上でリソースを有効活用するには、 +マルチコア CPU や GPU といった、マルチプラットフォームなアーキテクチャ上でリソースを有効活用するには、 それぞれのプラットフォームに対して最適な形でプログラムを並列に動作させる必要がある。 -ここでいう最適な形とは、実行の順番やどのリソース上で Task を実行するかといった +ここでいう最適な形とは、実行の順番やどのリソース上で Task を実行するかといった、 Scheduling を含めたチューニングの事である。 -しかしこれらのチューニングは複雑で、コーディング時に毎回行うと煩雑さや拡張性の点で問題がある。 -そういった問題を解決するため、本研究では並列プログラミングフレームワーク Cerium の開発を行った。 -Cerium によりプラットフォーム間で統一的にコードを記述できる。 +しかし、これらのチューニングは複雑で、コーディング時に毎回行うと煩雑さや拡張性の点で問題がある。 +このような問題を解決するため、本研究では並列プログラミングフレームワーク Cerium の開発を行った。 +Cerium により、プラットフォーム間で統一的にコードを記述できる。 一般的なマルチプラットフォームフレームワークとして OpenCL や CUDA が挙げられるが、 これらと同等の並列度を維持したい。 -Cerium では Task という単位で処理を記述し、それらは並列に実行される。 +Cerium では、Task という単位で処理を記述し、それらは並列に実行される。 プログラマが Task 間の依存関係を設定するとパイプラインが構成され、高い並列度で実行される。 プログラマが生成した Task は TaskManager に送信され、設定した依存関係の解決を行った後、 Scheduler に送信される。 Scheduler がパイプラインの機構を持っており、Task はそのパイプラインに沿って実行される。 -Scheduler が受信した Task は既に TaskManager が依存関係を解決しているため、実行順序は任意で良い。 +Scheduler が受信した Task は、既に TaskManager が依存関係を解決しているため実行順序は任意で良い。 計算機において並列処理を行うための設計様式として、1つの命令を同時に複数のデータに適用し、並列に処理する方式がある。 これをSIMD と呼ぶ。 @@ -38,6 +34,5 @@ TaskManager はプログラマが記述した単一の Task を複数生成し、 受け取ったデータ(Input/Output)に対しその Task を割り当てる。 生成した復数の Task を並列実行する事でデータ並列実行を実現した。 - -Sort 、Word Count 、FFT の例題を元に、 +更に、Sort 、Word Count 、FFT の例題を元に、 Cerium の持つ並列実行機構がマルチプラットフォームにおける並列プログラミングで有効に作用する事を示す。 diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/master_paper.bbl --- a/paper/master_paper.bbl Mon Feb 23 17:09:12 2015 +0900 +++ b/paper/master_paper.bbl Mon Feb 23 19:12:19 2015 +0900 @@ -1,5 +1,32 @@ \begin{thebibliography}{10} +\bibitem{cell} +Sony Corporation. +\newblock Cell broadband engine architecture. +\newblock 2005. + +\bibitem{opencl} +Aaftab Munshi and Khronos OpenCL~Working Group. +\newblock The opencl specification version 1.0. +\newblock 2007. + +\bibitem{cuda} +{CUDA}. +\newblock {https://developer.nvidia.com/category/zone/cuda-zone/}. + +\bibitem{starpu} +{C{\'e}dric Augonnet, Samuel Thibault, Raymond Namyst, Pierre-Andr{\'e} + Wacrenier}. +\newblock {StarPU: A Unified Platform for Task Scheduling on Heterogeneous + Multicore Architectures}. +\newblock {\em Concurrency and Computation: Practice and Experience, Special + Issue: Euro-Par 2009}, Vol.~23, pp. 187--198, February 2011. + +\bibitem{fft} +Yasuhiko OGATA, Toshio ENDO, Naoya MARUYAMA, and Satoshi MATSUOKA. +\newblock 性能モデルに基づく cpu 及び gpu を併用する効率的な fft ライブラリ. +\newblock 情報処理学会論文誌コンピューティングシステム, 2008. + \bibitem{yutaka:2012a} Yutaka KINJO. \newblock 並列プログラミングフレームワーク cerium の改良. @@ -33,31 +60,4 @@ \newblock 情報処理学会システムソフトウェアとオペレーティング・システム研究会, 2014. -\bibitem{fft} -Yasuhiko OGATA, Toshio ENDO, Naoya MARUYAMA, and Satoshi MATSUOKA. -\newblock 性能モデルに基づく cpu 及び gpu を併用する効率的な fft ライブラリ. -\newblock 情報処理学会論文誌コンピューティングシステム, 2008. - -\bibitem{cell} -Sony Corporation. -\newblock Cell broadband engine architecture. -\newblock 2005. - -\bibitem{opencl} -Aaftab Munshi and Khronos OpenCL~Working Group. -\newblock The opencl specification version 1.0. -\newblock 2007. - -\bibitem{starpu} -{C{\'e}dric Augonnet, Samuel Thibault, Raymond Namyst, Pierre-Andr{\'e} - Wacrenier}. -\newblock {StarPU: A Unified Platform for Task Scheduling on Heterogeneous - Multicore Architectures}. -\newblock {\em Concurrency and Computation: Practice and Experience, Special - Issue: Euro-Par 2009}, Vol.~23, pp. 187--198, February 2011. - -\bibitem{cuda} -{CUDA}. -\newblock {https://developer.nvidia.com/category/zone/cuda-zone/}. - \end{thebibliography} diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r 4a4d4ef632d0 -r f9b73e12a52f paper/master_paper.tex --- a/paper/master_paper.tex Mon Feb 23 17:09:12 2015 +0900 +++ b/paper/master_paper.tex Mon Feb 23 19:12:19 2015 +0900 @@ -10,7 +10,7 @@ \jtitle{マルチプラットフォーム対応\\並列プログラミングフレームワーク} %\etitle{supporting multiplatform of parallel programming framework} \etitle{Multi-Platform Framework For Parallel Programming} -\year{平成26年度 3月} +\year{平成26年度} \affiliation{\center% \includegraphics[clip,keepaspectratio,width=.15\textwidth] {images/u-ryukyu-Mark.eps}\\